去年公司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
分享到:
相关推荐
关联规则挖掘 FP-tree关联规则挖掘 FP-tree关联规则挖掘 FP-tree关联规则挖掘 FP-tree关联规则挖掘 FP-tree
详解python实现FP-TREE进行关联规则挖掘 python3.2实现,可以生成每一步fp树的图片(需要安装PIL)
python3.2实现FP-TREE挖掘算法,可以显示每一步FP树的图片
FP-Growth采用频繁模式挖掘技术构建频繁模式树(FP-Tree),可用于提取关联规则。与 Apriori 相比,FP-Growth 方法更加高效,并且在大型数据集中的规则挖掘方面具有更好的性能。适合研究生学习。
为解决经典关联规则生成算法挖掘效率低及形成规则冗余性大的问题,提出在FP-tree基础上直接生成频繁概念格并提取无冗余关联规则的算法。其建格过程根据FP-tree频繁项目头表中各项的索引可分别独立进行,由支持度计数...
数据挖掘关联规则FP-Tree的java实现
对于超市销售记录进行关联挖掘,项目集庞大,每次事务中涉及到项目数非常少。针对这类稀疏数据,提出了基于事务哈希表和线性对象表的FP-Tree改进算法,其只需扫描数据库一次,把相关信息压入事务哈希表和线性对象表中。当...
数据库的访问频度是影响关联规则挖掘性能的关键因素之一。通过研究FP-tree算法,提出了一种基于FP-tree的快速构建算法,使FP-tree的构建过程仅需一次数据库扫描。该算法通过动态调整项头表中各项的顺序,同时动态...
在数据挖掘中发现关联规则是一个基本问题,而发现频繁项集是关联规则挖掘中最基本、最重要的问题。提出了基于FP-Tree的共享前缀频繁项集挖掘算法-FP-SPMA算法。构造FP-Tree来压缩事务数据库,通过共享前缀和前瞻...
java编写的,对于研究关联规则FP-Growth算法很有帮助
基于FP树的FP-Growth关联规则挖掘算法,不需要产生候选项集,是当前频繁项集挖掘算法中应用最为广泛的算法之一.针对该算法在对大型的数据库挖掘的时候,存在运行速度慢,占用资源多的问题,文中发现算法中FP树和条件...
数据挖掘Apriori和FP-Tree算法工程+测试用例 VC++6.0工程,图形化界面
针对目前关联规则挖掘频繁树(FP-Tree)算法实现较困难以及难以处理数据库更新的缺点,提出了频繁模式网络(FP-network)模型,将关联规则挖掘所需要的信息压缩到一个无向网络图上,并建立事务项目关联矩阵,从而进行...
现有的基于频繁模式树FP-tree和概念格的规则挖掘算法在构造概念格时存在重复遍历FP-tree问题,在挖掘后件约束的规则时算法构造的概念格包含冗余结点。针对这两个问题,提出了通过遍历FP-tree生成候选概念格节点的...
Apriori和FP-Tree算法实现+两个测试数据 图形化界面 vc++6.0工程 ps:csdn太不给力了,自己的资源不能编辑了,刚才传的那个忘了把测试数据加上了,所以这次重传一遍。
为了克服 Apriori 算法在复杂度和效率方面的缺陷,本节还进一步的介绍了基于 FP-Tree 的频繁模式挖掘方法。 Apriori关联分析算法 Apriori 算法是挖掘产生关联规则所需频繁项集的基本算法,也是最著名的关联分析算法...
资源包含了FP-tree算法的演示文本、算法源码的讲解、可执行程序的演示以及可编译程序代码,通过这些资源,你可以掌握fp_tree 算法的原理和树的创建过程。
通过对两个有代表性的算法Apriori和FP-Growth的剖析,说明频集模式挖掘的过程,比较有候选项集产生和无候选项集产生算法的特点,并给出FP-tree结构的构造方法以及对挖掘关联规则的影响,提出了对算法的改进方法。
数据挖掘关联规则详解,有一个药店的实例..