Frequent Pattern 挖掘之二(FP Growth算法)

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,a>与第一步发生的路径<f,m,p>的前三项是沟通的，也就是说他们可以共享一个前缀。于是我们在第一步发生的路径的基本上，把<f,a>三个节点的数量加1，然后将<(b:1),(m:1)>作为一个分支加在(a:2)节点的后头，成为它的子节点。看下图

?

第三步:接着扫描第三条买卖营业记录(TID=300),你会看到这笔记录的荟萃是<f,b>,与已存在的路径对比,只有f是共有的前缀,那么f节点加1,同时再为f节点天生一个新的字节点(b:1).就会有下图:

?

第四步：继承看第四条买卖营业记录，它的荟萃是<c,p>，哦，这回纷歧样了。你会发明这个荟萃的第一个元素是c,与现存的已知路径的第一个节点f纷歧样，那就不消往下比了，没有任何民众前缀。直接将该集相助为根节点的子路径附加上去。就获得了下图（图1）：

?

第五步：最后一条买卖营业记录来了，你看到了一条荟萃<f,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,p:2>我们可以看出包括p的路径<f,p>呈现了2次，同时也会有<f,a>呈现了3次，<f>呈现了4次。可是我们只存眷<f,p>，由于我们的目标是找出包括p的全部频仍荟萃。同样的原理我们可以得出<c,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,m:2>和<f:4,b1,m:1>.那么它的频仍前提子模式基就是{ (fca:2),(fcab:1)}.为这个子模式基结构FP树,同时舍弃不满意最小频仍阈值的分支b,那么着实在这棵FP树中只存在独一的一个频仍路径<f:3,a:3>.既然这颗子FP树是存在的,而且不是一颗只有一个节点的非凡的树,我们就继承递归得发掘这棵树.这棵子树是单路径的子树,我们可以简化写成mine(FP tree|m)=mine(<f: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>,<fm:3>.

最后再加上m的直接频仍子模式<m:3>,就是整个第二步发掘m的最后的功效。请看下图

?

第三步:来看看头表倒数第三位<b:3>的发掘,它有三条路径<f:4,b:1>,<f:4,<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,f我们都可以天生响应的投射数据库,这些投射数据库组成的FP树相对而言巨细就小得多,完全可以放在内存里.

在当代数据发掘使命中,数据量越来越大,因此并行化的需求越来越大,上面提出的题目也越来越急切.下一篇博客,博主将说明一下,FP Growth如安在MapReduce的框架下并行化.

[1]Mining Frequent Patterns without Candidate Generation: AFrequent-Pattern Tree Approach

（编辑：湖南网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!