用于图分类的频繁子结构挖掘算法研究

论文摘要

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

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景
• 1.2 研究现状
• 1.2.1 国外研究现状
• 1.2.2 国内研究现状
• 1.3 课题的研究意义及主要研究内容
• 1.3.1 课题来源
• 1.3.2 课题的研究意义
• 1.3.3 课题的主要研究内容
• 1.4 论文结构
• 第2章 基于图的数据挖掘理论概述
• 2.1 引言
• 2.2 图的基本定义
• 2.3 图挖掘的理论基础
• 2.3.1 子图的分类
• 2.3.2 子图同构
• 2.3.3 图的不变量
• 2.3.4 挖掘度量
• 2.3.5 解决方法
• 2.4 图挖掘的方法
• 2.4.1 基于贪心搜索的方法
• 2.4.2 基于ILP 的方法
• 2.4.3 基于归纳数据库的方法
• 2.4.4 基于数学图论的方法
• 2.4.5 基于核函数的方法
• 2.5 图挖掘的主要问题
• 2.6 本章小结
• 第3章 基于标准编码的频繁子图挖掘算法
• 3.1 引言
• 3.2 图的存储结构
• 3.3 gSpan 算法的缺点
• 3.4 频繁子图挖掘算法
• 3.4.1 图模式的扩展
• 3.4.2 图的标准化编码
• 3.4.3 构建ADI++存储结构
• 3.4.4 删除非标准编码
• 3.4.5 同构的判断
• 3.4.6 算法设计
• 3.4.7 算法理论分析
• 3.5 算法的实现与分析
• 3.5.1 实际的数据集
• 3.5.2 模拟的数据集
• 3.6 本章小结
• 第4章 特征模式的选取方法研究
• 4.1 引言
• 4.2 特征模式
• 4.2.1 组合特征的定义
• 4.2.2 有判别力的图模式
• 4.3 目标函数的选取
• 4.3.1 度量手段的非单调性
• 4.3.2 基于信息论的意义度量
• 4.3.3 优化的图模式挖掘
• 4.4 剪枝技术
• 4.4.1 垂直剪枝
• 4.4.2 频数封装
• 4.4.3 结构相似性
• 4.4.4 水平剪枝
• 4.5 特征模式选取算法
• 4.6 算法的实验分析
• 4.6.1 实验环境
• 4.6.2 比较挖掘结果的质量
• 4.6.3 比较算法的效率
• 4.7 本章小结
• 第5章 基于特征模式的图分类方法研究
• 5.1 引言
• 5.2 分类概述
• 5.2.1 分类的定义
• 5.2.2 分类的有关问题
• 5.2.3 典型的分类方法
• 5.2.4 二元分类
• 5.3 基于频繁模式的分类框架
• 5.3.1 频繁模式的有用性
• 5.3.2 判别力和支持度的关系
• 5.3.3 基于频繁模式分类的证明
• 5.4 最小支持度的设置
• 5.4.1 最小支持度的影响
• 5.4.2 设置策略
• 5.5 分类器的构造
• 5.5.1 构造分类规则
• 5.5.2 使用分类规则进行分类
• 5.5.3 算法的实验分析
• 5.6 本章小结
• 结论
• 参考文献
• 攻读博士学位期间承担的科研任务与主要成果
• 致谢
• 作者简介