1 论文笔记：Efficient Trajectory Similarity Computation with ContrastiveLearning

2022CIKM

1 intro

1.1 背景

• 轨迹相似度计算是轨迹分析任务（相似子轨迹搜索、轨迹预测和轨迹聚类）最基础的组件之一
• 现有的关于轨迹相似度计算的研究主要可以分为两大类：
  • 传统方法
    • DTW、EDR、EDwP等
    • 二次计算复杂度O(n^2)
    • 缺乏稳健性
      • 会受到非均匀采样、噪点的影响
  • 基于学习的方法
    • 旨在减少计算复杂度和/或提高稳健性
    • 根据它们的目的将它们分为两个方向
      • 神经逼近方法
        • 利用强大的神经网络在隐藏空间中逼近任何现有的轨迹测量
        • 训练一个神经网络g以将轨迹编码到隐藏空间
        • 最小化估计的相似性和基准之间的差异
          • 
            • Dh​是隐藏空间中的差异（相似性）测量（例如，欧几里得距离）
        • 不需要两个轨迹之间的点对齐，因此计算复杂度在轨迹的长度上是线性的
        • 由于要逼近的测量而遭受 稳健性问题
      • auto-encoder 方法
        • 无监督地学习映射函
        • 为了提高潜在表示相对于低质量的鲁棒性，这些方法采用了不同的策略
          • t2vec利用去噪顺序自编码器
          • Trembr整合了路网信息并设计了多个任务
        • 在训练编码模型方面 效率低下。
          • 这是由于顺序自编码器架构的固有限制，其中解码过程和逐步重构非常耗时
          • t2vec 在 Tesla K40 GPU 上训练 2千万轨迹的一个epoch大约需要 14 小时，平均每个轨迹有 60 个样本
        • 这些方法试图学习相同基础路线轨迹（高采样轨迹）的一致表示以解决质量问题
          • 换句话说，即使来自相同基础路线的轨迹具有不同的采样率和噪点，表示应该是相同的
          • 论文认为，由于他们的目标是重构轨迹而不是基础路线，顺序自编码器无法实现这一目标
          • ——>对于顺序自编码器来说， 获得一致的表示是非常困难的

1.2 论文思路

• 提出了一种基于对比学习的轨迹相似性计算的新型鲁棒模型（CL-TSim）
  • 遵循常见的范例，首先学习轨迹的表示，然后使用欧几里得距离在编码空间中计算轨迹之间的相似性
• 对轨迹 Ti 进行预处理，以获得增强轨迹 Tj
  • 其中使用下采样和扭曲增强来适应轨迹特征，包括非均匀采样率和噪点
• 同时将它们编码到隐藏空间并最大化它们之间的一致性

• 遵循对比学习架构，CL-TSim 只包含一个编码器和一个投影器
  • 编码器用于编码原始轨迹以学习它们的表示
  • 投影器用于将表示映射到损失函数的度量空间
  • 与顺序自编码器相比，它不需要解码器和逐步重构，这可以显著减少训练时间。

2 Preliminary

2.1 基础路线

• 由移动对象生成的连续空间曲线
• 只存在于理论中，因为配备了 GPS 的设备无法连续记录时空位置

2.2  轨迹

• 移动对象的轨迹，记为 T
• 从基础路线中采样的一系列有限点的序列，形式为 𝑇=((𝑥1,𝑦1,𝑡1),(𝑥2,𝑦2,𝑡2),...,(𝑥𝑛,𝑦𝑛,𝑡𝑛))
• xi,yi 代表在时间戳 𝑡𝑖 的采样位置的经度和纬度信息
• 受采样方法和设备的影响，轨迹通常基于不同的采样率生成，并包含有噪点

2.3 问题定义

给定一组轨迹，我们的问题是设计一个高效且鲁棒的模型，以计算轨迹之间的相似性，目标如下：

1）高效的表示学习：有效地为每个轨迹 T 学习一个表示 t，其中 t 可以反映轨迹 T 的基础路线，用于计算轨迹相似性；

 2）模型的鲁棒性：换句话说，两个任意轨迹Ti 和Tj 之间的相似性是一致的，不受非均匀采样率和噪点的影响

3 模型

4 实验

4.1 数据

4.2 评估方法

4.2.1 自相似性

• 给定一组轨迹，随机选择 m 条轨迹和 n 条轨迹，分别记为 Q 和 D
  • 对于 Q 中的每条轨迹，通过交替从中取点来创建两个子轨迹（称为双胞胎轨迹），并将第一个子轨迹加入 Q1，而另一个加入 Q2
  • 对于 Q1 中的每条轨迹，称为查询轨迹，我们在Q2∪D 中检索最相似的轨迹，称为数据库轨迹
  • 显然，Q2 中的轨迹应该排在 D 之前，因为它们是由与 Q1 中相同的轨迹生成的
• 假设 Ti 是 Q1 中的一个查询轨迹，而 Tj 是 Q2 中的相应双胞胎轨迹
  • 计算 Ti 与 Q2∪D1 之间轨迹的相似性，根据相似性对轨迹进行排序，并记 Tj 的排名为 ri
• 基于此，采用两个广泛使用的度量标准，即精确度 P 和平均排名 MR
  • 

当 ri 等于 0 时，pi 等于 1；否则，pi 等于 0。（只有查询数据集里面Tj是最相似的，才会是1）

更大的 P 或更小的 MR 值意味着更好的自相似性性能。

4.2.2 交叉相似性

一个好的相似性度量应该能够保持两个不同轨迹之间的相似性，而不考虑数据采样策略

交叉距离偏差（CDD）来评估性能

Ta 和 Tb 是具有原始率的两个不同的轨迹，Ta′(rd) 是通过以 d 的速率随机丢弃（或扭曲）样本点获得的Ta 的变体，而 Tb′(rd) 是以与 Ta′(rd) 相同的方式获得的 Tb 的变体。

较小的 CDD 值表明评估的相似性（即，距离）更接近真实值。

4.3 结果

、