数据挖掘小论文.doc

摘要随着计算机与信息技术的发展，数据挖掘技术已经广泛应用到数据仓库、人工智能、模式识别、生物信息等许多领域。在研究逐步深入的过程中，愈来愈多的问题也呈现在我们面前,人们开始意识到用图能更好地描述这些数据结构，进而在此基础上进行挖掘可以得到更多的有用信息。因此，针对图等结构化数据，已经成为数据挖掘研究领域的重要研究方向。本文首先分析图挖掘的背景，图挖掘研究内容粗略地分为:频繁子图挖掘、图的聚类与分类、图查询、带约束的图挖掘等等。其次介绍图挖掘相关的概念。再次，根据gSpan算法，仿真出频繁子图挖掘的效率。最后进行本文的总结。关键词 数据挖掘；频繁子图；图挖掘等。ABSTRACTWith the development of computer science and information technology, data mining technology has been widely applied to data warehousing, artificial intelligence, pattern recognition, bioinformatics and many other fields. During the course of research, more and more questions are presented, and people begin to realize that graphs could describe these data structures more clear, therefore more useful information could be mined. Therefore, research on structured data mainly on graph has become an important field of research.Firstly, this paper analyzes the background of graph mining. Graph miningconsist of frequent subgraph mining and graphclusteringand classification and graph inquiry and constrainedgraph mining. Secondly, Introduceconcepts related tograph mining. Again, according to the algorithm of gSpan, simulatetheefficiency offrequent subgraphmining. Finally, summarize and outlook this paper.KEY WORDS data mining; frequent subgraph; graph mining.数据挖掘之gSpan算法仿真1、图挖掘背景随着数据挖掘1方法的演化，所针对的数据结构方式也在发生着悄然的变化，传统的针对序列、事务、文本等非结构化数据的挖掘方法已经不能满足不断出现的结构化数据挖掘要求。数据挖掘从当初的简单结构或简单关系的数据集，发展到有很多应用背景的树结构模式(XML访问路径、核糖核酸分子结构等)，及更为复杂的对象之间或对象内部关系的图结构模式。图结构是最通用的数据结构类型，它可以描述世界万物之间错综复杂的联系。图挖掘研究内容可以粗略地分为:频繁子图挖掘、图的聚类与分类、图查询、带约束的图4挖掘等等。在这些针对图的挖掘内容中，频繁子图的挖掘一直是研究人员重点关注的一个问题。对于图的频繁子图挖掘就是从单个大图5中或者众多图形中，找出满足最小出现次数的公有子图，它是图的聚类、分类、查询以及带约束的图挖掘等图挖掘问题研究的基础。对于频繁子图挖掘问题，己经陆续提出了许多相应的算法。初期的频繁子图挖掘算法采用模糊计算方法，得到的是近似挖掘结果。在2000年，Inokuchi和Kuramochi先后将Apriori2思想用于频繁子图挖掘算法中，对图的顶点和边进行逐层构造，产生了算法，能够完整地枚举出所有的频繁子图，从而正式开创了用数据挖掘思想来解决图挖掘问题的研究。近年基于FP-growth思想的gSpan3算法，则将频繁子图挖掘算法的效率提高到了一个新的层次。2、概念描述2.1 标记图的同构设有标记图与，若有映射函数：，满足：(1) ，；(2) ，则称与同构，记为。2.2 标记图的子图设有标记图和，若有的某一子图与同构，则称为的子图，记为。如图1中，图1(b)是图1(a)的子图。图12.3 图的支持度和频繁子图设有图库及图，图在图库中的支持度，即中含为子图的标记图的个数。给定一个最小支持度，在图库中，支持度大于的子图称为频繁子图。设为频繁子图，如果不存在频繁子图，使得为的子图，则称子图为最大频繁子图。3、关键算法3.1 gSpan算法gSpan算法第一步，扫描图数据集去掉非频繁的顶点和边(顶点和边的支持度小于最小支持度);第二步，将包含k条边的频繁子图作为种子图，根据最右拓展规则生成包含k+1条边的候选子图，计算支持度，生成包含k+l条边的频繁子图，并将作为新的种子图。第三步，重复第二步，直到没有新的候选子图或频繁子图生成为止。算法gspan的描述如下:3.2 算法仿真DFS(Depth-First Seareh)编码，顾名思义，即深度优先遍历一个连通图时的路径码。对于一条被遍历的边,采用一个五元组表示，其中表示点的标号，表示点的标号，表示边的标号。如图2所示，同样一个连通图(a)，通过不同搜索顺序，可以产生不同的搜索路径(b)、(c)、(d),相应的DFS编码如表1所示。由此可见，一个图深度优先搜索树不唯一，这取决于图顶点的访问次序。所以不能根据DFS序列来判断两个图是否同构。因此，采用DFS字典顺序及最小DFS编码作为其规范表达来解决这个问题。图2表1给定标号图的任意两条边,其线性顺序由下列条件决定:l),当且仅当,;2),当且仅当,使()，且;3),其他情况。在表1中，对于边,图2(b)和图2(d)前4个元素相同，而第5个元素,所以。由此可以推断出图(b)、(e)、(d)的偏序顺序为:。就是图2(a)的最小DFS编码。两个图的最小DFS编码和同构之间有重要联系：给定两个图和，和同构当且仅当。基于这个性质，为了挖掘频繁子图，只需对最小DFS编码执行最右扩展，因为这种扩展将确保挖掘结果的完全性。图3展示如何通过最右扩展在搜索树中安排所有DFS编码。根是一个空编码。每个节点都是一个图编码形成的DFS编码。每条边代表从长度为（k-1）的DFS编码到长度为k的DFS编码最右扩展。树本身是有序的：根据DFS词典序，左兄弟比右兄弟小。因为图至少有一个DFS编码，所以搜索树能够枚举图数据集中的所有可能子图。然而，一个图可能有几个DFS编码，最小和非最小。非最小DFS编码搜索不产生有用的结果。递归的gSpan算法，使他们的频繁后代被发现，直到支持度小于或者它的编码不再最小。图3本文用C+实现gSpan算法用于挖掘频繁子图。实验环境Pentium IV 2.80GHz处理器，256MB内存，80G硬盘，Windows XP Professional SP2操作系统。频繁子图挖掘所要实现的结果是:给定图库和最小支持度，要求能够挖掘出所有满足最小支持度的最大频繁子图。例如，图4中，当时，可以挖掘出如图(1)、(2)的频繁子图。图4调用以结点数为m，边数为n的图为例，则用DFS编码来表示的图同构判断效率为O()。对于这样的图，因为有n条边，在进行一次深度遍历的时候(即添加一条边进入遍历路径)，每一条边都有被选择和不被选择2种状态，因此在得到最小DFS编码之前，需要条遍历路径。gSpan在对某一频繁子图扩增一条边时，每一个符合条件的边都有被选择扩增的机会，因此其扩展复杂度为O()，算法总的复杂度为O(*)。4、结论图模式挖掘技术作为数据挖掘领域一个新的研究热矛恢正在迅猛发展，基于图模式挖掘的应用也逐渐渗透到现实生活中的诸多领域，其基于图挖掘的思想极大地扩展了以往的以项集为操作对象的挖掘能力，真实地反映了现实生活中之间互相联系的关系，挖掘出更复杂，更符合事实的模式。因此，针对图等结构化数据，并结合非结构化数掘方面的经验和方法论，来实现结构化数据高效挖掘的研究，已经成为数掘研究领域的重要的研究方向。在图挖掘之初，主要采用Apriori思想进行子图扩展，由于频繁子图生成过程中，每一次从k项频繁图增长到k+1频繁图时，都要调用同构判断算法在挖掘过程中生成大量重复候选子图，因而降低了算法的整体效率。在之后的算法中，我们采用了深度优先的子图增长策略，从而显著地提高了图挖掘算法的效率。图挖掘方面，可以拓展挖掘对象，研究带约束的子图的挖掘。在运用方面，可以拓展到实际的化学分子库的图数据库中。参考文献1 J.Han,m.Kamber.Data mining Concepts and TechniquesM(2版).北京:机械工业版社,2006,p489-513. 2 R.Agrawal，T.Imielinski，and A.N.Swalni.Mining association rulesbetween sets of items in large databases.In Proeeedings of the 1993 ACM SIGMOD Internatlonal Conference on Management of Date,VOL22(2)， p207-216,19933 YanY，HanJ.gSpan:Graph-Based substrueture pattern mining.Proe.of ICDM，2002 4 Haiyan Hu,Xifeng Yan,Yu Huang,Jiawei Han，Xiang hong Jasmin Zhou.Mining coherent dense subgraphs across massive biological networks fo