融入興趣區(qū)域的差分隱私軌跡數(shù)據(jù)保護方法*

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

1.云南大學(xué) 軟件學(xué)院，昆明650091

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

1 引言

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

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

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

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

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

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

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

（1）如何在保護用戶隱私的前提下減少噪聲數(shù)據(jù)帶來的誤差，從而提高數(shù)據(jù)的可用性。在進行軌跡數(shù)據(jù)的隱私保護時，對全部數(shù)據(jù)集進行直接保護，會極大降低數(shù)據(jù)的可用性。因此，如何通過適當(dāng)?shù)姆椒ㄔ谒熊壽E數(shù)據(jù)中選擇部分?jǐn)?shù)據(jù)進行隱私保護為一大難點。例如，某一用戶一天的軌跡中存在560個位置點，如果直接對每個軌跡點進行保護，將造成嚴(yán)重信息損失，導(dǎo)致保護后發(fā)布的軌跡可用性極低。

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

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

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

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

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

2 差分隱私

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

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

2.1 相關(guān)定義

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

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

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

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

2.2 實現(xiàn)機制

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

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

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

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

Fig.1 Probability density function of Laplace圖1 Laplace概率密度函數(shù)

為生成服從Laplace 分布的噪聲，主要利用構(gòu)造逆函數(shù)的方法：

其中，U是服從均勻分布（0,1）的隨機數(shù)，F(xiàn)-1為F的逆函數(shù)。當(dāng)有多個x滿足逆函數(shù)時，只取值最小的x。

Laplace分布函數(shù)如下：

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

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

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

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

由于本文研究的是本質(zhì)為實數(shù)序列的軌跡數(shù)據(jù)，因此選擇Laplace機制實現(xiàn)加噪。

3 相關(guān)工作

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

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

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

4 研究方法

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

Fig.2 Architecture of this paper圖2 本文架構(gòu)

4.1 數(shù)據(jù)預(yù)處理

4.1.1 興趣區(qū)域及駐留點定義

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

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

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

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

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

4.1.2 挖掘興趣區(qū)域

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

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

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

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

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

4.2 挖掘頻繁駐留點

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

4.3 基于頻繁駐留點的加噪

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

5 實驗驗證

5.1 實驗數(shù)據(jù)

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

5.2 評價標(biāo)準(zhǔn)

在面向數(shù)據(jù)發(fā)布的軌跡隱私保護研究中，數(shù)據(jù)可用性和隱私保護程度是兩個主要的衡量指標(biāo)。

5.2.1 數(shù)據(jù)可用性

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

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

5.2.2 隱私保護度

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

5.3 參數(shù)設(shè)定對算法表現(xiàn)的影響

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

5.3.1 距離閾值

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

Fig.4 Effect of ΔS on the number of interest regions圖4 ΔS 對興趣區(qū)域數(shù)量的影響

5.3.2 時間閾值

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

Fig.5 Effect of ΔT on the number of interest regions圖5 ΔT 對興趣區(qū)域數(shù)量的影響

5.3.3 支持度

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

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

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

5.4 實驗結(jié)果及分析

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

5.4.1 數(shù)據(jù)可用性

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

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

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

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 方法對比

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

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

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

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

5.4.2 隱私保護度

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

實驗結(jié)果如表2 所示，從第2 列起每一列分別表示每位用戶軌跡在不同噪聲值下的平均失真度。從表中可看出，由于ε取值越大，生成的噪聲越小，因此ε的取值與3 位用戶的軌跡平均失真度成反比。當(dāng)ε取0.05 時，平均值失真度最大，ε取1 000 時平均失真度最小。這個結(jié)果與加入的噪聲越大，隱私保護性能越好的結(jié)論相符。當(dāng)ε取0.05和1 000時，用戶2軌跡數(shù)據(jù)平均失真度分別為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。可見不同ε之間的平均失真度的降低幅度并非持續(xù)變小，這是由于不同用戶軌跡數(shù)據(jù)的特殊性以及算法中生成的隨機數(shù)在一定區(qū)間內(nèi)波動。

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

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

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

5.5 仿真數(shù)據(jù)實驗

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

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

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

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

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

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

6 結(jié)束語

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

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