Press "Enter" to skip to content

辨析Apriori与FP-Growth

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

写在前面:Apriori算法与FP-Growth算法都是很经典的挖掘算法,自己也是断断续续地学习这两个算法。本文主要记录自己对这两个算法的理解和区别,有误的地方还请多多指教

 

Apriori算法

 

Apriori 算法使用了逐层搜索的迭代方法,即用 k-项集探索 (k+1)-项集(后续的HUI-Miner、FHN 和UMEpi 等算法都是这个思路)。该算法使用了 向下封闭性(downward closure property) ,即一个频繁项集的所有非空子集也必须是频繁项集。假如项集 A 不满足最小支持度阈值,即 A 不是频繁的,则如果将项集 B 添加到项集 A 中,那幺新项集(AUB)也不可能是频繁的

 

算法步骤

 

 

    1. 扫描数据集,确定每个一元项的支持度,通过计算得到的支持度,就可以得到所有频繁 1-项集的集合 F1 ;

 

    1. 使用上一次发现的 (k-1)-项集,两两组合产生新的候选 k-项集;

 

    1. 对得到的候选项集计算其支持度,再扫描一遍数据库,使用自己函数确定包含在每一个交易项t中的所有候 k-项集;

 

    1. 删除支持度小于阈值的所有候选项集;

 

    1. 重复 2~4 步骤,直到没有任何新的频繁项集产生时,算法终止

 

 

 

缺点

 

从上面的算法步骤可以看出,1)Apriori算法需要多次扫描数据集从候选项集中计算频繁项集的支持度,当数据集很大的时候,I/O开支就变得不可接受了;2)其次,在产生候选项集上是很庞大的,一般认为是 呈指数级增长 ,这对内存消耗和时间开支无疑是不可接受的

 

优点

 

毋庸置疑,Apriori算法作为最早也是最经典的频繁项集挖掘算法,使用 先验性质 ,开创了一个新的挖掘思路;而且简单易理解,数据集要求低;最后,该算法在实际中得到广泛的运用,能够挖掘出很多有用的关联规则

 

FP-Growth算法

 

FP-Growth算法 针对 Apriori算法 的种种问题作出了许多改进,尤其是设计的 FP-Tree 结构来存储关键信息,借用 Tree 可以避免再去扫描数据集来确认结果(后续的 UP-Growth 、 UP-GNV 和RFM-Growth 等算法都用到了这个存储结构)。通过递归调用 的方法可直接产生频繁模式,因此在整个发现过程中也不需产生候选模式

 

算法步骤

 

 

    1. 扫描数据集,以频繁一元项为基础构建有序项表头,并在第二次扫描数据集过程中对各个项元素进行排序;

 

    1. 根据项表头和排序调整后的数据集,构建 FP-Tree存储结构

 

    1. 按项表头内元素自底向上(同时也意味着FP-Tree自底向上)进行构建高阶项集,每一个高阶项集就是一条树枝路径

 

 

 

缺点

 

剪枝不够彻底,用到的边界值其实还不够贴近真正的支持度

 

优点

 

FP-Tree是数据集的浓缩,里面不包含非频繁一元项的数据;每次查找频繁项集也不需要重复扫描数据集,只需要固定一个元素,从下往上依次遍历各个节点直到root构造出一棵 sub FP-Tree( 投影 )

 

总结

 

在核心思路上,

Apriori算法是 使用两个低阶的频繁项集构建高阶的频繁项集
FP-Growth算法是 使用一个低阶频繁项集作为前提,筛选出包含这个频繁项集的所有高阶频繁项集

在实现过程中,

Apriori算法需要多次扫描数据集来确认频繁项集的支持度
FP-Growth算法通过固定一个节点构造更多的子FP-Tree来挖掘频繁项集

两个算法代表了不同的挖掘思路,根据这些思路可以结合不同的剪枝策略、存储结构等得到更高效的算法

 

Ps. 除了研究这些算法的性能差异性,更多的还是要理清来龙去脉,为什幺这个算法能够得到大家的认可?为什幺大家不使用其它看起来性能比它好得多的算法?

Be First to Comment

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注