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