基于多层索引结构的频繁子图挖掘算法研究

论文摘要

随着信息技术的飞速发展,数据规模的急速膨胀,如何有效地解决海量数据的利用问题具有巨大的商机和科学研究价值,特别是近几十年来数据库、统计学和人工智能等学科的发展决定并促进了数据挖掘的产生和迅速发展。数据挖掘是指从大型数据库或数据仓库中挖掘出数据间潜在的模式,自动提取未知的、完整的、有价值的信息,以指导商业行为或辅助科学研究。数据挖掘技术及其算法成为目前国际上数据库和信息决策领域最前沿的研究方向之一。频繁模式挖掘是数据挖掘的重要任务并被广泛应用于各个领域,基于Apriori思想和FP-Growth树的算法成为两大主流被广泛应用,前期主要是针对无结构数据的模式挖掘,随着研究的深入日益表现出它的局限性,而频繁模式中的频繁子图结构可以表达更为丰富的信息也具有更大的挖掘难度。图结构挖掘在社会网络、分子结构和生物信息学等领域有着更为广泛的应用。近年来,关于图结构挖掘的研究成为热点。频繁子图挖掘算法是图结构挖掘研究的基础问题之一,决定着图结构挖掘中图分类和图查询等问题的研究难度,但频繁子图挖掘的核心操作子图同构测试复杂性太高,测试支持度必须多次重复扫描数据库,也耗费了大量时间,因此如何有效挖掘频繁子图已成为数据挖掘领域的热点问题之一。在各种频繁子图算法中:最早采用Apriori思想的是AGM算法,它采用邻接矩阵来表示图,并将min（code）作为该图的唯一邻接矩阵,从而避免了直接进行子图同构的计算;gSpan算法采用深度优先搜索和模式增长的方法,从而在一定程度上避免了子图同构测试的代价,但面对大规模图集的挖掘时,大量的I/O操作就会大大降低算法的性能;ADI-Mine算法在gSpan算法基础上引入了ADI索引结构,这种索引结构可以降低子图同构检查的单位时间,并使得算法的执行效率有所提高;最近又提出了将搜索范围限制在一定边缘区域的MARGIN算法等。在深入研究已有的各种频繁子图挖掘算法基础上,针对无向标号连通图,本文设计了一种图的多层索引存储结构GDI,提出了基于GDI的频繁子图挖掘算法TG-Mine。首先,此算法使用了DFS编码树的搜索空间,不会丢失任何频繁子图,保证了结果集的完备性。其次,它运用的GDI索引结构可以完全代替对原始图集的搜索,简化了频繁子图挖掘过程中大量的数据访问操作。TG-Mine算法的整个挖掘过程可分为两步:第一步,深度优先（DFS）挖掘频繁子树,第二步,广度优先（BFS）扩展第一步生成的所有频繁子树集为频繁子图集。在第一步DFS扩充边的过程中仅仅扩充前向边,保证生成的更大的频繁模式是树结构,第二步扩充边的过程中仅仅扩充后向边,不生成新的结点,有效地生成候选子图,降低了检查子图同构的单位时间并减少了DFS编码的测试次数。最后,本文对TG-Mine算法进行实验,并与gSpan算法和ADI-Mine算法进行了比较,TG-Mine的效率相对较高。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景
• 1.2 国内外研究现状
• 1.3 所做的主要工作
• 1.4 论文的结构
• 第2章 数据挖掘与图结构数据挖掘简介
• 2.1 数据挖掘简介
• 2.1.1 数据挖掘的产生背景
• 2.1.2 数据挖掘的概念与过程
• 2.1.3 数据挖掘的分类及功能
• 2.1.4 数据挖掘的难点与发展趋势
• 2.2 图结构数据挖掘简介
• 2.2.1 图的基本概念
• 2.2.2 图结构数据挖掘的背景及应用
• 2.2.3 图结构数据挖掘的分类
• 2.2.4 图结构数据挖掘的难点
• 2.3 本章小结
• 第3章 几种典型的频繁子图挖掘算法
• 3.1 基于Apriori的算法AGM
• 3.2 经典算法gSpan
• 3.2.1 gSpan算法的相关概念
• 3.2.2 gSpan算法思想
• 3.3 ADI-Mine算法思想
• 3.4 MARGIN算法
• 3.5 频繁子图挖掘算法小结
• 第4章 频繁子图挖掘算法TG-Mine的研究与实现
• 4.1 TG-Mine算法的相关概念
• 4.2 TG-Mine算法思想
• 4.3 多层索引结构GDI的构建
• 4.4 频繁子树挖掘算法TreeMine
• Mine算法思想'>4.4.1 判断DFS编码最小化的Quick_Mine算法思想
• 4.4.2 数据结构
• 4.4.3 TreeMine算法的分析与设计
• 4.5 频繁子图挖掘算法TG-Mine
• 4.6 复杂度分析
• 4.6.1 GDI多层索引结构的空间复杂度
• 4.6.2 TG-Mine算法的时间复杂度
• 4.7 实验结果与性能分析
• 4.8 本章小结
• 第5章 总结与展望
• 5.1 总结
• 5.2 进一步工作
• 参考文献
• 附录
• 致谢
• 攻读硕士学位期间的研究成果