-
Notifications
You must be signed in to change notification settings - Fork 0
/
apriori.py
80 lines (67 loc) · 2.46 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
from basicOperation import count
# import time
# merge two itemset (if possible)
def merge(itemset1, itemset2):
newFreqItem = set(itemset1).union(set(itemset2))
if len(newFreqItem) == (len(itemset1)+1):
return newFreqItem
# generate candidates of length (k+1) by merging two frequent itemsets of length k
def generateCandidates(oldCandidates):
newCandidates = set()
for i in range(len(oldCandidates)):
for j in range(i + 1, len(oldCandidates)):
newItemset = merge(oldCandidates[i], oldCandidates[j])
# if merge is success, add it to newCandidate set
if newItemset is not None:
newCandidates.add(tuple(sorted(tuple(newItemset))))
# conver the set to a list
result = list()
for i in newCandidates:
result.append(sorted(i))
return sorted(result)
# check whether a itemset has infrequent subsets
def isFrequentSubset(itemset, old_candidates):
for i in range(len(itemset)):
subset = list(itemset)
del subset[i]
if subset not in old_candidates:
return False
return True
# prune candidates which has infrequent subsets
def prune(candidates, oldCandidates):
afterPrune = list()
for itemset in candidates:
if isFrequentSubset(itemset, oldCandidates):
afterPrune.append(itemset)
return afterPrune
# generate the frequent items of length 1
def length_1_freqItemSet(data, minsup):
items = dict()
for record in data:
for i in record:
if i in items:
items[i] += 1
else:
items[i] = 1
freq_items = list()
for item in items:
if items[item] >= minsup:
freq_items.append([item])
return sorted(freq_items)
# data is a list of transaction, minsup is the minimum support
def aprioriAlgorithm(data, minsup):
# generate frequent itemsets of size 1
candidates = length_1_freqItemSet(data, minsup)
freq_itemsets = list(candidates)
while len(candidates) > 0:
# length K+1 candidates
nextCandidates = generateCandidates(candidates)
# remove infrequent candidates
nextCandidates = prune(nextCandidates, candidates)
# count and kick away infrequent candidate
candidates = list()
for itemSet in nextCandidates:
if count(itemSet, data) >= minsup:
candidates.append(itemSet)
freq_itemsets.append(itemSet)
return freq_itemsets