论文部分内容阅读
从大型数据库中挖掘频繁模式是数据挖掘研究的一类基本问题,也是该领域最具挑战性的一个研究热点。其中频繁子图挖掘旨在解决结构化模式挖掘问题,诸如化学,生物学,WWW应用等领域的关联性问题。由于实际应用中具有数据规模大,抽象出的图结构复杂等特性使得高性能的子图挖掘算法一直是该领域研究中的一个难点。本文首先提出了并行频繁项集挖掘算法HPFP-Miner,并以此为基础,提出一个高效的并行频繁子图挖掘算法PG-Miner。论文主要内容包括：1、并行频繁项集挖掘算法HPFP-MinerHPFP-Miner为了能够在并行处理中生成完备且不冗余的结果集提出了两个数据结构HPFP树和HPFP-Forest来压缩存储频繁项集信息,与FP树的根为"null"不同的是,每一颗HPFP树都独立完整的表述了当前数据库中以其根节点为前缀的模式,HPFP树中反向表示父节点到子节点的指针。同时,所有HPFP树通过指针链接形成HPFP-Forest,到执行时再由主节点根据从节点的多少向各处理节点分发HPFP树,这使得算法具有更高的可扩展性,并且进一步也容易控制各处理节点的负载。2、并行频繁子图算法PG-Miner设计与实现在这部分,我们提出一种新的并行频繁子图挖掘算法PG-Miner。该算法以尽可能大的并行粒度将频繁子图挖掘算法中时间复杂度最高的子图同构判断过程分发到多台处理器上并行处理,使得算法的执行时间随着处理节点的线性增加而线性减少。该算法的主要策略是,首先将整个挖掘过程分成两部分,由主处理节点来生成频繁子树集,接着将生成的子树集分发到从处理节点。其次,将频繁子图边扩展及同构判断这部分频繁子图挖掘算法中时间复杂度最高的部分并行处理。经过算法分析得出,本文提出的算法时间复杂度为O(2n*n2/k),其中n是图集中的频繁边数,k是用于并行计算的从节点个数(总节点个数为k+1)。本文分析了该算法的时间复杂度,并在不同的真实和模拟数据集上验证了算法的可行性。