基于自適應網(wǎng)格的隱私空間分割方法

張嘯劍 金凱忠 孟小峰

1(河南財經(jīng)政法大學計算機與信息工程學院 鄭州 450002) 2 (中國人民大學信息學院 北京 100872) (xjzhang82@ruc.edu.cn)

信息時代的飛速發(fā)展，空間數(shù)據(jù)的獲取與收集變得尤為容易，例如移動用戶位置、GPS位置、家庭住址等數(shù)據(jù).通過對空間數(shù)據(jù)的分析，使得交通監(jiān)控、位置推薦等應用能夠提高自身的服務質量.然而，空間數(shù)據(jù)蘊含著豐富的個人敏感信息，在提供給第三方應用的同時，個人的敏感信息有可能被泄露.因此，如何在隱私保護的前提下，發(fā)布空間數(shù)據(jù)是當前基于位置服務的主要挑戰(zhàn)問題.匿名化[1]與差分隱私[2-4]是常用的隱私保護模型.然而，匿名模型由于對攻擊背景知識與攻擊模型給出過多特定假設，而不適合真實的位置服務.例如，文獻[5]指出在給出150萬條匿名后的用戶位置數(shù)據(jù)，在無任何背景假設情況下，隨機給出2個時空點，能夠甄別出50%用戶的敏感位置，隨機給出4個時空點，能夠甄別出97%用戶的敏感位置.不同于傳統(tǒng)的匿名化模型，差分隱私模型要求數(shù)據(jù)庫中任何一個用戶的存在都不應顯著地改變?nèi)魏尾樵兊慕Y果，從而保證了每個用戶加入該數(shù)據(jù)庫不會對其隱私造成危險.

近年來，出現(xiàn)了幾種基于差分隱私的網(wǎng)格空間分割方法.UG(uniform grid)[6]是利用網(wǎng)格結構劃分二維空間數(shù)據(jù)的早期代表方法，該方法首先對空間數(shù)據(jù)進行均勻劃分，然后再對每個單元格添加相應的拉普拉斯噪音.雖然UG能夠比較合理地設定劃分粒度，但卻沒有考慮單元格中計數(shù)的稀疏性*稀疏性是指空間中很多0值計數(shù)被劃分到同一單元格.與偏斜性*偏斜性是指對空間數(shù)據(jù)分布偏斜方向與程度的度量(參考表1)..例如，圖1是從1 000萬條紐約出租車數(shù)據(jù)中抽取到的100萬條數(shù)據(jù)，然后劃分成8×8個網(wǎng)格.查詢框Q1要求返回該范圍內(nèi)的計數(shù)值，其真實的計數(shù)為5.這8個單元格所添加的噪音值為8Lap(1ε)，則返回的噪音計數(shù)值為5+8Lap(1ε).如果設置ε=0.01，則8Lap(1ε)≈1 000，該噪音值扭曲了真實值5.因此，Q1的查詢結果可用性很低.DP-Where(differentially private where)[7]方法同樣采用均勻網(wǎng)格對移動人群的位置進行分割，但該方法的不足與UG類似.

為了彌補UG與DP-Where沒有兼顧網(wǎng)格單元的稀疏性與稠密性問題，AG(adaptive grid)[6,8]方法采用兩層網(wǎng)格結構劃分空間數(shù)據(jù)，該方法對第1層的每個單元格進行自適應地劃分，進而可以避免UG與DP-Where的稠密性劃分不足問題.雖然AG能夠自適應地劃分每個網(wǎng)格單元，然而該方法無法顧及用戶的查詢粒度.例如圖1中的Q2查詢所覆蓋的單元格c9至c12，單元格c9可以繼續(xù)分割，而c10，c11，c12由于本身的稀疏性無需再繼續(xù)分割，否則會導致更大的噪音誤差.上述3種方法均采用網(wǎng)格結構對空間數(shù)據(jù)進行分割，然而這些方法存在以下問題.

問題1. UG，AG，DP-Where方法僅僅在小的空間數(shù)據(jù)上進行了分割，支持相應的范圍查詢.然而，當數(shù)據(jù)點達到千萬級別時，這些方法的分割與響應查詢精度很低.

問題2. UG，AG等方法沒有很好地兼顧單元格的稀疏性、稠密性與偏斜性.盡管AG在稀疏性與稠密性作了改進，而該方法沒有考慮用戶的查詢粒度問題，有可能在第2層導致很大的查詢誤差.

總而言之，目前還沒有一個行之有效的方法同時克服上述兩種問題帶來的不足.為此，本文提出了一種融合抽樣與過濾的3層網(wǎng)格分割方法.在滿足差分隱私的情況下，采用伯努利抽樣技術對大規(guī)模原始空間數(shù)據(jù)進行抽樣.在構建網(wǎng)格結構過程中，利用閾值過濾單元格，判斷是向下繼續(xù)分割還是向上合并，進而實現(xiàn)高質量的空間數(shù)據(jù)分割.

本文主要貢獻有4個方面：

1) 為了解決問題1，提出了一種滿足差分隱私的抽樣方法，該方法利用伯努利抽樣技術對海量空間數(shù)據(jù)進行抽樣，該技術不但滿足差分隱私需求，而且能夠比較精確地抽取原始空間數(shù)據(jù).

2) 為了有效解決問題2，提出了3層網(wǎng)格分割方法STAG(sampling-based three-layer adaptive grid decomposition)，該方法利用閾值過濾技術判斷第2層中的單元格是否繼續(xù)分割.對于大于或等于閾值的單元格，采用自適應地向下分割成較細粒度的單元格；對于小于閾值且彼此連接的單元格，則向上重新組成較粗粒度的單元格.

3) 為了比較精確地相應不同粒度的范圍查詢，本文提出了一種約束推理方法，該方法利用平均化和一致性操作來增強查詢結果的精度.

4) 理論分析了STAG方法滿足ε-差分隱私，通過真實數(shù)據(jù)集上的實驗分析展示該方法在兼顧高可用性和準確性的同時，優(yōu)于同類方法.

1 相關工作

2 定義與問題

相比于傳統(tǒng)的隱私保護模型，差分隱私保護模型具有2個顯著的特點：1)不依賴于攻擊者的背景知識；2)具有嚴謹?shù)慕y(tǒng)計學模型，能夠提供可量化的隱私保證.

定義1. 設D={d1,d2,…,dn}為原始空間數(shù)據(jù)點.D′={d1,d2,…,dr-1,dr+1,…,dn}，D與D′相差一個數(shù)據(jù)點，則二者互為空間近鄰關系.

結合D與D′給出ε-差分隱私的形式化定義，如定義2所示：

定義2. 給定一個空間數(shù)據(jù)分割方法A，Range(A)為A的輸出范圍，若方法A在D與D′上任意分割結果G(G∈Range(A))滿足下列不等式，則A滿足ε-差分隱私.

Pr[A(D)=G]≤exp(ε)×Pr[A(D′)=G]，

(1)

其中，ε表示隱私預算，其值越小則算法A的隱私保護程度越高.

從定義2可以看出，ε-差分隱私限制了任意一個記錄對算法A輸出結果的影響.實現(xiàn)差分隱私保護需要噪音機制的介入，拉普拉斯與指數(shù)機制是實現(xiàn)差分隱私的主要技術.而所需要的噪音大小與其響應查詢函數(shù)f的全局敏感性密切相關.

定義3. 設f為某一個查詢，且f:D→d，f的全局敏感性為

(2)

文獻[2]提出的拉普拉斯機制可以取得差分隱私保護效果，該機制利用拉普拉斯分布產(chǎn)生噪音，進而使得發(fā)布方法滿足ε-差分隱私，如定理1所示.

定理1[2].設f為某個查詢函數(shù)，且f:D→d，若方法A符合下列等式，則A滿足ε-差分隱私.

A(D)=f(D)+Lap(Δfε)n，

(3)

其中，Lap(Δfε)為相互獨立的拉普拉斯噪音變量，噪音量大小與Δf成正比、與ε成反比.因此，查詢f的全局敏感性越大，所需的噪音越多.

文獻[17]提出的指數(shù)機制主要處理抽樣算法的輸出為非數(shù)值型的結果.該機制的關鍵技術是如何設計打分函數(shù)u(D,di).設A為指數(shù)機制下的某個隱私算法，則算法A在打分函數(shù)作用下的輸出結果為

(4)

其中，Δu為打分函數(shù)u(D,di)的全局敏感性，O為采用算法的輸出域.由式(4)可知，di的打分函數(shù)越高，被選擇輸出的概率越大.

定理2[17]. 對于任意一個指數(shù)機制下的算法A，若A滿足式(4)，則A滿足ε-差分隱私.

3 基于3層網(wǎng)格的自適應空間分割方法

3.1 空間分割的原則

基于相關工作部分的分析，在設計新的基于網(wǎng)格空間分割方法時需要考慮2項原則：

1) 針對大規(guī)?？臻g數(shù)據(jù)問題，所設計的分割方法應在滿足差分隱私條件下盡量能夠抽取充足數(shù)據(jù)點作為分割對象；

2) 針對現(xiàn)有網(wǎng)格分割方法無法有效兼顧用戶查詢與單元格粒度的缺陷，所設計的分割方法應根據(jù)查詢框所覆蓋單元格的粒度，確定是細粒度分割，還是粗粒度重組.

針對原則1與原則2，本文設計一種基于抽樣與過濾的3層自適應網(wǎng)格分割方法STAG.

3.2 STAG算法實現(xiàn)

本節(jié)描述STAG算法的具體實現(xiàn)細節(jié).

算法1. STAG算法.

輸入：D、隱私預算ε、分割閾值θ；

輸出：滿足差分隱私的自適應網(wǎng)格結構G.

①V<θ=?,V≥θ=?；*V<θ為小于θ單元格 組成的集合，V≥θ為大于或等于θ單元格 組成的集合*

② 以概率γ執(zhí)行多次伯努利實驗，獲得樣本

Dγ；

③εγ=ln(exp(ε)-1+γ)-lnγ；*由定理3

算出εγ*

④εγ=ε1+ε2+ε3；

⑤ 利用m2×m2網(wǎng)格均勻劃分Dγ產(chǎn)生集合Vm2×m2，標注每個單元格ci(ci∈Vm2×m2)為unvisited(ci)=0；*m2為劃分粒度，設置ci為未訪問單元格*

⑥ whileunvisited(ci)=0 do

⑦V<θ=Threshold-Filter(c(ci),<θ,ε2);

⑧V≥θ=Threshold-Filter(c(ci),≥θ,ε2);

⑨ 標注unvisited(ci)=1；

⑩ end while

算法1包括2個主要步驟：伯努利隨機抽樣(步驟②③)與網(wǎng)格分割(步驟⑤～).在利用網(wǎng)格對空間數(shù)據(jù)點進行分割時，如何確定劃分粒度m2非常關鍵，本文基于文獻[12]，設定：

其中，|Dγ|表示所抽取的具體樣本個數(shù)，p2為常數(shù).此外，分割網(wǎng)格存在3種重要操作：利用Threshold-Filter操作過濾第2層中每個單元格，進而形成V<θ與V≥θ集合(步驟⑦⑧).對于V≥θ，調用Down-Split操作向下細分，進而形成自適應網(wǎng)格G的第3層；對于V<θ，調用Up-Merge操作進行重組，進而形成G的第1層.算法STAG的具體思路可由圖2給予說明.

Fig. 2 An example for STAG algorithm圖2 STAG算法例子

例如給定Dγ=14個空間數(shù)據(jù)點，θ=3.在第2層，Dγ被分成3×3的單元格.單元格c7，c9被細分成2×2的單元格，如第3層所示.單元格c1，c2，c4，c5，c8被重組成g1，c3，c6被重組成g2，如第1層所示.

因此，本文的目標是根據(jù)范圍查詢的粒度不同，利用STAG方法生成3層網(wǎng)格來自適應相應查詢，并使得查詢結果具有較高的精度.接下來介紹如何利用伯努利抽樣實現(xiàn)空間分割樣本的采集.

3.2.1 伯努利隨機抽樣過程

STAG算法的第1個重要步驟是伯努利隨機抽樣，該過程的操作細節(jié)如下：

1) 確定抽樣概率γ；2)以γ對D做伯努利實驗，如果實驗成功，則獲得空間樣本，否則放棄該樣本;3)計算出整個空間分割所需的隱私代價εγ(算法1步驟②所示).而該過程的關鍵在于如何使得抽樣過程滿足差分隱私.文獻[18]給出的定理3說明該過程滿足ln(1+γ(exp(ε)-1))-差分隱私.

定理3. 給定一個數(shù)據(jù)D，令算法A在D上滿足ε-差分隱私.如果算法Aγ操作包括：以概率γ從D中抽取樣本獲得Dγ，然后A作用于Dγ.則Aγ滿足ln(1+γ(exp(ε)-1))-差分隱私.

3.2.2 Threshold-Filter閾值過濾

通過閾值θ過濾單元格噪音計數(shù)能夠提高最終的范圍查詢精度.然而，θ的選擇至關重要，θ過大導致稠密單元格分割不徹底，θ過小導致稀疏單元格重組不夠充分.本文利用指數(shù)機制與高通濾波設計2種閾值過濾方法.

1) 基于高通濾波的閾值過濾

高通濾波技術是通過經(jīng)驗值確定過濾閾值，例如設置θ=η×lb(|Dγ|ε2)[19].當所需的隱私代價ε2給定后，θ直接有經(jīng)驗值η來確定.本文的高通濾波技術如算法2所示.

算法2. Threshold-Filter-HP算法.

輸入：m2×m2個單元格組成的集合Vm2×m2、隱私預算ε2；

輸出：V<θ，V≥θ.

①θ=η×lb(|Dγ|ε2)；

② for eachc(ci)(ci∈Vm2×m2) do

⑥ else

⑧ end if

⑨ end for

⑩ returnV<θ，V≥θ.

算法2針對Vm2×m2中m2×m2個單元格的噪音計數(shù)值(步驟③)，采用閾值θ直接過濾，進而生成集合V<θ與V≥θ.盡管算法2可以有效減少網(wǎng)格稀疏和稠密帶來的影響，而經(jīng)驗值η的設置卻是不易，本文實驗中設置η=6.25.

2) 基于指數(shù)機制的閾值過濾

利用指數(shù)機制在m2×m2個單元格中抽取滿足閾值θ的單元格計數(shù)關鍵是設計合適的打分函數(shù).

設Sθ={cj|cj∈Vm2×m2,c(cj)≥θ}.根據(jù)Sθ設計相應的打分函數(shù)是u(Sθ,c(cj))=max(c(cj)-θ).u(Sθ,c(cj))的敏感度只與c(cj)相關，在原始數(shù)據(jù)集D中，添加或者刪除一個數(shù)據(jù)點，最多影響Vm2×m2中一個單元格計數(shù)，則可以得到Δu(Sθ,c(cj))=1.

算法3. Threshold-Filter-EM算法.

輸入：Vm2×m2、常數(shù)r、隱私預算ε2；

輸出：V<θ，V≥θ.

① 計算Sθ；

② for eachc(cj)(cj∈Sθ) do

③ 計算u(Sθ,c(cj))；

④ 在集合Sθ中無放回地抽取單元格計數(shù)c(cj)，且抽取概率滿足Pr[c(cj)]∝exp(ε2×u(Sθ,c(cj))4rΔu)；*參數(shù)r表示要抽取的單元格個數(shù)*

⑤ ifj≤rthen

⑥V≥θ=V≥θ∪c(cj);

⑦ end if

⑧ end for

⑨ for eachc(ci)(ci∈(Vm2×m2-Sθ)) do

算法3利用指數(shù)機制從Vm2×m2抽取r個單元格(步驟②～⑧)，形成集合V≥θ.對剩余(m2×m2-r)個單元格，利用拉普拉斯機制擾動，形成集合V<θ(步驟⑨～).

根據(jù)定理1與定理2可知，算法2與算法3均滿足ε2-差分隱私.實驗部分會對2種過濾方法給詳細對比分析.

3.2.3 Up-Merge向上重組過程

該過程是克服單元格稀疏性與提高查詢精度的重要技術.對于V<θ中的單元格計數(shù)，沒有必要采用Down-Split操作向下繼續(xù)細分，否則細分后會出現(xiàn)更多稀疏單元格.而如何針對V<θ中單元格計數(shù)重組粗粒度單元格是個很大挑戰(zhàn).

算法2與算法3中生成的噪音集合V<θ，只是避免在第2層中泄露其真實計數(shù).如果在V<θ直接進行重組，會導致第1層中的查詢噪音累加.例如，圖2中的g1=c1,c2,c4,c5,c8，若查詢Q恰好覆蓋g1，則響應結果6+5Lap(1ε2)，進而導致Q的查詢精度比較低.因此，本文給出數(shù)據(jù)依賴的Up-Merge方法.

設V<θ=c(c1),c(c2),…,c(cl)為所有小于θ的單元格真實計數(shù)組成的集合.如果直接在V<θ上進行重組，則會破壞差分隱私，因此，利用ε2尋找優(yōu)化的重組策略.利用ε1對重組后的組平均值添加噪音.

設V<θ被重組成k個分組C=g1,g2,…gk.在重組的過程中，會引入2種誤差:1)拉普拉斯機制引起的噪音誤差;2)平均值引起的重組誤差.設gi=c(cj),…,c(cm)(1≤i≤k,1≤j≤m≤l)為任意一個分組，則|gi|為gi的真實平均值.根據(jù)上述分析，可以得到定理4.

(5)

(6)

(7)

由|a+b|≤|a|+|b|可知，式(7)滿足不等式:

證畢.

根據(jù)定理4可以推理出定理5.

定理5. 設V<θ重新分成k個分組后形成C，則C攜帶的誤差滿足不等式:

證明. 由定理4可知，定理5成立.

證畢.

根據(jù)定理5可知，若使得最終的重組誤差最小，重組個數(shù)k值的大小至關重要.為了重組方便，設每次重組成k個分組的代價為RC(V<θ,C,ε1)，則RC(V<θ,C,ε1)可以表示成：

(8)

因此，如何在V<θ中找出一個最優(yōu)的重組集合C，并使得最小RC(V<θ,C,ε1)，即min(RC(V<θ,C,ε1))，是本文的主要目標之一.

為了避免重組過程破壞差分隱私，利用指數(shù)機制與隱私代價ε2來尋找最優(yōu)化的重組策略.根據(jù)式(4)可知，實施指數(shù)機制的關鍵是如何設計打分函數(shù).因此，本文根據(jù)式(8)設計打分函數(shù):

(9)

設O為V<θ中所有可能的由k個分組重組的集合.因此，我們希望在集合O中抽取代價較小的一種重組方法.基于上述分析，給出Up-Merge方法的具體實現(xiàn)細節(jié)，如算法4所示.

算法4. Up-Merge算法.

輸入：V<θ、隱私預算ε1和ε2；

①O=?；

② for eachk(1≤k≤l) do

③ 計算RC(V<θ,C,ε1)；

④ 生成一種重組形式C，使得O=O∪C；

⑤ 計算u(V<θ,C)=-RC(V<θ,C,ε1)；

⑥ end for

⑦ 以概率

抽取一種重組形式C；

⑧ for eachc(ci) (ci∈C) do

⑩ end for

算法4利用指數(shù)機制從集合O抽取打分最高的分組C(步驟②～⑦)，然后對C中的每個分組的均值添加拉普拉斯噪音(步驟⑧～⑩).例如圖2中，V<θ=c1,c2,c4,c5,c8,c3,c6被重組成g1與g2，2組的噪音計數(shù)分別為1.5 +Lap(1ε1)5，1 +Lap(1ε1)2.因此，利用重組結果響應查詢所帶來的噪音誤差較小.

算法4從集合O中抽取C與打分函數(shù)有關，但打分函數(shù)的敏感度卻是控制抽取質量的主要因素.

定理6. 設Δu為u(V<θ,C)敏感度，則Δu≤2.

則:

進而獲得Δu≤2.

證畢.

由于空間數(shù)據(jù)本身的稀疏性與偏斜性，使用網(wǎng)格劃分時會出現(xiàn)大量計數(shù)為0的局部單元格，例如圖1Q1查詢中的c1,c2,c3,c4單元格計數(shù)均為0.這些計數(shù)為0的單元格對實際的范圍查詢沒有作用，反而導致Up-Merge操作產(chǎn)生較多的重組誤差與噪音誤差.如果在第2層所有的單元格中找到那些彼此相連又滿足Up-Merge操作的單元格，則能夠避免0值的影響.為此，采用圖中的連通分量技術，提出了Boost-Up-Merge方法，如算法5所示：

算法5. Boost-Up-Merge算法.

輸入：V<θ，V≥θ；

④ for eachcido

⑥L=L∪ci；

⑦Si=Si∪ci；*Si表示不同的連通分量*

⑧visited(ci) =1；

⑨ end if

⑩ whileL≠? do

算法5采用連通分量與湊整(Rounding)技術提高Up-Merge的質量.算法5中的Rounding操作(步驟①)主要考慮大量0值的影響.該操作對V<θ中每個單元格計數(shù)過濾，如果原始真實計數(shù)為0，則直接把其添加的噪音湊整為0.算法5中步驟④～是計算所有的連通分量Si，針對每個連通分量，利用Up-Merge進行分割重組.例如，圖2中第2層為3×3的劃分網(wǎng)格，利用Boost-Up-Merge對其操作的結果如圖3所示：

Fig. 3 An example for Boost-Up-Merge algorithm圖3 Boost-Up-Merge算法例子

① 假設單元格中數(shù)據(jù)在均勻分布的情況下響應查詢，而數(shù)據(jù)實際分布與均勻分布存在偏差，該偏差帶來的誤差為均勻假設誤差，參閱文獻[6].

圖3中Noise Counts表的每個單元格計數(shù)通過閾值過濾與湊整操作產(chǎn)生Filtering Results表，其中灰色0是從Noise Counts表中c(c1)的噪音計數(shù)經(jīng)過湊整操作獲得的值.Connected Component是經(jīng)過算法5的步驟④～而獲得的連通分量，Grouping Results是調用Up-Merge操作獲得的重組結果.

3.2.4 Down-Split向下細分過程

該過程是為了克服單元格過于稠密帶來的非均勻假設誤差①.對于V≥θ中的單元格，采用Down-Split方法向下細分，進而形成第3層.而向下細分的關鍵是如何確定第3層劃分粒度.

算法6. Down-Split算法.

輸入：V≥θ、隱私預算ε3；

③m3×m3個單元格形成集合Vm3×m3；

④ for eachc(cj) inVm3×m3do

⑦ end for

⑧ end for

算法6首先把V≥θ中的單元格m3根據(jù)粒度劃分成m3×m3個單元格(步驟②～③);然后對m3×m3個單元格添加相應的拉普拉斯噪音(步驟④～⑦).

3.2.5 雙向約束推理

通過網(wǎng)格的3層自適應分割，可以在每層中獲得相應的噪音計數(shù)值.為了提高范圍查詢的精度，基于文獻[20]提出了一種約束推理的查詢求精方法，該方法的細節(jié)如下：

對m3×m3個噪音計數(shù)約束推理表達式為

3.2.6 STAG算法隱私性

主要從差分隱私定義角度，證明STAG算法如何滿足ε-差分隱私，如定理7所示.

定理7. STAG算法滿足ε-差分隱私.

證明. 設A是算法1去掉抽樣操作的方法，即是算法1去掉步驟②③.Aγ表示STAG算法本身.首先證明A滿足εγ-差分隱私.

A中只有步驟⑦⑧，步驟⑩用到隱私代價.步驟⑦⑧利用閾值過濾形成V<θ與V≥θ集合.利用定理1可知，步驟⑦⑧滿足ε2-差分隱私.步驟利用指數(shù)機制與拉普拉斯機制重組V<θ，根據(jù)定理1與定理2，以及結合差分隱私的并行性質[21]與順序性質[21]可知，步驟滿足(ε1+ε2)-差分隱私.同理結合定理1可知步驟滿足ε3-差分隱私.由εγ=ε1+ε2+ε3可知，A滿足εγ-差分隱私.

由于εγ=ln(exp(ε)-1+γ)-lnγ，結合定理3可知，算法Aγ滿足ln(1+γ(exp(εγ)-1))-差分隱私.把εγ帶入ln(1+γ(exp(εγ)-1))，則ln(1+γ(eln(exp(ε)-1+γ)-ln γ-1))=ε.因此，算法Aγ滿足ε-差分隱私，由于Aγ表示算法1本身，則STAG滿足ε-差分隱私.

證畢.

4 實驗結果與分析

實驗采用3個數(shù)據(jù)集NYC①，Beijing②，Checkin③，其中NYC數(shù)據(jù)集是2011年整個12個月內(nèi)紐約市出租車的乘車和下車地理坐標數(shù)據(jù)，該數(shù)據(jù)集包含1 000萬條信息；Beijing數(shù)據(jù)集是2011年2月份某一周內(nèi)北京市10 357輛出租車的乘車和下車地理坐標數(shù)據(jù)，該數(shù)據(jù)集包含1 500萬條信息；Checkin數(shù)據(jù)集從基于地理位置的社交網(wǎng)站Gowalla獲取，該數(shù)據(jù)集記錄了在2009年2月至2010年10月期間，Gowalla用戶簽到的時間和位置信息，包含6 442 890條記錄.3種數(shù)據(jù)集具體細節(jié)與可視化結果分別如表1與圖4所示.

Table 1 Characteristics of Datasets表1 數(shù)據(jù)集的屬性

結合上述3種數(shù)據(jù)集，類似于文獻[6]，采用相對誤差(relative error,RE)度量STAG，UG，AG，Kd-Stand，Kd-Hybrid方法的范圍查詢精度.相對誤差如式(10)所示：

(10)

本文設置伯努利隨機抽樣概率為10%，隱私預算參數(shù)ε的取值為0.1，0.5，1.0.實驗中范圍查詢Q的查詢范圍分別覆蓋NYC，Beijing，Checkin這3種數(shù)據(jù)集的[1%,5%]，[5%,10%]，[10%,20%]，在每種查詢范圍內(nèi)隨機生成5 000次查詢.本文用到的其他參數(shù)設置：θ=40，p2=5，η=6.25.

1) 基于NYC數(shù)據(jù)集的STAG，UG，AG，Kd-Stand，Kd-Hybrid算法RE值比較

Fig. 5 Results of range queries on NYC dataset圖5 NYC數(shù)據(jù)集范圍查詢結果

由圖5(a)～(c)可以發(fā)現(xiàn)，當查詢范圍固定時，ε從0.1變化到1.0，5種方法的RE均減少.然而，STAG的范圍查詢精度明顯優(yōu)于其他4種方法.在ε=1.0時，STAG所取得的查詢精度是AG與UG的將近2倍，是Kd-Stand與Kd-Hybrid的將近3倍.特別在查詢范圍是[5%,10%]且ε=0.1時，STAG所取得的查詢精度是UG，Kd-Stand，Kd-Hybrid的將近10倍.圖5(d)～(f)顯示，查詢范圍從[1%,5%]變化到[10%,20%]且ε固定時，STAG同樣優(yōu)于其他4種方法.當ε=0.1且查詢范圍為[5%,10%]時，STAG所取得的查詢精度是UG，Kd-Stand，Kd-Hybrid方法的將近9倍.其原因是NYC數(shù)據(jù)集的偏斜度比較嚴重(由表1可知，經(jīng)緯度偏斜值為-3.28-123.9)，而STAG利用抽樣與3層自適應網(wǎng)格能夠較好地避免偏斜與稀疏問題.

2) 基于Beijing數(shù)據(jù)集的STAG，UG，AG，Kd-Stand，Kd-Hybrid算法RE值比較

由圖6(a)～(c)可以看出，固定查詢范圍且變化ε時，STAG的查詢精度優(yōu)于其他4種方法.查詢范圍為[1%,5%]時，STAG的查詢精度優(yōu)于其他4種方法不到1倍.而隨著查詢范圍擴大，STAG的查詢精度優(yōu)勢比較明顯.特別是查詢范圍為[10%,20%]且ε=1.0時，STAG所取得的查詢精度是Kd-Stand與Kd-Hybrid的將近5倍，是UG的將近3倍.由圖6(d)～(f)顯示，查詢范圍從[1%,5%]變化到[10%,20%]且ε固定時，STAG所取得的查詢精度與AG差別不是很大，然而卻優(yōu)于剩余3種方法.特別是在ε=1.0時，STAG取得的查詢精度是UG與Kd-Hybrid的將近3倍，是Kd-Stand的將近6倍.

Fig. 6 Results of range queries on Beijing dataset圖6 Beijing數(shù)據(jù)集范圍查詢結果

3) 基于Checkin數(shù)據(jù)集的STAG，UG，AG，KD-Stand，KD-Hybrid算法RE值比較

圖7(a)～(c)顯示，變化ε且固定查詢范圍時，STAG的查詢精度明顯優(yōu)于其他4種方法，是AG與UG的將近2倍，是Kd-Hybrid的將近3倍.特別在ε=0.1且查詢范圍為[10%,20%]時，STAG所取得的精度是Kd-Stand的3倍之多.圖7(d)～(f)顯示，變化查詢范圍且固定ε時，STAG所取得的查詢精度同樣好于其他4種方法，其查詢精度是AG，UG，Kd-Hybrid的將近2倍，是Kd-Stand的將近11倍.其原因是Checkin數(shù)據(jù)的稀疏性很高(經(jīng)緯度偏斜值為139.334.93)，STAG利用抽樣、過濾以及向上重組技術避免了Checkin數(shù)據(jù)的稀疏性與偏斜性.

Fig. 7 Results of range queries on Checkin dataset圖7 Checkin數(shù)據(jù)集范圍查詢結果

4) 基于3種數(shù)據(jù)集的閾值過濾方法對比分析

本文2種閾值過濾技術主要受到參數(shù)η與r的影響.設置ε=0.5，查詢范圍為[5%,10%].圖8(a)～(c)顯示了η與r變化對范圍查詢相對誤差的影響.從圖8(a)～(c)可以看出，參數(shù)r從70%變化到90%時，3種數(shù)據(jù)集上的查詢誤差均在η=6.25時達到最小,此時對應的閾值θ=40.參數(shù)η從3.91變化到7.03時，參數(shù)r在Checkin數(shù)據(jù)上，值為80%時查詢誤差到達最小.而在NYC與Beijing 數(shù)據(jù)上，值為75%或者80%時，查詢誤差達到最小.因此參數(shù)η與r的設置直接制約著最終閾值過濾的效果.

6 結束語

針對差分隱私保護下基于網(wǎng)格空間分割存在的問題，本文結合現(xiàn)有的網(wǎng)格分割方法存在的不足，提出了基于伯努利隨機抽樣的3層網(wǎng)格分割方法.該方法通過向下細分與向上重組操作來提高空間范圍查詢精度，從差分隱私定義角度分析STAG滿足ε-差分隱私，最后通過3種真實的大規(guī)模數(shù)據(jù)集驗證了STAG方法的范圍查詢精度.實驗結果表明，STAG明顯優(yōu)于現(xiàn)有的同類方法.未來工作考慮動態(tài)環(huán)境下的隱私空間數(shù)據(jù)分割問題.

[1]Sweeney L. K-anonymity: A model for protecting privacy[J]. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2002, 10(5): 557-570

[2]Dwork C, McSherry F, Nissim K, et al. Calibrating noise to sensitivity in private data analysis[C]Proc of the 3rd Theory of Cryptography Conf (TCC 2006). Berlin: Springer, 2006: 363-385

[3]Dwork C. Differential privacy[C]Proc of the 33rd Int Colloquium on Automata, Languages and Programming (ICALP 2009). Berlin: Springer, 2006: 1-12

[4]Dwork C, Lei J. Differential privacy and robust statistics[C]Proc of the 41st Annual ACM Symp on Theory of Computing (STOC 2009). New York: ACM, 2009: 371-380

[5]Montjoye D, Hidalgo Y A. Unique in the crowd: The privacy bounds of human mobility[J]. Nature: Scientific Reports, 2013 (3): 1376-1376

[6]Qardaji W H, Yang W, Li N. Differentially private grids for geospatial data[C]Proc of the 29th IEEE Int Conf on Data Engineering (ICDE 2013). Piscataway, NJ: IEEE, 2013: 32-33

[7]Mir D J, Isaacman S, Caceres R, et al. DP-Where: Differentially private modeling of human mobility[C]Proc of the 2013 IEEE Int Conf on Big Data (BigData 2013). Piscataway, NJ: IEEE, 2013: 580-588

[8]To H, Ghinita G, Shahabi C. A framework for protecting worker location privacy in spatial crowdsourcing[J]. Proceedings of the VLDB Endowment, 2014, 10(7): 919-930

[9]Xu Jia, Zhang Zhenjie, Xiao Xiaokui, et al. Differential private histogram publication[J]. International Journal of Very Large Database, 2013, 22(6): 797-822

[10]Michael H, Ashwin M, Gerome M. Principled evaluation of differentially private algorithms using DPBench[C]Proc of the 2016 ACM SIGMOD Int Conf on Management of Data (ACM SIGMOD 2016). New York: ACM, 2016: 139-154

[11]Su Sen, Tang Peng, Cheng Xiang, et al. Differentially private multi-party high-dimensional data publishing[C]Proc of the 32nd IEEE Int Conf on Data Engineering (ICDE 2016). Piscataway, NJ: IEEE, 2016: 205-216

[12]Xiao Yonghui, Xiong Li, Yuan Chun. Differentially private data release through multidimensional partitioning[C]Proc of the 7th VLDB Workshop on Secure Data Management (SDM 2010). Berlin: Springer, 2010: 150-168

[13]Cormode G, Procopiuc C M, Srivastava D, et al. Differentially private spatial decompositions[C]Proc of the 28th IEEE Int Conf on Data Engineering (ICDE 2012). Piscataway, NJ: IEEE, 2012: 20-31

[14]Zhang Jun, Xiao Xiaokui, Xie Xing, et al. PrivTree: A differentially private algorithm for hierarchical decomposi-tions[C]Proc of the 2016 ACM SIGMOD Int Conf on Management of Data (ACM SIGMOD 2016). New York: ACM, 2016: 155-170

[15]Qardaji W H, Yang Weining, Li Ninghui. Understanding hierarchical methods for differentially private histograms[J]. Proceedings of the VLDB Endowment, 2013, 6(14): 1954-1965

[16]Kellaris G, Papadopoulos S. Practical differential privacy via grouping and smoothing[J]. Proceedings of the VLDB Endowment, 2013, 6(5): 301-312

[17]McSherry F, Talwar K. Mechanism design via differential privacy[C]Proc of the 48th Annual IEEE Symp on Foundations of Computer Science (FOCS 2007). Piscataway, NJ: IEEE, 2007: 94-103

[18]Li Ninghui, Qardaji W H, Su Dong. On sampling, anonymization, and differential privacy or,k-anonymization meets differential privacy[C]Proc of the 7th ACM Symp on Information, Computer and Communications Security (AsiaCCS 2012). New York: ACM, 2009: 32-33

[19]Michael H, Vibhor R, Gerome M. Boosting the accuracy of differentially private histograms through consistency[J]. Proceedings of the VLDB Endowment, 2010, 3(1): 1021-1032

[20]Lei Jing. Differentially privatem-estimators[C]Proc of the 25th Annual Conf on Neural Information Processing Systems (NIPS 2011). Berlin: Springer, 2011: 361-369

[21]McSherry F. Privacy integrated queries: An extensible platform for privacy-preserving data analysis[C]Proc of the 2009 ACM SIGMOD Int Conf on Management of Data (ACM SIGMOD 2009). New York: ACM, 2009: 19-30

ZhangXiaojian, born in 1980. PhD, associate professor in the School of Computer and Information Engineering, Henan University of Economics and Law. His main research interests include differential privacy, data mining, and graph data management.

JinKaizhong, born in 1991. MSc candidate in the School of Computer and Information Engineering, Henan University of Economics and Law. His main research interests include differential privacy, database, etc.

MengXiaofeng, born in 1964. Professor and PhD supervisor at Renmin University of China. Executive director of CCF. His main research interests include cloud data management, Web data management, native XML databases, flash-based databases, privacy-preserving, and etc.