程序员经验分享-hwhale

论文笔记：GRLSTM: Trajectory Similarity Computation with Graph-Based Residual LSTM 2023 AAAI

2023-11-09

1 intro

1.1 背景

  • 轨迹相似度
    • 早期的度量采用成对匹配并依赖动态规划来计算最优对齐（DTW、LCSS、EDR。。。）
      • 时间复杂度为O(n^2)
        • n是轨迹的平均长度
        • ——>对于大规模的轨迹数据并不是理想的选择
        • ——>会受到噪点的干扰，导致最终准确度下降
      • 近几年有模型利用基于嵌入的相似度计算方法
        • 每一条轨迹都被编码为一个由深度学习模型生成的潜在向量
          • 将自然语言处理的深度学习模型用于生成轨迹表示
        • 轨迹的相似度可以通过向量相似度计算在线性时间内完成
        • 这些深度学习方法通常能够捕捉轨迹数据的复杂性和多样性，因此在处理大规模轨迹数据和高维空间数据时具有优势
          • 然而，它们也有自己的挑战和局限性，例如模型解释性差、需要大量标注数据等
  • 尽管上述方法在计算欧几里得空间中的轨迹相似性方面是有效的，但它们在计算道路网络上的轨迹相似性方面并没有预期的效果
    • 目前少数研究尝试解决道路网络上的轨迹相似性计算问题
      • 采用手工设计的启发式方法来将轨迹与道路网络对齐
      • 定义了一些相似度函数，测量道路网络上的轨迹相似性
      • ——>仍然面临高计算复杂性的问题
    • 最新的 GTS 框架在道路网络上运用了深度学习方法和图神经网络，并取得了不错的性能
      • GTS 遗漏了两个问题
        • GTS 只考虑了道路网络信息，而在图处理过程中忽略了轨迹信息
          •  轨迹中的相邻点在道路网络上不一定是相邻的
            • 这可能是由于数据丢失或不一致的采样率导致的
        • GTS 在轨迹上使用了优化策略，但没有考虑点优化
          • （原定轨迹是p1-p8-p2，因为采样率的关系，变成了p1-p2)

1.2 论文思路

  • 为了充分利用轨迹和道路网络的点信息，论文提出了一个全新的框架，名为 GRLSTM
    • 每个点在道路网络和轨迹中都有多种关系
      • ——>通过构建一个知识图谱来考虑这一点
      • 使用知识图谱嵌入（KGE）方法，并通过 k-最近邻选择进一步构建一个融合图
    • 引入了 GAT来捕获融合图的拓扑结构信息
    • 最终的轨迹表示是通过多层 LSTM 学习得到的
      • 为了解决在深层 LSTM 中各层之间的梯度消失问题，论文使用的残差网络结构
  • 设计了两个全新的基于邻点的点感知损失函数来优化 GRLSTM
    • 基于图的点损失（Graph-based point loss）
      • 为了优化图级点嵌入，论文认为图中连接的点应该是相似的
    • 基于轨迹的点损失（Trajectory-based point loss）
      • 同一轨迹中的点嵌入应该是相似的（一个轨迹通常是由同一辆车采样得到的）

2 Preliminary

2.1 带路网的轨迹

  • 路网G=(V,E)
    • 每个节点v都具有地理坐标，代表一个道路段的端点或一个道路交叉口
    • 每条边e=<u,v>，表示连接u和v的路段
  • 路网G中一条长为n的轨迹\tau=<v_1,v_2,\ddots,v_n>
    • 由n个G中的点有序组成

2.2 问题定义

给定一个道路网络的图 G=(V,E) 和一个轨迹集合T=\{\tau_1,\tau_2,\cdots,\tau_m\}，对于集合 T 中的任意轨迹τa，轨迹相似度计算的目的是找到一个轨迹τb∈T，使得 τb​ 与 τa​ 最为相似，其中 a≠b。

3 模型

【建立知识图谱的时候，论文没有明说，但我的理解是：上图的流程是求得一条轨迹的embedding，所以知识图谱“在轨迹中”这个关系只考虑这一条轨迹，不考虑集合中其他的轨迹】

3.1 点的知识图谱表征

  • 每个点既属于道路网络也属于轨迹。
    • 由于设备的不同采样率或数据丢失，轨迹通常不是道路网络上的连续序列，这意味着轨迹内的相邻点在道路网络上不一定是相邻的。
    • 换句话说，轨迹中存在一些虚拟边，而这些边在道路网络中并不存在

  • 为了解决上述问题，论文将道路网络和轨迹结合起来构建一个知识图谱
    • 给定一个轨迹数据集和道路网络图，构建一个道路网络-轨迹知识图G=(V,E,R)
      • R 有三种关系类型：道路网络边r_n，轨迹虚拟边r_t，双重边r_{nt}
    • 每一条边e=<u,v>都有一个对应的关系r∈R
      • 构建为一个三元组<u,r,v>
  • 论文使用TransH来学习实体和关系的嵌入
    • 知识图谱笔记：TransH_UQI-LIUWJ的博客-CSDN博客
    • TransH 的基本思想是使用不同的超平面来表示不同的关系空间
      • 给定一个三元组〈u,r,v〉
        • eu和ev的embedding首先被投影到wr超平面上（||w_r||_2=1)
        • 然后，使用一个得分函数 f(⋅) 来计算三元组的差异
          • hr是超平面上关系r的表征
          • 如果三元组的关系是正确的，值应该较低；如果相反，则值应该较高
  • 到目前为止，每个实体（即点）和每个关系都已经通过嵌入来表示
    • 为了捕获不同关系内点之间的相关性，论文设计了一个实体-关系相似度函数 s(⋅)，用于计算特定关系 r 内点 u 和点 v 之间的嵌入相似度
  • 通过相似度构建点融合图G_f \in R^{|V| \times |V|}
    • 使用 k-最近邻选择来基于相似度获得点vi的邻域集合N_s(v_i)
      • ——>以保持图的稀疏性并减少噪声
    • Gf​ 是一个通过相似度构建的新图
      • 轨迹中的相邻点、路网中的相似点在融合图中也不一定是相邻的
      • 融合图的点可以同时包含道路网络和轨迹的特性

3.2 点的Graph Embedding

就是图注意力网络GAT

W和a都是可学习参数，σ是激活函数，||是拼接操作，Ni是邻居集合，pi是点embedding

公式(8)是单头注意力，公式(9)是多头注意力

3.3 多层LSTM+残差网络

4 目标函数

4.1 嵌入相似度

使用点积来衡量轨迹嵌入之间的相似性。假设轨迹 τi​ 和 τj​ 的嵌入分别是 ti​ 和 tj​。轨迹嵌入的相似性得分可以如下计算：

同样地使用点积来定义点嵌入的相似性得分。假设点 vi​ 和 vj​ 的嵌入分别是 pi​ 和 pj​。点嵌入的相似性得分可以定义为：

可以通过这些相似性函数定义目标函数来优化模型。

4.2 点敏感损失函数

  • 如图1所示，点在道路网络上具有不同的属性，点融合图 Gf​ 是基于这些属性构建的。
  • 受这些不同关系的启发，论文定义两种基于邻域的点敏感损失函数（基于图的点损失和基于轨迹的点损失）来优化点嵌入

4.2.1 基于图的点邻居

  • 将基于图的点邻居定义为融合图上的一阶邻居
    • 直观地说，图上的每个节点与其一阶邻居具有很高的相似性。
    • 将一个点的一阶邻居集合记为N_{gp},(|N_{gp}|=k)
  • k-最近邻选择中k的取值对融合图上一阶邻居的数量有显著影响
    • 为了减少这些影响，论文应用了广泛用于其他基于排名的应用的成对方法，来设计基于图的点损失函数
    • 给定一个轨迹集合T=\{\tau_1,\tau_2,\cdots,\tau_m\}，其中轨迹\tau_i=<v_i^i,v_2^i,\ddots,v_{|\tau_i|^i}> \in T
    • 定义基于图的点损失函数为：
        • 轨迹集的每一个点v_j^i，从N_{gp}(v_j^i)中找一个正样本，从不在N_{gp}(v_j^i)中找一个负样本
          • 正样本的Sp越大越好，负样本的Sp越小越好

4.2.2 基于轨迹的点邻居

  • 轨迹中相邻的点在道路网络上并不一定是相邻的，这对融合图 Gf​ 也是如此
    • k近邻选择邻居，从而构图，所以轨迹相邻、地理不相邻的点不一定选得上
  • 然而，轨迹中相邻点之间存在很高的相似性，比如车辆的运动趋势
    • 给定一个轨迹\tau=<v_1,v_2,\ddots,v_{|\tau|}>，和一个特定的点vi，定义vi的前一个点和后一个点为基于轨迹的点邻居
    • 将基于轨迹的点邻居表示为N_{tp},(|N_{tp}|=1 or 2) 【轨迹第一个点和最后一个点只有单边邻居】
  • 同样使用成对方法来设计基于轨迹的点损失函数
    • 给定一个轨迹集合T=\{\tau_1,\tau_2,\cdots,\tau_m\}，其中轨迹\tau_i=<v_i^i,v_2^i,\ddots,v_{|\tau_i|^i}> \in T，定义基于轨迹的点损失函数如下：
    • 轨迹集的每一个点v_j^i，从N_{tp}(v_j^i)中找一个正样本，从不在N_{tp}(v_j^i)中找一个负样本
      • 正样本的Sp越大越好，负样本的Sp越小越好

4.3 轨迹敏感损失函数

论文的目标是找到最相似的轨迹，而不仅仅是计算相似性分数。

——>因此，需要定义轨迹敏感损失函数来优化模型

  • 也使用成对方法来设计轨迹损失函数
    • 给定一个轨迹集合T=\{\tau_1,\tau_2,\cdots,\tau_m\}，我们为一个轨迹定义轨迹损失函数如下：
    • \tau_{pos}是最相似的轨迹，\tau_{neg}是除了\tau_{pos}和τi之外的其他轨迹

4.4 最终的损失函数

 5 实验

5.1 数据集

纽约 

北京：T-drive数据集（10,357辆出租车在几天内收集的出租车ID、GPS坐标和时间戳来获得的）
将这些数据随机分为训练集、验证集和测试集，比例分别为[0.2, 0.1, 0.7]。

5.2 评估指标

  • 采用HR@K作为主要的性能指标
    • Top-k命中率（HR@k）检查返回的Top-k结果与基准真值之间的重叠

5.3 Baseline

  • Traj2vec（Yao等人，2018）：一个用于学习轨迹嵌入的序列到序列模型。使用均方误差作为优化模型的损失函数。

  • Siamese（Pei、Tax和van der Maaten，2016）：一个基于Siamese网络的时间序列学习方法。它使用交叉熵损失函数来训练模型。

  • NeuTraj（Yao等人，2019）：这个框架修改了LSTM的结构，以基于网格学习轨迹嵌入。

  • Traj2SimVec（Zhang等人，2020）：该方法采用了一种新的损失函数，通过点匹配来进行轨迹相似性计算。

  • GTS（Han等人，2021）：这个框架是第一个在道路网络上使用图学习进行轨迹相似性计算的模型。它使用GCN和LSTM来学习轨迹嵌入。

5.4 实验结果

 5.5 ablation study

  • w/o FG 没有融合图，只用路网
  • w/o GAT 仅使用GCN
  • w/o P：不用基于图的点邻居loss function（4.2.1）
  • w/o TP：不用基于轨迹的点邻居loss function（4.2.2）
  • w/o Resnet：多层LSTM中不适用残差链接

5.6 是否使用残差链接，使用几层？

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

论文笔记

论文阅读

论文笔记：GRLSTM: Trajectory Similarity Computation with Graph-Based Residual LSTM 2023 AAAI 的相关文章

  • Python面向对象详解（4-2）

    目录 一 类中的参数self 二 Python中self的解析与总结 1 self是什么 python中self代表类的实例 2 Python中只有针对类来说self才有意义 3 self只能用在python类的方法中 4 举例说明 三 类

随机推荐

  • 第十届蓝桥杯国赛 G排列数（动态规划精简题解+图解）

    动态规划 集合 f i j f i j f i j 表示填了前

  • 在socket编程中，如何获取连接另一端（客户端）的ip地址，使用accept或者getpeername

    这段代码没有实际的功能 只是为了获取连接另一端的ip地址 include

  • 因果推断----必要因和充分因

    必要因 或 若非因 和充分因 必要因 已知张三堵住消防通道 X 1 并且李四死了 Y 1 假如X为0 那么李四还活着 Y 0 的概率是多少 必要性概率 P N PN PN为 P

  • （c语言）PAT 乙级 1010 一元多项式求导 (25分)

    设计函数求一元多项式的导数 注 x的n次方 n为整数 的一阶导数为n乘x的n 1次方 输入格式 以指数递降方式输入多项式非零项系数和指数 绝对值均为不超过 1000 的整数 数字间以空格分隔 输出格式 以与输入相同的格式输出导数多项式非零项

  • cat命令

    Linux cat命令的使用 cat命令主要用来查看文件内容 创建文件 文件合并 追加文件内容等功能 A 查看文件内容主要用法 1 cat f1 txt 查看f1 txt文件的内容 2 cat n f1 txt 查看f1 txt文件的内容

  • 使用R语言实现逻辑回归预测客户流失

    目录 1 引言 2 加载并理解数据 3 数据预处理 4 构建并训练逻辑回归模型 5 模型评估

  • c语言函数中调用的参数太多_函数的参数太少（C语言错误）

    c语言函数中调用的参数太多 很少参数无法使用C语言 Too few arguments to function in C language This error occurs when numbers of actual and forma

  • 玩牌高手极其基本解法

    标题 玩牌高手 时间限制 1秒 内存限制 32768K 语言限制 不限 给定一个长度为n的整型数组 表示一个选手在n轮内可选择的牌面分数 选手基于规则选牌 请计算所有轮结束后其可以获得的最高总分数 选择规则如下 1 在每轮里选手可以选择获取

  • 时间操作——moment.js参考文档

    目录 一 引入moment js 1 Node js方式引入 2 浏览器方式引入 二 moment时区和转换 1 时区的设置 2 UTC和北京时间的互转 三 使用 1 获取时间 2 js 是一个轻量级的JavaScript时间库 它方便了日

  • （Slide）Attention Mechanism注意力机制

    PPT地址 http download csdn net download mounty fsc 10113027

  • Ubuntu有线校园网认证窗口提示：could not connect : no route to host

    问题 在Linux系统 Unbuntu22 04 上连接校园网时 遇到一个问题 因为使用的是有线连接校园网 弹出校园网认证窗口时提示 could not connect no route to host 尝试的方法 尝试了以下方法 但都没能

  • win11任务栏图标大小设置教程

    最近有不少小伙伴在升级安装最新的Win11系统后 发现任务栏的图标太小 不知道win11任务栏图标怎么调大小 下面小编就来给大家详细介绍下win11任务栏图标大小设置的具体方法吧 希望对大家有所帮助 win11任务栏图标大小设置教程 1 w

  • 错误：Visual Studio has encountered a problem and needs to close

    我使用VS2008 Qt4 7 4开发时 安装Qt后报出该错误 google了一下解决了问题 原来在安装QT插件不正确导致的 在360软件管家中 卸载了qt win opensource 4 7 4 vs2008 但qt vs addin

  • Android 9 静默安装、卸载App

    文章目录 引言 安装流程 实现代码 AndroidManifest xml配置 apk运行打包 放到源码目录下重新进行签名 编译 安装日志 转载自 Android 9 P静默安装 卸载App适配终极指南 引言 静默安装是指apk安装不需要用

  • Scratch图形化编程等级考试简介

    目录 全国青少年软件编程等级考试是行业首个且规模最大的编程等级考试 并且还有权威认证 对孩子未来的升学也有非常大的益处 全国青少年软件编程等级考试是由中国电子学会发起的面向青少年机器人软件编程能力水平的社会化评价项目 中国电子学会是工业和信

  • springboot 获得请求ip地址

    package com example winterholity util import javax servlet http HttpServletRequest import java net InetAddress import ja

  • Yii Framework 开发教程(41) Zii组件-Tabs示例

    CJuiTabs 显示分页UI组件 和Yii Framework 开发教程 17 UI 组件 TabView示例功能类似 它封装了 JUI tabs插件 前基本用法如下 php view plain copy print

  • (一)：Qt信号槽原理---元对象与moc

    一 信号槽 当信号被调用时 与其关联的槽函数会被调用 调用时机与连接类型有关 同一个线程内的信号 槽 就相当于函数调用 和观察者模式相似 只不过信号 槽稍微有些性能损耗 这个后面细说 跨线程的信号 槽 在信号触发时 发送者线程将槽函数的调用

  • Visual Assist X AND MSDN

    assist X 推荐 这款插件是visual studio或者vc的插件 没想到vs用起来也可以这么爽 用起来居然比sourceinsight还好用 好用到哭 好用到哭 好用到哭 自动补全 补全的时候还可以看到对这个补全的东西的介绍 鼠标

  • 论文笔记：GRLSTM: Trajectory Similarity Computation with Graph-Based Residual LSTM 2023 AAAI

    1 intro 1 1 背景 轨迹相似度 早期的度量采用成对匹配并依赖动态规划来计算最优对齐 DTW LCSS EDR 时间复杂度为 n是轨迹的平均长度 gt 对于大规模的轨迹数据并不是理想的选择 gt 会受到噪点的干扰 导致最终准确度下降

热门标签