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

道路网络空间中移动对象轨迹聚类算法的研究

作　者: 王雅琳
导　师: 韩启龙
学　校: 哈尔滨工程大学
专　业: 计算机系统结构
关键词: 时空数据挖掘 轨迹聚类 增量聚类 轨迹距离 DBSCAN算法
分类号: TP311.13
类　型: 硕士论文
年　份: 2011年
下　载: 31次
引　用: 0次
阅　读: 论文下载
 

内容摘要


近年来,随着定位技术、传感器技术及跟踪监测设备的发展和普及,人们可以容易地对移动物体进行跟踪,并将它们的运动轨迹记录下来。运动对象的轨迹数据中包含大量有用的信息,采用数据挖掘技术对获取到的轨迹信息进行分析处理,可以发现数据中隐藏的关系和规则,并对移动对象未来的运动情况进行预测等。本文研究的目标就是对道路网络空间中的移动对象的轨迹进行分析和挖掘,聚类相似轨迹得到移动对象的运动特征和模式,为路径规划和智能导航等服务提供依据。移动对象在道路网络中连续运动,将随时间持续地产生轨迹,而对轨迹的聚类请求却可能发生在任意时间,每次请求时路网中的轨迹都发生了变化。传统的聚类方法处理的都是静态的数据集,而用于动态的轨迹聚类时,每次都要把所有轨迹重新处理一次,包括已经处理过的轨迹段,会浪费很多不必要的开销。本文正是基于以上提出的问题,对现有方法进行分析和总结,提出了以下方法对移动对象轨迹数据进行聚类：首先,提出了一种基于道路网络空间的移动对象轨迹的表示方法。以离散的点的方式表示一条轨迹,记录了在某时刻移动对象在路网上的真实位置信息,而且包括对象经过每点时的速度,能反映出移动对象在路网上位置变化的真实情况；其次,考虑轨迹的时空特性对轨迹间距离进行计算。在分析和总结了现有的轨迹距离函数和轨迹相似性度量计算方法的基础上,本文采用平均值的Hausdorff距离进行轨迹空间距离的计算,对于轨迹上的两点计算其网络距离而不使用欧氏距离,然后用时间距离对轨迹进行提纯,从而得到轨迹的时空距离作为聚类的依据：第三,提出了一种轨迹的增量聚类算法INC_CLUS进行轨迹聚类。采用基于密度的聚类方法,首先在初始时刻对现有轨迹进行初始聚类,得到一组初始聚类簇,然后对新增加的或发生变化的轨迹进行增量聚类,更新初始聚类簇得到最终的聚类结果,同时由于考虑了轨迹的时间信息,可以区分出不同时间段内的相似轨迹；最后,通过实验对哈尔滨市区的一块路网区域进行了分析存储,并模拟了一组移动对象在真实的道路网络空间中运动的轨迹数据,对其使用本文提出的增量轨迹聚类算法进行聚类,并与原始的DBSCAN算法进行比较,从聚类结果和运行时间的性能评估方面验证了所提INC_CLUS算法的正确性和有效性。

全文目录


摘要  5-6
Abstract  6-10
第1章 绪论  10-19
  1.1 研究背景和意义  10-11
  1.2 国内外研究现状  11-15
    1.2.1 移动对象轨迹建模  11-12
    1.2.2 轨迹距离函数  12-14
    1.2.3 轨迹聚类算法  14-15
  1.3 存在的问题  15-17
  1.4 研究内容  17-18
  1.5 论文的组织  18-19
第2章 时空数据挖掘相关技术  19-32
  2.1 时空数据库  19-23
    2.1.1 时空数据的建模  19-20
    2.1.2 时空数据库的索引  20-21
    2.1.3 时空数据库的查询  21-22
    2.1.4 时空移动对象概述  22-23
  2.2 时空数据挖掘  23-26
    2.2.1 时空数据挖掘的任务和技术  23-24
    2.2.2 时空数据挖掘的过程  24-26
    2.2.3 时空数据挖掘的特殊性  26
  2.3 轨迹数据挖掘  26-31
    2.3.1 移动对象轨迹的描述  26-28
    2.3.2 轨迹的查询及更新  28-30
    2.3.3 轨迹聚类  30-31
  2.4 本章小结  31-32
第3章 移动对象轨迹模型  32-40
  3.1 移动对象轨迹数据模型  32-34
  3.2 移动对象轨迹距离  34-39
    3.2.1 空间距离  35-38
    3.2.2 时间距离  38-39
    3.2.3 时空距离  39
  3.3 本章小结  39-40
第4章 移动对象轨迹聚类算法  40-54
  4.1 移动对象轨迹聚类算法的基本框架  40-41
  4.2 轨迹转化算法  41-43
  4.3 移动对象轨迹初始聚类算法  43-47
    4.3.1 聚类算法的选取  43-45
    4.3.2 初始聚类  45-47
  4.4 增量聚类  47-53
    4.4.1 从聚类簇中提取代表轨迹  49-50
    4.4.2 聚类新增加的轨迹  50-51
    4.4.3 聚类发生变化的轨迹  51-52
    4.4.4 执行效率分析  52-53
  4.5 本章小结  53-54
第5章 实验与结果分析  54-61
  5.1 实验环境  54-56
    5.1.1 实验背景  54-56
    5.1.2 软件环境  56
  5.2 算法分析  56-60
    5.2.1 参数的选择  56-57
    5.2.2 聚类效果  57-59
    5.2.3 算法运行时间  59-60
  5.3 本章小结  60-61
结论  61-62
参考文献  62-66
攻读硕士学位期间发表的论文和取得的研究成果  66-67
致谢  67

相似论文

  1. 基于聚类分析的网络流量分类研究,TP393.06
  2. 关于运动对象轨迹的分割与聚类算法研究,TP311.13
  3. 数字遥感图像解译分类方法研究,TP751
  4. 增量文本聚类在舆情监控中的研究与实现,TP391.1
  5. 基于监测信号加权特征的批量钻削工步质量增量聚类研究,TG52
  6. 三维模型分割及检索的方法研究,TP391.41
  7. 基于web文献的数据挖掘研究应用,TP311.13
  8. FCM聚类及其增量算法的研究,TP311.13
  9. 空间数据聚类分析算法研究及实现,P208
  10. 基于数据挖掘的入侵检测系统的研究与实现,TP311.13
  11. 基于聚类的入侵检测算法研究与实现,TP393.08
  12. 聚类算法及其在页面聚类中的应用研究,TP301.6
  13. 聚类算法在入侵检测中的应用,TP393.08
  14. 增量聚类算法的设计与实现,TP301.6
  15. 基于时空约束的轨迹聚类方法研究与应用,TP18
  16. 完备/不完备信息系统的若干知识约简算法的研究,TP182
  17. 金融数据挖掘中的增量聚类算法及应用研究,TP311.13
  18. 面向移动环境的时空数据挖掘研究,TP311.13
  19. 基于Web使用挖掘的个性化推荐系统研究与设计,TP311.52
  20. 时空数据模型的建模研究与应用,TP311.5

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