资源描述：
《Apriori与FP-growth与ECLAT算法比较分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、Apriori算法、FP-growth算法和Eclat算法比较分析1、关联分析关联分析是在大规模数据集中寻找有趣关系的任务。这些关系可以有两种形式：频繁项集、关联规则。频繁项集是经常出现在一块儿的物品的集合，关联规则暗示两种物品之间可能存在很强的关系。下面用一个例子来说明：图1给出了某个杂货店的交易清单。交易号码商品0豆奶，莴苣1莴苣，尿布，葡萄酒，甜菜2豆奶，尿布，葡萄酒，橙汁3莴苣，豆奶，尿布，葡萄酒4莴苣，豆奶，尿布，橙汁频繁项集是指那些经常出现在一起的商品集合，图中的集合{葡萄酒,尿布,豆奶}就是频繁项集的一个例子
2、。从这个数据集中也可以找到诸如尿布->葡萄酒的关联规则，即如果有人买了尿布，那么他很可能也会买葡萄酒。2、Apriori算法Apriori算法使用频繁项集的先验知识，使用一种称作逐层搜索的迭代方法，k项集用于探索(k+1)项集。首先，通过扫描事务（交易）记录，找出所有的频繁1项集，该集合记做L1，然后利用L1找频繁2项集的集合L2，L2找L3，如此下去，直到不能再找到任何频繁k项集。最后再在所有的频繁集中找出强规则，即产生用户感兴趣的关联规则。用下面的实例具体实现Apriori算法：上图为某商场的交易记录，共有9个事务，利
3、用Apriori算法寻找所有的频繁项集的过程如下:详细介绍下候选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中删除。注意，由于Apr
4、iori算法使用逐层搜索技术，给定候选k项集后，只需检查它们的（k-1）个子集是否频繁。将Apriori算法应用于Mushroom.dat数据集时：E:/DataMiningSample/FPmining/Mushroom.datthreshold:0.25共用时：54015ms共有5545项频繁模式E:/DataMiningSample/FPmining/Mushroom.datthreshold:0.2共用时：991610ms共有53663项频繁模式由仿真实验结果可知Apriori算法对Mushroom.dat挖掘出来
5、的频繁模式及支持度、频繁模式总数正确，但是算法速度很慢。这种算法虽然比遍历的方法要好很多，但其空间复杂度还是非常高的，尤其是L1比较大时，L2的数量会暴增。每次增加频繁项集的大小，Apriori算法都会重新扫描整个数据集，开销也非常大。即便如此apriori算法在很多场景下也足够用。在R语言中使用arules包来实现此算法（封装的是C实现，只要装载的sparsematrix可以载入内存，support设置合理，速度非常快）。3、FP-growth算法FP-growth算法基于Apriori构建，可以不用每次都扫描全表，而是
6、用一个简洁的数据结构（压缩之后的数据库）把整个数据库的信息都包含进去，通过对数据结构的递归就完成整个频繁模式的挖掘，只对数据库进行两次扫描。所以运算速度优于Apriori算法。这个算法因为数据结构的size远远小于原始的数据库，所有的数据操作可以完全在内存中计算，挖掘速度就可以大大提高。具体的算法步骤如下：（1）、读取数据库，构造频繁1项集及FP-tree（2）、遍历FP-tree的头表，对于每个频繁项x，累积项x的所有前缀路径形成x的条件模式库CPB（3）、对CPB上每一条路径的节点更新计数为x的计数，根据CPB构造条件
7、FP-tree（4）、从条件FP-tree中找到所有长路径，对该路径上的节点找出所有组合方式，然后合并计数（5）、将（4）中的频繁项集与x合并，得到包含x的频繁项集（6）、循环，直到遍历头表中的所有项使用上述步骤，对Mushroom.dat数据集做频繁模式挖掘的结果如下：虽然FP－growth算法已经算是关联规则挖掘算法中较为高效的一种算法，但还是存在着一些不足：（1）为满足FP－tree的构建和频繁项集的挖掘，FP－tree中节点结构需要设计大量的指针；（2）生成的频繁项集存在过多的冗余信息；（3）频繁项头表的遍历耗费了
8、过多的时间。4、Eclat算法Eclat算法是一种深度优先算法,采用垂直数据表示形式,在概念格理论的基础上利用基于前缀的等价关系将搜索空间(概念格)划分为较小的子空间(子概念格)。Eclat算法加入了倒排的思想，加快频繁集生成速度，其算法思想是由频繁k项集求交集，生成候选k+1项集。对候选k+1项集做裁
