《机器学习实战》12.1 FP树：用于编码数据集的有效方式

FP-growth算法

优点：一般要快于Apriori缺点：实现比较困难，在某些数据集上性能会下降适用数据类型：标称型数据

FP-growth算法将数据存储在一种称为FP树的紧凑数据结构中。FP代表频繁模式（Frequent Pattern）。一棵FP树看上去与计算机科学中的其他树结构类似，但是它通过链接（link）来连接相似元素，被连起来的元素项可以看成一个链表。图12-1给出了FP树的一个例子。

图12-1　一棵FP树，看上去和一般的树没什么两样，包含着连接相似节点的链接

同搜索树不同的是，一个元素项可以在一棵FP树中出现多次。FP树会存储项集的出现频率，而每个项集会以路径的方式存储在树中。存在相似元素的集合会共享树的一部分。只有当集合之间完全不同时，树才会分叉。 树节点上给出集合中的单个元素及其在序列中的出现次数，路径会给出该序列的出现次数。上面这一切听起来可能有点让人迷糊，不过不用担心，稍后就会介绍FP树的构建过程。

相似项之间的链接即节点链接（node link），用于快速发现相似项的位置。为了打消读者的疑惑，下面通过一个简单例子来说明。表12-1给出了用于生成图12-1中所示FP树的数据。

表12-1　用于生成图12-1中FP树的事务数据样例

在图12-1中，元素项z出现了5次，集合{r,z}出现了1次。于是可以得出结论：z一定是自己本身或者和其他符号一起出现了4次。我们再看下z的其他可能性。集合{t,s,y,x,z}出现了2次，集合{t,r,y,x,z}出现了1次。元素项z的右边标的是5，表示z出现了5次，其中刚才已经给出了4次出现，所以它一定单独出现过1次。通过观察表12-1看看刚才的结论是否正确。前面提到{t,r,y,x,z}只出现过1次，在事务数据集中我们看到005号记录上却是{y,r,x,z,q,t,p}。那么，q和p去哪儿了呢？

这里使用第11章给出的支持度定义，该指标对应一个最小阈值，低于最小阈值的元素项被认为是不频繁的。如果将最小支持度设为3，然后应用频繁项分析算法，就会获得出现3次或3次以上的项集。上面在生成图12-1中的FP树时，使用的最小支持度为3，因此q和p并没有出现在最后的树中。

FP-growth算法的工作流程如下。首先构建FP树，然后利用它来挖掘频繁项集。为构建FP树，需要对原始数据集扫描两遍。第一遍对所有元素项的出现次数进行计数。记住第11章中给出的Apriori原理，即如果某元素是不频繁的，那么包含该元素的超集也是不频繁的，所以就不需要考虑这些超集。数据库的第一遍扫描用来统计出现的频率，而第二遍扫描中只考虑那些频繁元素。

FP-growth的一般流程

1. 收集数据：使用任意方法。
2. 准备数据：由于存储的是集合，所以需要离散数据。如果要处理连续数据，需要将它们量化为离散值。
3. 分析数据：使用任意方法。
4. 训练算法：构建一个FP树，并对树进行挖据。
5. 测试算法：没有测试过程。
6. 使用算法：可用于识别经常出现的元素项，从而用于制定决策、推荐元素或进行预测等应用中。