轨迹建模与应用的深度生成模型

1. 介绍

挑战：

(1)现实世界的轨迹很难建模，因为它们的空间路径分布是时变的。通常采用路网兴趣点(POIs)、天气信息等外部时空特征来增强轨迹建模。然而，现有的轨迹工作忽略了对捕获轨迹路径模式至关重要的底层路网属性(例如，道路类型和道路方向)。道路属性是密切相关的，因此通过图1中不同道路类型上的轨迹空间分布实例，建立轨迹分布模型是十分重要的。

(2)很难对现实世界的轨迹进行建模，因为轨迹数据相对于路线边缘的数量是高维的，并且在路网上分布非常倾斜。虽然目前流行的时空图卷积模型对于常见的图节点或边属性建模是有效的，但对于高维且倾斜的轨迹建模是不够有效的

为了解决上述挑战，我们提出了一个名为MTNet的深度生成模型，通过充分利用底层道路属性，有效地建模高维但倾斜的轨迹数据。首先，我们从OpenStreetMap中收集了重要的道路属性，并将其编码为道路元知识，以增强轨迹的时空表示，解决C1挑战。

其次，MTNet采用基于知识的元学习模块，通过从倾斜轨迹中学习广义轨迹分布模式，逐步生成高维轨迹，以解决C2挑战。

贡献：

(1)利用时空信息形式化地图匹配轨迹建模问题，并建立轨迹生成模型以支持轨迹应用。

(2)利用时空特征、潜在道路元知识、道路边缘之间的空间相关性和时间周期性信息对轨迹序列进行编码，以增强轨迹建模能力。

(3)提出了一个名为MTNet的深度生成模型，基于上述良好编码的轨迹特征对倾斜轨迹数据进行建模。利用MTNet为下游应用程序生成合成且真实的轨迹，并直接支持多个轨迹应用程序。

(4)演示了如何使用剪切梯度隐私学习的方法。

(5)在两个真实数据集上进行了综合实验。结果表明，MTNet显著优于现有方法

2. 问题定义

原始轨迹

路网

路网匹配轨迹

差分隐私

2.2 轨迹建模和应用

轨迹分布建模

从原点边到目的地边使用相应的时间信息一步一步地生成轨迹，其中每条边都依赖于它的轨迹前缀。因此，给定一个轨迹数据集

其轨迹联合概率密度函数(PDF)可表示为:

$Pr(x_1)$ 是第一条边的概率分布，

$f(td_1|x_1)$是出发时间$td_1$在$x_1$概率密度函数

$f(tc_1|x_1,td_1)$是在$x_1$上的出行时间$tc_1$在$td_1$时刻出发的概率密度函数

直接得到联合分布十分困难，所以用深度生成模型隐式地近似真实的轨迹分布

使用Jensen-Shannon散度来计算分布距离

$X$是来自真实数据集或者由$G$生成的轨迹

建立轨迹生成模型G

为了灵活支持不同粒度的合成轨迹生成，同时支持多个轨迹应用，将G定义为以原点边和(下一条边的)出发时间为输入条件的条件生成模型。将轨迹序列的生成分解为逐级生成路线边和行程时间的过程。具体地说,

实现DP隐私算法

3. MTNet

3.1 模型框架：

深度生成模型MTNet，该模型利用时空特征嵌入和基于元学习的轨迹生成的固有道路知识。图4展示了MTNet的概述，它由以下四个模块组成:

(1)轨迹表示模块(图4 (b))用于嵌入空间路线边缘和时间特征，旨在有效地表示轨迹序列。

(2)道路知识编码模块(图4 (c))用于道路边缘属性编码，引入固有的路线规划特征，增强轨迹前缀编码和后缀生成。

(3)轨迹前缀编码模块(图4 (a)的一部分)用于轨迹前缀编码，旨在从高维轨迹前缀中提取长期时空依赖关系。

(4)元生成器模块(图4 (d))用于轨迹路线边缘及其走时生成，旨在有效支持偏轨轨迹数据上的轨迹建模和生成。此外，图4 (e)中的路网拓扑约束对输出进行了屏蔽，以提高生成效率和质量。

3.2 轨迹表征

边嵌入

对于路网直接使用one-hot编码，它会生成一个$|E|$维度的向量，但是可能会造成维度过高。为了克服这个问题，用矩阵嵌入边

时间嵌入

为了模拟轨迹数据的可变时间分布，嵌入了出发时间，并将其作为MTNet的输入。将每天分为$N_t$个时间片，为了更好的表示能力，用矩阵嵌入出发时间片

时空关系编码

用node2vec来预训练和初始化的所有 $W_x$ 的嵌入来获取边之间的空间相关性。

我们使用时间嵌入矩阵建模这些时不变因子来生成旅行时间。

对于每条边有出行时间隐式向量

3.3 轨迹前缀编码

道路知识编码

从路线图中收集道路属性，并将其编码为信息格式。然后，采用道路知识编码子模块 MKEncoding 将编码后的道路边属性和出发时间信息串联成道路元知识(简称知识)，将时变路径模式组合起来，用于轨迹前缀编码和元生成模块。

道路长度、道路类型、地理方向、限速

道路前缀编码

基于每条路径边缘的时空轨迹嵌入和道路知识，进一步对轨迹前缀进行LSTM编码，获取轨迹前缀与待生成的轨迹后缀之间的长期时空相关性。

3.4 使用元生成器生成轨迹

MetaLearner的元学习子模块，为轨迹生成提供一系列神经权值，其中权值针对任何出发时点的每个边选择进行优化

元学习器

基于来自MKEncoding的时空知识，捕获每个道路边缘的道路网络路线规划模式，并为每个下一个边缘候选的输出神经网络适应和服务优化设置(神经权值)。从元学习的角度来看，是否选择特定的边缘候选作为下一个在特定出发时隙生成的边缘被视为一个单独的子任务。每个子任务都有不同的优化输出神经网络(具有不同的神经权值), 从丰富真实样本的边学习到的经验(模式)可以很容易地适应到样本较少的边，并提高相应的生成性能。MetaLearner采用单层全连接前馈网络实现。

输出神经网络

该子模块分别使用MaskedSoftmax和MaskedSigmoid函数生成道路和旅行时间。

对于每一步假设下一个候选道路边是 $x{a1:ak}$ 出发时间是。前缀的特征向量 $h^x_t$ 旅行时间隐状态向量 $h^{tc}{a1:ak}$ 计算流程如下：

道路边生成

对于每一条侯选边通过优化神经权重的点积得到一个分数和前缀特征向量。然后，基于MaskedSoftmax函数将相邻边缘候选点的所有分数转化为选择概率。基于对这些概率的多项抽样，随机选择一个候选作为下一个生成的边。

出行时间生成

当前所选边的出行时间和出行时间状态向量由相应优化后的神经权值的点积产生，最后通过一个sigmoid函数来生成一个重新缩放的旅行时间。

3.5 支持的轨迹应用

轨迹生成

从真实的大轨迹数据中学习的MTNet可以用来生成具有代表性的合成轨迹，并保留原始轨迹数据中的统计信息。MTNet可以为每个固定原点生成合成轨迹，其性能与真实世界旅行时间估计任务中的原始数据相似。

直接支持的轨迹应用

MTNet也能够直接支持统计轨迹分析，而不生成轨迹

(1) 轨迹流行度排名

给定一组轨迹，MTNet可以根据它们受时间影响的受欢迎程度对它们进行排名。输入是轨迹路径候选集和出发时间候选集，可以计算出排名值来比较受时间影响的流行度

(2) 轨迹后缀预测

轨迹后缀预测。给定一个轨迹前缀(例如，一个带出发时间的原点)，MTNet在后缀生成过程的每一步中，根据生成概率保持有希望的候选集合，搜索最有希望的后缀。

(3) 时间依赖的出行时间预测

给定一个具有出发时间的轨迹，MTNet可以直接估计每个路线边的行进时间

4. DP

高效地建模噪声轨迹数据，同时保留个人轨迹隐私。建立由学习轨迹路线分布和相应行程时间分布两部分组成的训练损失函数。

对于轨迹路线，使用负对数似然损失

对于出行时间，使用平均绝对损失

采用差分隐私随机梯度法来学习 MTNet，使得真实轨迹数据隐私地用于训练和指导轨迹生成

5. 实验

5.1 实验设置

数据集

成都和西安

评价指标

将JSD度量化为路线边使用率JSD和目的地JSD。MAE评估旅行时间产生误差。

基线

Ngram
AutoSTG
CSSRNN

路网提取与处理

道路网络来自OpenStreetMap。首先，将节点、边及其地理几何和道路水平等属性解析并建模为有向图，其中去除主连接组件中不可达的边;道路长度和地理方向是根据GPS坐标计算出来的。

轨迹数据预处理

基于FMM算法，将原始轨迹的地理坐标和时间戳与路网匹配.映射匹配有两个问题。首先，由于轨迹可能不会在边缘关节处开始和结束,根据偏移比计算相应的行程时间。其次，原始轨迹的时间戳可能与路段不一致，无法直接计算出发时间和出行时间。所以采用基于道路长度的线性插值来计算每个路线边缘的出发时间和行驶时间。轨迹长度不大于L的被收集到输入数据集中，小于L的被加装了停止标志。轨迹被打乱并分成训练数据(80%)和测试数据(20%)