基于确定图频繁子图挖掘技术概述

《基于确定图频繁子图挖掘技术概述》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于确定图频繁子图挖掘技术概述摘要：化学信息学、生物信息学、医学和社会科学等领域的科学研究的迅速发展积累了大量的图数据，如何从复杂和庞大的图数据中挖掘出有效信息成为数据挖掘领域的热点。通过介绍现阶段图数据挖掘技术的进展，特别是确定图挖掘技术中有代表性的频繁子图挖掘技术研究，讨论并预测了频繁子图挖掘研究的发展趋势。关键词：确定图；频繁子图挖掘；子图同构中图分类号：TP311.13文献标识码：A文章编号：1007-9599(2012)17-0000-021引言广泛应用于描述化学信息学、生物信息学、医学和社会科学等领域的图数据挖掘技术是目前数据库研究领域的重要研究方向。在生物技

2、术领域，图数据挖掘技术可以帮助生物学家减轻蛋白质结构匹配实验的代价；在小世界(社会)网络分析中，对小部分节点的高度局部聚类的挖掘，有助于理解如何能接触到其他人、设计网络，有利于信息或其他资源的有效传输，从而不用太多的冗余连接使网络过载［1］。在进行确定图数据挖掘技术的讨论之前，先给出确定图数据的基本定义。确定图是一个五元组，=(,,,,)o其中是图的顶点集合；是图边的集合；是图的顶点标号集合；是图的边标号集合；是用来对顶点和边分配标号的函数。本文将对国内外基于确定图的频繁子图挖掘技术研究进行介绍和总结，并对未来的发展趋势和研究热点进行展望。2确定图的数据挖掘技术一段时间以

3、来，确定图的频繁子图挖掘问题得到了一定的研究，确定图的频繁子图挖掘是指在确定图集合中挖掘出公共子结构。常见的频繁子图挖掘算法可以分为4类：基于模式增长的算法、基于的算法、基于模式规约的算法以及基于最小描述长度的近似算法。2.1基于的频繁子结构挖掘算法基于的频繁子结构挖掘算法，包括算法和算法等。AkihiroInokuchi>TakashiWashio和HiroshiMotoda提出的算法以递归统计的方法为基础，图的顶点相当于传统频繁项集挖掘算法中的项集，通过每次增加一个图节点来实现子结构规模的增大，该算法可以挖掘出所有频繁子图，对集成的密集数据集具有良好性能。Michih

4、iroKuramochi和GeorgeKarypis提出的算法对进行了改进，图的边相当于传统频繁项集挖掘算法中的项集，也就是说，和传统频繁项集挖掘算法通过每次增加一个单一项来增加频繁项集的大小一样，算法也是通过每次增加一条边来增加频繁子图的大小。首先算法枚举所有的单边图和双边图。然后，基于得到的单边图和双边图集合，开始循环计算。在每个循环期间，算法首先产生比前一个频繁子图多一条边的候选子图，接着计算这些候选子图的频繁度，对支持度约束不满意的子图进行剪枝，并在计算候选子图的支持度时采取了一定的优化措施，与相比，的执行效率有一定提高。2.2基于模式增长的频繁子结构挖掘算法基于

5、模式增长的频繁子结构挖掘算法包括(Graph-BasedSubstruturePattern)算法、(Fast算法等，这些算法得FrequentSubgraphMining)算法、到频繁子图的方法都是扩展频繁边的方式。图结构因为其本身特性以及图的同构性问题，对图的频繁子图挖掘问题的难点就在于怎样将无序的图结构转换成有序列表，因此YanXifeng和HanJiawei提出的算法首次将深度优先遍历算法思想及最右路径扩展技术应用于频繁子图挖掘算法。算法的思想是首先将确定图的边转换成DFS(depth-firstsearch)代码，用(，，，)这个五元组表示确定图的边，和表示一条

6、边的两个顶点，和表示顶点和顶点的标签，表示连接和的边。因此，图中的边=(,,,,)、边二(，，，，)。同时，定义当二，〈或者〈，=这两个条件任意满足一条时，就认为是的前驱边，或者是的后继边，通过这种方式可以将无序的边集形成一个有序的线性序列。然后计算图的最小DFS代码。该算法选择图中任意一个顶点开始遍历，将起始顶点设置为树的根节点，最后访问的顶点是最右顶点，知道建立一个完全的depth-firstsearchtreeoJunhuan、Weiwang和Janprins一同提出的算法在一个代数图框架内采用垂直搜索方案来减少频繁子图挖掘中出现的候选过多的问题。该算法用邻接矩阵表

7、示图结构,将矩阵的下三角元素（包括对角线元素）序列定位为矩阵代码code（M）,邻接矩阵的所有矩阵代码中的最大代码被定义为标准邻接矩阵（CAM）与［2,3］使用最小代码不同是的，使用最大代码来表示矩阵的标准形式，然后将图的所有连通子图的标准邻接矩阵按以下方式组织为CAM树：（1）树的根是一个空矩阵；（2）树的每个节点是图的不同连通子图；（3）对于每个非根节点，它的双亲M的子矩阵。枚举所有子图的方法主要有两种方式，第一种是和所使用的连接操作第二种是算法中使用的扩展操作。连接操作主要关注的问题是单个操作可能产生多个候选集以及多个连