论文笔记：Deep Trajectory Recovery with Fine-Grained Calibration using Kalman Filter

TKDE 2021

1 intro

1.1 背景

• 用户轨迹数据对于改进以用户为中心的应用程序很有用
  • POI推荐
  • 城市规划
  • 路线规划
• 由于设备和环境的限制，许多轨迹以低采样率记录
  • 采样的轨迹无法详细说明物体的实际路线
  • 增加了轨迹中两个连续采样点之间的不确定性
  • ——>开发有效的算法以基于原始低采样数据恢复高质量轨迹非常重要
• 总的来说，轨迹恢复任务在两种不同的环境中被研究，这取决于地图信息（如道路网络）是否可用
  • 在第一种环境中，轨迹位置通常映射到道路段或POI
  • 在第二种环境中，地图信息作为输入是不可用的，称之为自由空间轨迹恢复
    • 本文关注的是第二种环境

1.2 之前的工作

• 现有研究中存在两个潜在问题
  • 许多方法依赖于启发式搜索算法或简单的概率模型
    • 主要模拟位置之间的相邻过渡模式
      • 深度优先搜索算法
      • 吸收马尔可夫链
      • 吉布斯抽样
    • 这些方法不能很好地捕获复杂的顺序依赖性或全局数据相关性
  • 为了减少无约束数值坐标的预测复杂性，大多数以前的研究采用了一个常见的预处理策略——将空间映射到离散单元，例如单元格或锚点
    • 然后，他们的焦点变成如何在离散单元上开发有效的恢复算法
    • 使用离散单元可能会带来噪音或不准确的信息
      • 因此，通常需要一个后校准步骤来产生更准确的结果
      • 然而，以前的方法主要采用简单的启发式校准方法，例如识别单元格中的频繁位置或简单地使用单元格的中心坐标
      • 忽视了后校准在细化粗糙单元级预测结果中的重要性
• 深度学习任务（如RNN）
  • 只专注于局部时间窗口内的下一步或短期位置预测
  • 仍直接产生单元格级的预测，并没有在他们的模型中结合原则性的后校准组件来得出更准确的估计
  • ——>将现有的基于神经网络的轨迹模型直接应用于自由空间轨迹恢复任务是困难的

1.3 本文贡献

• 提出了一种新颖的深度混合轨迹恢复模型（DHTR)
  • 子序列到序列恢复模型（即subseq2seq）
    • 扩展了seq2seq
  • 为了有效捕获全局时空相关性，采用了空间和时间注意力机制来增强模型性能
    • 通过注意力机制，我们的模型能够表征轨迹点之间的长距离相关性
  • 将subseq2seq组件与卡尔曼滤波器（KF）整合在一起，以校准噪声单元预测为准确坐标
    • 在每一个时间步，来自subseq2seq组件的噪声预测将被送入KF组件进行校准
    • 然后精炼的预测将被转发到subseq2seq组件，用于下一个时间步的计算
• ——>模型具有两个组件的优点
  • 建模复杂序列数据的能力
  • 降低预测噪声的能力

2 Preliminary

2.1 一些概念

• 位置
  • 经纬度坐标<x,y>
• 区域单元
  • 整个地理空间被划分为一组区域单元，用C表示
  • 每个单元c∈C是一个边长为l的正方形空间
  • 区域单元坐标为中心点的坐标<Xc,Yc>
• 轨迹点
  • 一个移动物体的轨迹点是一个带时间戳的位置
  • 由一个四元组<x；y；s；c>来建模
    • a:x是经度，a:y是纬度，a:s是时间戳，a:c是点a被分配到的单元
• 采样间隔
  • 一个移动物体两个连续采样点之间的时间差
• ε-采样轨迹
  • 同一移动物体使用采样间隔"的n个均匀采样点的时间有序序列
  • （后续表述中把上标(t)去掉了）
• ε采样子轨迹
  • 给定一个ε采样轨迹t，相应的子轨迹t是t的一个m长度的子序列
  • 子轨迹中的位置在时间戳上可能不是均匀分布的

2.2 问题定义

• 给定一个ε采样轨迹数据集和一个子轨迹t‘，我们希望重建或恢复相应的轨迹t。
• 也就是说，对于每个缺失的轨迹点ai（即ai属于t但不属于t‘），我们将推断其在时间ai:s时对应的经度ai:x和纬度ai:y。

3 模型

3.1 模型总览

• 包含三个主要部分
  • 第一部分是精心设计的子序列到序列（subseq2seq）神经网络模型
    • 在seq2seq的基础上开发的
  • 第二部分是一个注意力机制，它用于使subseq2seq能够捕获复杂的时空关联
    • 注意力机制同时考虑了整个轨迹中位置之间的空间和时间影响
    • 为了减少直接建模数值坐标序列的复杂性，subseq2seq组件在单元级捕获序列注意力相关性
  • 第三部分用基于卡尔曼滤波器的新型后校准组件增强了subseq2seq模型
    • 将subseq2seq组件和KF组件整合在一个联合的深度混合模型中

3.2 Subseq2seq

• 不是直接预测数值坐标值，而是首先推断缺失轨迹点的对应单元
  • 单元ID序列比原始数值序列更可靠且易于建模
• 主要思想是将恢复任务转化为一个序列到序列的任务
  • 输入序列是子轨迹，输出序列是重建的完整轨迹
  • 输入与相应的输出高度相关

3.3  时空attention

3.4     应用卡尔曼滤波器

【精选】机器学习笔记：卡尔曼滤波_UQI-LIUWJ的博客-CSDN博客

• 之前的方法应用subseq2seq模型来表征轨迹的单元序列，然后将预测单元的中心坐标视为最终预测
  • 这种方法有两个潜在的缺点
    • 预测模型可能会受到噪声的影响，例如仪器误差
    • 由于我们使用对应的单元坐标作为代理，最终的估计是粗略的
• ——>提出将上述神经网络模型与卡尔曼滤波器(KF)整合

3.4.1 卡尔曼滤波器

• 卡尔曼滤波器（KFs）通常在线性和高斯噪声的假设下是最优的状态估计器。
• 在KF模型中，使用一个状态向量 gi​，它可能包含位置和/或速度，来表示i时刻物体的状态。
  • 物体以高斯噪声 eg​ 线性更新状态gi​ 
  • 
    • M是噪声eg的协方差，Φ是状态更新矩阵
• 在KF模型中，真实值 gi​ 可以通过测量向量 zi​ 来测量
  • 
    • φ是测量矩阵
• 在KF模型中，测量向量 zi​ 是可观察的，真实状态 gi​ 是待估计的未知变量
  • 方程(13)和(14)中的矩阵φ，Φ，M,N被视为先验已知的
• KF模型使用两个程序，即预测（Prediction）和更新（Update），来迭代估计 g 的真实值并计算一个协方差矩阵，表示为 H，用以表达 g 的不确定性。

3.4.1.1 预测

在预测过程中，卡尔曼滤波器使用以下方程来预测时i时刻的状态 g 和协方差矩阵 H

• 下标“i−1∣i−1”表示在i-1时刻由更新程序生成的变量，而下标“i∣i−1”表示预测的状态和协方差。

3.4.1.2 更新 

在更新过程中，KF模型使用可观察的测量向量 zi​ 来更新/校正预测的 gi∣i−1​ 和 Hi∣i−1​ ：

其中，Ki​ 被称为最优卡尔曼增益，它结合了预测状态和测量状态作为更新状态。

• 我们可以看到 Ki​ 是估计误差的协方差矩阵 Hi和测量误差的协方差矩阵 Ni​ 之间的权衡系数矩阵。注意，在标准KF中，协方差矩阵 Ni​ 是一个预设常数。这里，我们加入了下标i，以便于我们随后的扩展。
• 在每个时间步长i，KF接受噪声测量zi​ 及其对应的协方差矩阵 Ni作为输入，并产生“过滤”后的测量值 如下：

3.4.2 卡尔曼滤波+subseq2seq

3.5 训练 

4 实验

4.1 实验数据

4.2 实验结果