[comment]: # 机器学习实战 - 读书笔记(12) - 使用FP-growth算法来高效发现频繁项集
前言
最近在看Peter Harrington写的“机器学习实战”，这是我的学习心得，这次是第12章 - 使用FP-growth算法来高效发现频繁项集。
基本概念
FP-growth算法
FP-growth算法的性能很好，只需要扫描两次数据集，就能生成频繁项集。但不能用于发现关联规则。
我想应该可以使用Apriori算法发现关联规则。
FP代表频繁模式（Frequent Pattern）。
条件模式基（conditional pattern base）。
条件模式基是以所查找元素项为结尾的路径集合。每一条路径其实都是一条前缀路径（prefix path）。
一条前缀路径是介于所查找元素项与树根节点之间的所有内容。
FP-growth算法 - 用途
快速生成频繁项集
在一批有共性的文章中找到经常出现的匹配词汇（共现词），并进一步发现关联规则。可以用于输入自动补全功能。
发现数据中的共性。比如，可以找到，哪类用户喜欢哪些文章。
核心算法解释
FP-growth算法：生成频繁项集
FP-growth算法 - Step 1：生成FP树
输入
数据集[数据，出现次数]
注：出现次数默认为1。在第二步的时候，会再次用到这个方法，这是出现次数就用其用途了。
最小支持度
输出
FP树：FPTree
FPTree的根节点为项名为null的节点。
头指针表： headerTable
Tree Node 的数据结构
name : 项名
count ： 其路径在数据集中出现的频率
nodeLink ： 指向在FP树下一个同项名的项。
parent : 父节点
children : 子节点
Header Table Item 的数据结构
name : 项名
count ： 在数据集中出现的频率
nodeLink ： 指向在FP树第一个同项名的项。
逻辑过程
输入
sample 数据集
| 事务ID | 事务中的项集 |
|---|---|
| 1 | 'a', 's', 'w', 'x' |
| 2 | 'a', 'd', 's' |
| 3 | 'a', 'w' |
| 4 | 'a', 'x' |
| 5 | 'a', 'd', 'w' |
| 6 | 'a', 'e', 's' |
最小支持度为3
Step 1: 生成Header Table。
遍历数据集，获得每个元素项的出现频率
去掉不满足最小支持度的元素项。
结果如下：
| 元素项 | 出现频率 |
|---|---|
| a | 6 |
| s | 3 |
| w | 3 |
注: 项d,e,x被去掉了，由于它们的出现频率小于最小支持率3。
Step 2: 生成FP Tree。
遍历数据集，
对当前项集，去掉不在Header Table中的项。
对当前项集，按照在Header Table中出现频率从大到小排序。
加入到FP Tree()， 并且对每项，更新Header Table Item或者Tree Node的NodeLink属性。
去掉不在Header Table中的项的结果：
| 事务ID | 事务中的项集 | 过滤并排序后的项集 |
|---|---|---|
| 1 | 'a', 's', 'w', 'x' | 'a', 's', 'w' |
| 2 | 'a', 'd', 's' | 'a', 's' |
| 3 | 'a', 'w' | 'a', 'w' |
| 4 | 'a', 'x' | 'a' |
| 5 | 'a', 'd', 'w' | 'a', 'w' |
| 6 | 'a', 'e', 's' | 'a' |
把处理过的项集加入 FP Tree 的过程：
按照路径找，如果有count++，如果没有增加一个节点，count=1
对新增加的节点，连接到上一个同项集或者header Table的项集的NodeLinker上。
示意图如下：
FP树的构建过程
Ø
Ø
Add {a,s,w}
a:1
s:1
w:1
a:6
s:3
w:3
Ø
a:2
s:2
w:1
Add {a,s}
Ø
a:3
s:2
w:1
Add {a,w}
w:1
Header Table
最终的结果如下：(输出的FP树和头指针表)
FP树和Header Table的最终结果
Ø
a:6
s:3
w:1
w:2
Header Table
a:6
s:3
w:3
FP-growth算法 - Step 2：生成频繁项集
输入
FP树：PF Tree
头指针表： header Table
最小支持度
前缀项集: 初始值为Empty List (输出)
频繁项集List： 初始值为Empty List (输出)
输出
无
逻辑过程
对Header Table的项，按照count从小到大排序
对Header Table的每一元素项：
把当前元素项加入到频繁项集List中。（Header Table中的每个项都是满足最小支持度的）
前缀项集 = 前缀项集 + 当前元素项。
找到已当前元素项的结尾的条件模式基（到根节点的所有路径以及路径的count）。
将条件模式基看成一个数据集（每个数据有一个count数），用生成FP Tree的方法，生成新的FP Tree和Header Table。
注：上一步过滤掉了不满足最小支持度的子项集。(比如：对于元素项w,过滤掉了{s,a})
如果新的Header Table有数据：
使用生成频繁项集的方法（也就是递归调用本方法）继续生成（有n+1个元素项的）频繁项集。
每个元素项的条件模式基
| 元素项 | 条件模式基 |
|---|---|
| a | {}:6 |
| s | {a}:3 |
| w | {s,a}:1, {a}:2 |
元素项w的FP树和Header Table
注：元素项s和节点s实际上都不存在，因为不满足最小支持度。
元素项w的FP树和Header Table
Ø
a:3
s:1
Header Table
a:3
s:1
参考
Machine Learning in Action by Peter Harrington
