一种有效的并行频繁子图挖掘 算法

《一种有效的并行频繁子图挖掘 算法》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、一种有效的并行频繁子图挖掘算法陈晓云赵娟陈鹏飞邢乔金刘国华（兰州大学信息科学与工程学院兰州730000）摘要：在分析并行频繁项集挖掘算法的基础上，提出了一种有效的并行频繁子图挖掘算法，该并行算法采用主从节点处理模式，将主节点处理后生成的频繁子树集放到从节点上并行的生成频繁子图。通过实验验证了算法的可行性和有效性。关键字：并行化；频繁项集；频繁子图；Abstract：Basedontheanalysisoftheparallelfrequentitemsetminingalgorithm,akindofeffectiveparallelalgorithm

2、forminingfrequentsubgraphisintroducedinthispaper.Theparallelalgorithmadoptsamaster-slavenodeprocessingmode，putthefrequentsubtreesetswhichgeneratedbythemasternodeontheslavenodewhichparallelgeneratefrequentsubgraph.Theresultsoftheexperimentsshowthatouralgorithmhasgoodeffectiveness

3、andfeasibility.Keywords:parallel;frequentitemset;frequentsubgraph1.引言：频繁子图挖掘与其他比较成熟的频繁模式挖掘相比，图结构数据所包含的信息比一般的数据类型的数据量更大,其数据结构比线性表和树更为复杂。在图形结构中，结点之间的关系是任意的，任意两个数据元素之间都可能相关。尽管其结构很复杂，但是由于基于图的应用越来越广泛，其已经渗入到诸如语言学、逻辑学、物理、化学、计算机科学及数学的这些分支学科中。如通过对已有的生物分子结构与未知的生物结构的研究，来确定未知生物分子与已知生物分子之间的联

4、系与区别。例如在PTE(predictivetoxicologyevaluationchallenge)项目中找到频繁出现的而且与已有的有毒物质具有相同子结构的物质，这样就可以发现新的对人体有害的物质。因此，对基于图的频繁子图挖掘的算法研究是非常必要的，而且具有很好的实际应用价值。在通常情况下，由于没有任何先验知识做参考，频繁子图的挖掘工作量会很大。对于海量数据的挖掘任务来讲，现有的频繁子图挖掘算法速度比较慢，而且效率不高，因此没有得到广泛的应用。所以研究出一个算法效率高，执行速度快的频繁子图挖掘算法是目前一个非常热门的话题。本文在分析以往的并行频繁项

5、集挖掘算法的基础上，提出了一种并行频繁子图发掘算法PG-Miner。该挖掘算法采用主从模式，将整个过程分为两部分，第一部分由主处理节点来生成频繁子树集，然后将生成的子树集分发到其他从处理节点。第二部分将频繁子图边扩展及同构判断这部分频繁子图挖掘算法中时间复杂度最高的部分并行处理。文章在最后通过实验验证了本算法的有效性和可行性。2.并行频繁项集挖掘综述频繁模式挖掘的搜索空间可以被模拟成类似格的结构，其中由模式的大小来决定它处于格中的哪一层，每一层又以某种顺序进行排列。模式格的维数决定了问题的指数级别。例如，对于一个有着n个不同项的事务数据库，可能的模式就

6、会有2n。也就是说，如果一个事务数据库有100个不同的项，搜索空间就达到21001030。巨大的搜索空间使得在大型数据库上的频繁模式的挖掘成为一个计算密集型问题。然而传统的频繁模式挖掘算法被单一处理器和有限的内存空间所限制，不适用于大型数据库。因此，利用高性能并行计算来改善现有频繁模式挖掘算法的瓶颈，使其适用于大规模数据库是非常必要的。在FP-Growth算法的基础上，2001年OsmarR.Zaiane等人提出了并行频繁项集挖掘算法MLFPT，2004年Javed和Khokhar等人提出了并行频繁项集挖掘算法PFP-tree。2.1MLFPT算法Za

7、ïane.O.R等人于2001年提出基于共享式内存的类FP-Growth的并行频繁项集挖掘算法MLFPT。此算法对FP-Growth算法中的FP-Tree进行了并行化的改进。在整个执行过程中仅需扫描数据库两次，建立了一个特殊的数据结构叫做频繁模式树（FrequentPatternTree），之后在上面挖掘频繁项集。由于一颗在并行节点上共享的树结构势必需要在叶子或节点甚至路径上设置锁机制，这样就会导致严重的瓶颈。于是，MLFPT算法中采取了将FP-Tree分成块到每个节点上，而保持结果树是各节点上共享的来避免假负现象。建立这样的树大大减少了生成频繁项集的

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