一种端到端的个体出行轨迹重识别的深度学习方法

陆家双 王斌 翟希

摘  要： 对于行人的再识别研究大多采用图像处理和计算机视觉领域的相关方法，在社会治安领域和商业领域内受到了越来越多的关注. 从信息检索的角度出发，提出了一种端到端的深度学习框架，对匿名化的基于位置的服务（LBS）数据进行用户再识别. 首先，该框架采用嵌入网络对输入的位置序列及其对应的时间序列进行编码;然后采用递归循环网络对用户每天的历史轨迹进行编码;随后连接注意力机制网络，对需要比较的两条轨迹进行重要权重计算;最后得出其相似度. 实验结果表明：相较于计算轨迹之间向量距离的传统方法，此模型考虑了用户的时空位置信息，可以更加准确地计算轨迹序列之间的相似度，在某城市匿名化的LBS数据集上，对不同数量的用户重识别准确率较高.

关键词： 轨迹重识别; 注意力机制网络; 深度学习

中图分类号： TP 399      文献标志码： A      文章编号： 1000-5137（2021）01-0115-07

Abstract： A large number of researches on pedestrian re-identification based on the methods of image processing and computer vision were getting more and more attention in the field of social security and business. From the perspective of information retrieval，an end-to-end deep learning framework was proposed for user re-identification of anonymous location based services （LBS） data in this paper. Firstly，the embedded network was used to encode the input spatial sequence and the corresponding temporal sequence. Secondly，the recurrent network was adopted to encode the users daily history trajectory. Thirdly，the attention mechanism network was connected to calculate the importance weight of the two trajectories to be compared，and finally the similarity of the two trajectories was obtained. The experimental results showed that this model was able to take the users spatial-temporal position information into account，and achieve more accurate similarity between trajectory sequences compared with the traditional method of calculating the vector distance between trajectories. The re-identification accuracy of different number of users on the anonymous LBS dataset of a city was significantly improved.

Key words： trajectory re-identification; attention-based network; deep learning

0  引言

隨着移动互联网技术的快速发展，便携式移动通信设备在人们日常生活和工作中的使用频率越来越高.同时，服务提供商为了实现更高的商业价值和更优的用户体验，都会要求用户在使用手机的应用软件时，开启定位权限，借此采集用户实际的地理位置进行数据挖掘工作，从而理解用户的行为模式，这些数据已被成功应用于商业、城市及交通规划等.而移动轨迹数据的大量应用，也带来了人们对数据隐私泄露的担忧，特别是使用个体轨迹数据可对用户进行再识别.

早期的研究证实4个时空点或者3个被用户经常访问的位置就可以再识别出城市中80%～95%的用户[1-2].WANG等[3]收集了多个服务性平台匿名化后的轨迹数据，研究了不同平台的用户再识别问题，提出了一种高斯混合模型逼近用户轨迹数据的概率密度函数，缺点在于不同的数据要确定不同的高斯函数阶数，而且没有考虑个体的出行方式和位置信息，导致其对个体隐私的保护不够充分.用户再识别可被定义为轨迹二分类的检索问题，传统的轨迹分类方法主要关注用户的行为模式和出行方式，并利用动态贝叶斯网络（DBN）、隐马尔可夫模型（HMM）和条件随机场（CRF）等技术，结合历史访问位置和序列模式解决类似问题.然而，这些方法只适用于特定的场景，在用户位置服务（LBS）数据集上表现效果相对较差.还有一些方法考虑了数据存在时间或者空间上的噪声问题，例如：NARAYANAN等[4]提出一种在时间不匹配的情况下匹配用户的方法;MA等[5]收集了基于位置的时空数据用于研究用户隐私保护，但仅考虑数据的空间不匹配问题，没有考虑时间不匹配问题;ROSSI等[6]使用基于位置的社交网络（LBSNs）数据，提出一种基于时空轨迹点的方法，只需考虑用户签入活动的空间坐标点轨迹，但该方法没有考虑时间信息，仅把用户在每个位置的签入频率作为特征，导致识别率较低.近年来，研究人员开始利用深度神经网络对时空数据进行数据挖掘和轨迹匹配，如FENG等[7]采用注意力机制循环网络预测行人的移动轨迹.

针对上述相关方法的不足，本文作者提出一种同时考虑时间和空间序列的深度学习框架.将城市划分成相同大小的网格，把采集的LBS数据空间坐标映射到对应的网格，同时把时刻映射到对应的时间间隔，通过数据预处理，获取匿名用户的网格ID序列（空间序列）和时间序列，把时间和空间序列的one-hot稀疏编码以嵌入的方式映射成密集编码，拼接传入递归循环网络，训练得到原始轨迹的特征向量，利用相互注意力机制对两条轨迹的特征向量进行相似度计算.该注意力机制网络可以加大不同轨迹之间的重要权重，找到隐藏于轨迹数据中的重要信息.在采集到的LBS数据集上进行仿真实验，结果表明，本算法对比其他算法表现最好.

1  模型和方法

1.1 LBS数据集

采用某城市的匿名化LBS数据，数据采集的时间段为2014年1月6—17日.由于周末交通状况与工作日之间存在较大差异且规律性较差，剔除周末数据，采样数据为10 d.每条记录包括匿名化后的用户编号和，其中，t表示时间lo表示经度;la表示纬度.图1为500个样本数据经归一化处理后在10 d内的移动轨迹.

1.2 问题描述

由于人们使用手机的频率不同，所采集到的位置序列数据中每个用户的记录点长短也不同.根据对原始数据的统计分析，平均每个人有365个记录点.由于处于工作地点或居住地，并且手机一直处于通信状态，部分用户在连续时间内采集到的多个记录点属于同一个网格.在匹配任务上，若记录点较为稀疏，则能够被参考的记录点较少，尤其是轨迹编码，会造成编码后的向量稀疏且混入较多噪声，使匹配工作变得较为困难.设为第用户，，表示待匹配的500个样本用户.表示采集到的记录点，其中，为网格编号，共39 050个;为采集的时间间隔点，将原始数据采集的时刻映射到间隔为1 h的时间轴上，所以=0，1，…，240，且;表示第个用户有个记录点的轨迹序列，表示第个记录点，.用变量表示2个轨迹是否属于同一个用户，定义如下：

（1）

解决类似问题的传统方法是计算两条轨迹的距离函数或者轨迹分布相似度[6，8-10].本研究不直接处理轨迹，首先利用深度学习模型，获取移动轨迹潜在的两个特征向量，然后计算它们之间的相似度.

1.3 网络模型

1.3.1 模型总览

目前，深度学习方法已经成功应用于不同的研究领域，而且这种端到端深度学习方法可以弥补传统算法无法捕捉时空轨迹点内部重要特征的不足，可用于处理用户重识别问题.深度学习模型的架构主要由嵌入网络、递归循环网络和注意力机制网络3个部分组成，下文将详细介绍每个网络的架构和功能.

1.3.2 嵌入网络

嵌入网络是对经过数据预处理得到的进行编码的网络，如图2所示.其中，代表训练样本数表示每条序列的个数;表示总的样本序列个数，类似于自然语言处理领域的词的个数，空间序列嵌入网络的随着用户数量的增加而增加，时间序列嵌入网络的保持不变;表示嵌入维度大小.首先对某个用户的轨迹中的每个记录点进行one-hot编码，此编码相对稀疏，而且会丢失原始轨迹的物理层信息.针对上述问题，采用灵活性比较高的线性嵌入网络，把稀疏的one-hot编码映射成密集矩阵向量.

位置编码在移动轨迹预测任务中是经常采用的方式[11]，目的是将物理空间的相邻位置嵌入到潜在高维的相邻空间.值得注意的是，该嵌入模块由网络权值共享，对两条输入到网络中的轨迹分别进行嵌入编码.这种共享机制保证了两条来自同一物理空间的轨迹可以投影到另一个相同的潜在空间.此外，参数共享嵌入網络大大降低了整个网络的参数个数.

1.3.3 递归循环网络

将嵌入层输出的位置编码序列输入到递归循环网络，再次编码.该网络的基本单元主要采用门控循环单元（GRU）.GRU是长短期记忆（LSTM）网络的一种拓展[12].结构上，GRU有2个门：重置门和更新门;LSTM有3个门：遗忘门、输入门和输出门.GRU直接将隐状态传给下一个单元，而LSTM则用记忆单元把隐状态包装起来，所以GRU的参数较少.性能上，GRU较LSTM更容易收敛.采用参数较少且易收敛的GRU作为循环编码的基本单元.

为了提高模型的识别能力，对递归循环网络采用了权值共享的策略，对不同的两条轨迹进行编码时，改变模型的参数，使模型更好地适应多个轨迹空间.递归循环网络后面连接的是maxpooling层，该网络层有两个功能：一是把不同长度的轨迹编码变成统一的长度;二是可以提取重要的特征.通过这个网络层后，可以得到原始轨迹的特征向量表示.

1.3.4 注意力机制网络

为了捕捉轨迹中更宏观的语义层信息，在输出两条轨迹相似度分数之前，采用注意力机制网络对其再次进行信息交互.该网络使来源于不同时间维度下的空间序列能够进行重要位置的权重相乘，从而更精确地度量不同轨迹的相似度.

首先将查询向量和原始轨迹的特征向量逐一进行相似度计算，常用的相似度计算有点积、拼接、感知机等;接着，使用softmax函数将这些权重归一化，得到向量;最后，将权重和相应的特征向量加权求和，其中，，为待学习的参数，分别表示点积、拼接、感知机的相似度计算函数;为softmax函数为第个需计算的特征向量为查询向量为最终输出.

传统的注意力机制的查询向量为原本轨迹的特征向量，即，不同于传统的注意力机制网络，本研究采用文献[13]中提到的相互注意力机制，查询向量取另外一条轨迹的特征向量中的某个向量，例如，A轨迹的特征向量为，B轨迹的特征向量为，在对轨迹A进行注意力计算时，查询向量可以取轨迹B中的向量，即.据此，可以在计算相似度分数之前连接两个轨迹，并找到它们的相关部分，把得到的轨迹特征向量进行连接，传入多层前馈网络计算相似度，相似度分数经sigmoid函数及交叉熵损失函数转化为输出结果：

2  实验

2.1 数据集构造

原始LBS数据的采样周期为10 d（不包括周末）的500个用户数据，将原始数据分为前一周和后一周构造训练集、验证集和测试集.例如在构造训练集时，对于用户，把前一周和后一周中某天的轨迹和属于的位置序列进行随机组合，并给定标签为1;为了增加模型的识别能力，在构造负样本时，组合共同经过某个位置的不同用户的移动轨迹，并给定标签为0.为了满足训练阶段二分类问题的样本平衡要求，对于每个正样本轨迹对，随机选择一个负样本轨迹对与之对应.验证集和测试集取训练集之外的用户，并且一个正样本对应31个负样本.在实验中，训练、验证和测试数据的比例为6∶1∶3.

2.2 训练过程

模型的超参数batch_size设置为64，drop_out为0.5，学习率为0.001.在训练的过程中如果损失值在3个时刻内不下降，学习率以10%的幅度逐步下降，目的是使模型尽可能找到全局最优点.空间序列的大小随着用户数目增加而变大，对其嵌入维度为100，时间序列大小为240;对其嵌入维度为10，隐层单元个数为200.

在训练阶段，为了增加模型的泛化能力，对构造好的数据集进行随机排序.采用precision、recall、F1-score、特征曲线所覆盖的区域面积（AUC）等指标衡量训练阶段模型的性能.precision表示实际两条轨迹属于同一用户占预测两条轨迹属于同一用户的比例;recall表示实际两条轨迹属于同一用户占预测正确数的比例，预测正确数包括预测两条轨迹属于同一用户和预测两条轨迹不属于同一用户;F1-score定义为precision和recall的调和平均数，取值范围为0～1，1代表模型输出最好.

在验证和测试阶段，采用acc，acc5，acc10等指标评价不同模型，acc，acc5，acc10分别表示匹配过程中的轨迹相似度得分排名为前1、前5、前10.比如测试时，逐个计算两条轨迹的得分，然后将得分排序，如果可以在前5中找到相对应的用户编号，则统计到acc5.一些传统的算法在上述3个指标的差距较为明显，比如文献[2，5，14]计算轨迹相似度的acc5，acc10较高，但acc的准确率明显下降，表明这些算法在城市LBS数据集上缺乏泛化性，无法准确地识别指定用户.

2.3 方法对比

第一种方法是Hist算法，NAINI等[15]采用一种直方图的形式得到呼叫详细记录（CDRs）数据、网站浏览数据和GPS轨迹数据的轨迹分布，用Kullback-Leibler （KL）散度衡量两条轨迹分布的相似度.

另外一种方法是在按照KNN算法执行聚类的同时，对不同的连续空间点个数进行聚类.该方法随着连续空间点的数目增加，精确度呈现下降趋势，表明在城市区域复杂的情况下，单点识别比多点识别准确率高.

将Hist，K最近邻（KNN）算法与本研究所提深度学习模型进行比较，实验结果如图3和表1所示.图3表明用户数目不同时，所提模型比Hist和KNN模型识别准确率高，如表1所示，所提模型的acc高于其他模型，但是acc5和acc10较差，其原因为：1） 在训练阶段，所提模型构造了大量的负样本，导致待识别的轨迹数较多;2） 所提模型的主要功能是重识别具体某个用户.

3  结论

针对基于个体移动轨迹的用户重识别问题，采用了一种端到端的深度学习框架，使用嵌入网络和递归结构网络对位置点和轨迹序列进行编码，用注意力机制计算两条轨迹向量的重要部分，得出更加精確的相似度得分.实验采用了复杂的城市LBS数据进行训练和测试，结果表明在用户数量不同的情况下，所提模型较其他模型的性能具备一定优势.所提模型不仅局限于行人重识别问题，也可以应用于其他场景，比如行人轨迹预测和各种网络服务的推荐系统.在未来的工作中，将尝试把模型扩展到不同的应用场景中，探究其在轨迹数据隐私保护及智慧城市应用中的潜在价值.

参考文献：

[1] DEMONTJOYEY A，HIDALGO C A，VERLEYSEN M，et al.Uniquein the crowd：the privacy bounds of human mobility [J].Scientific Reports，2013，3：1376.

[2] ZANG H，BOLOT J.Anonymization of location data does not work：a large-scale measurement study [C]//Proceedings of the 17th Annual International Conference on Mobile Computing and Networking.Las Vegas：ACM，2011：145-156.

[3] WANG H D，GAO C，LI Y，et al.De-anonymization of mobility trajectories：dissecting the gaps between the oryand practice [C]//The 25th Annual Network & Distributed System Security Symposium.San Diego：NDSS，2018：1-15.

[4] NARAYANAN A，SHMATIKOV V.Robust de-anonymization of large sparse data sets [C]//Proceedings of the IEEE Symposiumon Security and Privacy （SP）.Oakland：IEEE，2008：111-225.

[5] MA C Y T，YAU D K Y，YIP N K，et al.Privacy vulnerability of published anonymous mobility traces [J].Transactionson Networking，2013，21（3）：720-733.

[6] ROSSI L，MUSOLESI M.Its the way you check-in：identifyingusers in location-based social networks [C]//Proceedings of the second ACM Conference on Online Social Networks （COSN）.Dublin：ACM，2014：215-226.

[7] FENG J，LI Y，ZHANG C，et al.Deepmove：predicting human mobility with attentional recurrent networks [C]//Proceedings of the 2018 World Wide Web Conference.Lyon：ACM， 2018：1459-1468.

[8] RIEDERER C，KIM Y，CHAINTREAU A，et al.Linking users acrossdomains with location data：theory and validation [C]//Proceedings of the 25th International Conference on World Wide Web.Montréal：ACM，2016：707-719.

[9] MULDERY D，DANEZIS G，BATINA L，et al.Identification via location-profiling in GSM networks[C]//Proceedings of the 7th ACM Workshop on Privacy in the Electronic Society.Alexandria：ACM，2008：23-32.

[10] CECAJ A，MAMEI M，ZAMBONELLI F.Re-identification and information fusion between anonymized CDR and social network data [J].Journal of Ambient Intelligence & Humanized Computing，2016，7（1）：83-96.

[11] YAO D，ZHANG C，ZHU Z H，et al.Trajectory clustering via deep representation learning [C]//International Joint Conference on Neural Networks.Anchorage：IEEE，2017：3880-3887.

[12] CHO K，MERRIENBOER B V，GULCEHRE C，et al.Learning phrase representations using RNN encoder-decoder for statistical machine translation [C]//International Joint Conference on Neural Networks （IJCNN）.Anchorage：IEEE，2014：1-13.

[13] FENG J，ZHANG M Y，WANG H D，et al.DPLink：user identity linkage via deep neural network from heterogeneous mobility data [C]//The Web Conference. San Francisco：ACM，2019：459-469.

[14] SHOKRI R，THEODORAKOPOULOS G，LE BOUDEC J Y，et al.Quantifying location privacy [C]//Proceedings of the 2011 IEEE Symposium on Security and Privacy.Washington，DC：IEEE，2011：247-262.

[15] NAINI F M，UNNIKRISHNAN J，THIRAN P，et al.Where you are is who you are：user identification by matching statistics [J].IEEE Transactions on Information Forensics and Security （TIFS），2016，11（2）：358-372.

（責任编辑：包震宇）