一種端到端的個體出行軌跡重識別的深度學習方法

陸家雙 王斌 翟希

摘 ?要： 對于行人的再識別研究大多采用圖像處理和計算機視覺領域的相關方法，在社會治安領域和商業領域內受到了越來越多的關注. 從信息檢索的角度出發，提出了一種端到端的深度學習框架，對匿名化的基于位置的服務（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.

（責任編輯：包震宇）