首页 > 编程语言 > 详细

静态频繁子图挖掘算法用于动态网络——gSpan算法研究

时间:2017-09-17 14:42:10      阅读:2095      评论:0      收藏:0      [点我收藏+]

标签:取图   百分比   enumerate   内置   最终   orm   提升   time   led   

 

摘要

 

随着信息技术的不断发展,人类可以很容易地收集和储存大量的数据,然而,如何在海量的数据中提取对用户有用的信息逐渐地成为巨大挑战。为了应对这种挑战,数据挖掘技术应运而生,成为了最近一段时期数据科学的和人工智能领域内的研究热点。数据集中的频繁模式作为一种有价值的信息,受到了人们的广泛关注,成为了数据挖掘技术研究领域内的热门话题和研究重点。

传统的频繁模式挖掘技术被用来在事务数据集中发现频繁项集,然而随着数据挖掘技术应用到非传统领域,单纯的事务数据结构很难对新的领域的数据进行有效的建模。因此,频繁模式挖掘技术需要被扩展到了更为复杂的数据结构上。

图不但可以对数据实体进行建模,还可以对数据实体之间的复杂关系进行建模,因此图可以作为一个通用的数据模型,故而与图有关的模式挖掘的研究就显得相当重要。在图数据集中挖掘频繁子图模式是一种困难的问题,虽然至今已经提出了很多的算法,但在将算法应用在具体应用问题上的时候,仍然存在很多待解决的问题。

gSpan算法是用于静态频繁子图挖掘的经典算法。然而除了静态图,目前使用图模型进行建模的具体应用很多都呈现出动态特性。因此本文试图将用于静态频繁子图挖掘的gSpan算法应用于动态网络。

本文首先介绍频繁子图挖掘问题的基本概念和相关算法,国内外的研究现状,并阐述频繁子图挖掘算法研究的应用背景和现实意义。然后详细介绍gSpan算法的基本思想和实现方法,并在静态图集数据和动态网络数据上对实现的程序进行测试,并分析算法的局限性和改进的方向。

 

关键词: 数据挖掘 图挖掘 频繁子图挖掘 频繁模式挖掘 gSpan

 

 

ABSTRACT

With the continuous development of information technology, it is easy to collect and store a large amount of data. However, how to extract useful information from the massive data becomes a big challenge. In order to deal with this challenge, data mining technology emerges, and has become a hotspot in the field of data science and artificial intelligence. As a kind of valuable information, the frequent patterns in data sets have been paid more and more attention and become a hot topic in the field of data mining.

Traditional frequent pattern mining techniques were used in the transaction data set to find frequent item sets, but with the application of data mining technology to the nontraditional areas, it is difficult to model new domain data by using transaction data structure. So frequent pattern mining techniques need to be extended to more complex data structures.

Graph not only can be used to model the data entities, also can be used to model the complex relationship between data entities, so the Graph can be used as a common data model, therefore the research on Graph mining is very important. Mining frequent subgraph patterns in graph set is a difficult problem. Although many algorithms have been proposed so far, when the algorithm is applied in the specific application problems, there are still many problems to be solved.

GSpan algorithm is a classical algorithm for static frequent subgraph mining. However, in addition to static graphs, many of the specific applications that are currently modeled with the graph are presented with dynamic characteristics. Therefore, this paper attempts to apply the gSpan algorithm for static frequent subgraph mining to dynamic networks.

This paper first introduces the basic concepts and related algorithms of frequent subgraph mining, the research status at home and abroad. Then I will introduce the basic idea and implementation method of gSpan algorithm in detail, and carries on the test on the static graph set data and the dynamic network data to the program, and analyzes the limitation of the algorithm and the direction of improvement.

 

 

Keywords:    data mining graph mining frequent subgraph mining frequent pattern mining gSpan

 

 

目录

目录

封面    1

摘要    3

ABSTRACT    I

目录    I

第1章 绪论    1

1.1 研究背景    1

1.2 国内外研究现状    2

1.3 研究目的和主要内容    3

1.4 论文的组织结构    4

第2章 基础理论    5

2.1 图论基础    5

2.2 频繁子图挖掘基础    5

2.3 频繁子 图挖掘算法的一般过程    7

2.3.1 候选生成    7

2.3.2 候选剪枝    8

2.3.3 处理图同构    8

2.3.4 支持度计数    8

2.4 本章小结    8

第3章 静态频繁连通子图挖掘算法    9

3.1 模式增长方法:一个朴素的算法框架    9

3.2 gSpan算法思想    10

3.2.1 图的规范化表示和规范化扩展思想概述    11

3.2.2 图的序列化    12

3.2.3 规范化表示    13

3.2.4 规范化扩展    13

3.3 gSpan算法介绍    14

3.3.1 gSpan算法框架    14

3.3.2 gSpan算法分析    16

第4章 算法实现和性能测试    18

4.1 算法实现    18

4.1.1 程序总体设计    18

4.1.2 类的详细设计    19

4.1.3 程序编码实现    26

4.2 实验分析    26

4.2.1 实验环境介绍    26

4.2.2 实验数据介绍    26

4.2.3 实验结果分析    27

第5章 总结和展望    31

5.1 总结    31

5.2 展望    31

致谢    33

参考文献    34

 

 

  1. 绪论

     

  2. 研究背景

    大数据和云计算技术的发展使得存储并分析大量的数据成为可能。然而从大量的数据中发现有用的模式是一个很大的挑战。通常,由于目标数据量太大,我们根本无法使用传统的数据分析工具和技术处理。有时候,即使数据量相对较小,但是由于数据本身具有非传统的特点,使得我们也不能利用传统的方法和技术处理这些数据。

    数据挖掘技术是一种用于处理大规模数据的思维方法和技术手段,它是在信息时代数据爆炸的背景下产生的。因为数据的拥有者很难从海量的数据中获取有用的信息和知识,这促使人们产生了对数据分析技术的强烈需求。

    数据挖掘技术现在已经被广泛用于零售,保险,电信,银行等领域的数据分析。由于数据挖掘技术在各种信息产业中的广泛应用而且具有很大的实用价值,数据挖掘技术逐渐的成为了数据科学领域的研究重点。

    频繁模式挖掘是数据挖掘研究中的一个重要问题。频繁模式挖掘技术最初被用于"购物篮分析"。在由购物篮数据构成的事务数据集中发现频繁项集,进而发现高置信度的关联规则,进而为超市的销售策略提供建议。频繁模式挖掘技术 在数据挖掘技术中扮演了很重要的角色,不但能作为关联规则分析的基础,还能将对象的频繁模式作为对象的特征,进而在分类和聚类等其它数据挖掘任务中发挥基础作用。

    最初,频繁模式挖掘只适用于有限的数据表示,比如购物篮数据。然而真实的应用需求需要处理不同的数据类型。随着研究的深入,频繁模式挖掘所涉及的数据模型,也从最初的集合,到序列,树,栅栏和图。图数据广泛存在于我们的生活中,如化合物分子结构数据,蛋白质相互作用网络数据,万维网数据,社交网路数据,因此基于图的频繁模式挖掘算法的研究很有必要。图作为一种通用的数据结构可以对数据实体以及实体之间的复杂关系进行建模,因此频繁子图模式的挖掘在频繁模式挖掘中有着重要的地位,受到了更多的关注。

    后来,随着研究的深入,研究者试图将频繁子图模式的概念拓展到动态网络。因为很多复杂的系统都是随着时间不断演化的,静态网络建模的建模方法在某种程度上具有很大的局限性。因为随着时间的变化,人与人之间的关系也会发生变化;生物系统也在不断地发生变化,从更长远的时间角度来看,生物物种在进化过程中,其分子网络结构在不断地发生着。从一个人的生命的范围来看,一个人从孕育、成长、衰老到死亡,其身体内部的分子网络在不断地发生变化。所以复杂网络的变化几乎是无时无刻不再发生的。对复杂网络的某一时刻的快照进行分析,必然会失去与其动态特性有关的有用模式。随着图挖掘技术的不断发展,研究者试图将静态频繁子图挖掘算法应用于动态网络进而分析动态网络中的频繁模式[2]

    本论文以此背景为出发点,主要研究与静态频繁子图挖掘有关的算法并试图将其应用于动态网络。

  3. 国内外研究现状分析

    在很多的复杂系统中,实体和实体之间具有复杂的联系,这种复杂的关系很难使用一般的数据结构加以表达。图数据结构作为表述复杂关系的一种通用数据结构,成为了数据挖掘研究的热点和难点。在社交网络分析中,人与人之间的关系可以抽象为一个图,其中每个人可以作为图中的顶点,人与人之间的关系可以被抽象为图中的边。因此,对社会群体的分析,就转化为了对社交网络拓扑结构和顶点属性的分析。在生物科学领域,生物学家发现蛋白质基因结构配位实验是费时费力的工作,他们希望使用数据挖掘技术,以提高结构匹配实验的效率。蛋白质的复杂结构可以被描述为图,其中氨基酸是图的顶点,而接触残基则是顶点之间的边。通过对蛋白质结构图集的挖掘可以预先发现蛋白质结构之间的内在关系或者共享模式。在一组图上面挖掘频繁子图具有很重要的意义。频繁子图传递了很多有意义的结构化信息,比如热点网络访问模式,公共蛋白质结构,对象识别中的共享模式,电子支付中的欺诈检测等。正是由于这些应用的迫切要求,图挖掘成为数据挖掘领域研究的一个热点。

    频繁子图挖掘算法的核心是图的同构测试。在过去四十年里,许多著名的图的同构测试算法被发现。例如J. R. Ullmann的回溯法和B. D. McKay的贪心算法,以及大量的近似算法。然而,频繁子图挖掘问题并没有很好的被解决。在化学信息学领域,一些高效的算法被设计出来,用以在一组化合物中发现频繁的公共子结构。L. Dehaspe et al. 使用化合物的公共子结构来预测化合物的毒性。然而这些系统都难以应用大规模较大的数据集上,可拓展性并不是很好。L. B. Holder et al. 提出了SUBDUC算法用来挖掘近似的子结构模式,所以其不能挖掘全部的频繁模式。2000年左右,Inokuchi et al. 提出了一种基于Apriori的算法AGM用来发现频繁子图模式。后来Kuramochi Karypis进一步发展了Apriori的思想,使用一种更高效的图的表示结构和边的增长策略。这个算法叫做FSG,获得了巨大的性能提高。

    AGMFSG都利用了Apriori的模式增长思想。这些方法虽然减少了搜索空间,但仍然存在一些致命的问题,使得算法的执行要浪费很多的时间。比如:

    1. 大量的候选生成
    2. 多次扫描数据库
    3. 比较耗费时间的同构测试
    4. 难以发现比较大的频繁子图模式

    为了避免这些问题,2002年,X. Yan等人提出了一种高效的利用深度优先策略搜索子图空间的方法,并在此基础上给出了基于图的子结构模式挖掘算法gSpan[4]GSpan算法不同于AGMFSG算法,它没有采用Apriori的思想,而是利用边模式增长的方式深度优先挖掘频繁子图。随后在2003年,他们在gSpan算法的基础上进一步提出了挖掘频繁闭合子图的算法CloseGraph,频繁闭合子图是频繁子图的压缩表示。它可以有效地去除冗余的频繁子图,减少结果集的大小,并能保证不丢失任何信息。

    当然,还有很多相关的研究成果,这里不再赘述。综上所述,图模式挖掘算法多种多样,应用广泛。虽然,图模式挖掘具有很高的复杂性,但是该领域的研究已经展现出广阔的发展空间和蓬勃的生机。

  4. 论文主要内容和组织结构

  5. 论文主要内容

    图数据结构对实体集合及其之间的关系具有强大的建模能力,因而图数据结构被广泛用于对现实生活中各种各样复杂的系统进行建模。作为大数据一部分的图结构数据,是大数据中最难以分析的一部分,因此如何从图结构数据中提取有用的模式和知识,进而帮助我们预测网络的变化和发展至关重要。

    本文围绕静态频繁子图挖掘算法中的gSpan算法进行研究,独自实现gSpan

    算法并将其应用于动态网络数据,发现动态网络演化过程中稳定存在的模式。

  6. 论文组织结构

    本文各章节的内容组织如下:

    第一章:论述研究背景,介绍国内外的研究现状,阐明了本文的主要研究内容和组织结构。

    第二章:简要介绍静态频繁子图挖掘的数学基础和有关概念。重要阐述了频繁子图挖掘的基本定义和基础知识,图论的基础知识,频繁子图挖掘中遇到的问题,一些基础的频繁子图挖掘技术和思想。最后介绍了几个著名的频繁子图挖掘算法及其主要技术。

    第三章:详细介绍与gSpan有关的基本概念,包括DFS编码,DFS字典序,DFS编码树等。详细介绍gSpan算法的伪代码。

    第四章:详细介绍gSpan算法实现的总体设计和详细设计。重点介绍gSpan算法实现的数据结构。介绍算法分别在静态图集数据和动态网络数据上的测试结果,详细地分析测试结果。

    第五章:总结和展望。总结在本论文中所做的研究工作,分析本论文所做工作的不足之处,指出可以改进的方向。

     

  7. 图挖掘相关基础

  8. 图论基础

    图是一种用来对数据实体以及数据实体之间的复杂关系进行建模的数据结构,可以作为一种通用的数据模型对数据进行建模。也就是说,任何的数据模型,包括序列,集合,树等数据结构都可以一般化为图数据结构。图由顶点和边构成,一般我们只考虑顶点和边的连接关系,而不考虑其具体的位置。其中顶点代表任意的实体,边代表实体之间的关系。为了增强图模型的表达能力,我们还可以为图的顶点和边赋予任意的标号或者标号组,用于表示顶点和边所具有的属性或者属性集合。下面,给出图的一些形式化的定义。

    定义2.1 技术分享包含顶点集技术分享和边集技术分享。因此图的本质是顶点集上的二元关系。若二元组技术分享是有序的,即技术分享,则图技术分享有向图directed graph)。若二元组技术分享是无序的,即技术分享,则图技术分享无向图undirected graph)。一般在有向图中,用技术分享来表示顶点技术分享到顶点技术分享之间有一条边。在本文中,若不特别指出,图一般指的是无向图[2]

    定义 2.2 子图 G‘=(V‘, E‘)是另一个图G=(V, E)的子图,如果它的顶点集V‘V的子集,并且它的边集E‘E的子集。子图关系记作技术分享[2]

    定义2.3 两个图技术分享技术分享同构的,当且仅当顶点集技术分享技术分享之间存在双射,即技术分享中的任意两个顶点技术分享若有边相连,则这两个顶点在技术分享的映射顶点之间也有边相连[2]

     

  9. 频繁子图挖掘基础

     

    什么才是图数据集上有用的模式呢?频繁模式就是一种有用的模式,因为频繁出现的模式可能代表着这个数据集上比较本质的东西,当然也不排除代表着比较普通的东西。图数据集上的频繁出现的模式就是频繁子图。考虑到一组具有抗癌作用的化合物集合,是什么样的共性使得这组药物具有抗癌的作用呢?也就是抗癌的效用是如何体现在分子的结构上的 。我们可以做出判断,在这组化合物上频繁出现的子结构模式可能代表了抗癌的效用的本质。因此,我们想知道如何才能在这组化合物上发现频繁的子结构模式。如果把化合物抽象为图,其中图的顶点表示化合物的原子,图中的边表示化合物的化学键,那么,我们就可以通过挖掘图集中的频繁出现的子图模式来发现化合物数据集中频繁出现的子结构模式,以此来发现这组化合物抗癌效用的本质。这将为人工合成新的抗癌药物提供参考。除此之外,频繁子图挖掘还有很多应用,如表 21所示[3]

    21 不同应用领域中实体的图形表示

     

    图形

    顶点

    Web挖掘

    Web浏览模式

    Web页面

    页面之间的超链接

    计算化学

    化学化合物的结构

    原子或离子

    原子或离子之间的键

    网络计算

    计算机网络

    计算机和服务器

    机器之间的关联

    语义Web

    XML文档的集合

    XML元素

    元素之间的父子联系

    生物信息学

    蛋白质结构

    氨基酸

    接触残基

     

    定义 2.4 支持度 给定图的集合ζ,子图g的支持度定义为包含它的所有图所占的百分比,即[3]

        技术分享     

    定义 2.5 频繁子图挖掘    给定图的集合技术分享和支持度阈值minsup,频繁子图挖掘的目标是找出使得技术分享的子图g[3]

    尽管该定义适用于所有类型的图,但是本文主要关注无向连通图(undirected, connected graph)。这种图的定义如下:

    1. 一个图是连通的,如果图中每对顶点之间都存在一条路径;其中,路径是顶点的序列<v1v2v3…vk>,使得序列中的每对相邻的顶点(vi,vi+1)之间都有一条边。

    1. 如果一个图是无向的,如果它只包含无向边。一条边(vi, vj) 是无向的,如果它与(vj,vi)没有任何区别。

    频繁子图挖掘是一项计算量很大的任务,因为搜索空间是指数级的。为了解释这项任务的复杂性,考虑包含d个数据实体的数据集。在频繁子图挖掘中,每个实体是一个项,待考察的搜索空间大小是2d,这是可能产生的候选项集的个数。在频繁子图挖掘中,每个实体是一个顶点,并且最多可以有d-1条到其它顶点的边。假定顶点的标号是唯一的,则子图的总数是

        技术分享

    其中,技术分享 是选择i个顶点形成子图的方法数,而技术分享 i个顶点的图的总数。表 22对不同的d比较了项集和子图的个数。

     

    22 对于不同的维度d,项集和子图的个数比较

    实体个数d

    1

    2

    3

    4

    5

    6

    7

    8

    项集个数

    2

    4

    8

    16

    32

    64

    128

    256

    子图个数

    2

    5

    18

    113

    1450

    40069

    2350602

    286192513

     

    挖掘频繁子图的一种蛮力方法是,产生所有的连通子图作为候选,并计算它们各自的支持度。候选子图的个数比传统的关联规则挖掘中的候选子图的个数大得多,其原因如下。

    1. 项在某个项集中至少出现一次,而某个顶点标号可能在一个图中出现多次。
    2. 相同的顶点标号对可以有多种边标号选择。

    给定大量候选子图,即使对于适度规模的图,蛮力方法也可能垮掉。

  10. 频繁子图挖掘过程

    因为有更高效的gSpan算法作为本文的核心算法,所以这里仅对类Apriori算法的基本框架做出一个简要的介绍。

    挖掘频繁子图的类Apriori算法由以下步骤组成。

    1. 候选生成:合并频繁(k-1)-子图对,得到候选k-子图。
    2. 候选剪枝:丢弃包含非频繁的(k-1)-子图的所有候选k-子图。
    3. 支持度计数:统计技术分享中包含每个候选的图的个数。
    4. 候选删除:丢弃支持度小于minsup的所有候选子图。
  11. 候选集生成

    首要的问题是如何定义子图的大小k。通过添加一个顶点,迭代地扩展子图的方法称为顶点增长(vertex growing )K也可以是图中边的个数。添加一条边到已有的子图中来扩展子图的方法叫做边增长(edge growing)。其中在类Apriori的频繁子图挖掘算法中,AGM算法采用顶点增长的策略,FSG算法采用边增长的策略。gSpan算法则采用边增长的策略。

  12. 候选集剪枝

    产生候选k-子图后,需要减去(k-1)-子图非频繁的候选。候选剪枝可以通过如下步骤实现:相继从k-子图删除一条边,并检查对应的(k-1)-子图是否连通且频繁。如果不是,则该候选k-子图可以丢弃。这种策略与频繁项集挖掘的Apriori算法是类似的。

    为了检查(k-1)-子图是否频繁,需要将它与其它频繁(k-1)-子图匹配。判定两个图是否拓扑等价(或同构)称为图同构问题。

  13. 支持度计数

    支持度计数也是开销很大的操作,因为对于每个技术分享 ,必须确定包含在G中的所有候选子图。在后面详细介绍gSpan算法的时候,我会有详细的介绍。

    在进行支持度计数的时候需要进行图的同构测试。处理图同构的标准方法是,将每一个图都映射到一个唯一的串表达式,称为规范标号(canonical label )。规范标号具有如下性质:如果两个图是同构的,则它们的代码一定相同。这个性质使得我们可以通过比较图的规范标号来检查图同构。

    在基于Apriori思想的算法中,通过图的邻接矩阵定义了一种规范标号。通过将图的邻接矩阵按行展开,逐行拼接,可以获得邻接矩阵的串表示。同一个图会有不同的邻接矩阵表示,所以也会有不同的串表示。我们将字典序最小的串表示作为图的规范标号。这里只是简单的陈述,因为在gSpan算法中,作者设计了一种独特的规范标号系统,我会在后面详细介绍gSpan算法的时候详细介绍。

     

  14. 本章小结

     

    本章主要介绍频繁子图挖掘的概念和基础知识。首先,简要介绍了图论的相关知识,包括图的定义和组成,子图的定义,图同构和子图同构的定义。其中图同构和子图同构问题是频繁子图挖掘领域研究的重点,因为图同构测试在很大程度上影响了频繁子图挖掘算法的性能。然后,重点介绍了频繁子图挖掘的基本定义和基础知识。介绍了解决频繁子图挖掘的一般步骤(候选产生,候选剪枝,支持度计数,候选删除)和对应的基本方法。

    本章介绍了频繁子图挖掘的基础知识,为了后面的章节详细介绍频繁子图挖掘算法做好了准备工作。

  15. 静态频繁连通子图挖掘算法

    在每一层频繁子图的挖掘过程中,Apriori算法都会产生大量的非频繁的候选子图。然后对候选的频繁子图执行支持度计数。对于所有频繁的候选子图,还需要进行图的同构测试,以减除重复的频繁候选子图。因为图的同构测试是一种NP完全问题,所以对于大规模的频繁子图进行图的同构测试是一个开销很大的过程,甚至是不可能完成的任务。因此,大量生成的候选子图和图的同构测试的巨大开销是Apriori类方法的性能瓶颈。下面,将介绍一种不同于Apriori类方法的算法:基于模式增长的方法。不同于Apriori类的方法通过每次合并频繁k子图来生成候选k+1子图,基于模式增长的方法,每次扩展一条边来生成规模更大的候选。

  16. 模式增长方法:一个朴素的算法框架

    算法1 NaiveGraph(g, D, min_sup, S)

    Input: A graph g, a graph dataset D, and min_sup.

    Output: The frequent graph set S.

    1: if g exists in S then return;

    2: else insert g to S;

    3: scan D once, find every edge e such that g can be extended to g技术分享e and it is frequent;

    4: for each frequent g技术分享e do

    5:     Call NaiveGraph(g技术分享e, D, min_sup, S);

    6: return;

     

    算法1描述了一个朴素的频繁子图挖掘算法[6]。这个算法挖掘所有的频繁子图。在下一节,我们试图对这个朴素的算法框架进行改造,创造性地提出高效率的gSpan算法。这个算法框架大概基于这样的过程:对于每一个已经发现的频繁子图g,迭代地执行边扩展的策略(每次增长一条边),直到所有能包含图g的频繁子图被完全发现为止。

    这个朴素的算法框架使用两种必要的和显而易见的策略对频繁子图挖掘算法的搜索空间进行剪枝。在第四行展示了一种剪枝策略:当一个被频繁子图扩展出来的子图的支持度小于最小支持度阈值的时候,我们就没有扩展这个子图的必要了(根据子图支持度的非单调性)。第一行展示出第二种剪枝策略,当一个被扩展出来的频繁子图已经出现在挖掘结果的集合里面了,我们也没有必要对此进行扩展了(因为对此图的扩展已经完成了,没有必要进行重复地扩展)。

    NaiveGraph虽然很简单,而且使用了两种高效的剪枝策略,但搜索频繁子图的代价仍然很高。它的瓶颈是扩展子图规模的时候的低效率,因为同样的图可能重复发现很多次[5]。我们只要观察一下一个频繁n边图是如何产生的,就可以明白这种重复是多么的严重。假设此n边图随意去除一条边可以生成连通的n-1边图(当然去除一条边可能使得n-1边图不连通,但是为了问题的简便,我们可以忽略掉),那么这个n边图可以生成nn-1边图(忽略掉图的对称性以及相同边的影响)。根据支持度计数的反单调性,这nn-1边图都是频繁的。反过来说,这nn-1边图都可以通过一条边的扩展生成此频繁n边图。同样的图的反复出现必然带来计算资源的浪费。我们称二度发现的图为复制图(duplicatie graph)[5]

    我们仔细看一下这种重复图是如何带来计算资源的浪费的。首先,重复图的产生会消耗计算资源,其次重复的支持度计数会带来资源的浪费。然后,对重复图递归调用NaiveGraph函数,在挖掘的结果集合中查找此图是否为重复图。在结果集合中查找频繁子图不是一个简单的过程,需要进行图的同构测试。然而图的同构测试属于一个NP完全问题,会消耗非常大的计算资源。所以我们可以看出这种朴素算法结构的局限性所在。

    为了优化这种朴素的算法框架,我们可以从两方面着手:首先,可以使用比较好的扩展策略,以此减少重复图的产生;其次,可以改进图的同构测试方法,以此降低图的查找和图的同构测试所产生的代价。正是这两个改进的方向,启发了gSpan算法的出现,极大地提高了NaiveGraph算法的性能。

  17. gSpan算法思想

    gSpan算法通过解决3.1节提出的问题来极大地提高了NaiveGraph算法的效率[5]gSpan算法通过执行最右扩展的策略减少了重复的产生,同时也保证了搜索结果的完备性。gSpan算法设计出一种新式的图的规范标号,将图的同构测试与重复图的检测结合到一块,避免了在已经获得的频繁子图集合中搜索重复图。这些改进极大地提高了频繁子图挖掘算法的效率。

    为此,gSpan算法引入了两个相关重要的概念:DFS字典序和最小DFS编码。以这两个创新的概念为基础,创造性的设计出一种高效的图的规范标号系统。

  18. 图的规范化表示和规范化扩展思想概述

    让我们回顾一下NaiveGraph算法所面对的两个重要缺陷:首先,模式增长的过程中产生了大量的重复图;其次,对于重复图的检索和同构测试耗费大量的计算机资源。为什么频繁项集挖掘的模式增长算法不是面临这样的问题呢?我想,问题的根源在于图的表示的