基于CloseGraph的图分类算法研究

论文摘要

随着计算机与信息技术的发展,数据挖掘技术已经广泛应用到人工智能、模式识别、生物信息等许多领域。当前,复杂类型数据的挖掘需求上升,专家学者开始关注这方面的新应用和理论研究,并试图利用结构化数据挖掘方面的经验和方法来帮助解决新问题。因此,基于图的数据挖掘就是本文所致力研究的课题。目前,在图挖掘领域中迫切需要解决的问题是如何提高在图挖掘算法中的效率。由于频繁子图挖掘会产生巨大的结果集,在一定程度上制约了算法性能,而最大频繁子图挖掘可以有效缩减频繁子图的结果集。因此,本文重点研究基于闭图的频繁子图挖掘算法和图分类算法,并提高算法效率。针对以上问题做以下几个方面的研究。首先,在研究闭图模式挖掘典型算法的基础上,提出了一个新的频繁子图挖掘算法BPCG。算法使用了一种新结构表存储频繁子图集,从而无需扫描图集就可直接扩展最频繁邻接边及计算频数阈值;算法又利用兄弟剪枝策略和删除局部频繁边,缩小搜索空间并减少不必要的操作。其次,基于改进的频繁闭图挖掘算法,以频繁闭图挖掘结果作为特征候选集,又提出了一种图分类算法CGC,并说明了如何提取分类特征及构造分类器的方法。最后,本文通过实例以及实验对BPCG算法进行了说明和验证,这种新的频繁子图挖掘算法处理较大图集时在运行时间上表现出了明显的优势。本文还通过实验证明了CGC算法的执行效率以及准确性。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 研究背景
• 1.2 研究现状
• 1.2.1 国外研究现状
• 1.2.2 国内研究现状
• 1.3 研究意义
• 1.4 研究内容
• 1.5 本文结构
• 第2章 基础知识概述
• 2.1 引言
• 2.2 图的基本定义
• 2.3 图挖掘简介
• 2.4 基于 Apriori 思想的频繁子图挖掘
• 2.4.1 AGM 算法
• 2.4.2 FSG 算法
• 2.5 基于 FP-Growth 思想的频繁子图挖掘
• 2.5.1 gSpan 算法
• 2.5.2 CloseGraph 算法
• 2.6 图挖掘的主要问题
• 2.7 本章小结
• 第3章 一种改进的 CloseGraph 挖掘算法
• 3.1 引言
• 3.2 算法思想
• 3.3 基础概念
• 3.4 图的邻接矩阵表示法
• 3.5 删除局部频繁边
• 3.6 最频繁邻接边扩展
• 3.7 基于结构相似的兄弟剪枝策略
• 3.8 BPCG 算法描述及复杂度分析
• 3.8.1 BPCG 算法描述
• 3.8.2 复杂度分析
• 3.9 本章小结
• 第4章 基于改进 CloseGraph 的图分类算法研究
• 4.1 引言
• 4.2 分类概述
• 4.2.1 基本定义
• 4.2.2 二元分类
• 4.2.3 分类框架
• 4.3 函数选择及特征集提取方法
• 4.4 分类器的构造
• 4.5 分类算法
• 4.6 本章小结
• 第5章 实验及结果分析
• 5.1 引言
• 5.2 BPCG 算法的实现与分析
• 5.2.1 实验设置
• 5.2.2 实际的数据集
• 5.2.3 模拟的数据集
• 5.3 CGC 算法的实现与分析
• 5.3.1 实验设置
• 5.3.2 数据集
• 5.4 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间承担的科研任务与主要成果
• 致谢
• 作者简介