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

一种有效的并行频繁子图挖掘算法 陈晓云 赵娟 陈鹏飞 邢乔金 刘国华 （兰州大学信息科学与工程学院 兰州 730000） 摘要：在分析并行频繁项集挖掘算法的基础上，提出了一种有效的并行频繁子图挖掘算法，该并行算法采用主从节点处理模式，将主节点处理后生成的频繁子树集放到从节点上并行的生成频繁子图。通过实验验证了算法的可行性和有效性。 关键字：并行化；频繁项集；频繁子图； Abstract：Based on the analysis of the parallel frequent itemset mining algorithm, a kind of effective parallel algorithm for mining frequent subgraph is introduced in this paper. The parallel algorithm adopts a master-slave node processing mode，put the frequent subtree sets which generated by the master node on the slave node which parallel generate frequent subgraph.The results of the experiments show that our algorithm has good effectiveness and feasibility. Key words: parallel; frequent itemset; frequent subgraph 引言： 频繁子图挖掘与其他比较成熟的频繁模式挖掘相比，图结构数据所包含的信息比一般的数据类型的数据量更大,其数据结构比线性表和树更为复杂。在图形结构中，结点之间的关系是任意的，任意两个数据元素之间都可能相关。尽管其结构很复杂，但是由于基于图的应用越来越广泛，其已经渗入到诸如语言学、逻辑学、物理、化学、计算机科学及数学的这些分支学科中。如通过对已有的生物分子结构与未知的生物结构的研究，来确定未知生物分子与已知生物分子之间的联系与区别。例如在PTE(predictive toxicology evaluation challenge)项目中找到频繁出现的而且与已有的有毒物质具有相同子结构的物质，这样就可以发现新的对人体有害的物质。因此，对基于图的频繁子图挖掘的算法研究是非常必要的，而且具有很好的实际应用价值。 在通常情况下，由于没有任何先验知识做参考，频繁子图的挖掘工作量会很大。对于海量数据的挖掘任务来讲，现有的频繁子图挖掘算法速度比较慢，而且效率不高，因此没有得到广泛的应用。所以研究出一个算法效率高，执行速度快的频繁子图挖掘算法是目前一个非常热门的话题。 本文在分析以往的并行频繁项集挖掘算法的基础上，提出了一种并行频繁子图发掘算法PG-Miner。该挖掘算法采用主从模式，将整个过程分为两部分，第一部分由主处理节点来生成频繁子树集，然后将生成的子树集分发到其他从处理节点。第二部分将频繁子图边扩展及同构判断这部分频繁子图挖掘算法中时间复杂度最高的部分并行处理。文章在最后通过实验验证了本算法的有效性和可行性。 并行频繁项集挖掘综述 频繁模式挖掘的搜索空间可以被模拟成类似格的结构，其中由模式的大小来决定它处于格中的哪一层，每一层又以某种顺序进行排列。模式格的维数决定了问题的指数级别。例如，对于一个有着n个不同项的事务数据库，可能的模式就会有2n。也就是说，如果一个事务数据库有100个不同的项，搜索空间就达巨大的搜索空间使得在大型数据库上的频繁模式的挖掘成为一个计算密集型问题。然而传统的频繁模式挖掘算法被单一处理器和有限的内存空间所限制，不适用于大型数据库。因此，利用高性能并行计算来改善现有频繁模式挖掘算法的瓶颈，使其适用于大规模数据库是非常必要的。 在FP-Growth算法的基础上，2001年Osmar R. Zaiane等人提出了并行频繁项集挖掘算法MLFPT， 2004年Javed和Khokhar等人提出了并行频繁项集挖掘算法PFP-tree。 2.1 MLFPT算法 Za?ane.O.R等人于2001年提出基于共享式内存的类FP-Growth的并行频繁项集挖掘算法MLFPT。此算法对FP-Growth算法中的FP-Tree进行了并行化的改进。在整个执行过程中仅需扫描数据库两次，建立了一个特殊的数据结构叫做频繁模式树（Frequent Pattern Tree），之后在上面挖掘频繁项集。 由于一颗在并行节点上共享的树结构势必需要在叶子或节点甚至路径上设置锁机制，这样就会导致严重的瓶颈。于是，MLFPT算法中采取了将F