本站原创
摘要：化学信息学、生物信息学、医学和社会科学等领域的科学研究的迅速发展积累了大量的图数据，如何从复杂和庞大的图数据中挖掘出有效信息成为数据挖掘领域的热点。通过介绍现阶段图数据挖掘技术的进展，特别是确定图挖掘技术中有代表性的频繁子图挖掘技术研究，讨论并预测了频繁子图挖掘研究的发展趋势。
关键词：确定图；频繁子图挖掘；子图同构
1007-9599 （2012） 17-0000-02
1引言
广泛应用于描述化学信息学、生物信息学、医学和社会科学等领域的图数据挖掘技术是目前数据库研究领域的重要研究方向。在生物技术领域，图数据挖掘技术可以帮助生物学家减轻蛋白质结构匹配实验的代价；在小世界（社会）网络分析中，对小部分节点的高度局部聚类的挖掘，有助于理解如何能接触到其他人、设计网络，有利于信息或其他资源的有效传输，从而不用太多的冗余连接使网络过载。在进行确定图数据挖掘技术的讨论之前，先给出确定图数据的基本定义。确定图 是一个五元组， =（ ， ， ， ， ）。其中 是图 的顶点集合； 是图 边的集合； 是图 的顶点标号集合； 是图 的边标号集合； 是用来对顶点和边分配标号的函数。本文将对国内外基于确定图的频繁子图挖掘技术研究进行介绍和总结，并对未来的发展趋势和研究热点进行展望。
2确定图的数据挖掘技术
一段时间以来，确定图的频繁子图挖掘问题得到了一定的研究，确定图的频繁子图挖掘是指在确定图集合中挖掘出公共子结构。常见的频繁子图挖掘算法可以分为4类：基于模式增长的算法、基于 的算法、基于模式规约的算法以及基于最小描述长度的近似算法。
Michihiro Kuramochi和George Karypis提出的 算法对 进行了改进，图的边相当于传统频繁项集挖掘算法中的项集，也就是说，和传统频繁项集挖掘算法通过每次增加一个单一项来增加频繁项集的大小一样， 算法也是通过每次增加一条边来增加频繁子图的大小。首先算法枚举所有的单边图和双边图。然后，基于得到的单边图和双边图集合， 开始循环计算。在每个循环期间，算法首先产生比前一个频繁子图多一条边的候选子图，接着计算这些候选子图的频繁度，对支持度约束不满意的子图进行剪枝，并在计算候选子图的支持度时采取了一定的优化措施，与 相比， 的执行效率有一定提高。
Jun huan、Wei wang和Jan prins一同提出的 算法在一个代数图框架内采用垂直搜索方案来减少频繁子图挖掘中出现的候选过多的问题。该算法用邻接矩阵 表示图结构，将矩阵的下三角元素（包括对角线元素）序列定位为矩阵代码code（M），邻接矩阵的所有矩阵代码中的最大代码被定义为标准邻接矩阵（CAM）与[2，3]使用最小代码不同是的， 使用最大代码来表示矩阵的标准形式，然后将图 的所有连通子图的标准邻接矩阵按以下方式组织为CAM树：（1）树的根是一个空矩阵；（2）树的每个节点是图 的不同连通子图；（3）对于每个非根节点，它的双亲M的子矩阵。枚举所有子图的方法主要有两种方式，第一种是 和 所使用的连接操作第二种是 算法中使用的扩展操作。连接操作主要关注的问题是单个操作可能产生多个候选集以及多个连接操作提出一个候选集，而扩展操作主要关注的是限制那些新引进的边可能附着的节点，因此算法最后使用CAM树的次优标准矩阵以及两种新的操作 和 FF-extension来枚举所有的频繁子图。这种方案能够很好的处理子图同构问题，并且算法效率比 更好。
Yan Xifeng和Han Jiawei提出的 算法利用（同等出现）
和 Termination（提前终止）方法极大减少了生成的冗余子图，因而提高了算法效率。给定图 和图 ，图 是由图 增加一个新边扩展形成的新图，如果图 在图数据集 中每个图的子图同构数量等于图 的扩展子图同构数量，则称图 和图 是同等出现，这表示在数据集 中图 出现时 必定出现。而提前终止表示如果 并且 （ 是 的扩 展）满足时能推导出 不是闭的，那么仅需要 来代替 的情况。 算法执行时首先生成一个频繁图；然后判断该图 与它的真超图 的支持度是否相等，如果相等则表示 是闭的，否则不是闭的；最后根据提前终止以及其他可能导致提前终止失败的条件来决定此生成图是否可以被扩展。
关键词：确定图；频繁子图挖掘；子图同构
1007-9599 （2012） 17-0000-02
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）代码，用（ ， ， ，）这个五元组表示确定图的边， 和 表示一条边的两个顶点， 和 表示顶点 和顶点 的标签， 表示连接 和 的边。因此，图中的边 =（ ， ， ， ， ）、边 =（ ， ， ， ， ）。同时， 定义当 = ， < 或者摘自：本科毕业论文www.udooo.com
< ， = 这两个条件任意满足一条时，就认为 是 的前驱边，或者 是 的后继边，通过这种方式可以将无序的边集形成一个有序的线性序列。然后计算图的最小DFS代码。该算法选择图中任意一个顶点开始遍历，将起始顶点设置为树的根节点，最后访问的顶点是最右顶点，知道建立一个完全的depth-first search tree。Jun huan、Wei wang和Jan prins一同提出的 算法在一个代数图框架内采用垂直搜索方案来减少频繁子图挖掘中出现的候选过多的问题。该算法用邻接矩阵 表示图结构，将矩阵的下三角元素（包括对角线元素）序列定位为矩阵代码code（M），邻接矩阵的所有矩阵代码中的最大代码被定义为标准邻接矩阵（CAM）与[2，3]使用最小代码不同是的， 使用最大代码来表示矩阵的标准形式，然后将图 的所有连通子图的标准邻接矩阵按以下方式组织为CAM树：（1）树的根是一个空矩阵；（2）树的每个节点是图 的不同连通子图；（3）对于每个非根节点，它的双亲M的子矩阵。枚举所有子图的方法主要有两种方式，第一种是 和 所使用的连接操作第二种是 算法中使用的扩展操作。连接操作主要关注的问题是单个操作可能产生多个候选集以及多个连接操作提出一个候选集，而扩展操作主要关注的是限制那些新引进的边可能附着的节点，因此算法最后使用CAM树的次优标准矩阵以及两种新的操作 和 FF-extension来枚举所有的频繁子图。这种方案能够很好的处理子图同构问题，并且算法效率比 更好。
Yan Xifeng和Han Jiawei提出的 算法利用（同等出现）
和 Termination（提前终止）方法极大减少了生成的冗余子图，因而提高了算法效率。给定图 和图 ，图 是由图 增加一个新边扩展形成的新图，如果图 在图数据集 中每个图的子图同构数量等于图 的扩展子图同构数量，则称图 和图 是同等出现，这表示在数据集 中图 出现时 必定出现。而提前终止表示如果 并且 （ 是 的扩 展）满足时能推导出 不是闭的，那么仅需要 来代替 的情况。 算法执行时首先生成一个频繁图；然后判断该图 与它的真超图 的支持度是否相等，如果相等则表示 是闭的，否则不是闭的；最后根据提前终止以及其他可能导致提前终止失败的条件来决定此生成图是否可以被扩展。
摘自：本科生毕业论文www.udooo.com