基于时空模式的轨迹数据聚类方法研究

摘要

近年来随着移动定位服务和云计算技术的快速发展，搜集和处理移动定位信息变得越来越容易，导致移动定位数据呈爆炸式增长。为了从海量移动定位数据中获取有用信息，许多学者利用当前可获取的移动定位数据展开了研究。时空轨迹数据的聚类算法是其中一项关键研究内容，然而现有的时空轨迹聚类算法中，相似性度量函数多以空间特征为主要度量标准，缺少对时间特征的考虑，从而影响了最终聚类结果的质量。针对这一问题，本文对时空模式下轨迹数据的聚类算法进行了认真的研究，主要研究内容如下： 首先，针对多数时空轨迹聚类算法没有考虑时间特征的问题，提出一种基于时空模式的轨迹数据聚类算法。该算法以划分再聚类框架为基础，先利用曲线边缘检测方法对原轨迹进行子轨迹段划分，然后对生成的子轨迹段集采用基于密度的聚类算法完成聚类，聚类时子轨迹段之间采用空间加时间的相似性度量方法。实验结果表明，所提方法较好地兼顾了轨迹的空间与时间特征，明显提高了聚类质量，使得聚类结果更具有实际应用价值。 其次，为了更好地划分轨迹段，将图像处理中的曲线边缘检测方法应用到轨迹段划分中，通过计算时空轨迹中某一样本点与该点附近轨迹段的变化趋势来判定该点是否为时空轨迹的特征点，以此得到轨迹的粗略特征。实验结果表明该方法在保持原轨迹精确性和子轨迹段简洁性之间找到较好的平衡。 最后，为了提高聚类结果的质量，提出了一种可以度量不等长时间序列距离的方法，该方法通过将较短时间序列向较长时间序列进行投影，将两条时间序列的最近距离作为两条子轨迹段的时间距离。最后通过设置距离权重w以调整时空特征的敏感性。实验结果表明该方法提高了时空轨迹相似性度量的精度，使得聚类簇中的轨迹段同时具有较高的空间及时间相似性。

目录

声明

第一章 绪论

1.1研究背景与意义

1.2国内外研究现状

1.2.1国外研究动态分析

1.2.2国内研究动态分析

1.2.3存在的问题

1.3本文主要研究工作

1.4本文组织结构

第二章 时空轨迹数据聚类理论基础

2.1时空轨迹数据

2.1.1时空轨迹数据定义

2.1.2建立时空轨迹数据模型

2.1.3时空轨迹数据的表达

2.2时空轨迹的相似性度量

2.2.1欧几里得距离

2.2.2 Hausdorff 距离

2.2.3动态时间调整距离

2.2.4最长公共子序列距离

2.2.5 Fréchet距离

2.3时空轨迹数据聚类算法

2.3.1基于全区间相似的时空轨迹聚类算法

2.3.2基于子区间相似的时空轨迹聚类算法

第三章 改进的时空轨迹数据聚类算法

3.1轨迹段划分

3.1.1轨迹相关定义

3.1.2轨迹上特征点的判定

3.1.3生成子轨迹段

3.2子轨迹段相似性度量

3.2.1空间相似性度量

3.2.2时间相似性度量

3.2.3时空相似性度量

3.3时空轨迹聚类算法

3.3.1基于密度的聚类算法

3.3.2 DBSCAN聚类相关定义

3.3.3时空轨迹聚类算法

3.3.4算法复杂度分析

3.4本章小结

第四章 实验分析

4.1实验准备

4.1.1数据选择

4.1.2实验内容

4.1.3算法评价指标

4.2参数设置

4.2.1转角阈值的设置

4.2.2距离权重的设置

4.3轨迹段划分

4.4聚类结果分析

4.5本章小结

第五章 结论

5.1研究工作总结

5.2研究工作展望

参考文献

攻读学位期间取得的相关科研成果

致谢