一種端到端的個體出行軌跡重識別的深度學(xué)習(xí)方法

陸家雙 王斌 翟希

摘 ?要： 對于行人的再識別研究大多采用圖像處理和計(jì)算機(jī)視覺領(lǐng)域的相關(guān)方法，在社會治安領(lǐng)域和商業(yè)領(lǐng)域內(nèi)受到了越來越多的關(guān)注. 從信息檢索的角度出發(fā)，提出了一種端到端的深度學(xué)習(xí)框架，對匿名化的基于位置的服務(wù)（LBS）數(shù)據(jù)進(jìn)行用戶再識別. 首先，該框架采用嵌入網(wǎng)絡(luò)對輸入的位置序列及其對應(yīng)的時間序列進(jìn)行編碼;然后采用遞歸循環(huán)網(wǎng)絡(luò)對用戶每天的歷史軌跡進(jìn)行編碼;隨后連接注意力機(jī)制網(wǎng)絡(luò)，對需要比較的兩條軌跡進(jìn)行重要權(quán)重計(jì)算;最后得出其相似度. 實(shí)驗(yàn)結(jié)果表明：相較于計(jì)算軌跡之間向量距離的傳統(tǒng)方法，此模型考慮了用戶的時空位置信息，可以更加準(zhǔn)確地計(jì)算軌跡序列之間的相似度，在某城市匿名化的LBS數(shù)據(jù)集上，對不同數(shù)量的用戶重識別準(zhǔn)確率較高.

關(guān)鍵詞： 軌跡重識別; 注意力機(jī)制網(wǎng)絡(luò); 深度學(xué)習(xí)

中圖分類號： TP 399 ?????文獻(xiàn)標(biāo)志碼： 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 ?引言

隨著移動互聯(lián)網(wǎng)技術(shù)的快速發(fā)展，便攜式移動通信設(shè)備在人們?nèi)粘Ｉ詈凸ぷ髦械氖褂妙l率越來越高.同時，服務(wù)提供商為了實(shí)現(xiàn)更高的商業(yè)價(jià)值和更優(yōu)的用戶體驗(yàn)，都會要求用戶在使用手機(jī)的應(yīng)用軟件時，開啟定位權(quán)限，借此采集用戶實(shí)際的地理位置進(jìn)行數(shù)據(jù)挖掘工作，從而理解用戶的行為模式，這些數(shù)據(jù)已被成功應(yīng)用于商業(yè)、城市及交通規(guī)劃等.而移動軌跡數(shù)據(jù)的大量應(yīng)用，也帶來了人們對數(shù)據(jù)隱私泄露的擔(dān)憂，特別是使用個體軌跡數(shù)據(jù)可對用戶進(jìn)行再識別.

早期的研究證實(shí)4個時空點(diǎn)或者3個被用戶經(jīng)常訪問的位置就可以再識別出城市中80%～95%的用戶[1-2].WANG等[3]收集了多個服務(wù)性平臺匿名化后的軌跡數(shù)據(jù)，研究了不同平臺的用戶再識別問題，提出了一種高斯混合模型逼近用戶軌跡數(shù)據(jù)的概率密度函數(shù)，缺點(diǎn)在于不同的數(shù)據(jù)要確定不同的高斯函數(shù)階數(shù)，而且沒有考慮個體的出行方式和位置信息，導(dǎo)致其對個體隱私的保護(hù)不夠充分.用戶再識別可被定義為軌跡二分類的檢索問題，傳統(tǒng)的軌跡分類方法主要關(guān)注用戶的行為模式和出行方式，并利用動態(tài)貝葉斯網(wǎng)絡(luò)（DBN）、隱馬爾可夫模型（HMM）和條件隨機(jī)場（CRF）等技術(shù)，結(jié)合歷史訪問位置和序列模式解決類似問題.然而，這些方法只適用于特定的場景，在用戶位置服務(wù)（LBS）數(shù)據(jù)集上表現(xiàn)效果相對較差.還有一些方法考慮了數(shù)據(jù)存在時間或者空間上的噪聲問題，例如：NARAYANAN等[4]提出一種在時間不匹配的情況下匹配用戶的方法;MA等[5]收集了基于位置的時空數(shù)據(jù)用于研究用戶隱私保護(hù)，但僅考慮數(shù)據(jù)的空間不匹配問題，沒有考慮時間不匹配問題;ROSSI等[6]使用基于位置的社交網(wǎng)絡(luò)（LBSNs）數(shù)據(jù)，提出一種基于時空軌跡點(diǎn)的方法，只需考慮用戶簽入活動的空間坐標(biāo)點(diǎn)軌跡，但該方法沒有考慮時間信息，僅把用戶在每個位置的簽入頻率作為特征，導(dǎo)致識別率較低.近年來，研究人員開始利用深度神經(jīng)網(wǎng)絡(luò)對時空數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘和軌跡匹配，如FENG等[7]采用注意力機(jī)制循環(huán)網(wǎng)絡(luò)預(yù)測行人的移動軌跡.

針對上述相關(guān)方法的不足，本文作者提出一種同時考慮時間和空間序列的深度學(xué)習(xí)框架.將城市劃分成相同大小的網(wǎng)格，把采集的LBS數(shù)據(jù)空間坐標(biāo)映射到對應(yīng)的網(wǎng)格，同時把時刻映射到對應(yīng)的時間間隔，通過數(shù)據(jù)預(yù)處理，獲取匿名用戶的網(wǎng)格ID序列（空間序列）和時間序列，把時間和空間序列的one-hot稀疏編碼以嵌入的方式映射成密集編碼，拼接傳入遞歸循環(huán)網(wǎng)絡(luò)，訓(xùn)練得到原始軌跡的特征向量，利用相互注意力機(jī)制對兩條軌跡的特征向量進(jìn)行相似度計(jì)算.該注意力機(jī)制網(wǎng)絡(luò)可以加大不同軌跡之間的重要權(quán)重，找到隱藏于軌跡數(shù)據(jù)中的重要信息.在采集到的LBS數(shù)據(jù)集上進(jìn)行仿真實(shí)驗(yàn)，結(jié)果表明，本算法對比其他算法表現(xiàn)最好.

1 ?模型和方法

1.1 LBS數(shù)據(jù)集

采用某城市的匿名化LBS數(shù)據(jù)，數(shù)據(jù)采集的時間段為2014年1月6—17日.由于周末交通狀況與工作日之間存在較大差異且規(guī)律性較差，剔除周末數(shù)據(jù)，采樣數(shù)據(jù)為10 d.每條記錄包括匿名化后的用戶編號和，其中，t表示時間lo表示經(jīng)度;la表示緯度.圖1為500個樣本數(shù)據(jù)經(jīng)歸一化處理后在10 d內(nèi)的移動軌跡.

1.2 問題描述

由于人們使用手機(jī)的頻率不同，所采集到的位置序列數(shù)據(jù)中每個用戶的記錄點(diǎn)長短也不同.根據(jù)對原始數(shù)據(jù)的統(tǒng)計(jì)分析，平均每個人有365個記錄點(diǎn).由于處于工作地點(diǎn)或居住地，并且手機(jī)一直處于通信狀態(tài)，部分用戶在連續(xù)時間內(nèi)采集到的多個記錄點(diǎn)屬于同一個網(wǎng)格.在匹配任務(wù)上，若記錄點(diǎn)較為稀疏，則能夠被參考的記錄點(diǎn)較少，尤其是軌跡編碼，會造成編碼后的向量稀疏且混入較多噪聲，使匹配工作變得較為困難.設(shè)為第用戶，，表示待匹配的500個樣本用戶.表示采集到的記錄點(diǎn)，其中，為網(wǎng)格編號，共39 050個;為采集的時間間隔點(diǎn)，將原始數(shù)據(jù)采集的時刻映射到間隔為1 h的時間軸上，所以=0，1，…，240，且;表示第個用戶有個記錄點(diǎn)的軌跡序列，表示第個記錄點(diǎn)，.用變量表示2個軌跡是否屬于同一個用戶，定義如下：

（1）

解決類似問題的傳統(tǒng)方法是計(jì)算兩條軌跡的距離函數(shù)或者軌跡分布相似度[6，8-10].本研究不直接處理軌跡，首先利用深度學(xué)習(xí)模型，獲取移動軌跡潛在的兩個特征向量，然后計(jì)算它們之間的相似度.

1.3 網(wǎng)絡(luò)模型

1.3.1 模型總覽

目前，深度學(xué)習(xí)方法已經(jīng)成功應(yīng)用于不同的研究領(lǐng)域，而且這種端到端深度學(xué)習(xí)方法可以彌補(bǔ)傳統(tǒng)算法無法捕捉時空軌跡點(diǎn)內(nèi)部重要特征的不足，可用于處理用戶重識別問題.深度學(xué)習(xí)模型的架構(gòu)主要由嵌入網(wǎng)絡(luò)、遞歸循環(huán)網(wǎng)絡(luò)和注意力機(jī)制網(wǎng)絡(luò)3個部分組成，下文將詳細(xì)介紹每個網(wǎng)絡(luò)的架構(gòu)和功能.

1.3.2 嵌入網(wǎng)絡(luò)

嵌入網(wǎng)絡(luò)是對經(jīng)過數(shù)據(jù)預(yù)處理得到的進(jìn)行編碼的網(wǎng)絡(luò)，如圖2所示.其中，代表訓(xùn)練樣本數(shù)表示每條序列的個數(shù);表示總的樣本序列個數(shù)，類似于自然語言處理領(lǐng)域的詞的個數(shù)，空間序列嵌入網(wǎng)絡(luò)的隨著用戶數(shù)量的增加而增加，時間序列嵌入網(wǎng)絡(luò)的保持不變;表示嵌入維度大小.首先對某個用戶的軌跡中的每個記錄點(diǎn)進(jìn)行one-hot編碼，此編碼相對稀疏，而且會丟失原始軌跡的物理層信息.針對上述問題，采用靈活性比較高的線性嵌入網(wǎng)絡(luò)，把稀疏的one-hot編碼映射成密集矩陣向量.

位置編碼在移動軌跡預(yù)測任務(wù)中是經(jīng)常采用的方式[11]，目的是將物理空間的相鄰位置嵌入到潛在高維的相鄰空間.值得注意的是，該嵌入模塊由網(wǎng)絡(luò)權(quán)值共享，對兩條輸入到網(wǎng)絡(luò)中的軌跡分別進(jìn)行嵌入編碼.這種共享機(jī)制保證了兩條來自同一物理空間的軌跡可以投影到另一個相同的潛在空間.此外，參數(shù)共享嵌入網(wǎng)絡(luò)大大降低了整個網(wǎng)絡(luò)的參數(shù)個數(shù).

1.3.3 遞歸循環(huán)網(wǎng)絡(luò)

將嵌入層輸出的位置編碼序列輸入到遞歸循環(huán)網(wǎng)絡(luò)，再次編碼.該網(wǎng)絡(luò)的基本單元主要采用門控循環(huán)單元（GRU）.GRU是長短期記憶（LSTM）網(wǎng)絡(luò)的一種拓展[12].結(jié)構(gòu)上，GRU有2個門：重置門和更新門;LSTM有3個門：遺忘門、輸入門和輸出門.GRU直接將隱狀態(tài)傳給下一個單元，而LSTM則用記憶單元把隱狀態(tài)包裝起來，所以GRU的參數(shù)較少.性能上，GRU較LSTM更容易收斂.采用參數(shù)較少且易收斂的GRU作為循環(huán)編碼的基本單元.

為了提高模型的識別能力，對遞歸循環(huán)網(wǎng)絡(luò)采用了權(quán)值共享的策略，對不同的兩條軌跡進(jìn)行編碼時，改變模型的參數(shù)，使模型更好地適應(yīng)多個軌跡空間.遞歸循環(huán)網(wǎng)絡(luò)后面連接的是maxpooling層，該網(wǎng)絡(luò)層有兩個功能：一是把不同長度的軌跡編碼變成統(tǒng)一的長度;二是可以提取重要的特征.通過這個網(wǎng)絡(luò)層后，可以得到原始軌跡的特征向量表示.

1.3.4 注意力機(jī)制網(wǎng)絡(luò)

為了捕捉軌跡中更宏觀的語義層信息，在輸出兩條軌跡相似度分?jǐn)?shù)之前，采用注意力機(jī)制網(wǎng)絡(luò)對其再次進(jìn)行信息交互.該網(wǎng)絡(luò)使來源于不同時間維度下的空間序列能夠進(jìn)行重要位置的權(quán)重相乘，從而更精確地度量不同軌跡的相似度.

首先將查詢向量和原始軌跡的特征向量逐一進(jìn)行相似度計(jì)算，常用的相似度計(jì)算有點(diǎn)積、拼接、感知機(jī)等;接著，使用softmax函數(shù)將這些權(quán)重歸一化，得到向量;最后，將權(quán)重和相應(yīng)的特征向量加權(quán)求和，其中，，為待學(xué)習(xí)的參數(shù)，分別表示點(diǎn)積、拼接、感知機(jī)的相似度計(jì)算函數(shù);為softmax函數(shù)為第個需計(jì)算的特征向量為查詢向量為最終輸出.

傳統(tǒng)的注意力機(jī)制的查詢向量為原本軌跡的特征向量，即，不同于傳統(tǒng)的注意力機(jī)制網(wǎng)絡(luò)，本研究采用文獻(xiàn)[13]中提到的相互注意力機(jī)制，查詢向量取另外一條軌跡的特征向量中的某個向量，例如，A軌跡的特征向量為，B軌跡的特征向量為，在對軌跡A進(jìn)行注意力計(jì)算時，查詢向量可以取軌跡B中的向量，即.據(jù)此，可以在計(jì)算相似度分?jǐn)?shù)之前連接兩個軌跡，并找到它們的相關(guān)部分，把得到的軌跡特征向量進(jìn)行連接，傳入多層前饋網(wǎng)絡(luò)計(jì)算相似度，相似度分?jǐn)?shù)經(jīng)sigmoid函數(shù)及交叉熵?fù)p失函數(shù)轉(zhuǎn)化為輸出結(jié)果：

2 ?實(shí)驗(yàn)

2.1 數(shù)據(jù)集構(gòu)造

原始LBS數(shù)據(jù)的采樣周期為10 d（不包括周末）的500個用戶數(shù)據(jù)，將原始數(shù)據(jù)分為前一周和后一周構(gòu)造訓(xùn)練集、驗(yàn)證集和測試集.例如在構(gòu)造訓(xùn)練集時，對于用戶，把前一周和后一周中某天的軌跡和屬于的位置序列進(jìn)行隨機(jī)組合，并給定標(biāo)簽為1;為了增加模型的識別能力，在構(gòu)造負(fù)樣本時，組合共同經(jīng)過某個位置的不同用戶的移動軌跡，并給定標(biāo)簽為0.為了滿足訓(xùn)練階段二分類問題的樣本平衡要求，對于每個正樣本軌跡對，隨機(jī)選擇一個負(fù)樣本軌跡對與之對應(yīng).驗(yàn)證集和測試集取訓(xùn)練集之外的用戶，并且一個正樣本對應(yīng)31個負(fù)樣本.在實(shí)驗(yàn)中，訓(xùn)練、驗(yàn)證和測試數(shù)據(jù)的比例為6∶1∶3.

2.2 訓(xùn)練過程

模型的超參數(shù)batch_size設(shè)置為64，drop_out為0.5，學(xué)習(xí)率為0.001.在訓(xùn)練的過程中如果損失值在3個時刻內(nèi)不下降，學(xué)習(xí)率以10%的幅度逐步下降，目的是使模型盡可能找到全局最優(yōu)點(diǎn).空間序列的大小隨著用戶數(shù)目增加而變大，對其嵌入維度為100，時間序列大小為240;對其嵌入維度為10，隱層單元個數(shù)為200.

在訓(xùn)練階段，為了增加模型的泛化能力，對構(gòu)造好的數(shù)據(jù)集進(jìn)行隨機(jī)排序.采用precision、recall、F1-score、特征曲線所覆蓋的區(qū)域面積（AUC）等指標(biāo)衡量訓(xùn)練階段模型的性能.precision表示實(shí)際兩條軌跡屬于同一用戶占預(yù)測兩條軌跡屬于同一用戶的比例;recall表示實(shí)際兩條軌跡屬于同一用戶占預(yù)測正確數(shù)的比例，預(yù)測正確數(shù)包括預(yù)測兩條軌跡屬于同一用戶和預(yù)測兩條軌跡不屬于同一用戶;F1-score定義為precision和recall的調(diào)和平均數(shù)，取值范圍為0～1，1代表模型輸出最好.

在驗(yàn)證和測試階段，采用acc，acc5，acc10等指標(biāo)評價(jià)不同模型，acc，acc5，acc10分別表示匹配過程中的軌跡相似度得分排名為前1、前5、前10.比如測試時，逐個計(jì)算兩條軌跡的得分，然后將得分排序，如果可以在前5中找到相對應(yīng)的用戶編號，則統(tǒng)計(jì)到acc5.一些傳統(tǒng)的算法在上述3個指標(biāo)的差距較為明顯，比如文獻(xiàn)[2，5，14]計(jì)算軌跡相似度的acc5，acc10較高，但acc的準(zhǔn)確率明顯下降，表明這些算法在城市LBS數(shù)據(jù)集上缺乏泛化性，無法準(zhǔn)確地識別指定用戶.

2.3 方法對比

第一種方法是Hist算法，NAINI等[15]采用一種直方圖的形式得到呼叫詳細(xì)記錄（CDRs）數(shù)據(jù)、網(wǎng)站瀏覽數(shù)據(jù)和GPS軌跡數(shù)據(jù)的軌跡分布，用Kullback-Leibler （KL）散度衡量兩條軌跡分布的相似度.

另外一種方法是在按照KNN算法執(zhí)行聚類的同時，對不同的連續(xù)空間點(diǎn)個數(shù)進(jìn)行聚類.該方法隨著連續(xù)空間點(diǎn)的數(shù)目增加，精確度呈現(xiàn)下降趨勢，表明在城市區(qū)域復(fù)雜的情況下，單點(diǎn)識別比多點(diǎn)識別準(zhǔn)確率高.

將Hist，K最近鄰（KNN）算法與本研究所提深度學(xué)習(xí)模型進(jìn)行比較，實(shí)驗(yàn)結(jié)果如圖3和表1所示.圖3表明用戶數(shù)目不同時，所提模型比Hist和KNN模型識別準(zhǔn)確率高，如表1所示，所提模型的acc高于其他模型，但是acc5和acc10較差，其原因?yàn)椋?） 在訓(xùn)練階段，所提模型構(gòu)造了大量的負(fù)樣本，導(dǎo)致待識別的軌跡數(shù)較多;2） 所提模型的主要功能是重識別具體某個用戶.

3 ?結(jié)論

針對基于個體移動軌跡的用戶重識別問題，采用了一種端到端的深度學(xué)習(xí)框架，使用嵌入網(wǎng)絡(luò)和遞歸結(jié)構(gòu)網(wǎng)絡(luò)對位置點(diǎn)和軌跡序列進(jìn)行編碼，用注意力機(jī)制計(jì)算兩條軌跡向量的重要部分，得出更加精確的相似度得分.實(shí)驗(yàn)采用了復(fù)雜的城市LBS數(shù)據(jù)進(jìn)行訓(xùn)練和測試，結(jié)果表明在用戶數(shù)量不同的情況下，所提模型較其他模型的性能具備一定優(yōu)勢.所提模型不僅局限于行人重識別問題，也可以應(yīng)用于其他場景，比如行人軌跡預(yù)測和各種網(wǎng)絡(luò)服務(wù)的推薦系統(tǒng).在未來的工作中，將嘗試把模型擴(kuò)展到不同的應(yīng)用場景中，探究其在軌跡數(shù)據(jù)隱私保護(hù)及智慧城市應(yīng)用中的潛在價(jià)值.

參考文獻(xiàn)：

[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.

（責(zé)任編輯：包震宇）