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

羅惠雯，龍士工*

（1. 貴州省公共大數(shù)據(jù)重點(diǎn)實(shí)驗(yàn)室（貴州大學(xué)），貴陽550000； 2. 貴州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴陽550000）

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

0 引言

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

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

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

3 滿足地理不可區(qū)分性的位置數(shù)據(jù)清洗算法

3.1 機(jī)制的檢索區(qū)域

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

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

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

3.2 針對感興趣區(qū)域位置數(shù)據(jù)的清洗

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

定理3 設(shè)ROI 的半徑為rI，當(dāng)d(x，z)＞rI時，報(bào)告位置點(diǎn)M為:

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

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

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

3.3 算法描述

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

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

3.4 查詢結(jié)果定量分析

經(jīng)過擾動后的位置數(shù)據(jù)主要用來進(jìn)行地圖查詢。對各檢索范圍的位置數(shù)據(jù)進(jìn)行統(tǒng)計(jì)，將真實(shí)位置的查詢結(jié)果分別與ε-地理不可區(qū)分性算法及本文算法的查詢結(jié)果進(jìn)行對比。

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

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

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

4 實(shí)驗(yàn)分析

4.1 檢索范圍對比分析

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

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

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

從圖3 中能夠看出，隨著檢索范圍的擴(kuò)大，在近似位置得到的查詢結(jié)果會越來越接近實(shí)際位置。但當(dāng)檢索范圍減小時，查詢的準(zhǔn)確程度有所降低。

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

4.2 機(jī)制服務(wù)質(zhì)量分析

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

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

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

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

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

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

4.3 清洗數(shù)據(jù)前后對比分析

通過以上實(shí)驗(yàn)可以發(fā)現(xiàn)，ε-G算法對小范圍檢索結(jié)果影響相對較大。基于此，從用戶感興趣區(qū)域的角度考慮，當(dāng)生成的近似位置落在該區(qū)域以外時，如果仍然報(bào)告該近似位置，會導(dǎo)致查詢結(jié)果的誤差較大。針對上述問題，將用戶感興趣區(qū)域作為約束條件，依據(jù)GROI算法，對查詢結(jié)果進(jìn)行清洗，在隱私程度不降低的情況下，查詢結(jié)果的位置分布比例如圖5所示。可以看出，相比ε-G算法，GROI算法的查詢結(jié)果更接近真實(shí)值。

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

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

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

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

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

5 結(jié)語

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