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

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

本文主要貢獻(xiàn)如下：

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

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

3）解析基于分組的方法可能達(dá)到的最佳誤差平衡，提出理論最小誤差Optimal 方法，并設(shè)計(jì)對(duì)比實(shí)驗(yàn)，驗(yàn)證所提方法的有效性。

1 問題描述及相關(guān)概念

1.1 問題描述

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

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

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

1.2 相關(guān)概念

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

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

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

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

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

1.3 基本思路

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

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

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

通過分析已有方法，得出以下3點(diǎn)結(jié)論：

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

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

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

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

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

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

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

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

以下給出HPHP算法的3個(gè)階段的詳細(xì)分析。

2.1 約束推斷

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

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

算法1 ConstrainedInference。

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

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

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

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

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

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

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

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

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

2.3 HPHP算法

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

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

算法2 HPHP。

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

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

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

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

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

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

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

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

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

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

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

算法3 Optimal。

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

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

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

3 實(shí)驗(yàn)分析

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

實(shí)驗(yàn)采用相對(duì)熵（Kullback-Leibler Divergence，KLD）與均方誤差的自然對(duì)數(shù)（Natural Logarithm of Mean Square Error，LNMSE）作為評(píng)價(jià)標(biāo)準(zhǔn)，詳細(xì)定義見3.1節(jié)。

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

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

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

3.1 發(fā)布直方圖誤差評(píng)價(jià)標(biāo)準(zhǔn)

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

KLD評(píng)價(jià)兩個(gè)直方圖之間的分布差異。計(jì)算原始直方圖H與發(fā)布直方圖之間的相對(duì)熵，公式給出如下：

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

3.2 KLD對(duì)比實(shí)驗(yàn)

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

圖2 不同隱私預(yù)算下的KLD對(duì)比Fig.2 KLD comparison with different privacy budgets

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

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

3.3 LNMSE對(duì)比實(shí)驗(yàn)

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

圖3 不同隱私預(yù)算下的LNMSE對(duì)比Fig.3 LNMSE comparison with different privacy budgets

4 結(jié)語(yǔ)

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