Apriori算法例子

《Apriori算法例子》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Apriori算法例子1Apriori介绍Apriori算法使用频繁项集的先验知识，使用一种称作逐层搜索的迭代方法，k项集用于探索(k+1)项集。首先，通过扫描事务（交易）记录，找出所有的频繁1项集，该集合记做L1，然后利用L1找频繁2项集的集合L2，L2找L3，如此下去，直到不能再找到任何频繁k项集。最后再在所有的频繁集中找出强规则，即产生用户感兴趣的关联规则。其中，Apriori算法具有这样一条性质：任一频繁项集的所有非空子集也必须是频繁的。因为假如P(I)<最小支持度阈值，当有元素A添加到I中时，结果项集（A∩I）不可能比I出现次数更多。因此A∩I也不是频繁的。

2、2连接步和剪枝步在上述的关联规则挖掘过程的两个步骤中，第一步往往是总体性能的瓶颈。Apriori算法采用连接步和剪枝步两种方式来找出所有的频繁项集。1）连接步为找出Lk（所有的频繁k项集的集合），通过将Lk-1（所有的频繁k-1项集的集合）与自身连接产生候选k项集的集合。候选集合记作Ck。设l1和l2是Lk-1中的成员。记li[j]表示li中的第j项。假设Apriori算法对事务或项集中的项按字典次序排序，即对于（k-1）项集li，li[1]

3、…..&&(l1[k-2]=l2[k-2])&&(l1[k-1]

4、为什么要压缩CK呢？因为实际情况下事务记录往往是保存在外存储上，比如数据库或者其他格式的文件上，在每次计算候选计数时都需要将候选与所有事务进行比对，众所周知，访问外存的效率往往都比较低，因此Apriori加入了所谓的剪枝步，事先对候选集进行过滤，以减少访问外存的次数。）3Apriori算法实例交易ID商品ID列表T100I1，I2，I5T200I2，I4T300I2，I3T400I1，I2，I4T500I1，I3T600I2，I3T700I1，I3T800I1，I2，I3，I5T900I1，I2，I3上图为某商场的交易记录，共有9个事务，利用Apriori算法寻找所有

5、的频繁项集的过程如下:详细介绍下候选3项集的集合C3的产生过程：从连接步，首先C3={{I1,I2,I3}，{I1,I2,I5}，{I1,I3,I5}，{I2,I3,I4}，{I2,I3,I5}，{I2,I4,I5}}（C3是由L2与自身连接产生）。根据Apriori性质，频繁项集的所有子集也必须频繁的，可以确定有4个候选集{I1,I3,I5}，{I2,I3,I4}，{I2,I3,I5}，{I2,I4,I5}}不可能时频繁的，因为它们存在子集不属于频繁集，因此将它们从C3中删除。注意，由于Apriori算法使用逐层搜索技术，给定候选k项集后，只需检查它们的（k-1）个

6、子集是否频繁。3．Apriori伪代码算法：Apriori输入：D-事务数据库；min_sup-最小支持度计数阈值输出：L-D中的频繁项集方法：L1=find_frequent_1-itemsets(D);//找出所有频繁1项集For(k=2;Lk-1!=null;k++){Ck=apriori_gen(Lk-1);//产生候选，并剪枝Foreach事务tinD{//扫描D进行候选计数Ct=subset(Ck,t);//得到t的子集Foreach候选c属于Ctc.count++;}Lk={c属于Ck

7、c.count>=min_sup}}ReturnL=所有的频繁集；P

8、rocedureapriori_gen(Lk-1:frequent(k-1)-itemsets)Foreach项集l1属于Lk-1Foreach项集l2属于Lk-1If((l1[1]=l2[1])&&(l1[2]=l2[2])&&……..&&(l1[k-2]=l2[k-2])&&(l1[k-1]