加载中…
个人资料
yfx416
yfx416
  • 博客等级:
  • 博客积分:0
  • 博客访问:103,799
  • 关注人气:75
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

Frequent Pattern挖掘之三(MapReduce框架下的FP Growth算法概述)

(2011-10-02 23:37:23)
标签:

fp

growth

mapreduce

分类: 数据挖掘

前面的博客分析了关联分析中非常重要的一个算法-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算法

第五步:聚合,将各台机器上的结果聚合成最终我们需要的结果。

前面的博客分析了关联分析中非常重要的一个算法-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算法

第五步:聚合,将各台机器上的结果聚合成最终我们需要的结果。

52C3190490D685A74CB772C81C5E0EEEF18E5288

上面的图就给出了算法步骤的框图。有了这个框图,大家可能对算法的步骤就有一定的认识了。后面的博客就针对每一步进行具体的分析。

上面的图就给出了算法步骤的框图。有了这个框图,大家可能对算法的步骤就有一定的认识了。后面的博客就针对每一步进行具体的分析。

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有