VLDB 2020 | 基于深度强化学习的相似轨迹搜索
论文链接：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。该论文进行下列定义。
增强学习搜索方案
按照上述训练得到的网络Q进行分割方案的指导，与传统模型中分割的进程类似，不过分割的决策由agent作出。
增加了跳过行为优化后的增强学习搜索方案
为了增加分割决策的效益，增加了另一个action: skip，该行为跳过一些节点不再进行分割决策，即不会使用网络对其是否分割的决策做计算，跳过后其效果和不分割结果上是完全一样的。
下面给出优化后增强学习搜索方案的实例
该论文在多个数据集上进行实验，分别为Porto，Harbin，STATS SPORTS数据集，囊括车辆轨迹以及人类轨迹多种轨迹数据。同时将增强学习的方案与多个传统方案进行比较，结果如下：