关联规则挖掘:FP-Growth算法

jopen 3年前

FP-Growth算法不同于Apriori算法的“产生-测试”模型,而是使用一种称作FP树的紧凑数据结构组织数据,并直接从该结构中提取频繁项集。

FP-Growth算法步骤:

1)导出频繁一项集。

数据库的第一次扫描与Apriori相同,它导出频繁1项集的集合和支持度计数。频繁项的集合按支持度计数的递减序排列。结果列表记作L。

2)构造FP树

然后,FP树的构造如下。首先,创建树的根节点,用“null”标记。第二次扫描数据库D。每个事务中的项按L中的次序处理(即按支持度计数递减序)并对每个事务创建一个分枝。一般地,当为一个事务考虑增加分枝时,沿着共同前缀上的每个节点的计数增加1,为在前缀后的项创建节点和链接。

为方便树遍历,创建一个项头表,使每项通过一个节点链指向它在树中的位置。这样,数据库频繁模式的挖掘问题就转换成挖掘FP树问题。

3)挖掘FP树

FP树的挖掘过程如下。由每个长度为1的频繁模式(初始后缀模式)开始,构造它的条件模式基(一个“子数据库”,由FP树中与后缀模式一起出现的前缀路径集组成),然后,构造它的条件FP树,并递归地对该树进行挖掘。模式增长通过后缀模式与条件FP树产生的频繁模式连接实现。

来自: http://blog.csdn.net//kingzone_2008/article/details/17010443