论文研究-一种有效的并行频繁子图挖掘算法 .pdf

所需积分/C币:32 2019-08-15 12:50:46 240KB .PDF
收藏 收藏
举报

一种有效的并行频繁子图挖掘算法,陈晓云,赵娟,本文在分析并行频繁项集挖掘算法的基础上,提出了一种有效的并行频繁子图挖掘算法,该并行算法采用主从节点处理模式,将主节点处
国武技论文在线 讯。在每·次通讯的最后,个节点需要解包收到的信息到本地的 树上 然后为下一次归并准备新的信息。 每个处理节点挖掘被分配的频繁项集。 由于 需要各节点交换基于每个频繁项集的条件模式基来得到本地所需的数 据分块,所以整个算法的通讯还是比较多的,降低了并行的效率。 并行频繁子图挖掘算法 为了提髙并行效率并且减少算法的通讯量,我们提岀了一个频繁子图挖掘算法,该挖掘 算法采用主从模式,将整个过程分为两部分,第一部分由主处理节点米生成频繁子树集,然 后将生成的子树集分发到其他从处理节点。第二部分将频繁子图边扩展及同构判断这部分频 繁子图挖掘算法中时间复杂度最高的部分并行处理。 主节点频繁子树挖掘算法 算法第一步判断要扩展的频繁子树是否为最 编码,来避免对重复生成的子树做进一步扩展。第二步通过对频繁边集中的每条边进行扩展 判断。第三步将已提取的边从边集中去掉,减小需要扩展的边集,第四步判断当前提取的边 是否为树边,如果是,将其加入到编码最小的频繁子树中。第五步判断在频繁子 树中是否存在的同构子树。如果不存在,将加入到结果集中。第六步对护展后的 执行 算法以得到全部频繁子树。 的挖掘结果是图集中出现的频繁子树 储存在集合中。频繁子树将被用于进一步对边扩展以形成图,同时,频繁子树作为图的 一种,是最终挖掘结果的子集。算法伪代码如 所小 Aldorithm3-1: FTGen Graph set吕maSu Sup Ds t Edge set e frequent tree T output Frequent tree T lift=minDS(t) eturn t is not the rrir DFS edge 3 reach e o↑ edge set E 5) if(istreeedge〔te E insert.e ifis ITEy nsertlT, t FTGen(Gst, t 从节点子图拓展挖掘算法 算法 在 算法的基础上做进一步挖掘,主要是从频繁子树向频繁」图的 扩展过程。第一步由于 本身生成的频繁子树也是最终结果的一部分,故需要将其也 加入到结果集中。第二步将中的频繁」树按降序编码排序,并且对中每颗」树做 国武技论文在线 扩展成图的处理。第三步先将当前需要扩展的子树初始化到图,然后对频繁边集中的每条 边倣扩展处理,将已提取要扩展的边从边集中去掉。第四步判断当前边是否可扩展,如 果当前边可以扩展,扩展这条边。第五步判断扩`展后的图是否满足最小编码的要求, 避免重复操作。第六步判断扩展的图在结果集中是否存在同构子图,如果不存在,将扩展的 子图加入到结果集。算法伪代码如 所示: AIgorithm3-2: FFTGen Input Gra帅S时5, minimum suport minsu, frequent subtree T Output: frequent subgraph FSG 1)InitresultFSG,T) 2)su(T)rE的yDF foreach t of T 4) initgraph(g, t) foreach e. of edge set e 6〕5uact(E,已。 if( extention(g,ee sertgraphge ifg=rnin(g) brea 10 if(isomorphism〔FsG更 insertresult(SG, g) 算法 算法第一步初始化并行境并且计算用」此次并行计算的所有节点。第 二步判断是否为主节点,打描图集并找到图集中所有频繁边,并删除图集中所有非频繁 边,将所有频繁边集抆编码和攴持度降序排列,初始化扩展子树。第三步调用 算法,获得频繁子树集。第四步啁用 算法,扩`展频繁子树到频繁子图。第五步结束 算法伪代码如 所示: 国武技论文在线 Aldorithm3-3: PG-Miner Input Graph Set Ds, minimum_ suport minsup Tre quent _ suhgra ) nit(eargc &argv )hiPI Comm size(MuPI CoM M WORLD, &numprocsy 3) Comm_rank(MPI WoRLD &myid 4 MulPI File openPlComiMWnRLD' poutput MPI Mod E_RDWR,MPIIMNFn MI_LL &Th 5 If(rmyid==U'mainnode b scanS, minsup, E desO it,t) 9 FTGenGGs tE,T 10) foreach t of t 神P⊥ Sendmessage, ength,MP千epth(% nurrprocs+1,99, MPI COMM oRLD) else T=N儿 13) N P Recvimessage, maxlength, MmPINt0,99, MPI CoMM WorLd, &status) 14 rt(l,t 15] PFGGen(GS, minsupT 16 foreach g of FG MPI File write shared(th, buffer(g) length g), MiPl CHAR status 18)MPI Barrier(MP CO M WORLD 19MP Finalize 实验结果与分析 实验环境:由台 内存的机搭建环境,机子之 间的通信采用千兆路器实现,操作系统为内核 。所有程序均用 和 编译实现。 在实验中,我们分别选取真实数据和仿真数据来与 作比较, 和 都是在单台机子运行,我们的算法启动个从节点来计算。数据可从以下网址获得: 图,,给出了在不同数据集上 的运行结果 10000 000 ← PG-Miner 10 support 图4-1CA数捱集 国武技论文在线 10000 1000 gopan 100 PG -Mine 10 3456了 Ipport ( 数据集 100o 00 FESM PG-Miner 10 support (% 图 数据集 仿真数据我们采用文献 和 提供的工具产生的数据集。我们选取了 两个参数集来测试我们的结果,第一个设置 代表可能的节点标识数, 代表 每个图的平均边数, 代表生成图的数量,代表可能生成的频繁子图的平均 大小;另一个数据集设置 在不同数据集 的运行结果 40 30 g口an 2 FFSML PG -Miner ] support(%) 图 数据集 国武技论文在线 30 FFSM her oport(%) 数据集 在下面,我们将 在从节点个数为和从节点为时在上的运行结果也展 示出米,用米分析我们的算法在处理节点扩展时的可扩展性,图给出了运行结果。 250 200 150 PG-Miner(n=4) 100 PG-Miner (n=2) 50 U 456 SUpPO 图 数据集 图到为了能更加清晰的列出结果,我们采用了对数值。在这几个真实数据集上, 我们比较了从支持度到,在图上我们可以看到,在支持度很小时, 算法的 运行时间仅是 的多一点,这说明 运行效率提高了接近处理节点数 倍。但当支持度增加时 算法的运行时间在左右,甚至出现高于 的情况, 这说明此时,环境的启动开销和通信开销己经成为程序运行的主要时间,在这种情况下, 并不适合 算法 图和是在模拟数据集上得到的运行结果,我们比较了支持度从到,由结 果可以得到与真实结果集上相同的结论 图在数据集上处理节点分别为和时,我们比较了支持度从到的运行 结果,从运行结果可以看出, 具有很好的可扩展性 结论 木文在研究以往并行频繁项集挖掘算法的基础,提岀∫并行频繁子图挖掘算法 。该算法成功的将频繁了图挖掘算法中吋间复杂度最扃的了图同构判断过程分发到多 台处理器上并行处理,使得算法的执行时间随处理节点的线性增加而线性减少。并且在不同 的真实和模拟数据集上验证了算法的可行性。 另外算法在并行化方面,如何提高并行粒度,使得各处理节点负载更加均衡以及如何诚 少子图同构的判断是我们下一步的研究方向。 国武技论文在线 参考文献 范明,孟晓峰.数据挖掘概念与技术第版 干丹阳,田卫东,胡学网.一种有效的并行频繁项集挖掘算法.计算机应用研 上永恒,杨树贔,贾焰.沟量文本数据库中的高效并行频繁项集挖掘方法.计算机I程与科 张大为,黄丹,嵇敏,谢福鼎.利用模式指导树的并行频繁项集挖据方法.计算机「程与应用. 王艳辉,吴斌,王柏.频繁子图挖掘算法综述.计算机科学 胡作霆董兰芳王洵.图的缴据挖拥算法研究,计算机工程. 李缑腾,骆忐刚,丁凡,田文颖。赵琦.最大频繁子图控掘算法硏究.计算机工程与科 学.1007-130X.2009.12.020 唐德权,朱林立.频繁孑图挖掘算法硏究.计算机上程.

...展开详情
试读 8P 论文研究-一种有效的并行频繁子图挖掘算法 .pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    • 至尊王者

      成功上传501个资源即可获取
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    论文研究-一种有效的并行频繁子图挖掘算法 .pdf 32积分/C币 立即下载
    1/8
    论文研究-一种有效的并行频繁子图挖掘算法 .pdf第1页
    论文研究-一种有效的并行频繁子图挖掘算法 .pdf第2页
    论文研究-一种有效的并行频繁子图挖掘算法 .pdf第3页

    试读已结束,剩余5页未读...

    32积分/C币 立即下载 >