-
Notifications
You must be signed in to change notification settings - Fork 0
/
Apriori.py
118 lines (94 loc) · 3.76 KB
/
Apriori.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
from csv import reader
from collections import defaultdict
from itertools import chain, combinations
def powerset(s):
return chain.from_iterable(combinations(s, r) for r in range(1, len(s)))
def getFromFile(fname):
itemSets = []
itemSet = set()
with open(fname, 'r') as file:
csv_reader = reader(file)
for line in csv_reader:
line = list(filter(None, line))
record = set(line)
for item in record:
itemSet.add(frozenset([item]))
itemSets.append(record)
return itemSet, itemSets
def getAboveMinSup(itemSet, itemSetList, minSup, globalItemSetWithSup):
freqItemSet = set()
localItemSetWithSup = defaultdict(int)
for item in itemSet:
for itemSet in itemSetList:
if item.issubset(itemSet):
globalItemSetWithSup[item] += 1
localItemSetWithSup[item] += 1
for item, supCount in localItemSetWithSup.items():
support = float(supCount / len(itemSetList))
if(support >= minSup):
freqItemSet.add(item)
return freqItemSet
def getUnion(itemSet, length):
return set([i.union(j) for i in itemSet for j in itemSet if len(i.union(j)) == length])
def pruning(candidateSet, prevFreqSet, length):
tempCandidateSet = candidateSet.copy()
for item in candidateSet:
subsets = combinations(item, length)
for subset in subsets:
# if the subset is not in previous K-frequent get, then remove the set
if(frozenset(subset) not in prevFreqSet):
tempCandidateSet.remove(item)
break
return tempCandidateSet
def associationRule(freqItemSet, itemSetWithSup, minConf):
rules = []
for k, itemSet in freqItemSet.items():
for item in itemSet:
subsets = powerset(item)
for s in subsets:
confidence = float(
itemSetWithSup[item] / itemSetWithSup[frozenset(s)])
if(confidence > minConf):
rules.append([set(s), set(item.difference(s)), confidence])
return rules
def getItemSetFromList(itemSetList):
tempItemSet = set()
for itemSet in itemSetList:
for item in itemSet:
tempItemSet.add(frozenset([item]))
return tempItemSet
def apriori(fname, minSup, minConf):
C1ItemSet, itemSetList = getFromFile(fname)
# Final result global frequent itemset
globalFreqItemSet = dict()
# Storing global itemset with support count
globalItemSetWithSup = defaultdict(int)
L1ItemSet = getAboveMinSup(
C1ItemSet, itemSetList, minSup, globalItemSetWithSup)
currentLSet = L1ItemSet
k = 2
# Calculating frequent item set
while(currentLSet):
# Storing frequent itemset
globalFreqItemSet[k-1] = currentLSet
# Self-joining Lk
candidateSet = getUnion(currentLSet, k)
# Perform subset testing and remove pruned supersets
candidateSet = pruning(candidateSet, currentLSet, k-1)
# Scanning itemSet for counting support
currentLSet = getAboveMinSup(
candidateSet, itemSetList, minSup, globalItemSetWithSup)
k += 1
rules = associationRule(globalFreqItemSet, globalItemSetWithSup, minConf)
rules.sort(key=lambda x: x[2])
return globalFreqItemSet, rules
if __name__ == "__main__":
freqItemSet, rules = apriori("kaggle.csv", 0.2, 0.4)
for i in freqItemSet:
print(str(i) + " : ")
for j in freqItemSet[i]:
print(j)
print("-----------------------------------------")
print("++++++++++++++++++++++++++++++++++++++++++++++++++++++++")
for i in rules:
print(i)