張嘯劍　邵　超　孟小峰

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

差分隱私下一種精確直方圖發(fā)布方法

張嘯劍1邵超1孟小峰2

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

摘要基于分組的差分隱私直方圖發(fā)布得到了研究者的廣泛關注，組均值造成的近似誤差與噪音造成的拉普拉斯誤差之間的均衡直接制約著直方圖發(fā)布精度.針對現(xiàn)有基于分組的直方圖發(fā)布方法難以有效兼顧近似誤差與拉普拉斯誤差的不足，提出了一種滿足差分隱私的精確直方圖發(fā)布方法DiffHR(differentially private histogram release)；通過分析直方圖桶計數(shù)序列的排序有助于提升發(fā)布精度，利用Markov鏈蒙特卡洛(Markov chain Monte Carlo, MCMC)方法中的Metropolis-Hastings技術與指數(shù)機制，提出了一種有效排序方法，通過不斷置換2個隨機選取的桶以逐漸逼近正確排序；基于抽樣排序后的直方圖，提出了一種基于懶散分組下界的自適應貪心聚類方法，該方法的時間復雜度為O(n)，并且可有效均衡近似誤差與拉普拉斯誤差.DiffHR，GS，AHP方法在真實數(shù)據(jù)上的實驗結果表明，其發(fā)布精度上優(yōu)于同類算法.

關鍵詞差分隱私；直方圖發(fā)布；分組；拉普拉斯誤差；近似誤差

快速而又準確地獲取數(shù)據(jù)分布的梗概是數(shù)據(jù)分析與查詢的主要任務.直方圖是近似估計數(shù)據(jù)分布的主要技術之一，該技術使用分箱技術近似描述數(shù)據(jù)分布信息，將數(shù)據(jù)集按照某種屬性劃分成不相交的桶，每個桶由頻度或者計數(shù)表示其特征.直方圖的發(fā)布通常用來支持聚集查詢、范圍計數(shù)查詢以及數(shù)據(jù)挖掘等應用.然而，如果直接發(fā)布直方圖而不給予隱私保護，桶的真實計數(shù)會泄露個人的敏感信息.圖1為HIV疾病監(jiān)控中心確診患者的年齡分布，其中40歲患者為20人.如果攻擊者知道了除Alice之外其他19人的年齡情況，攻擊者利用圖1中的直方圖可以推理出Alice患了HIV疾病，進而泄露了Alice的個人隱私.

Fig. 1　Original histogram under age.圖1　年齡分布下的原始直方圖

為了阻止直方圖統(tǒng)計信息帶來的隱私泄露，在發(fā)布之前，需要對其進行隱私保護處理.目前差分隱私[1-4]已經(jīng)成為一種新的隱私保護模型，基于該模型出現(xiàn)了多種直方圖發(fā)布方法.其中，基于數(shù)據(jù)相關(data dependent)的分組方法是差分隱私下直方圖發(fā)布的主要技術，該技術利用組平均值近似估計每個原始計數(shù)，例如圖2給出圖1的3個分組結果{C1,C2,C3}，其中C1的{10,40,10}計數(shù)被其均值20代替.分組操作的優(yōu)點在于能夠比較準確地響應范圍查詢.然而，由于均值與拉普拉斯機制實現(xiàn)隱私保護，不可避免地產(chǎn)生均值造成的近似誤差與拉普拉斯噪音造成的拉普拉斯誤差.文獻[5-9]描述了目前基于分組的差分隱私直方圖發(fā)布常用方法，這些方法通常在固定分組個數(shù)的基礎上利用有損壓縮、V-優(yōu)化直方圖以及等寬劃分技術減少誤差對發(fā)布結果的影響，然而這些方法存在3個問題.

1) 分組時只是考慮局部近鄰的桶計數(shù)(例如文獻[5-7])，而無法度量全局計數(shù)的近鄰關系，這種類型的分組無法均衡近似誤差與拉普拉斯誤差，導致所發(fā)布直方圖的精度比較低.例如，在圖1直方圖中，盡管桶10與桶30的計數(shù)值一樣，它們不能被單獨放在一個分組中，除非桶20也被放在該分組中.這通常會導致很大的近似誤差.

2) 分組時大都未考慮桶計數(shù)的全局順序性，進而無法聚集全局相似的計數(shù).例如，如果對圖1直方圖進行排序，則桶10，30，60由于計數(shù)值相同而被分到同一組，進而可以減少近似誤差帶來的影響.雖然文獻[8]采用了排序，但是其采取固定分組策略卻很難均衡近似誤差與拉普拉斯誤差；同樣文獻[9]采用簡單的噪音排序也會導致不準確的結果.

3) 文獻[5-9]中分組方法的時間復雜度大都是O(kn2)或者O(n2)，例如AHP，GS方法.然而當直方圖維度很大時，這些方法的分組效率比較低.

總而言之，目前還沒有一個行之有效的方法兼顧直方圖發(fā)布的近似誤差與拉普拉斯誤差.為此，本文提出了一種融合抽樣排序與全局化分組的方法DiffHR(differentially private histogram release)，在滿足差分隱私的情況下，采用Metropolis-Hastings技術對直方圖進行抽樣處理，并實施自適應貪心聚類，實現(xiàn)近似誤差與拉普拉斯之間的均衡.

Fig. 2　Histogram after grouping.圖2　分組后的直方圖

本文主要貢獻如下：

1) 為了精確發(fā)布直方圖，提出了一種滿足ε-差分隱私的方法DiffHR，該方法利用基于Markov鏈蒙特卡洛(Markov chain Monte Carlo, MCMC)方法中Metropolis-Hastings技術與指數(shù)機制對直方圖進行抽樣處理，通過不斷置換2個隨機選取的桶以逼近直方圖的正確排序；

2) 為了有效均衡近似誤差與拉普拉斯誤差，提出了一種自適應的貪心聚類方法，該方法在滿足差分隱私的前提下，采用懶散分組下界有效處理大維度直方圖發(fā)布，且其時間復雜度為O(n)；

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

1相關工作

差分隱私擁有極強的保護能力和依賴嚴謹?shù)慕y(tǒng)計模型，這些特點使其得到廣泛研究和應用.當前學術界的應用著重關注差分隱私保護下的計數(shù)查詢[10]、直方圖發(fā)布[5]、子圖查詢[11]、高維數(shù)據(jù)發(fā)布[12]、關聯(lián)數(shù)據(jù)查詢發(fā)布[13]、機器學習[14]與數(shù)據(jù)挖掘[15]等.鑒于直方圖在數(shù)據(jù)分析中的重要性，研究者已經(jīng)提出了大量基于差分隱私的直方圖發(fā)布方法.Dwork等人[1]提出了拉普拉斯機制，成為后續(xù)研究的基石.Xiao等人[16]提出了名為Privelet的基于小波的直方圖發(fā)布技術.Privelet首先對輸入數(shù)據(jù)進行小波變換,然后對變換后的頻域數(shù)據(jù)添加多重對數(shù)噪聲.Hay等人[17]指出約束推理可以作為一種后置處理方法來改善直方圖的查詢準確性.Li等人[10]提出了矩陣機制.給定一組查詢，矩陣機制首先生成另外一組被稱為查詢策略的查詢，并在其之上添加拉普拉斯噪音，最后通過查詢策略的加噪結果來估算給定查詢的值.Rastogi和Nath[18]指出靜態(tài)時間序列數(shù)據(jù)可以通過只保留前k個傅里葉系數(shù)來以較小的近似誤差換取較大的拉普拉斯噪音降幅.2012年Yuan等人[19]提出了低秩機制，它通過計算給定負荷矩陣的低秩近似來回答批次查詢.上述方法大都屬于數(shù)據(jù)無關(data independent)的方法，優(yōu)勢在于能夠給出嚴謹?shù)臄?shù)據(jù)效用理論下限；但在實際數(shù)據(jù)上，這一系列方法均無法獲得理想數(shù)據(jù)可用性和效率，這一缺點引出了數(shù)據(jù)相關方法的研究.

所有數(shù)據(jù)相關的研究中最有希望的當屬基于分組的方法.Xu等人[5]提出了NoiseFirst和Structure-First算法.對于給定的分組個數(shù)，NoiseFirst先對每個桶添加獨立拉普拉斯噪音，之后利用V-優(yōu)化直方圖構造方法在加噪后的直方圖上尋找分組；StructureFirst則通過不斷應用指數(shù)機制來確定不同組之間的分界.文獻[5]主要缺陷在于只考慮相對于非隱私的V-優(yōu)化直方圖的近似誤差，而忽略了拉普拉斯噪音帶來的誤差，此外其要求分組數(shù)目已知的假設也通常難以滿足.Acs等人[6]改進了文獻[5]中要求給定分組個數(shù)的缺陷，設計了一種分級的二分法算法，利用指數(shù)機制動態(tài)確定分組，并通過大量實驗證實基于分組的方法可以取得比數(shù)據(jù)無關方法更好的準確性.應該指出，分組僅僅提供“本地化”的聚類，通常無法找到最優(yōu)聚類，故而無法找到近似誤差和拉普拉斯誤差間的最佳平衡來最小化整體誤差.Li等人[7]提出了一種基于分組策略的直方圖方法DAWA，然而，該方法同樣沒有采用排序和“全局化”聚類方法.Kellaris等人[8]考慮一個稍微不同的問題設置：一個用戶可以重復出現(xiàn)在多個桶中.他們首先利用采樣方法對直方圖進行排序，然后將所有桶分成大小相同的組.然而，選取固定的組大小通常無法很好地平衡近似誤差和拉普拉斯誤差，從而直接影響最終的發(fā)布精度.Zhang等人[9]提出了一種全局化聚類方法AHP，該方法取得了比文獻[5-8]中較好的發(fā)布結果；然而，AHP在進行排序時，只是采用簡單的噪音處理方式，而這種方式通常導致不準確的排序結果.因此，本文針對上述數(shù)據(jù)相關方法存在的缺陷，提出了一種精確直方圖方法DiffHR來均衡近似誤差和拉普拉斯誤差.

2定義與理論基礎

2.1差分隱私

差分隱私要求數(shù)據(jù)庫中任何一個用戶的存在都不應顯著地改變?nèi)魏尾樵兊慕Y果，從而保證了每個用戶加入該數(shù)據(jù)庫不會對其隱私造成危險.傳統(tǒng)的隱私保護模型如k-anonymity[20]，l-diversity[21]等通常對攻擊背景知識與攻擊模型給出特定的假設，而現(xiàn)實中這些假設并不成立.相比于傳統(tǒng)保護模型，差分隱私保護模型具有2個顯著的特點：1)不依賴于攻擊者的背景知識；2)具有嚴謹?shù)慕y(tǒng)計學模型，能夠提供可量化的隱私保證.本文所關心的是在發(fā)布直方圖時，如何使得所發(fā)布直方圖滿足差分隱私.

定義1. 設H={H1,H2,…,Hn}為原始直方圖桶計數(shù)序列，其中Hi表示第i個桶的計數(shù).H′={H1,H2,…,Hr-1,Hr±1,Hr+1,…,Hn}，H與H′相差一個計數(shù)，則二者互為近鄰關系.

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

(1)

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

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

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

(2)

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

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

(3)

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

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

A(H,Hi)=

(4)

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

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

2.2直方圖發(fā)布誤差

(5)

其中，LE(Ci)為采用拉普拉斯分布的方差度量，AE(Ci)為采用和方差度量.LE(Ci)與AE(Ci)可表示為

LE(Ci)=2(Δfε)2.

(6)

3差分隱私下精確直方圖發(fā)布方法

3.1基于分組的原則

基于第1節(jié)相關工作分析，在設計新的基于分組的直方圖發(fā)布方法時需要考慮的基本原則包括：

1) 針對全局分組問題，算法需要在滿足差分隱私的條件下盡量把全局相似的計數(shù)值分到一組；

2) 針對近似誤差與拉普拉斯誤差之間的均衡問題，方法應從“全局化”自適應分組出發(fā).

若實現(xiàn)原則1，最直接有效的方法是對H進行排序，這樣相似的計數(shù)均會緊密排列.然而，如果直接基于H進行排序后分組，則會破壞ε-差分隱私[8].如何在滿足差分隱私下準確排序是本文的第一研究難點.最簡單的方法是對直方圖每個桶添加獨立的拉普拉斯噪音，根據(jù)加噪的計數(shù)值排序[8-9]，然而此方法會導致不準確的排序.因此，本文采用Metropolis-Hastings抽樣技術[23]與指數(shù)機制使全局相似的計數(shù)值盡可能分到同一個組；針對原則2，在不給定組個數(shù)以及不固定組大小的情況下，本文設計了一種自適應地貪心聚類分組方法.基于上述分析，提出了兼顧上述2種原則的直方圖發(fā)布方法DiffHR，如算法1所示.

3.2DiffHR方法實現(xiàn)

DiffHR方法的具體描述如下：

算法1. DiffHR方法.

輸入：直方圖H={H1,H2,…,Hn}、隱私預算ε；

①ε=ε1+ε2；

④ fori=1 tondo

⑥ end for

⑦ fori=1 tondo

⑨ end for

Fig. 3　Sorted-based histogram after grouping.圖3　基于排序分組后的直方圖

該方法包括2個主要步驟：Metropolis-Hastings抽樣技術與貪心聚類.給定一個原始直方圖計數(shù)序列H，給定部分隱私預算ε1，利用Metropolis-Hastings抽樣技術與指數(shù)機制對H進行排序處理(行②)；而算法的關鍵步驟是抽樣處理后的聚類操作(行③)，其目的是為了降低每個分組本身的誤差err(Ci);最后，求每個簇的均值，利用剩余的隱私預算ε2為各個均值添加拉普拉斯噪音(行④～⑨).

為了深入理解DiffHR方法在分組過程中所引入的誤差，給出以下定理.

證畢.

3.2.1抽樣處理方法Metropolis-Hastings-Sort

基于排序后的直方圖進行分組操作，則可以把全局性相似的桶計數(shù)分到同一個組中，如圖3右圖所示，分組C1中3個桶{10,30,60}的計數(shù)為10且均值為10，分組C2中2個桶{40,70}的計數(shù)為20且均值為20，進而使得分組C1與C2的近似誤差為0.

然而，如果直接基于原始直方圖H中真實桶計數(shù)進行排序(例如圖3右圖所示)，會導致個人隱私泄露.因此，本文通過MCMC把直方圖H模擬成Markov鏈，然后利用基于指數(shù)機制的Metropolis-Hastings抽樣技術來近似逼近H的正確排序.

1) 基于指數(shù)機制的Metropolis-Hastings抽樣技術

根據(jù)指數(shù)機制的定義可知，直方圖中任意一個桶被抽樣的概率可以表示為

(7)

為了采用MCMC中的Metropolis-Hastings抽樣技術，首先給出相關描述信息.

定義4. 給定一個Markov鏈{Xt:t=0,1,…}，則其定義為

P(Xt+1=Hj|Xt=Hi,Xt-1=Hi-1,…)=

P(Xt+1=Hj|Xt=Hi).

該定義說明下一個狀態(tài)只取決于當前的狀態(tài).

設X為一個隨機變量，其在狀態(tài)空間H={H1,H2,…,H|H|}中進行取值.Metropolis-Hastings方法根據(jù)Markov鏈定義在空間H中抽樣出一個不可約的、非周期的Markov鏈，并使其服從平穩(wěn)概率分布π(X).基于Metropolis-Hastings的Markov鏈構造過程，實際上是狀態(tài)空間的轉換過程，而狀態(tài)轉換由轉換概率P決定.

P(Hi,Hj)=P(Xt+1=Hj|Xt=Hi)=

(8)

其中，Q(Hi,Hj)為建議概率分布，αHiHj表示接受概率，即表示狀態(tài)Hi以概率αHiHj跳轉到狀態(tài)Hj，以(1-αHiHj)的概率保持原來狀態(tài).

(9)

采用式(7)中的π(Hi)代替接收概率式(9)中的π(Hi)，則αHiHj重新表述為

(10)

根據(jù)式(10)可知，剩余的2個問題分別是如何設計打分函數(shù)u(H,Hj)與建議概率分布Q(Hi,Hj).

打分函數(shù)u(H,Hj)在指數(shù)機制中至關重要，我們希望那些打分高的桶計數(shù)被抽樣出來.給定直方圖H與當前狀態(tài)Hi，采用抽樣狀態(tài)Hj與當前狀態(tài)Hi的距離作為打分函數(shù)，如式(11)所示:

(11)

根據(jù)式(7)與式(11)可知，距離當前狀態(tài)Hi越近的桶計數(shù)越容易被Metropolis-Hastings方法抽樣.u(H,Hj)的敏感度為1，因為改變H的桶中任意一個計數(shù)，最多影響u(H,Hj)的變化為1.

同樣，構造一個合理的建議概率分布Q(Hi,Hj)對Metropolis-Hastings抽樣效果也至關重要.因此，根據(jù)不同狀態(tài)之間的距離來設計Q(Hi,Hj).給定一個距離閾值θ(實驗中設置θ=50)，可以求出與當前狀態(tài)Hi近鄰的狀態(tài)集合S1(Hi)={Hj:||Hj-Hi|≤θ}.假設S1(Hi)中的狀態(tài)是被等概率抽樣，則Q(Hi,Hj)=1S1(Hi).若Hi的距離不滿足θ的狀態(tài)稱之為Hi的非近鄰狀態(tài)，該集合為S2(Hi)={Hj:||Hj-Hi|>θ}.同理，Q(Hi,Hj)=1S2(Hi).

2) Metropolis-Hastings-Sort算法

基于上述分析，給出Metropolis-Hastings-Sort方法的具體實現(xiàn)細節(jié).

算法2. Metropolis-Hastings-Sort算法.

輸入：直方圖H={H1,H2,…,Hn}、隱私預算ε1；

① fori=1 tondo

② 隨機選擇一個桶計數(shù)作為種子計數(shù)；

④ 根據(jù)閾值θ，計算從當前桶計數(shù)Hi到近鄰桶Hj的跳轉概率Q(Hi,Hj)；

⑤ 以接收概率αHiHj接收桶Hj，其中αHiHj如式(10)所示；

⑥ if抽樣Markov鏈收斂到π(X) then

⑨ end if

⑩ end for

3.2.2基于懶散分組下界的方法Greedy-Clustering

證畢.

根據(jù)上述分析，給出Greedy-Clustering方法的具體實現(xiàn)細節(jié)，如算法3所示.

算法3. Greedy-Clustering算法.

輸出：聚類后所得分組集合C.

①C=?；

③ whilej

⑧ else

⑨C=∪Ci；

4隱私性與可用性分析

算法的隱私性主要從ε-差分隱私的概念和性質(zhì)的角度來證明，而可用性主要是利用最終的發(fā)布誤差進行度量.本節(jié)主要論證DiffHR是否滿足ε-差分隱私，并在算法3的基礎上與AHP以及GS算法進行可用性對比分析

4.1隱私分析

定理5. DiffHR滿足ε-差分隱私.

證明. 在DiffHR方法中，行②利用指數(shù)機制對原始直方圖H進行Metropolis-Hastings抽樣.相當于n個查詢，這n個查詢記為Q1.根據(jù)定義3可知，刪除原始H一條記錄，最多影響H中一個桶的計數(shù)，則ΔQ1=1，根據(jù)定理2可知行②滿足ε1-差分隱私.行⑦利用拉普拉斯機制計算每個組的噪音均值.由于每個組的大小已知，相當于查詢每個組的計數(shù)總和，即是查詢SUM值，該類查詢記為Q2.同理ΔQ2=1.根據(jù)定理1可知，行⑧滿足ε2-差分隱私.根據(jù)定理6差分隱私的順序組合性質(zhì)可知，DiffHR滿足(ε1+ε2)-差分隱私.由于ε=ε1+ε2，則DiffHR滿足ε-差分隱私.

證畢.

4.2可用性分析

可用性是度量隱私算法的另外一個標準，采用發(fā)布誤差進行度量.DiffHR方法發(fā)布直方圖的最終誤差由總體的近似誤差與總體的拉普拉斯誤差構成.接下來比較DiffHR與AHP以及GS所發(fā)布直方圖的可用性和準確性.DiffHR方法主要是基于懶散分組下界的聚類劃分方法進行與其他2種方法進行比較.

1) DiffHR方法與AHP方法比較

2) DiffHR方法與GS方法比較

盡管GS算法也是采用排序與全局化分組策略，但是該方法采用固定寬度劃分可能會導致發(fā)布準確性比較低.定理7可以解釋固定寬度劃分存在的缺陷.設GS等寬劃分寬度為w.

因此，根據(jù)定理7可知，GS方法在固定寬度劃分下所形成的組，總能夠分裂成2個非均勻的誤差較小的子組.相反，DiffHR卻能夠自適應地找出這些大小不一的子組，并使得最終發(fā)布誤差最小.

5實驗結果與分析

實驗所采用的3個數(shù)據(jù)集Waitakere[8]，Nettrace[10]，Search_log[5]被廣泛使用于直方圖發(fā)布.其中Waitakere是新西蘭2006年的人口街區(qū)普查數(shù)據(jù)，抽取7725街區(qū)作為直方圖的桶；Search_log合成了2004～2010年Google Trends與American Online搜索關鍵字為“奧巴馬”的搜索日志，該數(shù)據(jù)集包含32 768條記錄；Nettrace源自于一所高校內(nèi)聯(lián)網(wǎng)的IP層網(wǎng)絡軌跡數(shù)據(jù)，包含65 535條記錄桶，每個桶記錄校外主機鏈接校內(nèi)某個主機個數(shù).

結合上述3種數(shù)據(jù)集，采用均方誤差(MSE)度量DiffHR，GS以及AHP方法發(fā)布直方圖的準確性與可用性.設置隱私預算參數(shù)ε分別為0.01,0.10,1.00.

1) 直接添加拉普拉斯噪音與DiffHR方法處理對比

Fig. 4　Original histogram and Laplace noise.圖4　原始直方圖與拉普拉斯噪音

Fig. 5　Original histogram and DiffHR noise.圖5　原始直方圖與DiffHR噪音

針對上述3個數(shù)據(jù)集，設ε=0.01，直接對3種數(shù)據(jù)集添加拉普拉斯噪音，結果如圖4所示.其中灰色表示拉普拉斯噪音，黑色表示3種數(shù)據(jù)集中直方圖的真實計數(shù).可以看出，拉普拉斯噪音幾乎覆蓋了真實的計數(shù)值，因此，直接在直方圖上添加拉普拉斯噪音，其可用性很低，并且不能較好地響應范圍計數(shù)查詢.圖5中灰色為基于DiffHR方法產(chǎn)生的噪音，黑色同樣為3種數(shù)據(jù)集上的真實計數(shù).可以看出DiffHR方法對真實直方圖的擾動遠低于拉普拉斯機制，特別是在Search_logs與Nettrace有序的數(shù)據(jù)集上，DiffHR方法的噪音影響更小.

2) DiffHR與GS以及AHP的均方差(mean squared error,MSE)值對比通過改變范圍查詢的大小以及結合不同的隱私預算參數(shù)ε值來對比DiffHR，GS以及AHP方法響應范圍查詢的結果準確性.進而比較這3種算法所發(fā)布直方圖的可用性.由圖6～8可以發(fā)現(xiàn)，范圍查詢的MSE值越小表示發(fā)布直方圖的可用性越高.隨著范圍查詢大小的增加，以及參數(shù)ε從0.01變化到1.00，DiffHR，GS以及AHP方法的MSE值也在相應增加，其原因是大的查詢范圍以及小的ε值造成拉普拉斯噪音的累積，進而增加拉普拉斯誤差.對比著其他2種算法，DiffHR響應3種數(shù)據(jù)集上的范圍查詢時所造成的MSE比較小.特別是在Waitakere與Search_log數(shù)據(jù)集上，DiffHR所取得的范圍查詢響應精度是GS方法的將近10倍，是AHP方法的將近3倍.雖然在Nettrace數(shù)據(jù)集上，DiffHR方法與AHP方法取得近似的均方誤差，但是DiffHR方法仍然優(yōu)于AHP方法，原因是DiffHR方法采用了比AHP方法更準確的排序策略.

Fig. 6　MSE on Waitakere under different ε values (y-axis is in log-scale).圖6　Waitakere下ε變化時MSE的變化

Fig. 7　MSE on Search_logs under different ε values (y-axis is in log-scale).圖7　Search_logs下ε變化時MSE的變化

Fig. 8　MSE on Nettrace under different ε values (y-axis is in log-scale).圖8　Nettrace下ε變化時MSE的變化

6結束語

針對差分隱私行下基于分組的直方圖發(fā)布問題，本文首先對現(xiàn)有基于分組發(fā)布進行分析，并在此基礎上提出基于聚類分組算法DiffHR，引入滿足差分隱私的Metropolis-Hastings抽樣技術進行逼近直方圖正確排序.在排序的基礎上提出了一種基于懶散分組的聚類方法.從理論角度進行對比分析的結果顯示，DiffHR優(yōu)于同類算法.最后，通過真實數(shù)據(jù)集的實驗結果表明DiffHR能夠在滿足差分隱私的同時輸出比較精確的直方圖.未來工作考慮數(shù)據(jù)流下發(fā)布直方圖，設計滿足數(shù)據(jù)流特點的分組發(fā)布策略.

參考文獻

[1]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

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

[3]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

[4]Dwork C, Naor M, Reingold O, et al. On the complexity of differentially private data release: Efficient algorithms and hardness results[C]Proc of the 41st Annual ACM Symp on Theory of Computing (STOC 2009). New York: ACM, 2009: 381-390

[5]Xu J, Zhang Z, Xiao X, et al. Differential private histogram publication[J]. The VLDB Journal, 2013, 22(6): 797-822

[6]Acs G, Chen R. Differentially private histogram publishing through lossy compression[C]Proc of the 11th IEEE Int Conf on Data Mining (ICDM 2012). Piscataway, NJ: IEEE, 2012: 84-95

[7]Li C, Hay M, Miklau G, et al. A data- and workload-aware algorithm for range queries under differential privacy[J]. Proceedings of the Very Large Database Endowment, 2014, 7(5): 341-352

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

[9]Zhang X, Chen R, Xu J, et al. Towards accurate histogram publication under differential privacy[C]Proc of the 14th SIAM Int Conf on Data Mining (SDM 2014). Philadelphia, PA: SIAM, 2014: 587-595

[10]Li C, Hay M, Rastogi V, et al. Optimizing linear counting queries under differential privacy[C]Proc of the 41st Annual ACM Symp on Theory of Computing (PODS 2010). New York: ACM, 2010: 123-134

[11]Chen S, Zhou S. Recursive mechanism: Towards node differential privacy and unrestricted joins[C]Proc of the 2014 ACM SIGMOD Int Conf on Management of Data (SIGMOD 2014). New York: ACM, 2013: 653-664

[12]Zhang J, Cormode G, Procopiuc C M, et al. PrivBayes: Private data release via Bayesian networks[C]Proc of the 2014 ACM SIGMOD Int Conf on Management of Data (SIGMOD 2014). New York: ACM, 2014: 1423-1434

[13]Zhu T, Xiong P, Li G, et al. Correlated differential privacy: Hiding information in non-iid data set[J]. IEEE Trans on Information Forensics and Security, 2015, 10(2): 229-242

[14]Kusner M J, Jacob R G, Roman G, et al. Differentially drivate Bayesian optimization[C]Proc of the 32nd Int Conf on Machine Learning (ICML). Brookline, MA: Microtome, 2015: 918-927

[15]Su S, Xu S, Cheng X, et al. Differentially private frequent itemset mining via transaction splitting[J]. IEEE Trans on Knowledge and Data Engineering, 2015, 27(7): 1875-1891

[16]Xiao X, Xiong L, Yuan C. Differential privacy via wavelet transforms[J]. IEEE Trans on Knowledge and Data Engineering, 2011, 23(8): 1200-1214

[17]Hay M, Rastogi V, Miklau G, et al. Boosting the accuracy of differentially private histograms through consistency[C]Proc of the 36th Int Conf on Very Large Data Bases (VLDB 2010). New York: ACM, 2010: 1021-1032

[18]Rastogi V, Nath S. Differentially private aggregation of distributed time-series with transformation and encryption[C]Proc of the 2010 ACM SIGMOD Int Conf on Management of Data (SIGMOD 2010). New York: ACM, 2010: 735-746

[19]Yuan G, Zhang Z, Winslett M, et al. Low-rank mechanism: Optimizing batch queries under differential privacy[J]. Proceedings of the Very Large Database Endowment, 2012, 5(11): 1352-1363

[20]Samarati P. Protecting respondents’ identities in microdata release[J]. IEEE Trans on Knowledge and Data Engineering, 2001, 13(6): 1010-1027

[21]Machanavajjhala A, Kifer D, Gehrke J, et al. l-diversity: Privacy beyondk-anonymity[J]. ACM Trans on Knowledge Discovery from Data, 2007, 1(1): 1-36

[22]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

[23]Rubinstein R, Kroese D. Simulation and the Monte Carlo Method[M]. New York: Wiley Heyden Ltd, 2008

[24]Gelman A, Rubin D. Inference from iterative simulation using multiplesequences[J]. Statistical Science 1992, 1(4): 451-511

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

Zhang Xiaojian, born in 1980. PhD, lecturer in the College of Computer and Information Engineering, Henan University of Economics and Law. His main research interests include differential privacy, data mining, and graph data management.

Shao Chao, born in 1977. PhD, associate professor and master supervisor in the College of Computer and Information Engineering, Henan University of Economics and Law. His research interests include machine learning, data mining and visualization.

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

Accurate Histogram Release under Differential Privacy

Zhang Xiaojian1, Shao Chao1, and Meng Xiaofeng2

1(CollegeofComputer&InformationEngineering,HenanUniversityofEconomicsandLaw,Zhengzhou450002)2(SchoolofInformation,RenminUniversityofChina,Beijing100872)

AbstractGrouping-based differentially private histogram release has attracted considerable research attention in recent years. The trade-off between approximation error caused by the group’s mean and Laplace error due to Laplace noise constrains the accuracy of histogram release. Most existing methods based on grouping strategy cannot efficiently accommodate the both errors. This paper proposes an efficient differentially private method, called DiffHR (differentially private histogram release) to publish histograms. In order to boost the accuracy of the released histogram, DiffHR employs Metropolis-Hastings method in MCMC (Markov chain Monte Carlo) and the exponential mechanism to propose an efficient sorting method. This method generates a differentially private histogram by sampling and exchanging two buckets to approximate the correct order. To balance Laplace error and approximation error efficiently, a utility-driven adaptive clustering method is proposed in DiffHR to partition the sorted histogram. Furthermore, the time complexity of the clustering method is O(n). DiffHR is compared with existing methods such as GS, AHP on the real datasets. The experimental results show that DiffHR outperforms its competitors, and achieves the accurate results.

Key wordsdifferential privacy; histogram release; grouping; Laplace error; approximation error

收稿日期：2015-04-17；修回日期：2015-10-19

基金項目：國家自然科學基金項目(61502146,61379050,U1404605,61202285)；國家“八六三”高技術研究發(fā)展計劃基金項目(2013AA013204)；河南省科技廳基礎與前沿技術研究項目(152300410091)；河南省教育廳高等學校重點科研項目(16A520002)；河南財經(jīng)政法大學校重大研究課題(201426)

中圖法分類號TP392

This work was supported by the National Natural Science Foundation of China (61502146,61379050,U1404605,61202285), the National High Technology Research and Development Program of China (863 Program) (2013AA013204), the Basic Research Program of Henan Science and Technology Department (152300410091), the Key Research Program of the Higher Education of Henan Educational Committee (16A520002), and the Key Research Program of Henan University of Economics and Law (201426).