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

Frequent Pattern挖掘之五(MapReduce框架下的FP Growth算法详解下篇)

(2011-10-02 23:45:46)
标签:

fp

growth

mapreduce

分类: 数据挖掘

接着前面的博客Frequent Pattern之四继续分析。

结果聚合

请看伪码如下:

FB995118F3C8C10FA2EB1F67A70CD6297F07DAC1
这个mapreduce实际上完成了一个index的功能,把上一步的结果进行了一个处理,它把上一步得到的frequent pattern按照item做了索引,这要得到的最后结果就是某一个item对应着一组frequent pattern。它把这些frequent pattern放在一个堆里,便于按频率的高低顺序进行访问。伪码中的if-else其实就是把frequent pattern插入堆,如果堆满了,和频率最小的那个节点(也就是根节点)比较一下,如果新节点的值大的话,删掉根节点,插入新节点。这样做的目的是始终保持堆里存储着某一item频率最高的top K个frequent pattern。

这就是map reduce框架下FP Growth算法的具体实现。在apache的开源项目mathout中它已经得到了实现,大家可以直接使用。

最后再谈一点个人意见,这个FP Growth Mapreduce实现在对F_list进行分组时可以再考虑一些负载均衡的策略,因为不采用任何策略的话,有可能会导致频率高的item都在一组,那么发射到这一组所对应机器上transaction就会得特别多,处理压力也会特别大,而别的机器上任务却过于轻松,这对整个系统效率的提升是很不利的。如果加入一定的策略考量,把频率高的item均匀的分配到各台机器上,将会使效率更加提高。

[1]PFP: ParallelFP-Growth for Query Recommendation

0

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

    发评论

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

      

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

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

    新浪公司 版权所有