基于地理位置信息的应用和服务的迅速发展,对轨迹数据挖掘提出了新的需求和挑战.原始轨迹数据通常是由坐标-时间戳元组构成的有序序列,而现有的大多数数据分析算法均要求输入数据位于向量空间中.因此,为了将轨迹数据从变长的坐标-时间戳序列转化成定长的向量表示且保持原有的特征,对轨迹数据进行有效的表示是十分重要且必要的一步.传统的轨迹表示方法大多是基于人工设计特征,通常仅将轨迹表示作为数据预处理的一部分.随着深度学习的兴起,这种从大规模数据中学习的能力使得基于深度学习的轨迹表示方法相比于传统方法取得了巨大的效果提升,并赋予了轨迹表示更多的可能性.对轨迹表示领域中的研究进展进行了全面的总结,将轨迹表示按照研究对象的不同尺度,归纳为对轨迹单元的表示和对整条轨迹的表示两大类别,并在每种类别下对不同原理的方法进行了对比分析.其中重点分析了基于轨迹点的表示方法,也对近年来广泛使用的基于神经网络的轨迹表示的研究成果做了系统的归类.此外,介绍了基于轨迹表示的关键应用,最后对轨迹表示领域的未来研究方向进行了展望.
The rapid development of location-aware applications and services poses new challenges for trajectory data mining. The raw trajectory data usually consist of ordered sequences of coordinate-timestamp tuple, while many algorithms widely used for data analysis require input data to be in vector space. Therefore, it is an important and necessary step to effectively represent trajectory data from variable-length coordinate-timestamp sequence to a fixed-length vector that maintains the spatial-temporal characteristics of the movement. Most conventional trajectory representation methods are based on feature engineering, in which trajectory representation is usually considered as part of the data preprocessing. With the prevalence of deep learning, the ability of learning from large-scale data endows deep learning-based methods for trajectory representation with more potential and vitality, which achieved better performance compared to traditional methods. This paper provides a comprehensive review of recent progress in trajectory representation and summarizes the trajectory representation methods into two categories according to the different scales: trajectory unit representation and entire trajectory representation. In each category, the methods of different principles are compared and analyzed. Among them, the methods based on trajectory point are emphasized, and also the widely used methods based on neural networks are systematically classified. Besides, the applications related to trajectory representation under each category are introduced. Finally, the future research directions are pointed out in the field of trajectory representation.
随着移动终端的兴起和定位技术的日趋成熟, 基于位置信息的应用在人们的生产生活当中得到了前所未有的广泛应用.与此同时, 遥感卫星、监控影像系统以及具有GPS(global positioning system)和AIS(automatic identification system)功能的设备无时无刻不在收集海量的轨迹数据, 这其中既包含行人出行、动物迁徙、台风移动等自由轨迹, 也涵盖了汽车、舰船、飞机等交通工具的行驶轨迹.在如此庞大的轨迹数据量背后, 同样有着广泛的应用场景, 从景点推荐(如预测游客下一到达位置)到智慧交通(如交通流量预测)、从公共安全(如预测台风轨迹)到国防安全(如识别领海内异常舰船轨迹), 不一而足.近年来, 轨迹数据相关的研究工作的数量呈逐年递增的趋势, 如
近10年来, 计算机科学领域内轨迹数据相关的文章数量
Number of papers relating trajectory data in the field of computer science during the last ten years
传统的轨迹数据挖掘技术主要集中在轨迹相似性计算[
在众多基于轨迹数据的技术中, 对轨迹数据进行有效的表示, 始终是贯穿其中的一项重要任务.原始的轨迹数据在形式上通常表现为由经纬度坐标-时间戳三元组构成的有序序列, 然而常见的数据分析算法(例如支持向量机)均要求输入数据位于向量空间中, 因此, 原始轨迹数据往往不能直接作为算法的输入数据.为了解决这一问题, 对轨迹数据进行表示成为了一项不可或缺的工作, 其目的是将原始轨迹数据转换成为适合处理的数据形式后, 再输入到算法或模型中, 例如向量、图像、图等形式.从数据降维的角度来看, 原始轨迹数据可以被看作是一种高维数据, 三元组中不仅每一个元素均代表一个维度, 而且还混合了时间(时间戳)和空间(坐标)这两种不同维度的信息.显然, 这样的数据不利于算法进行处理, 因此需要使用轨迹表示来对高维轨迹数据进行降维.这样不仅能够从形式上对原始轨迹数据进行规范和简化, 还可以从冗余的原始信息中提取出有价值的部分, 使整个模型更加高效.除此之外, 好的轨迹表示不仅能够保留轨迹数据原有的特征, 还能在一定程度上弥补原始轨迹数据的缺陷.例如, 传感器在信号采集、传输的过程中往往会不可避免地受噪声影响, 好的轨迹表示能够在一定程度上缓解轨迹噪声所带来的误差.由于涉及到模型的输入, 因此轨迹表示质量的好坏会直接影响到轨迹数据挖掘的最终效果.随着物联网等相关技术的发展, 我们相信: 在未来, 基于轨迹数据的应用必将成为与人们日常生活关系最为密切的应用之一, 同时也一定会涌现出更多形式多样、含义丰富的轨迹数据.因此, 研究对轨迹数据的有效表示有着十分重要的现实意义.
轨迹表示一直以来都是轨迹数据挖掘的重要研究内容之一.在长期的研究和实践过程中, 研究人员相继总结了有关轨迹数据处理的技术, 其中不乏一些针对轨迹表示方法的整理工作.郑宇等人[
本文第1节对轨迹表示的定义、轨迹表示的难点以及轨迹表示方法的分类作一概述.第2节和第3节分别介绍对轨迹单元和对整条轨迹的表示方法.第4节讨论轨迹表示领域的未来研究方向.最后, 在第5节对全文进行总结.
由于GPS等定位技术通常不会连续地记录位置信息, 因此在实际中, 我们收集到的轨迹数据通常都是在真实轨迹上采样后得到的.为了便于表述, 如无特别说明, 下文中涉及到轨迹之处均是指轨迹的离散采样.
对轨迹进行表示面临着诸多挑战[
传统的轨迹表示方法多是基于人工设计特征, 例如从原始轨迹数据中提取出速度、加速度、角度等信息, 再将这些信息组合到一起来表示轨迹.但这类方法受限于特征提取能力, 通常仅将轨迹表示作为数据预处理的一部分.随着深度学习逐渐流行起来, 利用卷积神经网络(CNN)和循环神经网络(RNN)来学习轨迹表示的方法取得了长足的进展, 其核心思想是, 通过数据驱动的方式来学习从原始轨迹到表示向量的映射过程.这类方法虽然在特征提取能力方面有较大的提升, 但也易受端到端训练框架的限制.这部分会在第3.2节中详细说明.
近年来, 有越来越多的工作在众多前人研究成果的基础上, 对轨迹数据混用了多种不同类型的表示方法, 导致轨迹表示环节更加难以直观地体现出来.这对轨迹表示方法的整理工作提出了一定的挑战.
在已有的涉及到轨迹表示的文献中, 通常是按照轨迹表示所使用的模型对轨迹表示方法进行分类, 例如CNN、RNN、LSTM、Seq2Seq等.而我们认为: 轨迹数据本身就有着非常丰富的表现形式, 轨迹数据应当是轨迹表示问题的重点.因此, 本文避开了传统的按照模型类别对轨迹表示方法分类的思路, 回归到轨迹数据本身, 将轨迹数据按照不同的尺度划分为轨迹单元和整条轨迹, 分别归纳了对轨迹序列单元的表示方法和对整条轨迹序列的表示方法.对轨迹序列单元的表示方法主要是以轨迹序列单元为基础, 通过学习单元的表示, 进而得到轨迹序列的表示.其中, 轨迹序列单元可以细分为轨迹点和轨迹段; 对整条轨迹序列的表示则着眼于完整的轨迹序列, 直接学习整条轨迹的表示.接下来将对这两类方法分别进行介绍.轨迹表示方法的整体分类见
轨迹表示方法的分类
Classification of trajectory representation methods
表示方法类别 | 关健技术 | 表示结果 | 主要特点 | ||
对轨迹单元的表示 | 基于轨迹点的表示方法 | 基于划分[ |
确定兴趣点 | 兴趣点序列 | 缓解数据稀疏问题, 具有一定的语义信息 |
划分网格 | 网格序列 | 缓解数据稀疏问题 | |||
基于人工设计特征[ |
专家知识 | 特征序列 | 依赖专家知识, 特征表达能力有限 | ||
基于词袋[ |
定义词语; 词嵌入 | 词向量序列 | 考虑轨迹序列的上下文信息 | ||
基于图表示[ |
构建图; 图节点表示 | 图节点序列 | 综合考虑多类型信息 | ||
基于轨迹段的表示方法[ |
轨迹分段 | 轨迹段特征序列 | 适用基于轨迹点的表示方法; 相比轨迹点, 轨迹段包含的信息更丰富, 可操作空间更大 | ||
对整条轨迹的表示 | 基于曲线拟合[ |
选择参数曲线 | 多项式参数 | 数学意义明确; 表示能力有限 | |
基于图像[ |
提取图像特征 | 轨迹图像 | 空间信息直观 | ||
基于神经网络[ |
设计网络结构和损失函数 | 特征向量 | 特征提取能力强; 任务相关 |
如上所述, 轨迹数据属于时空数据的一种, 天然地表现为序列形式.因此, 有很多轨迹表示方法都选择在轨迹序列单元的基础上学习轨迹表示.在本节中, 我们总结了基于轨迹点和轨迹段这两种尺度下的轨迹序列单元表示方法.
通常, 我们拿到的轨迹数据是如定义2所示的带有时间信息的二维坐标序列
(1) 不同的轨迹离散序列通常包含不同数量的轨迹点, 其数目可能差异巨大, 即有的轨迹采样十分致密, 而有的轨迹采样则十分稀疏.这对轨迹表示方法的稳健性提出了很高的要求; 此外, 即使是在同一条轨迹内部, 不同区段的采样密度也可能会有所差异.
(2) 原始轨迹数据所包含的信息是松耦合的(loose coupling), 例如时间信息(即时间戳
正是因为直接使用原始轨迹数据存在着诸多不便, 因此涌现出了各种方法来对轨迹序列加以处理.在讨论具体的方法之前, 我们首先提出一个序列-序列框架, 该框架总结了此类方法的常用模式, 将不同种类的方法纳入到相同的符号和概念基础上.
在序列-序列框架中, 表示方法的目标是基于原始的轨迹序列得到新的序列:
其中,
我们首先讨论轨迹序列中基于轨迹点的表示.由于数据采样的特性, 轨迹点是原始轨迹序列数据中最基本的单元, 在形式上由坐标点和时间戳组成.
在处理真实轨迹的过程中, 我们经常会面临轨迹长度过长和轨迹分布稀疏的问题, 这两者都会导致数据空间的激增.具体来说, 前者会因为轨迹点过多, 导致轨迹数据的处理时间增加; 后者会造成轨迹点的坐标值值域过大, 导致坐标取值稀疏, 进而影响表示效果, 如
轨迹序列分布稀疏示意图
An illustration of sparse distribution of trajectory sequences
基于划分的方法的主要思想就是将一些相互邻近的轨迹点看作一个集合, 转而用该集合的标识来代表集合中的轨迹点, 进而由多个集合的标识所构成的序列来表示轨迹.这既是一种近似, 也是一种抽象.在实际工作中, 通常使用兴趣点(point of interest)和网格(grid)来作为集合的基本单元.
(1) 划分兴趣点
借助兴趣点信息来划分轨迹, 是解决单条轨迹过长问题的一种有效方法.其基本假设是: 轨迹的产生是基于一系列兴趣点, 从而可以将轨迹点序列转化为兴趣点序列.例如, 一个人日常上班的轨迹可以用家、车站、公司、餐馆等兴趣点来表示.对应到序列-序列框架中, 新序列的数据点就是轨迹中的兴趣点, 它是部分原始轨迹点的集合:
其中,
具体实现时, 通常是以兴趣点为圆心、以一定的长度为半径在地图中划出一个圆形区域, 凡是落在该区域内的轨迹点都由该兴趣点来表示.轨迹则按照从一个兴趣点到下一个兴趣点的顺序依次表示出来.
划分兴趣点不仅可以大大简化轨迹数据的复杂程度, 而且还可以在一定程度上得到轨迹的语义信息, 因为每个兴趣点通常都具有相应的语义, 例如“公司”的语义信息和工作高度相关.这类方法常常被用于轨迹分类问题.不过, 基于兴趣点的划分方法的局限之处在于对额外地理位置信息的依赖.例如, 在城市中确定兴趣点需要依赖建筑、街区的功能信息.而在一些大范围场景中, 例如候鸟迁徙、台风移动等, 往往会由于缺少额外信息而难以提取出有效的兴趣点; 即使存在一些兴趣点, 也会由于轨迹空间过于广阔, 使得轨迹的兴趣点序列显得十分稀疏, 难以有实际用处.
(2) 划分网格
近年来, 轨迹数据挖掘领域中许多有代表性的工作都采用了划分网格这一方法对轨迹进行处理.该方法将地图划分成等间距的网格, 每个小网格都有各自的标识.落入同一网格所表示范围中的轨迹点都由该网格的标识来表示.于是, 原始的轨迹点序列被转化成为一系列网格构成的序列:
其中,
关于网格表示, 最简单的做法是使用独热向量[
划分网格的方法主要解决了原始轨迹数据分布稀疏的问题, 此外, 还可以缓解轨迹采样率不一致和采样率低的问题[
早期的轨迹表示方法大多使用人工设计的特征来表示轨迹, 因此这类方法也常被称为轨迹特征提取.之所以可以进行特征提取, 是因为原始的轨迹点序列中包含了丰富的空间和时间信息.这类方法的核心思想是: 利用已有的时空信息来挖掘新的特征, 将原始的轨迹点序列转化为特征序列.
其中,
郑宇等人在文献[
然而, 基于人工设计特征的轨迹表示方法有如下局限: 1) 特征的设计高度依赖专家知识, 而且针对不同的轨迹应用场景, 往往需要重新选择和优化特征, 这增加了此类方法的应用难度; 2) 人能够从轨迹数据中抽象出来的特征种类是有限的, 随着特征工程的深入, 新特征的获取会越来越难, 导致基于人工设计特征的方法所带来的增益趋于平缓.
近年来, 自然语言处理领域的研究取得了长足的进展[
基于词袋的表示方法本质上是将轨迹数据看作由一堆词语构成的词袋, 其中, 词语可以是轨迹点、轨迹段或是兴趣点等.然后再利用词嵌入(word embedding)的方法来学习“词语”的表示, 即轨迹序列单元的表示, 进而可以得到整条轨迹的表示:
其中,
这类方法的流程主要分为两步: 定义词语和词嵌入.
定义词语最简单的做法是直接将轨迹点看作词语[
词嵌入是词表示(word representation)[
近年来, 常用于轨迹表示的词嵌入方法主要有两类.
(1)
第1类方法借鉴了word2vec[
文献[
其中,
使用word2vec学习轨迹单元表示的优势在于: 能够利用无标签的轨迹单元上下文将轨迹单元转化成有标签的表示向量; 同时, 该表示向量能够捕获轨迹单元在空间中的邻近关系, 即, 在空间中邻近的轨迹单元有相似的向量表示.不过, 此类方法的局限在于无法获得词袋之外的轨迹单元的表示, 即, 未在训练集中出现过的轨迹单元没有相应的轨迹表示向量.因此, 此类方法通常与划分网格的方法相结合来缓解数据集的稀疏问题, 从而使得训练集能够覆盖到尽可能多的轨迹数据.
(2) 第2类方法是利用前馈神经网络对轨迹单元进行嵌入.
上述通过word2vec学习轨迹单元表示的过程在某种意义上属于数据预处理的范畴, 因为其学习过程独立于模型的训练过程, 即先通过word2vec对轨迹进行表示, 再将表示后的数据输入到模型中进行训练.其不足之处是, 轨迹的表示一经确定就不再改变.为了解决这一问题, 近两年来, 不少工作均采用前馈神经网络对轨迹序列单元进行嵌入表示.这样做的好处在于: 对轨迹单元进行嵌入属于模型的一部分, 嵌入的结果可以随着模型训练一起优化.个中原因一方面是得益于算力的提升; 另一方面是随着轨迹应用场景的扩展, 出现了诸如安防监控这样的小型场景下的轨迹分析需求, 使得在有限的轨迹数据空间中对轨迹单元嵌入变得可行.这一类方法的代表性的工作是文献[
其中,
我们上述的所有表示方法都是基于轨迹序列这一基本数据形式来演绎的, 然而轨迹数据除了序列形式之外, 还可以转化成其他的数据形式, 这极大地延展了轨迹表示领域的深度和广度.基于图表示的方法就是其中最有代表性的一种.
此类方法的重点在于如何构建图, 主要任务是对节点和边进行定义.一旦顺利将轨迹数据表示成图, 那么剩下的工作就是利用图表示方法将节点或边嵌入到低维空间中, 使得图的结构信息和属性能够在最大程度上保留.图表示的方法众多, 且不同类别的方法有各自的优缺点[
(1) 交通路网场景
交通路网本身就可以看作为一个有向图
(2) 自由空间场景
在自由空间中, 由于缺少像交通路网那样既有的物理条件, 往往需要利用其他信息来构建图, 如时间信息、语义信息等, 这也使得此类方法在内容上更加丰富.常见的方法是将城市区域或兴趣点作为图的节点.之所以不直接将轨迹坐标点作为图的节点, 是因为除了要考虑原始数据稀疏的问题外, 往往还会面临数据浮动(data variation)的问题[
文献[
现在我们来看基于轨迹段的表示方法, 这类方法的主要思想是, 将轨迹段作为轨迹序列的基本单元进行表示.所谓的轨迹段是指由若干个连续的轨迹点构成的集合, 在形式上表现为轨迹序列的子序列.之所以使用轨迹段作为序列单元, 一方面是因为相比于整条轨迹, 分段后不仅能够降低计算复杂度, 而且能够帮助我们挖掘出更丰富的信息, 例如不同区间段的轨迹模式; 另一方面是因为在一些场景中轨迹段更适合用来表示轨迹, 例如城市交通路网天然地由众多规整的路段组成, 位于同一路段中的所有轨迹点都不妨用该路段的标识来表示.
除了文献[
所谓的路段是指连接两个路口的道路, 而路网可以看作是由路段和路口组成, 如
路网结构示意图[
An illustration of road network[
其中,
从某种意义上讲, 轨迹段可以看作是一个更大的“轨迹点”.因此, 基于轨迹点的表示方法也大都适用于轨迹段的表示.文献[
此外, 同样是轨迹序列单元, 轨迹段和轨迹点的不同之处在于: 轨迹段本身就是包含了若干个轨迹点的子序列, 因而可以有更丰富的表示方法.最简单的做法是基于组合的方式, 即先将轨迹点表示成向量, 然后将轨迹段内所包含的轨迹点的表示向量组合到一起作为轨迹段的表示.但更常见的做法是: 利用轨迹段本身是序列的特点, 进而使用RNN来学习轨迹段的表示[
通过对轨迹单元如轨迹点和轨迹段进行表示, 原始的坐标-时间戳序列被转化成为新形式表示下的序列.相比于原始数据, 新表示下的轨迹序列不仅将时空信息更紧密地嵌入在一起, 而且在形式上更适合机器学习模型进行处理.一系列基于序列数据的轨迹应用可以就此开展, 例如轨迹序列预测、轨迹序列相似性计算等.
时空序列数据包含了丰富的上下文信息, 轨迹预测的目标就是基于用户的历史轨迹数据来分析和预测用户下一步将去往何处.此类应用不仅可以用来做基于地理位置的兴趣推荐, 还可以服务于公共生活, 例如预测交通堵塞将在何处发生, 或哪个城市将遭受恐怖组织袭击.
文献[
文献[
时空轨迹相似性计算, 即计算不同轨迹间的相似程度, 是诸多轨迹应用的基础.现有的轨迹相似性计算方法主要可以分为两类: 基于轨迹序列和基于表示向量.
传统的方法多是基于轨迹点序列, 通过点对匹配(pairwise points-matching)的方法来计算相似性, 即, 按某种方式累加轨迹点对之间的距离来作为度量轨迹间相似程度的依据.其中, 全局匹配度量方法有欧式距离法[
针对轨迹数据采样率低、采样率不一致、采样过程存在噪声等问题, 基于表示向量的方法试图通过将轨迹数据转化成向量来克服轨迹序列的不足.文献[
通过轨迹相似性计算, 我们可以从实验上较为直接地度量基于表示向量方法的效果.为此, 首先需要定义相似轨迹.例如, 文献[
在有了上述的轨迹相似性计算作为铺垫后, 轨迹聚类就是在其基础上进一步将相似的轨迹段或轨迹划分到一起.常见的轨迹聚类方法是将轨迹或轨迹段表示成向量, 通过计算向量间的距离来完成聚类.
文献[
然而文献[
接下来我们介绍针对整条轨迹的表示.从算法逻辑的角度来看, 上述的基于轨迹序列单元的表示方法遵循的是分治(divide and conquer)的思想.轨迹序列首先被分成若干个单元(即divide), 然后再对轨迹序列单元进行表示, 进而整条轨迹将会以新形式下的单元序列呈现出来(即conquer).而有别于上述逻辑, 针对整条轨迹的表示方法不再聚焦于序列单元的表示, 而是将整条轨迹序列视为一个单元来表示[
这类方法尤其常见于早期的一些工作.正如我们在定义1中所述, 轨迹可以看作是空间坐标关于时间的函数, 基于曲线拟合的方法的基本思想就是: 通过函数曲线来近似轨迹的形状, 一旦能够实现这种近似, 那么轨迹将不再由轨迹点序列表示, 取而代之的是由拟合函数的参数来表示, 即
最朴素的一种方法就是线性插值, 即将相邻的两个采样点用直线相连, 轨迹则由若干个分段函数来表示.但通过这样方式拟合得到的分段函数是不光滑的, 不仅不能表示真实的轨迹(真实的轨迹不是折线段), 而且在数学上也难以处理.常见的做法是用低阶曲线来近似轨迹(例如三阶曲线).文献[
基于曲线拟合的方法的优点是数学意义明确, 但其局限也显而易见.
(1) 仅仅通过近似轨迹形状所挖掘到的信息是十分有限的, 难以获知隐藏在轨迹背后的行为模式.此外, 在现实中, 尤其是在大范围场景下的轨迹通常较为复杂, 因此往往需要靠多段曲线拼接的方式来近似, 这给此类方法的应用带来了挑战.通过曲线拟合得到的轨迹表示通常适用于轨迹较为规范的小范围场景, 例如安防视频监控、车站人流监控.
(2) 拟合曲线的阶数不宜过高, 原因是可能会导致多项式数值在两点之间取得非常大的值, 并且这种数值的偏移会随着多项式阶数的增大呈指数增长.另外, 高阶多项式对数据点的微小变化非常敏感[
上述的种种因素都在一定程度上限制了基于曲线拟合方法的应用范围.
将轨迹数据转化成图像进行处理是另一种新颖的角度, 这类方法的灵感来自于深度神经网络在图像领域取得的诸多进展.最简单的转换方法是将整个地图看作一幅二值图像, 凡是轨迹经过的像素点将像素值设置为1, 没有经过的像素点则将像素值设置为0, 如
轨迹图像示意图
An illustration of trajectory image
文献[
从真实GPS轨迹提取的轨迹图像示例[
Examples of trajectory images extracted from real GPS trajectories[
一旦将轨迹表示成图像之后, 对轨迹进行表示的任务就进一步转化成为提取图像的特征, 故可以使用诸如深度神经网络、卷积神经网络[
原始的轨迹序列形式不能直接反映轨迹点之间的空间关系, 例如空间上邻近的轨迹点不一定在序列上相邻.而使用图像来表示轨迹的最大优势就在于图像天然地体现了空间关系, 空间上邻近和时序上邻近的位置点都可以通过相邻的像素点来表示.不过, 将轨迹数据转化为图像需要处理好分辨率与稀疏性之间的矛盾, 即图像的分辨率越高(即像素点的尺寸越小), 越能描绘出轨迹的细节; 但同时也会因为像素点过多而导致轨迹数据的稀疏, 如
使用神经网络学习轨迹表示的方法与前述方法的主要区别在于, 神经网络是以端到端(end-to-end)的方式来学习轨迹表示: 神经网络的一端接收输入, 另一端产生输出, 通过直接考虑输入和输出来优化模型参数.其优势显而易见, 即模型的每一步优化都以目标函数为导向.随着深度学习的发展, 这类方法以其超越传统表示方法的效果而逐渐得到研究人员的青睐.
在轨迹表示的实际工作中, 由于神经网络往往要求输入数据为数值向量, 因此常先由其他表示方法将原始轨迹数据初步表示成向量, 再经神经网络进一步学习轨迹表示.例如, 文献[
不过, 通过神经网络学习轨迹表示的方法也存在不足之处.
●轨迹表示难以显式地体现在神经网络模型中.神经网络的学习目标通常是诸如分类、预测等, 而非学习轨迹表示向量.换句话说, 轨迹表示向量往往是模型优化过程的副产品.以多层前向传播神经网络为例, 从理论上讲, 任何一层中间层的输出都可以作为原始轨迹数据的向量表示.
●轨迹表示向量是任务相关的, 即针对某一个任务学到的轨迹表示, 通常不适用于其他类型的任务.这主要是受端到端学习方式所限, 如果任务的优化目标发生改变, 那么轨迹表示则需要重新学习.
近年来, 常用于轨迹表示的神经网络模型主要是循环神经网络和卷积神经网络.
循环神经网络因其处理序列数据的天然优势, 最先在轨迹数据挖掘中被广泛应用.我们以最简单的循环神经网络为例: 对于长度为
在实际工作中, 通常会使用循环神经网络的各种变体, 例如使用LSTM[
不同于循环神经网络仅考虑轨迹序列在时间维度上的影响, 卷积神经网络的特点在于其可以对空间维度上一块“区域”内的数据进行处理.换句话说, 循环神经网络更多地是将轨迹看作一维时间序列, 而卷积神经网络则更多地是将轨迹看作多维张量.
文献[
相比于对轨迹序列单元的表示, 针对整条轨迹序列表示的研究工作偏少.其原因主要在于:
(1) 数据标签较为单一.一条轨迹中通常包含了丰富的信息, 例如轨迹中的不同区段都可以拥有不同的属性和标签.而若将整条轨迹序列视为基本数据单元, 那么一条轨迹只能拥有一个相应的标签, 这在一定程度上限制了该方法的使用场景.
(2) 不同的轨迹数据往往有不同的长度, 即轨迹序列所包含的轨迹点的数量不同.由于大多数机器学习算法, 尤其是神经网络均要求输入数据是固定长度, 这种长度上的不一致为算法设计带来了挑战.
(3) 缺乏一种有效的距离度量方式.在许多轨迹数据挖掘任务中都对计算轨迹间相似性提出了要求, 例如轨迹聚类、轨迹异常检测等.然而直接用整条轨迹计算相似性, 除了上述长度不一致的缺点外, 还会面临不同轨迹采样率不一致等问题, 这共同加剧了直接使用整条轨迹的难度.
尽管面临上述难点, 依然有一批工作从各个角度出发丰富了这一类方法的应用场景.
轨迹分类的目标是区分不同模式下的轨迹或轨迹段, 例如, 轨迹按照交通模式可以具体分为步行、骑车、乘坐公交、乘坐出租车等.对轨迹进行分类是众多应用的基础, 可以提供丰富的信息帮助我们理解移动主体.例如, 对实时轨迹的分类可以用来识别可疑的移动主体[
传统的轨迹分类方法通常使用人工设计的特征作为分类的依据.文献[
神经网络也被广泛用于此类应用中.文献[
此外, 随着移动互联网的发展, 近年来出现了众多互联网打车平台, 如Uber、滴滴等.这种通过移动设备和应用程序将司机和乘客联系起来的出行服务逐渐成为了一种新的交通模式.不过, 考虑到对用户隐私的保护, 通常难以从打车平台获取此类数据.为了解决这一问题, 文献[
轨迹异常检测可以看作是轨迹分类的特殊情况, 即把数据集中的正常轨迹和异常轨迹区分开来.但异常检测通常要比一般的分类问题更难, 其原因主要在于异常轨迹的样本量较少, 导致异常模式难以被建模.
文献[
轨迹隐私是指产生轨迹的用户不愿意透露的关于用户身份的信息以及从轨迹中推导出的相关信息, 例如用户的家庭住址、个人偏好、生活习惯等.随着越来越多基于位置数据应用的出现, 对轨迹主体的轨迹隐私保护逐渐成为一个重要问题.
传统的轨迹隐私保护技术主要可以分成两类.第1类是基于泛化的方法, 其主要思想是将轨迹点泛化到相应的匿名区域, 从而实现对轨迹隐私的保护.其中最有代表性的方法是位置
虽然众多研究工作针对各自的应用背景对轨迹表示提出了不同的解决方法, 但随着轨迹数据的日益丰富和轨迹应用场景的不断扩展, 依然存在许多具有挑战性的问题有待解决.本节将对一些现有研究工作的不足以及未来值得深入研究的问题作一探讨.
单纯依靠GPS轨迹数据已经逐渐难以满足当今轨迹应用的需求.例如, 随着经济全球化程度的加深, 航运业务的快速增长要求更有效、更及时的轨迹获取方式来避免海上交通事故, 如综合使用AIS、GPS和ARPA (automatic radar plotting aid)等数据.与此同时, 随着数据获取方式的不断丰富, 人们可以收集到越来越多不同来源、不同形式的轨迹数据.例如, 基于地理位置的社交网络产生了大量具有时空标记的多模态数据, 其中包括GPS信息、文本描述、图片、短视频等.综合考虑多种模态的数据, 有利于更加全面地获取轨迹信息, 从而获得表达能力更强的轨迹表示.如何对多模态数据进行组织和融合, 逐渐成为了轨迹表示领域所面对的新挑战.
多模态数据融合涉及模态转换、对齐、消歧、融合表示等多方面内容.早期的轨迹数据融合表示方法通常是将不同类型的数据拼接成向量, 例如将时间信息、位置信息、用户标识以及兴趣点信息分别表示成向量后, 再拼接到一起作为轨迹最终的表示向量[
由于轨迹数据在采集、传输等过程中存在的诸多限制, 往往导致收集到的轨迹数据中会不可避免地存在相当一部分的低质量轨迹数据.例如, 由于受采集精度、海上信号漂移、网络传输条件等因素的影响, AIS系统在实际场景中采集到的轨迹数据往往不尽如人意.质量不一、噪音、缺值等一直是船舶时空轨迹数据中普遍存在的问题.低质量轨迹数据会从源头上影响轨迹数据挖掘的效果.因此, 如何得到高质量的轨迹数据和高质量的轨迹表示, 一直以来都是轨迹数据挖掘领域的研究重点.
近年来, 随着以GAN为代表的生成模型的广泛应用, 利用生成模型来生成高质量轨迹数据成为了解决上述问题的一种新思路.生成的高质量轨迹不仅可以用来缓解轨迹稀疏、噪声等问题, 而且基于高质量轨迹得到的轨迹表示也会更加稳健.文献[
现有的轨迹表示方法大多只聚焦于轨迹数据本身, 很少考虑潜在的语义信息, 从而影响了轨迹建模的准确性.如在轨迹异常检测领域, 根据出租车辆的绕路等行为模式, 可以将一些轨迹判定为异常.然而, 如果考虑轨迹的语境, 比如途经某正在举办大型体育赛事的拥堵路段, 那么这些“异常”轨迹在当前语境下实际上应当是正常的.因此, 随着语义信息的获取越来越方便, 例如大型活动、天气、景点和突发事件等, 轨迹表示不应仅局限于轨迹本身, 还应充分利用从其他信息源获得的语义信息, 以得到表达能力更强的语义轨迹表示.使用语义轨迹表示有助于丰富轨迹数据挖掘的内容.例如, 将POI等信息作为轨迹的位置语义, 可以在度量时空相邻的同时增加对轨迹语义相似的度量和判断, 从而实现对人群更细粒度的识别和分类.因此, 近年来, 对语义轨迹的研究逐渐成为了一个新的研究热点, 其主要任务是通过借助外部语义信息来对轨迹数据的语义信息进行推断、匹配和挖掘, 从而将无语义的轨迹数据转化成带有语义信息的轨迹表示.目前, 针对语义轨迹表示的探索主要集中在以下两类方法上.
●第1类方法主要是通过引入地理位置的语义注释(例如兴趣点、兴趣区域和路径的语义注释)或借助已知语义信息的数据(例如地图、文本), 为轨迹单元匹配或生成语义标签.文献[
●第2类方法主要是在缺少外部语义信息的条件下, 通过融合先验知识和轨迹数据的自身属性来挖掘轨迹单元之间的隐含语义联系.其中最有代表性的一类工作是借鉴分布式词向量表示的思路, 将轨迹单元视为词语, 利用无监督学习的方式将轨迹单元映射到连续的向量空间中, 以此来挖掘邻近轨迹单元的上下文关系, 进而得到轨迹的语义表示[
现有的相关工作依然有很多挑战未解决.1) 当前的研究往往假设语义信息是确定的, 而实际环境中, 轨迹位置的语义数据通常是繁多且模糊的.例如, 同一个位置附近可能有多个重复的兴趣点, 从而造成语境上的冗余; 此外, 尽管重要事件可以显著地影响轨迹的语义解释, 但用户可能是因为相关事件而前往某场所, 也有可能只是经过该场所.因此, 轨迹数据与语义信息的相关程度度量、个性化的轨迹语义信息过滤等, 也是重要的研究问题.2) 现有对语义轨迹表示的研究主要侧重于局部语义, 很少对轨迹的全局语义进行表征.而不同粒度的语义单元也会对轨迹表示的质量带来影响.因此, 如何选择恰当的语义单元粒度, 以及如何构建可靠的语义轨迹距离度量方法来支撑有效的轨迹表示等, 都值得进一步深入研究.
定位设备的普及和基于位置信息应用的发展, 为轨迹数据挖掘提供了海量的数据支持和应用需求.轨迹数据挖掘的研究领域必然会随着数据的演化和技术的进步而不断地发展.而轨迹表示承担着将原始数据转化为模型输入的重要任务, 是轨迹数据挖掘中的一项关键技术, 研究者们针对不同应用背景下的轨迹表示做了大量的工作.本文对近年来轨迹表示的主要研究成果进行了全面的梳理和总结, 将轨迹表示按照研究对象的不同尺度分为对轨迹单元的表示和对整条轨迹的表示, 其中, 对每一种类别的表示方法按照方法的不同原理进一步做了详细的对比分析, 并给出了相应的轨迹数据挖掘应用.最后, 本文对轨迹表示领域现有工作研究不足的问题和未来值得研究的方向提出了自己的观点.
et al. Deep representation learning for trajectory similarity computation. In: Proc. of the IEEE 34th Int'l Conf. on Data Engineering (ICDE). 2018. 617-628. [doi: 10.1109/ICDE.2018.00062]]]>
doi: 10.1109/icws.2019.00059]]]>
doi: 10.1109/IJCNN.2017.7966345]]]>
Han B, Liu L, Omiecinski E. A systematic approach to clustering whole trajectories of mobile objects in road networks. IEEE Trans. on Knowledge and Data Engineering, 2017, 29(5): 936-949. [doi: 10.1109/TKDE.2017.2652454]
Endo Y, Toda H, Nishida K, Ikedo J. Classifying spatial trajectories using representation learning. Int'l Journal of Data Science and Analytics, 2016, 2(3-4): 107-117. [doi: 10.1007/s41060-016-0014-1]
http://arxiv.org/abs/1705.02636 ]]>
Chen X, Ye Q, Zou J, Li C, Cui Y, Jiao J. Visual trajectory analysis via replicated softmax-based models. Signal, Image and Video Processing, 2014, 8(1): 183-190. [doi: 10.1007/s11760-014-0671-2]
doi: 10.5244/C.22.103]]]>
Feng W, Han C. A novel approach for trajectory feature representation and anomalous trajectory detection. In: Proc. of the 2015 18th Int'l Conf. on Information Fusion. 2015. 1093-1099.
https://doi.org/10.24963/ijcai.2017/430 ]]>
et
Chow KH, Hiranandani A, Zhang Y,
doi: 10.1007/978-3-319-06605-9_5]]]>
Yang C, Sun M, Zhao WX,
Gao Q, Zhou F, Zhang K, Trajcevski G, Luo X, Zhang F. Identifying human mobility via trajectory embeddings. In: Proc. of the IJCAI Int'l Joint Conf. on Artificial Intelligence. 2017. 1689-1695.
Zhou F, Gao Q, Trajcevski G, Zhang K, Zhong T, Zhang F. Trajectory-user linking via variational autoencoder. In: Proc. of the IJCAI Int'l Joint Conf. on Artificial Intelligence. 2018. 3212-3218.
Zheng Y. Trajectory data mining: An overview. ACM Trans. on Intelligent Systems and Technology, 2015, 6(3): 1-41. [doi: 10.1145/2743025]
http://arxiv.org/abs/1906.04928 ]]>
He X, Cormode G, Machanavajjhala A,
et al. An adaptive trajectory clustering method based on grid and density in mobile pattern analysis. Sensors, 2017, 17(9): Article No. 2013. [doi: 10.3390/s17092013]]]>
et al. SERM: A recurrent model for next location prediction in semantic trajectories. In: Proc. of the 2017 ACM on Conf. on Information and Knowledge Management. 2017. 2411-2414. [doi: 10.1145/3132847.3133056]]]>
doi: 10.1109/IDEAS.2004.1319817]]]>
doi: 10.1145/1367497.1367532]]]>
doi: 10.1145/1409635.1409677]]]>
doi: 10.24963/ijcai.2018/545]]]>
http://arxiv.org/abs/1806.01482 ]]>
et al. Social LSTM: Human trajectory prediction in crowded spaces. In: Proc. of the IEEE Conf. on Computer Vision and Pattern Recognition. 2016. 961-971. [doi: 10.1109/CVPR.2016.110]]]>
doi: 10.1109/CVPR.2018.00240]]]>
http://arxiv.org/abs/1709.05584 ]]>
Cai H, Zheng VW, Chang KCC. A comprehensive survey of graph embedding: Problems, techniques, and applications. IEEE Trans. on Knowledge and Data Engineering, 2018, 30(9): 1616-1637. [doi: 10.1109/TKDE.2018.2807452]
et
doi: 10.1109/ACCESS.2018.2881457]]]>
doi: 10.1145/3132847.3133006]]]>
doi: 10.1145/2983323.2983711]]]>
Lee JG, Han J, Li X, Cheng H. Mining discriminative patterns for classifying trajectories on road networks. IEEE Trans. on Knowledge and Data Engineering, 2011, 23(5): 712-726. [doi: 10.1109/TKDE.2010.153]
Liu Q, Wu S, Wang L, Tan T. Predicting the next location: A recurrent model with spatial and temporal contexts. In: Proc. of the 30th AAAI Conf. on Artificial Intelligence (AAAI 2016). 2016. 194-200.
Sillito RR, Fisher RB. Parametric trajectory representations for behaviour classification. Multimedia Systems, 2006, 12: 227-238. [doi: 10.5244/C.23.101]
Li C, Han Z, Ye Q,
et
et
doi: 10.1109/BigComp.2018.00021]]]>
et
Yang C, Gidófalvi G. Detecting regional dominant movement patterns in trajectory data with a convolutional neural network. Int'l Journal of Geographical Information Science, 2020, 34(5): 996-1021. [doi: 10.1080/13658816.2019.1700510]
Feng J, Li Y, Zhang C,
et
doi: 10.1007/978-3-030-01418-6_7]]]>
Bengio Y, Courville A, Vincent P. Representation learning: A review and new perspectives. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2013, 35(8): 1798-1828. [doi: 10.1109/TPAMI.2013.50]
Mikolov T, Sutskever I, Chen K,
doi: 10.1109/ICDM.2014.41]]]>
et
et
Mikolov T, Chen K, Corrado G, Dean J. Efficient estimation of word representations in vector space. arXiv preprint arXiv: 1301. 3781, 2013.
Turian J, Ratinov L, Bengio Y. Word representations: A simple and general method for semi-supervised learning. In: Proc. of the 48th Annual Meeting of the Association for Computational Linguistics. 2010. 384-394.
doi: 10.1109/69.917563]]]>
http://arxiv.org/abs/1409.0473. ]]>
Agrawal R, Imieliński T, Swami A. Mining association rules between sets of items in large databases. In: Proc. of the 1993 ACM SIGMOD Int'l Conf. on Management of Data. 1993. 207-216.
doi: 10.1145/347090.347153]]]>
Chen L, Ng R. On the marriage of Lp-norms and edit distance. In: Proc. of the 30th Int'l Conf. on Very Large Data Bases, Vol. 30. 2004. 792-803.
Chen L, Özsu MT, Oria V. Robust and fast similarity search for moving object trajectories. In: Proc. of the 2005 ACM SIGMOD Int'l Conf. on Management of data. 2005. 491-502.
doi: 10.1109/ICDE.2002.994784]]]>
doi: 10.1145/1807167.1807197]]]>
Hung CC, Peng WC, Lee WC. Clustering and aggregating clues of trajectories for mining trajectory patterns and routes. The VLDB Journal, 2015, 24(2): 169-192. [doi: 10.1007/s00778-011-0262-6]
Hochreiter S, Schmidhuber J. Long short-term memory. Neural Computation, 1997, 9(8): 1735-1780. [doi: 10.1162/neco.1997.9.8. 1735]
Chung J, Gulcehre C, Cho K, Bengio Y. Empirical evaluation of gated recurrent neural networks on sequence modeling. arXiv preprint arXiv: 1412.3555, 2014.
doi: 10.5244/c.12.83]]]>
doi: 10.1145/1066116.1189037]]]>
doi: 10.1109/MDM.2008.29]]]>
Gruteser M, Liu X. Protecting privacy, in continuous location-tracking applications. IEEE Security & Privacy, 2004, 2(2): 28-34.
Huo Z, Meng XF. A survey of trajectory privacy-preserving techniques. Chinese Journal of Computers, 2011, 34(10): 1820-1830 (in Chinese with English abstract).
霍峥, 孟小峰. 轨迹隐私保护技术研究. 计算机学报, 2011, 34(10): 1820-1830.
doi: 10.1109/dsc50466.2020.00011]]]>
Li X, Cong G, Cheng Y. Spatial transition learning on road networks with deep probabilistic models. In: Proc. of the 2020 IEEE 36th Int'l Conf. on Data Engineering (ICDE). 2020. 349-360.
Liu X, Chen HZ, Andris C. trajGANs: Using generative adversarial networks for geo-privacy protection of trajectory data (Vision paper). In: Proc. of the Location Privacy and Security Workshop. 2018. 1-7.
Rao J, Gao S, Kang Y, Huang Q. LSTM-Trajgan: A deep learning approach to trajectory privacy protection. arXiv preprint arXiv: 2006.10521, 2020.
http://arxiv.org/abs/1506.03099 ]]>
Yao D, Zhang C, Huang JH, Chen YX, Bi JP. Semantic understanding of spatio-temporal data: Technology & application. Ruan Jian Xue Bao/Journal of Software, 2018, 29(7): 2018-2045 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/ 5576.htm[doi: 10.13328/j.cnki.jos.005576]
姚迪, 张超, 黄建辉, 陈越新, 毕经平. 时空数据语义理解: 技术与应用. 软件学报, 2018, 29(7): 2018-2045. http://www.jos.org.cn/1000-9825/5576.htm[doi: 10.13328/j.cnki.jos.005576]
Yin H, Zhou X, Cui B, Wang H, Zheng K, Nguyen QVH. Adapting to user interest drift for poi recommendation. IEEE Trans. on Knowledge and Data Engineering, 2016, 28(10): 2566-2581.
Yin H, Cui B, Zhou X, Wang W, Huang Z, Sadiq S. Joint modeling of user check-in behaviors for real-time point-of-interest recommendation. ACM Trans. on Information Systems (TOIS), 2016, 35(2): 1-44.
Liu X, Liu Y, Li X. Exploring the context of locations for personalized location recommendations. In: Proc. of the IJCAI. 2016. 1188-1194.
Ying JJC, Lee WC, Weng TC, Tseng VS. Semantic trajectory mining for location prediction. In: Proc. of the 19th ACM Sigspatial Int'l Conf. on Advances in Geographic Information Systems. 2011. 34-43.
De Brébisson A, Simon É, Auvolat A, Vincent P, Bengio Y. Artificial neural networks applied to taxi destination prediction. arXiv preprint arXiv: 1508.00021, 2015.
Clements M, Serdyukov P, De Vries AP, Reinders MJ. Using flickr geotags to predict user travel behaviour. In: Proc. of the 33rd Int'l ACM Sigir Conf. on Research and Development in Information Retrieval. 2010. 851-852.
doi: https://doi.org/10.1016/j.ins.2020.05.107]]]>