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

news2023/11/30 10:05:34

2022CIKM

1 intro

1.1 背景

轨迹相似度计算是轨迹分析任务（相似子轨迹搜索、轨迹预测和轨迹聚类）最基础的组件之一
现有的关于轨迹相似度计算的研究主要可以分为两大类：
- 传统方法
  - DTW、EDR、EDwP等
  - 二次计算复杂度O(n^2)
  - 缺乏稳健性
    - 会受到非均匀采样、噪点的影响
- 基于学习的方法
  - 旨在减少计算复杂度和/或提高稳健性
  - 根据它们的目的将它们分为两个方向
    - 神经逼近方法
      - 利用强大的神经网络在隐藏空间中逼近任何现有的轨迹测量
      - 训练一个神经网络g以将轨迹编码到隐藏空间
      - 最小化估计的相似性和基准之间的差异
        
        $|D_H(g(T_i),g(T_j))-D(T_i,T_j)|$
        
        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