交通数据的轨迹挖掘方法研究

朱 毅，祁雪婷，赵玉帅

（盐城工业职业技术学院，江苏 盐城 224000）

在轨迹聚类研究的发展历程中，对海量对象运动规律的发掘始终是重要的探讨课题之一。2005年，Kalni等[1]提出了基于一种密度的移动聚类思想，这种聚类思想主要可以被阐述如下：对于聚类中的每个数据点，给定范围（ε），在该范围中至少有一定数量（Minpts）的点。这类移动对象聚类模式也被Jeung等[2]称作Convoy模式。Convoy模式定义：K个连续时间段内存在超过某数目且共同移动的对象集合。本文中实验采用北京交通的数据集，此数据集主要由城市地图数据库、道路ID数据库、节点ID数据库以及轨迹数据库构成。

1 实验流程

本次实验基于数据总量庞大的特性，采用道格拉斯-普克算法（Douglas-Peucker）[3]对连续坐标进行测量，然后对相邻时间戳的数据进行了进一步填充以保证数据的平滑性。在对数据噪点清除和切分之后，本实验采用了3种聚类算法（MC1、MC2、CMC）对处理后的数据进行Convoy模式的聚类，并且对这3种聚类算法进行了效率、质量的对比[4]。

2 轨迹聚类算法实现

2.1 轨迹压缩

在轨迹压缩部分，本实验采用了时间同步欧氏距离（Time Synchronized Euclidian Distance）和DK算法来简化轨迹数据。时间同步欧氏距离能够从轨迹算法中产生近似轨迹[5]，而DK算法则能通过垂向距离对数据进行压缩[3]。本次实验基于这两种方法将测试数据中单个时间戳中缺失的数据进行了补全，然后通过DK算法对整体轨迹数据进行了压缩。即使数据经过算法进行了压缩，也需要对各个时段内所有坐标点进行统计之后才能聚类。为了提升聚类算法的性能，本次实验中采用了网格（Grid）数据结构[6]。网格数据结构将地图数据均分成若干小的网格并建立索引，单个网格的计算需要与其周围8个网格同步。

2.2 时间切片聚类过程

经过对轨迹数据进行预处理与压缩，我们得到了单个时间段内平滑的轨迹数据集。基于此数据集，本实验实现了基于DBSCAN算法的移动聚类算法（MC1、MC2、CMC）对数据进行聚类。MC1[1]算法对数据进行直接移动聚类，此算法的运行机制是：遍历所有时间切片，对单个时间切片进行DBSCAN聚类后，对所有时间切片进行移动聚类集合的创建，要求移动聚类集合中相同的单个数据点至少在一段时间内持续存在于该集合中。

本实验中实施的另一种算法是MC2[1]，本算法在MC1算法的基础上对移动聚类进行并集的创建和数据的连接。该算法指定聚类移动的扩展条件并对两个移动聚类之间进行相似性检查。当两个连续的时间戳具有较大或相等的阈值百分比时，该聚类可以被认为是有效的移动聚类。阈值的定义为，式中，Ct和Ct-1代表时间戳在t和t-1的聚类。

为了与MC2算法进行比较，本实验实现了另一种基于相似性检查的聚类算法，称为CMC[2]。该算法使用不同时间戳聚类之间的交集数量代替阈值θ作为验证条件，并将验证周期扩大到k个时间戳，以增强输出的特征。这种算法对移动聚类的生命周期处理类似于MC2，但判定条件改为|Ct∩Ct-1|≥m，即两个连续时间戳中交叉点数量需要大于m个，并且持续k个时间戳。

3 轨迹聚类算法比较与分析

3.1 算法效率对比

（1）距离计算方式选择：由于单个时间切片的聚类需要进行地图中坐标点与坐标点之间的距离计算，并且数据中也提供了整个城市的节点ID和链接位置。我们基于这些节点ID构建了一个有向加权图，并且使用迪杰斯特拉算法、基于Grid结构优化的迪杰斯特拉算法以及时间同步欧氏距离算法对节点进行了路径计算。实验显示，Dijkstra算法运行时间远超欧式距离算法，因此本次实验中采用欧氏距离算法为计算距离的唯一算法。

（2）空间数据结构效率对比：对于空间结构数据的使用，为了验证Grid结构是否适合轨迹数据挖掘。该实验采用MC1进行了使用Grid结构和不使用Grid结构之间的对比，通过时间戳来进行结构算法的时间复杂度计算。实验表明，当数据量提升至巨量水准时，使用Grid结构插入与搜索的时间复杂度远好于不使用Grid结构。

（3）移动聚类算法效率对比：本次实验对移动聚类算法MC1、MC2和CMC的算法效率进行了分析，以上述算法在整个聚类过程中随着时间切片数量上升产生的时间成本作为效率参考。DBSCAN算法的参数：范围（ε）=400、最小数量（MinPts）=5。移动聚类算法参数：MC1阈值θ=0.5、MC2阈值θ=0.333、CMC交叉点个数m=3。实验结果表明，3种移动聚类在算法时间成本上效率相近，CMC算法效率略好于其余两种算法。

图1 聚类算法的时间复杂度对比

3.2 算法实现成果

为对比不同轨迹精度和聚类算法精度，实验抽取更有代表性的特征时间戳用于聚类展示。首次进行切片的时间是3月1日中午12时的交通数据，采用此时间段的原因是午间交通流量高。数据经过移动聚类得到如图2所示结果，地图背景以网格形式展示。

图2 MC1（左）MC2（中）CMC（右）的聚类结果

由以上3幅图像上的点所构成的簇就是算法获得的移动聚类，本实验在3幅聚类图像的基础上，通过观察随时间戳不断运动的结果生成图像来观察数据聚类情况。就观察聚类生成的范围与精度，MC2是三种算法中适用情况最广的一类。而CMC算法则更适合需求高精度移动聚类的实验需求，如婚礼车队、游行等情况。因此根据获得的移动聚类图像，本实验总结如下：①MC1、MC2、CMC的算法的准确性存在差异，且由于算法中确定阈值，在阈值较高时MC2和CMC会有一些没有被识别为移动聚类的点聚类。②对于通用的情况，MC2能较好地分割出有更大范围的簇；而对于数据稀疏的情况，MC1能更方便轻易地将其分割成若干更小的簇。③CMC聚类算法的精度较高，但它定义的聚类数目比MC1和MC2要少。

3.3 算法参数对算法效果的影响

3.3.1 半径Radius与聚类密度指标Minpts的影响

基于算法效率以及准确性，本实验选取MC2算法作为参考对象，更改半径（Radius）并观察结果。我们检验了两个极值，即改变半径值为非常大（1 000米）和非常小（100米）来观察结果。通过检验，得出以下结论：①在半径仅为100米的情况下，即使轨迹总数非常大，也只能确定非常小数量的移动聚类。但是当轨迹总数量很大时，仅能识别出少量移动聚类。显然，这样做效果欠佳。②若半径值太大，则大部分轨迹点都会归为一个大的聚类。这样就会造成聚类效果变差。

在本次试验中，我们发现Minpts个数对对比之后的效果也有一定的影响。但由于此参数造成的影响在密集的轨迹数据中对聚类结果影响并不明显。所以本实验减少半径参数到100米并观察。结果表明Minpts个数的增加会使算法聚类得更严格，也会使得聚类被定义得更少。

3.3.2 聚类判断阈值影响

由于MC2的移动聚类验证机制与CMC不同，本实验采用这两种算法进行聚类判断阈值影响的验证。

（1）MC2的实验：本实验首先根据公式对阈值θ进行了调整，其取值范围为0.5～0.8。经实验表明，提高算法阈值θ对结果没有很大的影响。当改变量不大时，算法得出的聚类个数与结果几乎相同，并且当θ值增加到一定的阈值时聚类结果会收敛，实验中得出的聚类内部点个数也会非常少，算法的可用性就会降低。

（2）CMC的实验：基于前面给出的阈值判定公式|Ct∩Ct-1|≥m，我们可以通过更改m值的大小来操纵阈值。本实验观察了CMC算法在m=3以及m=5的状态下，移动聚类生成的精度与数量。实验表明：m与聚类大小成正相关，且会导致聚类精度降低。选择m值对于CMC算法的可用性影响较大，需要谨慎判断。

4 结束语

本实验采用一系列算法对北京交通轨迹数据进行处理，对轨迹聚类进行了实现与分析。实现了以MC1、MC2和CMC为算法的移动聚类，并对其进行比较。总之，该实验许多方法在多数场景下适用性不强，本次实验的算法较为同质化，可发掘更具有前瞻性的聚类模式。■