徐家兴作者

VLDB 2020 | 基于深度强化学习的相似轨迹搜索

论文标题:Efficient and Effective Similar Subtrajectory Search with Deep Reinforcement Learning

论文链接:https://www.aminer.cn/pub/5e621f3d91e01160711d6015?conf=vldb2020

论文背景

相似轨迹搜索是一个非常基础的问题,比较两条轨迹之间的相似性具有非常实际的应用。然而,子轨迹的相似性搜索问题(similar sub trajectory search)却很少引起研究者的重视。例如对于一条较长轨迹,轨迹当中的一部分与搜索轨迹T相似度很高,我们希望通过某种方法将该轨迹部分,即子轨迹提取出来。这类问题在实际应用中有非常广泛的真实案例,其中一个应用场景是在体育数据分析问题当中。体育运动如足球经常会记录下比赛中运动员以及足球的轨迹,其中一个任务就是从数据库中找到整场比赛轨迹中的一段子运动轨迹,其与被检索的轨迹T有较高相似性。通过找到类似的运动行为模式可以方便体育分析者进行数据分析。该问题的难点是如何从整段轨迹中快速找到一段子轨迹,而这段轨迹和被检索轨迹T最为相似。最简单的方法是对所有子轨迹进行暴力检索,但是显然这不是一个理想方法。为了进行更加迅速地进行子轨迹相似性检索,该论文提出了多个方法,从简单到复杂。其中最亮眼的就是使用DQN(Deep Q Network)方法,该方法通过建立深度增强学习框架对子轨迹进行检测,并且通过大量时间验证其有效性。

问题定义

为了检测两条轨迹之间的相似性,该论文提供了三个测定指标表示两轨迹中的相似度,分别是t2vec,DTW和Frechet。其中t2vec通过使用一个循环神经网络RNN得到一条sequence轨迹的embedding表示形式。通过计算两轨迹的embedding距离的得到两轨迹的相似程度。值得一提的是,由于被检索轨迹T在检索过程中是不变的,所以只需要生成一次embedding,所以在三个方法中,t2vec是时间复杂度最低的相似度检测方法。 

论文模型

该论文的增强学习基础框架实际上是一个分割模型。即模型检索sequential轨迹的每一个节点,同时决定是否在这个点上进行切割,得到一段子轨迹的其中一点。但是其对在该点是否分割的决策则由增强学习的agent进行决策。

将轨迹分割看作一个MDP问题
当使用增强学习的方法解决该问题,需要对其四个要素进行定义:state,action,transition以及reward。该论文进行下列定义。

Deep-Q Network(DQN)学习方法

增强学习搜索方案
按照上述训练得到的网络Q进行分割方案的指导,与传统模型中分割的进程类似,不过分割的决策由agent作出。

增加了跳过行为优化后的增强学习搜索方案
为了增加分割决策的效益,增加了另一个action: skip,该行为跳过一些节点不再进行分割决策,即不会使用网络对其是否分割的决策做计算,跳过后其效果和不分割结果上是完全一样的。
下面给出优化后增强学习搜索方案的实例

实验部分

该论文在多个数据集上进行实验,分别为Porto,Harbin,STATS SPORTS数据集,囊括车辆轨迹以及人类轨迹多种轨迹数据。同时将增强学习的方案与多个传统方案进行比较,结果如下:

实验显示增强学习方法比较于传统方法有很大的提升,同时通过增加skip行为后节省下了一些时间,而其牺牲的效果实际上不是很多,完全可以接受。

AMiner学术头条
AMiner学术头条

AMiner平台由清华大学计算机系研发,拥有我国完全自主知识产权。系统2006年上线,吸引了全球220个国家/地区800多万独立IP访问,数据下载量230万次,年度访问量1000万,成为学术搜索和社会网络挖掘研究的重要数据和实验平台。

https://www.aminer.cn/
专栏二维码
理论深度强化学习VLDB 2020
相关数据
数据分析技术

数据分析是一类统计方法,其主要特点是多维性和描述性。有些几何方法有助于揭示不同的数据之间存在的关系,并绘制出统计信息图,以更简洁的解释这些数据中包含的主要信息。其他一些用于收集数据,以便弄清哪些是同质的,从而更好地了解数据。 数据分析可以处理大量数据,并确定这些数据最有用的部分。

时间复杂度技术

在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。例如,如果一个算法对于任何大小为 n (必须比 n0 大)的输入,它至多需要 5n3 + 3n 的时间运行完毕,那么它的渐近时间复杂度是 O(n3)。

数据库技术

数据库,简而言之可视为电子化的文件柜——存储电子文件的处所,用户可以对文件中的数据运行新增、截取、更新、删除等操作。 所谓“数据库”系以一定方式储存在一起、能予多个用户共享、具有尽可能小的冗余度、与应用程序彼此独立的数据集合。

推荐文章
暂无评论
暂无评论~