JUST技术：基于注意力机制恢复细粒度轨迹

2021-03-05 00:00:00

随着基于位置服务的大量增长，越来越多的移动数据可以被分析挖掘，以更好地服务人们的生活。然而，与来自出租车等运输系统类的高采样率轨迹数据相比，用户地理服务数据具有严重稀疏性问题，是因为用户不会一直访问移动数据并贡献自己的位置信息（例如微博地址分享，大众点评签到等数据），而数据稀疏性问题不可避免的削弱了其实用价值。如何解决用户移动数据稀疏性，是一个非常具有挑战的问题。

本文将介绍清华大学发表在AAAI 2021上的论文《AttnMove: History Enhanced Trajectory Recovery via AttentionalNetwork》。该论文提出了一种基于注意力机制的神经网络结构，通过生成未观察到的位置信息以恢复用户细粒度的轨迹，进而更好地为后续应用提供支持和帮助。

一、问题背景

在大数据时代，分析挖掘用户位置数据为人们的生产生活带来非常多的便捷，如用户兴趣点推荐、城市交通流量预测、广告位投放选址等，这些应用场景以细粒度的用户移动数据为重要基础。然而由于隐私问题等方面的考虑，很多用户不会分享自己的位置信息，进而影响后续应用的分析挖掘。例如，利用有限的位置信息数据，研究人员很难去高质量地预测用户下一次出现的位置以及感兴趣的地点。此外，大量的稀疏位置数据也使得研究人员很难做细粒度的流量监测。因此，将用户稀疏的轨迹数据恢复至细粒度的轨迹数据是十分重要的。然而恢复稀疏轨迹数据至细粒度轨迹数据是非常困难的：1）已观察到的用户位置数据十分稀疏，使得未观察到的用户位置存在较多的不确定性；2）真实数据中存在大量噪声，如何有效的挖掘周期性规律存在一定困难；3）经常在历史轨迹中被访问的地点并不一定会是目标时间窗缺失的地点，如何利用用户历史上的位置数据是另一个挑战。为此，本文提出了一个基于注意力机制的神经网络结构AttnMove用以恢复用户的移动位置。AttnMove主要从以下三个方面着手解决数据稀疏问题：1）首先为了获取用户移动特征及推测缺失数据中最有可能访问的地点，本文利用轨迹内注意力机制设计了一个当前处理器用以初步填补缺失位置；2）其次，本文利用另一个轨迹内注意力机制设计了一个历史处理器用以挖掘不同的历史轨迹的周期性特征；3）最后，为了融合当前处理器以及历史处理器提取出来的特征并预测用户缺失地点，本文提出了一个基于轨迹间注意力及地点生成注意力机制的轨迹恢复模块，具体来说，轨迹间注意力机制用于生成历史轨迹对于当前移动状态影响的权重，地点生成注意力机制用于考虑时空约束，以此来更好地重建轨迹。

二、问题定义

本文定义一条轨迹为一个用户一天内按时间顺序的活动位置序列

，其中

表示用户u在第n天第t个时间间隙所处的位置，如果用户在t个时间间隙的位置信息未被观察到，则

为空，

为用户当前轨迹，

为用户u的历史轨迹。

在当前轨迹有大量缺失位置信息时，挖掘历史轨迹有助于恢复当前轨迹缺失信息。因此，本文将轨迹恢复问题定义为，给定一个用户当前轨迹及历史轨迹，恢复当前轨迹中的缺失位置信息，用以重建当前轨迹。

三、模型结构

为解决上述问题，本文提出AttnMove，图1展示其基本结构。首先为了更加有效地提取轨迹信息，AttnMove引用了轨迹嵌入模块用以预处理轨迹中的地点及时间信息，该模块是其他模块的基础。被嵌入模块处理过后的历史轨迹会被输入至历史处理器，经过嵌入模块处理的当前轨迹会进入当前处理器。而后，轨迹恢复模块会将二者的特征融合，用以恢复当前轨迹的完整位置。下文将对每个部分逐一展开介绍。

图1 模型结构示意图

1、轨迹嵌入模块

为了表示轨迹的时空属性，本文将轨迹中的时间与位置信息映射至低维嵌入层，并将此嵌入层作为其他模块的输入。具体而言，对于每个位置

，本文设置了一个可学习的嵌入层向量，所有的位置嵌入层向量表示为矩阵

。对于每一个时间信息t，本文借鉴了《Attention is all you need》的思路，将所有的时间t依据下述公式做转换，

其中i表示第i个维度，d表示与位置信息嵌入层一样的维度。最后，将位置信息与时间信息结合，最终形成如下的嵌入层向量以表达轨迹信息：

2、历史处理器

当挖掘历史轨迹信息时，由于用户每一天生成的轨迹都是稀疏的，单纯使用一条轨迹信息往往无法很好地获取周期性特征。因此，本文设计了一个历史结合器，如公式（3）所示，

其中，表示提取该时间间隙中被访问频率最高的位置。而后，根据公式（2），轨迹

被映射成

（其中，每一个时间间隙会被映射至

）。至此，历史结合器可以在一定程度上减少数据稀疏性。然而用户极有可能在历史上同一个时间间隙不生成任何位置信息，这使得在使用历史结合器之后，仍会存在缺失位置。为此，本文设计了历史处理器注意力机制，意在填补缺失位置。

图2 注意力机制结构图

直觉上，缺失的位置信息可以由缺失值前后两个可观察到的位置信息决定，例如缺失值

最有可能是

和

的中间位置，然后现实中，人们不会遵循线性移动，这中间存在很多不确定性。因此，本文设计了如图2所示的多头注意力神经网络模型，进而更好地为轨迹中的位置建立时空关系。具体而言，本文定义时间间隙t与k在头h的关系如下：

其中，

是转移矩阵，<,>是内积。下一步，通过结合所有在其他时间间隙出现的位置，生成了时间间隙t的代表向量：

其中，

是另一个转移矩阵。而后，本文通过不同的组合，模拟不同的时空依赖并将它们定义如下：

其中，表示结合运算符，H表示头的数量。为保留原始位置表示，本文在网络中添加了标准残差连接：

其中，

表示投影矩阵以防止维度错乱。由此，历史轨迹

被更新至

。

3、当前处理器

本文意在填补当前轨迹的缺失位置信息。对于缺失的位置信息来说，用户在之前以及之后访问的位置是十分重要的，因为前后两者可以为缺失位置提供空间约束。然而，由于存在连续的缺失值，前后被访问的位置信息对于缺失值的约束较弱。因此，本文设计了当前轨迹内注意力机制，旨在加强已观察到的位置信息对未观察的位置信息的约束。具体实现过程，同上文的历史处理器类似，区别在于将历史轨迹替换成当前轨迹，本模块不再赘述。

4、轨迹恢复模块

在提取了历史轨迹与当前轨迹的特征之后，轨迹恢复的问题被转换为如何将历史轨迹生成的候选位置与当前轨迹插入的位置相结合。直觉上来讲，一个好的方法是将二者比较，而后选择相似的位置作为最终的填补值。为此，本文设计了一个轨迹间注意力机制以及地点生成注意力机制。设计轨迹间注意力机制的目的是为了融合历史轨迹及当前轨迹的信息，由此可以更好地生成缺失的位置信息。

四、实验结果

1、实验设定

为了验证模型的有效性，本文分别在Tencent及Geolife两个数据集上进行了实验。本文将北京地区划分成10655个格子，每个格子平均256平方米，每条轨迹的时间间隙设定为30分钟，表1为数据的基本情况：

表1

本文随机隐藏20%的位置信息作为恢复的基准真值，即随机隐藏当前轨迹中20%的位置信息。召回率（Recall）及全类平均正确率（Mean Average Precision）被用作验证指标，二者皆为越大越好。此外，距离也被用于评估模型效果，该指标越小表示预测位置与基准真值约接近。

2、结果分析

表2

表2展示了AttnMove与其他基线模型对比结果，其中加粗表示最好结果，下划线表示次好结果。可以明显地看出，AttnMove在大部分指标中表现优异，除了在Geolife数据集上的距离指标，这极有可能是因为Geolife是一个小的数据集，基于深度学习的模型无法表现优于线性模型。此外，与基于LSTM模型的DeepMove以及去掉历史处理器的Attn –H 对比可以看出，历史轨迹对于当前轨迹恢复有重要影响，历史轨迹可以帮助减少不确定性，提高轨迹恢复的准确性。