Apriori与FP-growth与ECLAT算法比较分析.docx

Apriori算法、FP-growth算法和Eclat算法比较分析
1、关联分析
关联分析是在大规模数据集中寻找有趣关系的任务。这些关系可以有两种形式：频繁项集、关联规则。频繁项集是经常出现在一块儿的物品的集合，关联规则暗示两种物品之间可能存在很强的关系。
下面用一个例子来说明：图1给出了某个杂货店的交易清单。
交易号码
商品
0
豆奶，莴苣
1
莴苣，尿布，葡萄酒，甜菜
2
豆奶，尿布，葡萄酒，橙汁
3
莴苣，豆奶，尿布，葡萄酒
4
莴苣，豆奶，尿布，橙汁
频繁项集是指那些经常出现在一起的商品集合，图中的集合{葡萄酒,尿布,豆奶}就是频繁项集的一个例子。从这个数据集中也可以找到诸如尿布->葡萄酒的关联规则，即如果有人买了尿布，那么他很可能也会买葡萄酒。
2、Apriori算法
Apriori算法使用频繁项集的先验知识，使用一种称作逐层搜索的迭代方法，k项集用于探索(k+1)项集。首先，通过扫描事务（交易）记录，找出所有的频繁1项集，该集合记做L1，然后利用L1找频繁2项集的集合L2，L2找L3，如此下去，直到不能再找到任何频繁k项集。最后再在所有的频繁集中找出强规则，即产生用户感兴趣的关联规则。
用下面的实例具体实现Apriori算法：

上图为某商场的交易记录，共有9个事务，利用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中删除。注意，由于Apriori算法使用逐层搜索技术，给定候选k项集后，只需检查它们的（k-1）个子集是否频繁。
将Apriori算法应用于Mushroom.dat数据集时：
E:/DataMiningSample/FPmining/Mushroom.dat threshold: 0.25
共用时：54015ms
共有5545项频繁模式
E:/DataMiningSample/FPmining/Mushroom.dat threshold: 0.2
共用时：991610ms
共有53663项频繁模式
由仿真实验结果可知Apriori算法对Mushroom.dat挖掘出来的频繁模式及支持度、频繁模式总数正确，但是算法速度很慢。这种算法虽然比遍历的方法要好很多，但其空间复杂度还是非常高的，尤其是 L1 比较大时，L2 的数量会暴增。每次增加频繁项集的大小，Apriori算法都会重新扫描整个数据集，开销也非常大。
即便如此 apriori 算法在很多场景下也足够用。在R语言中使用 arules 包来实现此算法（封装的是C实现，只要装载的 sparse matrix 可以载入内存，support 设置合理，速度非常快）。
3、FP-growth算法
FP-growth算法基于Apriori构建，可以不用每次都扫描全表，而是用一个简洁的数据结构（压缩之后的数据库）把整个数据库的信息都包含进去，通过对数据结构的递归就完成整个频繁模式的挖掘，只对数据库进行两次扫描。所以运算速度优于Apriori算法。这个算法因为数据结构的 size 远远小于原始的数据库，所有的数据操作可以完全在内存中计算，挖掘速度就可以大大提高。
具体的算法步骤如下：
（1）、读取数据库，构造频繁1项集及FP-tree
（2）、遍历FP-tree的头表，对于每个频繁项x，累积项x的所有前缀路径形成x的条件模式库CPB
（3）、对CPB上每一条路径的节点更新计数为x的计数，根据CPB构造条件FP-tree
（4）、从条件FP-tree中找到所有长路径，对该路径上的节点找出所有组合方式，然后合并计数
（5）、将（4）中的频繁项集与x合并，得到包含x的频繁项集
（6）、循环，直到遍历头表中的所有项
使用上述步骤，对Mushroom.dat数据集做频繁模式挖掘的结果如下：

虽然FP－growth算法已经算是关联规则挖掘算法中较为高效的一种算法，但还是存在着一些不足：
（1）为满足FP－tree的构建和频繁项集的挖掘，FP－tree中节点结构需要设计大量的指针；
（2）生成的频繁项集存在过多的冗余信息；
（3）频繁项头表的遍历耗费了过多的时间。
4、Eclat算法
Eclat算法是一种深度优先算法,采用垂直数据表示形式,在概念格理论的基础上利用基于前缀的等价关系将搜索空间(概念格)划分为较小的子空间(子概念格)。
Eclat算法加入了倒排的思想，加快频繁集生成速度，其算法思想是 由频繁k项集求交集，生成候选k+1项集 。对候选k+1项集做裁剪，生成频繁k+1项集，再求交集生成候选k+2项集。如此迭代，直到项集归一。
具体实现算法步骤如下：
（1）、一次扫描数据库，获得初始数据。包括频繁1项集，数据库包含的所有items，事务总数（行）transNum，最小支持度minsup=limitValue*trans。
（2）、二次扫描数据库，获得频繁2项集。
（3）、按照Eclat算法，对频繁2项集迭代求交集，做裁剪，直到项集归一。
使用Eclat算法，对mushroom.dat的频繁模式挖掘结果如下：

关联规则算法中的数据通常采用水平数据形式，而采用垂直数据表示的挖掘性能优于水平表示。Eclat算法在项集规模庞大时，交集操作消耗大量时间和系统内存。为此，结合划分思想和突出基于概率的先验约束方法,把数据库中的事务划分成多个非重叠部分,对每一部分采用Eclat算法，减少每次"交"操作时项集的规模,从而减少比较次数。通过基于概率的先验约束，减少产生的局部频繁项集数。这样的设计具有更高的效率。
5、总结
FP-growth算法是一种用于发现数据集中频繁模式的有效方法。FP-growth算法利用Apriori原则，执行更快。Apriori算法产生候选项集，然后扫描数据集来检查它们是否频繁。由于只对数据集扫描两次，因此FP-growth算法执行更快。在FP-growth算法中，数据集存储在一个称为FP树的结构中。FP树构建完成后，可以通过查找元素项的条件基及构建条件FP树来发现频繁项集。该过程不断以更多元素作为条件重复进行，直到FP树只包含一个元素为止。
人们主要通过减少扫描数据库次数以及尽可能产生最少的候选项集对 Apriori算法进行改进优化，而FP-Growth 算法的改进则主要考虑减少构建 FP-growth树产生的消耗以及尽可能千方百计地节省内存，这些算法都只能挖掘单维的布尔型关联规则。虽然改进算法应用在部分传统数据集中取得了成功，但随着现在数据规模越来越大，应用环境越来越复杂，传统改进算法已经不适应时代的发展要求。
然而，传统 Eclat 算法并未充分利用Apriori 先验性质，因此会产生比较多的候选项集。传统Eclat 算法通过不断地循环，逐个比较两Tidset集合中各个项（事务）的值来求交集。
这种求交集算法通俗简单，但随着事务数规模的不断扩大，Tidset 的规模也会不断扩大，导致算法的比较次数成倍增长，最终影响到Eclat 算法的挖掘效率。根据对传统算法的仔细分析，发现其存在如下的问题：
（1）、算法的大量操作消耗在Tidset 的求交集过程上，这是原有算法的主要瓶颈之一；
（2）、求交集操作所使用的Tidset 这种数据表示形式，会占用系统大量的内存空间。
依据Eclat算法存在的不足，将散列表与布尔矩阵相结合，提出了散列布尔矩阵的思想，运用这种新的求交集计算方法来改进传统关联规则Eclat算法，加快支持度计数过程，提高频繁项集挖掘效率。

附录：
I．代码
II．检查报告结果：