定义
何谓频繁模式挖掘呢？所谓频繁模式指的是在样本数据集中频繁出现的模式。举个例子，比如在超市的交易系统中，记载了很多次交易，每一次交易的信息包括用户购买的商品清单。如果超市主管是个有心人的话，他会发现尿不湿，啤酒这两样商品在许多用户的购物清单上都出现了，而且频率非常高。尿不湿，啤酒同时出现在一张购物单上就可以称之为一种频繁模式，这样的发掘就可以称之为频繁模式挖掘。这样的挖掘是非常有意义的，上述的例子就是在沃尔玛超市发生的真实例子，至今为工业界所津津乐道。
Aprior挖掘算法：
那么接下来的问题就很自然了，用户该如何有效的挖掘出所有这样的模式呢？下面我们就来讨论一下最简单，最自然的一种方法。在谈到这个算法之前，我们先声明一个在频繁模式挖掘中的一个特性-Aprior特性。
Aprior特性:
这个特性是指如果一个Item set(项目集合)不是frequent item set(频繁集合),那么任何包含它的项目集合一定也不是频繁集合.这里的集合就是模式.这个特性很自然,也很容易理解.比如还是看上面沃尔玛超市的例子,如果啤酒这个商品在所有的购物清单中只出现过1次,那么任何包含啤酒这个商品的购物商品组合,比如(啤酒,尿不湿)最多也只出现了一次,如果我们认定出现次数多于2次的项目集合才能称之为频繁集合的话,那么这些包含了啤酒的购物组合肯定都不是频繁集合.反之,如果一个项目集合是频繁集合,那么它的任意非空子集也是频繁集合.
有了这个特性,那么就可以在挖掘过程中对一些不可能的项目集合进行排除,避免造成不必要的计算浪费.这个方法主要包含两个操作:product(叉积)和prune(剪枝).这两种操作是整个方法的核心.
首先是product:
先有几个定义，L(k)-候选项目队列，该队列中包含一系列的项目集合（也就是说队列是项目集合的集合），这些项目集合的长度都是一样的，都为k，这个长度我们称之为秩(呵呵，秩是我自己取的中文名)，这些长度相同的集合称之为k-集合。那么就有L(k+1)=L(k) product L(k).也就是说通过product操作（自叉积），秩为k的候选队列可以生成秩为k+1的候选队列。需要注意的是，这里所有的候选队列中的k-集合都按照字母顺序（或者是另外的某种事先定义好的顺序）排好序了。好，下面关键来了，product该如何执行？product操作是针对候选队列中的k-集合的，实际上就是候选队列中的k-集合两两进行执行join操作。K-集合l1,l2之间能够进行join有一个前提，那就是两个k-集合的前k-1个项目是相同的，并且l1(k)的顺序大于l2(k)(这个顺序的要求是为了排除重复结果)。用公式表示这个前提就是(l1[1]=l2[1])^(l1[2]=l2[2])^…^(l1[k-1]=l2[k-1])^(l1[k]<l2[k]).那么join的结果就形成了一个k+1长度的集合l1[1],l1[2],…,l1[k-1],l1[k],l2[k]。如果L(k)队列中的所有k-集合两两之间都完成了join操作，那么这些形成的k+1长度的集合就构成了一个新的秩为k+1的候选项目队列L(k+1)。
剪枝操作：
这个操作是针对候选队列的，它对候选队列中的所有k-集合进行一次筛选，筛选过程会对数据库进行一次扫描，把那些不是频繁项目集合的k-集合从L(k)候选队列中去掉。为什么这么做呢？还记得前面提到的Aprior特性么？因为这些不是频繁集合的k-集合通过product操作无法生成频繁集合，它对product操作产生频繁集合没有任何贡献，把它保留在候选队列中除了增加复杂度没有任何其他优点，因此就把它从队列中去掉。
这两个操作就构成了算法的核心，用户从秩为1的项目候选队列开始，通过product操作，剪枝操作生成秩为2的候选队列，再通过同样的2步操作生成秩为3的候选队列，一直循环操作，直到候选队列中所有的k-集合的出现此为等于support count.
FP树构造
FP Growth算法利用了巧妙的数据结构，大大降低了Aproir挖掘算法的代价，他不需要不断得生成候选项目队列和不断得扫描整个数据库进行比对。为了达到这样的效果，它采用了一种简洁的数据结构，叫做frequent-pattern tree(频繁模式树)。下面就详细谈谈如何构造这个树，举例是最好的方法。请看下面这个例子：
这张表描述了一张商品交易清单，abcdefg代表商品，(ordered)frequent items这一列是把商品按照降序重新进行了排列，这个排序很重要，我们操作的所有项目必须按照这个顺序来，这个顺序的确定非常简单，只要对数据库进行一次扫描就可以得到这个顺序。由于那些非频繁的项目在整个挖掘中不起任何作用，因此在这一列中排除了这些非频繁项目。我们在这个例子中设置最小支持阈值（minimum support threshold）为3。
我们的目标是为整个商品交易清单构造一颗树。我们首先定义这颗树的根节点为null，然后我们开始扫描整个数据库的每一条记录开始构造FP树。
第一步：扫描数据库的第一个交易，也就是TID为100的交易。那么就会得到这颗树的第一个分支<(f:1),(c:1),(a:1),(m:1),(p:1)>。注意这个分支一定是要按照降频排列的。
第二步：扫描第二条交易记录（TID=200），我们会有这么一个频繁项目集合<f,c,a,b,m>。仔细观察这个队列，你会发现这个集合的前3项<f,c,a>与第一步产生的路径<f,c,a,m,p>的前三项是相同的，也就是说他们可以共享一个前缀。于是我们在第一步产生的路径的基础上，把<f,c,a>三个节点的数目加1，然后将<(b:1),(m:1)>作为一个分支加在(a:2)节点的后面，成为它的子节点。看下图
第三步:接着扫描第三条交易记录(TID=300),你会看到这条记录的集合是<f, b>,与已存在的路径相比,只有f是共有的前缀,那么f节点加1,同时再为f节点生成一个新的字节点(b:1).就会有下图:
第四步：继续看第四条交易记录，它的集合是<c,b,p>，哦，这回不一样了。你会发现这个集合的第一个元素是c,与现存的已知路径的第一个节点f不一样，那就不用往下比了，没有任何公共前缀。直接将该集合作为根节点的子路径附加上去。就得到了下图（图1）：
第五步：最后一条交易记录来了，你看到了一条集合<f,c,a,m,p>。你惊喜得发现这条路径和树现有最左边的路径竟然完全一样。那么，这整条路径都是公共前缀，那么这条路径上的所有点都加1好了。就得到了最终的图(图2)。
好了，一颗FP树就已经基本构建完成了。等等，还差一点。上述的树还差一点点就可以称之为一个完整的FP树啦。为了便于后边的树的遍历，我们为这棵树又增加了一个结构-头表，头表保存了所有的频繁项目，并且按照频率的降序排列，表中的每个项目包含一个节点链表，指向树中和它同名的节点。罗嗦了半天，可能还是不清楚，好吧直接上图，一看你就明白：
以上就是整个FP树构造的完整过程。聪明的读者一定不难根据上述例子归纳总结出FP树的构造算法。这里就不再赘述。详细的算法参考文献1。
FP树的挖掘
下面就是最关键的了。我们已经有了一个非常简洁的数据结构，下一步的任务就是从这棵树里挖掘出我们所需要的频繁项目集合而不需要再访问数据库了。还是看上面的例子。
第一步:我们的挖掘从头表的最后一项p开始，那么一个明显的直接频繁集是(p:3)了。根据p的节点链表，它的2个节点存在于2条路径当中：路径<f:4,c:3,a:3,m:2,p:2>和路径<c:1,b:1,p:1>.从路径<f:4,c:3,a:3,m:2,p:2>我们可以看出包含p的路径<f,c,a,m,p>出现了2次，同时也会有<f,c,a>出现了3次，<f>出现了4次。但是我们只关注<f,c,a,m,p>，因为我们的目的是找出包含p的所有频繁集合。同样的道理我们可以得出<c,b,p>在数据库中出现了1次。于是，p就有2个前缀路径{(fcam:2),(cb:1)}。这两条前缀路径称之为p的子模式基（subpattern-base），也叫做p的条件模式基（之所以称之为条件模式基是因为这个子模式基是在p存在的前提条件下）。接下来我们再为这个条件子模式基构造一个p的条件FP树。再回忆一下上面FP树的构造算法，很容易得到下面这棵树：
但是由于频繁集的阈值是3。那么实际上这棵树经过剪枝之后只剩下一个分支(c:3),所以从这棵条件FP树上只能派生出一个频繁项目集{cp:3}.加上直接频繁集(p:3)就是最后的结果．
第二步:我们接下来开始挖掘头表中的倒数第二项m,同第一步一样,显然有一个直接的频繁集(m:3).再查看它在FP树中存在的两条路径<f:4,c:3,a:3,m:2>和<f:4,c:3,a:3,b1,m:1>.那么它的频繁条件子模式基就是{ (fca:2),(fcab:1)}.为这个子模式基构造FP树,同时舍弃不满足最小频繁阈值的分支b,那么其实在这棵FP树中只存在唯一的一个频繁路径<f:3,c:3,a:3>.既然这颗子FP树是存在的,并且不是一颗只有一个节点的特殊的树,我们就继续递归得挖掘这棵树.这棵子树是单路径的子树,我们可以简化写成mine(FP tree|m)=mine(<f:3,c:3,a:3>|m:3).
下面来阐述如何挖掘这颗FP子树,我们需要递归.递归子树也需要这么几个步骤:
1这颗FP子树的头表最后一个节点是a,结合递归前的节点m,那么我们就得到am的条件子模式基{(fc:3)},那么此子模式基构造的FP树(我们称之为m的子子树)实际上也是一颗单路径的树<f:3,c:3>,接下也继续继续递归挖掘子子树mine(<f:3,c:3>|am:3). (子子树的递归分析暂时打住.因为再分析子子树的递归的话文字就会显得太混乱)
2同样,FP子树头表的倒数第二个节点是c,结合递归前节点m,就有我们需要递归挖掘mine(<f:3>|cm:3).
3 FP子树的倒数第三个节点也是最后一个节点是f,结合递归前的m节点,实际上需要递归挖掘mine(null|fm:3),实际上呢这种情况下的递归就可以终止了,因为子树已经为空了.因此此情况下就可以返回频繁集合<fm:3>
注意:这三步其实还包含了它们直接的频繁子模式<am:3>,<cm:3>,<fm:3>,这在每一步递归调用mine<FPtree>都是一样的,就不再罗嗦得一一重新指明了.
实际上这就是一个很简单的递归过程,就不继续往下分析了,聪明的读者一定会根据上面的分析继续往下推导递归,就会得到下面的结果.
mine(<f:3,c:3>|am:3)=><cam:3>,<fam:3>,<fcam:3>
mine(<f:3>|cm:3)=><fcm:3>
mine(null|fm:3)=><fm:3>
这三步还都包含了各自直接的频繁子模式<am:3>,<cm:3>,<fm:3>.
最后再加上m的直接频繁子模式<m:3>,就是整个第二步挖掘m的最后的结果。请看下图
第三步:来看看头表倒数第三位<b:3>的挖掘,它有三条路径<f:4,c:3,a:3,b:1>,<f:4,b:1>,<c:1,b:1>，形成的频繁条件子模式基为{(fca:1),(f:1),(c:1)}，构建成的ＦＰ树中的所有节点的频率均小于3,那么FP树为空，结束递归．这一步得到的频繁集就只有直接频繁集合<b:3>
第四步：头表倒数第四位<a:3>，它有一条路径<f:4,c:3>，频繁条件子模式基为{(fc:3)}，构成一个单路径的ＦＰ树．实际上可能有人早已经发现了，这种单路径的ＦＰ树挖掘其实根本不用递归这么麻烦，只要进行排列组合就可以直接组成最后的结果．实际上也确实如此．那么这一步最后的结果根据排列组合就有：{(fa:3),(ca:3),(fca:3),(a:3)}
第五步：头表的倒数第五位<c:4>,它只有一条路径<f:4>,频繁条件子模式基为{(f:3)}，那么这一步的频繁集也就很明显了:{(fc:3),(c:4)}
第六步：头表的最后一位<f:4>，没有条件子模式基，那么只有一个直接频繁集{(f:4)}
这６步的结果加在一起，就得到我们所需要的所有频繁集．下图给出了每一步频繁条件模式基．
其实,通过上面的例子,估计早有人看出来了,这种单路径的FP树挖掘其实是有规律的,根本不用递归这么复杂的方法,通过排列组合可以直接生成.的确如此,Han Jiawei针对这种单路径的情况作了优化.如果一颗FP树有一个很长的单路径,我们将这棵FP树分成两个子树:一个子树是由原FP树的单路径部分组成,另外一颗子树由原FP树的除单路径之外的其余部分组成.对这两个子树分别进行FP Growth算法,然后对最后的结果进行组合就可可以了.
通过上面博主不厌其烦，孜孜不倦，略显罗嗦的分析，相信大家已经知道FP Growth算法的最终奥义．实际上该算法的背后的思想很简单，用一个简洁的数据结构把整个数据库进行ＦＰ挖掘所需要的信息都包含了进去，通过对数据结构的递归就可以完成整个频繁模式的挖掘．由于这个数据结构的ｓｉｚｅ远远小于数据库，因此可以保存在内存中，那么挖掘速度就可以大大提高．
也许有人会问?如果这个数据库足够大,以至于构造的FP树大到无法完全保存在内存中,这该如何是好.这的确是个问题. Han Jiawei在论文中也给出了一种思路,就是通过将原来的大的数据库分区成几个小的数据库(这种小的数据库称之为投射数据库),对这几个小的数据库分别进行FP Growth算法.
还是拿上面的例子来说事,我们把包含p的所有数据库记录都单独存成一个数据库,我们称之为p-投射数据库,类似的m,b,a,c,f我们都可以生成相应的投射数据库,这些投射数据库构成的FP树相对而言大小就小得多,完全可以放在内存里.
在现代数据挖掘任务中,数据量越来越大,因此并行化的需求越来越大,上面提出的问题也越来越迫切.下一篇博客,博主将分析一下,FP Growth如何在MapReduce的框架下并行化.
[1]Mining Frequent Patterns without Candidate Generation: AFrequent-Pattern Tree Approach
转载自原文链接, 如需删除请联系管理员。
原文链接：Frequent Pattern 数据挖掘关联规则算法（Aprior算法) FT-Tree，转载请注明来源！