Frequent Pattern发掘之三（MapReduce框架下的FP Growth算法概述

前面的博客说明白关联说明中很是重要的一个算法-FP Growth.该算法按照数据库在内存中结构一个优良的数据布局-FP Tree,通过对FP Tree不绝的递归发掘就可以获得全部的完整Frequent Patterns.可是在今朝海量数据的近况下，FP Tree已经大到无法驻留在计较机的内存中。因此，并行化是独一的选择。这篇博客首要讲一下如安在MapReduce框架下举办并行FP发掘，它首要的算法在文献1中有具体描写。

怎样举办FP Growth的并行化呢？一个很天然的设法就是，将原始的数据库分别成几个分区，这几个分区别离在差异的呆板上，这样的话我们就可以对差异数据分区并行得举办FP Growth发掘，最后将差异呆板上的功效团结起来获得最终的功效。简直，这是一个正确的思绪。但题目是：我们凭证什么样的要领来把数据库分别成区块呢？假如FP Growth可以或许真正的独立举办并行化，那么就必要这些数据分区必需可以或许相互独立，也就是这些分区针对某一部门项目来说是完整的。于是就有一种要领：通过对数据库的一次扫描，结构一个Frequent Item列表F_List = {I1:count1,I2:count2,I3:count3…} ^ (count1> count2 > count3>…)，然后将F_List分成几个Group，形成几个G_List.这时辰我们再扫描数据库的每一条Transaction，假如这条Transaction中包括一条G_List中的Item，那么这条transaction就被添加到该group对应的数据库分区中去，这样就形成了几个数据库分区，每个数据库分区对应一个group和一个group_list。这种分区要领就担保对group_list内里的item而言，数据库分区是完整的。这种分区方法会导致数据会有冗余，由于一条transaction也许会在差异的分区中都有备份,但为了保持数据的独立性,这是一个不得已要领。

下面就简朴谈谈该算法的步调:

第一步:数据库分区.把数据库分成持续的差异的分区,每一个分区漫衍在差异的呆板上.每一个这样的分区称之为shard。

第二步:计较F_list,也就是全部item的support count.这个计较通过一个MapReduce就可以完成.想想hadoop上word count的例子,本质上和这一步是一样的.

第三步:条目分组.将F_list里的条目分成Q个组,这样的话就行成了一个group_list,group_list里的每一个group都被分派一个group_id,每个group_list都包括一组item的荟萃.

第四步:并行FP Growth.这一步是要害.它也是由一个MapReduce来完成的.详细来看看.

Mapper:

这个Mapper完成的首要成果是数据库分区。它和第一步中的shard有所差异，它操作第一步shard的数据库分区，一个一个处理赏罚shard数据库分区中的每一条transaction,将transaction分成一个一个item，每一个item按照group_list映射到吻合的group里去。这样的话，通过mapper，属于统一个group的item荟萃都被聚合到一台呆板上，这样就形成了我们前面讲到的完整数据集，在下一步的reducer中就可以并行得举办FP Growth算法了。

Reducer：

基于mapper形成的完整数据集，举办local的FP_Growth算法

第五步：聚合，将各台呆板上的功效聚合成最终我们必要的功效。

上面的图就给出了算法步调的框图。有了这个框图，各人也许对算法的步调就有必然的熟悉了。后头的博客就针对每一步举办详细的说明。

上面的图就给出了算法步调的框图。有了这个框图，各人也许对算法的步调就有必然的熟悉了。后头的博客就针对每一步举办详细的说明。

（编辑：湖南网）

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