论文笔记:Deep Representation Learning for Trajectory Similarity Computation

ICDE 2018

1 intro

1.1 背景

  • 用于计算轨迹相似性的成对点匹配方法(DTW,LCSS,EDR,ERP)的问题:
    • 轨迹的采样率不均匀
      • 如果两个轨迹表示相同的基本路径,但是以不同的采样率生成,那么这些方法很难将它们识别为相似的轨迹
    • 当样本点的采样率很低时,很难对齐相似轨迹的样本点
    • 当样本点噪声时,这些方法的性能可能会下降。
    • 复杂度大O(n^2)【n是轨迹长度】

1.2 论文贡献

  • 论文提出t2vec,基于深度表示学习推断和表示轨迹的基本路径信息
    • 通过利用存档的历史轨迹数据和一个新的深度学习框架来实现的
    • 计算两个轨迹之间的相似性只需要线性时间O(n + |v|) (|v|是向量v的长度)
  • 为了学习轨迹表示,自然地考虑使用RNN。但是简单地应用RNNs来嵌入轨迹是不切实际的
    • 使用RNNs获得的表示不能在由于低采样率或噪声引起的不确定性下揭示轨迹的最可能的真实路径
      • ——>提出了一个seq2seq模型,以最大化恢复轨迹真实路径的概率
    • 用于训练RNNs的现有损失函数没有考虑空间接近性
      • ——>设计了一个空间接近性感知的损失函数和一个单元预训练算法,鼓励模型为由相同路径生成的轨迹学习一致的表示’
  • 还提出了使用噪声对比估计的近似损失函数,以提高训练速度

2 问题定义和preliminary

2.1 定义

  • 基本路径
    • 基本路径是一个连续的空间曲线,表示对象所走的确切路径
    • 本路径只是一个理论概念,因为位置获取技术不连续地记录移动位置
  • 轨迹
    • 轨迹T是从移动对象的基本路径中得到的样本点的序列

2.2 问题定义

  • 给定一组历史轨迹,我们的目标是为每个轨迹T学习一个表示v∈Rn,使得该表示可以反映轨迹的基本路径,用于计算轨迹相似性

2.3 sequence encoder-decoder

  • 两个序列x=<x_t>_{t=1}^{|x|},y=<y_t>_{t=1}^{|y|},其中每个xt​ 和 yt​ 表示一个token

  • 编码器用于将序列x编码为一个固定维度的向量v,该向量保留了x中的顺序信息,然后解码器根据编码的表示v解码出序列y
  • RNN接受实值向量形式的输入,因此添加了一个token嵌入层来将离散token嵌入到一个向量中

  • 计算P(y|x)【链式法则】
      • 由于v编码了x中的顺序信息,我们有:
      •  
        • EOS是一个特殊的token,表示序列的结束

3 方法

  • 基本路径R在实践中通常是不可用的,为了绕过这个问题,论文利用两个观察
    • 非均匀、相对低采样率轨迹,表示为Ta;相对高采样率轨迹,表示为Tb
    • 相对高采样率的轨迹Tb比Ta更接近它们的真实基本路径R,它的不确定性更低
  • ——>最大化P(R∣Ta) 的目标替换为最大化P(Tb∣Ta)
  • 编码器将Ta嵌入到其表示v中,然后解码器将尝试恢复其相对高采样率的配对Tb

3.1 处理变化的采样率和噪声

  • 给定一组轨迹集合\{T_b^{​{(i)}}\}_{i=1}^N
    • N是集合的元素数量
    • 创建一组对 (Ta, Tb),其中Tb是一个原始轨迹,Ta是通过从Tb中随机丢弃样本点(丢弃率为r1)获得的
    • ——>每一个下采样的Ta也是非均匀采样的,因此代表一个具有非均匀和低采样率的实际轨迹
    • Tb的起点和终点在Ta中得到保留,以避免改变下采样轨迹的基本路径
  • 生成过程之后,我们使用序列编码器-解码器模型最大化所有(Ta, Tb)对的联合概率:
  • 在序列编码器-解码器模型中,输入应该是离散token的序列
    • 将空间分割成等大小的单元,并将每个单元视为一个token
    • 所有落入同一单元的样本点都被映射到同一token
      • ——>有助于克服非均匀和低采样率的问题
  • 现实的轨迹也可能有噪声样本点
    • 为了消除噪声样本点的影响,只保留被超过δ个样本点击中的单元
    • 这些单元被称为热单元,并形成最终的词汇V
    • 样本点由它们最近的热单元表示
  • 为了使学习到的表示对噪声数据更加鲁棒,我们进一步扭曲每一个下采样的Ta,基于一个扭曲率r2来创建扭曲的变体
    • 随机采样一部分点(由r2指示的大小),然后扭曲它们

3.2 学习表征

  • 原始的序列编码器-解码器并没有对单元间的空间关联进行建模
  • ——>论文提出了一个新的空间接近性感知损失函数和一个新的考虑空间接近性的单元表示预训练方法。
  • ——>为了进一步提高训练效果,还提出了基于噪声对比估计的近似损失函数

3.2.1 空间接近性感知损失函数

  • 损失函数的差异会鼓励模型学习不同的表示[32]
  • NLP中的损失函数大多为NLL
      • 简单地采用这个损失函数对于时空数据是有问题的
        • 图3中有两个从同一路线 R 生成的轨迹 Tb 和 Tb′ (在坐标转换为单元后,它们的对应序列分别是 y 和 ′y′ )
        • 轨迹的样本点交错在我们的空间分区中的单元
        • 设 Ta 和 Ta′ 分别表示 Tb 和 Tb′ 的子轨迹
          • 理想情况下,为 Ta 和 Ta′ 学习到的表示应该是相似的,因为它们都是从路线 R 生成的
          • 方程4中的NLL损失函数将 Tb 和 T′b 区分为两个相同的目标轨迹,因此它不能发现 Ta 和 T′a 之间的相似性
          • ——>这是因为方程4中的损失函数对输出单元进行了等权重的惩罚
          • 直观地说,接近目标的输出单元应该比远离目标的输出单元更可接受
            • 如果解码的目标单元是y3,损失函数会对输出y′3和y1进行相同的惩罚。这不是一个好的惩罚策略。
            • 因为y′3在空间上离y3更近,所以对于解码器输出y′3而不是输出y1来说,这是更可接受的
  • ——>空间接近性感知损失函数背后的直觉是,当我们试图从解码器解码目标单元yt时,我们为每个单元分配一个权重
    • 单元u ∈ V的权重与其与目标单元yt的空间距离成反比,因此单元离yt越近,我们将为其分配的权重越大
  • 尽管方程5中的空间接近性感知损失函数帮助我们为从同一路线生成的轨迹学习一致的表示,但每次我们解码目标yt时,都需要对整个词汇进行两次求和:
    • 当词汇大小 ∣V∣ 很大时,训练模型的成本将会很高(时间复杂度O(|y|×|V|)

3.2.2 近似空间接近性感知损失函数

  • 为了减少训练成本,根据以下两个观察设计了一个近似的空间接近性感知损失函数
    • 除了接近目标单元 yt 的单元外,大多数 wuyt​ 都非常小
      • 仅使用 yt 的K个最近的单元
    • 不需要计算方程6中的对数概率的确切值,只要我们可以鼓励解码器将概率分配给接近目标单元的单元
      • 使用噪声对比估计(NCE)来计算方程6中的对数概率
      • 类似于负采样
        • 从V−NK(yt) 随机抽样得到一小部分单元作为噪声数据来近似地最大化
    • ——>时间复杂度从O(∣y∣×∣V∣) 降低到O(∣y∣)

3.3 预训练单元表示

  • 为了进一步确保由相同路线生成的轨迹在潜在空间中有接近的表示,论文提出了一个单元表示学习算法,用于预训练模型嵌入层中的单元
    • 为空间上接近的单元学习相似的表示
  • 有两种直接的单元表示,都存在问题
    • one-hot
      • 失去了单元的空间距离关系,因为所有单元都被独立对待
      • 所提出的模型可能需要更多的训练时间来在单元嵌入层中发现空间关系
    • 单元的质心坐标(GPS坐标)
      • 自然地为单元编码了空间接近性
      • 但是将表示限制在一个二维空间中,这使得损失函数很难在它们的参数空间中进一步优化表示
  • 借鉴skip-grams捕获单元空间接近性
    • skip-grams背后的直觉是,意义相似的词语往往在相同的上下文中出现,如果我们使用一个词的表示来预测其周围的词,那么我们可以以一种捕获词语之间的语义距离的方式将词嵌入到欧几里得空间中
    • 论文通过根据对单元随机采样其邻居u′ ∈ NK(u)(也只考虑其K个最近的邻居),为给定的单元u ∈ V创建上下文
  • 此单元采样分布与方程5中的空间接近性权重类似
    • 他们的θ值不必相等
  • 对于每个单元u∈V,单元采样分布倾向于采样与其空间接近的单元作为其上下文
    • 通过最大化观察到给定单元u的其上下文中的相邻单元的对数概率C(u)

3.4 复杂度

需要O(n)时间将轨迹嵌入到一个向量中

O(|v|)比较两个向量的欧几里得距离,来衡量两个轨迹的相似性

衡量两个轨迹之间的相似性的时间复杂性为O(n + |v|)

4 实验

4.1 数据集

  • 波尔图轨迹
    • 19个月,包含170万轨迹
    • 每辆出租车每15秒报告一次其位置
    • 移除了长度小于30的轨迹,得到了120万轨迹
  • 哈尔滨轨迹
    • 8个月内从13,000辆出租车中收集的轨迹
    • 选择长度至少为30的轨迹,并且连续采样点之间的时间间隔小于20秒。这产生了150万轨迹

4.2 衡量标准

  • 相似轨迹搜寻
    • 从测试数据集中随机选择10,000个轨迹,记为Q
    • 选择另外m个轨迹,记为P
    • 对于每一个轨迹Tb ∈ Q,我们通过从中交替取点来创建它的两个子轨迹,分别记为Ta和Ta′,并使用它们构建两个数据集DQ = {Ta}和D′ Q = {Ta′ }
    • 对P中的轨迹执行相同的转换,得到DP和D′ P
    • 然后,对于每一个查询Ta ∈ DQ,我们从数据库D′ Q ∪ D′ P中检索其前k个最相似的轨迹,并计算Ta′的排名
  • 理想情况下,Ta′应该排在最前面,因为它是由与Ta相同的原始轨迹生成的
  • 使用D′ Q ∪ D′ P作为数据库而不是D′ Q ∪ P的原因是,查询轨迹的平均长度与数据库中的轨迹相似(使用D′ Q ∪ P也有类似的结果)

4.3 结果

4.3.1 mean rank

4.3.1.1 和m(P的大小)相关的结果

4.3.1.2 和downsampling rate 相关的结果

4.3.1.3 和distorting rate相关的结果

4.3.2 交叉相似性比较

一个好的相似性度量不仅应该能够识别同一基本路线的轨迹变体(自相似性),而且还应该保留两个不同轨迹之间的距离,而不考虑采样策略

计算如下:

Tb 和Tb′ 表示两个不同的原始率轨迹,Ta(r) 和Ta′(r) 是通过随机丢弃(或扭曲)样本点获得的其变体,其中丢弃(或扭曲)率为 r。

从测试数据集中随机选择10,000个轨迹对 (Tb,Tb′) 来计算它们的平均交叉距离偏差。较小的交叉距离偏差表示评估的距离非常接近真实值。

4.3.3 KNN 查询

  • 随机选择1000条轨迹作为查询,从测试数据集中选择10,000条轨迹作为目标数据库
    • 应用每种方法从目标数据库中找到每个查询轨迹的k个最近邻居(k-nn)作为其基准真值
    • 接下来,根据丢弃率r1(或扭曲率r2)随机丢弃或扭曲查询和数据库轨迹的某些样本点
    • 最后,对于每个变换后的查询,我们使用每种方法从目标数据库中找到其k-nn,然后将结果与相应的基准真值进行比较
  • 这种方法背后的逻辑是,一个鲁棒的距离测量应该适应非均匀和相对较低的采样率(或扭曲),并产生接近相对较高采样率(或非扭曲)的结果

4.3.4 延展性

4.3.5  网格数量的影响

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/130633.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

如何用Jmeter编写脚本压测

随着商业业务不断扩张&#xff0c;调用adsearch服务频率越来越高&#xff0c;所以这次想做个压测&#xff0c;了解目前多少并发量可以到达adsearch服务的界值。 这次选用的jmeter压测工具&#xff0c;压测思路如图&#xff1a; 同时&#xff0c;我也准备了一份软件测试面试视频…

基于Dlib+PyQt5+TensorFlow智能口红色号检测推荐系统——深度学习算法应用(含Python全部工程源码及模型)+数据集

目录 前言总体设计系统整体结构图系统流程图 运行环境Python环境TensorFlow环境安装face_ recognition安装colorsys模块安装PyQt 5安装QCandyUi库依赖关系 模块实现1. 数据预处理1&#xff09;源数据的存储2&#xff09;处理数据3&#xff09;合并得到json文件 2. 系统搭建1&am…

计算机竞赛 大数据商城人流数据分析与可视化 - python 大数据分析

0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; 基于大数据的基站数据分析与可视化 该项目较为新颖&#xff0c;适合作为竞赛课题方向&#xff0c;学长非常推荐&#xff01; &#x1f947;学长这里给一个题目综合评分(每项满分5分) 难度…

无涯教程-JavaScript - FVSCHEDULE函数

描述 FVSCHEDULE函数在应用一系列复合利率后返回初始本金的未来值。使用FVSCHEDULE以可变或可调汇率计算投资的未来价值。 语法 FVSCHEDULE (principal, schedule)争论 Argument描述Required/OptionalPrincipalThe present value.RequiredScheduleAn array of interest rat…

Android T 窗口层级其三 —— 层级结构树添加窗口

文章目录 序节点添加Task以DefaultTaskDisplayArea为父节点以Task为父节点 ActivityRecordWindowTokenWindowState以WindowToken为父节点以ActivityRecord为父节点 小结调用场景添加差异 流程分析添加log堆栈打印流程LauncherStatusBar 序 尚未添加窗口的层级结构树&#xff0…

关于ESP32S3无法识别到端口问题

前言 &#xff08;1&#xff09;因为实习问题&#xff0c;需要使用ESP32BOX进行二次开发。一般来说&#xff0c;接触一款MCU&#xff0c;3天上手是基本操作。但是对于乐鑫的芯片&#xff0c;环境搭建是真的折磨人&#xff08;苦笑&#xff09;&#xff0c;而且官方文档几乎没有…

安防监控/视频汇聚/云存储/AI智能视频分析平台EasyCVR显示CPU过载,该如何解决?

视频云存储/安防监控/视频汇聚平台EasyCVR基于云边端智能协同&#xff0c;支持海量视频的轻量化接入与汇聚、转码与处理、全网智能分发、视频集中存储等。安防视频监控系统EasyCVR拓展性强&#xff0c;视频能力丰富&#xff0c;具体可实现视频监控直播、视频轮播、视频录像、云…

Tomcat配置ssl、jar包

Tomcat配置ssl 部署tomcat服务&#xff0c;项目做到用https访问&#xff0c;使用nginx去做&#xff0c;访问任意一个子网站&#xff0c;都是https 或者 医美项目需要 上传jdk 456 tomcat war包 [nginx-stable] namenginx stable repo baseurlhttp://nginx.org/packages/…

DataGrip实时模板的配置2.0

印象里一直记着配置过代码实时模板&#xff0c;但是忘了换了工作电脑&#xff0c;之前配置的模板在我另一台电脑上 需要重新配置一下&#xff0c;我是笨蛋orz 配置方法和之前的一致 DataGrip实时模板的配置_王小小鸭的博客-CSDN博客https://blog.csdn.net/clover_oreo/articl…

AHR亚马逊账户健康评级多久更新,如何查看解决

AHR&#xff08;Account Health Rating&#xff09;即亚马逊账户健康评级&#xff0c;是亚马逊为卖家提供的一种评估卖家账户健康状况的工具。通过AHR&#xff0c;亚马逊会对卖家的账户进行综合评估&#xff0c;并给出相应的评级&#xff0c;以反映账户的整体表现和信誉。 亚马…

C++中使用R“()“标记符书写多行字符串

在C#中使用表示的字符串能够跨越数行。用于在C#中写JS或SQL代码比较方便。 string sqlInsert "INSERT INTO tb_param(protocol, slave, number, ptype, pid, name, format) VALUES(2, 24, 0, 1, 1, a04005, .3);INSERT INTO tb_param(protocol, slave, number, ptype, …

水循环原理VR实景教学课件开发

日本核污水排海让人们越来越重视海洋大气层水循环的安全&#xff0c;水循环是一个周而复始、循环往复的动态过程&#xff0c;为了将水循环过程以形象、生动地形式展示出来&#xff0c;水循环VR全景动态演示逐渐受到大家青睐。 传统的水循环教育方式通常是通过图片、动画或实地考…

REST风格【SpringBoot】

1.REST简介 行为动作 通常模块名使用复数&#xff0c;也就是加s 2.RESTful入门 Controller public class UserController {RequestMapping(value "/users", method RequestMethod.POST)public String save() {System.out.println("user save");return &…

iwebsec靶场 文件包含漏洞通关笔记3-session文件包含

目录 1.打开靶场 2.源码分析 &#xff08;1&#xff09;session文件包含漏洞的的工作原理 &#xff08;2&#xff09;sessionstart()做了哪些初始化工作 3.获取session文件位置 4.向session写入webshell 5.访问webshell 1.打开靶场 iwebsec 靶场漏洞库iwebsechttp://iw…

【CesiumJS入门】(10)绘制多边形(动态实时画面)

前言 如果你是在寻求解决方案&#xff0c;可以直接用cesium-draw这个插件。 鼠标左键添加点、右键完成绘制,单击右侧弹窗关闭按钮清空绘制。参考沙盒示例&#xff1a;Drawing on Terrain 直接上代码了 /** Date: 2023-07-12 18:47:18* LastEditors: ReBeX 420659880qq.com* L…

OneFormer: One Transformer to Rule Universal Image Segmentation论文笔记

论文https://arxiv.org/pdf/2211.06220.pdfCodehttps://github.com/SHI-Labs/OneFormer 文章目录 1. Motivation2. 方法2.1 与Mask2Former的相同之处2.2 OneFormer创新之处2.3 Task Conditioned Joint Training2.4 Query Representations2.4 Task Guided Contrastive Queries 3…

c++的引用和指针

我们要清楚的知道&#xff0c;使用指针和引用都可以的传入函数的main函数的变量在局部函数改变值时&#xff0c;main函数里面相应的变量也会改变值。但他俩的方式不同。 我们先来说指针&#xff0c;指针传入局部参数时&#xff0c;他会在创建个局部指针变量&#xff0c;然后把…

Unity——导航系统补充说明

一、导航系统补充说明 1、导航与动画 我们可以通过设置动画状态机的变量&#xff0c;让动画匹配由玩家直接控制的角色的移动。那么自动导航的角色如何与动画系统结合呢&#xff1f; 有两个常用的属性可以获得导航代理当前的状态&#xff1a; 一是agent.velocity&#xff0c;…

Pyinstaller打包EXE时添加版本信息、作者信息并在运行时读取外部配置文件

&#x1f9d1;‍&#x1f4bb;作者名称&#xff1a;DaenCode &#x1f3a4;作者简介&#xff1a;CSDN实力新星&#xff0c;后端开发两年经验&#xff0c;曾担任甲方技术代表&#xff0c;业余独自创办智源恩创网络科技工作室。会点点Java相关技术栈、帆软报表、低代码平台快速开…

【计算机网络】UDP协议详解

目录 前言 端口号的拓展 端口号范围划分 netstat pidof UDP协议 UDP协议端格式 UDP的特点 面向数据报 UDP的缓冲区 UDP使用注意事项 基于UDP的应用层协议 前言 我们前面讲完了http和https协议&#xff0c;它们都属于应用层&#xff0c;按照TCP/IP五层模…