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

jopen 9年前

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树产生的频繁模式连接实现。