数据挖掘的对象包括像关系数据库中的结构化数据,也包括诸如文本、图像、图形的半结构化数据或非结构化数据。同结构化数据相比,非结构化数据能更好地表达对象间的联系。随着非结构化频繁模式挖掘的发展,子图挖掘成为新的研究热点。图是一种复杂的数据结构,这使得挖掘图中令人感兴趣的子结构以及频繁模式变得比挖掘一般数据要更加困难,需要综合运用图的相关知识和数据挖掘的技术。目前子图挖掘领域中主要存在的问题是:生成的候选子图数量庞大,需要花费大量时间判断子图匹配以及重复扫描数据集来计算支持度,影响算法性能。本文重点研究如何缩减频繁子图的候选集,提高算法效率。主要工作如下:1.本文结合图论知识,对AGM (Apriori-based Graph Mining)算法进行了改进。改进方法针对子图同构以及冗余子图的问题,将图的顶点和边追加标识,并按标识大小进行排序,在参与候选图生成前先确定图的邻接矩阵,这样能在一定程度上减少冗余子图生成数量,减少了计算时间开销,提高挖掘效率。同时改进算法能够更有效、便捷地判断矩阵间是否存在等价子矩阵。2.针对连通图特定模式,本文提出了一种连通图频繁模式挖掘的改进方法。结合图论知识,深入分析了节点邻接矩阵,提出了图的连通性判定准则。同时从数学定义上严格描述了路径和节点邻接矩阵的概念,并运用于改进方法。该方法基于AGM算法,在图的邻接矩阵结合时加入一些限制条件,使之满足一些特性。改进方法有效地减少了候选子图的生成数量,缩减了计算时间。