论文部分内容阅读
摘要：化学信息学、生物信息学、医学和社会科学等领域的科学研究的迅速发展积累了大量的图数据，如何从复杂和庞大的图数据中挖掘出有效信息成为数据挖掘领域的热点。通过介绍现阶段图数据挖掘技术的进展，特别是确定图挖掘技术中有代表性的频繁子图挖掘技术研究，讨论并预测了频繁子图挖掘研究的发展趋势。
关键词：确定图；频繁子图挖掘；子图同构
中图分类号：TP311.13 文献标识码：A 文章编号：1007-9599 （2012） 17-0000-02
1 引言
广泛应用于描述化学信息学、生物信息学、医学和社会科学等领域的图数据挖掘技术是目前数据库研究领域的重要研究方向。在生物技术领域，图数据挖掘技术可以帮助生物学家减轻蛋白质结构匹配实验的代价；在小世界（社会）网络分析中，对小部分节点的高度局部聚类的挖掘，有助于理解如何能接触到其他人、设计网络，有利于信息或其他资源的有效传输，从而不用太多的冗余连接使网络过载[1]。在进行确定图数据挖掘技术的讨论之前，先给出确定图数据的基本定义。确定图 是一个五元组， =（ ， ， ， ， ）。其中 是图 的顶点集合； 是图 边的集合； 是图 的顶点标号集合； 是图 的边标号集合； 是用来对顶点和边分配标号的函数。本文将对国内外基于确定图的频繁子图挖掘技术研究进行介绍和总结，并对未来的发展趋势和研究热点进行展望。
2 确定图的数据挖掘技术
一段时间以来，确定图的频繁子图挖掘问题得到了一定的研究，确定图的频繁子图挖掘是指在确定图集合中挖掘出公共子结构。常见的频繁子图挖掘算法可以分为4类：基于模式增长的算法、基于 的算法、基于模式规约的算法以及基于最小描述长度的近似算法。
2.1 基于 的频繁子结构挖掘算法
基于 的频繁子结构挖掘算法，包括 算法和 算法等。Akihiro Inokuchi、Takashi Washio和Hiroshi Motoda提出的 算法以递归统计的方法为基础，图的顶点相当于传统频繁项集挖掘算法中的项集，通过每次增加一个图节点来实现子结构规模的增大，该算法可以挖掘出所有频繁子图，对集成的密集数据集具有良好性能。
Michihiro Kuramochi和George Karypis提出的 算法对 进行了改进，图的边相当于传统频繁项集挖掘算法中的项集，也就是说，和传统频繁项集挖掘算法通过每次增加一个单一项来增加频繁项集的大小一样， 算法也是通过每次增加一条边来增加频繁子图的大小。首先算法枚举所有的单边图和双边图。然后，基于得到的单边图和双边图集合， 开始循环计算。在每个循环期间，算法首先产生比前一个频繁子图多一条边的候选子图，接着计算这些候选子图的频繁度，对支持度约束不满意的子图进行剪枝，并在计算候选子图的支持度时采取了一定的优化措施，与 相比， 的执行效率有一定提高。
2.2 基于模式增长的频繁子结构挖掘算法
基于模式增长的频繁子结构挖掘算法包括 （Graph-Based Substruture Pattern）算法、 （Fast Frequent Subgraph Mining）算法、 算法等，这些算法得到频繁子图的方法都是扩展频繁边的方式。图结构因为其本身特性以及图的同构性问题，对图的频繁子图挖掘问题的难点就在于怎样将无序的图结构转换成有序列表，因此Yan Xifeng和Han Jiawei提出的 算法首次将深度优先遍历算法思想及最右路径扩展技术应用于频繁子图挖掘算法。 算法的思想是首先将确定图的边转换成DFS（depth-first search）代码，用（ ， ， ， ）这个五元组表示确定图的边， 和 表示一条边的两个顶点， 和 表示顶点 和顶点 的标签， 表示连接 和 的边。因此，图中的边 =（ ， ， ， ， ）、边 =（ ， ， ， ， ）。同时， 定义当 = ， < 或者 < ， = 这两个条件任意满足一条时，就认为 是 的前驱边，或者 是 的后继边，通过这种方式可以将无序的边集形成一个有序的线性序列。然后计算图的最小DFS代码。该算法选择图中任意一个顶点开始遍历，将起始顶点设置为树的根节点，最后访问的顶点是最右顶点，知道建立一个完全的depth-first search tree。
Jun huan、Wei wang和Jan prins一同提出的 算法在一个代数图框架内采用垂直搜索方案来减少频繁子图挖掘中出现的候选过多的问题。该算法用邻接矩阵 表示图结构，将矩阵的下三角元素（包括对角线元素）序列定位为矩阵代码code（M），邻接矩阵的所有矩阵代码中的最大代码被定义为标准邻接矩阵（CAM）与[2，3]使用最小代码不同是的， 使用最大代碼来表示矩阵的标准形式，然后将图 的所有连通子图的标准邻接矩阵按以下方式组织为CAM树：（1）树的根是一个空矩阵；（2）树的每个节点是图 的不同连通子图；（3）对于每个非根节点，它的双亲M的子矩阵。枚举所有子图的方法主要有两种方式，第一种是 和 所使用的连接操作第二种是 算法中使用的扩展操作。连接操作主要关注的问题是单个操作可能产生多个候选集以及多个连接操作提出一个候选集，而扩展操作主要关注的是限制那些新引进的边可能附着的节点，因此算法最后使用CAM树的次优标准矩阵以及两种新的操作 和 FFSM-extension来枚举所有的频繁子图。这种方案能够很好的处理子图同构问题，并且算法效率比 更好。
Yan Xifeng和Han Jiawei提出的 算法利用（同等出现）
和 Termination（提前终止）方法极大减少了生成的冗余子图，因而提高了算法效率。给定图 和图 ，图 是由图 增加一个新边扩展形成的新图，如果图 在图数据集 中每个图的子图同构数量等于图 的扩展子图同构数量，则称图 和图 是同等出现，这表示在数据集 中图 出现时 必定出现。而提前终止表示如果 并且 （ 是 的扩 展）满足时能推导出 不是闭的，那么仅需要 来代替 的情况。 算法执行时首先生成一个频繁图；然后判断该图 与它的真超图 的支持度是否相等，如果相等则表示 是闭的，否则不是闭的；最后根据提前终止以及其他可能导致提前终止失败的条件来决定此生成图是否可以被扩展。 2.3 基于最小描述长度的近似算法
Nikhil S.Ketkar、Lawrence B.Holder和Diane J.Cook共同提出了基于图的数据挖掘系统 。该系统通过查找子图的方法在图数据集中挖掘感兴趣的子结构，它使用最小描述长度原理（MDL）而不是频繁度来评估子结构。 是一个基于图的关系学习系统， 系统的输入数据可以是一个单一图或者是图集合（这些图可以是标记图也可以是非标记图），而根据最小描述长度原理输出的是最好的压缩输入数据集的子结构。 基于计算约束的定向搜索，它由所有具有唯一标记的顶点组成的子结构开始，通过每次（一个顶点+一条边）或者每次（一条边）方式扩展子结构，扩展得到所有可能的子结构，然后在例图的指导下生成候选子结构。
2.4 基于模式增长及规约的算法
Yan Xifeng、Zhou X Jasmine和Han Jiawei提出的 算法是基于模式规约的算法。 从小的频繁候选图开始，通过增加新边来尽可能地扩展，直到找到具有相同支持度的闭超图，在闭超图中把先前候选图的顶点压缩成为一个顶点；然后分解这个高连通性的闭超图，判断每个顶点的度是否满足连通性约束条件，提取满足连通性约束的子图，删除所有的与不满足连通性约束的顶点连接的边；然后，通过增加新边来扩展候选图，并且重复进行上述操作直到没有候选图是频繁的。
3 结语
图挖掘技术已经在化学信息学、生物信息学、社会学等领域广泛应用。利用图数据挖掘技术在大型数据库中挖掘出人们感兴趣的知识是图挖掘技术发展的驱动力。确定图的挖掘技术特别是频繁模式挖掘已经有了一定的进展，但是不确定图的研究还处于初级阶段，对于不确定图的研究将成为下一阶段的热点问题。
本文系德宏师范高等专科学校科研立项课题《基于数据流形式的不确定图挖掘研究》（DSK201206）的阶段性研究成果。
参考文献：
[1]丁悦，张阳等.图数据挖掘技术的研究与进展.计算机应用[J].2012，32（1）：182-190.
[2]Inokuchi A，Washio T，Motoda H. An apriori-based algorithm for mining frequent sub structures from graph data[C]//proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery（PKDD’00）.Freiburg，Germany，2000：13-23.
[3]Kuramochi M，Karypis G. Frequent subgraph discovery[C]//Proceedings of the 2001 IEEE International Conference on Data Mining （ ICDM 2001 ） . San Jose， California， USA，2001： 313-320.
[4]Yan Xifeng，Han Jiawei.gSpan：Graph-based substructure pattern mining[C]//Proceeding of the 2002 IEEE International Conference on Data Mining.Washington，DC：IEEE Computer society， 2002：721-724.
[5] Huan Jun，Wang Wei， Prins J.Efficient mining of frequent subgraphs in the presence of isomo- rphism[C] // Proceedings of the 2002 IEEE International Conference on Data Mining.Washington，DC： IEEE Computer Society，2002：549-552.
[6] Yan Xifeng，Han Jia Wei.Closegraph：Mining closed frequent graph patterns[C]// Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York： ACM Press，2003：286-295.
[7] KetKar S，Holder B，Cook J.Subdue：Compression-Based Frequent Pattern Discovery in Graph Data.In ACM，2005：71-76
[作者简介]
黄鑫（1981.8-），男，汉族，湖北武汉人，德宏师范高等专科学校，系统分析与集成硕士，讲师，从事网络安全、计算机体系结构、算法设计与分析研究。
关键词：确定图；频繁子图挖掘；子图同构
中图分类号：TP311.13 文献标识码：A 文章编号：1007-9599 （2012） 17-0000-02
1 引言
广泛应用于描述化学信息学、生物信息学、医学和社会科学等领域的图数据挖掘技术是目前数据库研究领域的重要研究方向。在生物技术领域，图数据挖掘技术可以帮助生物学家减轻蛋白质结构匹配实验的代价；在小世界（社会）网络分析中，对小部分节点的高度局部聚类的挖掘，有助于理解如何能接触到其他人、设计网络，有利于信息或其他资源的有效传输，从而不用太多的冗余连接使网络过载[1]。在进行确定图数据挖掘技术的讨论之前，先给出确定图数据的基本定义。确定图 是一个五元组， =（ ， ， ， ， ）。其中 是图 的顶点集合； 是图 边的集合； 是图 的顶点标号集合； 是图 的边标号集合； 是用来对顶点和边分配标号的函数。本文将对国内外基于确定图的频繁子图挖掘技术研究进行介绍和总结，并对未来的发展趋势和研究热点进行展望。
2 确定图的数据挖掘技术
一段时间以来，确定图的频繁子图挖掘问题得到了一定的研究，确定图的频繁子图挖掘是指在确定图集合中挖掘出公共子结构。常见的频繁子图挖掘算法可以分为4类：基于模式增长的算法、基于 的算法、基于模式规约的算法以及基于最小描述长度的近似算法。
2.1 基于 的频繁子结构挖掘算法
基于 的频繁子结构挖掘算法，包括 算法和 算法等。Akihiro Inokuchi、Takashi Washio和Hiroshi Motoda提出的 算法以递归统计的方法为基础，图的顶点相当于传统频繁项集挖掘算法中的项集，通过每次增加一个图节点来实现子结构规模的增大，该算法可以挖掘出所有频繁子图，对集成的密集数据集具有良好性能。
Michihiro Kuramochi和George Karypis提出的 算法对 进行了改进，图的边相当于传统频繁项集挖掘算法中的项集，也就是说，和传统频繁项集挖掘算法通过每次增加一个单一项来增加频繁项集的大小一样， 算法也是通过每次增加一条边来增加频繁子图的大小。首先算法枚举所有的单边图和双边图。然后，基于得到的单边图和双边图集合， 开始循环计算。在每个循环期间，算法首先产生比前一个频繁子图多一条边的候选子图，接着计算这些候选子图的频繁度，对支持度约束不满意的子图进行剪枝，并在计算候选子图的支持度时采取了一定的优化措施，与 相比， 的执行效率有一定提高。
2.2 基于模式增长的频繁子结构挖掘算法
基于模式增长的频繁子结构挖掘算法包括 （Graph-Based Substruture Pattern）算法、 （Fast Frequent Subgraph Mining）算法、 算法等，这些算法得到频繁子图的方法都是扩展频繁边的方式。图结构因为其本身特性以及图的同构性问题，对图的频繁子图挖掘问题的难点就在于怎样将无序的图结构转换成有序列表，因此Yan Xifeng和Han Jiawei提出的 算法首次将深度优先遍历算法思想及最右路径扩展技术应用于频繁子图挖掘算法。 算法的思想是首先将确定图的边转换成DFS（depth-first search）代码，用（ ， ， ， ）这个五元组表示确定图的边， 和 表示一条边的两个顶点， 和 表示顶点 和顶点 的标签， 表示连接 和 的边。因此，图中的边 =（ ， ， ， ， ）、边 =（ ， ， ， ， ）。同时， 定义当 = ， < 或者 < ， = 这两个条件任意满足一条时，就认为 是 的前驱边，或者 是 的后继边，通过这种方式可以将无序的边集形成一个有序的线性序列。然后计算图的最小DFS代码。该算法选择图中任意一个顶点开始遍历，将起始顶点设置为树的根节点，最后访问的顶点是最右顶点，知道建立一个完全的depth-first search tree。
Jun huan、Wei wang和Jan prins一同提出的 算法在一个代数图框架内采用垂直搜索方案来减少频繁子图挖掘中出现的候选过多的问题。该算法用邻接矩阵 表示图结构，将矩阵的下三角元素（包括对角线元素）序列定位为矩阵代码code（M），邻接矩阵的所有矩阵代码中的最大代码被定义为标准邻接矩阵（CAM）与[2，3]使用最小代码不同是的， 使用最大代碼来表示矩阵的标准形式，然后将图 的所有连通子图的标准邻接矩阵按以下方式组织为CAM树：（1）树的根是一个空矩阵；（2）树的每个节点是图 的不同连通子图；（3）对于每个非根节点，它的双亲M的子矩阵。枚举所有子图的方法主要有两种方式，第一种是 和 所使用的连接操作第二种是 算法中使用的扩展操作。连接操作主要关注的问题是单个操作可能产生多个候选集以及多个连接操作提出一个候选集，而扩展操作主要关注的是限制那些新引进的边可能附着的节点，因此算法最后使用CAM树的次优标准矩阵以及两种新的操作 和 FFSM-extension来枚举所有的频繁子图。这种方案能够很好的处理子图同构问题，并且算法效率比 更好。
Yan Xifeng和Han Jiawei提出的 算法利用（同等出现）
和 Termination（提前终止）方法极大减少了生成的冗余子图，因而提高了算法效率。给定图 和图 ，图 是由图 增加一个新边扩展形成的新图，如果图 在图数据集 中每个图的子图同构数量等于图 的扩展子图同构数量，则称图 和图 是同等出现，这表示在数据集 中图 出现时 必定出现。而提前终止表示如果 并且 （ 是 的扩 展）满足时能推导出 不是闭的，那么仅需要 来代替 的情况。 算法执行时首先生成一个频繁图；然后判断该图 与它的真超图 的支持度是否相等，如果相等则表示 是闭的，否则不是闭的；最后根据提前终止以及其他可能导致提前终止失败的条件来决定此生成图是否可以被扩展。 2.3 基于最小描述长度的近似算法
Nikhil S.Ketkar、Lawrence B.Holder和Diane J.Cook共同提出了基于图的数据挖掘系统 。该系统通过查找子图的方法在图数据集中挖掘感兴趣的子结构，它使用最小描述长度原理（MDL）而不是频繁度来评估子结构。 是一个基于图的关系学习系统， 系统的输入数据可以是一个单一图或者是图集合（这些图可以是标记图也可以是非标记图），而根据最小描述长度原理输出的是最好的压缩输入数据集的子结构。 基于计算约束的定向搜索，它由所有具有唯一标记的顶点组成的子结构开始，通过每次（一个顶点+一条边）或者每次（一条边）方式扩展子结构，扩展得到所有可能的子结构，然后在例图的指导下生成候选子结构。
2.4 基于模式增长及规约的算法
Yan Xifeng、Zhou X Jasmine和Han Jiawei提出的 算法是基于模式规约的算法。 从小的频繁候选图开始，通过增加新边来尽可能地扩展，直到找到具有相同支持度的闭超图，在闭超图中把先前候选图的顶点压缩成为一个顶点；然后分解这个高连通性的闭超图，判断每个顶点的度是否满足连通性约束条件，提取满足连通性约束的子图，删除所有的与不满足连通性约束的顶点连接的边；然后，通过增加新边来扩展候选图，并且重复进行上述操作直到没有候选图是频繁的。
3 结语
图挖掘技术已经在化学信息学、生物信息学、社会学等领域广泛应用。利用图数据挖掘技术在大型数据库中挖掘出人们感兴趣的知识是图挖掘技术发展的驱动力。确定图的挖掘技术特别是频繁模式挖掘已经有了一定的进展，但是不确定图的研究还处于初级阶段，对于不确定图的研究将成为下一阶段的热点问题。
本文系德宏师范高等专科学校科研立项课题《基于数据流形式的不确定图挖掘研究》（DSK201206）的阶段性研究成果。
参考文献：
[1]丁悦，张阳等.图数据挖掘技术的研究与进展.计算机应用[J].2012，32（1）：182-190.
[2]Inokuchi A，Washio T，Motoda H. An apriori-based algorithm for mining frequent sub structures from graph data[C]//proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery（PKDD’00）.Freiburg，Germany，2000：13-23.
[3]Kuramochi M，Karypis G. Frequent subgraph discovery[C]//Proceedings of the 2001 IEEE International Conference on Data Mining （ ICDM 2001 ） . San Jose， California， USA，2001： 313-320.
[4]Yan Xifeng，Han Jiawei.gSpan：Graph-based substructure pattern mining[C]//Proceeding of the 2002 IEEE International Conference on Data Mining.Washington，DC：IEEE Computer society， 2002：721-724.
[5] Huan Jun，Wang Wei， Prins J.Efficient mining of frequent subgraphs in the presence of isomo- rphism[C] // Proceedings of the 2002 IEEE International Conference on Data Mining.Washington，DC： IEEE Computer Society，2002：549-552.
[6] Yan Xifeng，Han Jia Wei.Closegraph：Mining closed frequent graph patterns[C]// Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York： ACM Press，2003：286-295.
[7] KetKar S，Holder B，Cook J.Subdue：Compression-Based Frequent Pattern Discovery in Graph Data.In ACM，2005：71-76
[作者简介]
黄鑫（1981.8-），男，汉族，湖北武汉人，德宏师范高等专科学校，系统分析与集成硕士，讲师，从事网络安全、计算机体系结构、算法设计与分析研究。