文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 一种基于极大完全子图的最大频繁项集并行挖掘算法
侵权投诉

一种基于极大完全子图的最大频繁项集并行挖掘算法

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页)

上一页第3页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email