基于地理空间感知型表征学习的轨迹相似度计算

摘要：度量轨迹间的相似性不仅是一项基础的研究问题, 同时也为众多轨迹数据挖掘应用提供支持。传统相似性度量方法面临数据噪声敏感、算法效率低等问题, 难以进行大规模数据计算。当前研究开始尝试使用深度表征学习方法, 将高维轨迹数据映射到低维向量空间, 通过度量表征间的距离高效地完成相似度计算任务。本文在轨迹表征学习中引入Transformer机制, 提出了一种地理空间感知的深度轨迹表征学习方法。首先, 使用Geohash编码将二维空间坐标点转换为一维编码序列, 使轨迹点在嵌入过程中保留空间相关性。然后, 引入Transformer框架构建轨迹表征的深度学习模型, 并采用一种隐轨迹点训练模式, 以保证模型能从低频、噪声的数据中习得更稳健的向量表示。最后, 设计了一个空间感知损失函数, 通过距离因子调整模型误差, 拉近空间相近轨迹的表征。试验表明, 本文方法在轨迹相似性计算任务中超越了基准模型, 并且计算效率远高于传统度量方法。

(相关资料图)

引 言

通信技术和位置采集设备日新月异，卫星、监控系统和移动设备无时无刻不在收集各种地理时空对象的轨迹数据，并广泛应用于位置推荐

[1

-2

]

、智慧交通

[3

-5

]

和公共安全

[6

-7

]

等场景中。学者们挖掘轨迹数据中蕴含的丰富信息与知识，在轨迹数据挖掘领域开展大量研究，如目的地预测

[8

-9

]

、移动群体发现

[10

-12

]

和轨迹聚类

[13

-14

]

等。而众多研究均依赖于一项基础工作，即轨迹相似性度量，只有正确度量轨迹之间的相似与差异情况，才能进一步开展相关的挖掘工作。经典方法(如LCSS、DTW和EDR等)主要基于逐点匹配的思想，虽然可以实现轨迹间相似度的计算，但受制于算法效率低、噪声影响大、扩展性和迁移性弱等问题，难以在海量数据场景中落地。

近年来，受自然语言处理(nature language processing，NLP)技术的启发(如NNLM

[15

]

、word2vec

[16

]

)，学习数据的向量化通用表征已经在语言翻译、文本分类，乃至图像检索等相似性分析任务中取得巨大的成功。学者们将这个思想借鉴到轨迹挖掘任务中，催生了轨迹表征学习这一研究方向。不同于传统“经纬度坐标-时间戳”的数据格式，轨迹表征是通过深度神经网络将高维轨迹映射到低维向量空间，在保留轨迹原有特征的基础上实现数据的降维表达。轨迹表征模型可以从大量训练数据中学习到地理对象的真实移动路径，从而纠正异常数据中的噪声点、漂移点，提升相似性计算的精度；同时，将原始的采样轨迹转化为一维向量后，相似性计算的效率得以大幅度提升，更适用于大规模数据挖掘应用。

当前轨迹表征学习技术主要是借鉴循环神经网络的编码-解码架构，如序列到序列(seq2seq)

[17

]

，来学习轨迹序列数据的表征。文献[18—19]将轨迹转化为空间网格编码序列，使用seq2seq的学习模型来获取轨迹表征，并应用于轨迹相似性计算，克服了轨迹采样不一致、点位漂移等问题；文献[20]基于滑动窗口思想提取了轨迹的动态特征作为行为序列，并用seq2seq模型生成行为序列的深度表征，解决了轨迹聚类中的时空偏移问题；文献[21]采用地图匹配方法将轨迹映射为道路编号序列，同时通过预训练任务捕获路段之间的相关性，二者融合后再使用seq2seq模型来学习轨迹表征。这些方法虽然可以实现高维轨迹向低维向量的转换，但依然存在两个问题：①基于空间网格的方法将轨迹点表示为独立的网格编号，使得轨迹点在编码阶段丢失了原有的地理空间相关性，在解码过程中也无法依据空间距离关系来计算模型损失；②seq2seq的编解码器是基于循环神经网络，容易出现信息遗忘问题，导致模型对长序列轨迹的建模能力差，难以捕获轨迹的全局信息。

为了解决上述问题，本文提出一种基于地理空间感知型表征学习的轨迹相似度计算方法，总体流程如图 1所示。首先，在轨迹点嵌入过程中引入Geohash编码方法，保证轨迹点从二维向一维转换的过程中保留它们的空间位置关系，并通过门控循环神经网络(GRU)捕获编码间的相关性。然后，本文将Transformer模型引入轨迹表征学习中，利用注意力机制让模型学习各个轨迹点之间的空间相关性，捕获长序列轨迹的全局信息。同时，模型采用隐轨迹点训练模式，通过随机掩蔽的方法模拟真实世界中轨迹的采样频率不一致、失真等问题，使轨迹表征模型更具稳健性。本文还设计了一个空间感知的损失函数，根据预测位置与目标位置的空间距离对模型损失进行加权，进一步提升模型的精度。最后，通过余弦函数度量轨迹表征，完成轨迹相似度计算。本文在大型公开数据集中评估模型的表现，试验证明，本文方法在相似性度量任务中表现优于基准模型，同时在计算效率上远超传统度量算法。

图 1本文方法流程 Fig. 1Flowchart of the proposed method

1 地理空间感知的深度轨迹表征模型1.1 问题定义

定义1：轨迹序列，轨迹T是由移动对象产生的一系列时空采样点p组成。点p包含对象的地理位置(x,y)(即经度和纬度)和时间戳t。

定义2：轨迹表征学习，给定一条离散采样的轨迹数据T，轨迹表征的目的是找到一个映射

将轨迹数据转化为低维空间中的向量V∈R

d

(d是向量空间的维度)。本文中该映射函数即为一个经过训练的深度神经网络编码器。

轨迹表征旨在反映了地理对象在现实路径上的活动情况，不仅需要克服数据采样不一致和噪声影响，还要尽可能地保留原始轨迹数据的时空属性

[22

]

。

定义3：基于表征的相似性度量，给定两条采样轨迹T

a

和T

b

，经轨迹表征编码后得到向量V

a

和V

b

，通过计算两个向量之间的距离来评估轨迹间的相似度。本文以余弦函数作为度量公式，即

1.2 地理空间感知的轨迹点嵌入

轨迹点的位置通常用纬度和经度来描述，虽然数值上它们是连续的，但它们并不适合直接输入到深度学习模型中，其原因有两个：首先，纬度和经度可以描述整个地球表面，但实际轨迹所经过的地点，通常只占地球表面一个非常小的区域。因此，用轨迹点的经纬度坐标来训练的模型会受到了稀疏性问题的影响。第二，纬度和经度之间有很强的相互作用关系，只有通过联合使用它们才能识别一个地点。如果将它们作为两个独立的值输入，模型将难以捕获这种地理空间的关联性

[23

]

。为解决以上问题，本文引入了Geohash编码。Geohash是一种常见的地理编码，其原理是将地球理解为一个二维平面，将平面按规律递归剖分成更小的网格，每个网格表示一定的经纬度范围，范围内所有的经纬度坐标都用相同的一维编码进行表示。Geohash编码的优势是在数据降维的基础上保留坐标的空间邻近属性。如图 2(右侧)所示，先将上海东方明珠电视塔的坐标(121.499 706°E，31.239 893°N)依据Geohash标准转换为二进制码，再按照固定间隔划分后转换为十进制序列[28, 25, 28, 3, 24, 31, 1]。序列的长度与其所代表空间网格的精度呈正相关，本文轨迹点坐标转换后的编码长度设为7，表示空间网格尺寸约为150 m×150 m。以整数序列进行表示具有两个优点：①将二维离散的空间坐标转换为一维的数字序列，更适合作为模型和算法的输入；②序列编码有效地保存了空间位置的邻近关系，在空间上相近的点位，它们的序列前缀保持一致。

图 2地理空间感知的深度轨迹表征学习模型 Fig. 2Geography-aware deep trajectory representation learning model

将空间轨迹点转换为序列编码后，需要进一步将其映射到高维空间中，提取编码的深度信息同时捕获序列间的相关性。这里采用门控循环神经网络(GRU)

[24

]

来进行轨迹点编码的嵌入。GRU是长短期记忆网络(LSTM)

[25

]

的变体，它能够学习顺序数据的长期依赖性，而不会导致性能下降。GRU通过引入一个更新门z和一个复位门r来控制信息在时间步长内的流动，从而顺序地更新隐藏态。在i∈{1, 2, …,n}的每个序列位置，给定位置编码l

i

和前一位置的隐藏态向量e

i-1

，通过以下公式得到e

i

(1)

(2)

(3)

(4)

式中，W代表各个门控单元的权重；b是它们的偏差；σ是Sigmoid激活函数。这里将轨迹点编码嵌入过程进行简化为

(5)

最后的状态e

n

∈R

d

即为感知了空间信息的轨迹点嵌入表示，它将进一步作为轨迹表征学习模型的输入。

1.3 基于Transformer的轨迹表征学习框架

目前，已有的轨迹表征模型均是基于序列到序列的方法，由一个基于循环神经网络的编码器将输入轨迹转化为指定维度的向量，再通过一个解码器将这个向量还原为轨迹序列。但基于循环神经网络的单向传播模式难以捕获长序列的全局信息，容易出现信息遗忘的现象，这制约了轨迹表征的效果。最近出现的Transformer模型

[26

]

在自然语言处理与图像处理领域的相关任务中表现优越，其成功主要归因于内部的自注意力机制，该机制保证模型可以学习到序列中各个位置之间的相关性，捕获序列的长程依赖关系。基于此，本文将它引入到轨迹表征的学习任务中。

图 2展示了基于Transformer框架的轨迹表征学习模型。

Transformer编码器是由一个自注意力层和一个前馈网络层组成，自注意力层以序列张量E∈R

m×d

(m表示序列的长度)作为输入，然后通过W

Q

,W

K

,W

v

∈R

d×d

3个不同的矩阵转换运算后，得到带有不同位置权重的输出，公式为

(6)

需要注意的是，由于自注意力编码器不能像RNN那样捕捉序列中的相对位置，本文参考文献[27]的方法，将融合位置编码P与张量E融合，即E=E+P。函数Attn()表示一种通过矩阵点积的计算机制，公式为

(7)

自注意力层的输出将被输入到前馈网络层中，它包含一个简单全连接层和一个ReLU激活函数，分别用于捕获维度内部的相关性和非线性变换。前馈网络层在第i个位置的计算公式为

(8)

经过N个Transformer编码器的计算后，得到输出张量F∈R

m×d

。为了进一步求取轨迹的全局表征，需引入了一个池化层对输出张量进行降维。本文采用的池化策略为平均池化，最终得到轨迹序列的深度表征V。

1.4 隐轨迹点训练模式

现实世界中的活动轨迹往往采样频率不一致，同时伴有噪声点、漂移点等问题，对轨迹数据挖掘相关任务产生很大的影响。针对这个问题，本文设计了一个隐轨迹点训练模式

[27

]

，通过随机地隐藏部分轨迹点，或加入位置偏移的噪声，让模型根据上下文关系预测被隐藏的轨迹点。首先，对原始轨迹序列进行处理，通过随机掩蔽将原始轨迹模拟成带噪声的轨迹，如图 2中将掩蔽轨迹点用[MASK]标识。本文的掩蔽方式有两种：一种是将轨迹点编码序列替换为指定的标号，且该标号与原有编码值不重复；另一种是将轨迹点编码序列中任意位置的编号进行随机替换，替换后的编码序列代表空间位置中的另一个点位，以此构建噪声点。模型的目标是利用上下文的点位来预测被掩蔽的轨迹点，这种训练模式能够有效拉近空间相邻点的向量表征。最后，将预测得到的轨迹点表征输入解码器，还原为轨迹点编码序列，并与真值进行比较，计算模型损失。解码器使用的是与轨迹点嵌入方法中相同的GRU网络。

隐轨迹点训练模式模拟了真实采样轨迹的噪声情况，让模型能够克服点位漂移的影响，使最终的轨迹表征模型具有更强的稳健性；同时隐轨迹点训练模式还可以让模型学习到序列中每个位置之间的相关性，使轨迹点表征具备空间上下文的特性，即使面对低频采样轨迹，模型依然可以得到有效的轨迹表征。

1.5 空间感知损失函数

损失函数是模型训练过程中十分重要的部分，它的差异会导致模型习得不同的表征。当前表征学习主要应用交叉熵损失函数进行模型优化，其公式为

(9)

由于本文采用基于Geohash的轨迹点编码方法，它将坐标点转化为带有空间信息的整数序列。这个序列的前后关系代表了不同空间尺度，序列位置靠前表示的空间范围越大，且每个位置的编号对应该空间尺度下的不同网格。交叉熵损失函数中的y

i

∈R

c

是解码器在第i个位置的输出，通过Softmax函数将其转化为c个类别(网格编码)的概率值。这种损失函数并不适用于空间数据，因为该计算方法将序列中所有位置的损失都认为是相等的，使得模型无论在序列中哪个位置预测错误，惩罚都是一致的。而轨迹数据的空间相关性很强，预测点与目标点的空间距离决定了它们之间的相似程度，如果距离越小，那么模型的损失也应减小。根据这一思想，本文设计了一个具有地理空间感知能力的损失函数，它能够在不同空间尺度下设置动态的惩罚系数，同时在尺度内按照预测格网与目标网格的空间距离设置损失，具体公式为

(10)

(11)

式中，w

ic

是距离因子，它由网格编码c和当前解码位置i决定；||c-y

i

||表示编码c与模型输出y

i

所代表网格的空间距离；dist/i是一个尺度系数，代表不同序列位置的空间尺度，具体系数值根据Geohash位数换算得到。

2 试验与分析

2.1 数据集与试验设置

试验在开源的波尔图出租车数据集上进行，该数据集中约170万条轨迹，时间跨度为19个月，每辆出租车的轨迹采样时间间隔为15 s。数据预处理中去掉了长度小于20的轨迹，得到约120万条轨迹，并按照8∶1∶1的比例划分为训练集、验证集、测试集。模型训练过程中，轨迹点掩蔽比例设置为[0.0，0.2，0.4，0.6]。模型共训练50轮(epoch)，训练过程中采用early stopping策略，当模型在验证集上的损失不再下降时，模型停止训练。由于计算机内存有限，本文试验将训练数据集分为不同批次输入模型，批大小(batch size)设置为256。本文的深度学习模型优化器采用Adam

[28

]

，并将初始学习率设置为0.001。所有模型均是在一台带有两个GTX 2080Ti图形处理器和英特尔i7 7700K中央处理器的计算机上用开源编程语言Python实现的。

2.2 对比模型与相似性度量指标

轨迹的相似性计算是数据挖掘分析中最重要的任务之一，本文通过这项经典任务来评估轨迹表征模型的效果。试验选取的对比模型可以分为两类，一是传统的度量算法，包含DTW

[29

]

、EDR

[30

]

和LCSS

[31

]

，其中DTW用于解决两个时序数据不对齐的问题，后被广泛应用于轨迹相似性计算；EDR和LCSS分别基于编辑距离和最长公共子序列的方法来进行轨迹相似性度量。二是基于轨迹表征的深度学习模型，包含GRU和t2vec。其中GRU是门控循环神经网络，它属于循环神经网络的一个变体，本文通过预测下一个轨迹点位置的方式来训练模型，并取其最后一个时间步的隐藏态作为轨迹表征；t2vec

[18

]

是一项关于深度轨迹表征的开创性工作，它通过seq2seq模型来学习轨迹表征，解决了轨迹点采样不一致、噪声敏感等问题，是目前最先进的轨迹相似度计算方法。

由于真实数据缺少可用标签，本文采用文献[18]中的相似轨迹查询排名方法来评估模型的性能：从测试集中随机选择了10 000条轨迹作为待查询轨迹，表示为P，然后另选择1000条轨迹作为查询轨迹，表示为Q。对于Q中的每条轨迹，通过交替取点来创建两条子轨迹，表示为T

q

和T

q′

，并构建两个数据集D

Q

和D′

Q

。对P中的轨迹执行相同的操作，得到D

P

和D′

P

。对于每条查询轨迹T

q

，将其与数据集D′

Q

∪D′

P

中所有轨迹进行相似度计算，之后观察T

q

与T

q′

的相似度在所有轨迹相似度中的排名。理想情况下，T

q

与T

q′

的相似度应排在第一名，因为它们是由同一条轨迹生成的。最终统计Q中1000条轨迹的平均排名作为性能评估指标。对于轨迹表征模型，试验采用余弦函数来度量两个轨迹表征之间的向量距离作为其相似性计算结果。

2.3 试验结果

待查询数据集P的轨迹数量为2000~10 000，各模型相似轨迹查询的平均排名情况见表 1。当数据集规模变大时，所有模型的平均排名均有下降，这是因为随着数据集内的轨迹数量增加，更多与目标相似的轨迹出现，影响了平均排名。传统方法中，DTW的轨迹查询平均排名情况最差，EDR和LCSS算法的表现接近。基于深度轨迹表征的方法中，GRU并没有取得突出的效果，主要原因是其单向的训练模式难以获取有效的全局轨迹表征。t2vec模型采用序列到序列编解码结构，有效地实现轨迹深度表征，试验结果超越了传统度量方法。表格下半部分展示了本文方法的消融试验，仅使用Transformer进行轨迹表征，效果较t2vec有小幅提升，证明了该框架相比基于seq2seq的模型具有更强的表征能力。引入轨迹点嵌入模块(trajectory point embedding，TE)代替一般的网格编码，模型的性能得到提升，说明具备地理空间相关性的编码有助于轨迹的降维表征。进一步将交叉熵损失函数(L

1

)改进为空间感知损失函数(L

2

)后，模型性能达到最优，主要原因是相似轨迹往往出现在相同的空间路径上，L

2

损失函数能够根据空间距离来动态调整惩罚值，可以有效拉近相似轨迹的表征，有助于提升相似度计算的表现。试验结果显示本文提出的具备地理空间感知能力的轨迹表征模型，在相似轨迹查询平均排名的表现较t2vec提升了约23.5%，较传统方法精度提升约55.3%。

表 1不同数据集规模的平均排名对比

Tab. 1Comparison of mean rank with different database sizes

为进一步验证本文方法的稳健性，试验评估了模型对不同长度和不同采样率的轨迹的表征能力。将待查询数据集P的规模固定为2000，观察各模型的相似轨迹查询排名情况。由图 3可知，当降采样频率提升时，LCSS模型性能退化最为严重，表明传统方法对降采样后的轨迹较为敏感，缺失轨迹点会严重影响模型的相似性度量的表现。而基于深度轨迹表征的方法能在一定程度上克服低频采样轨迹的影响，本文提出的方法较t2vec还有提升，是因为自注意力机制成功捕获了轨迹内所有轨迹点之间的相关性，即使部分轨迹点缺失，模型依然可以得到有效的表征。图 4展示了模型针对不同长度轨迹的表征能力，试验将轨迹按不同长度区间筛选后，进行相似轨迹查询并观察平均排名情况。随着轨迹长度的提升，GRU和t2vec模型的表征能力开始退化，这是因为基于循环神经网络的单向传播结构更注重相邻时间步的信息，忽略了轨迹序列中靠前位置的影响。而本文方法能够捕获轨迹内所有轨迹点的依赖关系，因此对长轨迹依然有较强的表征能力。

图 3不同降采样率下的平均排名对比 Fig. 3Comparison of mean rank with different down-sampling rates

图 4不同轨迹长度的平均排名对比 Fig. 4Comparison of mean rank with different trajectory lengths

深度学习模型的参数设置会导致结果存在差异，本文试验将讨论不同表征维度与池化策略对模型表征能力的影响。由图 5可知，当表征维度为32时，模型性能最差。这是因为表征的维度大小将决定该表征蕴含信息的容量，当表征维度过小，数据向量化的过程中就会出现信息丢失，导致模型性能退化；而提高表征维度，就需要足够多的训练样本来满足向量空间的表达。本文试验中当维度大小为128时，模型的表征能力最佳。基于Transformer的表征模型需要进一步连接一个池化层以得到序列的全局表征，试验分别采用了First池化策略(选取序列首位的表征代表全局表征)、Max池化策略(选取序列中的最大值代表全局表征)和Average池化策略(选取序列中所有位置的平均值代表全局表征)，由图 5可以发现First池化策略的表现最差，尽管模型中自注意力机制能够捕获序列中任意位置的相关性，但只选取序列首位仍然不足以反映轨迹的全局情况。Average池化策略在试验中的表现最优，证明该策略更适用于全局轨迹表征。未来工作将进一步研究如何获取更好的轨迹全局表征，如将池化层代替为神经网络层，通过微调的方式来改善模型的表现，同时匹配更多下游任务。

图 5表征维度与池化策略对平均排名的影响 Fig. 5The dimension size and the pooling strategy impact on mean rank

图选项

最后，图 6展示了轨迹表征学习方法与传统相似性度量方法在计算效率上的区别。试验从测试集中随机选取了20 000条轨迹并计算两两轨迹间的相似性。DTW和LCSS均是基于动态规划思想，按顺序匹配轨迹点后进行距离计算，导致算法的时间复杂度为O(n

2

)，其中n为数据集中轨迹序列的平均长度。基于表征的方法是使用线下训练好的深度学习模型，将待计算轨迹编码为一维向量，并通过余弦函数度量向量之间的距离，属于线性复杂度O(n+d)，其中d是向量的维度。在未使用加速算法的情况下，本文试验中DTW和LCSS完成计算耗时为78 643 s和76 970 s。深度表征模型虽然训练成本较高(本文模型在约100万条数据上训练18 h)，但将训练好的模型部署到线上能够大幅度提升轨迹相似性度量任务的计算效率，最终本文模型与t2vec完成计算耗时分别为2198 s与2184 s。

图 6模型计算效率对比 Fig. 6Efficiency comparison with different methods

3 结语

轨迹相似性度量是众多轨迹挖掘任务的基础工作，传统算法对数据质量敏感且计算效率低，因此研究借助深度表征学习方法，将原始轨迹数据映射到低维向量空间后进行相似度计算。但现有的轨迹表征模型均是基于朴素的空间网格编码结合序列到序列的编解码结构来学习，这使得轨迹点的空间位置属性丢失，同时难以构建长轨迹的全局表征。针对这些问题，本文提出了一个地理空间感知型轨迹表征学习模型，通过Geohash编码使轨迹点在嵌入过程中保留地理空间属性，并首次引入Transformer框架进行轨迹表征学习，利用自注意力机制解决了长轨迹信息遗忘的问题。同时，本文采用隐轨迹点训练模式保证模型能从低频、有噪声的轨迹中习得稳健的表征。为了进一步提升模型的效果，本文还设计了一个空间感知函数，通过距离因子调节模型的损失。在波尔图公开数据集中，本文方法在轨迹相似性度量任务中超越了基准模型。同时试验也证明了轨迹表征方法较传统度量模型的高效性。在后续研究中，将进一步引入对比学习机制

[32

]

，解决轨迹向量表征的各向异性问题，提升模型对正负样本的区分能力；考虑引入轨迹的时间属性和语义信息

[33

]

，如道路信息、兴趣点信息等，扩充深度模型的轨迹表征能力，使轨迹表征与更多下游任务耦合，如目的地预测、轨迹分类等。

关键词：