(1)
北京大学学报(自然科学版) 第60卷 第6期 2024年11月
Acta Scientiarum Naturalium Universitatis Pekinensis, Vol. 60, No. 6 (Nov. 2024)
doi: 10.13209/j.0479-8023.2024.087
中央高校基本科研业务费和腾讯犀牛鸟大出行专项研究计划资助
收稿日期: 2023–12–01;
修回日期: 2024–01–25
摘要 现有的地图匹配方法主要依赖序列到序列模型来捕获轨迹内关联性, 忽略路段间、轨迹间以及轨迹与路段间的关联性。同时, 现有方法采用的循环神经网络因其固有结构, 难以进行高效的并行计算。为了充分利用数据中存在的多种关联性, 并提升模型的并行计算能力, 提出一种融合图结构学习和轻量级循环建模的地图匹配方法(GMMSR)。通过路网卷积和轨迹图卷积, 建模路段之间和轨迹之间的关联性, 采用在隐空间对齐路网和轨迹表示的方式, 建模轨迹与路段之间的关联性。利用轻量级循环单元实现模型更高效的并行计算。在北京市某区域轨迹路网数据集上的实验结果表明, 所提模型较已有基准模型在精度上实现大幅度提升, 在效率上相当或更好。
关键词 地图匹配; 轨迹和路网关联性; 图神经网络; 轻量级循环单元
地图匹配任务将车辆产生的轨迹与路网进行匹配, 经算法修正后得到匹配行驶轨迹的路段序列。地图匹配在诸如行程时间估计、日常通勤数据挖掘以及导航等方面有着广泛的应用。Newson 等[1]将轨迹作为观察, 路段作为隐状态, 将隐马尔科夫模型(Hidden Markov Model, HMM)应用于地图匹配问题上, 比以往基于几何信息的匹配算法在匹配精度上有很大的提升。在此基础上, 刘旻等[2]引入可靠点的概念, 将每个轨迹分割成不同的增量, 对每个增量应用 HMM 进行地图匹配, 这种处理方式使得转移概率的计算量减少, 从而缩短匹配结果的输出延迟, 提升了算法效率。近些年, 随着深度学习的兴起, 序列到序列(sequence-to-sequence, Seq2Seq)的解决方案[3–8]被引入地图匹配任务中, 并取得最先进的性能。这种编码器–解码器架构采用循环神经网络(recurrent neural network, RNN)或 Transfor-mer[9]作为基础组件, 编码器首先对稀疏的 GPS 轨迹进行编码, 然后解码器通过自回归的方式恢复高采样率轨迹, 并将恢复的轨迹匹配到路网上。
然而, 已有的工作在计算精度和效率方面都有一定的局限性。基于 HMM 的方法只在高采样率轨迹上效果较好, 且推断速度慢。基于 Seq2Seq 的解决方案受所使用序列模型的限制, 仅能捕获前后轨迹点间的时序依赖关系, 即轨迹内关联性。此外, 传统循环单元每个时间步的计算都依赖前一个时间步的结果, 使得基于 RNN 的地图匹配模型的并行计算能力较弱。在地图匹配任务中, 现有研究并没有充分发掘路网和轨迹中所蕴含的信息, 包括路网路段间关联性、轨迹间关联性以及轨迹–路网关联性。路段间关联性指匹配序列中前后的路段在路网上要可达, 故应当具有相似的特征表示; 轨迹间关联性指相似的轨迹能相互矫正, 即轨迹可以利用相似轨迹中的轨迹点来纠正不合理的预测; 轨迹–路网关联性指轨迹点的特征表示应当与其对应的真实路段的嵌入表示在隐空间中更相似。
为此, 本文提出一种基于图增强和轻量级循环建模的地图匹配模型(graph-enhanced map matching model with simple recurrence, GMMSR)。该模型基于编码器–解码器架构, 但在模型结构设计上实现以下改进。首先, 利用路网和轨迹图上的图卷积来捕获路段间关联性和轨迹间关联性, 从而得到更有效的轨迹和路段向量表示。其次, 引入轻量级的循环单元(simple recurrent unit, SRU), 实现在不降低序列建模能力的前提下, 通过解耦不同隐状态维度间的计算来提高模型的并行化能力。在解码过程中, 使用向量点积对齐轨迹点隐向量和路段嵌入表示, 计算轨迹点匹配到每个路段的概率。通过这种方式, GMMSR 能够消除最终用于分类的全连接层, 从而显著地减少模型参数量, 提高效率。此外, 也使得 GMMSR 具备归纳(inductive)能力, 当路网变化时, 无需重新训练。最后, 在北京市某区域的轨迹路网数据集 Tencent8.5K 上进行性能对比和消融实验, 验证 GMMSR 的计算精度和效率。
目前关于地图匹配的方法大致分为两大类: 基于 HMM 的方法和基于 Seq2Seq 的方法。基于 HMM的方法[1–2]将轨迹作为观测值, 路段作为隐状态。具体地, 给定长度为 l 的轨迹 T=(p1, …, pl), HMM 通过最大化 T 和 R 之间的联合概率 P(T, R)来获取长度为 l 的预测路段序列 R=(r1, …, rl):
(1)
其中, 初始状态概率 π(r1)服从路段上的均匀分布; 发射概率 P(pi|ri)和转移概率 P(ri+1|ri)则根据预先定义的估计行驶距离概率分布进行设置, 仅包含少量可学习参数。
在预测过程中, 基于 HMM 的方法需要使用维特比算法进行解码。基于 HMM 的方法仅通过一些简单的距离分布进行预测, 无法从轨迹数据中捕获复杂的时空模式, 使得此类方法在稀疏轨迹上的应用效果较差。此外, HMM 的计算模式也使得其推断速度较慢。
基于 Seq2Seq 的方案[3–8]都遵循如下的编码器–解码器架构, 并将地图匹配建模为多分类问题:
hT=SequenceEncoder(T), (2)
R=SequenceDecoder(hT)。 (3)
首先, 序列编码器对输入轨迹 T 进行编码, 获取 T 相应的上下文向量表示 hT。然后, 序列解码器利用 hT, 以自回归的方式得到地图匹配的轨迹 R。在编码器–解码器架构中, 广泛采用基于 RNN 或Transformer[9]的序列建模技术。使用 RNN 时, 可以进一步融入注意力机制[10]。引入注意力机制可以减少将整个输入轨迹序列压缩为单个向量时造成的信息损失, 因为它能在每个解码步中自适应地选择对当前解码最重要的输入部分。由于是多分类, 一般基于交叉熵损失函数进行模型优化。
在基于 Seq2Seq 的工作中, MTrajRec[3]是一种基于 RNN 的代表性解决方案。MTrajRec 将门控循环神经网络(gated recurrent unit, GRU)作为基础组件, 并整合注意力机制、约束掩码层和多任务学习框架。约束掩码层通过设定距离阈值来过滤距离当前轨迹点过远的路段, 从而减少不合理的预测。
多任务指在解码过程中需要同时预测匹配的路以及移动率(轨迹点在当前路段上行进的比例)。Jina 等[8]将 Transformer 引入地图匹配任务中。由于缺少带标签的轨迹数据, 他们提出一种基于路网的轨迹生成方法, 并利用生成的轨迹数据对 Transfor-mer 进行预训练。为了减小生成数据与真实轨迹数据之间的差异, 还使用少量真实数据对预训练后的Transformer 进行微调, 并将该模型应用于测评。现有的 Seq2Seq 方案只能捕获轨迹点间的序列关联性, 而且大部分代表性工作都采用 RNN 作为基础组件, 计算效率不高。
目前, 随着图神经网络(graph neural network, GNN)[11–17]的不断发展, 在节点分类、链接预测和图分类等任务中取得巨大成功。通过 GNN, 图节点可以获得融合了节点特征、边特征和图结构的嵌入表示。从图拓扑结构的角度, GNN 可概括为消息传递(message passing, MP)范式[11], 即每个图节点迭代地聚合来自邻居节点的消息, 并结合自身的特征, 生成自己新的消息表示。大多数遵从消息传递范式的 GNN 可以通过如下计算过程来描述:
(4)
(5)
其中, N(v)表示节点 v 的邻居节点集, 
表示节点 v 在第 l 层的隐藏层表示, evw 表示节点 u 与节点 v之间边的特征, Mt 表示消息函数, Ut表示节点消息聚合函数。
如何提升序列建模效率的研究一直备受关注, 目前代表性工作主要包括基于卷积神经网络(con-volutional neural network, CNN)、基于循环神经网络(recurrent neural network, RNN)改进和基于 Trans-former 的方案。Gehring 等[18]首次提出基于 CNN 的Seq2Seq 方案, 充分发挥了 CNN 并行计算的优势, 同时 CNN 的层级结构也有利于发现序列中的结构信息。Bradbury 等[19]使用 CNN 代替传统的循环单元, 使得模型既具备 CNN 高效并行计算的优势, 又能像 RNN 一样建模时序依赖关系。Wang 等[20]提出名为 genCNN 的全新 CNN 架构, 能有效地结合语言的局部和长距离结构来建模当前预测词的条件概率。Diamos 等[21]利用图形处理单元(graphics procs-sing unit, GPU)缓存 RNN 参数, 实现 RNN 在小批量数据上的高计算吞吐量。Kuchaiev 等[22]采用矩阵分解和分组计算两种方式对长短期记忆网络(long short-term memory, LSTM)进行改进, 减少 LSTM 的参数量, 加快模型的训练速度。Lei 等[23]对传统的循环单元进行改进, 提出 SRU, 通过解耦序列状态不同维度间的计算, 在不牺牲模型表达能力的前提下, 实现比传统循环单元更高的并行计算性能。Vaswani 等[9]提出 Transformer 架构, 用多头自注意力机制替代传统编码器–解码器架构中的卷积层或循环层。相较于 CNN 和 RNN, 自注意力机制使得Transformer 能够更好地捕获序列的长距离依赖关系, 并提高并行计算效率。在 Transformer 的基础上, Wu 等[24]设计基于序列周期性的自相关机制, 在子序列层面上进行依赖关系发现和表示聚合。对于长度为 L 的序列, 该机制将 Transformer 中 O(L2)的时间复杂度降低到 O(LlogL)。
给定路网 GR 和稀疏轨迹集{Ti, …, TS}, 地图匹配指将每条轨迹 Ti=(p1, …, pl)匹配到路网中, 得到对应的匹配路段序列R=(u1, …, ul'), R称为地图匹配的轨迹。
2.1.1 路网
路网用有向图 GR=(VR, εR)表示。节点集 VR 表示路网上的路段集合, ui∈VR表示路网路段, 路段的初始特征为其起点和终点的 GPS 坐标。边集 εR 反映路网路段之间的邻接关系, eij=(ui, uj)∈εR表示路段 ui 与路段 uj 相交且方向为 ui 到 uj。
2.1.2 轨迹
轨迹由一系列轨迹点组成, 用 T={p1, …, pl}表示, 其中 pi 表示轨迹点, 每个轨迹点都对应一个经纬度坐标(lati, lngi)和时间戳 t。在许多地图应用中, 轨迹点的采集使用固定的时间间隔 ε, 当采样间隔时间 ε 较大时(例如 30 秒), 将采集的轨迹称为稀疏轨迹。
2.1.3 轨迹图
轨迹图 GT=(VT, εT)基于轨迹集构建。给定轨迹集{T1, …, TS}, 将路网区域划分为二维网格, 利用函数 Grid(·)将轨迹点映射到网格上, 映射结果
即为节点集 VT。相应地, 根据所有轨迹中前后轨迹点对的邻接关系, 可以构造边集 εT。具体来说, 给定任意轨迹 Tk={p1, …, px, px+1, …, pl}, k∈{1,…, S}, 轨迹上的前后轨迹点对(px, px+1)可以转换为 εT 中的边 eij=(vi, vj), 其中vi=Grid(px), vj=Grid(px+1)。eij 是带权的, 边权为wij=|{(px, px+1)|Grid(px)=vi, Grid(px+1)=vj}|, 其含义是(vi, vj)在轨迹集中共现的频率。
图 1 为一个典型的轨迹图构造示例。图 1(a)包含轨迹 T1=(p11, p12, p13)、轨迹 T2=(p21, p22, p23)和11 个路段 u1～u11。据此构造的轨迹图为图 1(b), 轨迹图的节点集为{v1, v2, v3, v4, v5}, 边集为{(v1, v2), (v1, v4), (v2, v3), (v4, v5)}, 其中 Grid(p11)=Grid(p21)=v1, Grid(p12)=v2, Grid(p13)=v3, Grid(p22)=v4, Grid(p23)=v5。
GMMSR 采用编码器–解码器架构, 模型分为图增强的轨迹编码器和基于图的解码器两部分, 基本架构如图 2 所示。给定路网 GR、构造的轨迹图GT和轨迹 T, 图增强的轨迹编码器利用 GNN 先后进行路网卷积和轨迹图卷积, 用于捕获路段与轨迹间的关联性, 之后经轻量级循环建模, 得到最终的轨迹表示 hT。借助隐向量相似性计算, 基于图的解码器, 使用轻量级循环单元 SRU, 根据 hT 解码, 并预测得到匹配的路段序列 R。
图1 轨迹图构造示例
Fig. 1 A toy example of trajectory graph construction
图2 GMMSR架构
Fig. 2 Architecture of GMMSR
图增强的轨迹编码器包含路网卷积、轨迹图卷积和轻量级循环建模三部分。
2.3.1 路网卷积
借助路网卷积, 路段的嵌入表示能够融合路网的结构信息。给定路网 GR=(VR, εR), 对于 GR的每个路段 u, 其初始特征为路段的起始 GPS 坐标, 用
表示。利用 L 层 GIN[15]图卷积, 可以获取路网路段的最终嵌入表示
。第l∈{1, …, L}层卷积的计算公式如下:
(6)
其中, MLP(l)表示多层感知机, ε(l)表示第 l 层的可学习参数。组合所有路段 u 的最终嵌入
, 可得路网的嵌入矩阵
, 其中 nR 表示路网的路段数, HR在后续用于隐向量相似性计算。
2.3.2 轨迹图卷积
根据 2.1 节描述的方法, 可以通过轨迹数据以及特定路网区域来构建相应的轨迹图 GT。为了增强轨迹图节点的特征, 对划分后的网格
, 我们首先利用与其相交的路段的特征来增强其初始化表示
:
(7)
其中, Mean 表示平均池化, CONCAT 表示向量拼接操作, intersects 表示路段落在相应的网格中。通过这种方式, 轨迹图能够融合路网表示, 有助于在隐空间内对齐轨迹和路网。
对于轨迹图, 采用 GCN[12]进行图卷积操作, 轨迹图卷积能够使得轨迹点聚合邻近相似轨迹上的信息, 提高轨迹点表示的准确性。由于轨迹图是带权的, 需要对 GCN 的传播公式进行细微的修改。对于 L′层轨迹图卷积, 第 l层的传播公式如下:
(8)
其中, 
和
表示第 l 层可学习的参数矩阵, N(v)中不包含 v。轨迹图卷积后, 网格 v 的特征表示为
。对轨迹图上的轨迹点特征进行汇集, 可得轨迹图节点嵌入矩阵 HT。对于轨迹 T 上的轨迹点pi, 利用 Grid(·)函数对pi进行映射, 根据索引从 HT中取出相应的轨迹点表示, 即 hpi=HT[Grid(pi)]。
2.3.3 轻量级循环建模
给定输入轨迹 T 的表示序列{hp1, …, hpl}, 本模块利用循环单元来捕获轨迹的序列关联性。鉴于传统循环单元的计算效率瓶颈, 模块选择轻量级循环单元 SRU[23], 单层 SRU 的计算公式为
(9)
(10)
(11)
(12)
其中, Wf, Wr, W, vf, vr, bf和 br 都是可学习的参数, ⊙表示哈达玛积。与传统循环单元不同, SRU在状态计算过程中用哈达玛积替代矩阵乘法, 使得状态不同维度间的计算解耦, 从而提升并行计算效率。为方便表述, 下面用 SRU(·)表示式(10)～(13)对应的计算过程。为充分利用轨迹序列的上下文信息, 轨迹内关联性建模采用双向 SRU 来同时捕获前向和后向信息:
(13)
其中
表示编码器第 t 步对应的隐向量, 序列的最终编码输出用
表示。
基于图的解码器, 利用轨迹 T 编码后的隐向量表示 hT, 预测得到匹配的路段序列。除使用 SRU 作为基础循环单元来提升解码效率外, 解码框架与MTrajRec[3]基本上一致。另外, 以往的分类模型通常使用全连接层对解码隐向量进行映射分类。对地图匹配任务而言, 这种方式会引入海量的学习参数。假设隐向量维度为 384, 路网包含的路段数为8500, 仅该全连接层就会引入超 300 万的参数量。这也是基于 Seq2Seq 的地图匹配解决方案训练和推断效率低下的主要原因。
针对此问题, 我们提出用隐向量相似性计算来替代传统的全连接层分类。具体地说, 给定第 i 步解码输出的隐向量
, 通过矩阵乘法计算当前轨迹点匹配到各路段的概率:
(14)
通过这种方式, GMMSR 能够通过模型优化, 在隐空间内对齐轨迹表示和路网嵌入。隐向量相似性计算也为模型带来归纳能力, 即使路网改变, 同样可以直接应用 GMMSR 进行预测。
我们将地图匹配建模为多分类任务, 其中类别为路网路段, 采用交叉熵进行模型优化:
(15)
其中, Tr表示训练轨迹集, T和R表示成对的轨迹和匹配路段序列, yi=(yi1, …, yinR)表示 R 上第 i 个位置的真值对应的独热码, 
为 yik 对应的预测概率。
3.1.1 数据集
本文使用的数据集 Tencent8.5K 来自腾讯地图, 该数据集包含北京市 8.68km
7.67km 区域 3 个月内的部分车辆轨迹数据和路网。路网包含 8.5K 路段和 15K 条边。整个数据集拥有 64K 条轨迹, 轨迹的采样间隔 ε 为 15 秒。数据集按 7:1:2 划分训练集、验证集和测试集。为获得稀疏轨迹, 按 50%, 25%和12.5%的重采样率对原始轨迹进行采样, 模拟 30 秒、1 分钟和 2 分钟的采样间隔。原始轨迹上的每个轨迹点都是独立采样。
3.1.2 对比模型
针对基于 HMM 的方法和基于 Seq2Seq 的方法, 我们各选择最具代表性的解决方案作为对比基线。
1)HMM: 采用腾讯地图提供的隐马尔科夫模型的工业优化版本。该模型在发射概率的计算过程中同时考虑GPS坐标到路段的距离以及轨迹路段方向的一致性。在模型转移概率的计算过程中, 仅以距离轨迹点 200 米范围内的路段作为候选集, 排除大量不相关的路段, 显著地减少计算量, 提高计算效率。
2)MTrajRec 和 MTrajRec w/o CM: 基于 RNN 的代表性方案, 我们沿用 Ren 等[3]的实现方式, 但根据实际情况对模型进行细微的修改。由于 Tencent 8.5K 无法获取移动率, 因此多任务学习框架被移除。另外, Tencent8.5K 未提供额外的属性信息(如天气情况和 POI 分布等)。对于该模型, 我们还额外对比不添加约束掩码层的变体 MTrajRec w/o CM, 约束掩码层对模型的贡献很大, 但会严重地拖累效率。
3)Transformer-based MM (Map Matching): 基于Transformer 的地图匹配模型[8], 我们复现 Jina 等[8]的工作, 并对其进行改动, 以提升性能。在实际训练中, 我们发现仅使用轨迹 GPS 映射得到的空间特征作为 Transformer 的输入表现不佳, 因此将路网区域划分为相同大小的网格, 并为每个网格定义可学习的嵌入向量。对于输入的轨迹序列, 先将其映射到网格上, 然后取出对应的嵌入向量。另外, 我们并未采用先基于规则生成轨迹, 然后进行预训练微调的做法, 而是直接利用 Tencent8.5K 中大量带标签的真实轨迹数据, 对 Transformer 进行充分训练。由于预训练与微调的任务相同, 并且真实数据量足够, 因此可以不使用生成轨迹进行预训练。
需要说明的是, 我们未考虑其他基于 RNN 的方案(如 DeepMM[4–5]和 DHTR[7])作为对比基线, 原因是这些模型的主体框架与 MTRrajRec 类似, 且预测准确率低于 MTrajRec。
3.1.3 评价指标
根据腾讯地图实际业务场景的需求, 采用准确率 Accuracy 和最长公共子序列比率 R-LCS (ratio of longest common subsequence)作为评价指标。给定轨迹集TS={T1, …, TS'}, Ti=(pi1, …, pili)表示单条轨迹, S'表示轨迹总数, li 表示轨迹 Ti的长度, 则单条轨迹的 Accuracy 和 R-LCS 的计算公式为
(16)
(17)
其中, I(A)表示指示变量, 若条件 A 为真, 则取 1, 否则取 0。LCS 用来求两个序列的最长公共子序列的长度。基于式(18)和(19), 可得全量轨迹上相应指标的计算公式:
(18)
(19)
3.1.4 模型的实现
GMMSR 基于 PyTorch 和 PyTorch Geometric 来实现。对于 MTrajRec, 在 Ren 等[3]提供的源代码基础上, 根据实际情况进行修改。实验超参数基本上沿用 MTrajRec 的默认配置。为了获取更好的收敛结果, 将学习率修改为 0.0005, 训练迭代轮数修改为 100。对于复现的 Transformer-based MM, 我们在实际训练中发现, 在层数为 2, 嵌入大小为 384 的配置下, 训练迭代 100 轮模型能够达到最佳性能。对于 GMMSR, 学习率设置为 0.0001, 隐向量维度大小设置为 384, 将采用 Adam 作为优化器, 训练共迭代 200 轮。所有实验都在包含两张 NVIDIA Ge-Force RTX 3090 Ti 显卡的 Ubuntu 服务器上进行。
在 Tencent8.5K 数据集上比较 HMM, MTrajRec, Transformer-based MM 和 GMMSR 的预测精度, 结果见表 1。可以看出, HMM 基本上不受采样率的影响, 我们猜测这是工业实现中各种优化的结果。受限于模型的表达能力, HMM 无法从轨迹数据中捕获复杂的时空模式, 因此其性能明显低于基于深度学习的方法。对于 MTrajRec, 约束掩码层对模型精度提升有重要贡献。Transformer-based MM 在 50%采样率下的性能与 MTrajRec 相当, 但在 25%和 12.5%采样率下的性能却明显不如 MTraj-Rec。这可能是因为在更低的采样率下, Tranformer 更容易过拟合。此外, Transformer 在训练过程中完全依赖真值的指导, 但在推断时只能进行自回归解码, 这种训练和推断模式间的差异也会导致模型的泛化能力较弱[25]。对比众多基线, GMMSR 具有明显的性能优势。在准确率上, GMMSR 在 50%, 25%和 12.5% 采样率设置下相较于次优的模型分别提升 4.09%, 4.47%和 5.86%。在 R-LSC 上, 也分别提升 3.14%, 1.61%和 1.1%。
此外, 实验中还评估了 GMMSR 在归纳设置下的性能。归纳设置下, 训练仅使用训练轨迹集构造轨迹图, 路网同样仅选择恰好能覆盖训练轨迹集的部分。在推断时, 需要将测试轨迹集及其对应的额外路段分别添加到轨迹图和路网上。由于 HMM 不需要训练, 因此它在两种设置下性能相同。MTraj-Rec 和 Transformer-based MM 不具备归纳能力, 因此在归纳设置下不将二者考虑在内。从表 1 可以看出, 在归纳设置中, GMMSR 在 50%, 25%和12.5%重采样下, 准确率仅分别下降 1.07%, 1.53%和 0.82%, R-LSC 仅分别下降 0.31%, 1.37%和 0.59%, 足以表明 GMMSR 具备较强的归纳能力。
图 3 展示采样率为 50%时, 不同模型的每轮训练时间和推断时间。由于 HMM 不需要训练, 因此未提供其训练耗时。由图 3 可以看出, 在效率方面, Transformer-based MM > GMMSR > MTrajRec w/o CM > MTrajRec > HMM。由于 Transformer-based MM 的自注意力机制可以同时计算所有时间步之间的关系, 因而实现高度的并行计算。GMMSR 采用轻量级循环单元 SRU 和隐向量相似性计算来提高效率。尽管 GMMSR 在效率上略逊于 Transformer-based MM, 但它比基于传统 RNN 的方案快得多, GMMSR 的训练(推断)速度要比 MTrajRec w/o CM快 9 倍(14 倍)。从效率的角度看, 探索基于 Trans-former 的 Seq2Seq 地图匹配解决方案非常有必要, 但并不意味着简单地替换编码器–解码器框架中的基础组件。根据表 1 的结果, 需要解决因引入 Trans-former 后训练与推断模式不一致导致的泛化性能差的问题, 这个问题留待后续工作中进一步研究与讨论。此外, 图 3 也表明约束掩码层会严重地拖累MTrajRec 的训练测评速度。
表1 直推式和归纳式设置下的预测精度
Table 1 Prediction accuracy under transductive and inductive settings
实验设置模型50% (30 s)25% (1 min)12.5% (2 min)Accuracy(T)R-LCSAccuracy(T)R-LCSAccuracy(T)R-LCS 直推HMM0.36550.41620.34430.37900.35190.3726 MTrajRec w/o CM0.55890.63800.41930.55400.29820.4724 MTrajRec0.61540.67520.49920.59970.37060.5071 Transformer-based MM0.62160.66680.42560.54650.36190.4772 GMMSR0.66250.70660.54390.61580.42920.5181 归纳GMMSR (Inductive)0.65180.70350.52860.60210.42100.5122
说明: 对于直推式设置, 分别用粗体和下划线表示最优和次优的结果。
图3 测试集上的每轮训练时间和推断时间对比
Fig. 3 Training time per epoch and inference time on test sets
为了验证所设计模块的有效性以及超参对性能的影响, 本文对网格大小、隐向量维度大小以及GMMSR 的重要模块进行消融实验。所有实验都在重采样率为 25%的设置下进行。图 4 展示在 5, 20, 50 和 100 这 4 组不同大小网格下, MTrajRec 和 GM-MSR 的精度变化趋势。可以看出, 缩减网格大小(默认值为 50m)可以提升 MTrajRec 和 GMMSR 的精度, 增加网格大小会使得模型性能变差, 表明细粒度的网格划分能保留更精确的地理信息。图 5 显示不同隐向量维度对应的精度, 结果表明, 在一定范围内增大嵌入的维度有助于提高模型的精度。然而, 与计算开销相比, 过大的嵌入维度带来的精度提升并不显著, 因此需要在精度和计算效率之间进行权衡。
为了验证 GMMSR 所提模块的有效性, 对路网卷积、轨迹图卷积、循环单元模块进行消融实验。图 6 中, GMMSR-RC 和 GMMSR-TC 分别表示将路网卷积模块和轨迹图卷积模块替换为相同层数和隐藏层维度大小的多层感知机。GMMSR(GRU)表示将 SRU 替换为传统的 GRU。由对比可知, 路网卷积对模型精度提升的贡献度最大, 表明在地图匹配中考虑路网是必要的。轨迹图卷积和 SRU 模块同样有助于提升模型的预测精度。对于 SRU 和 GRU, 除图 6 展示的精度对比外, 实验中还额外测量隐藏层维度大小为 384 和 768 两种情况下模型进行一轮训练的前向传播和反向传播总耗时(Forward+Back-ward)以及循环单元编码解码总耗时(RNN Runtime), 结果见表 2。可以看出, 在相同隐藏层嵌入维度下, SRU 在计算效率上略优于 GRU。当嵌入维度增大时, SRU 模块的计算耗时几乎没有增加, GRU 模块的计算耗时则增加 40%。这主要是因为 SRU 解耦了不同隐状态维度间的计算, 当轨迹长度不变时, 其效率优势更加明显。
图4 预测精度随网格大小的变化
Fig. 4 Prediction accuracy varying with grid size
图5 隐向量维度对预测精度的影响
Fig. 5 Impact of hidden dimension on prediction accuracy
表2 SRU与GRU效率对比(s)
Table 2 Efficiency comparison between SRU and GRU (s)
模型隐藏层维度=384隐藏层维度=768Forward+BackwardRNN RuntimeForward+BackwardRNN Runtime GMMSR31.623.1544.693.24 GMMSR (GRU)34.514.9750.826.99
图6 模块消融
Fig. 6 Module ablation
本文提出一种融合图结构和轻量级循环建模的地图匹配方法 GMMSR。为了充分利用路网和轨迹数据中所蕴含的复杂时空模式, 采用图神经网络来挖掘路网和轨迹间的关联性。与其他 Seq2Seq 的方案中直接使用传统循环单元来捕获轨迹内关联性相比, GMMSR 引入更轻量级的 SRU 作为序列建模的基础单元。在不牺牲性能的前提下, 模型的效率有所提升。在 Tencent8.5K 数据集上的实验结果表明, 相较于已有的 HMM 模型和 Seq2Seq 模型, GMMSR在精度上有显著的提升, 并且在训练和推断效率上也表现良好。未来, 我们将继续探索地图匹配问题中的可扩展性和精度, 提出适用于大规模路网和长轨迹上兼顾效率和表达能力的解决方案。
参考文献
[1] Newson P, Krumm J. Hidden Markov map matching through noise and sparseness // Proceedings of the 17th ACM SIGSPATIAL international conference on advan-ces in geographic information systems. Seattle, 2009: 336–343
[2] 刘旻, 李梅, 徐晓宁, 等. 一种基于HMM模型改进的地图匹配算法. 北京大学学报(自然科学版), 2018, 54(6): 1235–1241
[3] Ren H, Ruan S, Li Y, et al. MTrajRec: map-constrained trajectory recovery via Seq2Seq multi-task learning // Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. Singapore, 2021: 1410–1419
[4] Zhao K, Feng J, Xu Z, et al. DeepMM: deep learning based map matching with data augmentation // Pro-ceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Chicago, 2019: 452–455
[5] Feng J, Li Y, Zhao K, et al. DeepMM: deep learning based map matching with data augmentation. IEEE Transactions on Mobile Computing, 2022, 21(7): 2372– 2384
[6] Park SH, Kim B, Kang CM, et al. Sequence-to-sequen-ce prediction of vehicle trajectory via LSTM encoder-decoder architecture // IEEE Intelligent Vehicles Sym-posium (IV). Changshu, 2018: 1672–1678
[7] Wang J, Wu N, Lu X, et al. Deep trajectory recovery with fine-grained calibration using Kalman Filter. IEEE Transactions on Knowledge and Data Enginee-ring, 2019, 33(3): 921–934
[8] Jina Z, Choia S, Yeoa H. Transformer-based map mat-ching model with limited ground-truth data using transfer-learning approach [EB/OL]. (2021–10–07) [2024–09–29]. https://arxiv.org/pdf/2108.00439
[9] Vaswani A, Shazeer N, Parmar N, et al. Attention is all you need // Advances in Neural Information Processing Systems. Long Beach, 2017: 5998–6008
[10] Bahdanau D, Cho K, Bengio Y. Neural machine tran-slation by jointly learning to align and translate [EB/ OL]. (2016–05–19) [2024–09–29]. https://arxiv.org/ pdf/1409.0473
[11] Gilmer J, Schoenholz S S, Riley P F, et al. Neural message passing for quantum chemistry // International Conference on Machine Learning. Sydney, 2017: 1263– 1272
[12] Kipf TN, Welling M. Semi-supervised classification with graph convolutional networks [EB/OL]. (2017–02–22) [2014–09–29]. https://arxiv.org/pdf/1609.02907
[13] Hamilton W, Ying Z, Leskovec J. Inductive represen-tation learning on large graphs // Advances in Neural Information Processing Systems. Long Beach, 2017: 1024–1034
[14] Veličković P, Cucurull G, Casanova A, et al. Graph attention networks [EB/OL]. (2018–02–04) [2024–09–29]. https://arxiv.org/pdf/1710.10903
[15] Xu K, Hu W, Leskovec J, et al. How powerful are graph neural networks? // 7th International Conference on Learning Representations, New Orleans, 2019
[16] Feng J, Chen Y, Li F, et al. How powerful are k-hop message passing graph neural networks // Advances in Neural Information Processing Systems. New Orleans, 2022: 4776–4790
[17] Morris C, Ritzert M, Fey M, et al. Weisfeiler and leman go neural: higher-order graph neural networks // Pro-ceedings of the AAAI Conference on Artificial Intel-ligence. Hawaii, 2019: 4602–4609
[18] Gehring J, Auli M, Grangier D, et al. Convolutional sequence to sequence learning // Proceedings of the 34th International Conference on Machine Learning. Sydney, 2017: 1243–1252
[19] Bradbury J, Merity S, Xiong C, et al. Quasi-recurrent neural networks [EB/OL]. (2016–11–21) [2024–09–29]. https://arxiv.org/pdf/1611.01576
[20] Wang M, Lu Z, Li H, et al. GenCNN: a convolutional architecture for word sequence prediction // Procee-dings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing of the Asian Federation of Natural Language Processing. Beijing, 2015: 1567–1576
[21] Diamos G, Sengupta S, Catanzaro B, et al. Persistent RNNs: Stashing recurrent weights on-chip // Procee-dings of the 33nd International Conference on Machine Learning. New York, 2016: 2024–2033
[22] Kuchaiev O, Ginsburg B. Factorization tricks for LSTM networks [EB/OL]. (2018–02–24) [2024–09–29]. https://arxiv.org/pdf/1703.10722
[23] Lei T, Zhang Y, Wang S I, et al. Simple recurrent units for highly parallelizable recurrence // Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing. Brussels, 2018: 4470–4481
[24] Wu H, Xu J, Wang J, et al. Autoformer: decomposition transformers with auto-correlation for long-term series forecasting // Advances in Neural Information Proces-sing Systems. Virtual, 2021: 22419–22430
[25] Zhang W, Feng Y, Meng F, et al. Bridging the gap between training and inference for neural machine translation // Proceedings of the 57th Conference of the Association for Computational Linguistics. Florence, 2019: 4334–4343
Leveraging Graph Structure and Simple Recurrence for Map Matching
Abstract Existing solutions for map matching mainly rely on sequence-to-sequence models to capture the correlations within a trajectory while neglecting the correlation between road segments and trajectories as well as trajectory-road correlations. Meanwhile, recurrent neural networks suffer from inherent limitations in conducting computations efficiently in parallel. To fully exploit all the aforementioned correlations and to improve the model parallelism, a Graph-enhanced Map Matching model with Simple Recurrence (GMMSR) is proposed. The model captures the correlations between road segments and trajectories through road network convolution and trajectory graph convolution respectively, and exploits the trajectory-road correlation by aligning road network and trajectory representations in latent space. Moreover, the model utilizes simple recurrent units to achieve more efficient parallel computations. Extensive experiments on a map matching dataset in a subarea of Beijing demonstrate significant improvements in accuracy compared with existing baselines while achieving comparable or better efficiency.
Key words map matching; trajectory and road correlations; graph neural networks; simple recurrence unit