2007年第24卷第10期微电子学与计算机
3l
MFI=IⅦFIULMFI。tJPM兀。t3SMIH!
算法3:PMFlM算法
输入:事务数据库D,最小支持度mlnsup。
输出:全局最大频繁项集MFI。
sl:扫描事务数据库,计算l一项集的支持度计数,得到频繁1—项集:
S2:由鞭繁l一项集连接生成候选2一项集.再次扫描数据库.计算候选2.项集的支持度计数,得到颇繁2_项集;S3:由频繁2一项集构造频繁2一项集邻接矩阵;
s4:遍历频繁2-.项集邻接矩阵,得到所有极大完全子图的集合G:
s5:对于G中的每一个元素C。(1≤i≤n.1G}凯).其顶点
序列为n.该顶点序列对应一个项集,;s6:将得到的项集正添加到队列;
s7:若当前队列元素个数大于O.将队首元素分配给空闲的处理器P.队列元素个数硪1:S8:每个处理器运行lmfi_miner算法;s9:直到队列元素个数为0。否则返回57:
S10:调用merge_mtl算法合并局部最大频繁项集.得到全局最大频繁项集Mn;
S11:如果当前进程是根进程,从通信器中的所有进程中(包括根进程自己)收集数据得到全局最大频繁项集
M兀。
PMHM算法在各处理机上挖掘最大频繁项集的时候.在第一阶段不需要各处理机之间协调通信.仅在第二阶段合并最大频繁项集的时候需要协调通信.因此对于分布式内存并行计算环境也有较好的适应性。由于各处理机处理的项集有大有小.因此率先完成第一阶段工作的处理机可以先于其他处理机合并最大频繁项集.这样做使得各处理机的计算时间和通信时间有效重叠。进一步提高了算法的性能。
在频繁项集挖掘算法中.项集支持度的计算通常使用“向量与”运算完成.需要大量的密集计算和内存I/O访问.通过优化这一部分能够显著地提升算法的性能。循环扩展是一种非常有效的程序优化技术。它不仅可以改善算法的时间特性和空间特性。还由于增加了每步循环中运算指令的数目.对于现代CPU可以充分发挥多个部件的功能.微观上提高了“与”运算的并行度。
4实验结果分析
在IBM
BladeCenter
HS20上进行了实验.该刀
片服务器配备“组刀片,每组刀片配置2个英特
尔双核至强3.0GHz处理器,2GB内存.操作系统为
RedhatEnterprise4,共128个节点。每个节点存储
空间都使用NF¥方式共享2TB存储阵列.为了检验算法的有效性在PMnM算法中的lmfiminer算法中采用了和MAFIA算法相同的深度优先策略及剪枝策略。并选取串行算法MAFIA为参照.通过实验结果来分析PMFIM算法的正确性和有效性.所有代码在MPICHI.2.7和gcc3.2.3下编译通过.编译器优化使用“-03”选项。实验数据集为:BMS-.Web-vjew—l和connect,。测试数据集来自bffp:llfimi.cs.
helsinki.fddata/。
BMS—WebView一-1来自于一个电子商务Web站点的访问数据。每一个事务是一个Web会话.每一个项目为浏览的产品页面的代码。B^lIS-.WebView一1是一种稀疏的事务数据集的代表.有59602个事务,497个项目,事务的平均长度为2.3l,最大频繁项集的平均长度为5撕。connect数据集来自一个电子游戏的状态信息.是一种拥有大量长频繁项集的稠密数据集,有67557个事务。130个项目.事务的平均长度为43.最大频繁项集的平均长度为20。23。图l给出了BNIS..-WebView一1和connect中最大频繁项集的分布。
最大颤繁项集长度
图1数据集中最大频繁项集的分布
图2给出算法在connect和BMS..WebView一1数据集上,随着CPU数目的逐渐增加,算法的时间
CPU教目什
图2cPu数目对算法的影响,支持度阈值分别为O.003(BMS-WebView-1),和00005(connect)
(下转第35页)
维普资讯 http://www.cqvip.com 200 7年第 2 4卷第1 O期 微 电子 学与计 算机 2 9 一 种基于极大完全子 图的最大频繁项集并 行挖掘算法 杨仕博 ...
一种有效的并行频繁子图挖掘算法 陈晓云 赵娟 陈鹏飞 邢乔金 刘国华 (兰州大学信息科学与工程学院 兰州 730000) 摘要:在分析并行频繁项集挖掘算法的基础上,提出...
目前已经提出的最大频繁项目集挖掘算法大多是基于单机环境的,在分布环境中挖掘最大频繁项目集的算法尚不多见。文章提出了一种基于分布数据库的并行挖掘最大频繁项目...
挖掘最大频繁项集的并行化策略 提出基于因子项集的并行化策略GP以发挥串行算法的剪枝功效。其基本思想是利用因子项集的完全包含关系在处理机之间贪心分配等价类....
一种基于FP-Growth的频繁项目集并行挖掘算法_互联网_IT/计算机_专业资料。... 基于FP-tree的最大频繁项... 42人阅读 4页 2.00 一种改进的FP-...
一种有效的并行频繁项集挖掘算法_专业资料。传统的挖掘频繁项集的并行算法存在各节点间负载不均衡、同步开销过大、通信量大等问题。针对这些问题,提出了一种多次...
一种基于极大完全子图的最... 4页 5财富值 一种高效的并行频繁集挖掘.....) "#) CA" 一种频繁项集并行挖掘算法李 ! 力! 翟东海! 靳 ! 蕃 ! !...
一种基于后缀项表的并行闭频繁项集挖掘算法_信息与通信_工程科技_专业资料。第3 1卷第 2期 201 4年 2月 计算机应用研究 Application Research of Comput...
一种基于频繁模式树的最大频繁项目集挖掘算法_IT/计算机_专业资料。小型微型...M A F IA 算法的概念框架是项集网格和 子集树 , 并利用纵向位图存储事务...
2012 分布式全局最大频繁项集挖掘算法杨君锐,何洪德,杨莉,李海文,薛萍 (西安科技大学 计算机科学与技术学院,陕西 西安,710054) 摘要:提出一种分布式全局最大频繁...
热门文档