基于编码器-解码器模型的人群移动预测分析

陈建伟 李建波

(青岛大学计算机科学技术学院 山东 青岛 266071)

0 引 言

如今，许多移动设备如手机和智能手环已成为人们出门必备的物品。这些设备往往内置GPS，可以实时检测人的位置。因此，人们的运动轨迹可以轻松获得，从而为探索人类的移动规律带来可能。此外，人类移动规律性的探索一直是自然、社会等领域长期以来的研究热点[1-2]。该研究对疾病传播、交通流量控制有很大影响，它可以帮助解决很多城市问题，如避免交通堵塞、预防疾病等。

本文通过分析人类移动模式，预测人群未来轨迹。现有的人群轨迹预测任务主要面临两个问题，一个是数据的稀疏性；另一个是冗长的历史轨迹。其中数据的稀疏性表现在两个方面：(1)人们的轨迹从现实世界中获取，由于人类移动的不确定性和个人隐私问题，收集的数据量通常比较稀疏；(2)每个人的轨迹记录的时间间隔在稀疏的数据中的分布也不均匀，这导致了轨迹的碎片化，加重了数据稀疏性的问题。而冗长的历史轨迹表现为：收集的每个用户的全部轨迹往往很冗长，这为寻找有价值的移动轨迹增加了难度。总的来说，以上的两个问题使得预测任务更加困难。

人的移动轨迹本质上是一个空间分布的时间序列数据，早期RNN被提出用来处理时间序列数据，却容易出现长输入导致的梯度消失问题。LSTM的提出改善了这一问题，其通过门控制结构来处理长输入并且表现优异。直观地，单一的LSTM网络可以直接用来处理轨迹预测问题，然而却不是有效的。首先，LSTM对于过长的输入依然有着遗忘的问题[3]，冗长的移动轨迹使得单一的LSTM难以捕捉顺序转换规律。其次，数据的稀疏性也使得单一的LSTM更难以处理预测任务。这表现在稀疏的特征和丢失的数据使得LSTM难以训练。另外，LSTM网络由于过长的输入丢失数据的长期依赖关系，导致无法捕捉轨迹的历史移动模式。

为了解决上述问题，本文提出一个基于LSTM的编码器-解码器模型。具体地，本文将用户的轨迹划分成历史轨迹和当前轨迹，随后一个嵌入矩阵被用来处理轨迹的稀疏性。被嵌入的历史轨迹输入到编码器中，得到语义向量和隐藏状态。继而，解码器的输入为来自编码器的输出和被嵌入的当前轨迹，最后生成用户未来轨迹。针对长历史轨迹，本文使用数据逆置和双向长短期神经网络作为编码器的两个方法，有效地缓解了LSTM对于早期轨迹遗忘的问题。

1 相关工作

虽然人类行为的预测有局限性，但Song等[4]发现了93%的潜在可预测性。在此基础上，许多研究者探索人类移动模式和预测人类移动性。如文献[5-6]通过数据挖掘探索了人类移动模式。具体地，Marta等[5]发现人类轨迹显示出高度的时间和空间规律性，每个人都有很大概率访问常去的地点，且每个人的移动距离与时间无关。随后，文献[7-8]提出了与移动模式结合来预测人类的移动性的方法，其中文献[7]通过当前观察的历史移动模式提出了一个高斯混合模型来计算未来移动地点的概率。与以上方法相比，本文模型可以在训练过程中学习用户之间的移动模式。

以上方法都取得了良好的结果，但预先定义的模式往往不能表达用户移动轨迹的顺序转换规律，因此后来的研究者们建立模型预测人类的移动性。如马尔可夫链模型是一种经典的统计模型，但此方法仅考虑上一步的状态，这使得其难以捕获到复杂的顺序转换规律。随后，文献[9]提出了隐马尔可夫模型(HMM)来与隐藏的未知状态结合，从而改进马尔可夫模型。虽然HMM表现优异，但其忽略了轨迹的时间依赖关系。随着深度学习技术的兴起，RNN被用来捕捉时间依赖关系并预测用户移动轨迹[10-12]。Liu等[10]提出了ST-RNN，并对轨迹局部时间和空间上下文进行建模。Yao等[11]提出了一个结合了语义信息的LSTM神经网络。与以上方法相比，本文模型同时考虑历史轨迹和当前轨迹来预测未来轨迹，且限制了当前轨迹的长度，使得预测精度得以提升。

编码器-解码器模型率先由文献[13]提出，且已经在轨迹预测的很多领域中取得优异表现。Park等[14]提出基于编码器-解码器的车辆轨迹预测技术，该技术可以实时生成周围车辆的未来轨迹序列。Nguyen等[15]提出了一种序列到序列模型，根据历史路线预测船舶的下一个位置。Feng等[16]提出了注意力机制循环神经网络来捕捉历史轨迹的多层周期性。本文工作与文献[14-15]思路有相似之处，与文献[16]相比，改进了模型结构，提高了预测精度。

2 移动轨迹问题的LSTM模型

2.1 问题定义

本文首先收集每个用户的移动轨迹，轨迹全部按照时间顺序排列。因此，用户ux轨迹定义为:

(1)

2.2 RNN和LSTM

神经网络(NN)由大量相互连接的节点组成，它本身是表示数据关系的近似函数。此外，NN经常处理的任务大致分为分类和回归问题，可以通过各种结构来解决不同的问题。NN中最常见的网络结构是擅长处理图像的卷积神经网络(CNN)和擅长处理时间序列的RNN。

在标准RNN结构中，隐藏层中的神经元建立权重连接，因此RNN拥有“记忆”。但是当序列太长时，早期的输入对后来的输入影响较小，这导致了梯度消失问题。为了解决这个问题，RNN的变体LSTM和GRU被提出。现在，LSTM被广泛用于长输入问题。本文模型基于LSTM结构，式(2)-式(7)描述了LSTM的工作原理：

it=σ(Wii×xt+bii+Whi×ht-1+bhi)

(2)

ft=σ(Wif×xt+bif+Whf×ht-1+bhf)

(3)

gt=tanh(Wig×xt+big+Whg×ht-1+bhg)

(4)

ot=σ(Wio×xt+bio+Who×ht-1+bho)

(5)

ct=ft×ct-1+it×gt

(6)

ht=ot⊙tanh(ct)

(7)

式中：Wii、Whi、Wif、Whf、Wig、Whg、Wio、Who是各个控制门的权重矩阵；b为偏置向量，ct是t时刻存储在神经元中的值；ht是隐藏层在t时刻的输出；⊙表示点积。

3 基于编码器-解码器的位置预测模型

3.1 模型结构

编码器-解码器模型[13]最先应用于自然语言处理的问题上，如机器翻译。在机器翻译中，一种语言被翻译成另一种语言，两种语言的长度通常不同。而传统的RNN模型的输入和输出长度相同，因此限制了翻译的准确性。随后，编码器-解码器模型被提出。该模型由两个单独的RNN组成，分别称为编码器和解码器，其工作机制是首先通过编码器对源输入进行编码并且获得语义向量，接下来语义向量作为编码器和解码器的连接，最后通过解码器分析语义向量并且预测目标语言。

在本文模型中，如图1所示，给出一个序列对(x1,x2,…,xt)和(y1,y2,…,yτ)，其中t和τ不一定相等。通过式(2)到式(7)，编码器处理输入(x1,x2,…,xt)。经过t个时间步的处理，编码器产生最终的语义向量ct。ct的计算过程可以表示为：

图1 编码器-解码器模型

ct=f(xt,ct-1)

(8)

式中：f为编码器的运行函数, 具体地，f是式(2)到式(6)的整合表示。随后，它作为解码器的输入。解码步骤为由xt作为初始的输入，在随后的τ个时间步中生成(y1,y2,…,yτ)。基于LSTM的编码器-解码器模型的目标是通过编码器生成的语义向量ct计算输出序列的条件概率p(y1,y2,…,yτ|x1,x2,…,xt)，该条件概率可以表示为：

(9)

由于本文使用xt作为解码器的初始输入，p(y1)的计算过程如下：

p(y1)=z(ct,xt)

(10)

式中：z是解码器的运行函数，同理z也是式(2)到式(6)的整合表示。为了与编码器区分，此处使用了符号z。

两个LSTM网络分别在本文的模型中用作编码器和解码器，如图1所示，编码器首先对用户的历史轨迹进行编码并生成语义向量(Context)。注意到语义向量的大小由隐藏层的大小决定，因此语义向量的大小保持固定。随后，解码器对语义向量进行解码。最后从当前轨迹中预测未来的轨迹。更清楚地来解释，假设用户的历史轨迹是(x1,x2,x3,x4,x5)，当前轨迹是(y1,y2,y3),将历史轨迹作为编码器的输入，获得编码器最后一个时间步的隐藏状态和Context。然后将编码器的最后时刻的隐藏状态作为解码器的初始状态，并将历史轨迹的最后一个地点x5作为解码器的初始输入。在解码器中，每更新一个时间步，将语义向量用作当前位置的参考向量。最后，将y3输入解码器来预测下一个地点y4。以上是模型的核心工作流程，更具体地，每个地点首先通过嵌入网络层来将稀疏的特征(如地点标识、时间)表示为密集矩阵。嵌入层使用非常广泛，在语义表达方面表现良好[17]。随后，将一个完全连接层添加到解码器的输出层。最后，本文加入Softmax层根据上一层的输出计算预测地点的概率分布。完整的网络结构如图2所示。

图2 预测模型整体结构

3.2 训练集准备

在3.1节中，注意到编码器-解码器模型使用的训练集是序列对。为了方便训练，本文制作了相似的训练集。

制作此训练集的方法是：分割每个用户的全部轨迹为多个子轨迹；划分子轨迹们为历史轨迹和当前轨迹。示例描述如下：假设用户u1有10个子轨迹，那么首先第一个子轨迹作为该用户的历史轨迹，而第二个子轨迹作为当前轨迹，要预测的目标地点是当前轨迹的最后一个地点。随后，将该用户的第一个和第二个子轨迹作为历史轨迹，第三个子轨迹为当前轨迹。因此对于u1，可以生成9个数据对样本。本文对其他用户使用相同的方法，生成所有的训练集。

3.3 新的问题

3.2节的训练集的制作方法会导致长历史轨迹的问题。即使LSTM擅长处理长输入问题，神经元存储的“记忆”也会因输入过长而消失。因此，Feng等[16]提出将注意力机制添加到模型中以计算历史轨迹与当前轨迹的关联，这在一定程度上解决了长轨迹的问题。然而，新增加的注意力机制在训练过程中计算当前解码器的输入和编码器的所有输出之间的概率分布，这浪费了很多时间。此外，基于现有的两个网络添加这种机制会增加参数数量，使训练更加困难。

3.4 改进方法

先前的研究者们提出了许多方法解决过长的输入带来的问题[18]，本文使用两种方法来提高预测的准确性。具体地，从数据和模型两个方面来改进。在数据方面，参考文献[19]中逆置数据的方法，这不仅没有降低精度，反而提高了预测的准确性。例如，如果原始训练集是(x1,x2,x3,x4,x5)和(y1,y2,y3)，将逆置的数据输入到编码器中，并且目标数据不变，即新的训练集为(x5,x4,x3,x2,x1)和(y1,y2,y3)。分析认为，逆置的数据使x1更接近y1，从而使其他位置相对而言更接近目标位置。在模型方面，由于注意到编码器可以通过逆置数据来学习早期的历史数据，从而减轻了早期遗忘的问题。因此，本文使用BiLSTM(Bidirectional LSTM)-LSTM结构，即编码器基于BiLSTM结构。如上所述，过长的输入限制了LSTM的能力，因此编码器的语义信息不能保存历史轨迹的完整信息。根据数据的改进方法，逆置的历史轨迹提升了预测精度。因此，正向的历史轨迹和反向的轨迹可以一起丰富语义信息。很方便地，本文采用了BiLSTM结构作为编码器来实现这种想法。改进模型如图3所示，在编码器中，c1(x1,xn)和c2(xn,x1)分别是编码器的前向传播过程和后向传播过程的神经元向量。并且，本文提出使用c1和c2的简单加法作为更新后的参考语义向量，解码器的初始状态是前向传播的隐藏状态h1(x1,xn)。

4 实 验

4.1 数据集

本文使用三个不同的数据集，分别是Foursquare 2010、Foursquare 2012和Gowalla。Foursquare 2010数据集来自文献[16]，Foursquare 2012[20]数据集是Foursquare于2012年4月12日至2013年2月16日在纽约市收集的长期真实签到数据。Gowalla[21]和Foursquare都是基于用户位置信息的服务机构，它们鼓励用户与他人共享有关其当前位置的信息。数据格式如下：用户ID；地点ID；类别ID；类别名称；经度；纬度；时间。数据集的信息如表1所示。

表1 数据集信息

对于每一个数据集，本文都使用各个用户80%的数据作为训练集，20%的数据作为测试集。

4.2 实验平台

本文提出的神经网络模型以及比较的所有神经网络都基于Pytorch平台运行，且使用了一个Nvidia GTX1080Ti GPU来加速训练。

4.3 评价指标和参数设置

为了公平比较，本文使用了精确度Top@k、召回率Recall、F1分数(F1-score)和负对数似然Negative Log-Likelihood (NLL)来评价模型，其中NLL从损失函数角度来评价真实地点的分布和预测地点的分布之间的可能性。Recall和F1是分类问题中常用的两个评价指标，Top@k可以描述为预测结果中前k个最高概率结果的准确率，定义l*(m)为输入m的真实结果，Lk(m)为前k个预测的列表，那么Top@k可以描述为：

(11)

本文的对比模型包括传统方法和几个最近被提出的深度学习方法，包括：Markov模型；单个RNN神经网络(simple_rnn)：以LSTM为默认结构，用户的全部轨迹作为该神经网络的输入；SERM[11]：Yao等提出的一个结合了语义信息的循环神经网络；DeepMove[16]：Feng等提出了一个注意力机制考虑历史轨迹的多层周期性。为了方便表示，本文初始模型表示为LSTM-LSTM，数据改进方法表示为data_reverse，模型改进方法表示为BLSTM-LSTM。不失一般性，每个模型都试验了3次并取其中的最大值比较。

本文的模型由两个LSTM组成，因此需要设置每个神经网络。具体地，首先设置两个LSTM网络都为1层。并且，使两个LSTM隐藏层的大小相同，这可以使解码器更方便地处理编码器的输出。随后，由于数据的稀疏性，本文在每个地点进入模型之前使用嵌入层嵌入，嵌入层的维度与两个LSTM隐藏层的大小相同。由于本文将该预测问题看作一个分类问题，因此使用了NLLLoss计算真实地点和预测地点之间的误差，最后使用Adam[22]算法作为优化器。由于各个数据集参数都不相同，本文给出各个数据集的参数设置如表2所示。

表2 各个数据集使用的模型参数

4.4 结果分析

在Foursquare的两个数据集上,各模型的Top@k结果如图4和图5所示，LSTM-LSTM结构与传统方法Markov和简单的深度学习方法simple_rnn进行比较，可以看到Markov的性能最差，因为它的结构特点是下一个预测的地点只与前一个地点有关。simple_rnn由于其对过去位置的记忆而具有更好的性能。LSTM-LSTM结构限制了各个子轨迹的长度，使得LSTM能力没有受到限制，因此性能表现最好。此外，LSTM-LSTM结构同时考虑历史轨迹和当前轨迹，有效地减弱了长历史轨迹造成的影响。在Foursquare2010和Foursquare2012两个数据集上，BiLSTM-LSTM结构的Top@1精确度比simple_rnn分别提升31%和33%，Top@5精确度比simple_rnn分别提升33%和33%。

图4 各个模型在Foursquare 2010上的Top@k结果

图5 各个模型在Foursquare 2012上的Top@k结果

本文的改进方法与SERM和DeepMove两个深度学习方法对比，可以看到SERM仅在Top@5结果上优于simple_rnn，但由于长历史轨迹使得LSTM能力受到限制，因此导致Top@1结果与simple_rnn几乎相同。DeepMove相比SERM在两个数据集上表现优异,但没有超过data_reverse方法和BLSTM-LSTM方法，这验证了数据逆置以及改进模型对预测的有效性。BiLSTM-LSTM结构相比DeepMove在两个数据集上的提升效果分别为Top@1:7%和9%；Top@5:12%和9%。分析认为，本文的改进模型相较DeepMove取得更好的效果。原因在于模型更加简洁，这使得训练起来更加容易；编码器-解码器的连接方式，历史轨迹的最后一个地点作为解码器的初始输入；编码器的改进增加了语义向量的参考信息，同时考虑了未来和过去的轨迹的影响，使得解码器预测未来轨迹更加准确。

在Gowalla数据集上，实验结果如图6所示，可以得出与Foursquare两个数据集上相同的结论。DeepMove相比简单的模型有着更好的表现效果，而本文的改进方法相比DeepMove有了一定的提升。BLSTM-LSTM结构在Gowalla数据集上相比DeepMove的提升效果为Top@1:9%；Top@5：11%。此外，本文还比较了两个改进方法的Recall、F1分数和NLL在各个数据集上的表现，结果如表3所示。可以看出，BiLSTM-LSTM结构的Recall和F1分数都是最高的，这表明了其分类结果的准确性最好。此外，BiLSTM-LSTM结构的NLL值最低，也从损失函数的角度说明了本文模型预测的准确性。

图6 各个模型在Gowalla上的Top@k结果

表3 各个数据集在其他指标上的表现

续表3

由于本文数据集为多用户数据集，本文模型对每个用户预测未来轨迹并得到其预测精度。本文选用最重要的实验指标Top@1生成所有用户预测结果数据，随后介绍其统计意义上的合理性。如图7所示，本文比较了改进模型BiLSTM-LSTM和DeepMove箱形图上的结果。可以看到，本文改进模型总体Top@1结果优于对比模型。本文模型的下四分位线高于DeepMove模型，表示本文模型可预测的用户数相对更多。此外本文模型异常值相比DeepMove也更多，这表明本文模型高准确率用户的数量增加，同时通过中位数的位置也验证了本文模型总体结果优于对比模型。紧接着，本文使用t检验验证了两组预测结果的差异性。其中t值为-2.585表明DeepMove模型多用户预测均值小于本文模型，p值为0.01表明有95%的概率假设两组预测结果在统计意义上有显著的差异。为了更清楚地表示p值变化规律，本文绘制了p值随用户数增加的变化图。如图8所示，从两条曲线交叉点可以得到，当用户数大于700左右时，p值小于0.05。通过以上结果可以得到，两组预测结果在均值上差异是显著的，从统计意义上解释了结果的合理性。

图7 BiLSTM-LSTM与DeepMove箱形图对比

图8 p值变化曲线

本文还对比了各个模型的运行效率，如图9所示。可以看出本文改进模型BiLSTM-LSTM最先收敛，且整体预测精度优于改进方法和对比模型，而DeepMove收敛最慢，且耗时最长。这主要是因为该模型结构复杂，难以训练。本文模型及其改进方法在前10个epoch中收敛都比较快，而后预测精度都趋于稳定，这主要是本文模型结构简单且易于训练的结果。

图9 各个模型的收敛曲线

5 结 语

本文的主要贡献如下：

(1) 提出一个基于编码器-解码器的轨迹预测模型，该模型同时考虑历史轨迹和当前轨迹，通过限制当前轨迹的长度，可以有效提高预测精确度。

(2) 针对冗长的历史轨迹改进了编码器的结构，即使用BLSTM结构。该结构有效地丰富了历史信息，通过正向传播考虑移动轨迹的顺序转换规律和时间依赖性关系，通过反向传播考虑未来轨迹对当前和过去轨迹造成的影响，有效地丰富了解码器的参考语义向量。

(3) 在两种测试数据集和一个世界真实数据集上实验，并与传统方法和几个近年被提出的深度学习方法相比，结果显示本文模型更有效。

本文通过用户历史轨迹预测未来的轨迹。但是，数据集的稀疏性和过长的轨迹导致预测准确性比较差。因此，本文将用户全部轨迹划分为历史轨迹和当前轨迹，并且使用编码器-解码器模型来解决这个问题。对于过长的轨迹，本文使用数据逆置和BiLSTM-LSTM结构来缓解早期遗忘的问题。与传统的预测方法和近年被提出的深度学习方法相比，本文方法显示出更好的结果。本文方法仍有许多不足，如数据的特征过少，只靠嵌入矩阵还远远不够，未来会加入语义信息如兴趣点等来丰富数据的特征。