 | 深度学习在轨迹数据挖掘中的应用研究综述
人工智能技术与咨询
图片
来源：《 计算机科学与应用》 ，作者李旭娟等
关键词: 深度学习；数据挖掘；轨迹挖掘；长短时记忆；序列到序列
摘要: 在过去十年，深度学习已被证明在很多领域应用非常成功，如视觉图像、自然语言处理、语音识别等，同时也涌现出来了大量深度学习模型，如深度卷积神经网络，深度循环神经网络、深度信念网络、深度对抗生成网络等，其深度越深学习能力越强，但同时也增加了网络训练的复杂度，权衡利弊取其中，所以在不同的应用中有很大的研究空间。另外，在基于时序数据的应用研究中，如股票趋势预测、天气预测、异常气候地质灾害预测等，相比较于传统的方法，各种改进的、融合的深度学习方法显然更胜一筹。而轨迹数据是时序数据的一种，它除了有时间维度的依赖性还有空间维度的相关关系。轨迹数据挖掘与我们的生活息息相关，从城市规划到个性化推荐，从出行安全到优质服务。所以本文通过对轨迹数据进行简单的剖析，对轨迹数据的应用进行一定的总结，并分析了一些用于轨迹数据挖掘的深度学习模型的优缺点，提出了一些小技巧，以此来对后续轨迹数据挖掘提供一些思路。
1. 介绍
由于位置感知设备如手机、可穿戴产品的不断普及，基于位置的社交网络被广泛使用，大量的轨迹数据应运而生。如手机定位系统会产生每个人的行为轨迹数据，汽车导航定位系统会产生大量的汽车轨迹数据，飞机的广播式自动相关监视系统(Automatic dependent surveillance-broadcast，缩写为ADS-B)也会形成大量的航迹数据。这些轨迹数据集已被证明是非常宝贵的资源，可以用来做城市规划、交通管制、行为生态学研究、运动场景分析、监测管理和提高安全系数等。学者们花了大量的时间和精力研究了很多轨迹数据分析和挖掘的方法。其中 [1] 在2015年对轨迹挖掘应用中已解决的问题做了系统的总结，包括解决方法和应用场景，并分析了他们的关系， [2] 在2016年对轨迹的数据预处理、数据管理和数据查询技术，轨迹数据应用和隐私保护等方面进行了分析和讨论，但其中的解决方案、技术应用都没有提及发展得如火如荼的深度学习方法。终于在2019年， [3] 站在了更高更广的角度系统的总结了深度学习在时空数据挖掘中的应用，然而它在具体的轨迹数据挖掘方面的阐述并不详细，因此本文就哪些深度学习方法解决了哪些轨迹数据挖掘任务的问题进行系统地分析和讨论。
本文接下来将在第2部分对轨迹数据和轨迹数据挖掘任务进行简单的介绍；在第3部分列举一些在轨迹数据挖掘应用中常用的深度学习模型；第4部分，叙述了如何为特定的任务选择和设计深度学习模型；第5部分，总结和展望。
2. 轨迹数据
2.1. 定义
轨迹数据是物体或者人随着时间移动而产生的路径信息，包括位置坐标和速度等，通常由随物体或人携带的传感器产生并在一定的时间间隔记录相关信息。全球卫星导航系统(The Global Navigation Satellite System，缩写为GNSS)是传感器提供位置信息的主要来源，常用的现阶段最完善的是GPS系统，还有正在亚太地区全面开启服务的BDS、GLONASS系统也将广泛使用，在轨迹数据上的体现将是更加实时性和更高的精度。
2.2. 表达方式
通常一条轨迹可以表示为一个序列，如 {(p1,t1),(p2,t2),⋯(pn,tn)}{(p1,t1),(p2,t2),⋯(pn,tn)}，其中pi表示位置(如经度、纬度)，
ti表示物体或者人经过该位置的时间。它可以直接作为循环神经网络(RNN)的输入，成为典型的深度学习模型学习的对象之一。
有时轨迹数据也可以用一个二维图像(或2维矩阵)来表示，如一条轨迹可以对应着一张二维地图，如图1(a)。若将地图划成M * M的网格，M是预定义的常量，表示地图的分辨率，用Cx,y表示第x行和第y列的网格，则每个轨迹点都可以根据它的经纬度映射到一个网格Cx,y中，通过这种方式，我们就将一条轨迹转化为一个M * M的图像(如图1(b))，其中网格中的值要么为零，要么是轨迹坐标对应的一个非负值，表示位置信息。这种数据表达多是为了符合CNN模型的输入格式，让卷积网络尝试学习轨迹数据中的特征，这种表达方式更能保留位置间的相关关系。
图片
Figure 1. (a) Raw trajectory, (b) Cell trajectory in the 2D grid map
图1. (a) 原始轨迹，(b) 二维地图中的单元格轨迹
2.3. 深度学习在轨迹数据挖掘中的应用
用深度学习方法研究轨迹数据，任务类型集中在预测、表示学习、分类、异常检测等，应用的领域多涉及城市交通、航海、航空、行人轨迹等方面。
而基于历史数据对未来做预测是轨迹数据最常用的领域。轨迹预测在一定程度上与语言模型中预测词语、句子很像，比如给定一个句子，语言模型被训练用来从句子数据中学习词句模式，然后预测下一个词可能是什么。而在轨迹数据中，一系列的位置坐标可以看作是字典里的字词，一条轨迹就可以看作是一个句子，那么轨迹下一个位置的预测就与句子下一个词的预测如出一辙。 [4] 将轨迹数据的时间信息剥离，每个点只留下经纬坐标，通过城市区域网格化将简化了的轨迹序列转化为单元格序列，再逐条输入GRU构成的RNN网络，预测下一个位置。[5] [6] 分别用的不同的深度学习方法进行交通速度预测， [7] 用循环神经网络对出租车的需求进行实时预测， [8] 将轨迹数据和文本数据分别输入长短时记忆网络(或者全连接层)和卷积层，再把得到两种特征进行融合，从而进行事件区域的出租车需求预测。
在船舶交通服务系统中，准确、有效地对船舶的航行轨迹进行及时跟踪和预测是海上交通事故预警的重要技术支撑， [9] 通过结合船舶自动识别系统提供的历史轨迹数据和当前轨迹预测未来某时刻船舶的轨迹。在航空领域，管制员需要精确地知道经过其管辖范围的每架飞机的实时位置，这便需要空管系统能够精确地预测飞机的轨迹， [10] 结合了航班计划和气象信息，用深度生成模型根据某时刻以前轨迹信息预测接下来一段时间的轨迹。
有时要想获得运动模式或实施某项数据挖掘任务如位置预测，轨迹聚类是基础任务，意在把轨迹划分为几组，每组中的轨迹有很高的相似度。 [11] 先提取轨迹数据中的时空不变特征，如运动特征，再通过Seq2Seq的自动编码器得到特征的固定长度表达，最后通过分类器达到轨迹聚类的目的。另外，在信息化作战领域，为辅助指挥员分析战局， [12] 使用CNN模型对雷达提供的目标物体进行航迹类型识别，此为分类任务。
另一种常见的相关任务是异常检测。 [13] 提出的双Attention融合机制的行人轨迹预测方法同样可以作为异常事件检测手段，其中编码器得到的目标行人轨迹编码就会与正常行人轨迹的编码有很大区别，因此用一些经典的聚类算法便可将异常检测到。由于ADS-B数据的易获取性，为确保飞机和地面接收站收到的是正确安全的信息， [14] 提出了一个基于深度神经网络的SODA系统，包括一个信息分类器和一个航空器分类器，能够精确地检测到欺骗攻击。[15] 采用Seq2Seq模型进行异常的ADS-B时间序列检测，并通过对序列特征维度的增加来提升检测效果。
3. 常用的深度学习模型
3.1. 循环神经网络
循环神经网络(Recurrent Neural Network, 缩写为RNN)是被设计用来识别序列特征并使用模式来预测下一个可能的场景，最大的特点就是有了记忆功能。与传统深度神经网络中每一层使用不同的参数的做法不同，RNN在所有时刻中共享相同的参数，这反应了在每一步中都在执行相同的任务，即循环所在，只是用了不同的输入，这样极大地减少了需要学习的参数的个数。之后出现的RNN变体，如Bidirectional RNN是在某时刻的输出不仅依赖于序列之前的元素也依赖于之后的元素。DeepBRNN，即在Bidirectional RNN的基础上，每时每刻会有多个隐藏层，这将会使它有更强的学习能力。
图2展示了RNN的基本结构。其中xt和ht分别表示t时刻的输入和学习到的隐藏状态，A是一组神经网络，它不停的接收xt并输出ht。可以看出前一时刻t − 1的输出(ht − 1)被输入到了下一时刻t，这样历史信息就被存储并传递下去了。
RNN有两个缺点，一是记忆力短，随着网络的加深前面存储的内容的影响将逐渐减弱，这将会丢失部分重要的信息。二是没办法控制信息中记住哪些，舍掉哪些，这使得一些不重要的信息增加网络的训练负担，增加干扰。
图片
Figure 2. Structure of RNN model
图2. 循环神经网络模型结构
3.2. 长短时记忆
长短时记忆(Long Short Term Memory，缩写为LSTM)是RNN的一个扩展，图3展示了LSTM的基本结构，与RNN不同的是循环的神经网络A结构变复杂了，它加入了一种特殊的记忆单元(细胞状态)，即贯穿图表顶部的水平线，能很好的保持信息不变；并用三个门控制信息的输入输出，即输入门、忘记门和输出门；最后，每个时刻的输出由两部分组成：细胞状态和输出状态。其中，门的结构很简单，就是一个sigmoid层(即图x中的σ处)来决定输入信息中哪些需要丢弃、哪些需要更新、哪些需要输出。细胞状态是由上一次的细胞状态按元素乘以遗忘门，再加上输入门与当前状态(输入信息经过tanh处理后)的乘积结果，而最后的输出状态是由细胞状态经过一个tanh之后与输出门的乘积。LSTM这种结构提供了只把重要的内容存下来，需要的时候再输出，甚至必要的时候清空等十分强大的功能，解决了RNN的两个问题，但也同时增大了网络的训练难度，因为结构中所需的参数大大增加了。
图片
Figure 3. Structure of LSTM model
图3. 长短时记忆模型结构
但参数的数量还没有大到让人们望而却步，反而LSTM与其它网络的结合使用频繁出现，如 [16] LSTM-FCN将数据转换成相应的维度同时输入FCN和LSTM，并将输出的结果合并，取得了非常好的效果。[17] 提出的Conv-LSTM结构堆叠在编码–解码模型中，不仅很好的保留了数据的时序性，还能在空间维度保留数据间的相关关系。[18] 提出了一个新的方法来训练LSTM，使门的输出不是0到1的一个范围，而是非0即1。这种方法使得输出结果更容易理解，意思是经过门的信息要么保留要么舍弃。试验结果也证明这种训练方式的效果更佳。另外，门循环单元(Gated Recurrent Unit，缩写为GRU)是在LSTM的基础上省略了一个门，并将单元状态与输出状态合并为一个ht，使得结构得以简化，参数量变小。 [19] 比较了RNN、LSTM、GRU的记忆能力，并提出了一个记忆能力更强的ELSTM和一个性能优于BRNN和Seq2Seq的DBRNN模型。
LSTM在轨迹预测方面有了广泛地应用。[9] 运用RNN-LSTM的网络结构，将船舶的历史轨迹特征和当前轨迹特征作为网络的输入，输出未来某时刻船舶的轨迹特征，再与真实值相对比进行网络的训练，建立历史船舶轨迹与未来船舶轨迹特征数据之间的映射关系，并实现对未来轨迹特征的推算和预测，达到了很好的效果。[20] 提出了一个基于随机森林和MLP-LSTM的轨迹预测混合模型，先利用随机森林构成的移动状态预测组件来对运动状态进行预测，在用多层感知机来捕获轨迹数据中的局部特征，最后利用LSTM来获取轨迹数据中的时间依赖关系，解决了轨迹预测中关于静止轨迹数据预测误差大和提取轨迹数据中长时间依赖的问题。
3.3. Seq2Seq
Seq2Seq全称为Sequence to Sequence，是一个编码器——解码器结构的生成神经网络，它的输入是一个序列，输出也是一个序列。图4表示了Seq2Seq的基本结构，这里的每一个方块代表着一个RNN单元，通常是LSTM或者GRU。其过程就是，编码器将可变长度的序列如 {x1,x2,x3,x4}{x1,x2,x3,x4} 转变为固定长度的向量表达v，解码器将这个固定长度的向量v转换为可变长度的目标输出序列 {y1,y2,y3}{y1,y2,y3}。
图片
Figure 4. Structure of Seq2Seq model
图4. 序列到序列模型结构
然而，由于编码器将输入序列编码为固定大小的状态向量实际上是一个信息有损压缩的过程，如果信息量很大，压缩过程将造成大量信息丢失，同时解码器在解码这个固定长度的向量时也很难关注到输入信息的更多细节，所以注意力(Attention)概念的引入和双向编码器(Bidirectional encoder layer)的提出，使模型的性能大大提高。如Attention机制可以把输入序列根据时间步编码为不同的向量vi，在解码时，结合每个不同的vi进行解码输出，这样得到的结果会更加准确。 [13] 通过结合两种不同的Attention机制来预测行人轨迹。在目标行人轨迹上使用Soft Attention，即注意力不同程度的分散在轨迹的各个部分，而在周围行人的轨迹上使用Hardwired Attention，重点关注他与目标行人的距离，最后将某时刻各个Attention获得的信息想融合作为预测输入的一部分。
鉴于Seq2Seq模型有强大的获取序列数据间关系的能力，它已被用于很多轨迹数据挖掘任务。如 [21] 提出了基于Seq2Seq的模型用来学习轨迹特征，作为轨迹相似度计算的基础研究。[6] 提出了Dest-ResNet的序列学习模型，用来处理两种不同形式的序列数据，如交通速度序列和用户在特定时间段的查询请求序列，其中用到的Seq2Seq被用来完成未来一段时间的交通速度预测。
3.4. 卷积神经网络
卷积神经网络(Convolutional Neural Network, 缩写为CNN)是一类深度前馈神经网络，一般用于视觉图像领域。典型的CNN模型(如图5)通常包括输入层、卷积层、池化层和输出层。卷积层是用不同大小的卷积核来进行特征提取，池化层则通常用于在空间维度进行下采样，起到数据压缩、特征降维、降参的作用。同时在对图像处理时，卷积操作所获得的特征具有平移、缩放和旋转不变性，它的权值共享结构大幅度减少了参数，能有效降低深度网络模型的连接复杂度和训练难度。而如今，一些CNN已被证明对单变量时序数据的分类任务有很好的效果，如FCN、ResNet等。[22] 又提出了多变量卷积神经网络(MVCNN)对多变量时序数据进行分类并证明了其高性能。[23] 将轨迹位置数据转化为二维图像作为CNN的输入，利用CNN的卷积层和池化层获取图片中轨迹的不同尺度特征，再与轨迹的其他数据特征相融合进行分类预测，达到了很不错的预测效果。[24] 通过将原始轨迹序列转化为语义上重要的位置轨迹序列，研究评估了CNN结构在语义位置预测任务中的性能表现。
图片
Figure 5. Structure of basic CNN model
图5. 卷积神经网络模型基本结构
但试验也表明，若直接将一维时序数据作为卷积网络的输入来训练时很容易出现过拟合的现象，所以用验证集来适时地调整超参数是常用的方法。或者增大训练数据，因为深度学习的一个最大的特点就是，数据量越大效果越好。此外，对数据做变换如数据增强、数据归一化处理，手动进行特征选择、问题重构、算法上调优等方法都能对过拟合问题提供或多或少的帮助。
3.5. 自动编码机
自动编码机(Auto Encoder, 缩写为AE)是一类人工神经网络，能以一种非监督的模式学习到输入数据的有效特征。最简单的AE由一个输入层、一个隐藏层和一个输出层组成。输入层到隐藏层的映射关系可以看作一个编码的过程，将输入信息进行压缩表示，从隐藏层到输出层的过程相当与一个解码的过程，输出的结果其实是对输入信息的一个重构。作为一个有效的非监督的特征表达学习方式，AE多用于数据挖掘下采和机器学习的分类聚类任务中。而堆叠自动编码器(Stacked Auto Encoder)是逐层对输入数据进行处理，降维，特征提取，最终获得输入数据的高阶特征。图6展示了一个一层的AE模型结构。
图片
Figure 6. Structure of the one-layer Auto Encoder model
图6. 一层的自动编码器模型结构
由于很多网络都是从权重随机初始化开始的，这会使得训练不稳定。 [25] 提出用一个序列编码器(Sequence Auto Ncoder)作为LSTM网络的预训练算法，这个训练步骤中得到的参数作为有监督的训练模型LSTM的起点，发现LSTM的训练变得更稳定，泛化能力更强。[26] 通过测量“轨迹长度”学习到网络是如何将输入进行变换的，证明了低层网络权重的微小变化将随着网络的加深，影响是成指数倍放大的，所以优化低层网络的权重尤为重要。
4. 深度学习模型的选择和设计
当进行某一项轨迹数据挖掘任务时，涉及到的数据种类可能有很多，有的是时序数据，有的是文本，正如前文所述，RNN、LSTM、Seq2Seq、AE和它们相应的改进变体模型可以为时序数据提供较好的学习方法，而CNN则更偏向于视觉图片领域的特征学习。为完成数据挖掘任务，我们或者将不同的数据喂入不同的学习模型，再进行特征融合，或者将不同的数据先进行融合，再喂入同一个网络进行学习，如 [27] 用传统的方法先将来自雷达和ADS-B的数据用相同的模式进行匹配，删除冗余，最后合并，再进行轨迹预测任务。而在多源异构的大数据环境下，传统的方法很多时候并不适用，所以 [28] 提供了三类方法，即基于特征的数据融合，基于阶段的数据融合，还有基于语义的数据融合，这需要具体问题具体分析。如基于特征的融合方式有 [8] 和 [29]，其中 [8] 将文本数据预处理之后喂入CNN，同时将轨迹、天气等时序数据喂入LSTM，他们得到的特征编码再融合进行出租车需求预测；[29] 也是首先通过不同的特征提取方式获得来自不同数据源的信息，再投入一个深度堆栈自动编码器得到最终的特征表达，最后通过多层感知器来进行出行时间的预测。而 [30] 则是进一步概述了基于深度学习模型的城市大数据融合，分为早期(输入阶段)数据融合、晚期(输出阶段)数据融合和双阶段(输入阶段和输出阶段)数据融合，即是基于阶段的数据融合。
另一方面，一些数据挖掘聚类分类算法与深度学习框架融合使用时，除了常用的K-means和DBSCAN，还可以考虑使用高斯混合模型，尤其当网络的输出有多种可能时，我们可以学习到每个高斯分布的均值、方差和混合系数，再通过采样来做最终的预测。如 [7] 就是通过LSTM和混合密度网络的结合，来预测不同地区的出租车需求。
轨迹数据是典型的时序数据，它的最大特征是数据之间在时间维度上是相互关联的，根据 [31] 提出的趋势分离方法，我们可以先把这种时间相关性消除，可以让网络学习到更多甚至被隐藏的特征， [8] 就是利用此方法先获取轨迹中的运动特征，便可将LSTM替换成全连接网络，最后的预测效果也不错。
有时，为了提高轨迹挖掘任务的精度等评价指标，不仅可以通过改进神经网络的结构、修改算法、提出新的训练方式等，还可以根据具体的情况提出特殊的损失函数等。如 [21] 为了学习连续的表示特征，提出了一个新的空间距离意识损失函数和一个细胞表示特征学习方法，将他们一起融入深度学习模型中,同时为了加速训练，还提出了一个基于噪声对比估计的近似损失函数。
5. 总结与展望
本文通过对轨迹数据和已经研究过的轨迹数据应用进行阐述和总结，并对应用在轨迹数据挖掘中的深度学习模型进行分析和讨论，总结了一些方法和技巧。实际上还有很多本文没有提到的轨迹挖掘任务和深度学习方法，包括频率模式挖掘、关系挖掘任务等。还有对抗生成网络模型也是深度学习方法中有待研究的热点之一，它已经在图像生成的试验中得到了不错的效果，将其应用在轨迹生成的问题上也会是未来研究的方向之一。此外，给网络提供参数初始化的方法除了AE还有受限玻尔兹曼机(Restricted Boltzmann Machine)，都是未来可以尝试的方法。最后，以上对轨迹数据的研究都只考虑了数据在时间维度上的依赖特性，而从空间维度或者同时考虑时空维度进行特征学习也可以作为未来的研究点。
关注微信公众号：人工智能技术与咨询。了解更多咨询！
| |
