论文题目: 结构数据挖掘与处理的若干问题的研究
论文类型: 博士论文
论文专业: 计算机软件与理论
作者: 王晨
导师: 施伯乐
关键词: 数据挖掘,半结构化与结构化,频繁子树,频繁子图,导出式子树,嵌入式子树,模式增长,单调约束,反单调约束,非单调约束,索引,查询,网络日志,社会网络,生物基因序列
文献来源: 复旦大学
发表年度: 2005
论文摘要: 目前,数据挖掘及其应用已经渗透到多个学科,并在人工智能与机器学习、数据库、模式识别、生物信息学、神经计算等领域取得了丰硕的成果。同时,数据挖掘也不仅是科学家的兴趣所在,更多地得到了政府、工业界的密切关注。通过引进数据挖掘的能力,可以大大提高生产力,取得社会的更大进步。世界上许多国家和地区的政府及工业界都希望掌握数据挖掘技术,提升国家和企业的科技含量,并最终取得领先的地位。 随着研究的深入,越来越多的问题呈现在我们面前,也提出了更高的要求。当前,复杂类型数据的挖掘需求上升,专家学者开始关注这方面的新应用和理论研究,并试图利用无结构化数据挖掘方面的经验和方法论来帮助解决新问题。而针对结构数据的挖掘与处理就是本文所致力研究的问题。 本文针对结构数据挖掘与处理目前存在的几个关键问题进行了研究,包括提高半结构化数据挖掘的速度与效率、提高图结构数据挖掘的可量测性和处理速度、约束条件下的图结构数据挖掘的方法、图结构数据索引技术。本文的创造性研究成果主要有: (1) 提出了4个频繁子树挖掘算法,分别是Chopper、XSpanner、ESMiner、ISMiner。分别采取了序列增长技术和最右路径增长技术,挖掘嵌入式子树和导出式子树模式。实验结果表明这些算法的运行效率良好,在性能上优于目前已提出的子树挖掘算法。 (2) 提出了一个新颖的子图索引结构ADI,并将其应用于频繁子图挖掘过程中,形成了图挖掘算法ADI-Mine和图挖掘应用系统GraphMiner。实验结果表明,ADI在一定程度上避免了子图同构判断的巨大代价,提高了算法的效率和可量测性。通过与目前世界上认可的最快的图挖掘算法gSpan比较,ADI-Mine无论从可量测性上还是从时间效率上,都大大优于对方。在此基础上,还提出了将ADI移植到其他图挖掘算法中的想法,进一步提高效率。 (3) 总结了目前常用的图约束条件,并根据其特性将约束分成若干类别,最后提出了带约束的图挖掘算法CabGin。实验证明,通过聚集挖掘焦点,不仅可以减少噪声结果对分析造成的影响,还可以提高挖掘效率。
论文目录:
ABSTRACT
摘要
第1章 绪论
1.1 引言
1.2 数据挖掘与处理的基本概念
1.3 结构数据挖掘与处理研究的重要性
1.4 结构数据挖掘与处理的一些问题
1.5 本文的工作
第2章 半结构化数据的频繁模式挖掘
2.1 国际研究现状
2.2 基本知识和问题定义
2.3 基于序列模式增长的频繁嵌入式子树挖掘算法
2.3.1 基本思想
2.3.2 朴素算法Chopper
2.3.3 扩展算法XSpanner
2.4 基于最右路径模式增长的频繁子树挖掘算法
2.4.1 基本思想
2.4.2 嵌入式子树挖掘算法ESMiner
2.4.3 导出式子树挖掘算法ISMiner
2.5 实验与性能分析
2.5.1 模拟数据实验
2.5.2 真实数据实验
2.6 小结与进一步工作
第3章 图结构数据的频繁模式挖掘
3.1 国际研究现状
3.2 基本概念和问题描述
3.2.1 图的基本概念
3.2.2 图挖掘算法和瓶颈
3.3 ADI索引结构
3.3.1 数据结构
3.3.2 空间代价
3.3.3 ADI索引基础上的数据访问
3.3.4 ADI索引的构建
3.3.5 使用ADI索引的投影数据库
3.3.6 ADI索引对大规模图集挖掘的作用
3.4 频繁子图挖掘算法ADI-MINE
3.4.1 ADI-Mine算法
3.4.2 优化技术
3.4.3 复杂度分析
3.5 图结构模式挖掘系统GRAPHMINER
3.6 实验与性能分析
3.6.1 模拟数据实验
3.6.2 真实数据实验
3.7 小结与进一步工作
第4章 约束条件下图结构数据的挖掘
4.1 国际现状研究
4.2 图结构模型的基本概念和约束的定义描述
4.2.1 图的基本概念
4.2.2 约束的定义
4.2.3 约束的描述
4.3 带约束的图挖掘算法CABGIN
4.3.1 算法CabGin
4.3.2 带复杂聚集约束条件的频繁子图挖掘方法
4.4 实验与性能分析
4.4.1 模拟数据实验
4.4.2 真实数据实验
4.5 小结与进一步工作
第5章 图结构数据的查询和索引
5.1 国际研究现状
5.2 基本知识
5.3 主索引结构及查询算法
5.3.1 基本思想
5.3.2 主索引结构gADI
5.3.3 基于主索引结构的查询算法gADI-Query
5.4 辅助索引结构及查询算法
5.4.1 辅助索引结构QgADI
5.4.2 基于辅助索引结构的查询算法QgADI-Query
5.5 实验与性能分析
5.5.1 模拟数据实验
5.5.2 真实数据实验
5.6 小结与进一步工作
第6章 结束语
参考文献
攻读博士学位期间的科研工作情况总结
致谢
发布时间: 2005-09-19
参考文献
- [1].结合可视化与数据挖掘的数据分析方法探究[D]. 马昱欣.浙江大学2017
- [2].正则化方法在数据挖掘中的应用与研究[D]. 姜彦.湖南大学2015
- [3].时间序列数据挖掘研究与应用[D]. 王达.浙江大学2004
- [4].粗糙集理论在数据挖掘领域中的应用[D]. 马昕.浙江大学2003
- [5].序列数据挖掘的模型和算法研究[D]. 杨虎.重庆大学2003
- [6].数据挖掘相关算法的研究与平台实现[D]. 李秋丹.大连理工大学2004
- [7].数据挖掘方法研究及其在中药复方配伍分析中的应用[D]. 李力.西南交通大学2003
- [8].Rough Set理论及其在数据挖掘中的应用研究[D]. 于洪.重庆大学2003
- [9].KDD中的几个关键问题研究[D]. 陈莉.西安电子科技大学2003
- [10].数据挖掘中聚类方法的研究[D]. 王莉.天津大学2004
标签：数据挖掘论文; 半结构化与结构化论文; 频繁子树论文; 频繁子图论文; 导出式子树论文; 嵌入式子树论文; 模式增长论文; 单调约束论文; 反单调约束论文; 非单调约束论文; 索引论文; 查询论文; 网络日志论文; 社会网络论文; 生物基因序列论文;