昨天回顾了一下频繁集挖掘的 Apriori 算法，今天继续补充一下另一个比较有名的 FP-Growth 算法吧。
2000 年的时候，由数据挖掘大牛 Han Jiawei 教授等人提出了不生成候选集而直接挖掘频繁集的 FP-Growth 算法。主要目的是避免了多次访问数据库造成的频繁 IO 操作以及无谓的数据生成、暂存操作。（题外话：频繁的事情确实有原因的，但是，从这个算法的角度看，频繁的 IO 读写也未必是一个算法的必要的原因。）
在看 FP-Growth 以前，总觉得 FP-Growth 算法多么复杂，却可以在很短的时间内把频繁集都找出来，就像数据结构里复杂的红黑树（Red-black Tree）。实际上， FP-Growth 算法远没有红黑树复杂，但对于比较长的 itemset 来说，效率确实高不少。
FP-Growth 的算法实现是使用类似投影数据库的方法实现的（接下来频繁集的算法很多会用到这个概念，详细的解释请看下文）。算法依然分为多次遍历的算法，但是这次并不是对全局数据库进行遍历，而是维护一个不断缩小的投影数据库。对于每次遍历，先找出当前数据库的频繁项，然后从频繁项中构建只包含当前找到的所有事件的一个“前缀”数据库（这个结构即 FP-Tree）。在这个前缀数据库里递归执行以上过程，继续挖掘出频繁项，拼接起之前挖掘的频繁项，就形成频繁集了。
概括地说一下：
先把当前的数据库中的频繁项（就是单一的事件了）找出来，这些频繁项即是待挖掘的事件集，按照阈值过滤不符合的项目。
然后，构建 FP-Tree ，即把数据库中的记录，过滤掉不频繁（即计算不超过设定阈值的项）按照一定顺序插入到“前缀树”结构中。
这个“前缀树”之所以和前缀有关，是这样描述的，从根节点到某一子节点的路径，构成一个频繁集的所有项，也就是说，每个节点以上的所有父节点实际上就是它的前缀了。得到了前缀树以后，实际上是得到了一个压缩了的事件集数据库，我们可以从这棵 FP-Tree 上得到所有频繁集的信息了。
这里需要提到的一个结构是表头（即文献中的 header table），这个结构是以“当前数据库中的频繁项”为 key 的一个 Map ，这个 Map 的 value 即是该项在 FP-Tree 上节点的集合。也就是说，我们可以通过表头直接获取每一个项对应的前缀了，这些前缀，也是一个列表，并且归属于原来的数据库。这些前缀的集合就形成了一个数据库了，这种方法就是上面提到的“投影数据库”。
以上一步构建出来的“前缀”数据库，递归地执行步骤 1 。
详细的算法实现就不说了，给出一个博文链接吧。当然，这篇博文实现可能不是最优的（我的实现方法也不尽相同，但是基本思路也是那样吧），不过对我的启发也挺大的。具体的算法参见 FP-Growth 的原文献 。
不过，要评论一下这个算法的话，我觉得实际上这个算法并没不是不生成候选集的，只是生成的方式比较隐蔽，这个候选集实际上就是 FP-Tree 这个结构；在频繁集生成方面，这个算法也没有完全摆脱 Apriori 的逐层生成的框架。不过，利用 FP-Tree 保存及压缩频繁集数据库以及候选集数据库确实是一个比较好的优化。