ICDE 2025 | 面向相似性计算的鲁棒轨迹嵌入：当距离度量中的三角不等式不成立时的解决方法

一. 背景

计算轨迹相似性距离对于轨迹数据管理和分析中的各种任务至关重要，多项研究对此有所涉及。特别是，轨迹相似性度量有效衡量了两条不同轨迹之间的距离，这对于许多下游应用至关重要，例如轨迹聚类、高效轨迹查询与检索以及交通状况优化。为了满足这些多样化应用的需求，研究者们研究了一系列计算轨迹距离的方法，包括 DTW、SSPD、EDR 和 Hausdorff。然而，这些方法都是在欧几里得空间中会受到三角不等式约束，所以作者引入了非欧几里得双曲空间的概念，该空间在规避约束方面显示出潜力，这需要解决三个挑战：挑战1：需要设计适用于双曲空间的距离函数；挑战2：需要利用现有轨迹编码模型有效实现双曲嵌入；挑战3：需要适应不同轨迹对之间三角不等式约束的变化幅度。

为了应对第一个挑战，论文设计了 洛伦兹距离（Lorentz distance），该距离通过 洛伦兹内积（Lorentz inner product） 计算，用以衡量嵌入之间的相似性。论文还证明该距离不受三角不等式的约束，因此是一种鲁棒的相似性度量方法。为了应对第二个挑战，提出了一种与模型无关的洛伦兹双曲插件（LH-plugin），可以无缝集成到任何现有的轨迹嵌入模型中，无需修改原始框架。论文首先探索了一种基础的双曲投影方法，用于将欧几里得嵌入转换为双曲嵌入。然而，通过观察与理论分析，作者发现该方法在嵌入范数增大时会导致距离缩小的问题。为此，提出了一种改进的投影方法，基于 双曲余弦函数（hyperbolic cosine function），从而实现更有效且理论上更合理的映射，避免了距离缩小的问题。为了应对第三个挑战，论文评估了不同数据集和相似性度量下三角不等式约束的变化影响，并引入了一种新的 动态融合距离（Dynamic Fusion Distance） 方法。该方法能够根据每一对轨迹的特性自适应地调整度量方式，动态融合洛伦兹距离与欧几里得距离，从而构建出一种能适应不同三角不等式约束强度的混合距离度量。          
二. 方法介绍

为了让大家能够更好的理解下面的方法，先为大家介绍一下什么是轨迹嵌入中的三角形不等式约束，因为轨迹嵌入空间是一个 d 维欧几里得空间，不同轨迹之间的嵌入距离满足三角不等式约束，如下所示：

而DTW（一种空间轨迹距离）的计算方式为：

其中T_a是一个轨迹也就是一个点的序列，d(p_ai,p_bj) 表示点p_ai和 p_bj 之间的欧几里得距离。但许多轨迹距离不满足三角不等式。具体而言，我们可以使用以下特定示例来阐明此问题。

图1 三角不等式不成立的一个例子

在图1 中，令 Ta=[(0,0),(0,1),(0,3)] ,Tb=[(2,0),(0,1),(2,3)] 和Tc=[(3,0),(3,1),(4,3),(5,3)]。使用DTW 距离计算公式，计算出的轨迹距离分别为Dist_D(Ta,Tb)=4，Dist_D(Tb,Tc)=9和Dist_D(Ta,Tc)=15。可以发现Dist_D(Ta,Tc)>Dist_D(Ta,Tb)+Dist_D(Tb,Tc)，这与之前提到的轨迹嵌入中的三角不等式约束相矛盾。

2.1 LH -plugin框架概述

图2 双曲空间与洛伦兹距离插件的（LH-plugin）框架概览

作者提出了一个轻量级框架，称为 LH-plugin。该框架旨在适配现有的轨迹嵌入模型，提升训练与推理的效率。此外，加入两个插件的设计能够确保即插即用的兼容性，避免对现有模型工作流造成干扰，从而提升其实用性与鲁棒性。如图2所示，该框架在原有的嵌入流程中引入了两个新模块：Hyperbolic Projection 模块：将嵌入映射到双曲空间；Dynamic Fusion 模块：以可学习的比例动态融合欧几里得距离与洛伦兹距离，用于衡量轨迹相似性。LH-plugin插件的工作过程为1.在欧几里得空间中生成嵌入（Generating Embeddings in Euclidean Space）；2.将嵌入映射到双曲空间（Mapping Embeddings to Hyperbolic Space）；3.计算融合距离（Computing Fusion Distance）。          
2.2 双曲线投影

在一个 n 维欧几里得空间中，嵌入向量 x^E∈R_n 拥有 n 个自由度。而在 n 维的双曲空间中，由于其本身的定义约束，仅有 n−1 个自由度。为了对齐两个空间的自由度，需要将 n 维欧几里得向量嵌入到 n+1 维的双曲空间中，得到x^H∈R_n+1。具体来说，欧几里得空间中的每一个点都会被唯一映射到双曲空间 H 中的一个点，从而建立这两个空间之间的一一对应关系（映射）。这种关系对表示学习至关重要，可以保证不同轨迹 T 和 T′，即使它们的欧几里得嵌入向量 x^E 不同，也不会被错误地映射到相同的双曲空间点 x^H 上。否则，可能会造成轨迹相似性判断混乱，产生误判。为了实现一一映射，论文中提出了两种双曲线投影方法，分为普通双曲线投影（Vanilla Hyperbolic Projection）与科斯双曲线投影（Cosh Hyperbolic Projection）。          
1. 普通双曲线投影：即在欧几里得空间的基础上增加一个新维度，从而将原始向量映射到双曲空间中。

2．科斯双曲线投影：但是普通双曲线投影的方法存在一个主要缺陷，就是普通双曲线映射会导致双曲空间中的向量长度在模较大时变得过于庞大，尤其是当原始向量模本身就很大时。这些向量会倾向于收敛到双曲空间的渐近线（如图2所示）或在高维空间中的渐近超曲面。为了解决这个问题，作者提出了引入一种非线性变换，对欧几里得模进行压缩，防止其在双曲空间中被无限放大。

图3 普通双曲线投影与科斯双曲线投影之间的比较

实际上，科斯双曲线投影来源于双曲角度（hyperbolic angle）的定义。如图 3(b)所示，假设橙色点位于双曲线x²−y²+1=0 上，其对应的双曲距离 d 等于该点与 y 轴之间的扇形面积的两倍（橙色阴影区域）。x 轴和 y 轴坐标值分别对应 cosh(d) 和 sinh(d)。作者利用这一性质，来减缓洛伦兹距离因模过大而趋近于 0 的问题。将整个映射过程用双曲余弦函数形式定义为：

2.3 动态融合

在一个具体的轨迹数据集 T 中，不同相似性函数（如 DTW、EDR）在面对三角不等式时的容忍度不尽相同。为了定量分析这种变异性，作者引入了一个违约标志函数（violation flag），定义如下：

其中， Sim[k|i,j]=f(T_i,T_j)−f(T_i,T_k )−f(T_j,T_k)，而 f(T_i,T_j)表示轨迹间的相似度度量。有了标准后就可以对不同的数据集与不同的距离计算方法进行实现，如表1说明：约有五分之一的轨迹样本在 DTW 度量下违反了三角不等式，不能忽视。

表1 不同数据集与相似性函数下的三角约束违反情况

虽然部分样本违反三角不等式，但大部分仍然满足。仅依赖洛伦兹距离会忽视有效的欧几里得结构，完全依赖欧几里得距离又无法处理三角不等式的违反情况。

因此，论文提出了一种动态融合机制，根据每对轨迹是否满足三角不等式来自适应调节欧几里得距离和洛伦兹距离的融合比例。为避免引入过多计算成本，论文设计了一种仅需 线性时间复杂度 的方法：对每个轨迹T_a，生成两个向量,洛伦兹因子向量与欧几里得因子向量，对（,) 的融合比例 计算如下：

那么最终的融合距离为： 

三. 实验          
3.1 实验目的          
为了评估论文提出的框架 LH-plugin并验证：1.LH-plugin 能否解决轨迹嵌入中的三角不等式问题；2.LH-plugin 如何影响嵌入模型的训练和推理效率；3.LH-plugin 框架在增强不同模型的相似性检索效果方面是否具有鲁棒性。
3.2 实验设置
硬件环境：实验在单节点服务器上进行，配置为Intel Xeon Gold 6248 CPU和NVIDIA Tesla V100 GPU

软件平台：基于 PyTorch 2.0.1 将 LH-plugin 集成轨迹相似性模型中，实验环境为 Ubuntu 18.04.6 系统

数据集：采用了几个常用于轨迹相似性方法的公开数据集来进行实验：Chengdu、Porto与T-Drive

嵌入模型：Neutraj、TrajGAT、Traj2SimVec、ST2Vec、Tedj          
评估指标：空间相似性计算：使用 DTW、SSPD 和 EDR 作为基准相似性度量，这些方法不满足三角不等式约束；时空轨迹相似性：使用 TP、DITA 和一种称为 secret Frechet 的距离度量来评估 LH-plugin 的有效性；准确性衡量：采用 Hit Rate 和 NDCG作为评估指标，HR@α 表示命中率，反映嵌入结果中与真实最相似的前 α 个结果所占比例。NDCG 衡量排序的相似性，广泛用于搜索与推荐系统中的检索质量评估。RVS是指相对不满足三角形不等式约束的归一化指数。
3.3 效率与效果研究          
为了验证 LH-plugin 在空间轨迹相似性方面相较原始模型的增强效果，论文比较了在集成 LH-plugin 之前和之后各模型的准确率，从而验证其在轨迹相似性学习中的有效性。结果如表2、表3、图4 所示，其中命中率以百分比形式展示。

实验结果明确表明：1.几乎在所有空间轨迹相似方法、数据集和模型中，集成 LH-plugin 后，命中率准确性均显著提高。尤其值得注意的是 Neutraj 和 Traj2SimVec：在 成都数据集中，这两个模型在 EDR 距离上的准确率提高了约 30%。这清楚地表明，LH-plugin 有效解决了空间轨迹相似表示学习中的三角不等式问题，从而提升了模型在相似性计算中的有效性。2. 原始精度越高的模型，在集成 LH-plugin 后的相对提升也越大（例如：Neutraj 在 DTW 距离下、Traj2SimVec 在 SSPD 距离下的表现）。这种提升归因于原始模型已接近其在欧几里得空间中的性能极限，引入超曲率空间后可进一步提高精度。相反，对于原始精度较低的模型（如 TrajGAT 在 波尔图数据集上计算 EDR 距离），提升幅度较小。这说明，在原始精度较低的情况下，三角不等式约束对相似性准确性的影响较弱，因此在集成 LH-plugin 后精度提升不明显。3. 不同相似性方法的交叉比较显示：DTW 距离在集成 LH-plugin 后的性能提升最显著，这表明 DTW 方法受三角不等式约束的影响最为明显。

表2 Chengdu和Porto数据集的准确性结果

表3 ST2Vec和Tedj准确性结果          

图4 RVS分配能力比较

四、总结

在本文中，论文对轨迹相似性表示学习中的三角不等式问题进行了深入研究，特别是欧几里得空间中的三角不等式约束与轨迹相似性度量之间的冲突。为了解决这一问题，论文提出了 LH-plugin —— 一个与模型无关的插件，可适用于任何轨迹相似性表示学习模型。该插件利用双曲空间中的 Lorentz 距离，规避了欧几里得空间中存在的三角不等式约束。具体而言，LH-plugin 使用 Cosh 函数来优化从欧几里得空间到双曲空间的映射，并根据不同的轨迹组合动态调整 Lorentz 距离与欧几里得距离的融合方式，从而使用融合距离进行相似性度量。论文在多个真实世界数据集上，结合多种主流轨迹相似性表示学习模型进行了大量实验，验证了 LH-plugin 的有效性。          

-End-

本文作者 洪程璁 重庆大学计算机科学与技术专业(弘深)2023级本科生，重庆大学Start Lab团队成员 主要研究方向：时空数据压缩

       

              图文｜洪程璁

              校稿｜黄天羽

              编辑｜周钦钦

              审核｜李瑞远

              审核｜杨广超