软件学报  2021, Vol. 32 Issue (5): 1461-1479   PDF    
轨迹表示学习技术研究进展
曹翰林1 , 唐海娜1 , 王飞2 , 徐勇军2     
1. 中国科学院大学 人工智能学院, 北京 100049;
2. 中国科学院 计算技术研究所, 北京 100190
摘要: 基于地理位置信息的应用和服务的迅速发展,对轨迹数据挖掘提出了新的需求和挑战.原始轨迹数据通常是由坐标-时间戳元组构成的有序序列,而现有的大多数数据分析算法均要求输入数据位于向量空间中.因此,为了将轨迹数据从变长的坐标-时间戳序列转化成定长的向量表示且保持原有的特征,对轨迹数据进行有效的表示是十分重要且必要的一步.传统的轨迹表示方法大多是基于人工设计特征,通常仅将轨迹表示作为数据预处理的一部分.随着深度学习的兴起,这种从大规模数据中学习的能力使得基于深度学习的轨迹表示方法相比于传统方法取得了巨大的效果提升,并赋予了轨迹表示更多的可能性.对轨迹表示领域中的研究进展进行了全面的总结,将轨迹表示按照研究对象的不同尺度,归纳为对轨迹单元的表示和对整条轨迹的表示两大类别,并在每种类别下对不同原理的方法进行了对比分析.其中重点分析了基于轨迹点的表示方法,也对近年来广泛使用的基于神经网络的轨迹表示的研究成果做了系统的归类.此外,介绍了基于轨迹表示的关键应用,最后对轨迹表示领域的未来研究方向进行了展望.
关键词: 轨迹数据挖掘    轨迹表示    时空数据挖掘    
Survey on Trajectory Representation Learning Techniques
CAO Han-Lin1 , TANG Hai-Na1 , WANG Fei2 , XU Yong-Jun2     
1. School of Artificial Intelligence, University of Chinese Academy of Science, Beijing 100049, China;
2. Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China
Abstract: 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.
Key words: trajectory data mining    trajectory representation    spatial-temporal data mining    

随着移动终端的兴起和定位技术的日趋成熟, 基于位置信息的应用在人们的生产生活当中得到了前所未有的广泛应用.与此同时, 遥感卫星、监控影像系统以及具有GPS(global positioning system)和AIS(automatic identification system)功能的设备无时无刻不在收集海量的轨迹数据, 这其中既包含行人出行、动物迁徙、台风移动等自由轨迹, 也涵盖了汽车、舰船、飞机等交通工具的行驶轨迹.在如此庞大的轨迹数据量背后, 同样有着广泛的应用场景, 从景点推荐(如预测游客下一到达位置)到智慧交通(如交通流量预测)、从公共安全(如预测台风轨迹)到国防安全(如识别领海内异常舰船轨迹), 不一而足.近年来, 轨迹数据相关的研究工作的数量呈逐年递增的趋势, 如图 1所示.轨迹数据挖掘已然成为了数据挖掘领域的研究热点之一.利用从轨迹数据中挖掘出的信息和知识, 能够帮助我们进一步理解人类活动, 进而改善人与社会、人与自然的关系.

Fig. 1 Number of papers relating trajectory data in the field of computer science during the last ten years 图 1 近10年来, 计算机科学领域内轨迹数据相关的文章数量

传统的轨迹数据挖掘技术主要集中在轨迹相似性计算[1, 2]、轨迹聚类[3, 4]、交通模式分类[5, 6]、轨迹异常检测[7-9]等方面.近几年来, 随着深度学习在各个领域大放异彩, 使用深度神经网络来研究轨迹模式逐渐成为了主流, 极大地推动了诸如轨迹预测[10-12]、轨迹推荐[13, 14]、行人-轨迹匹配[15, 16]等技术的发展.

在众多基于轨迹数据的技术中, 对轨迹数据进行有效的表示, 始终是贯穿其中的一项重要任务.原始的轨迹数据在形式上通常表现为由经纬度坐标-时间戳三元组构成的有序序列, 然而常见的数据分析算法(例如支持向量机)均要求输入数据位于向量空间中, 因此, 原始轨迹数据往往不能直接作为算法的输入数据.为了解决这一问题, 对轨迹数据进行表示成为了一项不可或缺的工作, 其目的是将原始轨迹数据转换成为适合处理的数据形式后, 再输入到算法或模型中, 例如向量、图像、图等形式.从数据降维的角度来看, 原始轨迹数据可以被看作是一种高维数据, 三元组中不仅每一个元素均代表一个维度, 而且还混合了时间(时间戳)和空间(坐标)这两种不同维度的信息.显然, 这样的数据不利于算法进行处理, 因此需要使用轨迹表示来对高维轨迹数据进行降维.这样不仅能够从形式上对原始轨迹数据进行规范和简化, 还可以从冗余的原始信息中提取出有价值的部分, 使整个模型更加高效.除此之外, 好的轨迹表示不仅能够保留轨迹数据原有的特征, 还能在一定程度上弥补原始轨迹数据的缺陷.例如, 传感器在信号采集、传输的过程中往往会不可避免地受噪声影响, 好的轨迹表示能够在一定程度上缓解轨迹噪声所带来的误差.由于涉及到模型的输入, 因此轨迹表示质量的好坏会直接影响到轨迹数据挖掘的最终效果.随着物联网等相关技术的发展, 我们相信: 在未来, 基于轨迹数据的应用必将成为与人们日常生活关系最为密切的应用之一, 同时也一定会涌现出更多形式多样、含义丰富的轨迹数据.因此, 研究对轨迹数据的有效表示有着十分重要的现实意义.

轨迹表示一直以来都是轨迹数据挖掘的重要研究内容之一.在长期的研究和实践过程中, 研究人员相继总结了有关轨迹数据处理的技术, 其中不乏一些针对轨迹表示方法的整理工作.郑宇等人[17]对轨迹数据挖掘领域的问题和方法做了全面且系统的梳理, 但文中关于轨迹表示的内容只总结了3种轨迹表示的形式, 这对于轨迹表示来说仅占其中的一小部分.文献[18]主要总结了深度学习在时空数据表示领域的工作, 其中虽然有少部分内容涉及到轨迹表示, 但仅局限于基于深度学习的方法, 且篇幅较短, 未能展现该问题的全貌.因此就目前来说, 轨迹表示领域缺少一篇较为全面和详细的综述文章.本文通过广泛整理轨迹表示相关的文献, 针对轨迹表示的研究成果和关键技术进行了系统的归纳和总结, 并对轨迹表示方法按照研究对象的不同尺度和方法的不同原理进行了详细分类, 同时还给出了不同类别的方法所适用的应用场景.此外, 本文还对轨迹表示领域存在的一些开放性问题和未来的研究方向进行了探讨和展望.

本文第1节对轨迹表示的定义、轨迹表示的难点以及轨迹表示方法的分类作一概述.第2节和第3节分别介绍对轨迹单元和对整条轨迹的表示方法.第4节讨论轨迹表示领域的未来研究方向.最后, 在第5节对全文进行总结.

1 轨迹表示概述 1.1 轨迹与轨迹表示的定义

定义1. 轨迹是指物体在地理空间中移动的真实路径, 是从时间(时刻)到空间(二维坐标)的连续函数.

定义2. 轨迹的离散采样是最基本的轨迹数据类型, 具体形式为离散点序列S={(l0, t0), …, (lk, tk)}.其中, li表示移动主体所在的地理位置(如经度和纬度), ti则表示移动主体通过该位置的时刻.

由于GPS等定位技术通常不会连续地记录位置信息, 因此在实际中, 我们收集到的轨迹数据通常都是在真实轨迹上采样后得到的.为了便于表述, 如无特别说明, 下文中涉及到轨迹之处均是指轨迹的离散采样.

定义3(轨迹表示), 给定一条轨迹离散采样数据S, 轨迹表示的目的是找到一个映射f将轨迹数据转化为d维空间中的向量vRd, 同时要求该向量能够尽可能地保留原始轨迹数据的时空属性.

1.2 轨迹表示的难点

对轨迹进行表示面临着诸多挑战[17]: 首先, 不同的轨迹有着不同的属性, 例如长度、形状、采样率、轨迹点数量等等, 这对表示方法的稳健性提出了挑战; 其次, 轨迹数据属于时空数据, 采用传统方法难以捕获其时空相关性.尽管人们在轨迹数据挖掘领域进行了广泛的研究, 但专门针对轨迹表示的工作依然有限.对于如何将不同类型的轨迹数据转化为相应的高效表示形式、使其有利于进行模式识别, 一直以来都还没有一套成体系的解决方案.

传统的轨迹表示方法多是基于人工设计特征, 例如从原始轨迹数据中提取出速度、加速度、角度等信息, 再将这些信息组合到一起来表示轨迹.但这类方法受限于特征提取能力, 通常仅将轨迹表示作为数据预处理的一部分.随着深度学习逐渐流行起来, 利用卷积神经网络(CNN)和循环神经网络(RNN)来学习轨迹表示的方法取得了长足的进展, 其核心思想是, 通过数据驱动的方式来学习从原始轨迹到表示向量的映射过程.这类方法虽然在特征提取能力方面有较大的提升, 但也易受端到端训练框架的限制.这部分会在第3.2节中详细说明.

1.3 轨迹表示方法的分类

近年来, 有越来越多的工作在众多前人研究成果的基础上, 对轨迹数据混用了多种不同类型的表示方法, 导致轨迹表示环节更加难以直观地体现出来.这对轨迹表示方法的整理工作提出了一定的挑战.

在已有的涉及到轨迹表示的文献中, 通常是按照轨迹表示所使用的模型对轨迹表示方法进行分类, 例如CNN、RNN、LSTM、Seq2Seq等.而我们认为: 轨迹数据本身就有着非常丰富的表现形式, 轨迹数据应当是轨迹表示问题的重点.因此, 本文避开了传统的按照模型类别对轨迹表示方法分类的思路, 回归到轨迹数据本身, 将轨迹数据按照不同的尺度划分为轨迹单元和整条轨迹, 分别归纳了对轨迹序列单元的表示方法和对整条轨迹序列的表示方法.对轨迹序列单元的表示方法主要是以轨迹序列单元为基础, 通过学习单元的表示, 进而得到轨迹序列的表示.其中, 轨迹序列单元可以细分为轨迹点和轨迹段; 对整条轨迹序列的表示则着眼于完整的轨迹序列, 直接学习整条轨迹的表示.接下来将对这两类方法分别进行介绍.轨迹表示方法的整体分类见表 1.

Table 1 Classification of trajectory representation methods 表 1 轨迹表示方法的分类

2 对轨迹序列单元的表示

如上所述, 轨迹数据属于时空数据的一种, 天然地表现为序列形式.因此, 有很多轨迹表示方法都选择在轨迹序列单元的基础上学习轨迹表示.在本节中, 我们总结了基于轨迹点和轨迹段这两种尺度下的轨迹序列单元表示方法.

2.1 方法概述: 序列-序列框架

通常, 我们拿到的轨迹数据是如定义2所示的带有时间信息的二维坐标序列S={(l0, t0), …, (lk, tk)}, 但直接使用该数据存在着一些缺陷.

(1) 不同的轨迹离散序列通常包含不同数量的轨迹点, 其数目可能差异巨大, 即有的轨迹采样十分致密, 而有的轨迹采样则十分稀疏.这对轨迹表示方法的稳健性提出了很高的要求; 此外, 即使是在同一条轨迹内部, 不同区段的采样密度也可能会有所差异.

(2) 原始轨迹数据所包含的信息是松耦合的(loose coupling), 例如时间信息(即时间戳ti)和位置信息(即二维坐标li)都是独立表示的, 各个轨迹点的取值在数据空间中的分布无规律可循.尽管轨迹数据的序列形式可以在一定程度上体现出轨迹点之间的次序关系, 但这种简单的次序关系远不足以表现出轨迹点之间的时空关系.

正是因为直接使用原始轨迹数据存在着诸多不便, 因此涌现出了各种方法来对轨迹序列加以处理.在讨论具体的方法之前, 我们首先提出一个序列-序列框架, 该框架总结了此类方法的常用模式, 将不同种类的方法纳入到相同的符号和概念基础上.

在序列-序列框架中, 表示方法的目标是基于原始的轨迹序列得到新的序列:

$ { EMB: } S \rightarrow Z. $

其中, Z={z1, z2, …, zk'}是经过表示后得到的新的序列, zi是新序列中的数据点, EMB是表示过程.不同表示方法的区别, 主要体现在不同的表示过程上.

2.2 基于轨迹点的表示

我们首先讨论轨迹序列中基于轨迹点的表示.由于数据采样的特性, 轨迹点是原始轨迹序列数据中最基本的单元, 在形式上由坐标点和时间戳组成.

2.2.1 基于划分

在处理真实轨迹的过程中, 我们经常会面临轨迹长度过长和轨迹分布稀疏的问题, 这两者都会导致数据空间的激增.具体来说, 前者会因为轨迹点过多, 导致轨迹数据的处理时间增加; 后者会造成轨迹点的坐标值值域过大, 导致坐标取值稀疏, 进而影响表示效果, 如图 2所示(其中, 不同的轨迹位于坐标空间中的各处, 坐标的值域极易受其影响).

Fig. 2 An illustration of sparse distribution of trajectory sequences 图 2 轨迹序列分布稀疏示意图

基于划分的方法的主要思想就是将一些相互邻近的轨迹点看作一个集合, 转而用该集合的标识来代表集合中的轨迹点, 进而由多个集合的标识所构成的序列来表示轨迹.这既是一种近似, 也是一种抽象.在实际工作中, 通常使用兴趣点(point of interest)和网格(grid)来作为集合的基本单元.

(1) 划分兴趣点

借助兴趣点信息来划分轨迹, 是解决单条轨迹过长问题的一种有效方法.其基本假设是: 轨迹的产生是基于一系列兴趣点, 从而可以将轨迹点序列转化为兴趣点序列.例如, 一个人日常上班的轨迹可以用家、车站、公司、餐馆等兴趣点来表示.对应到序列-序列框架中, 新序列的数据点就是轨迹中的兴趣点, 它是部分原始轨迹点的集合:

$ S \rightarrow Z, z_{i}=\left\{\left(l_{h+1}, t_{h+1}\right), \ldots, \left(l_{h+w}, t_{h+w}\right)\right\}, $

其中, zi表示兴趣点, w是隶属于该兴趣点的轨迹点的数量.

具体实现时, 通常是以兴趣点为圆心、以一定的长度为半径在地图中划出一个圆形区域, 凡是落在该区域内的轨迹点都由该兴趣点来表示.轨迹则按照从一个兴趣点到下一个兴趣点的顺序依次表示出来.

划分兴趣点不仅可以大大简化轨迹数据的复杂程度, 而且还可以在一定程度上得到轨迹的语义信息, 因为每个兴趣点通常都具有相应的语义, 例如“公司”的语义信息和工作高度相关.这类方法常常被用于轨迹分类问题.不过, 基于兴趣点的划分方法的局限之处在于对额外地理位置信息的依赖.例如, 在城市中确定兴趣点需要依赖建筑、街区的功能信息.而在一些大范围场景中, 例如候鸟迁徙、台风移动等, 往往会由于缺少额外信息而难以提取出有效的兴趣点; 即使存在一些兴趣点, 也会由于轨迹空间过于广阔, 使得轨迹的兴趣点序列显得十分稀疏, 难以有实际用处.

(2) 划分网格

近年来, 轨迹数据挖掘领域中许多有代表性的工作都采用了划分网格这一方法对轨迹进行处理.该方法将地图划分成等间距的网格, 每个小网格都有各自的标识.落入同一网格所表示范围中的轨迹点都由该网格的标识来表示.于是, 原始的轨迹点序列被转化成为一系列网格构成的序列:

$ S \rightarrow Z, z_{i}=g_{i}, $

其中, gi是新序列中第i个网格的标识.

关于网格表示, 最简单的做法是使用独热向量[47], 但独热向量无法体现出相邻网格之间的空间关系.因此, 近年来有越来越多的工作都借鉴了自然语言处理领域中的word2vec方法[48]来对网格进行表示学习, 并取得了非常好的效果.这部分内容将会在第2.2.3节中详细介绍.

划分网格的方法主要解决了原始轨迹数据分布稀疏的问题, 此外, 还可以缓解轨迹采样率不一致和采样率低的问题[49-51].这是因为划分网格相当于将轨迹数据空间中的最小单元从无限小的实值点放大为自定义大小的网格, 于是数据空间得以压缩, 数据分布稀疏的问题得以缓解.有趣的是: 如果从兴趣点的角度考虑, 我们不妨将每一个网格看作是一个自定义的兴趣点, 从而划分网格的方法也可以被看作是划分兴趣点的方法在自由空间中的推广.相比于基于兴趣点的表示方法, 划分网格不依赖额外的地理信息, 因此, 该类方法更适合应用于缺少外部信息的自由空间场景.不过, 基于划分网格的轨迹表示方法需要先验地确定网格的大小, 且轨迹表示的效果会受到网格大小的直接影响.例如, 网格尺寸过大会导致划分过于粗糙从而缺少相应的轨迹模式细节, 而网格尺寸过小又会降低缓解稀疏性的能力.因此在实际应用中, 往往需要选择合适的网格大小.文献[19]分别使用边长为200m, 400m, 800m, 1600m和3200m的网格来划分区域, 通过不同层级的分辨率来捕获不同粒度下的轨迹特征; 文献[20]则是采用自适应的参数调整方法.在将轨迹分段后, 通过保证每个网格内轨迹段的平均数量Numavg来设置网格的尺寸, 并通过大量的实验, 经验地总结出: 当参数Numavg=2时, 能够获得最好的轨迹聚类效果.

2.2.2 基于人工设计特征

早期的轨迹表示方法大多使用人工设计的特征来表示轨迹, 因此这类方法也常被称为轨迹特征提取.之所以可以进行特征提取, 是因为原始的轨迹点序列中包含了丰富的空间和时间信息.这类方法的核心思想是: 利用已有的时空信息来挖掘新的特征, 将原始的轨迹点序列转化为特征序列.

$ S \rightarrow Z, z_{l}=f_{i}, $

其中, fi是根据若干个轨迹点数据提取到的特征.例如, 通过下列公式可以计算出移动主体的位移Li[22]、速度Vi[13]和加速度ai[6].

$\begin{gathered} {L_i} = Dist({P_i}, {P_{i + 1}}), \\ {\rm{\Delta }}{T_i} = {P_{i + 1}} \cdot T - {P_i} \cdot T, \\ {V_i} = {L_i}/{\rm{\Delta }}{T_i}, \\ {a_i} = ({V_{i + 1}} - {V_i})/{\rm{\Delta }}{T_i}. \\ \end{gathered} $

郑宇等人在文献[23]中先对轨迹进行分段, 然后在各个轨迹段内计算位移、最大速度、最大加速度、平均速度等物理量作为该段轨迹的特征, 并用特征的序列取代原有的轨迹点序列作为模型的输入数据, 进而对轨迹的交通模式进行分类; 他们还在文献[24]中设计了更为复杂的特征, 包括速度变化率(VCR)、停止率(SR)以及转向率(HCR), 从而实现了更准确的分类效果.除了设计不同的物理量, 文献[3]进一步将这些物理量的统计量作为特征, 如均值、最值、分位数, 使得轨迹的特征更加精细化.

然而, 基于人工设计特征的轨迹表示方法有如下局限: 1) 特征的设计高度依赖专家知识, 而且针对不同的轨迹应用场景, 往往需要重新选择和优化特征, 这增加了此类方法的应用难度; 2) 人能够从轨迹数据中抽象出来的特征种类是有限的, 随着特征工程的深入, 新特征的获取会越来越难, 导致基于人工设计特征的方法所带来的增益趋于平缓.

2.2.3 基于词袋

近年来, 自然语言处理领域的研究取得了长足的进展[48, 52], 其中涌现出的一些新方法也被轨迹表示领域的工作所借鉴.之所以可以借鉴, 是因为轨迹序列数据和文本数据有诸多共通之处: 一条轨迹类似于文本数据中的一个句子, 轨迹序列单元则可以被视为构成句子的词语.此外, 轨迹数据中轨迹点还服从幂律分布[15].

基于词袋的表示方法本质上是将轨迹数据看作由一堆词语构成的词袋, 其中, 词语可以是轨迹点、轨迹段或是兴趣点等.然后再利用词嵌入(word embedding)的方法来学习“词语”的表示, 即轨迹序列单元的表示, 进而可以得到整条轨迹的表示:

$ S \rightarrow Z, z_{i}=w_{i}, $

其中, wi为词向量.

这类方法的流程主要分为两步: 定义词语和词嵌入.

定义词语最简单的做法是直接将轨迹点看作词语[15, 16], 但其效果往往受制于数据量的大小, 例如, 当轨迹数据太多时, 通常会导致词典的体量过大.因此, 直接将轨迹点看作词语的做法仅限于小范围场景, 例如监控视频中的行人轨迹.更常见的做法是对轨迹数据进行划分, 将划分后的单元作为词语.文献[25]将出租车的行驶记录类比为句子, 并将行驶记录中的城市行政区域和出发到达事件类比为单词.文献[1, 7, 21]使用了划分网格的方法, 将每一个网格视为一个独立的单词; 除了空间坐标之外, 时间信息同样是连续的, 故文献[21]将一周的时间划分为48个时间区间, 每个时间段分别对应一个单词.

词嵌入是词表示(word representation)[53]的子集, 在此处主要是指词语的分布式表示[54].其核心思想是, 将高维空间中的单词映射到低维空间中.其主要针对的问题是: 用独热向量表示词语会造成词向量的维数等于词典的大小, 这样的话不仅计算量大, 而且词向量表示稀疏、缺少语义信息.

近年来, 常用于轨迹表示的词嵌入方法主要有两类.

(1) 第1类方法借鉴了word2vec[48]的思路.

文献[15]参考了CBOW(continuous bag-of-words model)模型, 对位置点li的嵌入通过最大化以其上下文位置点为条件的条件概率$\sum\nolimits_{i = 1}^m {\log p({l_i}|{l_{i - c}}:{l_{i + c}}){\kern 1pt} } $来完成.

$ \operatorname{maximizep}\left(\boldsymbol{v}\left(l_{i}\right) \mid C\left(l_{i}, l\right)\right)=\operatorname{maximize} \prod\limits_{l^{\prime} \in C\left(l_{i}, l\right)} p\left(\boldsymbol{v}\left(l_{i}\right) \mid \boldsymbol{v}\left(l^{\prime}\right)\right)=\operatorname{maximize} \prod\limits_{l^{\prime} \in C\left(l_{i}, l\right)} \frac{\exp \left\{\boldsymbol{v}\left(l_{i}\right) \boldsymbol{v}\left(l^{\prime}\right)\right\}}{\sum\limits_{l^{\prime} \in C} \exp \left\{\boldsymbol{v}\left(l^{\prime \prime}\right) \boldsymbol{v}\left(l^{\prime}\right)\right\}}, $

其中, C表示词袋, C(li, l)是轨迹单元li在轨迹序列中的上下文, 即li-c: li+c, c为滑窗的长度; v(l)是轨迹单元l的向量表示.文献[1, 2]则是借鉴了Skip-gram模型, 具体来说: 首先将空间划分成等大小的网格, 每一个网格代表一个单词; 然后对于给定的单词lC, 从它的邻居中随机采样得到上下文C(l); 最后, 通过最大化其上下文单词出现的概率来学习单词l的向量表示.

${\rm{maximize}}\sum\limits_{l \in C} {\log p(C(l)|v(l))} .$

使用word2vec学习轨迹单元表示的优势在于: 能够利用无标签的轨迹单元上下文将轨迹单元转化成有标签的表示向量; 同时, 该表示向量能够捕获轨迹单元在空间中的邻近关系, 即, 在空间中邻近的轨迹单元有相似的向量表示.不过, 此类方法的局限在于无法获得词袋之外的轨迹单元的表示, 即, 未在训练集中出现过的轨迹单元没有相应的轨迹表示向量.因此, 此类方法通常与划分网格的方法相结合来缓解数据集的稀疏问题, 从而使得训练集能够覆盖到尽可能多的轨迹数据.

(2) 第2类方法是利用前馈神经网络对轨迹单元进行嵌入.

上述通过word2vec学习轨迹单元表示的过程在某种意义上属于数据预处理的范畴, 因为其学习过程独立于模型的训练过程, 即先通过word2vec对轨迹进行表示, 再将表示后的数据输入到模型中进行训练.其不足之处是, 轨迹的表示一经确定就不再改变.为了解决这一问题, 近两年来, 不少工作均采用前馈神经网络对轨迹序列单元进行嵌入表示.这样做的好处在于: 对轨迹单元进行嵌入属于模型的一部分, 嵌入的结果可以随着模型训练一起优化.个中原因一方面是得益于算力的提升; 另一方面是随着轨迹应用场景的扩展, 出现了诸如安防监控这样的小型场景下的轨迹分析需求, 使得在有限的轨迹数据空间中对轨迹单元嵌入变得可行.这一类方法的代表性的工作是文献[26-28], 它们针对的是从监控视频中提取出的行人轨迹, 仅通过一个嵌入层完成对二维坐标点(xi, yi)的嵌入:

$ e_{i}=\phi\left(x_{i}, y_{i} ; W_{e}\right), $

其中, We是一个2×N的权重矩阵(N > 2).经过嵌入后, 轨迹点的表示由原先的二维坐标向量(xi, yi)升维成一个新的N维向量ei, 并且嵌入层的参数会随着模型一起优化, 这样就可以在数据驱动的方式下学到最有利于优化目标的轨迹点表示.除此之外, 利用前馈神经网络学习轨迹单元表示可以不受词袋容量的限制.这是因为轨迹单元的表示过程是从空间坐标(二维向量空间)映射到N维向量空间, 而非从词语映射到向量空间, 因此可以有效地解决基于word2vec方法的不足.但相应地, 使用前馈神经网络的方法无法保证相邻的轨迹单元空间拥有相似的表示向量.

2.2.4 基于图表示

我们上述的所有表示方法都是基于轨迹序列这一基本数据形式来演绎的, 然而轨迹数据除了序列形式之外, 还可以转化成其他的数据形式, 这极大地延展了轨迹表示领域的深度和广度.基于图表示的方法就是其中最有代表性的一种.

此类方法的重点在于如何构建图, 主要任务是对节点和边进行定义.一旦顺利将轨迹数据表示成图, 那么剩下的工作就是利用图表示方法将节点或边嵌入到低维空间中, 使得图的结构信息和属性能够在最大程度上保留.图表示的方法众多, 且不同类别的方法有各自的优缺点[29, 30].这里, 我们参考了文献[17]对此类方法的分类, 针对轨迹表示, 将常见的构建图的方法按照使用场景分为两类: 交通路网场景和自由空间场景.

(1) 交通路网场景

交通路网本身就可以看作为一个有向图G(V, E), 其中, V代表顶点(即十字路口)的集合, E代表边(即路段)的集合.每条边rE都对应于一条将一个顶点vV和另一个顶点v'(≠v)∈V连接起来的路段, 其中, r.s=vr.e=v'分别表示路段的起始路口和终止路口.文献[10]在通过这种构建方法得到的图上, 利用word2vec来学习边(即路段)的表示.

(2) 自由空间场景

在自由空间中, 由于缺少像交通路网那样既有的物理条件, 往往需要利用其他信息来构建图, 如时间信息、语义信息等, 这也使得此类方法在内容上更加丰富.常见的方法是将城市区域或兴趣点作为图的节点.之所以不直接将轨迹坐标点作为图的节点, 是因为除了要考虑原始数据稀疏的问题外, 往往还会面临数据浮动(data variation)的问题[31], 即产生于同一块区域或同一段时间内的轨迹点本可以被认为是属于同一类数据, 但却由于具体坐标值和时刻有些许差异而被分别对待.

文献[32]以兴趣点作为图的节点, 在建立连边时, 基于的假设是: 1) 同类型的位置点有相似的语义; 2) 距离上相近的位置点, 要比距离较远的位置点更相关.然后, 按照一定的距离阈值将附近的节点和同类型的节点进行连接, 利用node2vec学习兴趣点的向量表示.为了解决静态图没有考虑不同时间对节点功能的影响问题, 文献[33]采用了时序图的形式, 即同一节点按照不同时间段被拆分成多个节点.具体地, 以城市中的行政区域为节点, 基于出租车的行驶数据构建了交通流时序图.处于相同时间段的节点位于同一层, 层的数量等于时间段的数量.例如, 24层意味着一天被划分成24个时间段.相邻层之间的节点根据交通流数据进行连接, 然后在图中进行随机游走, 利用Skip-gram学习不同时间段的节点(即区域)表示.文献[34]使用基于位置的社交网络(LSBNs)数据构建了4个相关联的二分图(bipartite graph): POI-POI图、POI-Region图、POI-Time图、POI-Word图, 并将这4种不同的信息嵌入到同一个低维空间中来学习各自的向量表示.

2.3 基于轨迹段的表示

现在我们来看基于轨迹段的表示方法, 这类方法的主要思想是, 将轨迹段作为轨迹序列的基本单元进行表示.所谓的轨迹段是指由若干个连续的轨迹点构成的集合, 在形式上表现为轨迹序列的子序列.之所以使用轨迹段作为序列单元, 一方面是因为相比于整条轨迹, 分段后不仅能够降低计算复杂度, 而且能够帮助我们挖掘出更丰富的信息, 例如不同区间段的轨迹模式; 另一方面是因为在一些场景中轨迹段更适合用来表示轨迹, 例如城市交通路网天然地由众多规整的路段组成, 位于同一路段中的所有轨迹点都不妨用该路段的标识来表示.

除了文献[17]中总结的轨迹分段方法以外, 另一类很常见的轨迹分段方法就是上述的依靠城市路网背景, 以路段作为天然的轨迹段.

所谓的路段是指连接两个路口的道路, 而路网可以看作是由路段和路口组成, 如图 3所示.行驶在某一条路段上的车辆, 除非行驶至路口, 否则无法脱离此路段.利用路网的这一特点, 我们可以在不损失数据质量的前提下, 用路段来表示整个轨迹: 原始的轨迹点序列S=(l0, l2, …, lk)可以表示成路段的序列:

$T{r_\mathcal{E}} = ({e_1}, {e_2}, ..., {e_R}){\rm{ }}({e_i} \in \mathcal{E}, 1 \leqslant i \leqslant R, R \leqslant \min (k, |\varepsilon |)), $
Fig. 3 An illustration of road network[35] 图 3 路网结构示意图[35]

其中, $ \mathcal{E}$是所有路段的集合.

从某种意义上讲, 轨迹段可以看作是一个更大的“轨迹点”.因此, 基于轨迹点的表示方法也大都适用于轨迹段的表示.文献[3]利用滑窗法在原始轨迹点序列上滑动, 落在同一个滑窗内的轨迹点组成一个轨迹段, 再分别计算同一轨迹段内平均速度、速度差、角度差的6个统计量, 用3×6=18个统计量作为该轨迹段的特征.文献[35]是在城市路网的背景下, 以路段作为最基本的数据单元, 使用频繁项挖掘的方法找出那些有利于轨迹分类的频繁轨迹段序列.文献[10]同样借鉴了word2vec的思想, 将轨迹段序列和轨迹段分别看作句子和单词, 进而学习轨迹段的向量表示.

此外, 同样是轨迹序列单元, 轨迹段和轨迹点的不同之处在于: 轨迹段本身就是包含了若干个轨迹点的子序列, 因而可以有更丰富的表示方法.最简单的做法是基于组合的方式, 即先将轨迹点表示成向量, 然后将轨迹段内所包含的轨迹点的表示向量组合到一起作为轨迹段的表示.但更常见的做法是: 利用轨迹段本身是序列的特点, 进而使用RNN来学习轨迹段的表示[15, 16, 36].这样做一方面利用了RNN处理序列数据的天然优势, 从而得到更加抽象的向量表示; 另一方面解决了不同轨迹段包含的轨迹点数量不同的问题: 经过RNN处理后, 长短不一的轨迹段都被表示成为定长的向量, 从而便于后续的处理.

2.4 有关轨迹单元表示的应用

通过对轨迹单元如轨迹点和轨迹段进行表示, 原始的坐标-时间戳序列被转化成为新形式表示下的序列.相比于原始数据, 新表示下的轨迹序列不仅将时空信息更紧密地嵌入在一起, 而且在形式上更适合机器学习模型进行处理.一系列基于序列数据的轨迹应用可以就此开展, 例如轨迹序列预测、轨迹序列相似性计算等.

2.4.1 轨迹预测

时空序列数据包含了丰富的上下文信息, 轨迹预测的目标就是基于用户的历史轨迹数据来分析和预测用户下一步将去往何处.此类应用不仅可以用来做基于地理位置的兴趣推荐, 还可以服务于公共生活, 例如预测交通堵塞将在何处发生, 或哪个城市将遭受恐怖组织袭击.

文献[27]针对监控视频中的行人轨迹提出了Social LSTM模型, 对每条轨迹序列, 使用LSTM进行预测.其创新点在于, 通过引入局部池化来解决多用户交互下的轨迹预测问题.局部池化的本质是在以目标对象坐标点为中心的一定范围内划分网格, 将当前时刻落在每个网格内的邻居用户的隐向量相加作为该网格的权重, 最后以所有网格的权重构成张量作为池化的结果, 并将其作为下一时刻LSTM的输入.作者认为: 池化的结果融合了周围行人的信息, 通过训练可以有效地避免预测路径与邻居路径相撞.

文献[28]在Social LSTM的基础上做出两点改进, 提出了Social GAN模型: 首先, 作者认为用户可能会因为看到较远处的其他用户的行为而提早改变自己的轨迹, 而局部池化并不能够覆盖到远处的邻居, 因此, 作者设计了全局池化, 在池化时考虑了当前用户与其他所有用户之间的信息; 其次作者认为Social LSTM只能给出一种预测结果, 意味着模型学到的其实是一种“平均行为”, 这在一定程度上限制了预测的效果.因此, 作者在输入信息中引入了服从标准正态分布的随机噪声, 同一条轨迹在不同随机噪声的影响下将会得到不同的预测结果, 选取这些结果中最好的那个作为最终的预测结果, 并用来计算损失函数.值得一提的是: 模型采用了GAN去优化参数, 这在轨迹数据挖掘应用中是比较少见的.文献[26]进一步在Social GAN的基础上引入了注意力机制[55], 同时还使用语义分割的方法从场景图像中提取信息, 从而获得了更准确的预测结果.

2.4.2 轨迹相似性计算

时空轨迹相似性计算, 即计算不同轨迹间的相似程度, 是诸多轨迹应用的基础.现有的轨迹相似性计算方法主要可以分为两类: 基于轨迹序列和基于表示向量.

传统的方法多是基于轨迹点序列, 通过点对匹配(pairwise points-matching)的方法来计算相似性, 即, 按某种方式累加轨迹点对之间的距离来作为度量轨迹间相似程度的依据.其中, 全局匹配度量方法有欧式距离法[56]、动态时间规整(DTW)[57]、编辑距离法(ERP)[58]等, 局部匹配度量法主要有实序列编辑距离法(EDR)[59]、最长公共子序列法(LCSS)[60]k-最佳连接路径法(k-BCT)[61]和基于邻近点的轨迹互补法(CATS)[62]等.不过, 基于点对匹配方法的基本假设是轨迹数据具有一致的采样率, 因此, 此类方法容易受到轨迹采样率和轨迹噪声的影响.

针对轨迹数据采样率低、采样率不一致、采样过程存在噪声等问题, 基于表示向量的方法试图通过将轨迹数据转化成向量来克服轨迹序列的不足.文献[1]提出了一种针对低质量轨迹数据的稳健表示方法, 并以此来计算相似性.作者利用低采样率的轨迹去尽可能还原采样自同一轨迹的高采样率数据, 从而学习出轨迹的潜在表示.具体实现时, 作者对同一条轨迹进行下采样(down sampling)和变形(distortion)得到低质量的轨迹数据, 通过这种方式, 可以自行生成丰富的训练数据.对轨迹单元的表示依然采用了Skip-gram模型, 利用RNN来学习从低质量轨迹到高质量轨迹的嵌入.文献[2]在文献[1]的基础上进行了改进, 其借鉴了文献[21]对时间、位置、语义信息的处理, 将上述3种信息的表示向量组合到一起作为轨迹的表示, 并通过比较低采样率和高采样率轨迹的表示向量来完成轨迹间的相似性度量.

通过轨迹相似性计算, 我们可以从实验上较为直接地度量基于表示向量方法的效果.为此, 首先需要定义相似轨迹.例如, 文献[1]假设若两条轨迹SS'均采样自同一条真实路径, 则认为SS'属于相似轨迹.好的轨迹表示方法应当在对相似的轨迹进行表示后, 其表示结果依然满足相似关系.以此为依据, 通过对比相似轨迹在不同表示方法下表示结果的相似性, 可以实现对不同轨迹表示方法效果的度量和评价.

2.4.3 轨迹聚类

在有了上述的轨迹相似性计算作为铺垫后, 轨迹聚类就是在其基础上进一步将相似的轨迹段或轨迹划分到一起.常见的轨迹聚类方法是将轨迹或轨迹段表示成向量, 通过计算向量间的距离来完成聚类.

文献[3]通过人工设计特征的方式将轨迹段的位移、速度、角度信息表示成向量, 然后将该向量输入到Seq2Seq模型中做特征提取, 并将得到的定长向量作为轨迹段的表示, 最后使用经典的聚类算法完成对轨迹段的聚类.

然而文献[4]认为: 将轨迹映射到特征空间会造成轨迹间的距离关系不再被保持, 这不利于聚类这种依赖相似性度量的应用.针对这一问题, 文献[4]提出了一种完全基于几何变换的映射方法来保持轨迹间原有的距离关系.作者首先基于划分网格的方法对轨迹所涉及区域的范围进行表示, 通过计算不同轨迹间所占网格的交集与并集的比值来度量轨迹间的相似性.映射过程主要基于勾股定理(Pythagorean theorem), 保证了特征空间是正交的.最后, 使用改进后的K-means算法对轨迹进行聚类.

3 对整条轨迹的表示

接下来我们介绍针对整条轨迹的表示.从算法逻辑的角度来看, 上述的基于轨迹序列单元的表示方法遵循的是分治(divide and conquer)的思想.轨迹序列首先被分成若干个单元(即divide), 然后再对轨迹序列单元进行表示, 进而整条轨迹将会以新形式下的单元序列呈现出来(即conquer).而有别于上述逻辑, 针对整条轨迹的表示方法不再聚焦于序列单元的表示, 而是将整条轨迹序列视为一个单元来表示[4].

3.1 基于曲线拟合

这类方法尤其常见于早期的一些工作.正如我们在定义1中所述, 轨迹可以看作是空间坐标关于时间的函数, 基于曲线拟合的方法的基本思想就是: 通过函数曲线来近似轨迹的形状, 一旦能够实现这种近似, 那么轨迹将不再由轨迹点序列表示, 取而代之的是由拟合函数的参数来表示, 即$\left\langle x_{i}, y_{i}\right\rangle=f\left(t_{i} ; \varTheta\right) $.未被采样到的轨迹点也可以利用拟合函数进行插值.此外, 函数的参数$ \varTheta$不仅能够在一定程度上代表轨迹的特征, 而且还能大大地降低处理轨迹数据的计算复杂度.

最朴素的一种方法就是线性插值, 即将相邻的两个采样点用直线相连, 轨迹则由若干个分段函数来表示.但通过这样方式拟合得到的分段函数是不光滑的, 不仅不能表示真实的轨迹(真实的轨迹不是折线段), 而且在数学上也难以处理.常见的做法是用低阶曲线来近似轨迹(例如三阶曲线).文献[8, 37-39]均使用三阶B样条曲线来近似轨迹.

基于曲线拟合的方法的优点是数学意义明确, 但其局限也显而易见.

(1) 仅仅通过近似轨迹形状所挖掘到的信息是十分有限的, 难以获知隐藏在轨迹背后的行为模式.此外, 在现实中, 尤其是在大范围场景下的轨迹通常较为复杂, 因此往往需要靠多段曲线拼接的方式来近似, 这给此类方法的应用带来了挑战.通过曲线拟合得到的轨迹表示通常适用于轨迹较为规范的小范围场景, 例如安防视频监控、车站人流监控.

(2) 拟合曲线的阶数不宜过高, 原因是可能会导致多项式数值在两点之间取得非常大的值, 并且这种数值的偏移会随着多项式阶数的增大呈指数增长.另外, 高阶多项式对数据点的微小变化非常敏感[22].

上述的种种因素都在一定程度上限制了基于曲线拟合方法的应用范围.

3.2 基于图像

将轨迹数据转化成图像进行处理是另一种新颖的角度, 这类方法的灵感来自于深度神经网络在图像领域取得的诸多进展.最简单的转换方法是将整个地图看作一幅二值图像, 凡是轨迹经过的像素点将像素值设置为1, 没有经过的像素点则将像素值设置为0, 如图 4(b)所示.

Fig. 4 An illustration of trajectory image 图 4 轨迹图像示意图

文献[5]将轨迹转化为单通道灰度图像, 其中, 像素值与像素点所表示区域内的轨迹点数量成正比, 即移动主体在该区域内的停留时间越长, 像素值越大.通过这种方式可以在一定程度上保留轨迹片段的时间信息, 取代了用大型的二值图像来保留轨迹细节, 从而缓解了稀疏问题.其效果如图 5所示.文献[43]设计了一种通道数为9的方向流图像(directional flow image)来捕获轨迹的位置和方向信息, 它将移动主体在二维空间中移动方向等分成9个, 相应的, 图像的每个通道分别记录轨迹在所表示方向上的移动情况, 每个像素点的像素值则存储了轨迹点向邻居像素点移动的方向, 从实现对轨迹方向流的描述.

Fig. 5 Examples of trajectory images extracted from real GPS trajectories[5] 图 5 从真实GPS轨迹提取的轨迹图像示例[5]

一旦将轨迹表示成图像之后, 对轨迹进行表示的任务就进一步转化成为提取图像的特征, 故可以使用诸如深度神经网络、卷积神经网络[40-42]、自动编码器[5]等常用于计算机视觉领域的技术来进行轨迹数据挖掘.

原始的轨迹序列形式不能直接反映轨迹点之间的空间关系, 例如空间上邻近的轨迹点不一定在序列上相邻.而使用图像来表示轨迹的最大优势就在于图像天然地体现了空间关系, 空间上邻近和时序上邻近的位置点都可以通过相邻的像素点来表示.不过, 将轨迹数据转化为图像需要处理好分辨率与稀疏性之间的矛盾, 即图像的分辨率越高(即像素点的尺寸越小), 越能描绘出轨迹的细节; 但同时也会因为像素点过多而导致轨迹数据的稀疏, 如图 4(a)所示.

3.3 基于神经网络

使用神经网络学习轨迹表示的方法与前述方法的主要区别在于, 神经网络是以端到端(end-to-end)的方式来学习轨迹表示: 神经网络的一端接收输入, 另一端产生输出, 通过直接考虑输入和输出来优化模型参数.其优势显而易见, 即模型的每一步优化都以目标函数为导向.随着深度学习的发展, 这类方法以其超越传统表示方法的效果而逐渐得到研究人员的青睐.

在轨迹表示的实际工作中, 由于神经网络往往要求输入数据为数值向量, 因此常先由其他表示方法将原始轨迹数据初步表示成向量, 再经神经网络进一步学习轨迹表示.例如, 文献[15]先利用word2vec的方法得到轨迹兴趣点的表示, 再将兴趣点序列送入循环神经网络中学习轨迹段的向量表示.

不过, 通过神经网络学习轨迹表示的方法也存在不足之处.

●轨迹表示难以显式地体现在神经网络模型中.神经网络的学习目标通常是诸如分类、预测等, 而非学习轨迹表示向量.换句话说, 轨迹表示向量往往是模型优化过程的副产品.以多层前向传播神经网络为例, 从理论上讲, 任何一层中间层的输出都可以作为原始轨迹数据的向量表示.

●轨迹表示向量是任务相关的, 即针对某一个任务学到的轨迹表示, 通常不适用于其他类型的任务.这主要是受端到端学习方式所限, 如果任务的优化目标发生改变, 那么轨迹表示则需要重新学习.

近年来, 常用于轨迹表示的神经网络模型主要是循环神经网络和卷积神经网络.

3.3.1 基于循环神经网络

循环神经网络因其处理序列数据的天然优势, 最先在轨迹数据挖掘中被广泛应用.我们以最简单的循环神经网络为例: 对于长度为l的轨迹序列, 循环神经网络中共包含l个循环单元.第i个循环单元以轨迹序列的第i个序列单元作为输入来计算其隐状态:

$ h_{i}=f\left(W \cdot h_{i-1}+C \cdot e_{i}\right). $

hi是循环单元隐状态的向量表示, 通过结合上一个隐状态向量hi-1和当前序列单元的嵌入表示ei, 经由非线性映射f(·)计算而得.其中, WC均为参数矩阵.由于最后一个循环单元的隐向量融合了所有轨迹序列单元的信息, 因此可以用最后一个隐状态向量hl来表示整条轨迹.

在实际工作中, 通常会使用循环神经网络的各种变体, 例如使用LSTM[63]和GRU[64]来克服循环神经网络梯度消失的问题, 以及配合注意力机制来缓解轨迹序列过长的问题[44, 45].然而, 循环神经网络将轨迹数据看作时间序列, 往往会忽略轨迹单元之间的空间关系.例如在轨迹预测中, 待预测的轨迹点应该位于上一个轨迹点附近.为了弥补这一缺陷, 文献[1, 36]在损失函数中引入了空间信息, 以此来保证有更大的机率预测出附近的轨迹点; 针对实际空间中的拓扑限制问题, 如建筑、障碍物会挡住道路, 文献[10, 12]通过在softmax层中引入mask向量来限制模型预测出实际不能到达的地点, 从而使得预测结果更加可信.

3.3.2 基于卷积神经网络

不同于循环神经网络仅考虑轨迹序列在时间维度上的影响, 卷积神经网络的特点在于其可以对空间维度上一块“区域”内的数据进行处理.换句话说, 循环神经网络更多地是将轨迹看作一维时间序列, 而卷积神经网络则更多地是将轨迹看作多维张量.

文献[46]首先将轨迹数据表示成兴趣点序列, 然后为每一个兴趣点分配互不相同的索引, 再使用优化过的哈希表将索引值嵌入到k维空间, 由k维向量来表示兴趣点.于是, 轨迹被表示为由兴趣点向量组成的矩阵.对该矩阵使用卷积神经网络学习轨迹的抽象表示.除此之外, 图像是卷积神经网络最常处理的数据类型.文献[41]将轨迹转化为图像后用卷积神经网络来提取轨迹的模式.为了解决第3.2节中提到的图像分辨率对轨迹表示效果的影响, 作者认为综合多种尺度下的模式可以解决该问题, 而这一点可以通过在卷积神经网络中使用多层卷积层和池化层来完成.

3.4 有关整体轨迹表示的应用

相比于对轨迹序列单元的表示, 针对整条轨迹序列表示的研究工作偏少.其原因主要在于:

(1) 数据标签较为单一.一条轨迹中通常包含了丰富的信息, 例如轨迹中的不同区段都可以拥有不同的属性和标签.而若将整条轨迹序列视为基本数据单元, 那么一条轨迹只能拥有一个相应的标签, 这在一定程度上限制了该方法的使用场景.

(2) 不同的轨迹数据往往有不同的长度, 即轨迹序列所包含的轨迹点的数量不同.由于大多数机器学习算法, 尤其是神经网络均要求输入数据是固定长度, 这种长度上的不一致为算法设计带来了挑战.

(3) 缺乏一种有效的距离度量方式.在许多轨迹数据挖掘任务中都对计算轨迹间相似性提出了要求, 例如轨迹聚类、轨迹异常检测等.然而直接用整条轨迹计算相似性, 除了上述长度不一致的缺点外, 还会面临不同轨迹采样率不一致等问题, 这共同加剧了直接使用整条轨迹的难度.

尽管面临上述难点, 依然有一批工作从各个角度出发丰富了这一类方法的应用场景.

3.4.1 轨迹分类

轨迹分类的目标是区分不同模式下的轨迹或轨迹段, 例如, 轨迹按照交通模式可以具体分为步行、骑车、乘坐公交、乘坐出租车等.对轨迹进行分类是众多应用的基础, 可以提供丰富的信息帮助我们理解移动主体.例如, 对实时轨迹的分类可以用来识别可疑的移动主体[65].

传统的轨迹分类方法通常使用人工设计的特征作为分类的依据.文献[23]基于轨迹中的换乘点将轨迹划分成不同的轨迹段, 通过实验对比了使用决策树、贝叶斯网络、支持向量机和条件随机场识别这些轨迹段所属类别的效果.文献[35]以轨迹段中的频繁项为基础, 将信息增益作为衡量分类能力的指标, 筛选出有利于分类的频繁轨迹段序列; 然后将频繁轨迹段序列及其频率作为特征, 将轨迹映射到特征空间中; 轨迹特征向量的每一个维度均是特征空间中的一个坐标轴, 即轨迹段序列或轨迹段序列的频率; 最后, 将特征向量输入到支持向量机中进行分类.

神经网络也被广泛用于此类应用中.文献[6]使用速度及其统计量作为特征, 将其嵌入到特征空间中后再送入GRU对轨迹进行分类.文献[5]将不同类别的轨迹转化为灰度图像进行分析, 如图 5所示; 然后使用降噪自编码器从轨迹图像中提取特征, 并结合人工提取的物理量特征, 共同用来训练轨迹模式的分类器.

此外, 随着移动互联网的发展, 近年来出现了众多互联网打车平台, 如Uber、滴滴等.这种通过移动设备和应用程序将司机和乘客联系起来的出行服务逐渐成为了一种新的交通模式.不过, 考虑到对用户隐私的保护, 通常难以从打车平台获取此类数据.为了解决这一问题, 文献[42]通过迁移学习的方式对互联网打车轨迹进行识别.

3.4.2 异常检测

轨迹异常检测可以看作是轨迹分类的特殊情况, 即把数据集中的正常轨迹和异常轨迹区分开来.但异常检测通常要比一般的分类问题更难, 其原因主要在于异常轨迹的样本量较少, 导致异常模式难以被建模.

文献[8]采用3次B样条曲线来拟合正常轨迹, 用求解出的控制点坐标级联时间信息作为轨迹的表示向量, 输入到混合高斯模型中对正常轨迹进行建模.对于一个新的轨迹样本, 若模型给出很低的概率则被判定为异常轨迹.文献[39]同样先使用曲线拟合的方法表示原始轨迹, 然后用优化的方法计算出待测轨迹属于不同正常轨迹的权重向量, 最后通过权重向量的稀疏程度来判断异常.

3.4.3 隐私保护

轨迹隐私是指产生轨迹的用户不愿意透露的关于用户身份的信息以及从轨迹中推导出的相关信息, 例如用户的家庭住址、个人偏好、生活习惯等.随着越来越多基于位置数据应用的出现, 对轨迹主体的轨迹隐私保护逐渐成为一个重要问题.

传统的轨迹隐私保护技术主要可以分成两类.第1类是基于泛化的方法, 其主要思想是将轨迹点泛化到相应的匿名区域, 从而实现对轨迹隐私的保护.其中最有代表性的方法是位置k-匿名技术[66], 它通过将目标对象的轨迹点与其他k-1个用户的轨迹点泛化到同一匿名区域中, 使得目标对象在任意时刻的位置都无法与其他k-1个用户的位置区分开来.第2类是基于位置掩蔽(geomasking)的方法, 其主要思想是通过隐藏或者更改部分位置数据来达到保护隐私的目的; 同时, 空间模式不会受到显著的影响.例如, 可以通过对原始数据添加噪声来降低披露风险, 以及根据具体情况有条件地发布轨迹来保证敏感位置信息不被泄露[67-69].

4 未来研究方向

虽然众多研究工作针对各自的应用背景对轨迹表示提出了不同的解决方法, 但随着轨迹数据的日益丰富和轨迹应用场景的不断扩展, 依然存在许多具有挑战性的问题有待解决.本节将对一些现有研究工作的不足以及未来值得深入研究的问题作一探讨.

4.1 多模态数据融合

单纯依靠GPS轨迹数据已经逐渐难以满足当今轨迹应用的需求.例如, 随着经济全球化程度的加深, 航运业务的快速增长要求更有效、更及时的轨迹获取方式来避免海上交通事故, 如综合使用AIS、GPS和ARPA (automatic radar plotting aid)等数据.与此同时, 随着数据获取方式的不断丰富, 人们可以收集到越来越多不同来源、不同形式的轨迹数据.例如, 基于地理位置的社交网络产生了大量具有时空标记的多模态数据, 其中包括GPS信息、文本描述、图片、短视频等.综合考虑多种模态的数据, 有利于更加全面地获取轨迹信息, 从而获得表达能力更强的轨迹表示.如何对多模态数据进行组织和融合, 逐渐成为了轨迹表示领域所面对的新挑战.

多模态数据融合涉及模态转换、对齐、消歧、融合表示等多方面内容.早期的轨迹数据融合表示方法通常是将不同类型的数据拼接成向量, 例如将时间信息、位置信息、用户标识以及兴趣点信息分别表示成向量后, 再拼接到一起作为轨迹最终的表示向量[3, 8, 67].但这种数据融合方式过于简单粗糙, 不同类别的信息在整体中的权重以及在表示向量中的位置都缺乏考量.近年来, 有越来越多的工作[2, 70, 71]采用了深度神经网络来融合不同来源的数据, 通过数据驱动的学习方式以及配合注意力机制[70], 能够在一定程度上缓解不同来源数据的权重问题.但值得注意的是, 目前针对非结构化数据融合的研究依然尚浅.同时, 多模态融合的一个关键问题是充分利用模态信息之间的互补性来构建不同模态信息之间的隐式关联关系, 从而挖掘出更丰富的轨迹数据结构特征.对不同类型数据的处理还有赖于相关研究领域的进展, 因此, 轨迹表示领域的多模态数据融合问题在未来还需要更多的关注.

4.2 生成式轨迹表示

由于轨迹数据在采集、传输等过程中存在的诸多限制, 往往导致收集到的轨迹数据中会不可避免地存在相当一部分的低质量轨迹数据.例如, 由于受采集精度、海上信号漂移、网络传输条件等因素的影响, AIS系统在实际场景中采集到的轨迹数据往往不尽如人意.质量不一、噪音、缺值等一直是船舶时空轨迹数据中普遍存在的问题.低质量轨迹数据会从源头上影响轨迹数据挖掘的效果.因此, 如何得到高质量的轨迹数据和高质量的轨迹表示, 一直以来都是轨迹数据挖掘领域的研究重点.

近年来, 随着以GAN为代表的生成模型的广泛应用, 利用生成模型来生成高质量轨迹数据成为了解决上述问题的一种新思路.生成的高质量轨迹不仅可以用来缓解轨迹稀疏、噪声等问题, 而且基于高质量轨迹得到的轨迹表示也会更加稳健.文献[72]提出了一种叫做trajGANs的框架, 该框架可作为“隐私保护层”加入到轨迹数据处理的过程中, 通过生成可以满足分析任务的轨迹数据来达到保护隐私的目的.文献[73]受该框架所启发, 结合了LSTM和GAN来生成用于发布的轨迹数据, 并在轨迹-用户链接任务上验证了生成轨迹的有效性, 为轨迹隐私保护提供一种全新的视角.文献[1]提出一种学习轨迹深度表示的模型, 该模型基于seq2seq结构, 利用人工加噪得到的低质量轨迹去生成未经加噪处理的原始轨迹, 使得模型在面对低采样率、噪声等问题时具有一定的稳健性.作者使用轨迹的嵌入表示作为轨迹表示向量, 在轨迹相似性计算问题上取得了超越传统方法的效果.但需要指出的是, 由于轨迹数据具有天然的序列形式, 现有的轨迹生成模型大多是基于RNN, 通过最大化目标位置概率的方式来依次生成轨迹点.然而基于RNN的生成模型极易在测试阶段造成累积误差[74], 即模型根据之前预测得到的轨迹点来预测下一个轨迹点, 而预测的轨迹点本身可能存在误差, 并在之后的预测过程中造成误差的累积传递.因此, 探索更加多元的轨迹生成方法值得在未来进一步研究.

4.3 语义轨迹表示

现有的轨迹表示方法大多只聚焦于轨迹数据本身, 很少考虑潜在的语义信息, 从而影响了轨迹建模的准确性.如在轨迹异常检测领域, 根据出租车辆的绕路等行为模式, 可以将一些轨迹判定为异常.然而, 如果考虑轨迹的语境, 比如途经某正在举办大型体育赛事的拥堵路段, 那么这些“异常”轨迹在当前语境下实际上应当是正常的.因此, 随着语义信息的获取越来越方便, 例如大型活动、天气、景点和突发事件等, 轨迹表示不应仅局限于轨迹本身, 还应充分利用从其他信息源获得的语义信息, 以得到表达能力更强的语义轨迹表示.使用语义轨迹表示有助于丰富轨迹数据挖掘的内容.例如, 将POI等信息作为轨迹的位置语义, 可以在度量时空相邻的同时增加对轨迹语义相似的度量和判断, 从而实现对人群更细粒度的识别和分类.因此, 近年来, 对语义轨迹的研究逐渐成为了一个新的研究热点, 其主要任务是通过借助外部语义信息来对轨迹数据的语义信息进行推断、匹配和挖掘, 从而将无语义的轨迹数据转化成带有语义信息的轨迹表示.目前, 针对语义轨迹表示的探索主要集中在以下两类方法上.

●第1类方法主要是通过引入地理位置的语义注释(例如兴趣点、兴趣区域和路径的语义注释)或借助已知语义信息的数据(例如地图、文本), 为轨迹单元匹配或生成语义标签.文献[75]对地理位置语义理解的技术做了详细的归纳.现有的工作大多集中在挖掘分析轨迹的语义标签来得到语义轨迹, 进而基于语义理解进行诸如地理位置推荐[76-78]、预测[79-81]等任务.这类方法的优点是轨迹单元拥有明确的语义, 但关于如何进一步对语义轨迹进行表示并没有过多探究.此外, 在融合语义信息与时空信息这一方面, 也会面临第4.1节中提到的难点.

●第2类方法主要是在缺少外部语义信息的条件下, 通过融合先验知识和轨迹数据的自身属性来挖掘轨迹单元之间的隐含语义联系.其中最有代表性的一类工作是借鉴分布式词向量表示的思路, 将轨迹单元视为词语, 利用无监督学习的方式将轨迹单元映射到连续的向量空间中, 以此来挖掘邻近轨迹单元的上下文关系, 进而得到轨迹的语义表示[1, 2, 48, 82].这类方法的特点是其向量表示能够较好地体现轨迹单元之间的潜在语义联系, 但不足之处是缺少关于轨迹单元本身的语义理解.

现有的相关工作依然有很多挑战未解决.1) 当前的研究往往假设语义信息是确定的, 而实际环境中, 轨迹位置的语义数据通常是繁多且模糊的.例如, 同一个位置附近可能有多个重复的兴趣点, 从而造成语境上的冗余; 此外, 尽管重要事件可以显著地影响轨迹的语义解释, 但用户可能是因为相关事件而前往某场所, 也有可能只是经过该场所.因此, 轨迹数据与语义信息的相关程度度量、个性化的轨迹语义信息过滤等, 也是重要的研究问题.2) 现有对语义轨迹表示的研究主要侧重于局部语义, 很少对轨迹的全局语义进行表征.而不同粒度的语义单元也会对轨迹表示的质量带来影响.因此, 如何选择恰当的语义单元粒度, 以及如何构建可靠的语义轨迹距离度量方法来支撑有效的轨迹表示等, 都值得进一步深入研究.

5 总结

定位设备的普及和基于位置信息应用的发展, 为轨迹数据挖掘提供了海量的数据支持和应用需求.轨迹数据挖掘的研究领域必然会随着数据的演化和技术的进步而不断地发展.而轨迹表示承担着将原始数据转化为模型输入的重要任务, 是轨迹数据挖掘中的一项关键技术, 研究者们针对不同应用背景下的轨迹表示做了大量的工作.本文对近年来轨迹表示的主要研究成果进行了全面的梳理和总结, 将轨迹表示按照研究对象的不同尺度分为对轨迹单元的表示和对整条轨迹的表示, 其中, 对每一种类别的表示方法按照方法的不同原理进一步做了详细的对比分析, 并给出了相应的轨迹数据挖掘应用.最后, 本文对轨迹表示领域现有工作研究不足的问题和未来值得研究的方向提出了自己的观点.

参考文献
[1]
Li X, Zhao K, Cong G, 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]
[2]
Zhang Y, Liu A, Liu G, Li Z, Li Q. Deep representation learning of activity trajectory similarity computation. In: Proc. of the 2019 IEEE Int'l Conf. on Web Services (ICWS). 2019. 312-319. [doi: 10.1109/icws.2019.00059]
[3]
Yao D, Zhang C, Zhu Z, Huang J, Bi J. Trajectory clustering via deep representation learning. In: Proc. of the Int'l Joint Conf. on Neural Networks. 2017. 3880-3887. [doi: 10.1109/IJCNN.2017.7966345]
[4]
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]
[5]
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]
[6]
Jiang X, de Souza EN, Pesaranghader A, Hu B, Silver DL, Matwin S. TrajectoryNet: An embedded GPS trajectory representation for point-based classification using recurrent neural networks. 2017. http://arxiv.org/abs/1705.02636
[7]
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]
[8]
Sillito RR, Fisher RB. Semi-supervised learning for anomalous trajectory detection. In: Proc. of the British Machine Vision Conf. (BMVC 2008). 2008. [doi: 10.5244/C.22.103]
[9]
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.
[10]
Wu H, Chen Z, Sun W, Zheng B, Wang W. Modeling trajectories with recurrent neural networks. In: Proc. of the Int'l Joint Conf. on Artificial Intelligence. 2017. 3083–3090. https://doi.org/10.24963/ijcai.2017/430
[11]
Wang J, et al. Spatiotemporal modeling and prediction in cellular networks: A big data enabled deep learning approach. 2017. [doi: 10.1109/INFOCOM.2017.8057090]
[12]
Chow KH, Hiranandani A, Zhang Y, et al. Representation learning of pedestrian trajectories using actor-critic sequence-to- sequence autoencoder. arXiv preprint arXiv: 1811.08069, 2018.
[13]
Yin P, Ye M, Lee WC, Li Z. Mining GPS data for trajectory recommendation. 2014. [doi: 10.1007/978-3-319-06605-9_5]
[14]
Yang C, Sun M, Zhao WX, et al. A neural network approach to jointly modeling social networks and mobile trajectories. ACM Trans. on Information Systems (TOIS), 2017, 35(4): 1-28. [doi:10.1145/3041658]
[15]
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.
[16]
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.
[17]
Zheng Y. Trajectory data mining: An overview. ACM Trans. on Intelligent Systems and Technology, 2015, 6(3): 1-41. [doi:10.1145/2743025]
[18]
Wang S, Cao J, Yu PS. Deep learning for spatio-temporal data mining: A survey. 2019. 1-21. http://arxiv.org/abs/1906.04928
[19]
He X, Cormode G, Machanavajjhala A, et al. DPT: Differentially private trajectory synthesis using hierarchical reference systems. Proc. of the VLDB Endowment, 2015, 8(11): 1154-1165. [doi:10.14778/2809974.2809978]
[20]
Mao Y, Zhong H, Qi H, 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]
[21]
Yao D, Zhang C, Huang J, 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]
[22]
Yu B, Kim SH, Bailey T, Gamboa R. Curve-based representation of moving object trajectories. In: Proc. of the Int'l Database Engineering and Applications Symp. (IDEAS). 2004. 419-425. [doi: 10.1109/IDEAS.2004.1319817]
[23]
Zheng Y, Liu L, Wang L, Xie X. Learning transportation mode from raw GPS data for geographic applications on the Web. 2008. [doi: 10.1145/1367497.1367532]
[24]
Zheng Y, Li Q, Chen Y, Xie X, Ma WY. Understanding mobility based on GPS data. 2008. [doi: 10.1145/1409635.1409677]
[25]
Yao Z, Fu Y, Liu B, Hu W, Xiong H. Representing urban functions through zone embedding with human mobility patterns. In: Proc. of the IJCAI Int'l Joint Conf. on Artificial Intelligence. 2018. 3919-3925. [doi: 10.24963/ijcai.2018/545]
[26]
Sadeghian A, Kosaraju V, Sadeghian A, Hirose N, Rezatofighi SH, Savarese S. SoPhie: An attentive GAN for predicting paths compliant to social and physical constraints. 2018. http://arxiv.org/abs/1806.01482
[27]
Alahi A, Goel K, Ramanathan V, 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]
[28]
Gupta A, Johnson J, Li FF, Savarese S, Alahi A. Social GAN: Socially acceptable trajectories with generative adversarial networks. In: Proc. of the IEEE Computer Society Conf. on Computer Vision and Pattern Recognition. 2018. 2255-2264. [doi: 10.1109/CVPR.2018.00240]
[29]
Hamilton WL, Ying R, Leskovec J. Representation learning on graphs: Methods and applications. 2017. http://arxiv.org/abs/1709.05584
[30]
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]
[31]
Zhang C, et al. Regions, periods, activities: Uncovering urban dynamics via cross-modal representation learning. 2017. 361-370. [doi: 10.1145/3038912.3052601]
[32]
Wang G, Liao D, Li J. Complete user mobility via user and trajectory embeddings. IEEE Access, 2018. [doi: 10.1109/ACCESS.2018.2881457]
[33]
Wang H, Li Z. Region representation learning via mobility flow. In: Proc. of the Int'l Conf. on Information and Knowledge Management. 2017. 237-246. [doi: 10.1145/3132847.3133006]
[34]
Xie M, Yin H, Wang H, Xu F, Chen W, Wang S. Learning graph-based poi embedding for location-based recommendation. In: Proc. of the Int'l Conf. on Information and Knowledge Management. 2016. 15-24. [doi: 10.1145/2983323.2983711]
[35]
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]
[36]
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.
[37]
Sillito RR, Fisher RB. Parametric trajectory representations for behaviour classification. Multimedia Systems, 2006, 12: 227-238. [doi:10.5244/C.23.101]
[38]
Li C, Han Z, Ye Q, et al. Visual abnormal behavior detection based on trajectory sparse reconstruction analysis. Neurocomputing, 2013, 119: 94-100. [doi:10.1016/j.neucom.2012.03.040]
[39]
Chen Z, Cai H, Zhang Y, et al. A novel sparse representation model for pedestrian abnormal trajectory understanding. Expert Systems with Applications, 2019, 138: Article No. 112753. [doi: 10.1016/j.eswa.2019.06.041]
[40]
Zhang L, Zhang G, Liang Z, et al. Multi-features taxi destination prediction with frequency domain processing. PloS one, 2018, 13(3): Article No. e0194629. [doi: 10.1371/journal.pone.0194629]
[41]
Lv J, Li Q, Sun Q, Wang X. T-CONV: A convolutional neural network for multi-scale taxi trajectory prediction. In: Proc. of the 2018 IEEE Int'l Conf. on Big Data and Smart Computing (BigComp 2018). 2018. 82-89. [doi: 10.1109/BigComp.2018.00021]
[42]
Wang L, Geng X, Ke J, et al. Ridesourcing car detection by transfer learning. arXiv preprint arXiv: 1705.08409, 2017. [doi: 10.475/123]
[43]
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]
[44]
Feng J, Li Y, Zhang C, et al. DeepMove: Predicting human mobility with attentional recurrent networks. In: Proc. of the 2018 World Wide Web Conf. 2018. 1459-1468.
[45]
Liang Y, Ke S, Zhang J, et al. Geoman: Multi-level attention networks for geo-sensory time series prediction. In: Proc. of the IJCAI. 2018. 3428-3434. [doi: 10.24963/ijcai.2018/476]
[46]
Karatzoglou A, Schnell N, Beigl M. A convolutional neural network approach for modeling semantic trajectories and predicting future locations. In: Proc. of the Int'l Conf. on Artificial Neural Networks. Cham: Springer-Verlag, 2018. 61-72. [doi: 10.1007/978-3-030-01418-6_7]
[47]
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]
[48]
Mikolov T, Sutskever I, Chen K, et al. Distributed representations ofwords and phrases and their compositionality. arXiv preprint arXiv: 1310.4546, 2013.
[49]
Banerjee P, Ranu S, Raghavan S. Inferring uncertain trajectories from partial observations. In: Proc. of the IEEE Int'l Conf. on Data Mining. IEEE, 2014. 30-39. [doi: 10.1109/ICDM.2014.41]
[50]
Wu H, Mao J, Sun W, et al. Probabilistic robust route recovery with spatio-temporal dynamics. In: Proc. of the 22nd ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining. 2016. 1915-1924. [doi: 10.1145/2939672.2939843]
[51]
Ranu S, Deepak P, Telang AD, et al. Indexing and matching trajectories under inconsistent sampling rates. In: Proc. of the IEEE 31st Int'l Conf. on Data Engineering. IEEE, 2015. 999-1010. [doi: 10.1109/ICDE.2015.7113351]
[52]
Mikolov T, Chen K, Corrado G, Dean J. Efficient estimation of word representations in vector space. arXiv preprint arXiv: 1301. 3781, 2013.
[53]
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.
[54]
Hinton GE. Learning distributed representations of concepts. In: Proc. of the Eighth Annual Conf. of the Cognitive Science Society. 1986. [doi: 10.1109/69.917563]
[55]
Bahdanau D, Cho K, Bengio Y. Neural machine translation by jointly learning to align and translate. 2014. http://arxiv.org/abs/1409.0473.
[56]
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.
[57]
Keogh EJ, Pazzani MJ. Scaling up dynamic time warping for datamining applications. In: Proc. of the 6th ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining. 2000. 285-289. [doi: 10.1145/347090.347153]
[58]
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.
[59]
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.
[60]
Vlachos M, Kollios G, Gunopulos D. Discovering similar multidimensional trajectories. In: Proc. of the Int'l Conf. on Data Engineering. IEEE, 2002. 673-684. [doi: 10.1109/ICDE.2002.994784]
[61]
Chen Z, Shen HT, Zhou X, et al. Searching trajectories by locations: An efficiency study. In: Proc. of the 2010 ACM SIGMOD Int'l Conf. on Management of data. 2010. 255-266. [doi: 10.1145/1807167.1807197]
[62]
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]
[63]
Hochreiter S, Schmidhuber J. Long short-term memory. Neural Computation, 1997, 9(8): 1735-1780. [doi:10.1162/neco.1997.9.8.1735]
[64]
Chung J, Gulcehre C, Cho K, Bengio Y. Empirical evaluation of gated recurrent neural networks on sequence modeling. arXiv preprint arXiv: 1412.3555, 2014.
[65]
Fraile R, Maybank SJ. Vehicle trajectory approximation and classification. In: Proc. of the BMVC. 1998. 832-840. [doi: 10.5244/c.12.83]
[66]
Gruteser M, Grunwald D. Anonymous usage of location-based services through spatial and temporal cloaking. In: Proc. of the 1st Int'l Conf. on Mobile Systems, Applications and Services. 2003. 31-42. [doi: 10.1145/1066116.1189037]
[67]
Terrovitis M, Mamoulis N. Privacy preservation in the publication of trajectories. In: Proc. of the 9th Int'l Conf. on Mobile Data Management (MDM 2008). IEEE, 2008. 65-72. [doi: 10.1109/MDM.2008.29]
[68]
Gruteser M, Liu X. Protecting privacy, in continuous location-tracking applications. IEEE Security & Privacy, 2004, 2(2): 28-34. http://doi.ieeecomputersociety.org/10.1109/MSECP.2004.1281242
[69]
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). https://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201110008.htm
[70]
Zheng C, Peng Q, Xu X. Heterogenous multi-source fusion for ship trajectory complement and prediction with sequence modeling. In: Proc. of the IEEE 9th Int'l Conf. on Data Science in Cyberspace (DSC 2020). IEEE, 2020. 15-21. [doi: 10.1109/dsc50466.2020.00011]
[71]
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.
[72]
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.
[73]
Rao J, Gao S, Kang Y, Huang Q. LSTM-Trajgan: A deep learning approach to trajectory privacy protection. arXiv preprint arXiv: 2006.10521, 2020.
[74]
Bengio S, Vinyals O, Jaitly N, Shazeer N. Scheduled sampling for sequence prediction with recurrent neural networks. 2015. http://arxiv.org/abs/1506.03099
[75]
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]
[76]
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. [doi:10.1109/TKDE.2016.2580511]
[77]
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.
[78]
Liu X, Liu Y, Li X. Exploring the context of locations for personalized location recommendations. In: Proc. of the IJCAI. 2016. 1188-1194.
[79]
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.
[80]
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.
[81]
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.
[82]
Gao C, Zhang Z, Huang C, Yin H, Yang Q, Shao J. Semantic trajectory representation and retrieval via hierarchical embedding. Information Sciences, 2020, 538: 176-192. [doi: https://doi.org/10.1016/j.ins.2020.05.107]
[69]
霍峥, 孟小峰. 轨迹隐私保护技术研究. 计算机学报, 2011, 34(10): 1820-1830. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201110008.htm
[75]
姚迪, 张超, 黄建辉, 陈越新, 毕经平. 时空数据语义理解: 技术与应用. 软件学报, 2018, 29(7): 2018-2045. http://www.jos.org.cn/1000-9825/5576.htm [doi:10.13328/j.cnki.jos.005576]