軌跡數據發布中基于敏感語義位置的隱私保護算法

俞望年，宣占祥，馬小明，岳威，左開中,2

（1.安徽師范大學計算機與信息學院，蕪湖 241002；2.安徽師范大學網絡與信息安全安徽省重點實驗室，蕪湖 241002）

0 引言

近年來，隨著移動智能設備的普及和定位技術的發展，人們的海量軌跡數據被收集、存儲、挖掘和分析[1-4]。然而軌跡數據含有大量的個人隱私信息，例如社會身份、家庭住址、身體健康狀況、工作場所以及日常行程等，若不經處理直接發布軌跡數據，將會泄露個人隱私信息[5-6]。因此，如何保證發布的軌跡數據具有較高數據可用性的同時，保護用戶的敏感隱私信息，已成為國內外學者關注的熱點。

常用的軌跡隱私保護方法有K 匿名法[7-10]、假軌跡法[11-12]、抑制法[13-14]和差分隱私法[15-16]。文獻[7]提出（K，δ）-隱私保護算法，利用軌跡數據不確定性進行軌跡聚類，對軌跡位置進行隱私保護。文獻[8]利用網格技術對軌跡位置點進行空間泛化以滿足K 匿名，進而將軌跡轉換為連續網格序列。文獻[9]認為并非軌跡上的所有采樣位置都要進行匿名處理，通過停留位置提取算法獲取軌跡數據中的停留位置，再利用網格劃分技術和K 匿名構建匿名區域，進一步保護用戶敏感隱私信息。文獻[10]利用挖掘到的真實興趣點數據，提出（K，L）-隱私模型，利用網格劃分技術為停留位置構建匿名區域，使得匿名區域滿足K 匿名和L 語義差異性。文獻[11]通過計算虛假軌跡和真實軌跡的K 個交叉點，隨機生成交叉點間軌跡。文獻[12]隨機選擇軌跡采樣位置點，將用戶真實軌跡進行不同角度旋轉生成潛在虛假軌跡。文獻[13]通過對軌跡數據中的敏感或者頻繁訪問位置進行抑制處理，保護隱私信息。文獻[14]提出一種基于單點收益的軌跡隱私保護方法，通過計算收益結果，在軌跡數據集中抑制位置或者添加假軌跡，減少信息損失率。文獻[15]利用隱馬爾科夫模型度量用戶位置相關性，通過設計滿足差分隱私的拉布拉斯噪聲機制保護用戶隱私信息。文獻[16]利用四叉樹和R樹數據結構，提出兩種滿足差分隱私的軌跡數據發布方法。然而，這些方法存在信息損失率過大導致的數據可用性較低問題，同時沒有充分考慮用戶所處語義位置信息，存在語義推斷攻擊[17-18]，導致用戶敏感隱私泄露。

基于此，本文提出一種基于敏感語義位置的軌跡數據隱私保護算法，通過對用戶敏感的語義位置進行匿名處理，構建語義安全匿名區域，提高位置隱私保護程度，同時減少對非敏感語義位置的匿名處理，降低信息損失率，提高軌跡數據可用性。

1 預備知識

1.1 相關定義

定義1（語義位置）是指具有坐標、語義位置類型（如學校、商場等）和流行度等特征的位置，記為loc={address，type，（lon，lat），P（loc）}。其中：address 為語義地址；type 表示語義位置類型；（lon，lat）表示語義位置經緯度；P（loc）表示語義位置流行度。本文根據地理標簽將語義位置類型分為10 種，如圖1 所示。此外，語義位置是否敏感由用戶定義，例如醫院，部分患者認為是敏感的，醫生則認為是非敏感的。

圖1 語義位置地理標簽分類

定義2（語義位置流行度）是指用戶訪問該語義位置的概率。 設 loc 是一個語義位置，U(loc)={u1,u2,…,um} 是訪問過該語義位置的用戶集合，并設nj是用戶uj對loc 的訪問次數，該語義位置被訪問的總數記為因此該語義位置的流行度定義為P(loc)=2H(loc)，其中：它表示該語義位置的信息熵，即被用戶訪問的可能性。

圖2 語義位置Voronoi圖

定義3（語義位置Voronoi 圖）是指以語義位置為生成元構建的Voronoi 圖，如圖2 所示。每個語義位置的 Voronoi 單 元 滿 足Voronoi(loci)={x：d(x,loci)≤d(x,locj),loci≠locj}，其中：d（x，loci）表示 x 到語義位置 loci的歐式距離；x 表示任意位置。

定義4（語義軌跡）是指將原始軌跡上的采樣位置按時間順序語義化為移動對象停留位置序列，記為其中：表示第 i 個用戶身份標識符，表示STi的第j 個停留位置。為了簡便，系統會自動將停留位置轉化為最近鄰語義位置。

定義5（隱私需求）是指用戶的隱私保護需求，記為PR={θ,senstype}，其中：θ表示用戶定義的語義安全閾值；senstype 表示用戶定義的敏感語義位置類型集。

定義6（匿名區域）是指一個用來隱藏用戶語義位置的空間區域，記為CR={Voronoi(loc1),…,Voronoi(loci),...,Voronoi(locm)}，其中：ioVoronoi(loci)表示語義位置loci所處的Voronoi 單元。

定義7（θ-語義安全匿名區域）已知一個匿名區域CR 和一個用戶u，CR 中屬于u 的敏感語義位置用senslocsu表示，則匿名區域敏感語義位置總流行度記為POP（senslocsu），匿名區域語義位置總流行度記為POP（all），匿名區域語義安全程度用d（CR）表示：

若匿名區域的語義安全程度d(CR)≤u.PR.θ，我們就稱CR 對用戶u 來說是一個θ-語義安全匿名區域。

1.2 系統架構

本文系統架構如圖3 所示。

圖3 系統架構

該架構包括客戶端、軌跡收據收集服務器、原始軌跡數據庫、隱私保護算法服務器、可發布軌跡數據庫4個組件?？蛻舳素撠熡涗浻脩糗壽E數據，并將記錄的軌跡數據發送給軌跡數據收集服務器，軌跡數據收集服務器接收客戶端發送的軌跡數據，原始軌跡數據庫存儲軌跡數據收集服務器接收到的軌跡數據，隱私保護算法服務器對原始軌跡數據進行停留位置提取、匿名區域生成和軌跡匿名處理處理，匿名后的數據存儲在可發布軌跡數據庫中。

2 基于敏感語義位置的軌跡數據隱私保護算法

2.1 算法設計

本文充分考慮用戶的隱私需求和軌跡數據可用性問題，提出一種基于敏感語義位置的軌跡數據隱私保護算法，主要思想如圖4 所示。

圖4 算法流程圖

具體步驟如下：

（1）利用語義位置進行Voronoi 圖劃分。

（2）從原始軌跡的采樣位置數據中提取用戶停留位置。

（3）若停留位置處于非敏感語義位置的Voronoi 單元中，則不進行匿名處理；若處于敏感語義位置的Voronoi 單元中，則將該Voronoi 單元加入匿名區域，執行步驟（4）。

（4）遍歷所有與匿名區域相鄰近的語義位置，根據用戶設置的敏感語義位置類型，優先添加流行度最大的非敏感語義位置，其次選擇流行度最小的敏感語義位置。

（5）將該語義位置對應的Voronoi 單元加入匿名區域，若匿名區域語義安全程度滿足用戶設定的語義安全閾值，返回該匿名區域；否則，執行步驟（4）。

算法1 給出了基于敏感語義位置的軌跡數據隱私保護算法（Sensitive Semantic Location Privacy Protection Algorithm for Trajectory Data，SSLPP）的偽代碼。首先將原始軌跡traj 轉換為語義軌跡ST（第3 行），遍歷ST 中的每一個停留的語義位置loc（第4 行），若處在敏感語義位置（第5 行），將該語義位置所在Voronoi 單元加入匿名區域（第6 行）；其次根據PR.senstype 添加匿名區域鄰近Voronoi 單元，直至滿足語義安全閾值（第7-16行），并用該匿名區域替換loc（第17 行）；然后掃描原始軌跡traj 中的每一個采樣位置，將敏感的停留位置轉換為ST 中的相應匿名區域，同時若有采樣位置被ST 中的相應匿名區域覆蓋，則使用該匿名區域替代采樣位置，形成可安全發布的軌跡traj*，并將traj*放入軌跡數據庫 D*（第 20-21 行）；最后返回 D*（第 23 行）。

算法1 基于敏感語義位置的軌跡隱私保護算法

輸入：語義位置Voronoi 圖、原始軌跡數據庫D、隱私需求PR

輸出：可發布的軌跡數據庫D*

1）D*=? ；

2）For traj∈Ddo

3）轉換為語義軌跡ST={loc1,loc2,...,locn}；

4）Forloc∈STdo

5） Ifloc.type∈PR.senstypethen

6）CR=GetVoronoi(loc)；∕∕獲 取 loc 所 在 Voronoi單元

7） While（d(CR)>PR.θ）do

8）NSset=GetNSLinks(CR,PR.senstype)；∕∕記錄非敏感語義位置

9）SNset=GetSNLinks(CR,PR.senstype)；∕∕記 錄 敏感語義位置

10） IfNSset≠ ? then

11）loclink=SelectMaxpop(NSset)；∕∕選擇流行度最大的語義位置

12） Else

13）loclink=SelectMinpop(SNset)；∕∕選擇流行度最小的語義位置

14） End if

15）CR=CR?Voronoi(loclink)；

16） End while

17） 用 CR 替換 loc；

18）End if

19）End for

20）根據 ST 將 traj 轉換為 traj*；

21）D*=D*?traj*；

22）End for

23）Return D*；

2.2 算法分析

在軌跡數據發布中，真正泄露用戶隱私的是用戶停留的語義位置。因此，SSLPP 算法在此基礎上，考慮到用戶對不同語義位置的訪問具有差異性，利用真實數據計算各語義位置流行度。充分考慮用戶的隱私需求，根據用戶設置的敏感語義位置類型和語義安全閾值對停留的語義位置進行有選擇的構建θ-語義安全匿名區域，保護用戶敏感隱私信息。因為當用戶處于敏感語義位置時，構建的匿名區域CR 至少還包含一個非敏感語義位置，這是因為若沒有非敏感語義位置，CR的語義安全程度d（CR）=1，無法滿足用戶設置的θ閾值，因此增加攻擊者推測用戶敏感隱私信息的難度。

在軌跡數據可用性方面，SSLPP 算法使用信息損失率[19]來進行衡量，計算公式如下：

其中：ILAave表示停留位置轉化為匿名區域后的平均信息損失率；n 表示軌跡條數，m 表示每條軌跡上的采樣位置數，Asp 表示所有軌跡上的采樣位置數，Area（Zone（Ti，Sampij））表示第i 條軌跡的第j 個采樣位置所屬的匿名區域面積。信息損失率越低，數據可用性越高；反之，數據可用性越差。由于SSLPP 算法僅針對用戶敏感的停留位置進行隱私保護，減少匿名處理規模。因此，SSLPP 算法可以降低信息損失率，提高軌跡數據可用性。

3 實驗及結果分析

3.1 實驗設置

本文對比了文獻[7]的（K，δ）算法、文獻[9]的 Grid-Partition 算法和文獻[10]的 SSAC 算法。其中：（K，δ）算法是對軌跡數據中的所有采樣位置進行匿名處理，K 默認設置為 6，δ取值為 500，1000，1500，2000；GridPartition算法對軌跡數據中的停留位置進行K 匿名處理，K 默認設置為6；SSAC 算法對軌跡數據中的停留位置進行（K，L）匿名處理，K 默認設置為 6，L 默認設置為 3。

所有的匿名算法均用Java 實現，并運行在一臺配置為 Intel Core i5-4200M CPU@2.5GHz，12GB 內存的Windows 10 計算機上。實驗數據采用北京PoI（Point of Interest）數據[10]作為語義位置，敏感語義位置類型設置為{休閑娛樂，住宿，科教文化}，隨機選取Geolife 數據[9]中 100 個用戶的 10129 條軌跡，共計 16021938 個采樣位置。經過停留位置提取算法[9]后得到27116 個停留位置，具體分布如圖5 所示。表1 列出了實驗參數具體信息。

表1 實驗參數設置

圖5 停留位置可視化

圖6 θ值變動

3.2 實驗結果分析

（1）θ值變動的影響

圖6 描述θ值變動對信息損失率和運行時間的影響，其中語義位置數為50000，敏感語義位置類型為{休閑娛樂，住宿，科教文化}。由于（K，δ）算法、GridPartition 算法和SSAC 算法不考慮語義安全性，因此只對SSLPP 算法進行實驗驗證。

由圖 6（a）可知，隨著θ值的增加，SSLPP 算法的信息損失率不斷降低，這是因為θ值增大，構建語義安全匿名區域需要添加的相鄰語義位置越少，使得匿名區域面積相應減小，降低信息損失率。

由圖 6（b）可知，隨著θ值的增加，SSLPP 算法的執行時間不斷減少，這是因為θ值增大，匿名區域擴展添加Voronoi 單元次數逐漸減少，降低算法執行時間。

（2）敏感語義位置類型數量的影響

圖7 描述敏感語義位置類型數量的變動對信息損失率和運行時間的影響，其中語義位置數量為50000，θ值為0.6。

由圖7（a）可知，隨著敏感語義位置類型數量的增加，SSLPP 算法的信息損失率不斷增加，但始終低于（K，δ）算法、GridPartition 算法和 SSAC 算法。這是因為敏感語義位置類型數量增多，SSLPP 算法需要匿名處理的停留位置增多，相應信息損失率逐漸增加。但GridPartition 算法和SSAC 算法對所有停留位置進行匿名處理區域；（K，δ）算法是對軌跡數據中的所有采樣位置進行匿名處理，因此信息損失率始終高于SSLPP算法。

由圖7（b）可知，隨著敏感語義位置類型數量的增加，SSLPP 算法匿名時間不斷增加，但始終低于（K，δ）算法、GridPartition 算法和 SSAC 算法。這是因為SSLPP 算法僅對停留的敏感語義位置進行匿名處理，減少匿名處理規模，減少算法運行時間。

（3）語義位置數量的影響

圖8 描述語義位置數量的變動對信息損失率，其中敏感語義位置類型為{休閑娛樂，住宿，科教文化}，θ值為0.6。

由圖8 可知，隨著語義位置數量的增加，SSLPP 算法信息損失率不斷降低，且始終低于（K，δ）算法、Grid-Partition 算法和SSAC 算法。這是因為語義位置數量越多，非敏感語義位置數量相應增加，使得擴展添加Voronoi 單元次數減少，縮減匿名區域面積，從而降低信息損失率。（K，δ）算法不考慮語義位置，因此信息損失率不受語義位置數量變化的影響。隨著語義位置數量的增加，GridPartition 算法和SSAC 算法信息損失率不斷降低，但降低幅度較小。

4 結語

本文針對利用軌跡數據進行數據挖掘的場景，提出一種基于敏感語義位置的軌跡隱私保護算法。該算法根據移動對象設置的敏感語義位置類型和語義安全閾值對停留位置進行泛化處理，不僅可以避免語義推斷攻擊，而且可以降低信息損失率，從而提高軌跡數據可用性和敏感隱私信息保護程度。

圖7 敏感語義位置類型數量變動

圖8 語義位置數量變動

然而，本文算法沒有充分考慮城市交通路網和語義位置的時間維度。因此，下一階段的研究可以結合城市路網和時間維度構建匿名區域，進一步增強隱私保護程度。