李昆明，王超遷，倪巍偉*，鮑曉涵

（1.江蘇方天電力技術有限公司智能電網(wǎng)服務中心，南京 210000；2.東南大學計算機科學與工程學院，南京 211189）

（?通信作者電子郵箱wni@seu.edu.cn）

0 引言

直方圖作為一種可以直觀展示數(shù)據(jù)分布的統(tǒng)計工具，在社交網(wǎng)絡分析、數(shù)據(jù)共享等領域有廣泛的應用。數(shù)據(jù)采集者收集用戶數(shù)據(jù)，匯總為直方圖發(fā)布給第三方數(shù)據(jù)挖掘者，數(shù)據(jù)挖掘者從統(tǒng)計直方圖挖掘有價值的知識，用于輔助決策。該過程中數(shù)據(jù)挖掘者為不可信角色，攻擊者可以結合背景知識與統(tǒng)計直方圖推斷用戶數(shù)據(jù)，導致用戶隱私泄露問題。

差分隱私［1］作為數(shù)據(jù)隱藏發(fā)布常用技術之一，被廣泛應用于直方圖發(fā)布問題，已經(jīng)提出的基于差分隱私直方圖發(fā)布方法［2-16］可以分為數(shù)據(jù)無關（data-independent）方法與數(shù)據(jù)相關（data-dependent）方法。在隱匿過程中無需考慮原始數(shù)據(jù)分布的方法稱為數(shù)據(jù)無關方法［2-4］。Hay 等［2］提出基于數(shù)據(jù)固有約束的約束推斷方法，用于提高添加拉普拉斯噪聲的直方圖的可用性；Xiao 等［3］提出一種基于小波變換的直方圖發(fā)布方法，首先對原始數(shù)據(jù)進行小波變換，基于變換后的數(shù)據(jù)添加拉普拉斯噪聲。鑒于數(shù)據(jù)無關方法沒有考慮直方圖桶統(tǒng)計值的分布，無法獲得具有較高可用性的發(fā)布直方圖，由此引出數(shù)據(jù)相關的直方圖發(fā)布方法研究。

數(shù)據(jù)相關研究代表性方法是基于分組的直方圖發(fā)布方法［5-9］：一方面，分組操作將引入近似誤差（Approximation Error，AE）；另一方面，差分隱私所添加噪聲會引入拉普拉斯誤差（Laplace Error，LE）。該類方法通過平衡近似誤差與拉普拉斯誤差，在滿足差分隱私的前提下發(fā)布與原始直方圖盡可能相似的直方圖。Acs 等［5］提出P-HPartition 算法，通過遍歷所有候選分割點，選擇誤差最小值對應劃分方案。Xu 等［6］提出NoiseFirst 與StructureFirst 方法，NoiseFirst 在原始直方圖添加噪聲后應用動態(tài)規(guī)劃求得k 個最優(yōu)分組；StructFirst 使用指數(shù)機制對原始直方圖求得k 個最優(yōu)分組，進而在組均值添加拉普拉斯噪聲。P-HPartition、StructureFirst 與NoiseFirst 都是基于局部分組的思想，僅考慮局部范圍內(nèi)桶的數(shù)值近鄰，無法度量全局計數(shù)的近鄰關系，不能很好地平衡近似誤差與拉普拉斯誤差。

針對局部分組存在的不足，發(fā)展出基于全局分組的直方圖發(fā)布方法?？紤]到在原始直方圖全局分組違背差分隱私約束［7］，Kellaris 等［7］提出通過行采樣或列采樣的方法獲得有序直方圖，進而通過固定分組獲取全局分組，該方法的缺陷在于固定分組不能較好地均衡近似誤差與拉普拉斯誤差，因此不能得到較高可用性的發(fā)布直方圖。張嘯劍等［8］利用馬爾可夫鏈蒙特卡洛方法中的Metropolis-Hastings 方法與指數(shù)機制獲得有序直方圖，采用貪心聚類獲得全局分組，但是采樣方法具有隨機性，無法保證排序正確性，貪心聚類也無法較好地均衡近似誤差與拉普拉斯誤差。Zhang 等［9］提出AHP（Accurate Histogram Publication）方法，對添加噪聲的直方圖排序并貪心聚類獲得全局分組，發(fā)布直方圖可用性受隱私預算參數(shù)影響較大，在隱私預算較小的情況下無法有效平衡近似誤差與拉普拉斯誤差。因此，已有全局分組的方法基于采樣或?qū)μ砑釉肼暤闹狈綀D處理無法獲得可靠的有序直方圖，并且通過固定分組或貪心聚類無法保證分組誤差均衡，限制了發(fā)布直方圖的可用性。

目前基于分組的直方圖發(fā)布方法雖然可以保證發(fā)布直方圖的隱私安全性，但是無法保證發(fā)布直方圖的精度，導致低可用性?，F(xiàn)有方法主要存在以下問題：

1）局部分組方法只能聚合位置近鄰的桶，無法聚合全局范圍內(nèi)數(shù)值相近的桶，不能均衡近似誤差與拉普拉斯誤差，導致發(fā)布直方圖精度較低。

2）全局分組方法通過對原始直方圖采樣或?qū)μ砑釉肼暤闹狈綀D排序逼近基于統(tǒng)計數(shù)值排序的原始直方圖的桶順序，具有較大的隨機性，無法保證發(fā)布直方圖的可用性。

3）全局分組方法通過固定分組或貪心分組逼近原始直方圖的最佳誤差平衡全局分組，可能陷入局部最優(yōu)，無法較好地均衡近似誤差與拉普拉斯誤差，導致發(fā)布直方圖可用性降低。

針對上述問題，基于全局分組思想，采用約束推斷方法對直方圖排序，設計基于動態(tài)規(guī)劃的分組方法，在添加噪聲的直方圖上實現(xiàn)最佳誤差平衡的全局分組，進而提出基于全局分組的高精度直方圖發(fā)布方法（High Precision Histogram Publishing，HPHP）。

本文主要貢獻如下：

1）針對已有方法無法保證添加差分噪聲的直方圖與基于統(tǒng)計值排序的直方圖具有相同的桶順序，采用約束推斷對添加有序約束的原始直方圖修正實現(xiàn)直方圖的排序。

2）提出基于動態(tài)規(guī)劃的分組方法，在添加噪聲的直方圖上實現(xiàn)具有最佳誤差平衡的全局分組，均衡近似誤差與拉普拉斯誤差，降低發(fā)布直方圖與原始直方圖的總體差異。

3）解析基于分組的方法可能達到的最佳誤差平衡，提出理論最小誤差Optimal 方法，并設計對比實驗，驗證所提方法的有效性。

1 問題描述及相關概念

1.1 問題描述

給定數(shù)據(jù)集D 存在屬性A，D 中任意一條記錄為t。發(fā)布者需要統(tǒng)計屬性A 不同取值的記錄數(shù)量，并整理為直方圖發(fā)布。若A 是離散屬性，每一個離散取值對應一個統(tǒng)計值；若A是連續(xù)值屬性，首先對A 離散化，將A 的取值區(qū)間劃分為若干個子區(qū)間，每一個取值區(qū)間對應一個統(tǒng)計值。對于兩種類型的屬性，直方圖發(fā)布方法是相同的，為方便起見，本文只討論A 是離散屬性的情況。假設攻擊者已經(jīng)得知數(shù)據(jù)集除t 以外所有記錄在屬性A 上的取值，結合直方圖，攻擊者可以準確地推斷元組t在屬性A的取值，導致隱私泄露。

例 表1 是疾病與相應患者數(shù)量的統(tǒng)計表，醫(yī)院需要將上述統(tǒng)計數(shù)據(jù)發(fā)布供分析人員應用。若共有340 人參與疾病統(tǒng)計，假如攻擊者已經(jīng)知道Alice 參與統(tǒng)計，并掌握其他患者的患病情況，可以準確地推斷Alice所患疾病。

表1 患者統(tǒng)計表Tab.1 Patient statistics

1.2 相關概念

定義1直方圖。假設數(shù)據(jù)集D 存在屬性A，A 取值范圍是V；對 于?t ∈D，?v ∈V，定 義Hi=count(t.A=v)，其 中count(x)表示統(tǒng)計數(shù)據(jù)集D 中符合條件x 的記錄數(shù)量?；趯傩訟 統(tǒng)計得到直方圖H={H1，H2，…，Hn}，其中n=|V|，Hi表示V中第i個屬性取值的統(tǒng)計值。

定義2ε-差分隱私［1］。若數(shù)據(jù)集D 與D'僅有一條記錄不同，那么稱D 與D'為鄰居數(shù)據(jù)集，對于D 與D'，查詢函數(shù)F滿足差分隱私，當且僅當F滿足：

其中Pr[F(D) ∈S]表示在D上執(zhí)行F的結果在S中的概率。

定義3全局敏感度［1］。給定查詢F：D →Rd與數(shù)據(jù)集D及其鄰居數(shù)據(jù)集D'，定義全局敏感度為：

定義4拉普拉斯機制［1］。給定查詢F：D →Rd，為了使F 滿足差分隱私，需要在其查詢結果上添加滿足拉普拉斯分布的噪聲。具體形式如下：

1.3 基本思路

圖1 為HPHP 流程框圖。HPHP 算法可以分為6 個步驟：①原始直方圖排序，增加有序約束；②添加拉普拉斯噪聲；③基于添加噪聲的直方圖，約束推斷處理；④基于處理后的直方圖，動態(tài)規(guī)劃分組獲得添加噪聲的直方圖上具有最佳誤差平衡的分組⑤原始直方圖根據(jù)分組，得到⑥基于每一個分組，組內(nèi)統(tǒng)計值被替換為添加拉普拉斯噪聲的組均值，進一步根據(jù)非負約束對添加噪聲后的統(tǒng)計值修正，得到發(fā)布直方圖

圖1 HPHP流程框圖Fig.1 Block diagram of HPHP process

2 基于差分隱私的高精度直方圖發(fā)布方法

通過分析已有方法，得出以下3點結論：

1）相較于局部分組，全局分組能夠更有效地均衡近似誤差與拉普拉斯誤差；

2）添加差分噪聲的直方圖與基于統(tǒng)計值排序的直方圖具有相同的桶順序，有利于全局分組；

3）在添加噪聲的直方圖上得到最佳誤差平衡的分組，可以更好地平衡近似誤差與拉普拉斯誤差。

針對1），本文所提方法采用全局分組的思想。針對2），已有方法通過對原始直方圖采樣或者對添加噪聲的直方圖排序逼近基于桶計數(shù)排序后原始直方圖的順序，以上兩種方法都帶有較大的隨機性，往往導致不準確的排序。針對該問題，本文首先對原始直方圖增加有序約束，添加噪聲后應用約束推斷［2］方法對直方圖修正，使添加噪聲的直方圖與基于桶計數(shù)排序的直方圖桶順序一致。針對3），由于不能直接對原始直方圖全局分組，需要在采樣序列或添加噪聲的直方圖上獲得全局分組，根據(jù)分組將原始直方圖劃分。已有方法使用固定分組［7］或貪心聚類［8-9］，無法使近似誤差與拉普拉斯誤差得到較好的均衡。針對該問題，本文提出自適應的動態(tài)規(guī)劃分組算法，在添加噪聲的直方圖上得到具有最小總誤差的全局分組。

基于上述分析，提出綜合考慮3 個結論的直方圖發(fā)布方法HPHP。該算法可以分為3個階段：

1）間接排序階段。針對直接對原始直方圖排序分組導致無法滿足差分隱私約束的問題，首先在原始直方圖添加有序約束并添加拉普拉斯噪聲，采用約束推斷對添加噪聲的直方圖約束推斷處理。

2）全局分組階段?；诘?）階段得到的有序直方圖，采用基于動態(tài)規(guī)劃的全局分組方法，獲得分組方案。

3）發(fā)布階段?；谇皟呻A段得到的分組方案，將原始直方圖分組并添加差分隱私約束，得到發(fā)布直方圖。結合直方圖箱統(tǒng)計值本身具有的非負約束，進一步對發(fā)布直方圖修正。

以下給出HPHP算法的3個階段的詳細分析。

2.1 約束推斷

HPHP第1階段為間接獲得有序直方圖，基于有序直方圖分組，能夠有效地降低近似誤差，更好地平衡近似誤差與拉普拉斯誤差。第1 階段通過對原始直方圖排序并添加噪聲得到滿足差分隱私約束的直方圖，基于添加噪聲的直方圖采用約束推斷對直方圖修正使其滿足有序約束一致性。約束推斷利用查詢固有約束對添加噪聲的數(shù)據(jù)修正，降低數(shù)據(jù)的噪聲量，固有約束包括有序約束、非負約束等。若有序原始直方圖為Hs，添加噪聲之后為采用文獻［2］的定理求解滿足有序約束的解，定理描述如下：

例如，當Hs具有非降序約束，若根據(jù)定理1 得到約束推斷詳細描述見算法1［17］。

算法1 ConstrainedInference。

定理2HPHP第1階段滿足差分隱私與約束一致性。

證明 在原始直方圖添加有序約束并添加服從Lap(1/ε1)的拉普拉斯噪聲滿足差分隱私。假設原始直方圖H={H1，H2，…，Hn}，添加有序約束后的直方圖Hs={Hs1，Hs2，…，Hsn}，H 與Hs的全局敏感度相同，因此添加的噪聲均服從Lap(1/ε1)分布；假設H 與Hs添加噪聲后得到的直方圖為都滿足ε1-差分隱私約束。由于排序發(fā)生于添加噪聲之前，因此攻擊者具有“查詢結果是有序的”的背景知識，若結果中出現(xiàn)了亂序，可以斷定查詢結果添加了噪聲，因此違背一致性。通過約束推斷處理，可以使重新有序，保持添加噪聲前后的有序一致性。 證畢。

2.2 動態(tài)規(guī)劃分組

HPHP 第2 階段為間接獲得分組方案。為了均衡近似誤差與拉普拉斯誤差，需要自適應地將添加噪聲的直方圖分組，使得所有分組的總誤差達到最小，總誤差由近似誤差與拉普拉斯誤差兩部分構成。為了定義分組誤差，首先給出原始直方圖與發(fā)布直方圖的誤差計算方法，定義如下：

定義5發(fā)布直方圖的誤差［8］。假設原始直方圖為H，發(fā)布直方圖為E(?)表示期望值。定義二者之間的誤差為：

式（4）通過計算原始直方圖與發(fā)布直方圖桶統(tǒng)計值的均方差之和得到發(fā)布直方圖的誤差，作為發(fā)布直方圖的一個子集，分組誤差也使用均方差公式計算，分組誤差

定理3［8］對于任意分組其具有誤差是分組的均值，是分組的近似誤差，是分組的拉普拉斯誤差。

HPHP 第2 階段基于約束推斷處理后的有序直方圖自適應獲得總誤差最小的全局分組方案，該問題適合使用動態(tài)規(guī)劃解決，問題描述如下：對于數(shù)組尋找若干分割點，使得分割后所有分組的總誤差最小，分組的誤差評價函數(shù)動態(tài)規(guī)劃解決方法的遞推公式給出如下：

動態(tài)規(guī)劃分組方法DPCluster 時間復雜度分析。DPCluster 首先需要求解q矩陣，若使用公式計算，時間復雜度為O(n3)，因此修改此時求解q 矩陣的時間復雜度降為O(n2)。得到q 矩陣之后，求解Q 矩陣，該過程時間復雜度為O(n2)。因此動態(tài)規(guī)劃分組算法的時間復雜度為O(n2)。

2.3 HPHP算法

基于前面兩節(jié)分析，可以在滿足差分隱私約束前提下間接獲得原始直方圖的全局分組方案。HPHP 第3 階段基于分組方案將原始直方圖分組，將分組中的統(tǒng)計值用組均值替換并分別添加拉普拉斯噪聲，得到發(fā)布直方圖。為了進一步滿足非負約束，提升發(fā)布直方圖的可用性，需要將發(fā)布直方圖中負值統(tǒng)計值替換為0。經(jīng)過HPHP三個階段的處理，可以得到滿足差分隱私的發(fā)布直方圖。

基于3 個階段的算法設計，可以在滿足差分隱私與一致性約束前提下獲得較高可用性的發(fā)布直方圖，進一步提出HPHP算法，詳細描述見算法2。

算法2 HPHP。

輸入 原始直方圖H={H1，H2，…，Hn}，隱私預算ε；

HPHP算法的3個階段對應如下：1）原始直方圖添加有序約束（第2）行），添加拉普拉斯噪聲（第3）行），對添加噪聲的直方圖約束推斷處理（第4）行）；該階段在滿足差分隱私與一致性約束前提下間接得到有序直方圖；2）基于處理后的直方圖，動態(tài)規(guī)劃分組獲得分組（第5）行）；通過在有序直方圖動態(tài)規(guī)劃得到的分組方案，比較接近直接在原始直方圖全局分組的分組結果；3）原始直方圖根據(jù)分組方案劃分（第6）行），統(tǒng)計值被添加拉普拉斯噪聲的組均值代替（第7）～10）行），非負約束處理（第11）行），得到發(fā)布直方圖；第3 階段得到發(fā)布直方圖，同時維護直方圖的非負約束一致性。

定理4HPHP算法滿足一致性約束。

證明 定理2 已經(jīng)證明HPHP 第1 階段滿足有序約束一致性；HPHP 第2 階段只涉及分組操作，因此不需要維護一致性；第3 階段通過非負約束將發(fā)布直方圖負統(tǒng)計值修正，滿足非負約束一致性。因此HPHP算法滿足一致性約束。證畢。

定理5HPHP算法滿足(ε1+ε2)-差分隱私。

證明 HPHP 算法滿足差分隱私約束。隱私安全性評價需要從ε-差分隱私的定義分析，結合算法2 的具體步驟，分析每一步是否存在隱私泄露。根據(jù)定理2 可知，算法2 的1）～4）行滿足差分隱私；5）～7）行為訪問原始直方圖；8）～10）行在組均值添加服從Lap(1/ε2)分布的拉普拉斯噪聲，滿足差分隱私；11）行非負約束處理的是添加噪聲后的發(fā)布直方圖，滿足差分隱私。綜上所述，HPHP滿足差分隱私。

算法2分別在第3）行與第10）行添加了拉普拉斯噪聲，兩次都是在原始直方圖添加噪聲，根據(jù)定理6，可以知道HPHP滿足(ε1+ε2)-差分隱私。 證畢。

定理6［8］設有一系列算法M1，M2，…，Mk分別滿足隱私保護預算為ε1，ε2，…，εk的差分隱私，若k 個算法作用于同一數(shù)據(jù)集D，則組合算法M(M1(D)，M2(D)，…，Mk(D)) 滿 足差分隱私。

2.4 理論最小誤差直方圖發(fā)布算法

通過分析基于分組的直方圖發(fā)布方法可能達到的最佳誤差均衡，設計了獲得理論最小誤差直方圖的Optimal算法。文獻［7］指出，在原始直方圖全局分組不能滿足差分隱私約束，直方圖H 與其鄰居H'相差一條記錄，二者的全局分組無法保持一致，無法滿足式（1），因此后續(xù)的工作都致力于間接獲得原始直方圖的全局分組。文獻［7］與文獻［8］使用采樣與貪心聚類近似原始直方圖全局分組，文獻［9］通過對添加噪聲的直方圖分組近似原始直方圖全局分組，本文所提方法同樣通過對添加噪聲的直方圖處理近似原始直方圖的全局分組。以上方法中，近似得到的全局分組與原始直方圖全局分組的相似度決定是否能夠合理平衡近似誤差與拉普拉斯誤差，進而決定發(fā)布直方圖的可用性。因此，在原始直方圖上排序并動態(tài)規(guī)劃分組，可以使近似誤差與拉普拉斯誤差達到最佳平衡，得到理論最小誤差直方圖。

基于以上分析，提出可以獲得理論最小誤差直方圖的Optimal 方法，方便與已有方法對比分析。需要說明，Optimal違反了差分隱私的定義，因此無法得到可發(fā)布的直方圖。Optimal方法詳細描述見算法3。

算法3 Optimal。

輸入 原始直方圖H={H1，H2，…，Hn}，隱私預算ε2；

定理7Optimal方法得到的發(fā)布直方圖精度是已有基于全局分組的直方圖發(fā)布方法的上界。

證明 基于全局分組的直方圖發(fā)布方法可以分為3 個階段：間接對直方圖排序，得到與基于統(tǒng)計值排序的原始直方圖相近的有序直方圖；基于有序直方圖，間接獲得與基于原始直方圖全局分組相近的分組方案；將原始直方圖分組，添加拉普拉斯噪聲發(fā)布。Optimal方法在第1階段直接對原始直方圖排序，相較于已有方法間接獲得有序直方圖，Optimal 方法得到的有序直方圖桶統(tǒng)計值次序更加準確；Optimal 方法在第2 階段直接對有序直方圖動態(tài)規(guī)劃分組，相較于已有方法在采樣序列或添加噪聲的直方圖上間接獲得分組方案，Optimal 方法可以得到原始直方圖上具有最佳誤差平衡的分組方案。綜上，可以推斷Optimal方法得到的發(fā)布直方圖精度是已有方法的上界。 證畢。

3 實驗分析

實驗所用硬件環(huán)境為Intel Core i5CPU 2.40 GHz，4 GB 內(nèi)存，操作系統(tǒng)平臺為Windows10操作系統(tǒng)，使用Java 編程語言與C++語言實現(xiàn)所有方法，給出HPHP 算法與理論最小誤差算法（Optimal）、直接添加噪聲的DP 算法［1］、AHP 算法［9］的實驗對比結果。

實驗采用相對熵（Kullback-Leibler Divergence，KLD）與均方誤差的自然對數(shù)（Natural Logarithm of Mean Square Error，LNMSE）作為評價標準，詳細定義見3.1節(jié)。

實驗采用直方圖發(fā)布經(jīng)常使用的4 個數(shù)據(jù)集，分別是waitakere［9］、search_log［2］、nettrace［2］和socialnetwork［2］。其中：waitakere 是從新西蘭2006 年人口街區(qū)普查數(shù)據(jù)中抽取7 725個街區(qū)的數(shù)據(jù)構成的統(tǒng)計直方圖，街區(qū)人口數(shù)量作為直方圖的桶；search_log 由Google Trends 與American Online 的搜索數(shù)據(jù)合并而成，每個桶包含90 min 搜索“Obama”次數(shù)的統(tǒng)計值；nettrace 源自一所高校的路由追蹤數(shù)據(jù)統(tǒng)計；socialnetwork 來自一個在線社交網(wǎng)站的關系統(tǒng)計。數(shù)據(jù)集的詳細信息見表2。

表2 數(shù)據(jù)集信息Tab.2 Dataset information

設置不同的隱私預算，分別比較四個算法在不同數(shù)據(jù)集的KLD 與LNMSE。在相同的實驗預置條件下，直方圖誤差越小說明發(fā)布直方圖與原始直方圖差異越小，發(fā)布直方圖精度越高。理論上，Optimal 算法發(fā)布直方圖誤差最小，而直接加噪聲的DP 算法發(fā)布直方圖誤差最大，HPHP 算法和AHP 算法發(fā)布直方圖的誤差介于Optimal算法與DP算法之間。

3.1 發(fā)布直方圖誤差評價標準

本節(jié)給出評價發(fā)布直方圖與原始直方圖之間差異的標準：KLD 與LNMSE。發(fā)布直方圖與原始直方圖的KLD 與LNMSE 越小，發(fā)布直方圖與原始直方圖的差異就越小，發(fā)布直方圖的精度與可用性越高。

KLD評價兩個直方圖之間的分布差異。計算原始直方圖H與發(fā)布直方圖之間的相對熵，公式給出如下：

LNMSE 即均方差的自然對數(shù)。均方差評價發(fā)布直方圖桶統(tǒng)計值偏離原始直方圖統(tǒng)計數(shù)值的程度，使用自然對數(shù)可以降低均方差數(shù)量級，便于觀察實驗結果。給定一組統(tǒng)計查詢Q={Q1，Q2，…，Ql}，原始直方圖H與發(fā)布直方圖的LNMSE計算公式給出如下：

3.2 KLD對比實驗

圖2是Optimal、HPHP、AHP 與DP 分別在4個數(shù)據(jù)集運行得到的KLD對比，分別設置隱私預算ε=0.01、0.1、1.0。

圖2 不同隱私預算下的KLD對比Fig.2 KLD comparison with different privacy budgets

從圖2 中可以看出，HPHP 算法發(fā)布直方圖的KLD 值與Optimal 算法發(fā)布直方圖的KLD 值較為接近。相較于直接在統(tǒng)計數(shù)添加噪聲的DP，AHP 基于添加噪聲直方圖分組，并使用貪心方法平衡近似誤差與拉普拉斯誤差，顯著降低了誤差。與AHP 不同的是，HPHP 保證添加噪聲的直方圖與直接基于桶計數(shù)排序的直方圖具有一致順序，即使處理比較特殊的直方圖，也能獲得較好的全局分組，使近似誤差與拉普拉斯誤差得到較好均衡，進而得到誤差較小的發(fā)布直方圖，在不同的隱私預算與數(shù)據(jù)集條件下，HPHP 所發(fā)布直方圖的KLD 誤差約為AHP的10%。

不同于其他數(shù)據(jù)集，nettrace（ID 為2）是有序數(shù)據(jù)集，Optimal、HPHP與AHP均獲得了較高精度的發(fā)布直方圖，說明分組前數(shù)組的有序程度越高，基于分組的直方圖發(fā)布方法越能有效均衡近似誤差與拉普拉斯誤差，進而獲得誤差較小的發(fā)布直方圖。

3.3 LNMSE對比實驗

設置實驗數(shù)據(jù)集waitakere，圖3 給出Optimal、HPHP 與AHP 在隱私預算ε=0.01、0.1、1.0 時，查詢范圍為｛50，100，150，200，250，300，350，400，450｝的LNMSE 對比。隨著查詢范圍逐漸增大，噪聲逐漸累積，誤差呈遞增趨勢。在隱私預算較小時，AHP 的對數(shù)均方差遠大于HPHP 與Optimal，HPHP 的對數(shù)均方差接近Optimal，保證發(fā)布直方圖的高可用性；隨著隱私預算增大，三個算法發(fā)布直方圖的誤差都在降低，并且呈逐漸接近趨勢。因此，隱私預算充足時，AHP 與HPHP 發(fā)布直方圖的差異較小，隱私預算較小時，HPHP 算法能獲得更低LNMSE的發(fā)布直方圖。

圖3 不同隱私預算下的LNMSE對比Fig.3 LNMSE comparison with different privacy budgets

4 結語

針對滿足差分隱私的直方圖發(fā)布問題，本文首先分析已有基于分組的差分隱私直方圖發(fā)布方法存在的缺陷，并在此基礎上提出HPHP 算法；使用約束推斷，使添加差分噪聲的直方圖與基于桶計數(shù)排序的直方圖具有相同順序，同時提高直方圖的精度；基于有序直方圖提出動態(tài)規(guī)劃分組方法，在添加噪聲的直方圖上獲得具有最小誤差的分組。通過分析基于分組的方法可能達到最佳誤差均衡，提出理論最小誤差Optimal方法。HPHP 與Optimal、AHP 在真實數(shù)據(jù)集上的實驗對比結果表明：HPHP 發(fā)布直方圖誤差小于已有算法，接近Optimal的理論最小誤差。當隱私預算較小時，約束推斷后的直方圖可能具有大量相同的統(tǒng)計值，未來工作考慮解決這一問題，得到更加接近理論最佳誤差均衡的分組，進一步提升直方圖發(fā)布精度。