数据挖掘关联分析——FP-Growth挖掘频繁项集

挖掘频繁项集主要有两类方法，一类是Apriori算法，另一类是FP-Growth算法。本文介绍的FP-Growth算法采用了高效的树结构存储数据，然后从树结构中直接挖掘频繁项集。其一方面较Apriori算法存储小，另一方面也比Apriori算法快，但缺点是在某些数据集上性能会下降。

1.1 关联分析基础知识

关联分析一些基础知识如下。
TID Items
001 Cola, Egg, Ham
002 Cola, Diaper, Beer
003 Cola, Diaper, Beer, Ham
004 Diaper, Beer
1、事务：每一条交易称为一个事务。
2、项：交易的每一个物品称为一个项，例如Cola、Egg等。
3、项集：包含零个或多个项的集合叫做项集，例如{Cola, Egg, Ham}。
4、k−项集：包含k个项的项集叫做k-项集，例如{Cola}叫做1-项集，{Cola, Egg}叫做2-项集。
5、支持度计数：一个项集出现在几个事务当中，它的支持度计数就是几。例如{Diaper, Beer}出现在事务 002、003和004中，所以它的支持度计数是3。
6、支持度：支持度计数除于总的事务数。例如上例中总的事务数为4，{Diaper, Beer}的支持度计数为3，所以它的支持度是3÷4=75%，说明有75%的人同时买了Diaper和Beer。
7、频繁项集：支持度大于或等于某个阈值的项集就叫做频繁项集。例如阈值设为50%时，因为{Diaper, Beer}的支持度是75%，所以它是频繁项集。
8、前件和后件：对于规则{Diaper}→{Beer}，{Diaper}叫做前件，{Beer}叫做后件。
9、置信度：对于规则{Diaper}→{Beer}，{Diaper, Beer}的支持度计数除于{Diaper}的支持度计数，为这个规则的置信度。例如规则{Diaper}→{Beer}的置信度为3÷3=100%。说明买了Diaper的人100%也买了Beer。
10、强关联规则：大于或等于最小支持度阈值和最小置信度阈值的规则叫做强关联规则。关联分析的最终目标就是要找出强关联规则。

1.2 FP树的构建

假设原数据如下：
事务 项集
1 r,z,h,j,p
2 z,y,x,w,v,u,t,s
3 z
4 r,x,n,o,s
5 y,r,x,z,q,t,p
6 y,z,x,e,q,s,t,m
首先，我们人为规定最小支持度为3。对每一个项进行频次统计，将支持度小于3的项剔除，再将剩余项按照频次由大到小进行排序得到（频次相同的按照字母表顺序排列）：
项 频次
z 5
x 4
r 3
s 3
t 3
y 3
然后，将原数据中每一个事务剩余的项，根据上面字母的排序进行排序，得到新的数据如下：
事务 项集
1 z,r
2 z,x,s,t,y
3 z
4 x,r,s
5 z,x,r,t,y
6 z,x,s,t,y
构建FP树步骤如下：

FP树构建完成！

1.3 挖掘FP树中的频繁项集

1 抽取条件模式基

条件模式基，就是每一个频繁项的前缀路径的集合，用来构建条件FP树。此例中为：

2 构建条件FP树

利用刚才的每一个频繁项的条件模式基，创建条件FP树。该例中有6个频繁项，则会有6棵条件FP树。以t为例，输入的是对应的条件模式基：{z,x,s}:2, {z,x,r}:1。对输入的条件模式基，首先用最小支持度进行过滤。s及r是条件模式基的一部分，但是它们并不属于条件FP树，因为在当前的输入中，s和r不满足大于等于最小支持度的条件。

3 递归查找频繁项集

方框内的即为输入为t条件下所发现的频繁项集。