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

不确定图数据挖掘算法研究

作　者: 韩蒙
导　师: 李建中
学　校: 黑龙江大学
专　业: 计算机应用技术
关键词: 不确定图 图挖掘 极大频繁子图 紧密子图 无线传感器网络
分类号: TP311.13
类　型: 硕士论文
年　份: 2012年
下　载: 181次
引　用: 1次
阅　读: 论文下载
 

内容摘要


随着计算机产业及互联网的不断发展，各行各业积累了海量的数据信息，图作为最通用的数据结构之一，在描述数据的属性及结构特征等方面具有显著的优势：一方面它可以描述生物、化学等学科中的化合物及蛋白质并直观表达各类性质；另一方面在越来越广泛使用的互联网以及现实生活中，人与人之间或不同个体单位所构成的社交网络也都可抽象成图，使用图来描述的数据信息称为图数据。由于数据来源的差异及描述手段的限制，实际生活中获得的图数据经常出现结构与属性不精确和不完整的情况，具有各种不确定性的图数据广泛存在，从不确定图数据中所蕴含的丰富结构及语义信息中挖掘知识具有重要意义。本文对不确定图挖掘的几个典型算法问题进行了研究。主要研究成果如下：1.针对不确定图中的频繁子图挖掘问题提出一种基于随机游走技术的极大频繁子图挖掘算法。该算法基于随机游走技术，利用不确定图自身的特点，结合其与确定图的关系，避免了枚举指数级别可能图实例的计算，可高效快速地发现不确定图中的极大频繁子图。2.针对在不确定图中挖掘紧密子图问题提出一套有效的解决方案。首先对问题进行了形式化的定义，然后在理论上证明了紧密子图发现问题的计算复杂性，并根据不同的问题规模提出基于分枝限界策略的精确算法和具有更高效率的近似算法，实验证实所提算法可以有效挖掘不确定图中存在概率较高的紧密子图。3.在挖掘不确定图中紧密子图的相关研究基础上，提出适用于无线传感器网络特点的紧密区域发现算法。该算法首先在无线传感器网络中分布式地构建逻辑网络并将该网络抽象为不确定图，然后应用计算量较小的剪枝策略对网络进行搜索，最终快速有效地发现网络中的紧密子区域，为无线传感器网中其他有关的算法和应用提供基础。

全文目录


中文摘要  3-4
Abstract  4-9
第1章 绪论  9-24
  1.1 课题背景  9-12
  1.2 国内外研究现状  12-22
    1.2.1 图查询算法研究  12-13
    1.2.2 频繁子图挖掘算法研究  13-16
    1.2.3 稠密子图挖掘算法研究  16
    1.2.4 无线传感器网中区域发现问题研究  16-17
    1.2.5 其他图挖掘问题  17-19
    1.2.6 不确定数据挖掘算法研究  19-22
  1.3 本文的主要研究工作  22-23
    1.3.1 主要研究内容  22-23
    1.3.2 主要研究成果  23
  1.4 本文章节安排  23-24
第2章 不确定图上极大频繁子图模式挖掘算法  24-41
  2.1 引言  24-26
  2.2 相关研究工作  26-27
  2.3 问题定义  27-30
  2.4 极大频繁子图挖掘算法  30-36
    2.4.1 预处理原始数据  30-31
    2.4.2 构建有效搜索空间 W_SAG  31-33
    2.4.3 有效获得 K-极大频繁子图模式  33-36
  2.5 实验结果  36-40
  2.6 小结  40-41
第3章 不确定图上的紧密子图挖掘算法  41-59
  3.1 引言  41-43
  3.2 相关工作  43-45
  3.3 问题定义  45-47
  3.4 挖掘紧密子图  47-53
    3.4.1 紧密子图存在概率的计算  48
    3.4.2 计算不确定图中最高期望紧密函数上界  48-49
    3.4.3 基于树搜索策略的 TreeClose 算法  49-51
    3.4.4 基于贪心思想的 GreedyClose 算法  51-53
  3.5 实验结果  53-58
    3.5.1 实验数据  53-55
    3.5.2 算法执行情况及结果分析  55-58
  3.6 小结  58-59
第4章 无线传感器网络中紧密子区域挖掘算法  59-73
  4.1 引言  59-62
  4.2 相关工作  62
  4.3 问题定义  62-63
  4.4 紧密子区域发现算法  63-68
    4.4.1 计算子区域的存在概率  63-64
    4.4.2 分布式构建不确定图  64-65
    4.4.3 确定紧密子区域阈值 T  65-66
    4.4.4 算法 K-CLOSE  66-68
  4.5 实验结果  68-72
    4.5.1 实验数据  68-71
    4.5.2 算法性能及结果分析  71-72
  4.6 小结  72-73
结论  73-75
参考文献  75-83
致谢  83-85
攻读硕士学位期间发表的学术论文  85

相似论文

  1. 基于无线传感器网络的电动汽车电池组综合测试技术研究,U469.72
  2. 频繁图结构并行挖掘算法的研究与实现,TP311.13
  3. 传感器网络中渐变事件监测研究,TP212.9
  4. 无线传感器网络中定位攻击检测技术研究,TP212.9
  5. 基于功能节点的无线传感器网络多对密钥管理协议研究,TP212.9
  6. 基于LEACH的安全建簇无线传感器网络路由协议研究,TP212.9
  7. 无线传感器网络组播路由协议研究,TN929.5
  8. 基于地理位置的WSNs路由算法研究与改进,TN929.5
  9. 基于ZigBee技术的无线传感器网络研究与实现,TN929.5
  10. 一种自适应选择处理节点的时空查询算法,TN929.5
  11. 无线传感器网络MAC协议的研究,TN915.04
  12. 无线传感器网络节点定位算法的研究,TN929.5
  13. 城市照明管理系统中的时间同步方法研究,TM923
  14. 随机路由在无线传感器网络中的研究与应用,TN929.5
  15. 基于无线传感器网络的煤矿瓦斯监测系统的研究,TN929.5
  16. 基于行为可信的无线传感器网络入侵检测技术的研究,TP212.9
  17. 基于区域的无线传感器网络密钥管理方案研究,TP212.9
  18. 基于zigbee的智能楼宇环境监测无线传感网络,TN929.5
  19. 基于无线传感器网络的农田环境监测系统路由协议的研究,TN915.04
  20. 面向信息物理系统的IEEE802.15.4MAC协议分析及优化,TP212.9
  21. 基于多层WSN结构的非均匀簇路由协议研究,TP212.9

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