论文源:
Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach∗
FP-Tree是一个frequent itemset mining的算法。首先来说一下frequent itemset的相关内容。
Frequent itemset就是说在一个transaction数据库中(每个transaction由若干个item组成)，我们要找出现频率大于某个人们所期望的值e的itemset。
通常的方法有Apriori这类的，它需要按一定规律去产生candidate itemset，然后挨个检验看是不是frequent的。这种方法显然比较耗时，虽然在这个过程中那个“一定规律”起到了比较强的搜索空间的剪枝作用。同时重复性扫描数据库和进行pattern matching的工作也是十分耗时的。这里要说一下这个“一定规律”，他一般都是基于以下这个observation：
Itemset A是itemset B的子集，那么如果A是infrequent的，那么B也是infrequent的，这个很显然，用反证法非常容易就能证明。利用这一点就可以砍掉很多itemset了。
然而，重新分析我们所面临的问题，我们不难发现，我们所关心的信息只有frequency，那么有没有什么方法可以对数据库进行一定的预处理，忽略一些无关信息，利用某种数据结构来对整个数据库中的数据重新存储，以达到减少存储空间，同时还能便于mining frequent itemset呢？
一些基本的想法可以很轻松的想到：
- 我们可以删除/忽视一些items，这个做法的依据就是上面的那个observation，如果一个单一的item的frequency都不足，那么任何包含它的itemset的frequency都不可能满足e了。因此我们可以先扫描一次数据库，来确定哪些item是frequent的。
- 很多transaction之间是包含有相同的itemset的，这共有部分能不能合并在一起存起来，然后加上一个count之类的属性来统计它的出现频率呢？
基于以上，可以发现，一个前缀树prefix-tree是个好选择，如果我们将每个transaction中的items按照之前扫描数据库时获得的item频降序的顺序用来代表这个transaction，那么就可以用prefix-tree进行存储了。过程如下：
- 首先构造一个Null的root，它显然是所有可能的string的前缀
- 扫描第一个transaction，按照item频排序，获得了一个item string，调用insert(string, T)将这个string插入树T中，接着第二个transaction，如此知道所有transaction都被插入树中。
关于insert(string, T)，这是一个递归函数
为了便于表述，我们将string定义为这个形式(p|P)，p是string的首个item，P是剩余的items的string，我们将p和T的children做比较，如果
(1) 存在T.child.itemname= p.itemname，给T.child.count加一，那么调用insert(P, T.child)
(2) 否则，我们给T新建一个child，并让此child.itemname = p，child.count=1， 然后调用insert(P, T.child)
直到string为空。
这样就将所有数据及频率存储在这个prefix-tree中了。
下面将要讲述如何进行mining。
实际上在上面的建树过程中，还有一个小细节没有做，那就是在新生成一个node的时候，都要将以前的和这个node代表相同item的nodes链接起来，也就是，树中的代表相同item的nodes会形成一个链表，这些链表的表头存在一起，并且是按照这个表所链接的item的频率的降序顺序排列的。
这么做的原因是为了mine的工作。
下面简单叙述mine的过程：
假定threshold是3，从链表表头的表的最后一位的那个item开始，比如这个item是p，此时实际上我们要找的是以p为后缀的frequent pattern。显然p自身肯定就是一个frequent pattern了，否则它不会被留到现在。然后我们找寻树中从root到各个node.itemname=p的path，对于这个path我们复制下来重新处理一下。因为现在要找的是以p作为suffix的frequent pattern，所以之前的nodes的count要进行修正，对于任意获得的path上的node，他的count都应该和这个path上的代表p的node的count一致。这个很显然，比如一条从root到item为p的node的path上有a，它的count是4，而这条path上代表p的node.count =2，那么显然a只同时和p出现了2次。。。举例来说，有如下3条path{a5,b5,d3,p3} {c3,b2,p1} {d4,b2,p2},修改后的path应为{ a3,b3,d3 } {c1,b1}和{d2,b2}，此时我们将这3个path可以视为三个transaction，然后构建一个FP-subtree出来，然后重复上述工作进行mine。在mine这棵FP子树的时候，c的frequency不满足threshold会被删掉，最后frequency最小的是a，frequency是3，显然a是一个合格的pattern，而实际上，我们获得的总体的那个frequenct pattern，是{ap}，因为这个是以p为pattern suffix下的subtree。如此递归下去即可。
然后接着从链表表头的表的倒数第二个item开始mine，比如这个item是 a，此时要挖掘的就是以a为pattern suffix的pattern，此时p显然也就不用考虑了，因为任何一条树中的path，其中点的排列顺序都是一致的，是按照这个item的总频率降序排列的，对于a的挖掘，其过程和前面一样。
有一种特殊的FP-tree形态是可以简化mine的过程的，如图：
如图(a)所示，这个tree的从root到c:7是一条简单的单链，这样就可以更加轻松地处理了，处理方式是将这个tree分成两棵树，第一棵树如(b)所示，由于是单链，我们只需要枚举abc的排列组合即可，组合出的pattern的frequency显然等于pattern中的item的最小frequency。我们称这部分获得的frequent pattern的集合为A。另一部分如图(c)所示，我们给它建了一个伪root，然后正常进行挖掘，得到的frequent pattern为集合B。此时还有一部分frequent pattern还没有考虑，这部分可以用A X B来获得，也是很显然的，frequency等于X积时较小的frequency部分的frequency。
