论文 | 归类分析 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 ${Pi}{i=1}^n = {P_1, …, P_n}$ 分别描述每辆车行驶的路线。
      • 每一个 GPS Ping $P_i$ 包含每辆车的状态信息,即有车辆 ID $v_i$,经度和纬度 (位置信息 $p_i$),里程表 $d_i$,时间戳 $t_i$ 和 事件代码 $e_i$。
    • 工单数据
      • 设定有一系列的工单 ${Wi}{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(pi,p{i-1})$ 表示两点间的半正定距离。然后,对于给定车辆给予一对连续的 Ping $Pi\,and\,P{i-1}$,且满足以下约束,则可定义为怠速:
      • $si = H(p_i,p{i-1})\,/\,(ti - t{i-1}) \leq 1.4\,m/s\,(5km/h)$,确定速度接近零;
      • $H(pi,p{i-1}) \leq 150\,m$,确保 $P_{i-1}\,and\,P_i$ 足够接近,且避免了由于丢失数据而产生的 伪影
    • Journey (行驶状态):即不是发动机关闭状态,也不是怠速状态。
  • 当 Ping 被分类后,以每辆车为单位,按时间顺序排序;并把所有连续的怠速状态和发动机关闭状态的 Ping 聚集成集群 (并不会被其中 Journey 状态的 Ping 給分割开来)。
  • 由于丢失数据,导致一组连续的怠速状态 Ping 彼此相对较远地分布开来。故我们得重新执行 时间-空间 的约束条件 ($si \leq 1.4\,m/s$ and $H(p_i,p{i-1}) \leq 150\,m$)。

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

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

  • 每个 汽车停靠点 都有几个特性 ( 通过计算其中的 Ping ):Ping 的数量,停靠点的起点和终点 ( 属于该停靠点的 Ping 的第一个和最后一个时间戳 ),驻留时间 ( 属于该停靠点的起始时间和结束时间 ) 和形状 ( 由GPS消息的最大 (最小) 纬度/经度坐标定义 )。
  • 所有这些信息对于在第二阶段提取特征工作至关重要,即汽车停靠点意图的分类。

标注标签

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

分类特征

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

  • 汽车停靠点特征 ( Stop-wise features,SWF ):

    • 驻留时间:(汽车) 停靠点第一个和最后一个 Ping 的时间差。
    • 开始时间特征:一天中的小时,一周中的某天,某月某日,某年某日等。

      是否统一时间表示方式 (时间戳): yyyy-MM-dd HH:mm

    • 关闭引擎所花费的时间:对于每一个引擎关闭事件,我们计算当前 Ping 与前一个非引擎关闭状态的 Ping 之间的时间差,以表示引擎启动的时间。由于每个停靠点包含多个引擎关闭状态的 Ping,我们需要使用几个聚合函数聚合取得结果。

    • 形状:停靠点的宽度、高度、面积、比例。
    • 停靠点类型:发动机关闭状态。
    • 停靠点中发动机关闭状态 Ping 的数量。
    • 里程表距离:从第一次 Ping 到最后一次 Ping 的里程表距离。
    • 停靠点内 Ping 的总数。
    • 平均速度 (根据停留点中第一次和最后一次 Ping 之间的里程差除以驻留时间计算所得)。
  • 兴趣点特征 ( Points of interest features,POIF):利用 PTV xLocate Server 中提取以下 POI 类型:
    • 银行;
    • 大学;
    • 酒店;
    • 餐厅;
    • 休息区;
    • 杂货店;
    • 学校;
    • 购物中心;
    • 汽油;
    • 开放式停车场;
  • 汽车停靠点集群特征 ( Stop cluster features,CF ):描述当前停靠点集周围停靠点的特征所组成的特征集。其原理是,存在一些工作状态的工单和非工作状态的工单数据,趋向于聚类成簇。类似于 [7] 中提出的熵度量方法:对于每个停靠点,查看并收集 250 米半径内的周边环绕的停靠点数据。

    • 车辆熵,计算公式为:

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

    • 簇中汽车停靠点的平均,总和,最大和最小驻留时间。

    • 邻近汽车停靠点的数量 (在其质心250米半径以内)。
  • 序列特征 (Sequential features,SeqF):

    • 工作日内停车的次序位置:同一辆车在白天按照停车先后顺序的 (归一化的) 相对位置。
    • 停车所涵盖的时间百分比:停车行为在工作日中的时间占比 ( 注意该值与工作日的开始相关,且工作日的开始由一天中第一个 Ping 定义 )。这也是司机夜间休息时间的近似假设。

实验

实验过程请参考原文献,篇幅问题就不照搬文章内容了。

总结

  • 本文基于商用车队的 GPS 数据研究了停车目的识别和分类问题。
  • 为了建立地面真实数据集,通过查看考虑到每辆车的工作单进度数据,开发了一个时空聚类算法,实现了一个自动标注标签过程;
  • 为了提高分类精确度,从 GPS Ping 数据中提取了 4 组不同的特征 ( SWF、POIF、CF 和 SeqF );
  • 利用提取的特征训练随机森林模型,并与两种基线模型进行性能比较。实验结果表明,本文提取总结的 4 组特征显著提高了随机森林的分类能力。

不足

  • 在车辆停靠点侦查技术章节中,使用的是非监督方式的算法,即基于密度的 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.