`
安铁辉
  • 浏览: 241657 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

FP-tree 关联规则挖掘

阅读更多
          去年公司1拆4,再拆3,在拆25,真是72搬变化,看的我等屌丝一阵胆寒,但一年过去了并没有影响我和同事们的工作,也没有听得到一些负面消息,nice,看来level还查一大大截。拆25的一个大的结果是前台流量必然被瓜分,这个应该会很纠结,有点远,打住。今年我的技术方向有BI转向算法多一点,这也是我个人很甘兴趣的,团队专注于CRM这一块,现在提的比较多的是CEM,好像你还再提crm就不好意思和人打招呼。为了提高用户体验,所以在做一个用户行为分析的东东,思路就是采集用户行为,更好的服务会员,其中一个落地点就是根据会员状态,行为推测出来电的目的地是哪里,即什么问题。关联规则的算法主流的有3个,Apriori,基于划分的算法,FP-tree,他们都有自己的侧重点,百科地址:http://baike.baidu.com/view/1076817.htm
基本思路都是找出频繁项集 apriori迭代的方式找,效率低,但是思路很清晰,基于规划是在它基础上优化了性能,Fp-tree是韩佳伟设计的算法,只需要扫描2次数据库,性能有很大提升,并且最主要的mahout有对应的事项,mahout对于mapreduce支持友好,所以选它了.

一、环境
FP-tree wiki  https://cwiki.apache.org/confluence/display/MAHOUT/Parallel+Frequent+Pattern+Mining
hadoop 0.20.2+mahout 0.5 +jdk 1.6 不同版本间有不兼容情况,这个坑我踩过了,坑和安装见我之前的文章。安装环境过程中遇到好多问题,有些百度就能解决了,有好多需要谷歌看老外的论坛,觉得每次百度搞不定了就用谷歌,最后老外的解释都挺简单,但能解决问题,所以强烈建议在搜索之前想一下是否直接看老外的论坛,感觉国内遇到的问题总是更丰富一下。
二、讲算法前先讲一下如何配置eclipse进行debug,
1、eclipse安装mapreduce插件,网上找一个安装就行,应该与hadoop版本没关系
2、这个时候需要配置插件的hadoop信息了,因为需要与hadoop环境交互,所以需要知道namenode的监听端口和jobtracker的监听端口,如果你前面忘记了自己的配置,那查看一下文件。不同hadoop版本的配置文件也不同,我 的是hadoop0.20.2(这也是个坑)
core-site.xml文件的
fs.default.name

mapred-site.xml文件的
mapred.job.tracker

这样就可以在eclipse中run和debug了
二、算法逻辑
程序主入口是FPGrowthDriver 其实就是一个启动类,做一些输入参数解析,比如输入输出,根据掺入的参数选择单机还是分布式计算,由method指定,具体参数看mahout -fp-treewiki页面(或者你输入参数不对也会有提示的),我的method指定的mapreduce,如下代码:
if ("sequential".equalsIgnoreCase(classificationMethod)) {
				runFPGrowth(params);
			} else if ("mapreduce".equalsIgnoreCase(classificationMethod)) {
				Configuration conf = new Configuration();
				HadoopUtil.delete(conf, outputDir);
				PFPGrowth.runPFPGrowth(params);

PFPGrowth.runPFPGrowth主要计算逻辑都在这个方法总,这个方法调用了5个方法,所以计算过程可以分为5个步骤,我详细讲解下具体每一步都做了什么,之前有参照过另一片博客,头几步讲的很详细,而且有图,但是很多细节并没有提,博客地址是:http://www.cnblogs.com/zhangchaoyang/articles/2198946.html
1、
Count

startParallelCounting 这部就是个wordcount,对于DB中的每个元素做计数,可以叫做Count,这样方便记忆和理解,产出的是一个
fList, [(薯片,7), (面包,7), (鸡蛋,7), (牛奶,5), (啤酒,4)]
这个后面会用到,所以这些变量名最好都理解并记住。
2、
Group

startGroupingItems  fList随机分N组,每组放maxPerGroup个元素  maxPerGroup=fList.size() / numGroups;
分组后的数据放入gList {薯片=0, 牛奶=3, 鸡蛋=2, 面包=1, 啤酒=4} 数字是组ID
本次没有用到mapreduce,在本地完成,
fList相当于元素或元素对应编号与组的映射关系
3、
code

startTransactionSorting 编号,去重,排序,输入输出类似如下,只不过[0, 1, 2]不是数组,而是一个 TransactionTree,到现在位置逻辑还都很清晰,第四步开始构建树结构了
牛奶,鸡蛋,面包,薯片 ->> 单分支的树[0, 1, 2]

4、
tree

startParallelFPGrowth
map:读取第三步输出的树,并拆成多颗树:如把[0, 1, 2] --> [0, 1, 2] [0,1] [0]  输出K=groupId(fList中2对应的groupId)  V=对应的树
reducer:第三步中同一个groupid的输出构建成对应的一棵树。然后遍历表头项,分别从树上递归找到所有父节点,这样表头项中的1个元素会对应多条路径,然后把这些路径作为输入到第三步,迭代进行
5、
mining

startAggregating 根据第四步的输出产出top k频繁模式


ps:时间比较急,今天就搞环境和做ETL了,先写这些,后续再更新,发现还是没有我参照的博客写的详细,人家还有图呢,后续也会做个图,再把我代码中的一些注释抽取出来,会更清晰一些,方便来看的人,执行力,执行力啊,图会有的。收工,回家……2013-03-30
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics