机器学习实战：FP-growth算法之构建FP树

Hello，大家好！我是MPIG2018级研究生黄垚。在上一章节中，我们讨论了从数据集中获取有趣信息的方法，最常用的两种分别是频繁项集和关联规则。同时，我们介绍了发现频繁项集与关联规则的Apriori算法，这一章节我们将深入探索发现频繁项集这一任务，并为大家介绍一种更高效的算法--FP-growth算法。

之前我们介绍的Apriori算法对于每个潜在的频繁项集都会扫描数据集判定给定模式是否频繁，但FP-growth算法只需要对数据库进行两次扫描，因此FP-growth算法的速度要比Apriori算法快。FP-growth算法发现频繁项集的基本过程如下：

（1）构建FP树

（2）从FP树中挖掘频繁项集

今天我们将为大家先介绍一下第一个部分：FP树的构建。我们会讨论FP树的数据结构，然后看一下如何用该结构对数据集编码。

FP-growth算法将数据存储在FP树这种紧凑数据结构中。FP代表频繁模式--(Frequent Pattern)。FP树会存储项集的出现频率，而每个项集会以路径的方式存储在树中。存在相似元素的集合会共享树的一部分。只有当集合之间完全不同时，树才会分叉。树节点上给出集合中单个元素及其在序列中的出现次数。

下面一段代码给出了FP树的节点的类定义：

与其他树结构不同的是，FP树中一个元素可以出现多次，相似元素通过link来相互连接。被连起来的元素可以看成是一个链表，沿着相似项之间的链接(node link),可快速访问FP树中一个给定类型的所有元素。

上文我们提过，构建FP树需要对原始数据集扫描两遍。第一遍扫描统计所有元素项的出现次数。

接着，去掉不满足最小支持度的元素项。

在构建时，读入每个项集并将其添加到一条已经存在的路径中。如果该路径不存在，则创建一条新路径。此时每个事务是一个无序集合。在将集合添加到树之前，需要对每个集合进行排序。排序基于元素项的绝对出现频率来进行。

下面这段代码给出了第二次扫描数据集并对元素进行重排序的过程：

过滤及重排序后的事务如下图所示：

在对事务记录过滤和排序之后，就可以构建FP树了。从空集（符号为∅）开始，向其中不断添加频繁项集。过滤、排序后的事务依次添加到树中，如果树中已存在现有元素，则增加现有元素的值；如果现有元素不存在，则向树添加一个分枝。添加前两条事务的过程如下图所示：

最后的结果如图所示：FP树以文本形式被表示出来，每行的缩进代表树的的深度，树节点上存储着元素名称和出现频次。

想要更加详细了解本讲更多细节的内容吗？那就一起来观看下面的Presentation的具体讲解吧：