Apriori算法的Python实现

Apriori算法是数据挖掘中频发模式挖掘的鼻祖，从60年代就开始流行，其算法思想也十分简单朴素，首先挖掘出长度为1的频繁模式，然后k=2 将这些频繁模式合并组成长度为k的频繁模式，算出它们的频繁次数，而且要保证其所有k-1长度的子集也是频繁的，值得注意的

Apriori算法是数据挖掘中频发模式挖掘的鼻祖，从60年代就开始流行，其算法思想也十分简单朴素，首先挖掘出长度为1的频繁模式，然后k=2

将这些频繁模式合并组成长度为k的频繁模式，算出它们的频繁次数，而且要保证其所有k-1长度的子集也是频繁的，值得注意的是，为了避免重复，合并的时候，只合并那些前k-2个字符都相同，而k-1的字符一边是少于另一边的。

以下是算法的Python实现：

__author__ = 'linfuyuan'
min_frequency = int(raw_input('please input min_frequency:'))
file_name = raw_input('please input the transaction file:')
transactions = []


def has_infrequent_subset(candidate, Lk):
 for i in range(len(candidate)):
 subset = candidate[:-1]
 subset.sort()
 if not ''.join(subset) in Lk:
 return False
 lastitem = candidate.pop()
 candidate.insert(0, lastitem)
 return True


def countFrequency(candidate, transactions):
 count = 0
 for transaction in transactions:
 if transaction.issuperset(candidate):
 count += 1
 return count


with open(file_name) as f:
 for line in f.readlines():
 line = line.strip()
 tokens = line.split(',')
 if len(tokens) > 0:
 transaction = set(tokens)
 transactions.append(transaction)
currentFrequencySet = {}
for transaction in transactions:
 for item in transaction:
 time = currentFrequencySet.get(item, 0)
 currentFrequencySet[item] = time + 1
Lk = set()
for (itemset, count) in currentFrequencySet.items():
 if count >= min_frequency:
 Lk.add(itemset)
print ', '.join(Lk)

while len(Lk) > 0:
 newLk = set()
 for itemset1 in Lk:
 for itemset2 in Lk:
 cancombine = True
 for i in range(len(itemset1)):
 if i < len(itemset1) - 1:
 cancombine = itemset1[i] == itemset2[i]
 if not cancombine:
 break
 else:
 cancombine = itemset1[i] < itemset2[i]
 if not cancombine:
 break
 if cancombine:
 newitemset = []
 for char in itemset1:
 newitemset.append(char)
 newitemset.append(itemset2[-1])
 if has_infrequent_subset(newitemset, Lk) and countFrequency(newitemset, transactions) >= min_frequency:
 newLk.add(''.join(newitemset))
 print ', '.join(newLk)
 Lk = newLk