一种高效且可扩展的非聚类方法，用于检测大规模公交车轨迹中的协同运动模式

《Future Generation Computer Systems》：An efficient and scalable non-clustering approach for detecting co-movement patterns in large-scale bus trajectories

　　卢荣荣|熊文|罗超|王晓轩
云南师范大学信息科学与技术学院，昆明，650500，中国

**摘要**
检测城市车辆之间的共移动模式对于时空分析应用至关重要，例如识别公交车群集行为。然而，现有的基于轨迹聚类的方法存在两个主要限制：高计算复杂性和在处理大规模GPS数据集时的有限可扩展性。为了克服这些挑战，我们提出了一种高效且可扩展的非聚类方法，用于检测大规模公交运输系统中的共移动模式。我们的方法引入了一种轻量级检测算法，由三个关键组件组成：空间投影函数、混合索引和过滤-细化框架。具体来说，我们首先设计了一个距离投影函数，将3D GPS轨迹映射到2D空间中。然后使用时间窗口对轨迹进行分割，并使用结合方向角和最小边界矩形（MBR）的混合索引对轨迹进行组织，从而实现高效的空间遍历。最后，采用过滤-细化框架来加速检测过程。该解决方案在Apache Spark平台上实现，关键步骤无缝集成到分布式数据处理流程中。我们使用一个包含7350万条GPS记录的大规模真实世界数据集来评估我们的方法，这些记录来自10,708辆公交车在一天内的数据。在整个数据集上，我们的解决方案仅用597.14秒就检测到了共移动模式。此外，比较结果显示，与基于R树的解决方案相比，我们的方法运行时间提高了2.6倍，而与ST-DBSCAN相比则提高了3.8倍，同时保持了良好的可扩展性。

**引言**
在现代城市中，数以万计的公交车是城市公共交通的重要组成部分，与地铁和出租车系统并存。由于开放的道路网络和广泛的空间覆盖范围，管理公交车比管理地铁系统更具挑战性。一个关键的运营问题是公交车群集，即同一条路线上的多辆公交车同时到达一个站点，导致车头时距过近或重叠。这个问题在高峰时段尤为突出，其原因包括上车时间不均匀、交通信号和拥堵。公交车群集会扰乱乘客的等待时间预期，降低出行满意度，降低运营效率，并增加成本。快速有效地检测公交车群集对于提高服务质量至关重要。

公交车群集的检测依赖于挖掘移动对象之间的共移动模式。现有方法可以分为三类：基于车头时距间隔的方法[1]、[2]、基于规则和阈值的方法[3]、[4]以及基于轨迹聚类的方法[5]、[6]。第一类方法通过计算连续公交车在站点之间的时间间隔来检测瞬时共移动事件。虽然适用于小规模数据集，但无法捕捉空间分布的共移动事件。第二类方法使用预定义的时间或距离阈值来识别共移动事件。尽管简单，但它们不够灵活，无法检测事件的持续时间。第三类方法利用聚类技术来检测复杂的共移动模式。然而，基于聚类的方法在检测共移动模式时存在两个主要限制：高计算成本和有限的检测精度。

一方面，轨迹聚类方法通常具有高时间复杂性和大量的资源消耗。在大规模的历史GPS轨迹场景中，它们的计算效率和系统成本往往无法满足实际应用的需求，这促使人们需要更轻量级和可扩展的检测算法。另一方面，尽管聚类方法产生的轨迹簇可能包含共移动模式，但仅靠聚类不足以直接描述细粒度的语义信息，如具体的参与对象及其对应的开始和结束时间。提取此类信息需要额外的后处理步骤，包括轨迹分割、时间对齐和详细比较，这会引入进一步的计算开销和系统复杂性。为了解决这些问题，一些研究探索了基于采样的轻量级共移动模式检测方法[7]。虽然这些方法显著提高了计算效率，但其检测结果往往存在不可忽视的误差。此外，基于点的聚类策略在保证检测精度方面存在固有的局限性。在现实世界的交通场景中，车辆之间的GPS采样通常是异步的；并非所有车辆都在同一时间生成位置记录，导致一些轨迹点被排除在聚类过程之外，从而削弱了检测结果的可靠性。

更严重的是，现有方法是为小规模、单节点解决方案设计的，无法处理大城市的庞大GPS数据集。例如，截至2019年10月，深圳的公交系统包括1831条路线、10,708辆公交车和超过6000公里的覆盖范围。每辆公交车每天生成12小时的GPS记录，每月产生超过11亿条记录。在大规模数据中高效检测共移动模式面临两个主要挑战：高计算复杂性和有限的可扩展性。首先，必须最小化基于聚类的方法的计算复杂性以实现及时模式检测。其次，必须采用大数据技术来处理庞大的GPS数据集，克服单节点解决方案的局限性，并实现高效的并行处理。

为了解决上述挑战，我们提出了一种高效且可扩展的非聚类方法，用于检测大规模公交运输系统中的共移动模式。所有源代码和样本数据集可以从GitHub下载。

**算法细节**
首先，我们设计了一种轻量级的非聚类检测算法，显著降低了计算开销。然后，该算法在Apache Spark平台上进行了并行化实现，其关键步骤被高效集成到数据处理流程中，以提高可扩展性和处理性能。该解决方案包括四个关键步骤：
(1) 空间距离投影，这是一种特殊的距离投影函数，将纬度和经度投影到一维距离度量中。使用此函数，三维（3D）GPS轨迹被投影到二维（2D）空间中；
(2) 空间划分和索引，将2D空间划分为窗口，并使用考虑方向的MBR索引（OA-MBR）根据轨迹的方向角和空间范围组织每个窗口内的轨迹段；
(3) 轨迹段过滤，通过比较方向角并检查MBR交集，有效过滤掉不相关的轨迹对，显著减少计算负载；
(4) 实现和可扩展性，在Spark上对算法进行并行化，确保大规模GPS轨迹数据集的高效率和可扩展性。

基于这些关键步骤，我们的算法只需遍历一次OA-MBR索引即可生成一组初始的共移动候选对象。因此，算法的整体性能接近线性时间复杂度O(kn)，其中k表示共移动发生的次数，n表示移动对象的数量。这显著低于基于聚类的方法（如ST-DBSCAN）的O(n2)时间复杂度。我们的方法通过四个关键创新解决了计算和可扩展性挑战。具体来说，我们的贡献可以总结如下：
- **空间投影函数**：为了适应公交系统的固定路线特性，我们定义了一个称为标准化距离的网络约束度量，它表示车辆沿路线的相对位置，作为行驶网络距离与总路线长度的比率，归一化到[0,1]之间。基于此度量，我们设计了一个空间投影函数，将三维GPS轨迹映射到二维空间中，同时保持轨迹顺序和空间结构，降低了后续的计算复杂性。
- **非聚类-based共移动检测**：我们提出了一种高效的基于非聚类的共移动检测方法，以避免大规模场景中轨迹聚类的高计算成本。该方法整合了三个组件：空间映射函数、考虑方向的OA-MBR混合索引和过滤-细化框架。在投影空间中，使用方向角和最小边界矩形（MBR）组织轨迹段，通过单次索引遍历即可消除大量无效的候选对，大幅加速共移动检测。
- **可扩展的流程实现**：我们在Apache Spark平台上实现了所提出的方法，以支持大规模历史GPS轨迹数据集的高效处理。核心算法阶段——包括空间映射、窗口划分、混合索引构建、过滤-细化处理和结果聚合——被无缝集成到一个统一的自动化处理流程中。这种设计确保了在现实世界大数据环境中的强可扩展性和实际部署能力。我们在包含7350万条GPS点的真实世界数据集上验证了我们的方法。实验结果表明，所提出的解决方案分别比R-tree和ST-DBSCAN基线提高了2.6倍和3.8倍的性能。

**本文结构**
第2节回顾相关工作。第3节介绍问题定义。第4节详细说明所提出的算法。第5节通过实验评估所提算法的性能。第6节总结本文。

**相关工作**
一方面，在城市交通系统中，从车辆GPS轨迹中挖掘共移动模式已被广泛用于支持各种智能应用，包括交通流量预测、城市物流和配送优化。另一方面，人们也投入了大量努力开发用于处理大规模GPS轨迹的可扩展数据处理技术，如轨迹相似性搜索和相似性连接。因此，我们从两个方面回顾了相关工作。

**问题定义**
为了使描述更清晰易懂，我们将在以下部分提供相关定义、概念和表达式的详细解释。

**定义1 地理坐标**
地理坐标表示为一个包含两个属性的元组：经度和纬度。表示如下：w=(lon, lat)

**定义2 道路段**
道路段是一组有序的地理坐标，代表城市道路网络的基本元素。表示如下：r={w1, w2, w3, …, wn}

**数据采集**
本研究中使用的GPS数据集来自深圳市的公交运输系统。它包括960条公交路线、10,708辆公交车，覆盖面积为2000平方公里。数据集包含10,708辆公交车在一天内的GPS记录，总计7350万条记录，大小为8.4 GB。公交车上的GPS设备通过无线互联网持续生成并传输实时位置数据到后端存储系统。然而，传感器错误可能会导致异常值和重复记录的出现。

**实验结果与分析**
为了全面评估所提算法和解决方案的性能，本节从以下五个角度提供了详细的比较实验和分析：
- 我们通过改变时间窗口大小和倾斜角阈值进行了参数敏感性分析，并评估了它们对运行时间和检测精度的影响。
- 我们将所提出的OA-MBR与代表性的最先进方法进行了比较，包括基于R树的非聚类方法。

**结论**
为了解决大规模时空场景中检测公交车群集的挑战，我们提出了一种快速检测共移动模式的算法，适用于大规模公交运输系统。我们的方法包括四个步骤：
(1) 一种新颖的空间距离投影函数，将3D GPS轨迹映射到2D空间中，降低维度复杂性；
(2) 将2D空间划分为窗口，并使用方向角和最小边界矩形（MBR）构建OA-MBR索引。

**作者贡献声明**
卢荣荣：撰写——原始草稿、可视化、验证、软件。
熊文：撰写——审阅与编辑、方法论、研究、资金获取、数据管理、概念化。
罗超：可视化、验证。
王晓轩：验证、项目管理、资金获取。

**利益冲突声明**
作者声明他们没有已知的财务利益或个人关系可能影响本文报告的工作。