[数据结构与算法]关联规则——FP-growth算法

FP-growth算法

FP-growth是频繁模式的缩写，直接上例子：

下表是所示数据的清单，第一列为购买的id，第二列为物品的项目，1号购物id，它购买的商品是I1、I2、I5

Tid	Items
1	I1, I2, I5
2	I2, I4
3	I2, I3
4	I1, I2, I4
5	I1, I3
6	I2, I3
7	I1, I3
8	I1, I2, I3, I5
9	I1, I2, I3

构建FP树

1、统计各元素出现频率：扫描数据的集合，对每个商品进行统计计数：

I1	I2	I3	I4	I5
6	7	6	2	2

2、支持度过滤：设定最小的支持度，这里可以直接理解为商品最少出现的次数，人为设置为2

3、元素项降序排序：按照商品数目降序的规则重排数据集，对于计数的数目小于2的需要删除，结果为下表

I2	I1	I3	I4	I5
7	6	6	2	2

4、重排后项目集：重新调整物品清单，按照次数重排顺序，注意如果这边遇到元素的数量一样的时候按照关键字(比如26英文字母那就按照Z开始降序)降序排列，这种重排会影响后续的树的结构：

Tid	Items
1	I2, I1, I5
2	I2, I4
3	I2, I3
4	I2, I1, I4
5	I1, I3
6	I2, I3
7	I1, I3
8	I2, I1, I3, I5
9	I2, I1, I3

5、构建FP树

NUll作为根节点，加入第一条清单（I2、I1、I5）

继续加入第二条（I2、I4）

注意出现相同节点且相同路径就累加数目，比如I2相同那就增加I2的频数

最后全部加入3-9清单，得到FP树,其实这边还省略了一部分，相同物品但是在不同路径也是有关联的（比如I2下的I1：4劲额另外的路径I1：2也是有link相连的）

从FP树中挖掘频繁项集

条件模式基：头部链表中某一点的前缀路径集合就是条件模式基，条件模式基的值取决于末属节点的值（比如I5的条件模式基就是（I2 I1），（I2 I1 I3））

1、对头部链表进行降序排序，已降序

2、对头部链表进行由小到大的遍历，得到条件模式基，同时获得一个频繁项集，条件模式基的值取决于末尾节点的值

元素	频数
I2	7
I1	6
I3	6
I4	2
I5	2

比如：从I5开始遍历，I5节点加入频繁项集，找到以I5节点为末尾的路径如下：（I2、I1、I5），（I2、I1、I3、I5），去掉I5节点，得到条件模式基<左边是路径，右边是值>，[I2,I1]:1、[I2,I1,I3]:1

条件FP树：以条件模式基作为数据集构造的FP树叫做条件FP树

3、条件模式基继续构造条件FP树

比如上述的I5条件模式基构建FP树，I3：1不符合支持度舍去，I2：2，I1：2，和模式后缀I5取并集得到支持度大于2的频繁模式

得到频繁项集和之前频繁项集组合起来，作为最终结果，如下表