关联规则挖掘算法Aprior和FPGrowth对比与改进

发布时间：2020-12-14 02:01:40 所属栏目：大数据来源：网络整理

导读：Aprior算法和FPGrowth算法同属于关联规则挖掘算法，但Aprior是基于广度优先的，而FPGrowth是基于深度优先的，即Aprior算法需要建立K项集，然后扫描数据库；而FPGrowth算法则是扫描数据库，然后查找频繁项集。 Aprior算法 Aprior算法的原理和实现参见http://w

Aprior算法和FPGrowth算法同属于关联规则挖掘算法，但Aprior是基于广度优先的，而FPGrowth是基于深度优先的，即Aprior算法需要建立K项集，然后扫描数据库；而FPGrowth算法则是扫描数据库，然后查找频繁项集。

Aprior算法

Aprior算法的原理和实现参见http://www.voidcn.com/article/p-wqkmvgsj-sy.html和http://www.tuicool.com/m/articles/MFZnuuA
但Aprior算法每生成一轮K项集，就需要扫描数据库一次，不仅增加了数据库的负担，并且运算速度慢，故而对Aprior算法进行如下改进：
1.基于hash表的项集计数
将每个项集通过相应的hash函数映射到hash表中的不同的桶中,将桶中的项集计数和最小自信度confidence进行比较，若小于confidence,则将该项集删除。然后根据已经计算的项集生成更多项数的项集，依次映射到哈希表中。这样的方式可以减少项集的存储数量。
2.动态项集计数
在扫描的不同点添加候选项集，这样，如果一个候选项集已经满足最少支持度，则在可以直接将它添加到频繁项集，而不必在这次扫描的以后对比中继续计算。
3.对给定数据的子集进行挖掘
选取原始数据的一个样本进行数据挖掘，这是通过牺牲精确度来降低算法运行开销，样本的大小以恰好放入内存为宜。同时，最小支持度可以适当降低来减少遗漏的频繁项集。
4.事务压缩（压缩进一步迭代的事务数）
不包含任何k-项集的事务不可能包含任何(k+1)-项集，这种事务在下一步的计算中可以加上标记或删除

FPGrowth

FPGrowth算法的原理和具体实现参见http://www.cnblogs.com/fengfenggirl/p/associate_fpgowth.html，FPGrowth算法只需扫描两次数据库即可。FPGrowth的并行化运算参见http://www.voidcn.com/article/p-wohrntce-gq.html

关联规则评价

有时候，强规则（即同时满足支持度和自信度）并不能成功过滤掉我们并不感兴趣的规则，所以需要新的评价标准
1.相关性系数lift

l i f t = p （ A \cap B ） P ( A ) ? P ( B ) = p ( A ) ? p ( B | A ) P ( A ) ? P ( B ) = c o n f i d e n c e ( A ? > B ) s u p p o r t ( B )

如果lift(A,B)>1表示A、B呈正相关，lift(A,B)<1表示A、B呈负相关，lift(A,B)=1表示A、B不相关（独立）。实际运用中，正相关和负相关都是我们需要关注的，而独立往往是我们不需要的
2.全自信度

all_confidence=p(A∩B)max{p(A),p(B)}=min{p(A|B),p(B|A)}=min{confidence(A),confidence(B)}

3.最大自信度

all_confidence=max{confidence(A),confidence(B)}

4.Kulc

k u l c = c o n f i d e n c e ( A ) + c o n f i d e n c e ( B ) 2

5.cosine(A,B)

c o s i n e (A, B) = p ( A \cap B ) p ( A ) ? p ( B ) ? ? ? ? ? ? ? ? ? \sqrt = c o n f i d e n c e (A) ? c o n f i d e n c e (B) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? \sqrt

6.卡方系数

χ = \sum （ o b s e r v e d ? e x c e p t e d ） 2 e x c e p t e d

公式中的observed表示数据的实际值,expected表示期望值

上面表格的括号中表示的是期望值，(买影片，买游戏)的期望值E=6000*(7500/10000)=4500，总体记录中有75%的人买影片，而买游戏的有6000人，于是我们期望这6000人中有75%(即4500)的人买影片.
卡方系数需要查表才能确定值的意义，基于置信水平和自由度(r-1) (c-1)=(行数-1)(列数-1)=1，查表得到自信度为(1-0.001)的值为6.63，555.6大于6.63，因此拒绝A、B独立的假设，即认为A、B是相关的，而expected(买影片，买游戏)=4500>4000,因此认为A、B呈负相关。

在以上几种方法中，全自信度、最大自信度、Kulc、cosine，Leverage是不受空值影响的，这在处理大数据集是优势更加明显。推荐使用kulc准则和不平衡因子结合的方法

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!