标题: Micro-Macro Spatial-Temporal Graph-based Encoder-Decoder for Map-Constrained Trajectory Recovery
作者: 韦统龙，林友芳，林彦，郭晟楠，章澜，万怀宇
机构: 北京交通大学时空数据学习组
发表: IEEE Transactions on Knowledge and Data Engineering (TKDE，已接收）
代码链接: https://github.com/wtl52656/MM-STGED
摘要
在智能交通系统中，恢复稀疏轨迹中间缺失的GPS点，同时保证恢复的轨迹点约束在路网上，可以深入了解用户的移动行为。尽管最近的研究已经展示了通过端到端方式实现地图约束轨迹恢复的优势，但它们仍然面临两个重大挑战。首先，现有的方法大多是基于序列的模型。它们很难全面捕获每个轨迹的微观语义，包括每个GPS点的信息和两个GPS点之间的移动。其次，现有的方法忽视了宏观语义的影响，即道路路况和由一组轨迹反映出的人们的共享出行偏好。为了解决上述挑战，本文提出了一种融合轨迹微观和宏观语义信息的时空图模型（MM-STGED）。具体来说，将每条轨迹建模为一个图，以有效地描述轨迹的微观语义，并设计了一种新颖的消息传递机制来学习轨迹表示。此外，提取轨迹的宏观语义，并将它们进一步融入到基于图的解码器中，以指导轨迹恢复。在两个真实世界轨迹数据集上构建的具有三种不同采样间隔的稀疏轨迹上进行的广泛实验证明了提出的模型的有效性。
1. 引言
轨迹是一系列带时间戳的位置组成的序列，描述了用户移动。随着在智能交通系统（ITS）中GPS设备的部署，大量的用户轨迹数据被收集。挖掘轨迹数据在理解个人和车辆的出行模式以及支持各种下游智能导航应用方面起着至关重要的作用，例如，到达时间估计、路线预测和异常轨迹检测。然而，在现实生活中，由于采样机制和存储设备的限制，轨迹点的采样间隔较大导致轨迹通常很稀疏。例如，出租车通常每2到6分钟上传一次他们的GPS位置以节省能源。这些稀疏的轨迹通常导致重要信息的丢失。图1展示了一个由三个GPS点组成的稀疏轨迹的例子，其采样间隔为90秒：，其中 记录了GPS点的位置和时间信息，且 秒，。由于采样间隔大，GPS点之间的距离比较远，导致丢失了中间点的信息。因此，稀疏轨迹很难准确描述用户的详细移动。此外，大的采样间隔使得难以准确推断出用户途径的路段，从而导致道路相关的信息丢失（GPS点属于哪个路段以及相应的移动率）。然而，轨迹的道路相关信息对于下游应用至关重要，因为这些应用需要知道GPS点和路网之间的关系。因此，轨迹的稀疏性会降低下游轨迹挖掘任务的性能。为了提高稀疏轨迹的可用性和利用价值，有必要恢复稀疏轨迹上的多方面信息，包括GPS位置和道路相关的信息。这种任务被称为“地图约束轨迹恢复”，这是支持下游轨迹挖掘任务的关键轨迹预处理步骤。图1显示了一个地图约束轨迹恢复任务的例子。给定上述定义的轨迹，地图约束轨迹恢复任务旨在恢复一个采样间隔为30秒的地图约束轨迹：，其中每个地图约束点由路段，移动率，和时间组成。并且秒，。同时，可以通过和计算出精确的GPS位置信息（纬度和经度）。 现有关于地图约束轨迹恢复的工作可以分为两类：两阶段解决方案和端到端解决方案。两阶段解决方案可以进一步分为两个子类：首先恢复缺失的GPS点，然后进行地图匹配，或者首先进行地图匹配，然后恢复地图约束的轨迹点。前者可能会受到误差累积问题，因为恢复的GPS点可能不准确，导致地图匹配结果不可靠。后者首先将稀疏的GPS点映射到道路上，然后计算相邻点之间的最短路径。由于大多数基于隐马尔科夫模型（HMM）的地图匹配算法对稀疏轨迹进行道路匹配的准确率较低，因此这种方法在精度上通常有限制。此外，车辆的复杂移动模式通常会偏离最短路径。再者，由于地图匹配比较耗时，上述两种两阶段解决方案的效率比较低。 端到端解决方案旨在直接恢复地图约束的轨迹点。与两阶段解决方案相比，端到端解决方案更为有效，因为它们避免了误差的累积。此外，由于它们不需要地图匹配，因此更高效。然而，尽管最近的代表性工作已经取得了显著的进步，但端到端的地图约束轨迹恢复仍然面临以下未解决的挑战。1）现有的解决方案很难充分考虑到轨迹的微观语义信息，这对理解用户的移动行为非常重要。具体来说，如图2(a)所示，对于一个稀疏轨迹 ，其微观语义信息包括两部分：①每个GPS点提供的显式绝对信息，包括纬度、经度、时间戳和周围的道路网络，这些信息表示了移动对象的离散位置；②两个GPS点之间的隐式相对信息，包括空间转移 和时间成本 , 如图2 (a)所示， 并且 ，这反映了用户在两个观察到的GPS点之间的驾驶行为。GPS点之间的这种隐式相对信息描述了轨迹的连续性。例如，根据时间成本，可以推断用户的移动首先是从 到 ，然后到 ，因为 。另外，由于空间转移 ，可以猜测用户从 绕道到 ，而不是沿着最短路径行驶。这两类信息在理解个体轨迹和恢复轨迹细节中都是非常有价值的。因此，一个有效的轨迹学习方法应该能够同时捕获这两种类型的信息。然而，大多数现有的轨迹恢复方法将一条轨迹视为一个序列，并采用序列模型进行轨迹学习。如图2(b)所示，这些模型主要关注每个GPS点的显式绝对信息，而忽视了它们之间的隐式相对信息。因此，现有的相关工作并不能充分解决从这两个方面全面捕获微观语义信息的问题。2）无法显式地建模一组轨迹反映出的宏观语义信息，这通常对用户的个体出行决策有显著影响。具体来说，轨迹的宏观语义信息包括：1) 与行驶路线相关的路况和 2) 人们共享的出行偏好。与行驶路线相关的路况代表了用户所处的环境。这有助于恢复轨迹的细节，因为用户的实际驾驶行为受环境的影响。例如，如果当前路线拥堵，用户将以较慢的速度驾驶或切换到其他路线，这两种情况都会影响轨迹。人们的共享出行偏好反映了大多数人遵循的一般路线选择习惯，这可以提供先验知识来指导轨迹的恢复。然而，建模人们的共享出行偏好并非易事。一方面，人们的路线选择受到道路网络物理拓扑的约束，因为车辆必须在道路上行驶。另一方面，实时交通控制、道路通行规则和便利性也影响了人们的路线选择。例如，由于交通控制，物理上连接的道路可能无法通行。用户可能会基于综合考虑路线，如道路速度限制和类型，选择距离较长但行驶时间较短的路线，而不是选择最短距离的路线。因此，如何准确地表示人们的共享出行偏好以同时考虑这两个方面，并与行驶路线相关的路况一起指导轨迹恢复，是一个需要解决的问题。 为了应对上述挑战并实现准确的地图约束轨迹恢复，提出了Micro-Macro Spatial-Temporal Graph-based Encoder-Decoder (MM-STGED)模型。该模型同时融合轨迹的微观语义和宏观语义来指导轨迹恢复。与现有只依赖序列模型利用每个GPS点的显式绝对信息的工作不同，MM-STGED从图的角度建模轨迹，如图2(c)所示。这使得模型能够通过利用图的节点和边来捕获GPS点的显式绝对信息和它们的隐式相对信息。此外，MM-STGED引入了一种新的图卷积机制来聚合节点和边的信息，使其能够同时有效地捕获轨迹的离散性和连续性。为了从一组轨迹中提取宏观语义，根据轨迹数据和道路网络构建一个宏观轨迹流图，代表人们的共享出行偏好。此外，仅依赖可用的轨迹数据来描述路况，从而消除了对外部信息的需求。最后，MM-STGED利用基于图的解码器将宏观语义融入到轨迹恢复任务中。总的来说，本文贡献如下：- 首次从图的视角对轨迹进行建模以执行地图约束轨迹恢复任务。提出了一个新的框架，即MM-STGED，它全面地捕获了轨迹的微观和宏观语义。
- 设计了一个基于图的编码器来建模轨迹的微观语义，该编码器利用节点和边来描述GPS点的显式绝对信息和它们之间的隐式相对信息，同时提出了一种新的图卷积来同时聚合它们。
- 设计了一个基于图的解码器来融入轨迹的宏观语义，该解码器建模并利用人们的共享出行偏好和路况来指导轨迹恢复。
- 在两个真实世界的轨迹数据集，三种不同的采样间隔上进行了广泛的实验，结果显示的方法显著优于最先进的基线方法。
2. 前置定义
轨迹：将轨迹定义为一系列带有时间戳的GPS点，即 ，其中每个轨迹点 ，，表示移动对象在时间戳 时的GPS位置是 。 的采样间隔为 。路网：路网被定义为一个有向图 ，其中 是节点集合代表路段交叉口，每个节点都有 和 属性。 是边的集合代表了连接两个节点的路段。边 由起点路口 和终点路口 决定。地图约束的轨迹点：由于传感器误差，原始轨迹点并不一定严格限制在路网上。为了解决这个问题，定义原始轨迹点 地图约束的轨迹点为 ，其中 ， 表示地图约束的轨迹点所在的路段， 是移动率，表示沿路段移动距离相对于其总长度的比例，例如， 表示点 位于路段 的起点， 表示点 位于路段 的终点。图1 进一步阐述了移动率的定义。根据路段 和移动比例 ，可以计算地图约束的轨迹点 的经纬度，如下所示：-采样间隔的地图约束轨迹：一个 -采样间隔的地图约束轨迹是一系列地图约束的轨迹点序列，定义为 。 代表两个连续地图约束轨迹点之间的时间间隔，即 。称 为 -MM 轨迹。问题定义：给定一个稀疏轨迹 ，其采样间隔为 （例如，图1中的绿色 GPS 点 ）和一个期望的采样间隔 ，目标是设计一个算法来恢复 -采样间隔的地图约束轨迹 ，例如，图1中的红点 。请注意，采样间隔 大于 。在本文中，设置从采样间隔为1分钟、2分钟和4分钟的稀疏轨迹中恢复 秒的地图约束轨迹。3. 模型设计
3.1 模型概述
图3 为提出的MM-STGED模型框架。给定一个采样间隔为 的稀疏轨迹，目标是设计一个端到端模型，恢复相应的 -采样间隔地图约束轨迹。 首先，将稀疏轨迹输入到基于图的轨迹微观语义编码器中，提取其微观语义。在这个模块中，将每个轨迹视为一个图，其中图节点代表GPS点的显示绝对信息，边代表这些点之间的隐式相对信息。然后，使用一种新颖的图卷积机制来更新节点和边，以获得轨迹嵌入，并结合周围的道路网络全面捕获轨迹中嵌入的微观语义信息。 同时，将整体轨迹数据输入到宏观语义提取模块中，以获取宏观级别的信息，包括人类的出行偏好和与出行路线相关的路况。具体来说，根据所有的轨迹，计算两个道路段之间的连续通过次数，并构建一个宏观轨迹流图来表示人类的出行偏好。同时，分别将感兴趣的区域在空间维度上划分为多个网格以及在时间维度上切片，并计算每个单元格内的流量。最后，根据稀疏轨迹的 GPS 点和时空索引，我取与轨迹相关的道路条件。 一旦获得了轨迹的微观和宏观语义，将它们一起输入到基于图的轨迹恢复解码器中，以恢复地图约束的轨迹。在基于图的轨迹恢复解码器中，采用一个基于注意力的 GRU 作为基本组件，以自回归的方式恢复轨迹。在每个解码步中，将与轨迹相关的道路条件、前一步恢复的路段 ID 和移动率 作为输入，并生成当前步的路段 ID 和移动率 。在恢复过程的每一步中，为了缩小恢复路段候选的搜索空间并提高结果的准确性，将 GPS 点分为两类：观察到的和未观察到的 GPS 点。如果当前步骤的 GPS 点是观察到的，将周围的路段作为候选。否则，使用宏观轨迹流图中 的邻居作为候选。3.2 基于图的轨迹微观语义编码器
与之前基于序列模型编码轨迹的轨迹恢复方法不同，将轨迹表示为图，以捕获微观语义信息。具体来说，构建了一个新的轨迹图，其节点对应于轨迹点，边描述了这些点之间的隐式相对信息。然后，设计了一个基于图的轨迹编码器，通过充分利用图的节点和边来嵌入轨迹。3.2.1 微观时空轨迹图构造
对于一个稀疏轨迹 ，使用一个微观时空轨迹图 来表示它，其中每个节点对应于一个轨迹点 ，并且 。 是边集， 和 分别由 和 定义。 和 代表时间成本和空间转移邻接矩阵，第个元素 和 的计算方式如下：其中， 是点 和 之间的距离， 表示轨迹 中距离的方差。每个用户产生的轨迹都展示了与旅行目的和模式相关的固有特性，这导致了轨迹内所有点之间存在时刻相关性。为了全面捕获这些相关性，微观时空轨迹图 是完全连接的。
节点/边特征初始化：初始化节点特征最简单的方法是将每个轨迹点的经纬度输入到MLP中，但这种方法有两个缺点：(1) 轨迹中点之间的纬度和经度差异通常很小，这可能会在预测任务中使模型混淆。(2) 轨迹本质上是连续的，这意味着这些轨迹点不是独立的实体，而是通过时空相关性内在地联系在一起。然而，MLP将输入实体视为独立的，并不考虑它们的相关性。 为了克服这些缺点，首先将感兴趣的区域划分为网格，并将每个轨迹点 表示为一个三元组 ，其中 和 表示 所在的网格单元的索引。 是轨迹点 在所需采样间隔 下的时间索引。引入 的目的是使模型感知在两个连续观察的轨迹点之间需要重构的点的数量。然后，使用门控循环单元 (GRU) 来建模离散轨迹点之间的时间相关性。在处理每个轨迹点 时，GRU接收网格单元索引 ，时间索引 ，以及来自前一步的隐藏状态 作为输入，并产生隐藏状态 作为节点 的初始化特征。 图 中的边揭示了轨迹点之间的潜在隐式相对信息。具体来说，每条边都由两个原始属性特征化，即 ，其中 是连接运算符。使用一个非线性变换将原始边特征投影到 维：其中， 是ReLU激活函数， 和 是可学习的参数。3.2.2 轨迹编码器
图卷积网络（GCNs）被广泛用于编码图结构数据。传统的GCNs只根据拓扑邻接矩阵在节点特征之间进行信息传递，并未考虑丰富的边特征。然而，节点特征和边特征都在描述单个轨迹的微观语义信息中起着关键的作用，这对于轨迹恢复任务是有价值的。因此，精心设计了一种新的图卷积机制，使其同时融合和更新节点和边的信息。 给定微观时空轨迹图 ，联合编码节点和边的嵌入以完全描述微观语义信息。具体来说，边的嵌入 ，受其自身和它连接的节点的影响。同时，节点的嵌入受其自身属性、其邻居以及它们之间的边的影响：其中， 表示节点 的邻居集合。 是聚合函数， 是更新函数。如下所示，其中 表示批量归一化。这里使用残差连接来传递原始节点特征。 和 分别是聚合的时间邻居特征和空间邻居特征，计算如下：其中， 是可学习的参数。由于图 是全连接的，只进行一次聚合过程就能使每个节点感知到其他节点及其边的信息。3.2.3 路网感知层
虽然上述过程有效地将经度、纬度和时间戳作为显式的绝对信息，以及空间转移和时间消耗作为隐式的相对信息融合到轨迹点的表示学习中，但是它并没有对轨迹点周围的路网进行建模，而这也是轨迹微观语义的一个重要方面。正如在第1章中讨论的，路网在影响用户的路线选择方面起着关键的作用。因此，提出了一个道路网络感知层来增强轨迹表示。 具体来说，首先使用宏观轨迹流图（详见第3.3.1节）来表示道路网络，因为这种表示方式能够全面反映路网的物理拓扑结构和人类的出行偏好。然后使用Node2vec来学习路段的表示 ，其中表示道路段的数量。对于每一个观测到的轨迹点，定义一个距离加权函数来量化和道路段之间的关联。函数的公式为：其中， 是点 和路段 之间的最短距离， 是一个超参数。显然，函数 只考虑到距离 在阈值 以下的道路段，而忽略了距离 超过这个阈值的路段。然后，通过以下方式获取每个轨迹点 的路网表示 ： 最后，将轨迹编码器输出的每个轨迹点的表示和路网感知层输出的表示连接起来，然后采用非线性变换得到每个轨迹点的最终表示 ，其中， 和 是可学习的参数。最后，使用一个平均池化层来读取整个轨迹的嵌入。3.3 宏观语义提取模块
为了有效提取一组轨迹所反映的宏观语义信息，本文提出：模拟人类旅行偏好的宏观轨迹流图，以及描述所研究轨迹环境的路况表示。3.3.1 宏观轨迹流图构建
宏观轨迹流图的设计旨在以全局的视角提供人们旅行偏好的。如图4(a)所示，首先基于隐马尔可夫模型(HMM)对所有观测到的轨迹进行地图匹配，将轨迹点序列转换为路段序列。在这种转换之后，根据用户的路段选择构建宏观轨迹流图。- 是边集。如果存在一条轨迹依次经过道路 和道路 ，则从 到 有一条边。此外，为每个节点添加自连接。
- 是权重矩阵。 中的 等于轨迹依次经过道路 和道路 的总次数。
3.3.2 上下文路况表示
在现实中，出行路线的选择和相应的旅行模式（如速度）本质上是动态的，并受实际路况的影响。例如，当前路线拥堵拥堵可能会迫使驾驶员降低速度，甚至寻找其他路线，这两者都将影响轨迹。鉴于此，我们将路况的影响纳入所提出的模型中，从而模拟所研究的轨迹的环境。 为了获取路况信息，如图4(b)所示，将感兴趣的区域在空间维度上划分为 个网格单元，并将时间范围划分为 个时间步。通过分析历史轨迹记录，得到了每个单元的交通流量，由矩阵 表示。为了表征道路状况的时空相关性，在时间维度上使用一维卷积（1D CNN），在空间中使用二维卷积（2D CNN）来处理 。最后，得到了所有网格单元的路况表示 ，其中 是道路状况嵌入的维度。 考虑到轨迹是在特定的时间段发生，并且只覆盖特定区域，为了避免信息冗余，选择性地提取与轨迹紧密相关的路况信息，使用以下聚合公式：其中，、、 表示将纬度、经度和时间映射到相应索引的索引函数。然后，轨迹相关的道路状况 在轨迹恢复过程中被利用，从而使模型能够捕捉轨迹的动态性。3.4 基于图的轨迹恢复解码器
在编码器充分处理轨迹之后，解码器以自回归的方式恢复-MM轨迹。为此，选择GRU作为基础组件。 在每个时间步，输入到GRU的内容包括两部分：前一步的隐藏状态，以及当前步的输入。当前步的输入包括路段的嵌入和前一步输出的移动率，轨迹相关的上下文路况表示，以及从编码器输出的加权轨迹表示。由于稀疏轨迹中的不同点对恢复-MM轨迹点的贡献不同，这里引入一个全局注意力机制，该机制根据每个轨迹点对当前解码步骤的相关性对其贡献进行加权，公式如下：其中，，， 是可学习的参数。 是节点 的图卷积输出。第一个隐藏状态 由编码器生成的轨迹嵌入初始化。一旦GRU在时间步 产生了隐藏状态 ，就可以根据 预测相应地图约束轨迹点的路段和移动率。 预测路段的直接方法是将所有道路段视为候选，然后进行多分类。然而，这种方式会浪费不必要的计算，并增加找到正确道路段的不确定性，因为许多路段不可能是正确的答案。实际上，轨迹是由人们的出行生成的。从宏观角度看，人们有特定的出行模式，这是一种先验知识，生成的轨迹也应遵循这些特定的模式。因此，可以利用宏观语义信息来缩小路段候选的范围。 对于在采样间隔 下在时间步 处恢复的轨迹点，它与原始轨迹 的关系有两种情况：- Case 1：在时间步 观测到GPS位置。即 ，其中 是原始稀疏轨迹 中的第 个采样点。
- Case 2：在时间步 没有观测到GPS位置。即 。
对于Case 1，理论上， 应该位于某条道路 上。但在现实中，由于GPS设备误差， 可能会与道路 有轻微的偏差，如图1 所示。因此，使用距离来选择路段候选，通过这种方式可以减少搜索空间，提高模型的效率和准确性。在这里，使用公式9 中定义的权重函数 来表示 和道路段 之间的关联，并选择离 不远的道路段作为候选。 对于Case 2，不知道轨迹点的GPS位置，所以不能直接计算它到每个道路段的距离。因此，依赖于前一时间步的预测路段 和宏观轨迹流图 来指导轨迹恢复。即，当在时间步 进行预测时，选择节点 在 中的邻居作为候选，因为人们的出行习惯倾向于遵循全局转移偏好。可以按照以下方式定义时间步 恢复轨迹点与路段 之间的关联性：其中， 是可训练参数 的第 列向量。获取每个道路段的概率后，使用 函数获取时间步 的预测路段 。随后，将GRU隐藏状态 和 的嵌入输入到两层 MLP 以及 Sigmoid 激活函数中，以获得移动率 。路线和用户信息融合：在实际场景中，用户的个性化偏好以及在时间步 之前经过的路段对于时间步 的轨迹恢复是有帮助的。因此，在每一步，利用这些信息来丰富解码器的隐藏状态 。考虑到路段之间的拓扑关系，首先在宏观轨迹流图 上使用 Node2Vec 算法来获取每个路段的嵌入 。然后，将用户的嵌入 （随机初始化的可学习向量）、当前步隐藏状态 和先前经过的道路段的嵌入进行拼接，用来替换公式17中的 。形式上：3.5 模型训练
同时优化路段预测和移动率预测任务来训练模型。交叉熵被用作道路段预测的损失函数：其中， 是 -MM 轨迹的长度。对于移动率预测，采用均方误差作为损失函数：最终损失函数是 ，其中 是一个超参数，用于平衡上述损失。4. 数据集和实验结果
使用两个公开的出租车轨迹数据集，数据分别来源于波尔图和成都。将数据集的采样间隔设置成15秒，并删除过短和过长的轨迹，以及剔除异常轨迹。使用道路匹配算法得到真实标签用于模型训练。 本文通过上采样，在两个数据集上分别构造了3种稀疏轨迹，他们的采样间隔分别为4分钟，2分钟，1分钟，用于恢复15秒采样间隔的轨迹，实验结果如下表。 此外，还分析了模型不同组件的影响，包括在微观语义信息中，删除图编码器（w/o GCN）,删除路网感知层（w/o RN），在宏观语义中，删除路况（w/o RN），删除轨迹流图（w/o TLG），以及删除用户信息（w/o User）。实验结果如下：选择了4个重要的参数在两个数据集上探索了参数对模型性能的影响：5. 总结
本文提出了MM-STGED，一种用于地图约束轨迹恢复的端到端编码器-解码器方法。MM-STGED从图的视角建模轨迹，以描述微观语义信息，同时捕获每个GPS点的显式绝对信息和它们的隐式相对信息。并且提出了一种新的图卷积，同时汇集节点和边的信息。此外，提取了由一组轨迹反映的宏观语义信息，然后通过基于图的解码器有效地恢复轨迹点。实验结果表明，MM-STGED的性能优于最先进的基准。
