频繁子图挖掘算法的研究

论文摘要

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

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 频繁图挖掘的研究背景
• 1.2 频繁图挖掘的研究现状
• 1.3 研究目的和主要内容
• 1.4 论文的结构组织
• 第二章 频繁子图挖掘相关基础
• 2.1 数据挖掘概述
• 2.1.1 数据挖掘的概念
• 2.1.2 数据挖掘步骤
• 2.1.3 数据挖掘库的建立
• 2.1.4 数据的分析和准备
• 2.1.5 数据挖掘的分类
• 2.1.6 频繁模式挖掘概念
• 2.2 图的相关定义
• 2.3 频繁子图挖掘相关知识
• 2.3.1 频繁子图挖掘概念
• 2.3.2 频繁子图挖掘算法
• 2.3.2.1 广度优先算法
• 2.3.2.2 深度优先算法
• 2.4 本章小结
• 第三章 一种基于 AGM 频繁子图挖掘的改进方法
• 3.1 邻接矩阵的相关定义
• 3.2 算法的设计思想
• 3.2.1 邻接矩阵的正规化
• 3.2.2 正准形
• 3.3 算法的改进
• 3.3.1 顶点标识以及边标识的顺序关系
• 3.3.2 候选子图生成的判定条件
• 3.3.3 算法描述
• 3.4 实验结果及分析
• 3.5 改进方法与相关算法比较
• 3.6 本章小结
• 第四章 AGM 算法用于连通图频繁模式挖掘的方法
• 4.1 相关定义
• 4.1.1 图结构数据
• 4.1.2 AGM 算法
• 4.2 改进算法的设计思想
• 4.2.1 邻接矩阵的结合
• 4.2.2 子图检测
• 4.2.3 邻接矩阵的正准化
• 4.3 基于邻接矩阵的图连通性判定
• 4.3.1 连通图的概念
• 4.3.2 连通性的判定依据
• 4.3.3 图的连通性判定
• 4.4 算法设计
• 4.4.1 邻接矩阵结合的条件
• 4.4.2 算法描述
• 4.5 实验结果及分析
• 4.6 改进方法与FSG 算法比较
• 4.7 本章小结
• 第五章 结论与展望
• 5.1 结论
• 5.2 展望
• 参考文献
• 致谢
• 附录（攻读硕士学位期间发表录用论文）
• 摘要
• ABSTRACT