一种有效的并行频繁子图挖掘算法Word文件下载.docx

一种有效的并行频繁子图挖掘算法Word文件下载.docx

《一种有效的并行频繁子图挖掘算法Word文件下载.docx》由会员分享，可在线阅读，更多相关《一种有效的并行频繁子图挖掘算法Word文件下载.docx（6页珍藏版）》请在冰点文库上搜索。

frequentsubgraph

1.引言：

频繁子图挖掘与其他比较成熟的频繁模式挖掘相比，图结构数据所包含的信息比一般的数据类型的数据量更大,其数据结构比线性表和树更为复杂。

在图形结构中，结点之间的关系是任意的，任意两个数据元素之间都可能相关。

尽管其结构很复杂，但是由于基于图的应用越来越广泛，其已经渗入到诸如语言学、逻辑学、物理、化学、计算机科学及数学的这些分支学科中。

如通过对已有的生物分子结构与未知的生物结构的研究，来确定未知生物分子与已知生物分子之间的联系与区别。

例如在PTE（predictivetoxicologyevaluationchallenge）项目中找到频繁出现的而且与已有的有毒物质具有相同子结构的物质，这样就可以发现新的对人体有害的物质。

因此，对基于图的频繁子图挖掘的算法研究是非常必要的，而且具有很好的实际应用价值。

在通常情况下，由于没有任何先验知识做参考，频繁子图的挖掘工作量会很大。

对于海量数据的挖掘任务来讲，现有的频繁子图挖掘算法速度比较慢，而且效率不高，因此没有得到广泛的应用。

所以研究出一个算法效率高，执行速度快的频繁子图挖掘算法是目前一个非常热门的话题。

本文在分析以往的并行频繁项集挖掘算法的基础上，提出了一种并行频繁子图发掘算法PG-Miner。

该挖掘算法采用主从模式，将整个过程分为两部分，第一部分由主处理节点来生成频繁子树集，然后将生成的子树集分发到其他从处理节点。

第二部分将频繁子图边扩展及同构判断这部分频繁子图挖掘算法中时间复杂度最高的部分并行处理。

文章在最后通过实验验证了本算法的有效性和可行性。

2.并行频繁项集挖掘综述

频繁模式挖掘的搜索空间可以被模拟成类似格的结构，其中由模式的大小来决定它处于格中的哪一层，每一层又以某种顺序进行排列。

模式格的维数决定了问题的指数级别。

例如，对于一个有着n个不同项的事务数据库，可能的模式就会有2n。

也就是说，如果一个事务数据库有100个不同的项，搜索空间就达到2100

1030。

巨大的搜索空间使得在大型数据库上的频繁模式的挖掘成为一个计算密集型问题。

然而传统的频繁模式挖掘算法被单一处理器和有限的内存空间所限制，不适用于大型数据库。

因此，利用高性能并行计算来改善现有频繁模式挖掘算法的瓶颈，使其适用于大规模数据库是非常必要的。

在FP-Growth算法的基础上，2001年OsmarR.Zaiane等人提出了并行频繁项集挖掘算法MLFPT，2004年Javed和Khokhar等人提出了并行频繁项集挖掘算法PFP-tree。

2.1MLFPT算法

Za?

由于一颗在并行节点上共享的树结构势必需要在叶子或节点甚至路径上设置锁机制，这样就会导致严重的瓶颈。

于是，MLFPT算法中采取了将FP-Tree分成块到每个节点上，而保持结果树是各节点上共享的来避免假负现象。

建立这样的树大大减少了生成频繁项集的开销。

这些树上的频繁项都是交叉连接起来的（与FP-Tree中相同），并且总体上连接在一个全局头表上。

每块树森林（treeforest）被分配到各个处理节点上，分开后的FP-Tree在挖掘过程中被自下向上的顺序快速遍历。

树的位置降低了并行节点间由于错误的操作而覆盖其他节点更新的可能性，同时使得死锁的可能性最小化。

但是基于共享式内存的并行频繁项集不能够适用于广泛使用的集群系统，因此局限性比较大。

2.2PFP-tree算法

Javed和Khokhar等人于2004年提出了分布式内存环境下的类FP-Growth并行频繁项集挖掘算法PFP-Tree。

算法中将整个数据库分割成不重合的p块，其中p是处理节点的数量。

然后将各个数据块分配给相应的处理节点。

PFP-tree算法的具体步骤如下：

1各节点p扫描被分配的数据块并且计算本地数据库块中的频繁项的支持度。

2所有处理节点做同步得到总体的频繁项支持度计数。

3各节点依据总的支持度来排序频繁项，并删除非频繁项。

4各节点第二次扫描本地数据库块并建立本地FP-tree。

5头表被分成p个互不相交的子集，每个处理节点为被分配到的项的集合并行挖掘频繁模式。

6由于第5步中的划分是静态的，每个处理节点必须通过其他的节点来确认本地树上的信息。

在第4步被分配到一个节点上的单频繁前缀分支构成了挖掘步的完整信息。

利用一次自底向上的扫描来进行确认信息。

7第6步中确认的信息利用一个递归的归并树结构在各节点上将需要进行

次通讯。

在每一次通讯的最后，一个节点需要解包收到的信息到本地的FP-tree树上，然后为下一次归并准备新的信息。

8每个处理节点挖掘被分配的频繁项集。

由于PFP-tree需要各节点交换基于每个频繁1-项集的条件模式基来得到本地所需的数据分块，所以整个算法的通讯还是比较多的，降低了并行的效率。

3.并行频繁子图挖掘算法PG-Miner

为了提高并行效率并且减少算法的通讯量，我们提出了一个频繁子图挖掘算法，该挖掘算法采用主从模式，将整个过程分为两部分，第一部分由主处理节点来生成频繁子树集，然后将生成的子树集分发到其他从处理节点。

3.1主节点频繁子树挖掘算法FTGen

FTGen（frequentsubtreegeneration）算法第一步判断要扩展的频繁子树是否为最小DFS编码，来避免对重复生成的子树做进一步扩展。

第二步通过对频繁边集中的每条边进行扩展判断。

第三步将已提取的边从边集中去掉，减小需要扩展的边集，第四步判断当前提取的边是否为树边ee，如果是，将其加入到DFS编码最小的频繁子树t中。

第五步判断在频繁子树T中是否存在t的同构子树。

如果不存在，将t加入到结果集T中。

第六步对扩展后的t执行FTGen算法以得到全部频繁子树。

FTGen的挖掘结果是图集GS中出现的频繁子树，储存在集合T中。

频繁子树将被用于进一步对边扩展以形成图，同时，频繁子树作为图的一种，是最终挖掘结果的子集。

算法伪代码如Algorithm3-1所示：

3.2从节点子图拓展挖掘算法PFGGen

算法PFGGen在FTGen算法的基础上做进一步挖掘，主要是从频繁子树向频繁子图的扩展过程。

第一步由于FTGen本身生成的频繁子树也是最终结果的一部分，故需要将其也加入到结果集中。

第二步将T中的频繁子树按降序DFS编码排序，并且对T中每颗子树做扩展成图的处理。

第三步先将当前需要扩展的子树初始化到图g，然后对频繁边集中的每条边ee做扩展处理，将已提取要扩展的边从边集中去掉。

第四步判断当前边是否可扩展，如果当前边可以扩展，扩展这条边。

第五步判断扩展后的图是否满足最小DFS编码的要求，避免重复操作。

第六步判断扩展的图在结果集中是否存在同构子图，如果不存在，将扩展的子图加入到结果集。

算法伪代码如Algorithm3-2所示：

3.3PG-Miner算法

PG-Miner算法第一步初始化MPI并行环境并且计算用于此次并行计算的所有节点。

第二步判断是否为主节点，扫描图集并找到图集GS中所有频繁边，并删除图集中所有非频繁边，将所有频繁边集按DFS编码和支持度降序排列，初始化扩展子树t。

第三步调用FTGen算法，获得频繁子树集。

第四步调用PFGGen算法，扩展频繁子树到频繁子图。

第五步结束MPI。

PG-Miner算法伪代码如Algorithm3-3所示：

4.实验结果与分析

实验环境：

由5台2.8GHzIntelCoreCPU，2GB内存的PC机搭建MPI环境，机子之间的通信采用千兆路由器实现，操作系统为内核的UbuntuKarmicKoala（Ubuntu9.10）。

所有程序均用GCC3.4.3和MPI库mpich2-1.0.7编译实现。

在实验中，我们分别选取真实数据和仿真数据来与gSpan，FFSM作比较，gSpan和FFSM都是在单台机子运行，我们的算法启动4个从节点来计算。

数据可从以下网址获得：

。

图4-1，4-2，4-3给出了在不同数据集上gSpan，FFSM，PG-Miner的运行结果

图4-1CA数据集

图4-2CM数据集

图4-3CI数据集

仿真数据我们采用文献[16]Kuramochi和Karypis提供的工具产生的数据集。

我们选取了两个参数集来测试我们的结果，第一个设置N=10（N代表可能的节点标识数），T=40（T代表每个图的平均边数），D=10000（D代表生成图的数量），I=7（I代表可能生成的频繁子图的平均大小）；

另一个数据集设置T=40，N=5，D=10000，I=7。

图4-4，4-5在不同数据集上gSpan，FFSM，PG-Miner的运行结果

图4-4N10I7T40数据集

图4-5N5I7T40数据集

在下面，我们将PG-Miner在从节点个数为2和从节点为4时在CA上的运行结果也展示出来，用来分析我们的算法在处理节点扩展时的可扩展性，图4-6给出了运行结果。

图4-6CA数据集

图4-1到4-3为了能更加清晰的列出结果，我们采用了对数值。

在这几个真实数据集上，我们比较了从支持度3%到9%，在图上我们可以看到，在支持度很小时，PG-Miner算法的运行时间仅是FFSM的1/4多一点，这说明PG-Miner运行效率提高了接近n（处理节点数）倍。

但当支持度增加时，PG-Miner算法的运行时间在4s左右，甚至出现高于FFSM的情况，这说明此时，MPI环境的启动开销和通信开销已经成为程序运行的主要时间，在这种情况下，并不适合PG-Miner算法。

图4-4和4-5是在模拟数据集上得到的运行结果，我们比较了支持度从1%到6%，由结果可以得到与真实结果集上相同的结论。

图4-6在CA数据集上处理节点分别为2和4时，我们比较了支持度从1%到6%的运行结果，从运行结果可以看出，PG-Miner具有很好的可扩展性。

5.结论

本文在研究以往并行频繁项集挖掘算法的基础，提出了并行频繁子图挖掘算法PG-Miner。

该算法成功的将频繁子图挖掘算法中时间复杂度最高的子图同构判断过程分发到多台处理器上并行处理，使得算法的执行时间随处理节点的线性增加而线性减少。

并且在不同的真实和模拟数据集上验证了算法的可行性。

另外算法在并行化方面，如何提高并行粒度，使得各处理节点负载更加均衡以及如何减少子图同构的判断是我们下一步的研究方向。

文献：

[1]范明，孟晓峰.数据挖掘概念与技术第2版

[2]王丹阳，田卫东，胡学刚.一种有效的并行频繁项集挖掘算法.计算机应用研究.1001-3695（2008）11-3332-03

[3]王永恒，杨树强，贾焰.海量文本数据库中的高效并行频繁项集挖掘方法.计算机工程与科学.1007-130X（2007）09-0110-04

[4]张大为，黄丹，嵇敏，谢福鼎.利用模式指导树的并行频繁项集挖据方法.计算机工程与应用.1002-8331（2010）22-0147-04

[5]Fiedler,M.andBorgelt,C.:

2007,Supportcomputationforminingfrequentsubgraphsinasinglegraph,inP.Frasconi,K.KerstingandK.Tsuda（eds）,MLG.

[6]X.YanandJ.Han,“gSpan:

Graph-BasedSubstructurePatternMining,”Proc.2002Int’lConf.DataMining（ICDM’02）,pp.721-724,Dec.2002.

[7]Wu,J.andChen,L.:

MiningFrequentSubgraphbyIncidenceMatrixNormalization.JournalofComputers3（10）（2008）109–115.

[8]C.WangandS.Parthasarathy.Parallelalgorithmsforminingfrequentstructuralmotifsinscientificdata.InProceedingsoftheACMInternationalConferenceonSupercomputing（ICS）,2004.

[9]T.Meinl,I.Fischer,andM.Philippsen.Parallelminingforfrequentfragmentsonashared-memorymultiprocessor-resultsandjava-obstacles-.InM.Bauer,A.Kroner,andB.Brandherm,editors,LWA2005-BeitragezurGI-WorkshopwocheLernen,Wissensentdeckung,Adaptivitat,pages196–201,2005.

[10]M.KuramochiandG.Karypis.Frequentsubgraphdiscovery.InProceedingsoftheInternationConferenceonDataMining（ICDM）,pages313–320,2001.

[11]王艳辉，吴斌，王柏.频繁子图挖掘算法综述.计算机科学.2005Vol.32No.10.

[12]胡作霆,董兰芳,王洵.图的数据挖掘算法研究[J].计算机工程.2006,32（3）:

76278.

[13]A.JavedandA.A.Khokhar.Frequentpatternminingonmessagepassingmultiprocessorsystems.DistributedandParallelDatabases,16（3）:

321-334,2004.

[14]李继腾，骆志刚，丁凡，田文颖。

赵琦.最大频繁子图挖掘算法研究.计算机工程与科学.1007-130X．2009.12.020

[15]唐德权，朱林立.频繁子图挖掘算法研究.计算机工程.1000-3428（2009）09-0052-03

[16]ZaianeO.R,EI-HajjM,LuP.FastParallelAssociationRuleMiningWithoutCandiadateGeneratioin.TechnicalReportTR01-02.UniversityofAlberta,Canada:

DepartmentofComputingScience.2001:

665-668P.

[17]R.Agrawal,J.C.Shafer.ParallelMiningofAssociationRules.IEEETrans.KnowledgeandDataEng.,1996,8（6）:

962-969.