不規則線段樹的差分隱私位置隱私保護方法

胡德敏，廖正佳

(上海理工大學 光電信息與計算機工程學院，上海 200093)

1 引 言

差分隱私[1]作為位置擾動中一個常用的方法，具有嚴格的推理和證明的隱私保證，攻擊者無論是否擁有背景知識[2]都無法推斷出一條真實的位置數據，日漸成為位置保護中最受歡迎的方法.

基于差分隱私的位置保護方法會犧牲數據效用，用戶在移動環境下連續查詢時，單個位置點或興趣點添加噪聲后，會出現噪聲疊加導致位置查詢精度和服務質量下降等問題.樹形結構的差分隱私[3,12]方法能拆分位置數據集以增強數據效用，并能在保護位置隱私的同時有效提高移動查詢精度.但規則樹形結構的差分隱私方法會造成大量無效零節點，數據結構過大，在查詢精度上還有進一步提高的空間.

因此在規則樹結構的差分隱私位置保護的基礎上，提出了不規則樹結構的差分隱私位置保護方法(Irregular Segment Tree Differential Privacy，ISTDP).該方法能有效解決差分隱私方法在移動環境下的連續查詢精度下降的問題，并能適應不同密度環境.將k-匿名機制[4]與差分隱私相結合，引入線段樹(Segment Tree)[5]的概念，形成匿名集后，使用不規則的線段樹結構對數據進行劃分；并將不規則線段樹中節點覆蓋率的差異加入對查詢精度的考量，推導出衡量最優不規則線段樹的估值函數；根據節點覆蓋率構造子樹的估值函數，從而得出較低的查詢誤差的線段樹作為最終的不規則線段樹；最后為每個節點分配具有較小誤差上界的Laplace隱私預算.

2 相關工作

Dwork[1]最先提出的差分隱私方法，目標是對位置數據加入拉普拉斯噪聲來模糊真實位置.現實中用戶多是處于移動環境中進行位置查詢，差分隱私方法免不了會使疊加的噪聲量影響查詢精度和數據的可用性.如何在隱私保護和查詢精度之間獲得較好的權衡，是研究者們一直努力的方向.

Hoa Ngo[6]提出了一種基于地理不可分辨性(差分隱私的廣義變體)的隱私定義，通過發布多個版本的Hilbert曲線生成最小匿名區.該方法只是優化了匿名區，并沒有改進差分隱私的噪聲疊加問題.文獻[7]主要思想是將數據轉換成系數，將位置數據映射成小波樹，然后添加拉普拉斯噪聲，缺陷是映射成的小波樹會產生大量無效節點，需要進一步壓縮.在基于樹結構的數據轉換中，文獻[8]提出了PLDP-TD算法，在底層軌跡數據庫上構建一棵個性化的噪聲軌跡樹，并根據每個子軌跡分配一個隱私級，添加隱私參數，但規則的樹結構造成數據結構過大算法效率低.文獻[9]提出了kd-standard方法，在kd-樹上進行了改進，利用差分隱私的指數機制和噪聲均值機制，保證數據加噪后查詢誤差最小.但是這些的方法存在的共同問題是，使用樹結構對數據進行轉換時，需要將樹映射成滿n叉樹的結構(如二叉樹，四叉樹等)，若興趣點數據量不充足的情況下，會產生大量為零的節點，因此需要進一步壓縮，才能保證查詢誤差較小，但是會造成算法復雜度較高.規則的樹形結構會使數據結構較大無用節點較多，查詢精度有進一步提高的空間.

本文以k-匿名機制為基礎(利用Hilbert曲線[10]形成匿名集)，采用不規則線段樹結構對數據進行優化.將不規則線段樹中節點覆蓋率的差異加入對查詢精度的考量，根據節點覆蓋率構造子樹的估值函數，從而得出較低的查詢誤差的線段樹作為最終的不規則線段樹，最后為每個節點分配具有較小誤差上界的Laplace隱私預算.提高了差分隱私的位置查詢精度和服務質量，并能適應不同密度環境.

3 相關概念

3.1 差分隱私

定義1.ε-差分隱私[1].對于任何兩個數據表T和T′，至多包含一個不同的記錄，對任意輸出S，S滿足S?Range(f),隨機函數f滿足：

(1)

則稱算法f滿足ε-差分隱私.

差分隱私的定義規定了任意兩個數據表經過差分擾動后，差異不超過給定的eε.對數據添加噪聲主要由Laplace機制[1]實現.

(2)

滿足Laplace分布的方差為2λ2，期望為0.由定義3可知，差分隱私的隱私強度與噪聲參數λ有關，λ越大，噪聲幅度越大，隱私保護強度就越高，但是數據可用性就越低.

定義3.Laplace機制的敏感度[1].敏感度是數據表T中任何單個元組數據變化時f中的最大變化.

(3)

根據Laplace機制的敏感度Δf、噪聲參數λ、差分隱私參數ε，可以得出以下三者之間的關系：

3.2 線段樹

定義5.線段樹[5].線段樹是一種二叉搜索樹，給定一個數據集D，若滿足以下條件的樹，則稱該樹為D所對應的線段樹：

2)令x的孩子節點為child(x)，對于孩子節點child(x)要滿足：

(4)

(5)

若child(x)為空集，則x為葉子節點.

對于普通加噪方式來說，為每條位置數據添加噪聲后的敏感度Δf為1，由于查詢會涉及到O(l)個數據，因此噪聲方差和為O(lλ2).對于數據進行過基于線段樹的劃分后，線段樹的深度為O(logl)，根據廣義敏感度及其推理可知，深度為O(logl)的線段樹的敏感度為Δf=O(logl).對于不規則線段樹來說，設每個節點的扇出最大為d，因此噪聲方差和為：

∑2λ2=O(2dloglλ2)=O(dloglλ2)

(6)

運用不規則線段樹劃分數據加噪后的噪聲方差可以有效的減小誤差，提高查詢精度.

定義6[11].對于查詢Q=[left,right]，要求滿足一下條件的節點集合A：

3)|A|最小

目的是要找到覆蓋Q的查詢區間且最少的不相交的節點.需要注意的是，對于覆蓋節點x的查詢Q=[left,right]，Q不能覆蓋其父節點.

4 不規則線段樹的差分隱私位置隱私保護方法

4.1 計算節點覆蓋率

(7)

由于敏感度即為樹高，則可以進一步將研究查詢方差改為研究查詢方差的期望，對于查詢Q的方差的期望為：

(8)

利用Hilbert曲線劃分出k-匿名集后，將匿名集映射成不規則樹結構.如圖1，用戶在P9處形成的(k=3)匿名集的H值為<0,1,2,3,4>，將該H值進行線段樹的轉化后，該線段樹的區間為[0,4]，長度為5.

圖1 Hilbert曲線形成的匿名集Fig.1 Anonymous sets formed by Hilbert curves

區間左端點不為1，因此，將區間往左移一個設為[1,5](離散化的值要從1開始).假設構造出的兩種不規則線段樹如圖2所示，分別計算線段樹節點的覆蓋率：

圖2 線段樹的節點覆蓋率Fig.2 Node coverage rate of segment tree

4.2 不規則線段樹的估值函數

根據定義6對線段樹的查詢覆蓋區域的要求可知，根節點僅有一個查詢區域能覆蓋，即為該所在區域本身；對于非根節點x，其父節點為p，要求滿足left(p)≤left(x)≤right(x)≤right(p)，由于查詢區域Q=[left,right]不能覆蓋父節點p，因此查詢區域要求滿足以下兩個條件，見圖3.

圖3 節點查詢區域區間Fig.3 Node query qrea section

P1(x)=

滿足條件②的節點覆蓋率為：

P2(x)=

滿足條件的查詢區間Q算了重疊的一段區間，如圖3(c).重疊區域為(left(p)+1≤left≤left(x))∧(right(x)≤right≤right(p)-1)，該重疊區域的節點覆蓋率為：

根據容斥定理，非根節點的節點覆蓋率為P1(x)+P2(x)-P重(x).結合查詢方差的期望，定義不規則線段樹的估值函數為：

(9)

圖4 節點b不同區間分布的線段樹Fig.4 Segment tree with different section distribution of node b

此時節點b的估值函數為16.8，因此可以通過計算節點的估值函數，篩選出具有較低估值函數的線段樹.不規則線段樹的差分隱私位置保護方法的整體算法如下：

算法.不規則線段樹的差分隱私位置保護算法

輸入：生成的匿名區ASR，匿名集u.s

輸出：擾動后的匿名區域ASR′

1. order(H(ASR.POI));//將匿名區ASR中單元格區域的H值按從小到大排序

2. find Hmax,Hmin in H(ASR.POI);//找到ASR中H值的最大值Hmax和最小值Hmin，形成查詢區間[Hmin,Hmax]

3. if Hmin==0

4. Hmin =1,Hmax=Hmax+1;//若Hmin為0，將區間右移，變成[1,Hmax+1](保證左端點大于等于1)

5. end if;

6. if(left(x)！=right(x))//如果左端點不等于右端點，則遞歸劃分子線段樹

7. min=V(2,left(x),right(x));

8. m=2;//ary的值2 ary 20，先記錄第一個值，接下來循環找出估值函數V(2,left(x),right(x))最小的子線段樹

9. for(vari=3;i<=20;i++)

10. ary=i;

11. value=V(ary,left(x),right(x));

12. if(value

13. min=value;

14. m=ary;//記錄下最優子線段樹的扇出m

15. end if;

16. end for;

17. else break;//如果左右端點相同，則不用繼續劃分，該節點為葉子節點，否則重復步驟6-17

18. end if

5 實驗結果與分析

將不規則線段樹的差分隱私位置保護方法(ISTDP)、m叉平均樹的差分隱私位置保護方法(MATDP)[12]以及對提高差分隱私查詢精度有代表性的哈爾小波零樹壓縮算法(EHWT-DP)[7]進行對比實驗.針對不同地理密度的環境、不同的總隱私預算ε、不同匿名集規模等條件下，主要從查詢的誤差(方差)、算法運行時間等方面評價算法的查詢準確性以及算法運行效率.

5.1 實驗數據與環境

實驗環境為 Inter?CoreTMi5，windows7 操作系統，8GB 內存，算法是 Eclipse環境下基于Java 編寫.本章實驗使用了兩個數據集進行對比：第一個是由infochimps大數據網站提供的美國48個大陸州的地標位置組成的地標，數據分布較密集，約有870k個數據點，實驗中簡稱為“landmark”；第二個為美國存儲設施位置數據，包括國家連鎖存儲設施，以及本地擁有和運營的設施，數據機較稀疏，約有9000個數據點的，簡稱“storage”.

實驗中將查詢方差的期望作為一項對誤差的衡量標準，并且也將會與第三章中提出的m叉平均樹的差分隱私方法進行對比，對比其查詢誤差的大小.實驗中使用移動對象生成器，生成30km/h的300個移動用戶，設查詢總時間為 30min，查詢間隔為 5min，因此所有用戶一共要發起約1800次的連續查詢.

5.2 不同隱私參數ε和匿名集規模下查詢誤差的變化

主要測試的是隱私參數ε對查詢誤差的影響，因此在實驗中僅選擇在storage數據集中測試(密度較高的數據集實驗效果更明顯)，分別取ε在0.5、0.75與1.0，匿名集規模k取100～200的情況下，觀察ISTDP查詢誤差的變化，如圖5.

圖5 不同隱私參數ε和匿名集規模k下誤差的變化Fig.5 Errors in differnet privacy parameters and anonymous set sizes

5.3 查詢精度的對比

在該實驗中，ε分別選取0.5、0.75、1.0三個值，針對兩種不同地理環境的storage數據集與landmark數據集，測試ISTDP、MATDP與EHWT-DP三種算法的查詢精度的對比，結果如圖6.

圖6 不同算法查詢誤差的對比Fig.6 Comparison of query errors between different algorithms

從圖中可以看出，不論在哪種數據集下，本文的ISTDP方法的查詢誤差始終小于其他兩種方法，且查詢誤差僅有其他方法的20%.整體看來ISTDP在不同數據集中的查詢誤差波動幅度不大，基本上呈現緩慢增長的趨勢，這是由于分配的隱私預算具有最大的誤差上界.MATDP和EHWT-DP兩者受密度環境的影響較大，有的甚至有一個數量級的波動.可以得出結論，ISTDP比其他方法能更加不受地理環境密度分布的影響，且比其他減小查詢誤差的方法中查詢精度更佳，誤差較小，實驗結果符合理論預期.

5.4 算法運行效率的比較

圖7 算法運行時間Fig.7 Algorithm runtime

該實驗在storage數據集和landmark數據集中進行，取匿名集規模k=120，隱私參數ε=1.0，對比ISTDP、MATDP和EHWT-DP三種方法的算法運行時間，如圖7所示.

從圖中可以看出，ISTDP與MATDP在兩種數據集下的運行時間相差不大，這是因為這兩種算法是基于樹形結構的改進，僅與匿名集大小k有關，區域的網格劃分和Hilbert曲線填充都是在離線環境下進行，所以運行時間相較于EHWT-DP方法少.ISTDP的運行效率并沒有比MATDP提高多少，在ISTDP中主要時間復雜度是遞歸劃分子線段樹，所以該算法的時間復雜度為O(logk).ISTDP在MATDP的基礎上沒有對算法復雜度有大幅度的提高，但相比于EHWT-DP(時間復雜度為O(klogk))要提高了許多.

6 結束語

本文描述了不規則線段樹的差分隱私位置保護方法，詳細介紹了線段樹的基本概念，將不規則線段樹引入差分隱私方法中，能有效提高查詢精度，減小連續查詢時噪聲疊加帶來的查詢精度下降的問題.實驗驗證了該方法對地理環境密度的影響較小，能適應不同密度環境的LBS位置查詢服務，并且相對于其他提高差分隱私查詢精度的方法有更小的查詢誤差.