内容导读

物联网、传感器等技术不断发展,使得越来越多的轨迹被记录下来,如GPS记录、公交刷卡数据、手机信令数据等。现实中同一次的移动可能同时被多种传感器记录下来,例如用户的一次乘公交出行,用户的手机与不同的基站连接产生手机信令轨迹,用户的刷卡数据携带有上下车点信息,公交车上的GPS会记录公交车的轨迹。这些由不同传感器记录的轨迹往往在定位精度、采样频率、持续时长等方面差别很大,分别存储在不同的数据库中,如果能够将从同一次移动产生的不同轨迹匹配出来,就能够更充分地还原轨迹信息,从而应用于丰富轨迹语义、构建用户画像、挖掘共同出行者等。

时空轨迹匹配的核心是轨迹相似度的计算,已有的轨迹相似度(LCSS、DTW等)往往忽略轨迹的时间属性,但时空轨迹匹配要求轨迹在时间和空间上都尽量相近,如图1,轨迹B与A在平面上路径相似,但是时间不一致,所以不可能是同一次移动产生的。鉴于此,本研究提出了时间加权相似度(Time Weighted Similarity, TWS)与空间加权相似度(Space Weighted Similarity, SWS)来度量时空轨迹的相似度,并构基于Spark平台构建了分布式轨迹匹配的框架。使用真实数据和模拟数据的实验表明,我们的相似度度量方法准确率优于已有方法,分布式匹配框架能够极大地提升匹配效率。

时空轨迹

文章已于2019年11月发表于 Future Generation Computer Systems1.

时空轨迹相似度

对于目标轨迹,要在轨迹数据库中匹配到与其在现实中对应的轨迹,就需要通过计算轨迹相似程度,找到在时间与空间上都接近的轨迹。轨迹匹配的过程可以认为是搜索最相似轨迹的过程,其核心是轨迹相似度的度量。好的度量方式应该使得,与同一次移动采样得到的轨迹之间的相似度高,而与其他轨迹之间的相似度低。

给定两条连续的轨迹 \( T_1:p_1 = p_1(t), t \in[\alpha_1, \beta_1] \) 与 \( T_2:p_2 = p_2(t), t \in[\alpha_2, \beta_2] \), 它们重合的时间段为 \( t \in [\alpha,\beta] \)。 直观上,如果两个轨迹的点如果持续长时间或者长的距离离的比较近,那么它们就应该是相似的,基于此,我们定义时空轨迹的相似度。

时间加权相似度(Time Weighted Similarity, TWS) 定义为:$$TWS(T_1,T_2) = \frac{\int_\alpha^\beta m(p_1(t),p_2(t)) {\rm d} t}{\beta_1-\alpha_1}$$ 其中\( m(p_1(t),p_2(t)) \)代表两点的邻近度,式子右边的分子是点的邻近度对时间的积分,可以看作是轨迹贴合的时间长度,然后除以总持续时间,就是轨迹贴合的时间比例,即时间加权的相似度。

空间加权相似度(Space Weighted Similarity, SWS) 定义为: $$ SWS(T_1,T_2)=\frac{\int_\alpha^\beta m(p_1(t),p_2(t))v_1(t){\rm d} t}{\int_{\alpha_1}^{\beta_1} v_1(t){\rm d} t}$$ 其中 \( v_1(t) \) 指 \( T_1 \) 在时刻 \( t \) 的速度,式子右边的分母是\( T_1 \)的长度,分子是点的邻近度与其速度的乘积再对时间的积分,可以看作是轨迹贴合的距离,两者相除便是轨迹贴合的距离比例,即空间(距离)加权的相似度。

实际中,轨迹数据是离散的时间戳和位置序列,无法进行积分,我们用线性插值的方法推断轨迹在两个采样时刻间的位置,然后使用梯形公式近似计算积分:

$$ \int_\alpha^\beta m(p_1(t),p_2(t)){\rm d} t \approx \frac{1}{2}\sum_{i=1}^{n-1}(m_i+m_{i+1})(t_{i+1}-t_i) $$ $$ \int_\alpha^\beta m(p_1(t),p_2(t))v_1(t){\rm d} t \approx \frac{1}{2}\sum_{i=1}^{n-1}(m_i+m_{i+1})l_i $$

在计算的过程中,需要先对轨迹进行插值,然后计算在相应时间戳上的点的邻近度,最后计算积分,计算过程如下图所示: 计算步骤示意图

并行计算加速

轨迹匹配需要巨大的计算量,例如两个包含10,000条轨迹的数据集做匹配,就需要计算10^8次轨迹相似度,单机往往难以处理。为了支持海量时空轨迹数据的匹配,我们构建了分布式的匹配框架,框架主要分为三个阶段:

  1. 时空轨迹分片: 将轨迹拆分成线段,并构造时间—空间立方体,用于划分线段。
  2. 计算线段相似性得分: 在每个时间—空间立方体内计算线段的相似性得分。
  3. 合并汇总轨迹相似度: 将属于同一组轨迹的线段的相似性得分汇总,得到轨迹的相似度。

总体流程如下图所示(代码已在Github上共享2):

计算步骤示意图

实验

实验分别使用真实数据和模拟数据来衡量TWS与SWS的的准确性以及分布式框架的效率。我们使用新疆某高速路区域的车辆轨迹与手机信令轨迹做匹配,来挖掘乘客与车辆的实际对应关系。根据北京出租车GPS轨迹以及载客记录,模拟出乘客以及司机的手机信令数据,然后进行同样的匹配。下图是北京出租车模拟数据的一个样例:

北京模拟数据

准确率比较

以MHD3、MHDT、CU4、DTW5、TWD6方法作为对比方法,不同方法在不同实验中的准确率如下图所示:

准确率比较

可以看到,TWS与SWS方法的匹配准确率优于其他方法。

效率比较

以直接使用Spark进行全局Join的方法作为基准方法,在不同数据集上两种方法的耗时如图所示:

效率比较

可以看到,我们的框架的效率几乎是普通方法的100倍,对20万 × 2.7万的轨迹匹配也只需要11分钟左右的时间,效率非常可观。

总结

本研究针对时空轨迹匹配问题,提出了轨迹的时间加权相似度(TWS)与空间加权相似度(SWS),并构造了高性能的分布式框架来加速轨迹匹配的过程,最后使用实际数据与模拟数据进行实验,显示了方法在准确性和效率上的突出优势。


  1. 文章链接:https://authors.elsevier.com/c/1aAvy,3q5xWAT8 ↩︎

  2. https://github.com/Gooong/TrajectoryMatching/ ↩︎

  3. F. Shao, S. Cai, J. Gu, A modified hausdorff distance based algorithm for 2-dimensional spatial trajectory matching, in: 2010 5th International Conference on Computer Science & Education, IEEE, 2010, pp. 166–172. ↩︎

  4. D. Kondor, B. Hashemian, Y. de Montjoye, C. Ratti, Towards matching user mobility traces in large-scale datasets, IEEE Trans. Big Data (2019) 1, http://dx.doi.org/10.1109/TBDATA.2018.2871693. ↩︎

  5. K. Buchin, M. Buchin, M. Van Kreveld, J. Luo, Finding long and similar parts of trajectories, Comput. Geom. 44 (9) (2011) 465–476. ↩︎

  6. E. Frentzos, K. Gratsias, Y. Theodoridis, Index-based most similar trajectory search, in: 2007 IEEE 23rd International Conference on Data Engineering, IEEE, 2007, pp. 816–825. ↩︎