学术成果 | 高性能异质时空轨迹匹配
内容导读
物联网、传感器等技术不断发展，使得越来越多的轨迹被记录下来，如GPS记录、公交刷卡数据、手机信令数据等。现实中同一次的移动可能同时被多种传感器记录下来，例如用户的一次乘公交出行，用户的手机与不同的基站连接产生手机信令轨迹，用户的刷卡数据携带有上下车点信息，公交车上的GPS会记录公交车的轨迹。这些由不同传感器记录的轨迹往往在定位精度、采样频率、持续时长等方面差别很大，分别存储在不同的数据库中，如果能够将从同一次移动产生的不同轨迹匹配出来，进行时空轨迹匹配，就能够更充分地还原轨迹信息，从而应用于丰富轨迹语义、构建用户画像、挖掘共同出行者等。
时空轨迹匹配的核心是轨迹相似度的计算，已有的轨迹相似度（LCSS、DTW等）往往忽略轨迹的时间属性，但时空轨迹匹配要求轨迹在时间和空间上都尽量相近，如图1，轨迹B与A在平面上路径相似，但是时间不一致，所以不可能是同一次移动产生的。鉴于此，本研究提出了时间加权相似度（Time Weighted Similarity, TWS）与空间加权相似度（Space Weighted Similarity, SWS）来度量时空轨迹的相似度，并基于Spark平台构建了分布式轨迹匹配的框架。使用真实数据和模拟数据的实验表明，我们的相似度度量方法准确率优于已有方法，分布式匹配框架能够极大地提升匹配效率。
文章已于2019年11月发表于Future Generation Computer Systems。
图1 时空轨迹
时空轨迹相似度
对于目标轨迹，要在轨迹数据库中匹配到与其在现实中对应的轨迹，就需要通过计算轨迹相似程度，找到在时间与空间上都接近的轨迹。轨迹匹配的过程可以认为是搜索最相似轨迹的过程，其核心是轨迹相似度的度量。好的度量方式应该使得，与同一次移动采样得到的轨迹的相似度高，而与其他轨迹之间的相似度低。
给定两条连续的轨迹 T1:p1=p1(t), t∈[α1,β1]与 T2:p2=p2(t), t∈[α2,β2]，它们重合的时间段为 t∈[α,β]。直观上，如果两个轨迹的点如果持续长时间或者长的距离离的比较近，那么它们就应该是相似的，基于此，我们定义时空轨迹的相似度。
时间加权相似度（Time Weighted Similarity, TWS）定义为：
其中m(p1(t),p2(t))代表两点的邻近度，式子右边的分子是点的邻近度对时间的积分，可以看作是轨迹贴合的时间长度，然后除以总持续时间，就是轨迹贴合的时间比例，即时间加权的相似度。
空间加权相似度（Space Weighted Similarity, SWS）定义为：
其中 v1(t) 指 T1 在时刻 t的速度，式子右边的分母是T1的长度，分子是点的邻近度与其速度的乘积再对时间的积分，可以看作是轨迹贴合的距离，两者相除便是轨迹贴合的距离比例，即空间（距离）加权的相似度。
实际中，轨迹数据是离散的时间戳和位置序列，无法进行积分，我们用线性插值的方法推断轨迹在两个采样时刻间的位置，然后使用梯形公式近似计算积分：
在计算的过程中，需要先对轨迹进行插值，然后计算在相应时间戳上的点的邻近度，最后计算积分，计算过程如图2所示。
图2 时空轨迹相似度计算过程
2
并行计算加速
轨迹匹配需要巨大的计算量，例如两个包含10,000条轨迹的数据集做匹配，需要计算10⁸次轨迹相似度，单机往往难以处理。为了支持海量时空轨迹数据的匹配，我们基于Spark构建了分布式的匹配框架，框架主要分为三个阶段：
1. 时空轨迹分片： 将轨迹拆分成线段，并构造时间—空间立方体，用于划分线段。
2. 计算线段相似性得分：在每个时间—空间立方体内计算线段的相似性得分。
3. 合并汇总轨迹相似度：将属于同一组轨迹的线段的相似性得分汇总，得到轨迹的相似度。
总体流程如图3所示：
图3 分布式轨迹匹配流程
3
实验
实验分别使用真实数据和模拟数据来衡量TWS与SWS的的准确性以及分布式框架的效率。我们使用新疆某高速路区域的车辆轨迹与手机信令轨迹做匹配，来挖掘乘客与车辆的实际对应关系。根据北京出租车GPS轨迹以及载客记录，模拟出乘客以及司机的手机信令数据，然后进行同样的匹配。图4是北京出租车模拟数据的一个样例。
图4 北京出租车数据样例
准确率比较：
以MHD、MHDT、CU、DTW、TWD方法作为对比方法，不同方法在不同实验中的准确率如图5所示。
图5 准确率比较
可以看到，TWS与SWS方法的匹配准确率优于其他方法。
匹配效率比较：
以直接使用Spark进行全局Join的方法作为基准方法，在不同数据集上两种方法的耗时如图所示：
图6 效率比较
可以看到，我们的框架的效率几乎是普通方法的100倍，对20万 × 2.7万的轨迹匹配也只需要11分钟左右的时间，效率非常可观。
4
总结
本研究针对时空轨迹匹配问题，提出了轨迹的时间加权相似度（TWS）与空间加权相似度（SWS），并构造了高性能的分布式框架来加速轨迹匹配的过程，最后使用实际数据与模拟数据进行实验，显示了方法在准确性和效率上的突出优势。
本文代码已在Github上共享：
https://github.com/s3pku/TrajectoryMatching
点击文末“阅读原文” 可查看相关文献
参考文献
Gong, X., Huang, Z., Wang, Y., Wu, L., & Liu, Y. (2020). High-performance spatiotemporal trajectory matching across heterogeneous data sources. Future Generation Computer Systems, 105, 148 - 161.
素材来源：S³-Lab
材料整理：龚旭日
内容排版：杨桃汝
▼点击| 阅读原文 |查看文章