Apriori算法实例

Apriori算法与实例

R. Agrawal 和 R. Srikant于1994年在文献【2】中提出了Apriori算法，该算法的描述如下：

下面是一个具体的例子，最开始数据库里有4条交易，{A、C、D}，{B、C、E}，{A、B、C、E}，{B、E}，使用min_support=2作为支持度阈值，最后我们筛选出来的频繁集为{B、C、E}。



上述例子中，最值得我们从L2到C3的这一步。这其实就是在执行伪代码中第一个蓝色框条所标注的地方：Ck+1=GenerateCandidates(Lk)，具体来说在Apriori算法中，它所使用的策略如下：


可见生成策略由两部分组成，首先是self-joining部分。例如，假设我们有一个L3={abc, abd, acd, ace, bcd}（注意这已经是排好序的}。选择两个itemsets，它们满足条件：前k-1个item都相同，但最后一个item不同，把它们组成一个新的Ck+1的项集c。如下图所示，{abc}和{abd}组成{abcd}，{acd}和{ace}组成{acde}。生成策略的第二部分是pruning。对于一个位于Ck+1中的项集c，s是c的大小为k的子集，如果s不存在于Lk中，则将c从Ck+1中删除。如下图所示，因为{acde}的子集{cde}并不存在于L3中，所以我们将{acde}从C4中删除。最后得到的C4，仅包含一个项集{abcd}。

回到之前的例子，从L2到C3的这一步，我们就只能获得{B、C、E}。以上便是Apriori算法的最核心思想。

 

from:https://blog.csdn.net/baimafujinji/article/details/53456931