轨迹聚类算法及其应用

曹鑫磊 冯锋

摘要：为了提高交通工具的利用率，通过获取轨迹数据使移动点对象轨迹聚类分析在保证反映其相互之间正确的空间关系、时态关系、运动关系的基础上，提出合理有效的相似性度量公式的结果。欧氏距离与设定的阈值a用于判定两点之间是否处于同一位置，转换为计算轨迹最长公共子序列问题求得相似度并作为最大生成树聚类的权值。经过轨迹聚类分析，得到聚类结果。

关键词：轨迹；最大生成树聚类；相似性度量；轨迹聚类分析

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2018）29-0009-03

Abstract： In order to improve the utilization rate of vehicles， the trajectory data is obtained to make the moving point object trajectory clustering analysis to propose a reasonable and effective similarity metric formula on the basis of ensuring the correct spatial relationship， temporal relationship and motion relationship. the result of. The Euclidean distance and the set threshold a are used to determine whether the two points are in the same position， and are converted to the longest common subsequence of the calculated trajectory to obtain the similarity and as the weight of the maximum spanning tree cluster. After trajectory clustering analysis， the clustering results are obtained.

Key words： Trajectory；maximum spanning tree clustering；similarity measure；trajectory clustering analysis

近年来，交通拥堵的问题越来越严重，合理的引导民众选择合理的交通出行方式已经成为政府部门的责任。为此政府在大量的公共交通方式上安装了GPS卫星定位、北斗卫星定位等设备。因此在极短的时间内就积聚了海量的空间数据。伴随着GPS、北斗等一系列的定位技术上的不断成熟，能够轻松地获取到城镇居民选取出行活动的各种轨迹数据。为了达到能够了解城镇居民出行情况的目的，为了解决交通拥堵的问题，诸如GPS、北斗卫星等等的定位设备被有关部门越来越多的安装在新型出租工具上。城镇居民决定新型出租工具行驶的起点和终点，新型出租工具的运行轨迹能够很好地反映城镇居民出行特点。GPS、北斗卫星轨迹具有数据易获取、分布范围地域广阔、数据量特别巨大等特点，所以，GPS轨迹数据能够成为城镇居民出行方式分析的极佳数据来源。通过对这些GPS设备的信息采集，生成的大量的新型出租工具轨迹数据。明确新型出租工具轨迹数据中的大量信息才能够分析城镇居民的出行信息，才能够达到优化交通、改善路况的目的。

1 相关研究

分布式计算方法目前已成为大数据处理可行的办法之一，此方法需要结合批量计算技术。因此，这次课程设计针对轨迹大数据将轨迹聚类，Li和Zheng在早年间就提出了一种基于密度的轨迹聚类算法TRACLUS，TRACLUS首先划分轨迹，再将轨迹段进行聚类，

分析结果找出聚集的子线段簇。TRACLUS虽然是基于密度的轨迹聚类算法，结果可以显示为任意轨迹簇，但是也有只考虑轨迹数据中空间信息而忽略时间信息得不足。

軌迹聚类分析属于无监督的一种学习方法，通过数据探索，给出数据描述，在其他方面还可以用于数据预测和内容检索等等。数据挖掘中研究极广的课题之一包含聚类分析，聚类分析技术经常用在语音识别、字符识别[1]等新型应用上，将聚类分析技术按照不同的类别划分：在图像处理[2]方面，代表有Photoshop、美图、滤镜等，聚类主要用于数据的压缩和信息的检索，聚类过程需要把用户拍好的照片中的像素点存入缓存器中；在机器学习方面，代表有机器人、人工智能产品，聚类主要的算法应用在图像分割和机器视觉上。经过多年的发展聚类研究已经深入到统计科学的领域。值得一提的是，聚类分析通过大数据研究也用在心理学、地质学、考古学、生物学、地理学以及市场营销等领域。

2 聚类算法

2.1 欧几里得距离

欧几里得距离无论在理学中还是工学中都是最常用的计算距离的公式，特别适用于数据量巨大且很密集的时候。

2.2 基于动态规划的度量方法

动态规划是求解最优化问题的一种途径、一种方法。动态规划并不是算法，是因为它没有指定的数学表达式，没有像其他算法那样清晰的解题步骤，因此动态规划程序设计只能根据各种问题的性质结合求此问题最优解的条件，产生对此问题特定的解题方法。

2.2.1 基本模型

1） 首先要明确问题是什么，找出决策对象，进行下一步确认；

2） 根据问题所属类型，对此类决策过程划分成不同阶段；

3） 根据问题所属类型，设置问题所需变量并分发到各阶段；

4） 根据状态变量确定费用函数和目标函数；

5） 根据问题所属类型，建立此类问题各阶段的状态变量，通过变量确定状态转移方程。