融入興趣區域的差分隱私軌跡數據保護方法*

蘭 微，林 英,+，包聆言，李 彤，陳夢蓉，單今朝

1.云南大學 軟件學院，昆明650091

2.云南省軟件工程重點實驗室，昆明650091

1 引言

基于位置的服務[1]（location-based services，LBS）是通過利用路徑與地理位置信息為人們提供服務的一個新興領域，能為人們提供距離最近的商場、影院、ATM 機，日常出行中的導航信息，以及交通擁堵信息等。但用戶使用LBS，必須提供自己的位置相關信息。通過對一個或多個移動對象位置相關信息的采樣所獲得的數據信息根據采樣先后順序就構成了軌跡數據。

軌跡數據中包含了位置、時間、速度等與用戶隱私直接相關的信息，若不對原始軌跡數據進行保護而直接發布，軌跡數據的關聯性與時空特征使得攻擊者很容易地推斷出用戶的行為模式與習慣，同時攻擊者還可以根據用戶的歷史移動軌跡數據特征，挖掘出其活動范圍和活動場景[2]。根據文獻[3]的報道，在150 萬條匿名移動軌跡數據中，若無外部背景知識，隨機給出兩個時空數據點，50%以上的個人敏感移動軌跡可以被鑒別出來，隨機給出4 個時空點，便可以鑒別出95%的個人敏感移動軌跡。再者，隨著近年來大數據和物聯網相關技術的快速發展，極大地促進了軌跡數據挖掘技術[4-6]的發展，也導致用戶軌跡數據中的隱私信息更易于受到攻擊。因此，如何控制軌跡數據的發布和訪問是一個重要的研究問題。為實現軌跡數據發布隱私保護，研究者們提出了各種保護用戶軌跡隱私的手段，如You等[7]、Gao等[8]基于隨機方法和旋轉方法，生成一定數量的假軌跡，達到迷惑攻擊者的目的。Chen 等人[9]提出（K，C）L隱私模型，對敏感位置數據使用局部抑制的方法來實現軌跡數據的匿名。Abul 等人[10]提出（k-δ）匿名模型，使得發布的匿名集中的軌跡數量大于等于匿名數值k，且匿名集中任何兩條軌跡的距離（歐式距離）小于等于不確定性閾值δ。

傳統軌跡數據發布方法主要可以分為假數據[11]、抑制[12]及泛化[13]三種。假數據法是通過生成一些假軌跡對原始軌跡數據進行干擾，并且保證被干擾的軌跡數據的某些統計屬性不發生嚴重失真。抑制法主要通過不發布軌跡上的某些敏感位置或頻繁訪問的位置以實現隱私保護。泛化法將軌跡上所有的采樣點都泛化為對應的匿名區域，以達到隱私保護的目的。

假數據、抑制及泛化三種方法各有優缺點及不同的適用場景，其中假軌跡隱私保護方法簡單，計算量小，但容易造成假數據的存儲量大及數據可用性降低等缺點。因此，該方法適用于實時性較高并且對數據可用性要求不高的系統。抑制法能保證用戶較高的隱私保護度，然而過多的軌跡片段被抑制會造成巨大的信息損失。因此，該方法適用于隱私保護度高并且對數據可用性要求不高的系統。泛化法主要基于軌跡相似性進行軌跡聚類，但不合適的軌跡相似性度量會導致匿名過程中不必要的信息損失，從而降低軌跡數據的可用性。

以上三種隱私保護模型均無法提供一種有效且嚴格的方法來證明其隱私保護水平，因此2008 年Dwork[14]提出了一種更為嚴格的可證明隱私定義，即差分隱私保護方法。作為一種新的隱私保護模型，差分隱私保護無需考慮攻擊者所擁有的任何可能的背景知識，因此自誕生以來迅速被業界認可，并成為了隱私保護領域的研究熱點。

差分隱私保護最初被應用于統計數據庫安全領域，旨在發布統計信息時保護數據庫中個體的隱私信息。2012 年，Chen 等[15]首次提出將差分隱私用于對軌跡數據的保護，通過對軌跡數據加入Laplace 噪聲保證挖掘結果滿足差分隱私需求，從而實現對運輸信息的軌跡隱私保護。差分隱私機制自此也被用來進行軌跡隱私保護。

目前，針對軌跡數據的差分隱私保護還是一個新興研究領域，存在兩個主要問題亟待解決：

（1）如何在保護用戶隱私的前提下減少噪聲數據帶來的誤差，從而提高數據的可用性。在進行軌跡數據的隱私保護時，對全部數據集進行直接保護，會極大降低數據的可用性。因此，如何通過適當的方法在所有軌跡數據中選擇部分數據進行隱私保護為一大難點。例如，某一用戶一天的軌跡中存在560個位置點，如果直接對每個軌跡點進行保護，將造成嚴重信息損失，導致保護后發布的軌跡可用性極低。

（2）如何保證算法在滿足差分隱私的前提下，盡量提高數據的隱私保護程度。

為解決上述問題，本文提出了一種融入頻繁興趣區域進行差分隱私保護的軌跡數據保護方法。本文的主要工作如下：

（1）將軌跡數據中位置點集中出現的區域定義為興趣區域，以駐留點的形式代表興趣區域內所有位置點，在基本保持原有軌跡時序關系的前提下，精簡了軌跡中大量物理位置相近的數據點。

（2）通過對駐留點進行頻繁模式挖掘，發現用戶的頻繁駐留點，然后基于Laplace 機制，對頻繁駐留點進行加噪。傳統方法對所有軌跡數據點均進行加噪，而本文方法只需對部分軌跡數據點進行加噪，在保護用戶隱私的前提下，極大提高了數據的可用性。

（3）分別在公開的真實軌跡數據集和仿真軌跡數據上設計了詳細的實驗，以驗證本文方法的有效性。與三種現有方法進行了詳細對比，并詳盡地報告了實驗過程和結果。

2 差分隱私

發布數據信息時，信息發布者需要對數據信息中的個體隱私信息進行保護，差分隱私保護模型由此產生。差分隱私保護模型可實現在數據集中插入或刪除某一條記錄后，不會對輸出結果產生顯著影響的數據保護效果。

差分隱私保護下的數據發布，根據實現環境不同可以分為交互式數據發布和非交互式數據發布[7]，因此差分隱私保護下的軌跡數據保護也主要分為這兩種方式。在交互式環境下，用戶向軌跡數據管理者提出查詢請求，軌跡數據管理者根據用戶查詢請求對軌跡數據集進行操作，并將結果進行模糊化后反饋給用戶；在非交互式環境下，軌跡數據管理者針對可能的查詢，在滿足差分隱私的條件下一次性發布所有模糊化后的結果。本文主要考慮的為非交互環境下的軌跡數據發布。

2.1 相關定義

定義1（ε-差分隱私）設有隨機算法M，對于任意兩個相鄰數據集D和D′，若算法M在D和D′上的任意輸出結果S滿足：

則稱算法M提供ε-差分隱私保護，其中參數ε稱為差分隱私預算。ε控制隱私保護水平，ε越大，添加的噪聲越小，則隱私保護水平越低。ε越小，添加的噪聲越大，則隱私保護水平越高。當ε等于0 時，達到最高保護水平，此時經過加噪后的數據已無法反映與原數據相關的任何有效信息。

定義2（全局敏感度[16]）設有函數f:D→Rd，輸入為一數據集D，輸出為一個d維實數向量。對于任意的相鄰數據集D和D′，函數f的全局敏感度為：

其中，R表示所映射的實數空間，d表示函數f的查詢維度，||f(D)-f(D′)||1是f(D)和f(D′)之間的L1距離。敏感度是控制刪除數據集中某一記錄后對查詢結果造成的最大影響，函數的全局敏感度與數據集無關，僅與函數本身有關，且不同函數有不同的全局敏感度，其中噪聲大小與全局敏感度緊密相關。

2.2 實現機制

噪聲機制是實現差分隱私的主要技術，常用的噪聲機制有兩種：Laplace機制[16]和指數機制[17]。

Laplace 機制適用于數值型數據，其思路為根據Laplace 分布生成隨機噪聲，并將產生的隨機噪聲加入原始數據，以實現ε-差分隱私保護，Laplace 分布的概率密度函數為：

稱隨機變量x服從參數為b和u的Laplace分布。

定義3（Laplace 機制[16]）給定數據集D，設f:D →Rd是一個敏感度為Δf的函數。

Fig.1 Probability density function of Laplace圖1 Laplace概率密度函數

為生成服從Laplace 分布的噪聲，主要利用構造逆函數的方法：

其中，U是服從均勻分布（0,1）的隨機數，F-1為F的逆函數。當有多個x滿足逆函數時，只取值最小的x。

Laplace分布函數如下：

由上述分布函數即可生成服從Laplace 分布的隨機數X。

與只適用于數值型數據的Laplace 機制相比，指數機制適用于非數值型數據的查詢和處理。

定義4（指數機制[17]）設有可用函數u:(Dn×R)→R，輸出為一實體對象r∈Range，若算法A滿足下列等式，則A滿足ε-差分隱私。

其中，Δu為可用函數的全局敏感性，算法A以正比于的概率返回實體對象。由式（8）可知，打分越高，被選擇輸出的概率越大。

由于本文研究的是本質為實數序列的軌跡數據，因此選擇Laplace機制實現加噪。

3 相關工作

將差分隱私應用到保護軌跡數據發布，最早見于Chen 等人[15]將Laplace 噪聲添加到軌跡序列模式對應的真實支持度計數，并在此基礎上構建前綴序列樹，最終發布滿足差分隱私的軌跡數據庫。后續為降低序列維度的影響，提高挖掘結果的可用性，Chen等人[18]提出了n-gram 算法限制序列的最大長度。文獻[19]認為軌跡中的每一個位置都有可能暴露用戶隱私，因此提出一種結合速度與軌跡角度的生成噪聲的方法對所有位置點進行保護。Shao 等人[20]提出了一種結合采樣和插值的算法，打破了傳統差分隱私先驗敏感度的框架。Alaggan 等人[21]認為傳統差分隱私在無形中為用戶決定了隱私保護程度，這樣使得隱私保護方法缺乏靈活性。為解決這一問題，他們提出一種顯示機制來實現異構差分隱私。這種方法充分考慮每個位置點隱私程度，并用數值對隱私保護程度進行描述，使隱私保護結果更加合理和直觀。Dwork 等人[22]引入集中差分隱私來控制累積隱私損失，對差分隱私參數的選取做了深入討論。文獻[23]將馬爾科夫博弈與差分隱私相結合，以更準確地找出需要保護的位置點并進行相應的隱私保護。Li 等人[24]認為生成的隨機和無界噪聲并不能完全實現差分隱私，因此提出了有界噪聲生成算法和軌跡合并算法，有效提高了隱私保護效率。文獻[25]提出了將軌跡分割為較短的新軌跡的方法，該方法適用于處理較長的軌跡數據。文獻[26]提出LMDP（Lagrange multiplier-based differentially private）算法對隱私預算進行優化，經過保護后的軌跡數據能防止攻擊者通過兩位用戶的軌跡數據推測出其社會關系。文獻[27]基于稀疏位置攻擊和最大運行速度攻擊，采用構造噪聲四分樹和R-樹分割隱私預算。文獻[28]根據地理空間拓撲關系和馬爾科夫概率轉移矩陣提出了一種基于時空相關性的保護方法。

以上方法從噪聲生成方法或考慮軌跡中位置點敏感度并對所有位置點加入不同程度噪聲的角度實現軌跡數據保護，對軌跡中位置點進行擾動時均忽略不同位置點間隱私程度的差異，即其假設所有位置點都會泄露用戶隱私。且并非軌跡中所有位置點都需要進行隱私保護，否則將導致數據可用性過低，無法保證LBS 的服務質量。由于用戶的某些行為模式與習慣能夠通過挖掘用戶長時間停留的位置點或區域獲得，因此對這些位置點和區域的保護就顯得極為重要，應選取軌跡中最需要進行隱私保護的部分位置點和區域進行保護。

本文方法充分考慮軌跡中所有位置點間的時序性及相互關系，找出頻繁駐留點并對其進行保護，使得攻擊者無法從多個位置點間相互關系推測用戶隱私。相較于現有的對整條軌跡上所有位置點保護的方法，本文對軌跡中部分特殊位置點和區域進行保護研究，并在特殊的部分位置點上實施差分隱私保護。

4 研究方法

本文方法主要研究內容如圖2 中虛線框所示，主要包含數據預處理、挖掘頻繁駐留點和基于頻繁駐留點的加噪三部分。首先將軌跡數據進行精簡，在基本保持軌跡時序性的基礎上過濾冗余位置點，同時刪除敏感位置，對用戶隱私進行保護。數據預處理后，找出軌跡中頻繁出現的駐留點，并找到其所在的所有軌跡中對應的位置，最后利用差分隱私保護機制對頻繁駐留點加噪，生成隱私保護后的軌跡數據。

Fig.2 Architecture of this paper圖2 本文架構

4.1 數據預處理

4.1.1 興趣區域及駐留點定義

軌跡是指移動用戶的位置信息隨著時間變化形成的序列，一條軌跡T是一個GPS 序列，可形式化表示為{(x1,y1,t1),(x2,y2,t2),…,(xn,yn,tn)}，其中(xi,yi,ti),1 ≤i≤n即用戶的時空位置，稱為軌跡點，也可叫作位置點，表示移動用戶在ti時刻所處的位置為(xi,yi)，本文中xi為經度數據，yi為緯度數據，多條軌跡的集合組成了軌跡數據集D。

定義5（興趣區域）設有軌跡T={(x1,y1,t1),(x2,y2,t2),…,(xn,yn,tn)}，若存在：

稱滿足上式要求的，從(xi,yi)到(xj,yj),1 ≤i ＜j≤n的移動軌跡序列所形成的區域為用戶的興趣區域。其中ΔS為定義的某個距離閾值，ΔT為定義的某個時間閾值，Distance((xj,yj),(xi,yi))為根據兩位置點的經緯度計算得到的兩點之間的距離。

定義6（駐留點）軌跡T={(x1,y1,t1),(x2,y2,t2),…,(xn,yn,tn)},假設子軌跡Tr={(xi,yi,ti),(xi+1,yi+1,ti+1),…,(xj,yj,tj)}為用戶的興趣區域，稱,的位置點(xm,ym)為該興趣區域的駐留點。

值得說明的是，對ΔS和ΔT的取值將直接影響興趣區域的大小和數量，本文將在5.3 節詳細討論針對不同閾值選取對算法表現的影響。

4.1.2 挖掘興趣區域

軌跡數據的生成與位置點的采集時間有關，如果采集位置數據的時間間隔過短，例如每隔一秒就采集一次數據，將導致生成的軌跡數據量過大，且用戶頻繁且長時間停留的區域容易暴露用戶的行為模式。對于一個連續的GPS 移動軌跡，本文通過定義興趣區域，挖掘出用戶在一定距離范圍內停留了一段時間的區域，然后用駐留點代表此區域，同時從此原始軌跡中刪除該區域中所有的位置點，以達到避免信息冗余和保護用戶隱私的目的。

根據定義5，找出一條軌跡上的興趣區域的核心是計算出軌跡中停留時間大于一定時間閾值，但距離又限定在一定距離閾值內的軌跡點。

算法主要流程具體步驟如下：首先進行軌跡點之間時間的計算，即從軌跡初始點s=1 開始，依次計算第i個點與初始點s之間的時間差Δt。如果Δt＜時間閾值ΔT，就到達了軌跡的最后一個位置點，則程序結束；如果Δt＞ΔT，則計算從位置s到第i個位置之間的距離Δs。如果Δs＞距離閾值ΔS，則將起點位置s賦值為s+1，按照上述步驟重新計算；如果Δs＜ΔS則首先判斷第i個位置是否為結束位置，是則計算從位置s到位置i的駐留點，否則計算第i+1 個位置與位置s之間的Δs′。若Δs′＞ΔS，則計算從位置s至位置i的駐留點；若Δs′＜ΔS，則賦值i=i+1 繼續計算從位置s到位置i之間的距離，直至Δs′＞ΔS為止，計算駐留點，并判斷i是否為終點位置。如果是則程序結束，否則將當前位置i設為下一次循環的初始位置s，重新開始進行計算。挖掘興趣區域并找出駐留點后，用駐留點代替興趣區域覆蓋的原始位置點，并更新軌跡。算法如下：

Fig.3 Processes of mining interest region and simplifying trajectory圖3 挖掘興趣區域及精簡軌跡過程

假設已有一條用戶運動軌跡，如圖3（a）所示，實心圓點代表位置點，兩點間直線代表行走路線。根據算法1，首先從第一個位置點開始遍歷，依次判斷其與之后的位置點是否可組成興趣區域。若否，則將該位置點直接存入精簡軌跡；若是，則將滿足條件的所有位置點劃分為一個興趣區域，然后計算駐留點，如圖3（b）所示，圓圈內區域即為興趣區域，實心五角星為駐留點。駐留點存入精簡軌跡，進行下一次遍歷。遍歷完軌跡中所有位置點后即可得到精簡后的軌跡，如圖3（c）所示。

4.2 挖掘頻繁駐留點

定義7（頻繁駐留點）設通過算法1 得到駐留點數據集P{(x1,y1,t1),(x2,y2,t2),…,(xn,yn,tn)}，若存在Pi=(xi,yi,ti)的出現次數Occ≥θ，θ為支持度閾值，則稱Pi為頻繁駐留點。

4.3 基于頻繁駐留點的加噪

在挖掘出頻繁駐留點后，設有頻繁駐留點數據集Q{(x1,y1,t1),(x2,y2,t2),…,(xn,yn,tn)},依次遍歷Qi,i=1,2,…,n，首先找到Qi所在軌跡及其在軌跡中所處位置，產生服從Laplace 分布的隨機噪聲LatitudeNoise和LongitudeNoise，將噪聲依次加入xi和yi，最后用加噪后的位置點替換原始位置點。

5 實驗驗證

5.1 實驗數據

本文實驗首先使用微軟亞洲研究院的Geolife[29-31]項目提供的開源數據集，該數據集包含18 670 條真實用戶軌跡，被廣泛用于軌跡數據相關研究實驗[32-33]。由于原軌跡數據記錄位置時間間隔過短，導致位置點間距離過近，本文首先采取了每隔5 min 讀取一次位置點的方式對原軌跡數據進行精簡。

5.2 評價標準

在面向數據發布的軌跡隱私保護研究中，數據可用性和隱私保護程度是兩個主要的衡量指標。

5.2.1 數據可用性

數據可用性是對能否從保護后的數據中挖掘出有效信息的度量。針對不同的應用場景，出現了很多不同的數據可用性評價標準，如扭曲度[34]、軌跡相似性度量方法[35]、DTW 距離（dynamic time warping distance）[36]等。由于DTW 距離允許時間序列在局部縮放來最小化兩序列之間的距離，其能夠更好地匹配時間序列的特點使其被廣泛采用[37-40]，因此本文采用DTW 進行數據可用性度量。

定義8（DTW 距離）設有兩條軌跡T{(x1,y1,t1),(x2,y2,t2),…,(xm,ym,tm)} 和，長度分別為m與n，則兩條軌跡間的DTW 距離為：

5.2.2 隱私保護度

由Laplace 概率密度函數可知，ε越大，產生的噪聲越小，對原軌跡擾動越小，隱私保護度也越小。ε越小，產生的噪聲越大，對原軌跡擾動越大，隱私保護度也越大。

5.3 參數設定對算法表現的影響

根據定義5 和定義7 可知，距離閾值ΔS和時間閾值ΔT、支持度θ分別為進行興趣區域和頻繁駐留點挖掘時必要參數，為研究上述3 個閾值選取對算法表現的影響，本節首先對ΔS和ΔT的不同取值進行了分析，然后對支持度θ進行討論。

5.3.1 距離閾值

圖4 選擇了10 條軌跡進行展示,分析了時間閾值為10 min 時，距離閾值ΔS的變化對興趣區域個數的影響。從圖4 中可以看出興趣區域個數與距離閾值并非完全正相關，有時距離閾值大的興趣區域個數反而小于距離閾值小的興趣區域個數。在少數軌跡中，距離閾值的改變對興趣區域個數并未產生影響。

Fig.4 Effect of ΔS on the number of interest regions圖4 ΔS 對興趣區域數量的影響

5.3.2 時間閾值

圖5 同樣選擇了10 條軌跡進行展示，分析了距離閾值為200 m 時，時間閾值ΔT的變化對興趣區域個數的影響。由圖5 可見，時間閾值與興趣區域個數基本成負相關趨勢，時間閾值越大，對應的興趣區域個數反而越小。這是因為在距離閾值一定的情況下，時間閾值越大，表明用戶在某一位置點停留的時間就要越長，這就使該位置點可組成興趣區域的條件更加嚴苛，導致興趣區域個數減少。

Fig.5 Effect of ΔT on the number of interest regions圖5 ΔT 對興趣區域數量的影響

5.3.3 支持度

支持度θ代表某一位置點出現次數，本文將出現次數大于θ的駐留點稱為頻繁駐留點。本文對12 位用戶一年中所有軌跡數據集使用不同的θ進行實驗，結果如圖6 所示。在所有用戶軌跡中，支持度為2時，頻繁駐留點個數最大，支持度為6 時，頻繁駐留點個數最小。θ取值增大的同時頻繁駐留點個數呈下降趨勢?？梢娭С侄仍酱?，頻繁駐留點越少。圖7 中6條曲線分別為6 位用戶一年的軌跡在θ從1 至5 的情況下各自對應的平均失真度。從圖7 中可以看出，θ值越大，平均失真度越小。這是因為θ越大，即頻繁駐留點的條件越苛刻，滿足出現次數大于θ的駐留點就越少。因此在加噪時，擾動的位置點也就越少，失真度也隨之減小。

Fig.6 Changes in the number of frequent-stay points圖6 頻繁駐留點數量變化

Fig.7 Changes in average distortion圖7 平均失真度變化

5.4 實驗結果及分析

為驗證本文所提方法性能，將文獻[19]中提出的Pnoise、Cnoise 和Gnoise 作為基線方法，使用真實數據集進行對比實驗。本文實驗過程中對不同用戶一年中所有軌跡進行實驗，但限于文章篇幅，本文僅從中隨機選取10 條軌跡進行示例，但完整實驗結果與示例軌跡結果分布一致。

5.4.1 數據可用性

本文采用DTW 距離來衡量隱私保護前后軌跡的失真度，并以此來評價軌跡數據的可用性。一般情況下，兩條軌跡之間的差異越小，即失真度越小，則實施隱私保護后的軌跡可用性越強。

本文分兩種情況對數據可用性進行分析：首先選定時間閾值為10 min，然后選取不同的距離閾值；其次選定距離閾值為200 m，然后選取不同的時間閾值。為進行對比，本文實現了文獻[19]中提出的Pnoise、Cnoise 和Gnoise 隱私保護方法，同時計算出實施3 種隱私保護方法后不同軌跡的失真度，并與上述實驗設置后所得的本文方法性能結果進行對比。實驗結果如圖8、圖9、圖10 所示。

通過觀察圖8、圖9 以及圖10 中的圖（a）可以發現在ΔT固定的情況下，基本呈現ΔS越小，失真度也越小的趨勢。這是因為ΔS越小，興趣區域可包含的位置點就越少。對原始軌跡中的位置點進行越少的刪除，所劃分興趣區域后的精簡軌跡與原始軌跡相似度越高，因此在后續挖掘頻繁駐留點以及加噪的步驟中造成的信息損失度會小于興趣區域數量較大時的信息損失度。從圖10（a）可發現在第6 條軌跡處，ΔS=150 m 時的失真度高于ΔS=500 m 的失真率，由此可以得出失真度與ΔS并不完全成正比關系。

Fig.8 Comparison of Pnoise method and proposed method圖8 本文方法與Pnoise 方法對比

Fig.9 Comparison of Cnoise method and proposed method圖9 本文方法與Cnoise 方法對比

Fig.10 Comparison of Gnoise method and proposed method圖10 本文方法與Gnoise 方法對比

同時還可明顯看出本文方法在取不同閾值情況下，軌跡數據失真度均小于基線方法。尤其在圖10（a）中，ΔT=10 min，ΔS=50 m 時，本文方法失真度為0.031 3，Gnoise 方法失真度高達2.341，此時本文方法優越性最為明顯。這表明經本文方法保護后發布的軌跡數據在隱私信息得到保護的同時依然具有較高的可用性。

在得到軌跡數據集中所有軌跡的失真度后，將所有軌跡失真度累加后除以軌跡數據集中軌跡的個數即為平均失真度。表1 給出了采用不同方法對某一用戶一年中所有軌跡進行隱私保護后得到的軌跡數據集的平均失真度。

Table 1 Different methods and their average distortion on real world datasets表1 真實數據集上不同方法與平均失真度

在ΔT=10 min，ΔS=50 m 時，本文方法運行結果失真度為0.010 839，基線方法中的Gnoise 失真度則高達0.508 626，高出本文方法0.497 787。這表明經過本文方法保護后的軌跡數據可用性可大幅度高于現有軌跡數據發布方法。縱觀表1，本文方法在多種情況下平均失真度均低于基線方法，這再次證明上述3 組對比圖結果的正確性。

5.4.2 隱私保護度

本文隨機選取3 位用戶的所有軌跡，在進行數據預處理、挖掘頻繁駐留點后，對頻繁駐留點加入不同大小的噪聲并計算所有軌跡的平均失真度，以此論證隱私保護性能。根據差分隱私相關定義可知，ε越大，隱私保護度越低，ε越小，隱私保護度越高。

實驗結果如表2 所示，從第2 列起每一列分別表示每位用戶軌跡在不同噪聲值下的平均失真度。從表中可看出，由于ε取值越大，生成的噪聲越小，因此ε的取值與3 位用戶的軌跡平均失真度成反比。當ε取0.05 時，平均值失真度最大，ε取1 000 時平均失真度最小。這個結果與加入的噪聲越大，隱私保護性能越好的結論相符。當ε取0.05和1 000時，用戶2軌跡數據平均失真度分別為73.299 32 和0.046 312，差距最大，為73.253 01。觀察用戶1 軌跡的平均失真度，在ε=5 時，軌跡平均失真度相較于ε=1 時，降低幅度為0.966 12；在ε=10 時，軌跡平均失真度相較于ε=5 時，降低幅度為0.080 074；在ε=100 時，軌跡平均失真度相較于ε=10 時，降低幅度為0.094 967?？梢姴煌胖g的平均失真度的降低幅度并非持續變小，這是由于不同用戶軌跡數據的特殊性以及算法中生成的隨機數在一定區間內波動。

Tabel 2 ε and average distortion on real world datasets表2 真實數據集上ε 與平均失真度

表3 中的實驗結果表明，預處理后相較于每隔5 min 讀取一次位置點后，位置點個數減少比例最低為34.08%，最高為73.62%。軌跡中位置點數量的減少可降低攻擊者可獲得的位置信息，加大了攻擊者根據已有位置信息推測用戶隱私的難度，證明了本文方法軌跡數據隱私保護的有效性。

Table 3 The number of locations in different phases表3 不同階段位置點個數

5.5 仿真數據實驗

為進一步驗證本文方法有效性，本文使用軌跡數據相關研究領域[27,41-42]常用的Brinkoff 模擬器生成了15 000 條用戶軌跡，對本文方法進行了仿真實驗。隨機抽取部分實驗結果進行展示，展示結果與完整實驗結果趨勢相同。

表4 展示的為本文方法在相同ΔT，不同ΔS的情況下，與3種基線方法的平均失真度。由于Brinkoff生成的坐標均為模擬坐標，因此仿真實驗中使用的距離均為模擬地圖上的相對距離，故表4 中的ΔS無具體距離單位。本文方法在相同ΔT，不同ΔS時，平均失真度波動小，但3 種情況下的平均失真度均小于3 種基線方法。最為顯著的是，當ΔT=5 min，ΔS=490 時，本文方法平均失真度相較于Cnoise，平均失真度降低了0.655 263。

Table 4 Different methods and their average distortion on simulation datasets表4 仿真數據集上不同方法與平均失真度

表5 展示的為在不同ε的情況下，經本文方法處理后3 位用戶軌跡的平均失真度。從表中可看出，隨著ε的增長，3 位用戶軌跡的平均失真度均隨之降低，與表2 具有相同的趨勢。

Tabel 5 ε and average distortion on simulation datasets表5 仿真數據集上ε 與平均失真度

綜上可知，無論是在真實軌跡數據集或仿真軌跡數據集上，在保護軌跡數據隱私的前提下，本文方法相較于現有方法均有效提高了軌跡數據的可用性。

6 結束語

軌跡數據發布方法一直是隱私保護的研究熱點，針對現有方法中將軌跡中所有位置點進行保護導致數據可用性降低的問題，本文提出了一種融入興趣區域的差分隱私軌跡數據保護方法。該方法劃分興趣區域挖掘出駐留點，并通過差分隱私機制對頻繁駐留點進行隱私保護。達到通過對部分位置點進行保護，在保護數據隱私的前提下保證數據可用性的目的。通過對真實軌跡數據集和仿真軌跡數據集進行實驗，驗證了本文方法的有效性。在真實軌跡數據集上，當ΔT=10 min，ΔS=50 m 時本文方法與Pnoise、Cnoise 和Gnoise 三種基線方法相比，將平均失真度分別降低了0.287 998、0.478 895 和0.497 787；在仿真軌跡數據集上，當ΔT=5 min，ΔS=490 時，本文方法與Pnoise、Cnoise 和Gnoise 三種基線方法相比，將平均失真度分別降低了0.133 640、0.655 263 和0.070 671。同時，實驗中通過調整ε的取值可控制隱私保護的性能，ε的取值從0.05 增長至1 000 的過程中隱私保護性能逐步降低。在挖掘興趣區域時，對原軌跡進行精簡的步驟也對軌跡數據進行了隱私保護。實驗結果表明，相較于現有的在所有軌跡數據上進行加噪的隱私保護方法，本文方法雖只在部分軌跡數據上加噪，但在保護軌跡數據隱私的前提下，提高了數據可用性。

由于軌跡數據本質上是實數序列，不同軌跡具有自身特性，使得本文方法還存在部分問題有待探討，如還需找到更具普適性的興趣區域相關閾值等。同時由于駐留點代替的為一定區域，因此本文在挖掘頻繁興趣駐留點時對數據精度進行了適當調整。這些問題為將來的研究指出了方向，為進一步驗證本文方法的有效性，也為提高本文方法普適性，將對本文方法進行更深入的研究和改進。