学位论文 > 优秀研究生学位论文题录展示
频繁子图挖掘算法的研究
作 者: 陈立宁
导 师: 罗可
学 校: 长沙理工大学
专 业: 计算机软件与理论
关键词: 频繁模式 数据挖掘 AGM算法 邻接矩阵 候选子图 连通图
分类号: TP311.13
类 型: 硕士论文
年 份: 2011年
下 载: 38次
引 用: 0次
阅 读: 论文下载
内容摘要
数据挖掘的对象包括像关系数据库中的结构化数据,也包括诸如文本、图像、图形的半结构化数据或非结构化数据。同结构化数据相比,非结构化数据能更好地表达对象间的联系。随着非结构化频繁模式挖掘的发展,子图挖掘成为新的研究热点。图是一种复杂的数据结构,这使得挖掘图中令人感兴趣的子结构以及频繁模式变得比挖掘一般数据要更加困难,需要综合运用图的相关知识和数据挖掘的技术。目前子图挖掘领域中主要存在的问题是:生成的候选子图数量庞大,需要花费大量时间判断子图匹配以及重复扫描数据集来计算支持度,影响算法性能。本文重点研究如何缩减频繁子图的候选集,提高算法效率。主要工作如下:1.本文结合图论知识,对AGM (Apriori-based Graph Mining)算法进行了改进。改进方法针对子图同构以及冗余子图的问题,将图的顶点和边追加标识,并按标识大小进行排序,在参与候选图生成前先确定图的邻接矩阵,这样能在一定程度上减少冗余子图生成数量,减少了计算时间开销,提高挖掘效率。同时改进算法能够更有效、便捷地判断矩阵间是否存在等价子矩阵。2.针对连通图特定模式,本文提出了一种连通图频繁模式挖掘的改进方法。结合图论知识,深入分析了节点邻接矩阵,提出了图的连通性判定准则。同时从数学定义上严格描述了路径和节点邻接矩阵的概念,并运用于改进方法。该方法基于AGM算法,在图的邻接矩阵结合时加入一些限制条件,使之满足一些特性。改进方法有效地减少了候选子图的生成数量,缩减了计算时间。
|
全文目录
摘要 5-6 ABSTRACT 6-9 第一章 绪论 9-14 1.1 频繁图挖掘的研究背景 9-11 1.2 频繁图挖掘的研究现状 11-12 1.3 研究目的和主要内容 12 1.4 论文的结构组织 12-14 第二章 频繁子图挖掘相关基础 14-25 2.1 数据挖掘概述 14-19 2.1.1 数据挖掘的概念 14-15 2.1.2 数据挖掘步骤 15 2.1.3 数据挖掘库的建立 15-17 2.1.4 数据的分析和准备 17 2.1.5 数据挖掘的分类 17-19 2.1.6 频繁模式挖掘概念 19 2.2 图的相关定义 19-20 2.3 频繁子图挖掘相关知识 20-24 2.3.1 频繁子图挖掘概念 20 2.3.2 频繁子图挖掘算法 20-24 2.3.2.1 广度优先算法 21-22 2.3.2.2 深度优先算法 22-24 2.4 本章小结 24-25 第三章 一种基于 AGM 频繁子图挖掘的改进方法 25-34 3.1 邻接矩阵的相关定义 25-26 3.2 算法的设计思想 26-28 3.2.1 邻接矩阵的正规化 26-27 3.2.2 正准形 27-28 3.3 算法的改进 28-30 3.3.1 顶点标识以及边标识的顺序关系 28 3.3.2 候选子图生成的判定条件 28-29 3.3.3 算法描述 29-30 3.4 实验结果及分析 30-32 3.5 改进方法与相关算法比较 32-33 3.6 本章小结 33-34 第四章 AGM 算法用于连通图频繁模式挖掘的方法 34-46 4.1 相关定义 34-36 4.1.1 图结构数据 34-35 4.1.2 AGM 算法 35-36 4.2 改进算法的设计思想 36-38 4.2.1 邻接矩阵的结合 36-37 4.2.2 子图检测 37 4.2.3 邻接矩阵的正准化 37-38 4.3 基于邻接矩阵的图连通性判定 38-41 4.3.1 连通图的概念 38 4.3.2 连通性的判定依据 38-39 4.3.3 图的连通性判定 39-41 4.4 算法设计 41-42 4.4.1 邻接矩阵结合的条件 41 4.4.2 算法描述 41-42 4.5 实验结果及分析 42-44 4.6 改进方法与FSG 算法比较 44-45 4.7 本章小结 45-46 第五章 结论与展望 46-48 5.1 结论 46-47 5.2 展望 47-48 参考文献 48-52 致谢 52-53 附录(攻读硕士学位期间发表录用论文) 53-54 摘要 54-57 ABSTRACT 57-61
|
相似论文
- 基于数据挖掘技术的保健品营销研究,F426.72
- 高忠英学术思想与经验总结及运用补肺汤加减治疗呼吸系统常见病用药规律研究,R249.2
- 张炳厚学术思想与临床经验总结及应用地龟汤类方治疗慢性肾脏病的经验研究,R249.2
- Bicluster数据分析软件设计与实现,TP311.52
- 基于变异粒子群的聚类算法研究,TP18
- 融合粒子群和蛙跳算法的模糊C-均值聚类算法研究,TP18
- 基于遗传算法和粗糙集的聚类算法研究,TP18
- 基于数据挖掘的税务稽查选案研究,F812.42
- 面向社区教育的个性化学习系统的研究与实现,TP391.6
- 基于关联规则挖掘的入侵检测系统的研究与实现,TP393.08
- 数据仓库技术在银行客户管理系统中的研究和实现,TP315
- 关于特征多项式的两个参数及其应用,O157.5
- 基于Moodle的高职网络教学系统设计与实现,TP311.52
- 教学质量评估数据挖掘系统设计与开发,TP311.13
- 关联规则算法在高职院校贫困生认定工作中的应用,G717
- 基于数据挖掘技术在城市供水的分析与决策,F299.24;F224
- 数据挖掘技术在电视用户满意度分析中的应用研究,TP311.13
- Web使用挖掘与网页个性化服务推荐研究,TP311.13
- 数据挖掘在学校管理和学生培养中的应用,TP311.13
- 高校毕业生就业状况监测系统研究,G647.38
- 基于数据仓库的药品监管辅助决策支持系统的设计与实现,TP311.13
中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机软件 > 程序设计、软件工程 > 程序设计 > 数据库理论与系统
© 2012 www.xueweilunwen.com
|