基于用戶感興趣區域的地理不可區分性的位置擾動算法

羅惠雯，龍士工*

（1. 貴州省公共大數據重點實驗室（貴州大學），貴陽550000； 2. 貴州大學計算機科學與技術學院，貴陽550000）

（*通信作者電子郵箱1136297177@qq.com）

0 引言

由于位置服務的普及，個人訪問過的位置信息很容易被泄露，其中包括工作住址、喜好、運動模式等，攻擊者甚至能夠從中提取到關于用戶生活習慣、健康狀況等極其敏感的信息［1-3］。

目前較為流行的引入到位置隱私保護領域的技術主要是差分隱私［4-6］，其應用隨機機制加入受控噪聲，在數據發布中，已被證明是有效的。一些有關位置數據隱私保護的研究工作，主要將差分隱私直接應用到位置數據發布中。文獻［7］提出了一種利用區域四叉樹結構的空間分解技術，提供基于密度聚類算法的差分隱私保護。文獻［8］則創建了一個多層的位置信息樹模型，利用樹型結構結合用戶的簽到次數來分配隱私預算。文獻［9］將差分隱私與隱匿空間技術結合起來，對攻擊者的攻擊能力進行量化，限制了攻擊的成功率。文獻［10］證明了位置擾動機制是如何在隱私保護與其所提供服務的準確性之間進行權衡的。文獻［11］提出一種基于差分隱私機制的位置數據發布模型。

如果直接將差分隱私應用到位置數據發布中，會存在以下問題［2-3］:首先，當直接利用差分隱私機制來保護位置信息時，由于位置數據集稀疏性的特點，則需要在查詢返回值中加入較大的噪聲量；其次，對于位置數據集，由于其敏感度［2］的測量與距離有關，如果運用傳統的差分隱私方法來計算敏感度，會涉及到位置點間的最大距離，其對應的敏感度也會相對較大；再次，傳統的差分隱私適合發布敏感度較小的聚合查詢，但對于一組位置點幾何質心的發布而言，改變單個位置點可能會極大影響其質心的位置。

3 滿足地理不可區分性的位置數據清洗算法

3.1 機制的檢索區域

定理2 設檢索區域是一個以O為圓心、直徑為dA的圓形區域A。給定實際位置x∈A，如果生成的近似位置落在區域A外，則重新在A∩G中生成近似位置，即:

其中:K為滿足地理不可區分性的機制，G為笛卡爾網格。如果對用戶感興趣區域內的任意位置t，至少有1-δ的概率，使得檢索區域A的圓心O=K(t)滿足:

當擾動機制K滿足式（9）時，則機制K滿足(?，δ)-效用［12］。

3.2 針對感興趣區域位置數據的清洗

以用戶實際位置x為圓心，假設用戶感興趣區域（Region Of Interest，ROI）的半徑為rI。一方面，當機制生成的近似位置位于ROI 范圍以內時，機制對服務器反饋的位置信息進行清洗，只將ROI范圍內的信息呈現給用戶；另一方面，如果生成的近似位置z落在感興趣區域以外時，仍然將該近似位置作為報告點，可能會造成反饋給用戶的查詢結果與其感興趣區域內的實際位置信息偏差較大。針對上述問題，提出基于用戶感興趣區域的地理不可區分性擾動方法，對位置數據進行清洗。

定理3 設ROI 的半徑為rI，當d(x，z)＞rI時，報告位置點M為:

式（10）表示將z投影到rI的邊界上，取x與z所在直線lx，z與感興趣區域邊界的交點M作為報告位置點，來代替近似位置z，如圖2所示。圖2展示了以x=(0，0)為中心，ε=1.25時的平面拉普拉斯概率密度函數，其中，d(x，z)=1.29，取rI=0.8。

圖2 投影近似位置到感興趣區域邊界Fig. 2 Mapping approximate locations to boundary of ROI

下面將證明該方法的可用性。

3.3 算法描述

根據實際位置坐標提供l/r-地理不可區分性。首先為了實現ε-地理不可區分性的隱私保護水平，算法通過調整隱私參數ε，來確保其所需的可用性程度。對于用戶的實際位置，采用擾動機制畫出半徑r和角度θ。然后，在指定區域內，通過對真實位置添加噪聲(r，θ)，生成近似位置z。如果z落在感興趣區域外時，將x投影到感興趣區域的邊界上，得到投影點M并報告該點。最后，對近似位置添加噪聲(r0，θ)，得到檢索區域A的圓心O。動態調整O的位置，使半徑為r的保護區域范圍內任一個近似位置z都在檢索區域內的概率至少為1-δ。

結合上述內容，基于用戶感興趣區域的地理不可區分性（Geo-indistinguishability based on the Region Of Interest，GROI）的擾動算法如算法1所示。

3.4 查詢結果定量分析

經過擾動后的位置數據主要用來進行地圖查詢。對各檢索范圍的位置數據進行統計，將真實位置的查詢結果分別與ε-地理不可區分性算法及本文算法的查詢結果進行對比。

本文涉及的查詢主要分兩種情況:

1）對實際位置點x生成的近似位置zi∈ROI。根據GROI算法，檢索區域A取決于近似位置zi，假設檢索區域內包含i個用戶想要獲取的地理位置點point1，point2，…，pointi，然后統計這些位置點Count(i)←Count[pointi∈A]。

2）生成的近似位置zi?ROI。結合3.1節的內容，由于檢索區域A的圓心位置取決于近似位置，即O←zi+(r0cosθ，r0sinθ)，為了能使A能夠包含ROI，對位置點進行清洗后，再執行1）操作。下面對清洗位置點能夠提升精確度進行理論分析。

4 實驗分析

4.1 檢索范圍對比分析

實驗在谷歌地圖查詢下進行，設定用戶實際位置位于堪薩斯州的國家一次世界大戰（World War I，WWI）博物館內，該用戶對博物館附近900 m 范圍內的酒店位置信息進行查詢。指定距該博物館250 m范圍以內的區域作為機制的保護范圍。

在定理3 保證方法可用性及隱私保護水平的前提下，實驗主要從對比查詢結果與真實位置數據在不同檢索范圍內的準確度展開，分析影響查詢結果準確度的因素，并在4.3 節的實驗中將GROI算法與ε-G算法進行了對比。

本實驗共生成4 個改變隱私參數大小的查詢:0.1、0.2、0.4、0.6，通過ε-G算法對用戶實際位置進行擾動。圖3中展示的是不同檢索范圍內查詢結果與真實位置數據的分布對比。

從圖3 中能夠看出，隨著檢索范圍的擴大，在近似位置得到的查詢結果會越來越接近實際位置。但當檢索范圍減小時，查詢的準確程度有所降低。

圖3 不同檢索范圍內實際位置與近似位置對比Fig. 3 Comparison between real location and approximate location with different query ranges

4.2 機制服務質量分析

本實驗主要測試影響算法查詢結果的因素。采用相對誤差（Relative Error，RE）計算查詢結果的精確度。設定用戶位于堪薩斯州的一家名為Rozzelle Court 的餐廳內，并分別查詢了0～0.8 km，及0.8～1.8 km 范圍內的餐廳及賓館位置分布比例如圖4 所示。圖4（a）展示了當ε= 1 時，改變保護范圍，隨著可區分性水平l的增大，分布比例的對比情況。圖4（b）展示了當r不變時，隱私參數ε分別為0.10、0.50、1.00，隨著l增大，在不同檢索范圍查詢結果的位置分布比例情況。

圖4 不同隱私水平下的查詢對比Fig. 4 Query comparison under different privacy levels

表1展示了與圖4（a）相應的誤差率對比情況。與真實數據相比，l分別為1.36、6.55 時，查詢結果的精確度分別降低了7.0%、15.0%。

表2 展示了圖4（b）相應的誤差率對比情況。與真實數據相比，l從0.313增大到2.104時，查詢結果的精確度降低了9.1%。

表1 ε-G算法相對誤差Tab. 1 Relative error of ε-G algorithm

表2 ε-G 算法查詢相對誤差Tab. 2 Relative error of ε-G algorithm query

4.3 清洗數據前后對比分析

通過以上實驗可以發現，ε-G算法對小范圍檢索結果影響相對較大?；诖?，從用戶感興趣區域的角度考慮，當生成的近似位置落在該區域以外時，如果仍然報告該近似位置，會導致查詢結果的誤差較大。針對上述問題，將用戶感興趣區域作為約束條件，依據GROI算法，對查詢結果進行清洗，在隱私程度不降低的情況下，查詢結果的位置分布比例如圖5所示。可以看出，相比ε-G算法，GROI算法的查詢結果更接近真實值。

對比GROI 算法與ε-G 算法的查詢結果，在ε=0.2，0.8時，查詢結果的相對誤差如表3 所示。改變檢索范圍，尤其是針對近距離范圍進行檢索時，GROI算法查詢結果的精確度比ε-G算法提升了至少2個百分點。

圖5 算法查詢結果對比Fig. 5 Query result comparison of algorithms

表3 兩種算法的查詢相對誤差對比Tab. 3 Query relative error comparison of two algorithms

根據前面章節，由于ε-G算法與GROI算法均提供εd(x，z)-隱私，所以兩者均引入O(|x|3)的隱私約束［13］。下面對兩種算法的運行時間進行對比，如表4所示。從表4可以看出，GROI算法根據ROI對數據進行清洗，并沒有造成額外的計算開銷。

表4 兩種算法運行時間對比Tab. 4 Running time comparison of two algorithms

5 結語

本文通過理論分析和實驗，證明了基于感興趣區域的地理不可區分性方法的可用性，并對比了在改變保護區域范圍及隱私參數的情況下，擾動算法查詢結果精確度的變化。當保護范圍的半徑固定時，隨著可區分性水平的減小，隱私程度增大，查詢結果的精確度有所降低，這取決于用戶對隱私程度的要求。通過實驗發現，地理不可區分性算法查詢與真實位置相距較遠的位置信息較為準確，而檢索小范圍內位置信息時，存在一定的誤差?；诖?，GROI算法將用戶的感興趣區域作為算法的約束條件，對查詢結果進行清洗，在隱私保護程度不降低的情況下，進一步減少查詢誤差。并通過實驗結果對比分析，表明了通過數據清洗后得到的結果精確度整體高于地理不可區分性算法。