论文 | 从商用车队的 GPS 数据中归类车辆停留意图信息

原文：Stop purpose classification from GPS data of commercial vehicle fleets
作者：Sarti L, Bravi L, Sambo F.
来源：Data Mining Workshops, 2017 IEEE International Conference on. IEEE, 2017: 280-287.
转载：简书不支持公式渲染，便于阅读可参考 原博文。

摘要

从原始 GPS (全球定位系统) 数据中提取 汽车停靠意图数据 是大多数位置感知应用程序中的关键任务，且随着从移动设备收集 GPS 数据的不断增长，这项任务变得越来越有趣。近期很多研究都集中在行人 (手机) 数据上 (可理解为红海市场)，而商用车领域几乎没有探索 (蓝海市场)。

在本论文中，针对车辆 GPS 数据的汽车停靠意图的 识别 和 分类 问题 (利用来自不同行业的商业车队的大型异构数据集)。按照意图分类，旨在把汽车停靠点分为：工作相关 和 非工作相关。

对于每个汽车停靠点，要计算一组含 100 个不同特征的集合 (特征可分为四个主要类别：汽车停靠点特征，兴趣点特征，汽车停靠点集群特征和序列特征)，并通过随机森林分类模型，评估四组中每个特征对停靠点的相对重要性。

实验结果表明，本论文的方法显着地超越了现有商业车辆背景下用于汽车停靠意图的分类模型。

正文

引入

在过去的十年中，GPS 设备的巨大推广，使得人们越发关注 数据挖掘算法 在 时空数据 (GPS 产生的数据) 中的应用。而许多实际应用需要使用关于用户行为和地理位置的语义信息。例如，下述的两个实例：基于用户的历史位置以衡量用户之间的相似度 $^{[1]}$； 基于位置的兴趣地点推荐系统 $^{[2]}$。

语义标记 GPS 数据，目标旨在 识别 和 归类 GPS 沿途轨迹上的位置信息，即具体工作有 语义位置的侦察 和 汽车停靠或出游的意图识别。既管上述问题不是同一类型的问题，但却是强相关的。例如，对多个用户而言具有相同意图的共同定位点，可能是语义上相关联的地方 (反之亦然)，因为知道某个地方的语义对分类每个汽车停靠点意图有很大的帮助。

通常，对于上述问题的解决方法分两个阶段执行：

• 侦查兴趣地点：通常以非监督的方式实现位置侦查 $^{[3,4]}$，而作者提出了基于 DBSCAN $^{[5,or,6]}$ 的修改版本的聚类算法，即利用层次聚类从汽车停靠位置中提取访问点。

  当要处理非常大的数据集时需要考虑计算性能的问题，可参考其他论文中的扩展方法，例如对地点坐标进行哈希散列法 $^{[7,8]}$。

• 对侦查到的地点分类：对有关地点或汽车停靠点进行分类，可以在文献中找到两种主要方法：

  • 基于规则的系统 $^{[9,10]}$，其主要依赖于活动的位置、土地利用的数据以及机器学习方法，即活动本身提取特征；

  • 利用 SVM 分类器来区分标识位置内的活动停靠点和非活动停靠点。分类器 (SVM，随机森林或逻辑回归) 利用时间和空间特征 $^{[6]}$，以及隐马尔可夫模型 (HMM) 利用时序特征把这些汽车停靠点分类为预定义类型。

    1. SVM 提取三个主要特征：停车驻留时间，每个汽车停靠地段周围的点到质心的平均距离。
    2. 地点的语义分类是基于GPS数据和卫星图像的组合而定的 $^{[8]}$。

最后说明，本论文解决了与参考文献 [7] 的同样问题，即利用四个不同的特征集，使用一个随机森林分类器，对商业车队的汽车停靠意图数据进行分类。且本文的主要贡献如下：

• 描述了一种方法，即从 GPS Pings (GPS 定位仪) 中提取汽车停靠点信息，并从工作状态停车点一览表 (已知的地点信息) 中給它们分配地面实况标签 (贴标签);
• 基于带标签的数据集，建立了一个模型，可以自动分类汽车停靠点，即工作状态和非工作状态的停靠点;
• 提供了严格评估的多类型特征集，便于我们处理不同问题，其中包括：
  • 汽车停靠点特征 (Stop-wise features，SWF)；
  • 兴趣点特征 (Points of interest features，POIF)；
  • 停靠点集群特征 (Stop Cluster，CF)；
  • 序列特征 (Sequential features，SeqF).

方法

GPS和工单数据

• 本论文采用的数据集由 Fleetmatics 公司 (车队情报公司) 提供。
• 采集的数据有两种类型，分别是原始 GPS pings 数据 和 工单数据。
  • 原始 GPS Pings 数据
    • 提供有关车辆位置的信息，工单状态的信息，有关司机执行的工作进度及进度信息；
    • 设定有一系列的 GPS Pings ${P_i}_{i=1}^n = {P_1, ..., P_n}$ 分别描述每辆车行驶的路线。
    • 每一个 GPS Ping $P_i$ 包含每辆车的状态信息，即有车辆 ID $v_i$，经度和纬度 (位置信息 $p_i$)，里程表 $d_i$，时间戳 $t_i$ 和 事件代码 $e_i$。
  • 工单数据
    • 设定有一系列的工单 ${W_i}_{i=1}^n = {W_1, ..., W_n}$。
    • 每一个工单包含的信息有：车辆 ID $v_i$，经度和纬度 (位置 $p_i$)，时间戳 $t_i$ 和 状态代码 $c_i$ (例如：挂起，启动，完成)。

车辆停靠侦查技术

正如上述所描述的，关于瞬时车辆位置的原始数据是由 GPS Ping 组成的，将它们汇集起来以描述车辆的活动。为此本论文开发了一个 时空聚类程序。

• 首先得为每个 GPS 信息分配一种状态类型 (Engine off，iDling，Journey)，然后把它们聚集成 GPS Ping 群组，并把这个 GPS Ping 群组称为 汽车停靠点集。

• GPS Ping 的状态可分为三种类型：

  • Engine Off (发动机关闭状态)：发动机关闭事件。即这些 Ping 在发动机关闭的瞬间产生的 (当发动机处于关闭状态时不发送 Ping);
  • iDling (空转/怠速状态)：发动机处于开启状态，但车辆静止或车辆在小区域内仍然缓慢行驶。对于后者，我们还需要作一些约束，设定 $H(p_i,p_{i-1})$ 表示两点间的半正定距离。然后，对于给定车辆给予一对连续的 Ping $P_{i-1},and,P_i$，且满足以下约束，则可定义为怠速：
    • $s_i = H(p_i,p_{i-1}),/,(t_i - t_{i-1}) \leq 1.4,m/s,(5km/h)$，确定速度接近零；
    • $H(p_i,p_{i-1}) \leq 150,m$，确保 $P_{i-1},and,P_i$ 足够接近，且避免了由于丢失数据而产生的 伪影。
  • Journey (行驶状态)：即不是发动机关闭状态，也不是怠速状态。

• 当 Ping 被分类后，以每辆车为单位，按时间顺序排序；并把所有连续的怠速状态和发动机关闭状态的 Ping 聚集成集群 (并不会被其中 Journey 状态的 Ping 給分割开来)。

• 由于丢失数据，导致一组连续的怠速状态 Ping 彼此相对较远地分布开来。故我们得重新执行 时间-空间 的约束条件 ($s_i \leq 1.4,m/s$ and $H(p_i,p_{i-1}) \leq 150,m$)。

  无法满足约束条件：即一组连续的怠速状态 Ping 将被分隔得很远，其中的 Journey 状态的 Ping 都给丢失了。

• 以这种方式创建的 Pings 集群 代表我们想要分类的 已识别的汽车停靠点。综上所述，汽车停靠点被定义为按时间顺序排序的 Ping 集群 (包含怠速状态或发动机关闭状态的 Ping，并且满足进一步的 时间-空间 得约束条件。

• 每个 汽车停靠点 都有几个特性 (通过计算其中的 Ping)：Ping 的数量，停靠点的起点和终点 (属于该停靠点的 Ping 的第一个和最后一个时间戳)，驻留时间 (属于该停靠点的起始时间和结束时间) 和形状 (由GPS消息的最大 (最小) 纬度/经度坐标定义)。

• 所有这些信息对于在第二阶段提取特征工作至关重要，即汽车停靠点意图的分类。

贴标签

• 首先，对上述程序中获得的汽车停靠点分配 地面实况标签；再者，将它们与 工单数据 进行匹配。一般来说，若车辆停留点在时间上和空间上与工单数据 $W_i$ 相匹配，则可认为该汽车停靠点即为某一工单数据。
  • 对于只包含 idling 和 engine off Pings 的停靠点，我们认为它满足空间上的匹配。
  • 对于任何工单，空间上匹配了停留点；如果停留点的驻留时间与工单的时间项 (指示作业已启动的时间和指示服务已结束的时间) 间隔相交，时间的匹配也随着满足。

分类特征

在 车辆停靠侦查技术 章节中描述的，从一系列的 GPS Pings 提取汽车停靠点，并从中提取 100 个不同的特征用于训练随机森林模型，随之将这些特征划分为 4 个不同的组：

• 汽车停靠点特征 ( Stop-wise features，SWF )：

  • 驻留时间：(汽车) 停靠点第一个和最后一个 Ping 的时间差。
  • 开始时间特征：一天中的小时，一周中的某天，某月某日，某年某日。
  • 关闭引擎所花费的时间：对于每一个引擎关闭事件，我们计算当前 Ping 与前一个非引擎关闭状态的 Ping 之间的时间差，以表示引擎启动的时间。由于每个停靠点包含多个引擎关闭状态的 Ping，我们需要使用几个聚合函数聚合取得结果。
  • 形状：停靠点的宽度、高度、面积、比例。
  • 停靠点类型：发动机关闭状态。
  • 停靠点中发动机关闭状态 Ping 的数量。
  • 里程表距离：从第一次 Ping 到最后一次 Ping。
  • 停靠点内 Ping 的总数。
  • 平均速度 (根据停留点中第一次和最后一次 Ping 之间的里程差除以驻留时间计算所得)。

• 兴趣点特征 ( Points of interest features，POIF)：利用 PTV xLocate Server 中提取以下 POI 类型：

  • 银行;
  • 大学;
  • 酒店;
  • 餐厅;
  • 休息区;
  • 杂货店;
  • 学校;
  • 购物中心;
  • 汽油;
  • 开放式停车场;

• 汽车停靠点集群特征 ( Stop cluster features，CF )：其原理是存在一些工单数据和非工单数据趋向于聚类成簇，类似于 [7] 中提出的熵度量方法：对于每个停靠点，查看并收集 250 米半径内的周边环绕的停靠点数据。

  • 车辆熵，计算公式为：

  $$E_v = - \sum_{\nu \in V}
  \frac{n_{\nu}}{N} ln(\frac{n_{\nu}}{N})
  \tag{1}
  $$

  $V$ 是车队中的车辆集合， $N$ 是 250 米半径范围内车队所有车辆的总停留点数，$n_{\nu}$ 是车辆 $\nu$ 在同一区域停靠的总次数。这个熵度量给出了一个区域内同一车队车辆的多样性。

  • 簇中汽车停靠点的平均，总和，最大和最小驻留时间。
  • 邻近汽车停靠点的数量 (在其质心250米半径以内)。

• 序列特征 (Sequential features，SeqF).

不足

• 在车辆停靠点侦查技术章节中，使用的是非监督方式的算法，即基于密度的 DBSCAN 聚类算法。其中涉及密度阈值的设定多少问题，就需要对具体样本量进行考究才能决定。

参考

[1] Horozov T, Narasimhan N, Vasudevan V. Using location for personalized POI recommendations in mobile environments [C]//Applications and the internet, 2006. SAINT 2006. International symposium on. IEEE, 2006: 6 pp.-129.
[2] Jiang K, Yin H, Wang P, et al. Learning from contextual information of geo-tagged web photos to rank personalized tourism attractions [J]. Neurocomputing, 2013, 119: 17-25.
[3] Palma A T, Bogorny V, Kuijpers B, et al. A clustering-based approach for discovering interesting places in trajectories [C]//Proceedings of the 2008 ACM symposium on Applied computing. ACM, 2008: 863-868.
[4] Gong L, Sato H, Yamamoto T, et al. Identification of activity stop locations in GPS trajectories by density-based clustering method combined with support vector machines [J]. Journal of Modern Transportation, 2015, 23(3): 202-213.
[5] Ester M, Kriegel H P, Sander J, et al. A density-based algorithm for discovering clusters in large spatial databases with noise [C]//Kdd. 1996, 96(34): 226-231.
[6] Lv M, Chen L, Xu Z, et al. The discovery of personally semantic places based on trajectory data mining [J]. Neurocomputing, 2016, 173: 1142-1153.
[7] Gingerich K, Maoh H, Anderson W. Classifying the purpose of stopped truck events: An application of entropy to GPS data [J]. Transportation Research Part C: Emerging Technologies, 2016, 64: 17-27.
[8] Sambo F, Salti S, Bravi L, et al. Integration of GPS and satellite images for detection and classification of fleet hotspots [C]//Intelligent Transportation Systems (ITSC), 2017 IEEE 20th International Conference on. IEEE, 2017: 1-6.
[9] Wolf J, Guensler R, Bachman W. Elimination of the travel diary: Experiment to derive trip purpose from global positioning system travel data [J]. Transportation Research Record: Journal of the Transportation Research Board, 2001 (1768): 125-134.
[10] Bohte W, Maat K. Deriving and validating trip purposes and travel modes for multi-day GPS-based travel surveys: A large-scale application in the Netherlands [J]. Transportation Research Part C: Emerging Technologies, 2009, 17(3): 285-297.