随着计算机与信息技术的发展,数据挖掘技术已经广泛应用到人工智能、模式识别、生物信息等许多领域。当前,复杂类型数据的挖掘需求上升,专家学者开始关注这方面的新应用和理论研究,并试图利用结构化数据挖掘方面的经验和方法来帮助解决新问题。在计算机科学领域,图具有直观的表达形式,它能够表达更加丰富的语义,同时,图也是最复杂的数据结构之一,与一般的数据相比,这种丰富的语义也增加了数据结构的复杂性和挖掘令人感兴趣的图结构的难度。因此,图挖掘需要综合应用图论知识与数据挖掘的技术。图的挖掘无论在研究领域还是在商业领域都有着广泛的应用,例如:CAD电路分析、分子模型分析、Web浏览中的用户兴趣点的挖掘以及数据的压缩等等。在图挖掘中频繁子图挖掘又是图分类和图聚类的基础,如何从大量的图中挖掘出令人感兴趣的频繁子图模式成为国内数据挖掘领域研究的热点之一。本文的主要内容如下。首先,本文介绍了图的相关概念、图挖掘方法的类型和经典的频繁子图挖掘算法,并对现有的经典算法进行了全面的综合分析、归纳和总结,重点指出了有代表性的算法的优缺点以及图挖掘存在的主要问题,为下一步的研究指明了方向。其次,针对基于模式增长算法gSpan所存在的扩展频繁子图时产生冗余的问题,提出了一种改进的算法CSGM。用ADI++存储结构来代替原算法的邻接链表的存储结构,同时还提出了有效的删除非最小DFS编码的方法,保证算法在扩展频繁子图时每一次均能够生成图的标准编码,避免对标准编码不必要的判断以及非标准编码的支持度计算。另外,在挖掘中使用Hash表存储同构图的Hash地址,来计算频繁子图的支持度,避免了对图集的重复扫描,也相应地减少了子图同构判断的次数。在实际数据集和人工合成的模拟数据集上做了全面的实验,对算法的正确性、处理大规模图集的能力以及运行时间上进行了验证。再次,以频繁子图挖掘结果作为特征候选集,选取特征来生成一个有辨别力的频繁模式的小集合用作分类特征,本文又提出了一种特征模式选取算法。通过引入信息熵、信息增益这种有判别力的度量手段给出了目标函数,说明了如何选取分类特征的方法。同时,为了缩减图模式的搜索空间和提高挖掘效率,还给出了垂直剪枝和水平剪枝两种剪枝策略。通过实验验证了挖掘结果的质量及算法的运行效率。最后,提出了一种基于频繁模式的图分类算法。先从理论上分析了模式的预测能力和支持度之间的关系,给出了最小支持度阈值的设置策略。进一步采用有判别力的频繁子图作为特征图模式来构造分类规则,通过关联分类的方法来训练分类器,识别新图的类别。通过实验对分类器的性能进行了验证。