結合四叉樹劃分的差分隱私位置發布算法

王 輝，廉芳芳，申自浩

(河南理工大學 計算機科學與技術學院，河南 焦作 454002)

1 引 言

近年來，基于位置的服務(Location-based Service，LBS)給人們帶來了極大的便利，但是隨著互聯網、移動終端和定位技術的不斷發展，通過社交網絡平臺進行交流的用戶迅速增長，導致社交網絡積累用戶行為的數據庫不斷擴大，其中包括了用戶的敏感信息，比如家庭住址、身份證號等，這些敏感信息一旦被不法分子獲取，那么會對用戶的利益構成極大的威脅[1].例如，2018年5月，美國軟件公司AgentRun意外暴露了成千上萬保單持有人的個人敏感信息，而究其原因是因為一個未加密的Amazon S3儲存桶，該儲存桶包含了大量的緩存數據，涉及數千名不同保險公司的個人敏感信息，包括類似Cigna和SafeCom-Insurance這樣的大型保險公司的客戶，遭泄露的信息包括保險單文件、健康和醫療信息、各種證件的掃描件以及一些財務數據，而一些文件除了顯示收入范圍、種族和婚姻情況以外，甚至還附有空白的銀行支票，使得用戶的財產安全遭到了嚴重威脅.因此，如何使用戶在確保敏感信息不被泄露的同時，正常使用社交網絡平臺是當前亟待解決的問題.

傳統的位置隱私保護技術大多基于k-匿名[2-5]、l-多樣性[6]和t-緊密型[7]，但其忽略了攻擊者對已知背景知識的掌握以及人口分布密度等的影響，從而不能充分保護LBS隱私安全.針對此問題，本文提出一種基于差分隱私[8-10]的位置發布算法，該算法使得數據集的計算結果對元素的變化不敏感，并將因為數據集的加入而導致的隱私泄露風險控制在可接受的范圍中，從而為用戶提供更好的位置服務.本文在位置點數量、位置點稀疏程度等方面進行實驗分析，證明本算法在隱私預算相同的前提下，有效的提高了對位置隱私的保護程度.

本文各個章節安排如下：第2節主要介紹常見的位置隱私保護算法；第3節對差分隱私相關問題進行定義；第4節提出了一種基于四叉樹劃分的差分隱私位置發布算法；第5節闡述實驗評估的結果；最后總結全文并展望未來相關研究工作.

2 相關工作

差分隱私[11，12]應用隨機算法對真實位置添加噪聲，生成的發布位置被驗證是有效的.目前差分隱私的研究主要分為設計滿足差分隱私的算法和減少差分隱私噪聲量.Li等人[13]針對用戶個性化偏好，提出了基于個性化的算法來構建用戶興趣區，但是利用該算法構建的用戶興趣區的隱私保護程度偏低；Yan等人[14]提出了一種基于差分隱私和關聯規則的用戶需求隱私保護框架，這些算法加強了對用戶隱私的保護，但是卻忽略用戶區內位置差異對隱私保護的影響.Li等人[15]利用分類樹及其算法將數據進行融合，實現了數據的分級化，但是該方法需要合理分配差分隱私預算，不僅會增加算法的運行時間，且當隱私預算分配不合理時，會導致查詢誤差的增加；Qardaji等人[16]通過迭代算法往樹中添加噪聲，雖然降低了查詢誤差，但是忽略了一些層次不滿足一致性約束的情況；Huo等人[17]針對若干種空間索引結構設計了滿足差分隱私的算法，但是沒有考慮對空間結構中噪聲的注入量.

針對上述算法的相關缺陷，本文提出了一種基于用戶興趣區的位置差分隱私發布算法DPLIP，該算法在興趣區中發布位置時，通過結合四叉樹的特性既考慮位置點數量對噪聲添加量的影響，也考慮位置點稀疏程度對噪聲添加量的影響.

3 問題定義

差分隱私的基本思想是對原始數據、原始數據上的函數以及查詢結果所構成的數據集中添加干擾噪聲來達到隱私保護的目的.差分隱私算法通常是在相鄰數據集概念的基礎上完成的，該算法能夠保證對相鄰數據集進行插入或刪除一條記錄的操作后，其產生同一結果的概率的比值接近于1.

定義1.相鄰數據集.給定兩個數據集A和B，其中A={ai：i=1，2，…，n}，B={bi：i=1，2，…，n}，當A和B滿足結構相同，有且僅有一條數據不相同時，則稱A和B為相鄰數據集，如式(1)所示.

A∪B={a1，a2，…ai，…，an，bi}，i=1，2，…，n

(1)

定義2.ε-差分隱私.給定相鄰數據集A和B，q是A和B上的隨機查詢算法，算法q在數據集A和B上任意輸出的結果為Z，若滿足式(2)，則稱算法q滿足ε-差分隱私.

(2)

其中，ε表示單位距離的隱私預算，表示隱私保護程度，且其越小越說明隱私保護程度越高.當ε→0時，隱私保護程度越高，說明兩個數據集的輸出結果越接近.

定義3.位置敏感度.假設任意函數q，其輸入為數據集A和B，輸出為d維實數向量，對于任意數據集A和B，有：

Δq=maxA，B‖q(A)-q(B)‖

(3)

Δq表示函數q的位置敏感度，表示加躁后對數據查詢的影響.q(A)-q(B)表示q(A)和q(B)之間的曼哈頓距離.注意，敏感度與數據集無關，只和查詢結果相關.

本文在對區域劃分方面采用的是基于四叉樹的劃分方法，區域劃分的程度取決于以下函數的相對權重值.

定義4.權重函數.在四叉樹中，假設每個節點表示為e(key，parent)，該節點的父節點表示為parent(Key，Sub)，則該節點的權重表示如下：

(4)

其中，key表示每個節點的權，即所在區域的位置點數 量；Key表示父節點的權，即父節點所在區域的位置點的數量.

對興趣區進行劃分后，需要在每個區域中添加噪聲以達到對真實位置的擾亂效果，在選擇擾亂算法時引入距離函數這個概念，定義如下：

定義5.距離函數.假設二維平面上的n個位置對象K=oi(xi，yi)：i=1，2，…，n，則任意兩點之間的距離可表示為：

(5)

其中，o1·x表示點o1的橫坐標o1·y，點o1的縱坐標；o2·x點o2的橫坐標，o2·y點o2的縱坐標.

4 位置差分隱私發布算法

4.1 獨立擾亂發布算法

Laplace機制是實現差分隱私保護最基礎的噪聲機制之一，該機制向返回結果中添加服從Laplace分布的隨機噪聲，使得結果滿足差分隱私，適合于對數值型數據的保護.

定理1.Laplace擾動[18].對于數據集A上任意函數q，若算法D的輸出結果滿足式(6)，則算法D滿足ε-差分隱私.

(6)

其中，Lap(Δq/ε)d表示添加的Laplace噪聲，噪聲變量與位置敏感度成正比，與隱私預算ε成反比.

在二維空間中，不可直接使用上述公式添加噪聲，本文給出了在單個位置的情況下，為滿足ε-差分隱私需要添加噪聲的概率函數.

假設真實位置集合為A，當添加噪音后的擾亂位置集合B中的元素滿足式(7)，則滿足ε-差分隱私.

(7)

其中，Pr[D(a)=b]表示真實位置a添加噪音后的位置是b的概率.當ε一定時，從式(7)可看出，Pr[D(a)=b]只與a和b之間的距離有關，并且Pr[D(a)=b]隨著兩者距離的增大而減小.

為了簡化表示，可以采用極坐標函數來實現，表示如下：

(8)

其中dist(a，b)表示a和b之間的距離，α表示a在極坐標下和極軸之間的夾角.

為了方便求解，將公式(8)分解到距離dist(a，b)和角度α上得到公式如下：

(9)

(10)

根據以上公式可以對真實位置集合A中通過添加噪音并生成隨機的擾亂位置集合B，以此達到位置隱私保護的目的，其中B{bi=ai+[dist(a，b)cosα，diat(a，b)sinα]}.

獨立擾亂算法是對真實位置A中每個位置分別添加Laplace噪聲，該算法滿足ε-差分隱私，其隱私保護程度是每個位置的隱私保護預算之和.當真實位置數量較少，且真實位置之間相距較遠時，本節提出的加躁算法效果比較理想，但其隱私保護程度會隨著集合中位置數量的增加而降低，且滿足ε-地理不可區分性[19]，即距離真實位置越近的擾亂位置越容易被發布.當真實位置距離較近且過多時，隱私程度會降低.

4.2 質心擾亂發布算法

本節通過對多邊形模型的質心添加噪聲的方法來解決上述問題，該模型的思想是：首先將受保護的點與其周邊符合要求的點組成多邊形，其次利用質心公式計算出其質心坐標，最后利用獨立擾亂算法的方式對其添加噪聲.

假設某用戶的軌跡圖中位置集合F表示受保護的位置點，位置集合A表示用戶歷史位置點的二維信息，將位置集合A中用戶訪問次數大于m的點加入到待定集合H中.

針對這些位置點，根據算法用受保護的點fi(xi，yi)(i=1，2，…，n)和從待定集合H隨機選取的點hi(xi，yi)(i=1，2，…，n)構成多邊形，并計算出其質心，質心I(x，y)的計算公式如式(11)所示.圖1以三角形為例.

圖1 構建三角形求解質心

(11)

在構造多邊形時，假設以受保護點fi(xi，yi)(i=1，2，…，n)為圓心，以R為半徑畫圓，構造多邊形的位置點應該落在圓中.需要注意的是R的值不宜過小，否則生成的多邊形的范圍過小，起不到模糊真實位置的作用.R值也不宜過大，否則會降低隱私保護程度.故需要設置Rmax和Rmin，則:

Rmax≤R≤Rmin

(12)

根據上文所講的方法，求得受保護位置點的集合H所對應的質心集合M，然后再通過Laplace算法對每個質點添加噪音，將所得結果加入數據庫C中.

4.3 位置差分隱私發布算法DPLIP

假設用戶興趣區是以r為邊長的正方形.當通過擾亂算法D生成的擾亂位置b在用戶興趣區內時，則將b添加到數據庫C中；當通過擾亂算法D生成的擾亂位置b不在用戶興趣區內時，則使用映射函數將b投影到興趣區上，并將投影所得的點添加到數據庫C中.

某一時刻，已知先驗概率P(t)-(a)和擾亂算法D，求解其后驗概率P(t)+(a).根據貝葉斯公式有：

(13)

則映射函數F表示如下：

(14)

基于用戶背景知識可知，在用戶興趣區中，用戶不是單一的在某個區域活動.當用戶頻繁訪問的位置點相距不近或者數量不多時，使用獨立擾亂算法的隱私保護程度較高；但是當訪問的位置點相距較近或者數量過多時，使用質心擾亂算法優于獨立擾亂算法.針對上述問題，本節提出了一種結合四叉樹劃分的差分隱私位置發布算法，該算法通過引入相對權重閾值δ和稀疏程度閾值?，將獨立擾亂算法和質心擾亂算法有效的結合在一起，從而加強對位置隱私的保護.

四叉樹的思想是將地理空間遞歸劃分為不同層次的樹結構.它將已知范圍的空間等分成4個相等的子空間，如此遞歸下去，直到樹的層次達到一定深度或者滿足某種要求后停止分割，如圖2(a)所示.傳統方法使用的是完全四叉樹，雖然其易于實現差分隱私分析，但是當時位置分布不均衡時，該方法會因為四叉樹高度過大造成大量的空節點的產生，導致總體注入過多噪聲.本文設計一種依據相對權重的四叉樹分裂方法，有效的減少了噪聲的注入.

圖2 基于四叉樹權重的區域劃分方法

第1步.根據定義4可以計算出。叉樹中各個節點的權重；

由于對區域的每次劃分所生成的孩子節點的下標和其父節點的下標都有關聯，故對節點下標情況做以下定義：狀態i表示所求節點對應的父節點的下標；狀態ij表示狀態為i的節點的子節點的下標，其中j=1，2，3，4.

第2步.計算每個區域相對興趣區的權重，計算如下：

W[e]=wij[e]×W[parent]，1≤j≤4

(13)

其中，wij[e]表示所求區域的權重.

第3步.將第2步計算結果和δ進行比較，結果如下：

(16)

其中，Divide表示區域劃分，True表示繼續劃分，False表示停止劃分，δ表示相對權重的閾值，當δ=1/6時，區域劃分情況如圖2(b)所示.

這就證明了滿足ESCA2的最優分配方法應該將剩余資源優先分給指標(s-Ai(s))/pi最大的部門即Rdam(s)法.注意到指標(s-Ai(s))/pi滿足Ax.7，所以時不變永久性離散資源分配的最優方法是Rdam(s)法.

第4步.以此類推，直到整個興趣區不能再被劃分為止

接下來的關鍵問題就是如何為每個區域選擇合適的擾亂算法.設V1=v1t：i=1，2，…，m，則該區域稀疏程度計算如下：

(17)

(18)

根據上述推導公式，可以計算出整個區域劃分情況.針對每個區域真實位置點分布情況，利用式(18)計算出其稀疏程度Si(i=1，2，…，n)，將其與稀疏程度閾值?進行比較，當前者小時，使用獨立擾亂算法，否則使用質心擾亂算法，從而使加躁后產生的擾亂誤差盡可能降低.

下面給出位置差分隱私發布算法DPLIP的主要流程.

1)建立以r為邊長的正方形作為用戶興趣區；

2)根據四叉樹思想將用戶興趣區劃分為若干個小區域，通過權重閾值δ來控制四叉樹分裂情況.

3)由式(17)和式(18)計算每個區域所對應的稀疏程度Si(i=1，2，…，n)，將其與稀疏程度閾值?進行比較，根據比較結果來進行擾亂算法選擇，將計算出的擾亂位置放入數據庫C中；

4)對于落到興趣區外的擾亂位置，利用式(14)將其映射到興趣區中，并將映射結果添加到數據庫C中；

5)將真實位置A添加到數據庫C中，然后從數據庫C中隨機挑選若干位置點作為發布位置Z.

結合四叉樹劃分的差分隱私發布算法的整體算法如下：

算法.位置差分隱私發布算法DPLIP

輸入：真實位置集合A，興趣區邊長r，t時刻前非興趣區的先驗概率P(t)-，差分隱私預算ε，Rmax，Rmin，相對權重閾值δ，稀疏程度閾值?

輸出：發布位置Z

1. nshoCount=Initialize()；

2. fornshoCount>δ；

3. Recursion(e)；//迭代劃分區域

4. end for

5. 計算Si；//式(18)

6. ifSi>? THEN

7. D=Choose(0)；//0表示獨立擾亂算法

8. else：

9. D=Choose(1)；//1表示質心擾亂算法

10. C_in=Disturbed(D)；

11. P(t)+=ChooseLoc(P(t)-)；//式(15)

12. C_out←CalRelease(P(t)+)；

13. C←(C_in∪C_out∪A)；

14. Z=RandomChoose(C)；

15. return Z；

4.4 誤差分析

獨立擾亂算法總誤差為每個真實位置添加的噪聲之和.假設每個位置消耗的隱私預算為ε，那么每個位置添加的噪聲的期望是E[dist(a，b)]i(i=1，2，…，n)，則：

(19)

由式(19)可知，獨立擾亂算法的總誤差是：

(20)

質心擾亂算法的總誤差除了考慮對質心添加噪音時造成的誤差，還要考慮真實位置和所求質心之間的誤差.假設每個位置消耗的隱私預算為ε，但實際上每個位置消耗的隱私預算為ε′/n，則對質心添加的誤差為Es[dist(a，b)]=2/n2ε，1≤s≤m，那么質心擾亂算法的總誤差是：

(21)

DPLIP算法是一種根據相對權重閾值δ和稀疏程度閾值?將獨立擾亂算法和質心擾亂算法結合在一起的算法，故總誤差是：

(22)

5 實驗與分析

將結合四叉樹劃分的差分隱私位置發布算法(DPLIP)、不規則線段樹的差分隱私位置保護方法(ISTDP)[20]以及對提高差分隱私查詢精度有代表性的哈爾小波零樹壓縮算法(EH-WT-DP)[21]進行對比實驗.針對相同隱私預算的條件下，主要從位置稀疏程度以及位置點數量等方面評估算法查詢的準確性以及算法運行效率.

5.1 實驗設置

DPLIP算法均采用MATLAB實現，實驗環境是8.00GB RAM的Windows7操作系統和3.60GHzCPU.本章實驗采用的數據集是landmark和storage真實數據集，其中前者是infochimps大數據網站提供的美國48個大州的地理坐標組成的地標，約880k個數據點；后者是美國存儲設施位置數據，數據點較稀疏，大約1萬個數據點.

5.2 不同位置稀疏程度下查詢誤差的變化

實驗設定ε=1，稀疏程度取1-13，針對不同位置稀疏程度的landmark數據集和storage數據集，測試DPLIP、ISTDP以及EHWT-DP共3種算法查詢誤差的對比，實驗結果如圖3所示.

圖3 不同位置稀疏程度下的誤差

由圖3(a)可以看出，EHWT-DP算法的總誤差最大，位置可用性最低，即位置安全性最低，這是因為EHWT-DP受位置稀疏程度影響較大；ISTDP算法的總誤差波動幅度不大，基本上呈現緩慢增長的趨勢，其位置可用性最好，這是因為該算法在隱私預算相同時，基本上不受位置稀疏程度的影響，因此其查詢精度更佳，誤差最小且波動幅度不大；本文的DPLIP算法介于兩個算法之間，并接近ISTDP算法的表現，這是因為該算法結合了獨立擾亂發布算法和質心擾亂發布算法，所以會受到位置稀疏程度的影響，所以位置可用性略低于ISTDP算法.圖3(b)在landmark數據集上顯示類似的結果.同時，3種算法在storage數據集上的表現優于landmark數據集上的表現，原因是storage的數據分布較密集，landmark的數據分布較稀疏，故前者的總誤差小于后者.

5.3 不同位置點數量下查詢誤差的變化

除了位置稀疏程度對3種算法有影響以外，位置點數量也是影響誤差的重要因素，本文通過實驗分析位置點數量對3種算法總誤差的影響.實驗設定ε=1，稀疏程度為2，實驗結果如圖4所示.

圖4 不同位置點數量下的誤差

從圖4(a)中可以看出隨著位置點的增加，3種算法的總誤差也隨之增加，其中，EHWT-DP算法的增幅最大，原因是該算法的單個位置點的查詢誤差較大，因此隨著位置點的增加，總誤差會呈線性增長；DPLIP算法和ISTDP算法由于單個位置的查詢誤差較小，故總誤差的增長幅度較小于EHWT-DP算法，同時由于本文的DPLIP算法中引入了質心擾亂發布算法，減少了噪聲的注入量，故該算法較優于ISTDP算法.圖4(b)在landmark數據集上顯示相似的結果.

5.4 算法運行效率的比較

該實驗在storage數據集和landmark數據集中進行，實驗設定n=200，稀疏程度為2，對比DPLIP算法、EHWT-DP算法和ISTDP算法的運行時間，結果如圖5所示.

圖5 算法運行時間

從圖5中可以看出，DPLIP算法和ISTDP算法的運行時間相近，這是因為這兩種算法是基于樹形結構的改進，僅和位置集合n相關，區域的網格劃分是在離線環境下進行的，所以運行時間較EHWT-DP算法少.DPLIP算法的運行效率并沒有比ISTDP算法的運行效率有明顯提高，但是對比EHWT-DP算法則提高很多.

6 總 結

本文提出的基于用戶興趣區的差分隱私保護算法的核心是在傳統的位置擾亂的基礎上，引入相對權重閾值和稀疏程度閾值，并提出一種基于用戶興趣區的位置差分隱私發布算法以及相應的算法DPLIP.該算法首先利用四叉樹的思想對用戶興趣區進行劃分；然后對劃分后的區域進行稀疏程度判斷；最后根據稀疏程度進行擾亂算法選擇.該算法相較于傳統的算法，既考慮位置點數量的大小對發布位置產生的影響，又考慮位置點稀疏程度對位置發布造成的影響，本文設計的算法有效的減少了添加噪聲后的擾亂位置與真實位置之間的總誤差.

對實驗結果進行分析與比較后，證明了在相同隱私預算的條件下，有效的減少了噪聲的添加量，從而保證用戶的隱私信息不被泄露.今后的研究中可繼續對DPLIP算法進行優化，以減少算法的運行時間和擾亂位置發布的可用性，更好地應用到位置發布服務中.