关联规则如何并行实现呢?一个很直观的想法是要么分数据要么分计算。本文要说的是分数据,想法来自mahout的fp-tree并行实现。其中分数据的博客已在前篇 mahout关联规则FPGrowthDriver源码分析之如何分数据中说明,如何建树可以在网上查找(这个相对来说比较简单)或者直接看此片论文:《Mining FrequentPatterns
without Candidate Generation》,这篇博客要说的是如何挖掘已经建好的FP-tree,也是参考《Mining FrequentPatterns without Candidate Generation》的(最好对照原篇来看,原篇为全英)。
先把建好的树贴出来看:
挖掘的过程即为遍历Header table中的每个item,然后重新构造事务集,以及相应的f-list,然后重新建树的过程。下面就p和m项目进行演示:
查找项目p在fp-tree的链接可以找到两条路径:f,c,a,m:2; c,b:1 这里的次数以p的次数为准,比如f:4,c:3,a:3,m:2,因为后面的p:2,所以f,c,a,m:2;
则其事务集为{[f,c,a,m:2],[c,b:1]},其g-list为c:3;所以其建好的树为:
由于上面的树是单支(原文为:only onebranch),所以可以直接输出模式cp:3。(此处默认的阈值为3)
对于项目m,其事务集为 {[f,c,a:2],[f,c,a,b:1]},g-list: [f:3,c:3,a:3],事务集根据g-list进行删减项目得到新的事务集为{[f,c,a:2],[f,c,a:1]},则由新的事务集和g-list构造的fp-tree为:
对上面的树的挖掘和最开始的树是一样的,即分别对项目a、c、f进行挖掘。
1. 项目a:
输出(am:3)模式同时调用"mine(f:3,c:3)|am" ,"mine(f:3,c:3)|am" 输出(cam:3,fam:3)模式,以及调用"mine(f:3)|cam",这个调用输出(fcam:3)模式 ;
2. 项目c:
输出(cm:3)模式同时调用"mine(f:3)|cm","mine(f:3)|cm"输出(fcm:3)
3. 项目f:
直接输出模式(fm:3)
所以最原始的树上面项目p生成的模式为:(cp:3),项目m生成的模式为:(am:3)(cam:3)(fam:3)(fcam:3)(cm:3)(fcm:3)(fm:3)。其他的项目按照上面同样的规则进行生成频繁项目集。
分享,快乐,成长
转载请注明出处:http://blog.csdn.net/fansy1990
分享到:
相关推荐
关联规则挖掘 FP-tree关联规则挖掘 FP-tree关联规则挖掘 FP-tree关联规则挖掘 FP-tree关联规则挖掘 FP-tree
python3.2实现FP-TREE挖掘算法,可以显示每一步FP树的图片
详解python实现FP-TREE进行关联规则挖掘 python3.2实现,可以生成每一步fp树的图片(需要安装PIL)
用c++实现FP-tree的构建以及利用FP-tree来挖掘频繁模式的完全集。有良好注释。
针对FP-growth算法时空效率低的问题,提出了改进的FP-tree构造算法。该算法利用动态结点插入技术构造FP-tree,能有效减小模式树的宽度,达到压缩空间的目的;同时,该算法提高了前缀路径的共享性,提高了算法的效率。针对...
数据挖掘关联规则FP-Tree的java实现
数据挖掘的课程作业实现,两种算法的实现,包括测试数据,可执行程序和源代码,及两个算法实现的对比截图。
数据挖掘中频繁模式挖掘的经典算法fp-tree
用c#实现了数据挖掘中的fp-tree算法
为解决经典关联规则生成算法挖掘效率低及形成规则冗余性大的问题,提出在FP-tree基础上直接生成频繁概念格并提取无冗余关联规则的算法。其建格过程根据FP-tree频繁项目头表中各项的索引可分别独立进行,由支持度计数...
数据挖掘FP-Tree算法,源代码,仅供参考
FP-TREE的构建过程详细介绍,图文并茂,看完胜过看好几遍书,故分享一下。
fp-tree算法
数据挖掘中的频繁项集的算法fp-tree
提出了一种基于邻接矩阵的FP-tree构造方法。首先通过扫描数据库建立2-项集支持数的邻接矩阵,通过邻接矩阵对项进行过滤和新方式排序,然后再利用邻接矩阵构造FP-tree,使得FP-tree的分支、节点数和深度大幅度地减少...
针对这类稀疏数据,提出了基于事务哈希表和线性对象表的FP-Tree改进算法,其只需扫描数据库一次,把相关信息压入事务哈希表和线性对象表中。当支持度和事务记录变化时,可不用重新扫描数据库或扫描数据库更新部分。试验...
数据挖掘相关算法
FPGrowth算法主要分为两个步骤:FP-tree构建、递归挖掘FP-tree。FP-tree构建通过两次数据扫描,将原始数据中的事务压缩到一个FP-tree树,该FP-tree类似于前缀树,相同前缀的路径可以共用,从而达到压缩数据的目的。...