基于深度學習的GPS軌跡去匿名研究*

卜冠華,周禮亮,李 昊,張 敏

(1.中國科學院軟件研究所可信計算與信息保障實驗室,北京 100089;2.中國科學院大學,北京 100089;3.中國電子科技集團公司航空電子信息系統技術重點實驗室，四川 成都 610036)

1 引言

移動互聯網和LBS(Location-Based Services)技術的高速發展使得位置服務提供商可以輕松收集到數十億用戶的位置軌跡信息。由于位置軌跡數據中包含用戶的大量隱私信息，惡意攻擊者可根據公開或非法獲取的位置軌跡數據集推測出如用戶身份標識等重要隱私。一旦軌跡數據對應的用戶身份泄露，用戶的生活周期、敏感位置等隱私也會隨之暴露，從而可能嚴重威脅用戶的人身和財產安全。為了保護位置軌跡中的用戶隱私，位置服務提供商通常會采取一定的匿名或假名替換方法[1,2]對發布數據進行處理。

然而，這些匿名或假名替換方法并不能阻止攻擊者對軌跡數據中潛藏的用戶移動行為進行建模分析。現有的基于軌跡顯式特征的相似度分析[3 - 8]，以及基于歷史軌跡構建的概率模型方法[9 - 13]都能不同程度地實現匿名后軌跡數據集的用戶身份重識別攻擊，從而威脅到用戶的個人隱私。最近，隨著深度學習技術的發展，已出現了一些以循環神經網絡RNN(Recurrent Neural Network)為代表的深度學習方法對軌跡數據集進行分析[14 - 19]。相比于前面2種方法，基于RNN的方法能夠提取出軌跡數據的顯式特征所不能表征的隱藏信息，同時不用對用戶移動行為的概率模型進行假設，從而在軌跡數據的用戶行為分析中具有更高的準確率。上述基于RNN的研究在具有語義信息的簽到數據集上有較好的效果，但是尚缺乏針對語義信息匱乏且位置點更加密集的GPS軌跡數據的匿名重識別研究。

針對上述問題，本文提出了一種基于神經網絡訓練的GPS軌跡去匿名方法，能夠從匿名GPS軌跡數據中識別出較為精準的用戶標識。為了能夠使稀疏的GPS位置點序列作為神經網絡的輸入，本文在預處理階段提出了一種針對GPS軌跡的數據預訓練方法，能夠將原始軌跡轉化為由位置點向量構成的序列，同時將位置點之間的序列依賴關系嵌入到位置點向量中。最后，基于真實的Geolife GPS軌跡數據集對本文的去匿名方法進行驗證。實驗表明，本文方法在GPS軌跡數據的匿名重識別上具有較好效果。

2 相關工作

早期的基于顯式特征的軌跡去匿名方法通常會采集軌跡中的空間距離和序列長度等特征，對軌跡之間的距離和相似度進行計算[3 - 5]。為了模擬用戶的行為模式，一些研究者利用用戶軌跡中的一些高頻地點[6]、home/work pair[7]或隨機采集的K個坐標點[8]來標定軌跡并描述用戶的運動模式，如果待匹配用戶軌跡中的顯式特征與某個用戶的匹配度較高，則可判定為同一用戶。基于顯式特征的軌跡去匿名方法側重于軌跡顯式特征的對比，計算效率較高。但是，該類方法忽略了軌跡中的位置點時序性和非頻繁位置，浪費了大量軌跡信息，因此其用戶識別準確率并不理想。

還有一些研究人員根據用戶的歷史軌跡數據構建統計概率模型，通過匿名軌跡與用戶模型的匹配概率完成軌跡去匿名，稱為基于概率模型的軌跡去匿名。此類方法使用移動馬爾可夫鏈MMC(Mobility Markov Chain)[9 - 11]或隱馬爾可夫模型HMM(Hidden Markov Model)[12,13]對用戶軌跡進行建模，可用于模擬用戶的運動模式。相比于MMC，采用HMM建模的方法對用戶軌跡的產生過程增加了隱含態的假設，更加符合實際場景。具體地，Wang等[12]提出了一種基于移動行為在時間上的周期性規律建立HMM模型的方法，采用24小時作為HMM模型的隱含態，用空間位置作為觀察態，從而用HMM模型將用戶偏好在時間和空間上的特征進行了關聯。Chen等[13]更進一步提出了基于密度的HMM軌跡去匿名方法，使得隱含態的選擇更加符合用戶差異性描述需求，提高了用戶身份重識別的準確率。這些基于概率模型的軌跡去匿名考慮到了位置點之間的轉移概率，能夠對用戶習慣進行建模。但是，此類方法在建模時假設位置轉移必須滿足MMC或HMM的模型架構，并且在提取隱含態時有較強的先驗知識約束，因此其去匿名效果更多地依賴于模型假設與數據集的匹配程度，以及特征工程的優劣。

深度學習技術的出現為軌跡去匿名提供了新的思路。Luo等[14]最早使用深度學習方法進行軌跡去匿名，使用RNN編碼器對嵌入后的簽到點序列進行編碼，在訓練過程中對軌跡序列輸出和對應的用戶表示進行擬合，實現簽到點軌跡-用戶鏈接。Wang等[15]在軌跡預訓練中使用圖生成點序列 “語料庫”，并對RNN編碼器和用戶表示向量進行聯合訓練。Zhou等[16]使用變分自編碼器合并數據集中缺少用戶標記的軌跡，緩解了簽到點軌跡數據集的數據稀疏問題。Zhou等[17]則使用基于長短期記憶LSTM(Long Short-Term Memory)網絡的生成模型對原有軌跡數據集中的原始用戶軌跡進行補充，進一步提升了軌跡去匿名的準確率。權波等[18]在船舶自動識別系統數據集上采用LSTM模型對船舶的軌跡進行了較為準確的預測。這些研究工作表明，軌跡數據是時序數據的一種，它除了有時間維度的依賴性還有空間維度的相關關系[19]。因此，RNN及其變種在軌跡數據的分類、計算和預測中具有較大優勢，為基于深度學習的軌跡去匿名提供了技術基礎。然而，在許多場景中，GPS數據集的軌跡點更加密集，且缺少語義信息，因此針對GPS軌跡的去匿名效果仍有待提高。

3 GPS軌跡數據預訓練方法

針對原始GPS軌跡數據結構復雜，數據容量大，難以直接對其進行建模的問題，本文提出一種GPS軌跡數據預訓練方法，能夠將軌跡表示為特征向量。主要由3個步驟組成：子軌跡劃分、位置點轉化和位置點嵌入。

3.1 子軌跡劃分

GPS軌跡通常以天為時間單位進行組織，而用戶一天內可能會有多次出行活動，如果直接對一天內產生的長軌跡建模，則難以挖掘出準確的用戶運動習慣，因此需要對原始GPS軌跡進行劃分。子軌跡劃分一方面可以降低總體計算復雜度，另一方面能夠將表征用戶運動的子軌跡從原始GPS軌跡中提取出來。本文采用Liu等[20]提出的子軌跡劃分方案對原始GPS數據進行劃分，使得切分后的每條子軌跡盡量接近一次正常的出行活動(如上下班、散步等)。子軌跡劃分方案如下所示：

截取某個用戶一天內的GPS軌跡T= {p1,p2,…,pr}，pi表示位置點。以時間間隔Δt將軌跡T切分為多條子軌跡T= {T1,T2,…,Tm},使得同一子軌跡中相鄰兩坐標點間的時間間隔小于Δt。如圖1所示，軌跡被切分為3條子軌跡。

3.2 位置點轉化

原始的GPS軌跡由經緯度坐標組成，如果直接使用初始的經緯度信息可能引發3個問題：

(1)原始GPS數據精度過高，即使用戶在同一地點也很容易會被判斷為不同地點，使得待匹配軌跡中的位置點與模型中的位置點無法匹配。

(2)GPS軌跡坐標過高的精度可能導致計算量過大，使得模型長時間無法收斂。

(3)GPS軌跡坐標在軌跡數據集中極少重復且數量極多，神經網絡很難從原始GPS軌跡數據中學習到概率和上下文信息，也會導致訓練的失敗。

為了解決上述問題，本文使用了一種基于采樣區域網格化的位置點轉化方法，將GPS坐標轉化為類似位置標簽的編號。其基本步驟如下所示：

(1)根據GPS軌跡數據集中采樣區域的經緯度邊界maxlon,minlon,maxlat,minlat，得出軌跡所能覆蓋的矩形區域。

(2)將矩形區域按照一定長度分割成若干小的正方形(cell)，并給每個cell編號，得到cell_ID，完成采樣區域的網格化。

(3)按照GPS坐標與網格的對應關系，將所有GPS軌跡處理成原始cell_ID序列。

(4)對序列中連續重復出現的cell_ID進行去重，最終得到位置點序列。

位置點轉化的效果如圖2所示。

Figure 2 Example of location conversion圖2 位置點轉化示例

3.3 位置點嵌入

神經網絡需要的輸入形式為定長向量。通常的做法是對位置點進行嵌入(Embedding)，即將單個數值或文本嵌入到數值向量空間中，使位置點轉化為定長向量。

目前針對軌跡中的位置點嵌入方法的研究還較少。其中，Li等[21]使用神經網絡將位置點在空間距離上的K近鄰嵌入到了定長向量中，空間距離越接近的位置點，嵌入后的向量就越相似。然而在GPS軌跡數據中，空間上接近的位置點未必在空間上可達(如河流的兩岸、建筑的兩側)，該方法忽略了環境對人類運動的影響。

為了得到更精確的位置點嵌入向量，本文使用word2vec[22]的skip-gram方式進行位置點嵌入，從而將位置點的空間可達性嵌入到向量中。由于skip-gram方式能夠在嵌入過程中保持單詞的有序性，所以它比word2vec中的連續詞袋CBOW(Continues Bag Of Word)模型方式更加適合軌跡中位置點的嵌入。word2vec將每個位置點轉化為定長向量后，在軌跡數據集中，2個位置點的上下文越接近，嵌入后的向量越相似，即2點在空間上的可達性越高。位置點嵌入完成后，位置點序列被轉化為向量序列，并可用作RNN網絡的輸入。

4 GPS軌跡去匿名方法

4.1 問題定義

首先給出軌跡去匿名的基本概念和定義。

定義1已知Tui={pi1,pi2,…,pir}是由用戶ui生成的一條GPS軌跡,其中,r表示軌跡Tui中的位置點數目，而位置點pij(j∈[1,r])代表由用戶ui在tj時刻生成的一個位置點，位置點pij= (lon,lat,tj)包含經度、緯度和時間。

定義2假設存在一個匿名軌跡數據集D= {T1,T2,…,Tk}和一個用戶數據集U= {u1,u2,…,un},其中,軌跡數據集D中的所有軌跡都是由用戶數據集U中的用戶生成的，k為軌跡數，n為用戶數，且k遠大于n。為每一條軌跡Ti找到對應的用戶標識uj的過程被稱為軌跡去匿名，記為映射f：D→U。

4.2 基本原理

基于深度學習的軌跡去匿名，其基本原理是通過對已有軌跡數據集的訓練，得到能夠將輸入的軌跡序列編碼為用戶表示的RNN編碼器，再使用該編碼器對匿名軌跡進行編碼，從而得到該軌跡的用戶標識。GPS軌跡去匿名框架如圖3所示。

Figure 3 Framework of GPS trajectory de-anonymization圖3 GPS軌跡去匿名框架

實現軌跡去匿名的基本步驟如下所示：

(1)首先使用獨熱(One-hot)編碼對用戶進行編碼，得到所有已知用戶的用戶表示uj(j∈[1,|U|])。

(2)使用循環神經網絡編碼器(RNN編碼器)對預訓練后得到的位置點序列進行編碼，使用交叉熵損失函數擬合編碼輸出和軌跡對應的用戶表示。

(3)當RNN編碼器在軌跡數據集上完成訓練時，該編碼器可對匿名軌跡進行編碼，輸出向量每一維都表示該軌跡與對應編號用戶的相關度。

4.3 網絡結構與模型訓練

軌跡去匿名所用的網絡結構分為：RNN編碼層、Dropout層和Softmax層。

(1)RNN編碼層。

本文采用RNN的幾種變種，包括LSTM、Bi-LSTM和GRU。其中，LSTM使用輸入門、遺忘門和輸出門控制軌跡輸入的存儲狀態，實現了序列信息的時間記憶，減少了RNN在訓練過程中的梯度消失。Bi-LSTM使用2個LSTM分別對原始輸入序列和原始輸入序列的反向副本同時進行訓練，學習輸入序列的前向和后向特征。GRU是LSTM的簡化版本，它保留了更新門和重置門2種狀態更新機制，相比LSTM模型更加簡單，訓練代價更小。由于這幾種變種采用了門結構對輸入的位置點信息有選擇地記憶，因此適合處理GPS軌跡這種較長序列，可顯著提高用戶識別的準確率。

(2)Dropout層。

RNN編碼層之后添加了Dropout層，隨機舍棄一些神經元的信息傳遞，避免某些用戶判別只在固定組合下才生效，抑制過擬合的產生。通常Dropout率為0.5時效果最好。

(3)Softmax層。

Softmax層對RNN編碼后的輸出進行加權和計算，通過Softmax函數將其映射到軌跡訓練集的用戶標簽上，輸出一條軌跡屬于對應用戶的概率。

(4)損失函數。

神經網絡最終的訓練結果是由損失函數決定的，為了使RNN編碼器的輸出能夠用于軌跡去匿名，本文使用了軌跡-用戶交叉熵損失函數，如式(1)所示：

(1)

其中,uj是輸入軌跡對應的用戶表示，T′i是RNN編碼器對一條軌跡序列的編碼輸出。

交叉熵損失函數刻畫的是2個分布之間的差異，交叉熵越小，2個分布越接近。因此，神經網絡的訓練目標為：對于一條軌跡序列Ti，RNN編碼器的輸出向量能夠最大程度地接近其對應的用戶表示。

5 實驗和分析

5.1 實驗數據

本文使用Geolife軌跡數據集[23]進行GPS軌跡去匿名實驗。該數據集來源于微軟亞洲研究院Geolife項目，包含了北京微軟亞洲研究院182名員工采集的GPS軌跡坐標，每個坐標都包含經緯度、采樣時間等信息，共計17 162條原始軌跡，總時間約48 000 h,記錄了用戶居家、工作、購物、遠足和旅游等活動的位置軌跡。

5.2 數據預處理

(1)子軌跡劃分。

GPS軌跡預訓練的第一步需要對原始GPS軌跡進行子軌跡劃分。根據Liu等[20]對人類運動軌跡的連續性分析，時間間隔選擇6 h。為了獲取質量更高的子軌跡，實驗去除了數據集中軌跡少于10條的用戶數據，以Δt=6 h進行子軌跡劃分，得到了包含150個用戶的子軌跡集合。

(2)位置點轉化。

為了減少區域外軌跡對實驗的干擾，本文舍棄了部分數量少、規律性弱的軌跡，將采樣區域集中在北京城區(minlat=39.75，maxlat=40.10，minlon=116.15，maxlon=116.60)，對采樣區域進行網格化后，最終篩選出135個用戶的軌跡數據。

(3)位置點嵌入。

使用word2vec對軌跡數據集進行訓練，從而獲得每個位置點的向量表示。對于較小的“語料庫”，嵌入后的向量維度(Embedding Size)通常在200～300，實驗選擇250作為嵌入的向量維度，即每個位置點嵌入后都被轉化為250維的向量。

5.3 實驗設置

5.3.1 參數設置

實驗主要參數設置如表1所示，通過實驗選擇了本文方法及各對比方法都較優的取值。

Table 1 Experimental parameter settings

5.3.2 對照實驗

本文選取3種傳統軌跡去匿名方法，使用同樣的軌跡數據集，與本文提出的方法進行對照：

(1)Rand4方法[8]。該方法屬于基于顯式特征的軌跡去匿名方法，從每個用戶的訓練軌跡數據中隨機抽取4個位置點作為用戶的唯一標識，并以此進行用戶匹配。

(2)基于移動馬爾可夫鏈(MMC)的方法[9]。屬于基于概率模型的軌跡去匿名方法，對訓練數據和測試數據分別提取位置點后構建馬爾可夫鏈并對比馬爾可夫鏈之間的相似度，以此完成軌跡去匿名。

(3)基于隱馬爾可夫鏈(HMM)的方法[13]。屬于基于概率模型的軌跡去匿名方法，在對移動模式進行建模時，比MMC多考慮了隱含態對位置序列的影響。隱含態描述了用戶在發生位置移動時所處的狀態，這些狀態影響著軌跡序列的產生。具體地，本文采用密度聚類方式獲取隱含態，并基于這些隱含態和訓練數據為每個用戶構建HMM模型，最后采用維特比算法(Viterbi Algorithm)來尋找與軌跡序列最優匹配的用戶。

5.3.3 評價指標

實驗結果使用準確率(Accuracy)、TopK準確率(Accuracy@K)和macro-F1共3個指標進行性能評價。

在軌跡去匿名的過程中，軌跡編碼結果的每一維都表示該軌跡屬于對應編號用戶的判別概率，一條軌跡的前K個用戶匹配被稱為TopK候選用戶，若TopK候選用戶中有一個命中，則視為TopK命中。

而macro-F1是衡量不同方法的多分類任務性能的一項指標，其計算公式如式(2)所示：

(2)

其中，macroP和macroR分別表示多分類任務中所有分類的平均準確率和平均召回率。

5.4 實驗結果分析

實驗結果如表2和圖4所示。

Table 2 Experimental results on Geolife dataset

Figure 4 TopK accuracy of different methods圖4 不同方法的TopK準確率

本文提出的基于深度學習的GPS軌跡去匿名方法在各項評價指標上均優于傳統軌跡去匿名方法。其中，Rand4方法僅采用隨機的4個軌跡點這種顯式特征為用戶移動行為建模，在GPS數據集上效果最差。這是由于GPS數據集中的位置點往往缺乏語義信息，難以直接用于用戶移動行為建模。而基于MMC和基于HMM的2種方法都屬于基于概率模型的用戶移動行為建模方法，其區別僅在于，HMM在描述位置序列時引入了隱含態的概念，使其能夠描述這些位置點是在何種用戶狀態下產生的。然而，隱含態的定義需要與實際用戶狀態相符，目前尚缺乏較好的解決方案，因此基于MMC和基于HMM的方法在實驗中準確率接近。而本文方法在軌跡建模中分別采用了LSTM、Bi-LSTM和GRU 3種RNN模型及其變種進行軌跡去匿名實驗，其中 Bi-LSTM在各項指標評價中均表現出了最佳的性能。從TopK準確率曲線中可以看出，Bi-LSTM的用戶判別準確率明顯優于其他2種方法，而LSTM和GRU的性能則十分接近。這是由于GPS數據的每條軌跡的位置點間具有較強的序列性依賴，而Bi-LSTM相比于另外2類RNN模型，在學習這些依賴關系方面更有優勢。

6 結束語

本文提出了一種基于深度學習的GPS軌跡去匿名方法,能夠對GPS軌跡數據進行預訓練，并從受匿名保護的軌跡數據中提取出較為精準的用戶標識。實驗中軌跡去匿名的準確率和Top5準確率分別達到了56.73%和73.48%，實現了較為精準的軌跡用戶判別。下一步工作將考慮：(1)提出一種新的位置點嵌入方法，對更多的軌跡語義信息進行嵌入。(2)在開放數據集上對匿名軌跡進行重識別研究，即考慮匿名用戶不在訓練集數據中等更為實際的場景。