python哪个包实现apriori

python哪个包实现apriori

如连接中的例子，虽然新的{I1, I2, I3, I4}项集满足 子集{I1, I2, I3}; {I1, I2, I4} 都是频繁项集，但其他子集也得满足，这里特指剩下两个{I1, I3, I4},{I2, I3, I4}。所以验证一下他们，如果他们不满足，可根据定理1，新的项集也肯定不频繁。

所以剪枝的过程就是验证Ck中所有项集的所有k-1子集是否都频繁（只要看看他们是不是在Lk-1集合中即可），这样虽然要检查很多遍，但不需要对整个数据库进行遍历就能筛去许多不满足的情况。

上述方法是经典的Apriori算法，这两个步骤在k较高（3或以上）时效果非常好，因为商品同时存在的可能性会随k增大显著减小。

但是在k=2的时候（k=1用不到Apriori算法，必须遍历一遍数据库，相当于“链引发”），因为1项集一般都是频繁的，所以上述两个步骤基本上相当于没有用，还得遍历C(n,2)次数据库，n为频繁1项集的数量。

apriori算法是数据挖掘中频发模式挖掘的鼻祖，从60年代就开始流行，其算法思想也十分简单朴素，首先挖掘出长度为1的频繁模式，然后k=2 将这些频繁模式合并组成长度为k的频繁模式，算出它们的频繁次数，而且要保证其所有k-1长度的子集也是频繁的，值得注意的是，为了避免重复，合并的时候，只合并那些前k-2个字符都相同，而k-1的字符一边是少于另一边的。 以下是算法的python实现： [python] view plain copy print? __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