本文已参与「新人创作礼」活动, 一起开启掘金创作之路。
轨迹相似度衡量任务
背景&应用:
随着物联网设备和定位技术的发展,会产生许多时空相似度很高的轨迹,例如:
-
对于单个个体:其轨迹可能会被多个定位系统所采集,比如当你驾驶汽车在高速上行驶,手机或汽车的GPS、路边的监控摄像头,以及经过的收费站等都会记录你的位置信息,生成多条轨迹。
-
对于多个个体:比如你的朋友和你结伴出行,生成的两条轨迹也是相似度很高的。
本文研究的方向就是设计一种方法来度量两条轨迹之间的相似度,帮助我们发现一些相似度很高的轨迹对。这是一项很有实际意义的工作,比如在案件侦破中,警方通过相似度分析可以将犯人的车辆、手机和人像联系起来,降低破案的难度。在疫情扩散的当下,我们还可以通过分析感染者的轨迹来寻找密切接触者。
任务:
设计一种算法来衡量两条轨迹之间的相似度,并且这些轨迹数据是有定位误差和零星采样问题。
存在的挑战
- 定位误差:存在噪声
- 零星采样:同一个路径RR对应多个轨迹TrTr
- 采样率不同:给定轨迹和需要比较的轨迹的长度不一
传统方法
- DTW(动态时间规整,将轨迹长度进行缩放,再计算欧氏距离)
- LCSS(最长公共子串,将轨迹投影到网格,计算公共网格)
- EDR(最小编辑距离,与LCSS类似)
- ERP、APM(提出了一些更复杂的指标,如转移概率等)
局限: - 对采样率变化的轨迹对的处理较为粗糙;
- 依赖于轨迹对齐,时间复杂度:O(n2l2)mathcal{O}(n^2l^2) ,其中nn是样本数,ll是轨迹长度;
- 局限于一种度量,缺乏通用性。
深度表示学习方法
t2vec
- 来自论文:Deep Representation Learning for TrajectorySimilarity Computation[ICDE2018]
- 对原始轨迹TbT_b添加噪声、下采样为轨迹TaT_a,希望轨迹TaT_a能够生成原始轨迹TbT_b;利用encoder-decoder学习轨迹的表示。
- 对空间相关性的建模,主要是在嵌入层:
- 对于每个网格uu,根据远近的分布采样邻近网格集合C(u)mathcal{C}(u),用word2vec的方式得到uu的表示.
- 在decoder的t+1t+1步,对yty_{t}邻近的网格进行加权.
- 实验是看增广的轨迹能否匹配原轨迹,两个表示向量的相似度计算方法文中没有介绍,应该就是点积。
- 评价:将深度学习引入轨迹相似度计算,更强调的是学习轨迹的表示,测试集上:O(l+∣v∣)mathcal{O}(l+|v|).
NeuTraj
- 来自论文:Computing Trajectory Similarity in Linear Time: A Generic Seed-Guided Neural Metric Learning Approach [ICDE2019]
- 引入神经度量学习的方法,使得学习到的度量g(Ti,Tj)g(T_i,T_j)逼近真实度量f(Ti,Tj)f(T_i,T_j)
- 可以拟合任意的轨迹度量,f(⋅,⋅)f(·,·)可以是豪斯多夫距离、弗雷歇距离、动态时间规整等任意的轨迹相似度的度量
- 模型层面:(1)仍然是基于RNN的模型,构建相似轨迹集进行训练;(2)空间信息在门控机制上进行了记忆设计
- 测试集上的复杂度O(l)mathcal{O}(l),训练集复杂度是O(n2l2)mathcal{O}(n^2l^2),其中nn是训练样本数,ll是轨迹长度
- 评价:训练集的构建为方法不再局限于对原始轨迹的增广.
Traj2SimVec
- 来自论文:Trajectory Similarity Learning with Auxiliary Supervision and Optimal Matching [IJCAI2020]
- 和NeuTraj一样,神经度量学习,使得学习到的度量G(X,Y)G(X,Y)逼近真实度量S(X,Y)S(X,Y).
- 文章指出,尽管测试集上的轨迹相似度计算已经降低到线性时间,但是训练集的时间开销仍然是平方阶的,因为需要计算每个样本对之间的相似度。
- 对轨迹的处理:
- 引入了一篇轨迹简化(Trajectory Simplication)的工作,对轨迹点的重要性进行计算,对轨迹进行了划分和再采样后,引入了KD树(用于空间划分的特殊二叉树)进行存储。
- 建树对轨迹点进行表示,降低了计算成本:建树复杂度为O(nlogn)mathcal{O}(nlog n),查询为O(logn)mathcal{O}(log n).
- 基于再采样后的轨迹,设计了对比子轨迹(sub-trajectory)的loss,通过局部的loss加权得到单个样本的loss.
- 进一步考虑长短不一的轨迹的局部相似性的问题,作者还设计了一种轨迹匹配点的triplet loss,进一步拓展了轨迹相似度的定义.
- 模型层面:仍然是RNN-based model.
- 评价:更关注训练阶段的计算开销;拓展了“相似”的定义。
TrajGAT
对之前工作的总结
经典的轨迹相似度指标:计算复杂度平方阶,且局限于单一的度量
基于深度表示学习的模型:
Motivation1: 长序列的处理
(1) 均为RNN-based,难在长序列上表现衰减,难以捕获长序列依赖
存在长序列依赖问题是怎样影响轨迹的相似度计算呢?
- 论文中给出的理由是:轨迹相似度的计算基于轨迹的对齐,如下图所示。当一个长的轨迹和短的轨迹进行对齐时,无法很好地捕获长的轨迹的信息。
- 在训练集构建的阶段,是用的传统算法来计算的ground truth;先前工作中中涉及轨迹对齐的应该说只有计算轨迹匹配loss的模块。个人认为还是最终学出的表示不够好的原因。
- 但是事实上,根据作者的实验,在西安数据集上,确实长序列的轨迹的命中率Recall@10Recall@50和Recall10@50要小;效果更弱一些。
=> 最终目的是让长的轨迹得到比较好的表示。
Motivation2: 网格化的合理性
(2)作者认为,轨迹由空间的网格序列表示,让远距离的record无法相互作用(即:同一个轨迹中,间隔远的点也是具有相似性的)
(3) 此外,作者还认为,由于轨迹在空间中是不均匀分布的,一些网格的数据多,一些网格的数据少,这种空间的异质性会导致一些网格的token在网络训练过程中没有得到足够的数据去优化,因此在长序列的轨迹中,会恶化表示的效果。
=> 希望能充分利用远距离和小样本的网格信息。
Motivation3:长序列表示的挑战
- Transformer:GPU显存占用较高
- 长序列表示模型:Bp-transformer、Informer,没有建模空间信息
=> 希望能尽可能节省训练的显存占用。
本文的方案
引入了PR-四叉树可以较好地
- 保证各网格训练的均衡
- 基于四叉树的构图可以提供层次信息
- 相比于要计算每一个网格对的attention,在图上基于GAT的模型,只需要计算邻居的attention,限制了显存的占用。
问题定义
定义:
- 轨迹库Tmathcal{T}包含NN条轨迹;
- 我们强调轨迹都分布在区域Amathcal{A}上;
- 每条轨迹:T=[X1,…,Xt,…]∈TT=[X_1,…,X_t,…]inmathcal{T},其中Xt=(lont,latt)X_t=(lon_t,lat_t)是第t个到达点;
- f(Ti,Tj)f(T_i,T_j)是对于轨迹TiT_i和TjT_j相似度的一个度量,可以是DTW,Hausdorff,Frechet距离等…
- 任务是学习一个函数g(⋅,⋅)g(·,·)来估计轨迹的相似度,目标是最小化∣f(Ti,Tj)−g(Ti,Tj)∣|f(T_i,T_j)-g(T_i,T_j)|.
模型概述
- 首先是对区域Amathcal{A}做了一个层次划分,划分树是Hmathcal{H}。模型对Hmathcal{H}下的每一个层次的网格做了表示的预训练,希望能够获取不同层次的信息。
- 基于树Hmathcal{H},作者构造了一个图TgT^g. 用GAT获得TgT^g的表示。根据轨迹的序列信息和层次信息生成轨迹的嵌入。
- 最后,设计ranking loss去学习轨迹的相似度度量。
层次划分
Traj使用Point Region Quadtree(点-区域四叉树)来表征区域的层次划分。
- 通过对区域进行不断的划分,四叉树的分支,最终保证每个区域包含δdelta个节点,δdelta是一个经验性的参数。
- 忽略叶子节点,四叉树构成了对原区域Amathcal{A}的一个划分,记作Hmathcal{H}。
- 随着区域Amathcal{A}的增加,作者试图论证:Hmathcal{H}倾向于稳定(实验见附录A.3,但pdf中没有给出附录)。
- Traj模型基于这个划分进行设计。
网格的嵌入
- 将树Hmathcal{H}看做一个图。
- 用Node2vec获得图中各个节点的表示。
- 最终得到的嵌入记作:MH∈dh×Nhbold{M}_mathcal{H} in d_h times N_h,得到的各个节点的表示后续将用于计算轨迹的表示
轨迹的编码
构图
对于轨迹TT,我们构造了一个新的图Tg=(N,E)T^g = (bold{N},bold{E})
Nbold{N}包括两部分:由轨迹构成的Nrbold{N}_r和轨迹的层次信息构成的Nhbold{N}_h
- 首先找到其包含的轨迹点(对应的网格对应的节点)的嵌入:Nr={n1,…,nL}bold{N}_r = {bold{n}_1,…,bold{n}_L}.
- 递归地查找PR-四叉树Hmathcal{H}中叶子节点ii的父节点,即:包含该节点的所有大小的网格,直到网格大小(即节点的层次)到设定的阈值ηeta.
- ηeta是一个超参数,查找出的节点集合根据层级ii分别记作:Nr1,Nr2,…,Nrηbold{N}_r^1,bold{N}_r^2,…,bold{N}_r^eta
- 所有轨迹点的上ηeta层构成的节点的嵌入集合记作:Nhbold{N}_h,即:Nh={Nh1,…,Nhη}bold{N}_h = {bold{N}_h^1 ,… ,bold{N}_h^eta}
Ebold{E}包括两部分:(1)原有四叉树中的边;(2)对同层的非叶子节点增加的全连接边,即:每一个NhiN_h^i都是全连接的完全子图。
节点的表示
新的图Tg=(N,E)T^g = (bold{N},bold{E})是同质的,即:每个节点的表示方式是一致的,都包括三部分:fi=concat(fl,fr,fh)∈R3dfbold{f}_i = concat(bold{f}^l,bold{f}^r,bold{f}^h) in mathbb{R}^{3d_f}
- 地点特征:fil=MLP(xi,yi)bold{f}_i^l=MLP(x_i,y_i),(xi,yi)(x_i,y_i)是归一化后的节点坐标或区域中心坐标。
- 区域特征:fir=MLP(wi,hi)bold{f}_i^r=MLP(w_i,h_i),(wi,hi)(w_i,h_i)是区域的长和宽
- 层次特征:fih=Embedding(MH,ni)bold{f}_i^h=Embedding(bold{M}_mathcal{H},bold{n}_i) //查询节点i的信息
序列编码
作者通过层次遍历生成树的序列信息,形成节点的列表LL:
对LL进行位置编码,得到λislambda^s_i:
作者希望通过计算图的Laplacian矩阵对应的低频特征向量+节点对应的特征向量,表示节点的距离信息:
最终,得到节点的表示向量iibold{i}_i:
GAT
基于图去计算注意力,只需要利用领近节点的表示,避免了序列Transformer中计算每一组向量的注意力带来的过大开销:
经过PP层的聚合,得到每个节点的最终表示:[h1P,…,hMP][bold{h}_1^P,…,bold{h}_M^P]
轨迹的最终表示: