学位论文 > 优秀研究生学位论文题录展示
频繁图结构并行挖掘算法的研究与实现
作 者: 刘巍
导 师: 高宏
学 校: 哈尔滨工业大学
专 业: 计算机科学与技术
关键词: 频繁子图挖掘 频繁闭图挖掘 并行算法 动态负载平衡
分类号: TP311.13
类 型: 硕士论文
年 份: 2008年
下 载: 80次
引 用: 0次
阅 读: 论文下载
内容摘要
随着包括化学情报学、生物信息学、计算机视觉、视频索引、文本检索以及Web分析在内的广泛应用,图做为一种一般的数据结构在复杂结构和它们之间相互作用建模过程中变得越来越重要。为了进一步进行特征化、区分、分类和聚类分析,挖掘频繁子图模式已经成为了一项重要的任务,频繁子图挖掘已经成为了数据挖掘中一个活跃和重要的课题。在各种各样的图模式中,频繁子结构是可以在图集合中发现的非常基本的模式。频繁子结构可以用来刻画图集合的特征,区分不同的图组群,对图进行分类和聚类,构造图索引和更方便的在图数据库中进行相似性搜索,例如,通过对比不同类中频繁图的支持度,发现HIV甄别数据集中活跃的化学结构。但是,现有频繁子图挖掘算法在最小支持度很低时效果并不好,因此,本文给出在集群并行环境下频繁图并行挖掘算法。本文主要的研究结果如下:根据频繁子图挖掘算法gSpan的算法思想,提出了一种在基于集群并行环境下的动态负载平衡的频繁子图并行挖掘算法。该方法通过划分DFS词典树,维护本地负载队列,限制负载粒度等策略有效的实现了并行频繁子图的挖掘,理论分析和实验结果验证本文的并行算法在集群机器上具有很好的性能。针对频繁闭图挖掘算法CloseGraph,给出了早期终止失败检测的替代方法,实现了CloseGraph算法,并且进一步提出了频繁闭图并行挖掘算法,并且实验验证了算法,算法具有较好的性能。
|
全文目录
摘要 4-5 Abstract 5-9 第1章 绪论 9-13 1.1 课题研究的背景和意义 9-11 1.2 国内外研究现状 11 1.3 本文的主要研究内容 11-13 第2章 预备知识 13-18 2.1 频繁图结构挖掘的相关概念 13-14 2.1.1 什么是频繁子图挖掘 13-14 2.1.2 什么是频繁闭图挖掘 14 2.2 频繁子图的挖掘方法 14 2.2.1 基于Apriori方法 14 2.2.2 模式增长方法 14 2.3 gSpan算法的相关概念 14-17 2.4 本章小结 17-18 第3章 频繁子图并行挖掘算法的设计与实现 18-38 3.1 频繁子图并行挖掘算法的设计 18-28 3.1.1 基于DFS词典树的划分策略 18-19 3.1.2 动态负载平衡 19-20 3.1.3 协调机的分配节点选择 20-21 3.1.4 节点的负载重新划分 21-25 3.1.5 算法流程 25-28 3.1.6 算法性能分析 28 3.2 频繁子图并行挖掘算法的实验分析 28-37 3.2.1 单机gSpan的挖掘算法 29-30 3.2.2 朴素频繁子图并行挖掘算法 30-32 3.2.3 动态负载平衡策略对并行挖掘算法的效率提升 32-33 3.2.4 负载粒度控制策略对算法效率的影响 33-35 3.2.5 算法性能指标 35-37 3.3 本章小结 37-38 第4章 频繁闭图并行挖掘算法的设计与实现 38-53 4.1 频繁闭图的挖掘算法改进与实现 38-41 4.2 频繁闭图并行挖掘算法设计 41-47 4.2.1 基于DFS词典树划分策略 41-42 4.2.2 动态负载平衡 42-44 4.2.3 算法流程 44-46 4.2.4 算法性能分析 46-47 4.3 频繁闭图并行挖掘算法实现与实验分析 47-52 4.3.1 单机频繁闭图挖掘算法 47-48 4.3.2 频繁闭图并行挖掘算法 48-50 4.3.3 算法性能指标 50-52 4.4 本章小结 52-53 结论 53-54 参考文献 54-58 攻读学位期间发表的学术论文 58-61 致谢 61
|
相似论文
- 基于并行算法的模糊综合评价模型的设计与应用,TP18
- 基于视觉反馈与行为记忆的GPU并行蚁群算法,TP301.6
- GPU加速的仿射算术在几何设计中的应用研究,TP391.41
- 基于GPU的H.264到AVS视频转码并行设计,TN919.81
- H.264并行编码算法设计及其在GPU上的实现,TP391.41
- 基于ADSPTS201S的并行信号处理系统的设计与实现,TN957.51
- 基于小波变换的图像压缩并行算法研究,TP391.41
- 基于GPU的并行蚁群优化算法的研究与实现,TP301.6
- 基于MapReduce的聚类算法的并行化研究,TP311.13
- 面向星载计算机的容错并行算法研究与实现,TP302.8
- 激光能量沉积光路追踪法及其并行化,TN241
- 基于LBM的两相流数值模拟及其并行算法的实现,O359
- 基于树形计算结构的电力系统潮流并行算法研究,TM744
- 基于三层C/S结构的无线货物储运管理系统设计与实现,TP311.52
- 最大频繁子图挖掘算法研究,TP301.6
- D-TIN并行构建方法及其在地图综合中的应用研究,P283
- 图像匹配的并行算法研究,TP301.6
- 求解大规模支持向量机问题的并行算法研究,TP18
- 迁移式并行遗传算法求解支持向量机反问题,TP18
- 基于图的数据挖掘算法研究,TP311.13
中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机软件 > 程序设计、软件工程 > 程序设计 > 数据库理论与系统
© 2012 www.xueweilunwen.com
|