基于子图发现的设计模式识别系统——子图发现算法的设计与实现---毕业论文

本 科 毕 业 论 文 基于子图发现的设计模式识别系统子图发现算法的设计与实现Design Pattern Detecting System by Subgraph DiscoveryThe Design and Implementation of Subgraph Discovery姓 名： 学 号：学院：软件学院系：软件工程专 业：软件工程年 级：指导教师： 年 月摘要现代软件业已经广泛应用设计模式来重用最佳实践和改善软件质量。然而受制于软件系统的规模和设计文档的缺失，开发人员无法直观地理解现有软件系统中应用的设计模式，从源码中发现设计模式实例对于提高软件可理解性和可维护性、软件设计重用以及软件重构具有重要意义。 为了便于在实际应用中理解、选择和实践设计模式，设计模式的特征通常以非形式化的方式描述，在进行设计模式识别时需要对其进行形式化的表示，已有的研究中采用不同的中间表示来描述设计模式和系统源码以及提出不同的算法来进行设计模式识别。本文在比较目前已有的设计模式发现方法的基础上，进一步提出了一种新的设计模式识别方法。本文提出了一种基于子图发现的设计模式识别方法，将抽象语义图作为系统源码和设计模式签名的中间表示，将在系统源码中发现设计模式实例的问题转化成在非连通图中发现同构子图的问题。设计模式签名描述了设计模式的结构和行为特征，并转换成确定有限自动机，有限自动机的终态代表着特定的设计模式。子图发现算法包括了搜索集初始化、子图扩展和子图集合并等方面。该算法利用确定有限自动机来指导候选子图的生成，并且该算法只需运行一次就可以发现所有设计模式的实例。通过在三个开源项目进行实验，评估了该方法的精确性和以及效率。为了提高算法的性能，本文选择数据分解技术和基于线程的共享地址空间编程模型将原有算法设计成并行的算法。改进后的算法大幅提高了运行效率，运行时间减少了百分之三十。关键词：设计模式识别；子图发现；并行算法AbstractDesign patterns have been widely adopted by modern software industry to reuse the best practices and improve the quality of software systems. However, many systems are legacy and the design documents is often missing, this retard the comprehension of systems design and architecture during maintenance actives.Design patterns are normally described informally to understand and used them easily in practice; researchers need to characterize design patterns formally during design pattern detection. Related work uses several intermediate representations of software systems and design patterns, and introduces or proposes some algorithms to detect design pattern instances. This paper presents an algorithm based on subgraph discovery to recognize instances of design patterns in a software system. In the approach, the system and design patterns are both described with Abstract Syntax Graph (ASG), therefore finding a design pattern is to match ASG sub-structures with pattern signatures. Design pattern signatures describe the structural and behavior characteristics of design patterns and are transformed into Deterministic Finite Automaton (DFA).Subgraph discovery consists of search list initialization, subgraph extension and subgraph combination. This approach is to use DFA to guide the candidate generation and it recognizes all the pattern instances in one pass. Experimental evaluation on three open-source project demonstrates the accuracy and efficiency of proposed approach.To improve the performance, this paper chooses data decomposition technique and shared-address-space programming model based on threads to design a parallel approach, which improves efficiency greatly and reduces run time by 30%.Key words: design pattern detection; subgraph discovery; parallel algorithm目录第一章绪论11.1研究背景及选题意义11.2研究现状及存在问题21.3主要研究内容及特色41.4本文结构安排5第二章子图挖掘和并行算法62.1子图挖掘62.1.1图定义62.1.2图匹配72.1.3频繁子图挖掘92.1.4Subdue算法132.2并行算法152.2.1基本概念152.2.2并行性识别162.2.3分解技术172.2.4编程模型202.2.5并行算法模型222.3小结24第三章子图发现算法的设计与实现253.1图表示253.2自动机283.3子图发现293.3.1初始化搜索集323.3.2扩展子图343.3.3合并子图集373.4并行算法设计393.4.1数据分解403.4.2线程并行413.4.3临界区设置423.5小结44第四章实验结果454.1实验数据介绍454.1.1JUnit454.1.2JHotdraw454.1.3JRefactory454.2实验结果分析464.2.1识别的设计模式实例474.2.2自动机的作用484.2.3并行的效率494.3小结51第五章总结和展望52参考文献54致谢语57ContentsChapter 1:Introduction11.1Background and Significance11.2Research Status and Problems21.3Main Research and Contributions of The Paper41.4Outline of Thesis5Chapter 2:Subgraph Discovery and Parallel Algorithm62.1Subgraph Discovery62.1.1Graph Definition62.1.2Graph Matching72.1.3Frequent Subgraph Discovery92.1.4Subdue132.2Parallel Algorithm152.2.1Basic Concepts152.2.2Parallelism Detection162.2.3Decomposition Techniques172.2.4Programming Model202.2.5Parallel Model222.3Summary24Chapter 3:Implementation and Design of Subgraph Discovery253.1Graph Represention253.2Automaton283.3Subgraph Discovery293.3.1Search List Initialization323.3.2Subgraph Extension343.3.3Subgraph Combination373.4Design of Parallel393.4.1Data Decomposition403.4.2Thread Parallel413.4.3Critical Area Setting423.5Summary44Chapter4: Experimental Evaluation454.1Introduction of Experimental Data454.1.1JUnit454.1.2JHotdraw454.1.3JRefactory454.2Analysis of Experimental Result464.2.1Detected Instances of Design Patterns474.2.2Usage of DFA484.2.3Efficiency of Parallel494.3Summary51Chapter 5: Conclusions and future works52References54Acknowledgements57第一章 绪论第一章 绪论随着包括化学情报学、生物信息学、计算机视觉、视频索引、文本检索以及Web分析在内的广泛应用，图作为一种一般数据结构在复杂结构和它们之间相互作用建模中变得越来越重要。为了进一步进行特征化、区分、分类和聚类分析，挖掘频繁子图模式已经成为一项重要的任务。此外，图作为一种具有天然并行性的数据结构，满足了多核时代下并行编程的基本需求。巨大的数据量以及数据的地理上分布特性要求采用有效的并行算法来解决诸如规则挖掘、聚类、分类以及时间序列分析等问题。本章将对目前的研究现状以及存在的问题等进行阐述，最后对本文研究内容以及本文结构安排等进行总体阐述。1.1 研究背景及选题意义近年来，频繁项集挖掘算法可以有效地在大型事务或关系数据集中挖掘出项之间有趣的关联规则1。然而，随着数据挖掘技术被逐渐应用于非传统领域，现有的频繁模式识别算法所假设的事务框架不能有效地对新领域进行建模。一种取而代之的方法是用图对这些数据集进行建模。特别地，每个图中的顶点对应一个传统频繁项集中的项，每条边对应两个项之间的关系。在这种模型中，边和顶点可能会有与它们相关的标签。使用图表示方法，查找频繁模式的问题就变成在一张数据集图中查找频繁出现的子图。由于现在的软件项目大都包含数目众多的组件，其结构变得相当复杂和混乱，从而不利于软件系统的维护和改进。在软件系统的整个生命周期中，软件维护是十分重要和复杂的阶段，可以占据整个投入的50%-70%，程序理解在软件维护阶段起着重要的作用，尤其当程序结构较复杂，而且相关的文档与系统不同步时。软件工程数据，如代码、代码的修改历史、执行路径以及错误报告等，蕴含着大量与项目管理、软件平台技术有关的信息和知识。如果可以从上述大量的数据中挖掘出潜在的具有高度价值的信息和知识，将更好地进行项目管理，生产出高质量的代码。设计模式是软件设计中的一些普遍设计问题的解决方案，可以用统一的格式加以描述，主要有：意图、动机、适用性、结构、参与者、协作、实现细节和代码示例等2。从软件系统中的源码中发现所使用的设计模式已经成为许多研究领域的关键课题，如在反向工程和代码重构方面。通过发现软件系统中使用的设计模式可以展现系统设计的结构，帮助新系统开发人员更好地理解系统的设计和实现决策。但是现有的设计模式识别方法3-5一般都存在大型系统搜索空间爆炸和新模式的扩展性等问题，因此有必要设计一种全新的基于子图发现的设计模式识别方法，准确并且高效地识别出软件系统的设计模式实例。1.2 研究现状及存在问题图在诸如电路、图像、化合物、蛋白质结构、生物学网络、社会网络、Web、工作流和XML文档等复杂结构建模方面日趋重要。图相关算法已经被应用于化学情报学6-9、计算机视觉10、视频索引11和文本检索12等领域。在各种各样的图模式中，频繁子结构是可以在图集合中发现的非常基本的模式。频繁子结构可以用来刻画图集合的特征，区分不同的图组群，对图进行分类和聚类，构造图索引和更方便地在图数据库中进行相似性搜索。Borgelt 和Berthold13通过对比不同类中频繁图的支持度，发现HIV甄别数据集中活跃的化学结构。Deshpande 等人14用频繁子结构作为特征来对化学结构进行分类。Huan等人15成功地利用频繁图挖掘技术来研究蛋白质结构族。Yan等人16使用频繁图模式在图数据库中建立图索引和进行相似性搜索，他们的方法胜过传统的基于路径的索引签名方法。Koyuturk等人17提出了一种在生物网络中识别频繁子图的方法。AGM是最初的频繁子图发现算法，由Inokuchi等人18提出。这种方法用于发现在图数据集中所有频繁出现的满足最小支持度约束的子图。AGM类似于基于Apriori项集挖掘算法19。Apriori特性也被其他的子图挖掘算法应用，例如FSG20和Path-join21算法。所有的这些方法都是通过连接两个频繁子结构产生一个大的子结构候选，但是各自采用不同的候选产生策略：AGM基于顶点，FSG基于边，Path-join基于边不交叉路径。在频繁子结构挖掘的上下文中，基于Arpiori的算法有两种需要考虑的开销：(1)连接两个大小为k的频繁子结构产生大小为k+1的图候选。(2)检查每个候选的频繁度。这些开销导致了基于Apriori算法的性能瓶颈。为了避免这种基于Apriori算法的系统开销，最近提出了一种非基于Apriori的算法，如gSpan22，MoFa23，FFSM24，SPIN 25， 和 Gaston26等。这些算法的灵感来源于PrefixSpan27，TreeMinerV28，和FREQT29等方法在挖掘序列和树的应用。所有的这些算法都采用了PatternGrowth的方法30，这种方法试图从单个模式直接扩展模式。致力于完整的频繁子图搜索方法，例如FSG和gSpan，能保证找到所有满足用户指定约束的子图。虽然完整性是基本和合理的需求，但是这些完整方案所带来的副作用是这些系统都会典型地产生大量子结构，这些子结构提供领域内少量有价值信息。结果导致有趣的子结构要从这些大量子结构中识别出来需要靠领域专家或者其他自动的方法来深入这个领域。相较于精确图匹配算法的完整性，贪心搜索算法用启发式搜索方法来提供近似的解决方案。在这个领域中的先驱研究是Subdue算法31。然而使用Subdue算法来识别设计模式，存在两个问题：首先Subdue算法采用启发式集束搜索方法，会丢失设计模式；其次，一些不可能作为设计模式候选集的子图会被重复发现，从而导致不必要的系统开销。上述算法所面对的一个共同问题是无法充分利用CPU，因为它们均以串行方式在计算机上运行。在频繁子结构的挖掘中都涉及到子图同构检验，这是一个NP完全问题，其计算复杂度相当高。当程序以独占CPU的方式串行执行时，子图同构后面的指令必须等待。解决这一问题的有效办法是将程序执行方式由串行变为并行，充分利用操作系统的并发调度和CPU的分时执行。微处理器技术的高速发展则保证了并行计算的可行性。在过去的十年里，处理器的时钟频率从大约40 MHz（例如，1988年前后的MIPS R3000）增加到超过2GHz（例如，2002年前后的奔腾IV）。2005年多核处理器的出现则进一步让并发执行的多个程序以更高效的并行方式执行，也可以让一个程序中多个并发执行的线程以并行的方式执行，程序的执行效率有了本质的提升。在实践中，设计一个非平凡的并行算法包括下面某些步骤或者所有的步骤：l 识别能并发执行的任务部分。l 映射各并发任务块到并行运行的多处理器上。l 分布与程序有关的输入、输出和中间数据。l 管理对由多处理器共享的数据的访问。l 在并行程序执行的各个阶段对处理器进行同步。上面的每个都有几种选择，但通常只有少数组合所得到的并行算法，能够产生与要解决问题所用的计算和存储资源相匹配的性能。一般地，在不同并行体系结构或不同并行编程模式中要取得最佳性能，要使用不同的选择组合。1.3 主要研究内容及特色本文的研究内容是基于子图发现的设计模式识别算法。首先本文采用抽象语义图(Abstract Semantic Graph, ASG)来描述被研究的系统和设计模式，这样设计模式的识别就转换为图的子图发现问题；然后，提出了一个子图发现算法用来识别系统中的设计模式实例；最后，在开源系统上进行一系列的实验以评估该方法。本研究的着重点是子图发现算法以及并行算法的设计与实现。本文首先从三个方面对子图发现算法进行描述：(1)搜索集初始化：旨在查找所有出现在数据图集中的单边子图，设计的重点是尽量减少子图同构匹配次数以提高程序性能。(2)子图扩展：通过确定有限自动机（Deterministic Finite Automaton，DFA）得到从此状态到下一状态所需扩展边的迁移信息，添加一条边将k边图扩展成k+1边图，并且保证扩展后的子图与DFA下一状态同构。(3)子图集合并：定义一个链表结构保存候选子结构，提供子图合并的操作，并处理复制图的产生问题。本文接着从三个方面阐述并行算法的设计：(1)数据分解：对计算中的数据进行划分，然后在此基础上推导从计算到任务的划分，从而得到算法的并发性。(2)线程并行：提供一种基于Java线程的共享地址空间编程模式。(3)临界区设置：分析并行算法中共享的数据，设置临界区，避免发生竞争。相比之前Tsantalis等人的研究5，本算法特色如下：(1)本算法可以找到更多的设计模式实例，之前的算法将系统描述成图和矩阵，由于图中顶点数量过于庞大，将系统按照层次划分成一系列子系统，这样跨越多个子系统的模式实例就无法识别到；而本算法是基于非连通图的子图发现算法，无须对系统进行划分。(2)本算法使用了DFA来去除那些不可能作为设计模式候选集的子图，减少了不必要的系统开销，效率更高。(3)本算法只需运行一次就可以发现所有模式的实例，而之前的算法是运行一次只能发现一个模式的实例。1.4 本文结构安排本论文重点探讨基于子图发现的设计模式识别方法和并行设计的实现，总共分为五章，组织结构如下：第一章 绪论，介绍了课题研究背景及实际意义、频繁子图发现算法的国内外研究现状以及存在的问题等，最后阐述了本文的研究内容以及创新点；第二章 介绍关于子图挖掘和并行算法的相关知识，并分析它们在实践中的应用；第三章 描述了子图发现算法的详细设计与实现，并阐述了并行算法设计的细节；第四章 实验结果分析，分析本算法在三个开源系统上进行实验得出的结果，以评估本研究所采用方法的效果；第五章 对本论文的总结和展望，分析了本研究尚待优化之处，并对下一步研究进行了展望。5第二章 子图挖掘和并行算法第二章 子图挖掘和并行算法本章将介绍子图挖掘和并行算法的相关知识。子图挖掘包含了图的定义、图匹配、频繁子图挖掘以及Subdue算法等内容，在并行算法这一节中将介绍并行算法的基本概念、如何识别并行性、分解技术、编程模式和并行算法模型。2.1 子图挖掘基于图的数据挖掘提出时间并不长，但是由于图论作为数学的一个研究领域已经有很长的研究历史，因而图挖掘发展很快，并被广泛地应用到许多领域中。如在化学领域中，通过频繁子图发现算法找出构成有毒物质的分子结构，以及通过对网站浏览日志的挖掘分析出最频繁的浏览模式等。在各种各样的图模式中，频繁子结构是可以在图集合中发现的非常基本的模式。频繁子结构可以用来刻画图集合的特征，区分不同的图组群，对图进行分类和聚类，构造图索引和更方便地在图数据库中进行相似性搜索。因此，对基于图的频繁子图发现算法的研究是非常必要的。一些频繁子图挖掘算法只能处理特殊种类的图：带标记的、无向的、没有任何特殊约束的简单连通图。然而许多应用或用户可能需要对要挖掘的模式施加各种约束，或者寻找不同的子结构模式。本节也将研究被约束的子结构挖掘。2.1.1 图定义用无限制的字符标签来定义属性图是一种普遍的定义图的方式。事实证明，以下所给的定义，针对众多模式识别应用有足够的灵活性。(1)图给定一个顶点标签字符集LV和一个边标签字符集LE，定义图g为四元组g = (V, E, , )，其中l V代表一个有限顶点集l E V V 代表边集l : V LV 代表顶点标签的映射方法l : E LE 代表边的映射集合V可以看作一组顶点的标识符，而且常选择V = 1,|V|。集合V定的了顶点，边集E代表了图的结构。也就是说，一个顶点 u V 通过边e = (u, v) 连接顶点v V，如果(u, v) E。通过给LV和LE 赋值，标签映射可以用于整合顶点和边的信息到图中。通常对于标签字符没有限制。然而，在实际应用中，标签字符集L常被定义为一个固定大小的向量空间，L = Rk ，或者离散集的符号，L = s1,sk。从理论上说，顶点和边有更多复杂的标签字符串或者图形自身。上面介绍的图定义包含许多特殊的情况。例如，定义一个无向图，对于每条边(v, u) E还需要满足(u, v) E，因为(v, u) = (u, v)。对于无属性的图，应该定义标签字符集LV = LE = ，这样每个节点和每条边都被赋予空值。另外，空集被定义为 g = (, , , )。对于一些应用，识别一个小图是否存在于一个大图中是非常重要的。例如，在大图中是否存在一系列对象而小图只是其中的一个特殊对象。这直观地导出了子图的正式定义。(2)子图g1 = (V1, E1, 1, 1)和g2 = (V2, E2, 2, 2)是两张图，g1是g2的子图，记成g1 g2，如果满足l V1 V2l E1 = E2 (V1 V1)l 对于所有u V1 都满足1(u) = 2(u)l 对于所有(u, v) E1 都满足1(u, v) = 2(u, v)相反地，如果g1是g2的子图，则称g2是g1的超图。有时，此定义的第二个条件被记为E1 E2，并且一个子图如果符合更加严格的上述条件则被称为诱导子图。在下一部分，将介绍图匹配问题。2.1.2 图匹配图匹配分为精确的图匹配和容错的图匹配方法。1.精确图匹配精确的图匹配的目标是判断两张图的标签，结构，或者部分结构是相同的。判断特征向量或者字符串的相等很容易，但是相同的计算对于图而言要复杂得多。因为一个图的顶点和边一般不会按顺序排列，不像特征向量的组成部分或者字符串的字符，图相等的问题也就是图同构问题，需要很高的计算复杂度。(1)图同构 g1 = (V1, E1, 1, 1)和g2 = (V2, E2, 2, 2)是两张图。g1和g2之间的图同构是一个满足以下条件的双向映射f: V1 V2l 对于所有u V1，满足1(u) = 2(f(u)l 对于所有e1 = (u, v) E1 ,存在一条边e2 = (f(u),f(v) E2，这样1(e1) =2(e2)l 对于所有e2 = (u, v) E2 ,存在一条边e1 = (f-1(u),f-1(v) E2，这样1(e1) =2(e2)如果两张图中存在一个图同构关系，则称这两张图是同构的。依据上述定义，两张同构图的结构和标签都是相同的。为了建立同构关系，需要匹配第一张图和第二张图的每个顶点，这样保证了边结构并且边和顶点的标签是一致的。图2-1(a)和(b)描绘了两个不带标签的同构图。(a) (b) (c)图2-1：同构图和同构子图最简单判断两张图是同构关系的方法是遍历一颗考虑所有点对点关系的搜索树32。树的分支不断扩大，直到两张图的映射顶点所连接的边结构不对应相同时。如果顶点和边加上标签，则匹配的顶点和边标签也必须一致。当到达搜索树的叶子节点时，则说明了按照结构和标签的约束成功映射了所有的顶点，也就是说已经找到了一个图同构关系。一般而言，这种方法的计算复杂度是两个图顶点数的指数级。与图同构问题很相近的是在一张大图中检测小图是否存在的问题。如果图同构等同于图相等的定义，则子图同构可以认为子图相等。(2)子图同构g1 = (V1, E1, 1, 1)和g2 = (V2, E2, 2, 2)是两张图。单向映射f: V1 V2 称为从g1到g2的子图同构当且仅当存在一个子图 g g2，f是g1和g的一个同构映射。存在从g1到g2的子图同构关系当且仅当图g2可以通过删除一些顶点和边转换成与g1同构的图。如图2-1(a)和(c)，展示了两张具有子图同构关系的图。子图同构问题同样可以用上面提到的图同构问题的解决方案32。可以得知，子图同构问题属于NP完全问题。2.容错的图匹配基于现实世界模式的图表示方法中，同类型的图在结构和标签上有所不同是普遍的情况。因此，图匹配系统需要把结构错误列入考虑范畴。图修正距离33, 34是一种直观的方式把容错融入图匹配过程中，并适用于几乎所有类型的图。本来，修正距离是字符串匹配35而开发的，并且为字符串和图提出大量修正距离的变形和扩展方案。关键思想是通过结构修改反射而来的修正操作对结构变异进行建模，例如消除单个顶点或者对边附加属性的修正。一套标准的修正操作包含添加顶点，删除顶点，替换顶点，添加边，删除边和替换边操作。例如，应用顶点删除操作等同于从一张图中删除一个顶点，应用边替换操作等同于改变边的标签值。在本节余下部分将介绍频繁子图挖掘算法和Subdue算法，其中频繁子图挖掘算法在计算子图频繁度时采用精确的图匹配技术，而Subdue算法则使用了非精确的图匹配方案用以查找能最佳压缩图的子图。2.1.3 频繁子图挖掘在介绍图挖掘方法之前，需要先给出一些关于频繁图挖掘的基本定义。图g的支持度support(g)（或频度frequency(g)）定义为g作为子图在D中出现的百分比（或次数）。频繁图是支持度不小于最小支持度阈值min_sup的图。频繁子结构的挖掘通常包含两个步骤。第一步，生成频繁子结构的候选集。第二步检测每一个候选图的频繁度。大部分研究专注于第一步的优化，因为第二步涉及到子图同构检验，其计算复杂度相当高。接下来将考察频繁子结构挖掘的各种方法。一般，解决这一问题的基本方法有两种：基于Apriori方法和PatternGrowth方法。1.基于Apriori的方法基于Apriori的频繁子结构挖掘算法类似于基于Apriori的频繁项集挖掘算法。频繁图的搜索开始于小“规模”图。按照自底向上的方式产生具有附加顶点、边或路径的候选图。图规模的定义依赖于所使用的算法。算法：Apiori。基于Apriori的频繁子结构挖掘算法。输入：图数据集D，最小支持度阈值min_sup输出：频繁子结构的集合Sk方法：S1 数据集中的单个频繁元素call Apriori(D, min_sup, S1);procedure Apriori(D, min_sup, Sk)1: Sk+1 ;2: for each frequent gi Sk do3: for each frequent gj Sk do4: for each size (k+1) graph g formed by the merge of gi and gj do5: if g is frequent in D and gSk+1 then6: insert g to Sk+1;7: if Sk+1 then8: Apriori(D, min_sup, Sk+1);9: return;图2-2：Apriori算法图2-2描述了频繁子结构挖掘的基于Apriori方法的一般框架，该算法称为Apriori算法。Sk是规模为k的频繁子结构的集合。本文将会在后面介绍具体的基于Apriori方法，阐明图规模的定义。基于Apriori的方法采用逐层挖掘方法，每次迭代，新发现的频繁子结构规模增加一个单位。这些新的子结构的产生是通过连接上一次调用Apriori发现的、两个相似但稍微不同的频繁子图。第4行泛化了候选的产生过程。然后，检查新形成的图的频繁度。下一轮使用那些已发现的频繁子图来产生更大的候选。基于Apriori的子结构挖掘算法设计的最复杂的步骤是候选产生。在频繁项集挖掘中，候选的产生是简单的。例如，假设有两个大小为3的频繁项集：（abc）和（bcd）。通过连接，所产生的大小为4的频繁项集候选是（abcd）。然而，频繁子结构挖掘中的候选产生问题要比频繁项集挖掘中的候选产生问题更加复杂，因为连接两个子结构的方式可以有多种。最近提出的基于Apriori的频繁子结构挖掘算法包括AGM、FSG和Path-join方法等。AGM和基于Apriori的项集挖掘算法具有类似的特点。FSG和Path-join以基于Apriori的方式考察边和连接。每一种方法都利用了不同的候选产生策略。图2-3：FSG两个子结构模式及其潜在的候选FSG算法采用基于边的候选产生策略，在每一次调用Apriori时通过增加一条边来扩大子结构的规模。两个大小为k的模式合并，当且仅当它们共享相同的具有k-1条边的子图，该子图称为核。这里，图的规模取图中边的个数。新形成的候选包括核和来自大小为k的模式中的两条附加边。图2-3给出了由两个结构模式形成的潜在候选。每个候选都比这两个模式多一条边。这个例子说明连接两个结构形成较大模式候选的复杂性。2.PatternGrowth方法由于逐层产生候选，基于Apriori的方法必须使用宽度优先搜索（BFS）策略。为了确定一个大小为k+1的图是否频繁，必须检查它的所有对应的大小为k的子图来得到它频繁度的上界。这样，在挖掘大小为k+1的子图之前，类Apriori方法通常必须完成大小为k的子图的挖掘。因此，类Apriori的算法需要采用宽度优先搜索。相反，模式增长方法在搜索方式上更加灵活。它可以使用宽度优先搜索，也能使用深度优先搜索（DFS），后者占用较少内存。图g可以通过增加一个新边e来扩展。新形成的图记作g x e。边e可能给图g引入新顶点，也可能不引入。如果e引入一个新顶点，则新图记作g xf e，否则记作g xb e，其中f或b表示扩展是前向或后向的。图2-4给出了基于模式增长的频繁子结构挖掘的一般框架，该算法称为PatternGrowth。对于每个发现的图g，它递归地进行扩展，直到发现所有嵌入g的频繁图为止。一旦没有频繁图产生，递归停止。算法：PatternGrowth。简单的基于模式增长的频繁子结构挖掘。输入：频繁图g，图数据集D，最小支持度阈值min_sup输出：频繁图的集合S方法：S ;call PatternGrowth(g, D, min_sup, S);procedure PatternGrowth (g, D, min_sup, S)1: if g S then return;2: else insert g to S;3: scan D once, find all the edges e such that g can be extended to g x e;4: for each frequent g x e do5: Call PatternGrowth(g x e, D, min_sup, S);6: return;图2-4：PatternGrowth算法PatternGrowth简单但是效率低。它的瓶颈是扩展图的低效率。同样的图可能重复发现多次。例如，可能存在n个不同的n-1条边的图，可以扩展成相同的n条边的图。相同图的重复发现导致计算的低效率。称二度发现的图为复制图（duplicate graph）。尽管PatternGrowth的第1行删除复制图，但是复制图的产生和检测可能增加工作量。为了减少复制图的产生，每个频繁图应该尽可能适当地扩展。这个原则导致一些新算法的设计。一个典型的例子是下面将要介绍的gSpan算法。gSpan算法旨在减少复制图的产生。它不需要为检测复制图来搜索先前发现的频繁图。它不扩展任何复制图，但是仍保证发现的频繁图的完全集。为了遍历图，gSpan采用深度优先搜索。初始，随机选择一个起始顶点，并且对图中访问过的顶点做标记，这样，能够分辨出哪些顶点已经访问过。被访问过得顶点集合反复扩展，直到建立一个完全的深度优先搜索（DFS）树。2.1.4 Subdue算法尽管FSG和gSpan能保证找到所有满足条件的子图，但这些频繁子图挖掘算法只能处理简单连通图，而且这些完整方案所带来的副作用是这些系统都会典型地产生大量子结构，这些子结构提供领域内少量有用信息。相较于精确图匹配算法的完整性，贪心搜索算法Subdue用启发式搜索方法来提供近似的解决方案。同时，相比于FSG和gSpan，Subdue算法对于输入图的要求更少。表2-1列出了几种算法分别可处理的输入图，扩展后的FSG和gSpan算法不列入其中。表2-1：几种算法可处理的输入图图类型DirectedLabelsMultigraphSelf-edgesNumber of Vertices/EdgesSubdue文字/数字无限制FSG文字/数字无限制gSpan数字最大254/254作为一种无需监管的挖掘算法，Subdue算法查找输入图的一个最佳压缩子结构或者子图。Subdue在它的主搜索算法用的是集束搜索的一种变形方法，算法大致框架如图2-5所示。Subdue算法中的一个子结构包含一个子图定义和所有它在图中的实例。搜索的初始状态是所有单顶点的子结构，搜索的唯一操作就是ExtendSubstructure操作。顾名思义，它以各种可能的方式扩展子结构，通过添加一条边和一个顶点，或者当两个顶点都已经存在时只添加一条边。算法：SUBDUE。查找最佳地压缩图集子结构的算法。输入：图数据集Graph，束宽度BeamWidth，最佳压缩图集的大小MaxBest，最大子结构数量MaxSubSize，处理子结构的上限Limit输出：最佳压缩图集的子结构集合BestList1: ParentList = Null;2: ChildList = Null;3: BestList = Null;4: ProcessedSubs = 0;5: Create a substructure from each unique vertex label and its single-vertex instances;6: Insert the resulting substructures in ParentList;7: while ProcessedSubs Limit and ParentList not empty do8: while ParentList is not empty do9: Parent = RemoveHead(ParentList);10: Extend each instance of Parent in all possible ways;11: Group the extended instances into Child substructures;12: for each Child do13: if SizeOf(Child) less than MaxSubSize then14: Evaluate Child;15: Insert Child in ChildList in order by value;16: if BeamWidth Length(ChildList) then17: Destroy substructure at end of ChildList;18: Increment ProcessedSubs;19: Insert Parent in BestList in order by value;20: if MaxBest Length(BestList) then21: Destroy substructure at end of BestList;22: Switch ParentList and ChildList;23: return BestList;图2-5：Subdue算法算法通过对每个当前状态的子结构应用ExtendSubstructure操作迭代运行。然而结果状态并没有包含所有应用ExtendSubstructure操作生成的子结构。子结构被保存在一个队列中，并通过他们的压缩量（有时也指值）进行排序。压缩量是用最小描述长度（MDL）36原理计算的。只有最大的束结构会保留在队列中，作为主循环下一轮要扩展的对象。当达到子结构的最大扩展数或者搜索空间枯竭时，搜索终止。一旦搜索终止，Subdue算法返回一个最佳子结构的链表，图可以用这些最佳子结构进行压缩。压缩过程是将输入图出现的所有子结构实例用单个顶点替换，这个顶点代表了子结构的定义。所有指向或者指出被替换的实例将指向或者指出代表此实例的顶点。Subdue算法将可以在这个压缩图中多次被调用，这个过程可以重复多次，也就是迭代。2.2 并行算法算法设计是借助计算机解决问题的一个关键部分。串行算法实质上是用串行计算机解决问题的方法或基本步骤序列。与此类似，并行算法讲述的是怎样用多处理器解决问题。然而，设计并行算法远远不仅仅是详细说明这些步骤。至少，一个并行算法增加了并发性的维，设计者必须指定能同时执行的步骤集。为了从使用并行计算机获得性能上的好处，这是必不可少的。在本节中，首先给出一些并行算法的概念定义，然后阐述如何识别并行性，最后对分解技术、编程模型和并行算法模型进行了详细描述。2.2.1 基本概念分解（decomposition）是指把一个计算分为很多小的部分，其中的一些或所有部分都可能被并行执行。任务（task）是程序员定义的计算单元，其中为主要计算通过分解得到的划分。减少解决整个问题所需实践的关键是多任务同时执行。任务可以是任意大小的，但是一旦定义好，就被认为是不可再划分的计算单元。由问题分解出的任务大小可能并不相同。分解得到的所有任务都是独立的，可同时执行，也可以按任意顺序执行。然而，通常情况下，有一些任务可能需要使用别的任务所产生的数据，这样就要等到这些数据产生后再执行。任务依赖图（task-dependency graph）可以用于抽象表示任务间的依赖关系和任务的执行次序关系。任务依赖图是一种有向无环图，其中的节点表示任务，有向边就代表节点间的依赖性。对应于一个节点的任务，只有当与此节点相连的输入边相连的所有任务都执行完毕才能执行。注意，任务依赖图可以是不连接的，它的边集也可能是空的。本文中，术语“进程”并不严格等同于操作系统的进程定义，本节将使用进程（process）来表示执行任务的处理代理或计算代理。给进程分派任务的机制称为映射（mapping）。有意义的映射是把由边相连的任务映射到同一个进程上，因为这样才能防止任务间的交互转变成进程间的交互。在讲述并行算法设计的文字中，处理器是指实际执行计算的硬件部件。在多数情况下，进程和处理器都有一一对应的关系，并且可以假定进程的数量和并行计算机上的CPU的数量一样多。然而，有时候可能要从更高的抽象层次来表达某一个并行算法，尤其当复杂算法