如何有效地挖掘频繁项集

　　频繁模式是频繁地出现在数据集中的模式（如项集、子序列或者子结构）。例如，频繁地同时出现在交易数据集中的商品（如牛奶和面包）的集合是频繁项集。
　　一些基本概念
　　支持度：support(A=>B)=P(A并B)
　　置信度：confidence(A=>B)=P(B|A)
　　频繁k项集：如果项集I的支持度满足预定义的最小支持度阈值，则称I为频繁项集，包含k个项的项集称为k项集。
　　算法思想
　　Apriori算法是Agrawal和R. Srikant于1994年提出，为布尔关联规则挖掘频繁项集的原创性算法。通过名字可以看出算法基于这样一个事实：算法使用频繁项集性质的先验知识。apriori算法使用一种成为逐层搜索的迭代算法，其中k项集用于探索（k+1）项集。首先，通过扫描数据库，累计每个项的计数，并搜集满足最小支持度的项，找出频繁1项集的集合。该集合记为L1。然后，使用L1找出频繁2项集的集合L2，使用L2找出L3，如此下去，直到不能再找到频繁k项集。
　　可以想象，该算法基本思路计算复杂度是非常大的。为了提高频繁项集的产生效率，使用先验性质（ 频繁项集的所有非空子集也一定是频繁的；换句话说，若某个集合存在一个非空子集不是频繁项集，则该集合不是频繁项集 ）来压缩搜索空间。
　　如何在算法中使用先验性质？为了理解这一点，我们考察如何使用Lk-1找出Lk，其中k>=2。主要由两步构成：连接步和剪枝步。
　　连接步：为找出Lk，通过将Lk-1与自身相连接产生候选集k项集的集合。该候选集的集合记为Ck。设l1和l2是Lk-1中的项集。记号li[j]表示li的第j项（例如，l1[k-2]表示l1的倒数第2项）。为了有效实现，apriori算法假定事务或项集中的项按字典序排列。对于（k-1）项集li，这意味着把项排序，使得li[1]