学位论文 > 优秀研究生学位论文题录展示

图数据库频繁模式挖掘关键技术研究

作　者: 屈松
导　师: 杨艳
学　校: 黑龙江大学
专　业: 计算机软件与理论
关键词: 数据挖掘 频繁子图 极大频繁子图 代表性模式
分类号: TP311.13
类　型: 硕士论文
年　份: 2012年
下　载: 39次
引　用: 0次
阅　读: 论文下载
 

内容摘要


从图数据库挖掘频繁模式在化学信息学、计算生物学、WEB信息管理、社会网络分析等领域有着广泛的应用。因此本文重点研究了从图数据库中挖掘频繁模式的关键技术，并针对频繁模式挖掘所面临的效率瓶颈、结果集庞大以及高复杂、冗余性等问题，在本文中提出了基于随机化挖掘极大频繁子图的方法RMPM、挖掘具有代表性频繁子图的算法FRSM、InRSM。本文的主要研究成果有：1.随机化方法在挖掘海量数据集时非常高效，但是因为随机性，会造成结果的重复发现，势必造成很多重复和无用的子图同构计算。本文提出的基于随机化挖掘极大频繁子图的方法RMPM，通过对已挖掘到的结果建立索引，提高了随机算法的效率。在真实和模拟数据集上的实验结果也证实了RMPM算法是高效、可伸缩的。本文提出的随机算法的思想是通用的，可以应用于各种各样的模式，比如自由树、项集等，在真实数据集上挖掘极大频繁自由树的实验结果也证实了RMPM算法是通用的。2.为了压缩频繁模式集合，挖掘出更小、更有代表性的频繁模式集合，本文提出了挖掘具有代表性频繁模式的算法FRSM，算法第一步采用本文提出的效率更高的RMPM算法作为频繁模式挖掘算法，第二步在RMPM结果集上聚类，在聚类时，综合考虑频繁子图在事务空间上的相似性和模式空间上的相似性，使得聚类的质量更好，获得的模式更具代表性。在大量的实验上也证明了FRSM算法所得到的代表模式集合比不考虑或只考虑模式在事务空间上的相似性的聚类所得到的模式更具代表性。3.本文也提出直接从图数据库中挖掘代表模式集合的算法InRSM，它比两步算法FRSM更加高效，InRSM算法同样考虑了模式在事务空间上和模式空间上的相似性，大量的实验也证明了InRSM算法是高效的和可伸缩的。

全文目录


中文摘要  3-4
ABSTRACT  4-9
第1章 绪论  9-16
  1.1 研究背景  9-11
    1.1.1 数据挖掘概述  9-10
    1.1.2 频繁模式挖掘的作用  10-11
  1.2 国内外研究现状  11-12
  1.3 本文主要研究工作  12-15
    1.3.1 挖掘频繁子图面临的挑战  12-13
    1.3.2 主要解决办法  13-14
    1.3.3 本文主要研究成果  14-15
  1.4 本文章节安排  15-16
第2章 频繁模式挖掘  16-25
  2.1 引言  16
  2.2 传统的 FPM 算法  16-20
    2.2.1 频繁项集挖掘  17
    2.2.2 频繁序列挖掘  17-18
    2.2.3 频繁子树挖掘  18
    2.2.4 频繁子图挖掘  18-20
  2.3 采样和随机方法在 FPM 中的应用  20-21
  2.4 压缩频繁模式  21-24
    2.4.1 极大/闭频繁模式挖掘  21
    2.4.2 TOP-K 模式挖掘  21-22
    2.4.3 基于聚类的代表模式集合挖掘  22-23
    2.4.4 频繁图模式压缩  23-24
  2.5 本章小结  24-25
第3章 挖掘极大频繁子图  25-46
  3.1 引言  25-26
  3.2 背景知识  26-28
  3.3 极大频繁子图挖掘算法 RMPM  28-36
    3.3.1 算法的搜索空间  28-30
    3.3.2 算法使用的数据结构  30-31
    3.3.3 算法描述  31-34
    3.3.4 子图查询  34-36
    3.3.5 支持度计算  36
  3.4 实验结果与分析  36-43
    3.4.1 真实数据集上的实验结果与分析  37-40
    3.4.2 模拟数据集上的实验结果与分析  40-43
  3.5 极大频繁自由树挖掘实验结果与分析  43-45
  3.6 本章小结  45-46
第4章 挖掘具有代表性的频繁模式  46-66
  4.1 引言  46-47
  4.2 背景知识  47-49
  4.3 挖掘具有代表性的模式  49-56
    4.3.1 相似度测量  49-52
    4.3.2 FRSM 算法  52-53
    4.3.3 InRSM 算法  53-56
  4.4 实验结果与分析  56-65
    4.4.1 实验设置  56-58
    4.4.2 图相似度阈值对实验结果的影响  58
    4.4.3 相似度测量函数对聚类质量的影响  58-62
    4.4.4 权重系数对 MN_SIM 相似度测量函数的影响  62
    4.4.5 InRSM 和 FRSM 效率对比实验  62-65
  4.5 本章小结  65-66
结论  66-67
参考文献  67-75
致谢  75-76
攻读硕士学位期间发表的学术论文  76

相似论文

  1. 频繁图结构并行挖掘算法的研究与实现,TP311.13
  2. 基于数据挖掘技术的保健品营销研究,F426.72
  3. 高忠英学术思想与经验总结及运用补肺汤加减治疗呼吸系统常见病用药规律研究,R249.2
  4. 张炳厚学术思想与临床经验总结及应用地龟汤类方治疗慢性肾脏病的经验研究,R249.2
  5. Bicluster数据分析软件设计与实现,TP311.52
  6. 基于变异粒子群的聚类算法研究,TP18
  7. 融合粒子群和蛙跳算法的模糊C-均值聚类算法研究,TP18
  8. 基于遗传算法和粗糙集的聚类算法研究,TP18
  9. 基于数据挖掘的税务稽查选案研究,F812.42
  10. 面向社区教育的个性化学习系统的研究与实现,TP391.6
  11. 基于关联规则挖掘的入侵检测系统的研究与实现,TP393.08
  12. 数据仓库技术在银行客户管理系统中的研究和实现,TP315
  13. 基于行业参数优化模型的投资项目决策支持系统,F283
  14. 数据集市在电信经营分析中的应用研究,TP311.13
  15. 数据挖掘在高职院校学生成绩分析中的应用,TP311.13
  16. 基于数据挖掘的个性化在线教学辅助系统的研究与设计,TP311.13
  17. 基于数据挖掘的课程考核与分析决策系统的设计和实现,TP311.13
  18. 基于Moodle的高职网络教学系统设计与实现,TP311.52
  19. 教学质量评估数据挖掘系统设计与开发,TP311.13
  20. 关联规则挖掘在交通事故成因分析中的应用,U491.31
  21. 关联规则算法在高职院校贫困生认定工作中的应用,G717

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机软件 > 程序设计、软件工程 > 程序设计 > 数据库理论与系统
© 2012 www.xueweilunwen.com