康　健，吳英杰，黃泗勇，陳　鴻，孫　嵐福州大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福州 350116

?

異方差加噪下的差分隱私直方圖發(fā)布算法*

康健，吳英杰+，黃泗勇，陳鴻，孫嵐
福州大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福州 350116

KANG Jian,WU Yingjie,HUANG Siyong,et al.Algorithm for differential privacy histogram publication with non-uniform private budget.Journal of Frontiers of Computer Science and Technology,2016,10(6):786-798.

摘要：現(xiàn)有基于區(qū)間樹結(jié)構(gòu)的差分隱私直方圖發(fā)布方法大多采用同方差加噪方式，對(duì)其進(jìn)一步研究發(fā)現(xiàn)，采用異方差加噪策略可以進(jìn)一步提升發(fā)布直方圖的區(qū)間計(jì)數(shù)查詢精度，然而當(dāng)前基于異方差加噪的差分隱私直方圖發(fā)布方法對(duì)區(qū)間樹結(jié)構(gòu)卻有嚴(yán)格的要求，導(dǎo)致靈活性與實(shí)用性較低。為此，提出了一種異方差加噪下面向任意區(qū)間樹結(jié)構(gòu)的差分隱私直方圖發(fā)布算法LUE-DPTree（inear unbiased estimator for differential private tree）。首先根據(jù)區(qū)間計(jì)數(shù)查詢的分布，計(jì)算區(qū)間樹中節(jié)點(diǎn)的覆蓋概率，并據(jù)此分配隱私預(yù)算，實(shí)現(xiàn)異方差加噪；接著經(jīng)分析指出該異方差加噪策略適用于任意區(qū)間樹結(jié)構(gòu)，且從理論上證明了在任意區(qū)間樹結(jié)構(gòu)下進(jìn)行異方差加噪后，仍可在一致性約束下利用最優(yōu)線性無偏估計(jì)進(jìn)一步降低區(qū)間計(jì)數(shù)查詢的誤差。針對(duì)算法的區(qū)間計(jì)數(shù)查詢精度及執(zhí)行效率，與同類算法進(jìn)行了比較分析。實(shí)驗(yàn)結(jié)果表明，LUE-DPTree算法是有效可行的。

關(guān)鍵詞：隱私保護(hù)；差分隱私；直方圖發(fā)布；異方差加噪；區(qū)間樹

ISSN 1673-9418CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(06)-0786-13

E-mail:fcst@vip.163.com

http://www.ceaj.org

Tel:+86-10-89056056

1　引言

隨著信息技術(shù)的發(fā)展，大量數(shù)據(jù)的收集與發(fā)布在促進(jìn)科學(xué)技術(shù)進(jìn)步的同時(shí)，也帶來了隱私信息泄露的問題。因此，數(shù)據(jù)發(fā)布隱私保護(hù)成為現(xiàn)今一項(xiàng)熱門的研究課題。

近年來，在數(shù)據(jù)發(fā)布隱私保護(hù)領(lǐng)域，研究人員開展了一系列的研究，主要可分為數(shù)據(jù)加密、限制發(fā)布和數(shù)據(jù)擾亂等方面[1-3]，包括k-anonymity[4]、l-diversity[5]等保護(hù)方法。其中，Dwork[6]提出了差分隱私保護(hù)模型。該模型采用了嚴(yán)格的量化評(píng)估標(biāo)準(zhǔn)，能夠?qū)崿F(xiàn)有效的隱私保護(hù)，并保證較高的數(shù)據(jù)可用性。此后，研究人員在差分隱私保護(hù)的各個(gè)領(lǐng)域展開了大量研究，其中包括差分隱私直方圖發(fā)布方法的研究[7-15]，主要包含層次樹變換、聚類變換和傅里葉變換等[3]。本文主要針對(duì)層次樹變換中基于區(qū)間樹的差分隱私直方圖發(fā)布方法進(jìn)行討論。

現(xiàn)有基于區(qū)間樹的差分隱私直方圖發(fā)布方法大多采用同方差的加噪方式。Hay等人[8]建立了差分隱私區(qū)間樹，并進(jìn)行了同方差加噪與一致性調(diào)節(jié)。Xu等人[9]提出了StructureFirst，優(yōu)化直方圖劃分策略，并在劃分區(qū)間后的構(gòu)造區(qū)間樹中進(jìn)行了同方差加噪。采用同方差加噪方式的發(fā)布方法有效提升了發(fā)布數(shù)據(jù)的可用性和算法效率。而實(shí)際上通過研究可以發(fā)現(xiàn)，若采用異方差加噪方式，可進(jìn)一步提高發(fā)布精度。文獻(xiàn)[10]提出了通過迭代方式在區(qū)間樹進(jìn)行層次間隱私預(yù)算分配的方法，有效降低了查詢誤差，但其在相同層次的節(jié)點(diǎn)中仍使用相同的隱私預(yù)算，因此仍具有進(jìn)一步優(yōu)化的空間。文獻(xiàn)[11]提出了DP-tree（differential private tree），通過異方差加噪，能夠?qū)Χ嗑S數(shù)據(jù)進(jìn)行發(fā)布并提高查詢精度，但該方法采用了完全K叉樹結(jié)構(gòu)，限制了樹結(jié)構(gòu)調(diào)節(jié)的靈活性。

針對(duì)以上問題，本文提出了一種異方差加噪下，面向任意區(qū)間樹結(jié)構(gòu)的差分隱私直方圖發(fā)布算法，以期進(jìn)一步降低區(qū)間計(jì)數(shù)查詢誤差，提高發(fā)布數(shù)據(jù)的可用性。

2　基礎(chǔ)知識(shí)與問題

在現(xiàn)有差分隱私直方圖發(fā)布方法的研究中，主要通過重構(gòu)直方圖結(jié)構(gòu)來回答區(qū)間計(jì)數(shù)查詢，代表方法為基于差分隱私區(qū)間樹的發(fā)布方法。該方法利用區(qū)間樹結(jié)構(gòu)重構(gòu)原始直方圖，可有效提高發(fā)布數(shù)據(jù)的精確度和算法運(yùn)行效率。

定義1（差分隱私區(qū)間樹[8]）對(duì)于給定計(jì)數(shù)直方圖H={C1,C2,…,Cn}，對(duì)H建立的差分隱私區(qū)間樹T滿足以下特性：

（1）非葉節(jié)點(diǎn)的兒子節(jié)點(diǎn)數(shù)大于等于2。

（2）每個(gè)節(jié)點(diǎn)x對(duì)應(yīng)于H中的一個(gè)區(qū)間范圍，表示為[L(x),R(x)]，根節(jié)點(diǎn)所代表的區(qū)間為[1,n]。

定義2（同/異方差加噪方式[8,11]）給定區(qū)間樹T，通過噪聲機(jī)制[8]使每個(gè)節(jié)點(diǎn)x滿足εx-差分隱私。若對(duì)任意節(jié)點(diǎn)x、y，均有εx=εy，則稱作同方差加噪方式；若存在節(jié)點(diǎn)x、y，使得εx≠εy，則稱作異方差加噪方式。

如圖1，當(dāng)ε=1.0時(shí)，在圖1（a）的同方差加噪方式下，區(qū)間樹的每個(gè)節(jié)點(diǎn)的隱私預(yù)算εx均為0.5。而在圖1（b）的異方差加噪方式中，節(jié)點(diǎn)1隱私預(yù)算為0.33，節(jié)點(diǎn)2、3、4的隱私預(yù)算均為0.67。由于通常情況下，區(qū)間樹中的各個(gè)節(jié)點(diǎn)被查詢區(qū)間覆蓋的頻率并不完全相同。例如在查詢區(qū)間隨機(jī)分布的情況下，節(jié)點(diǎn)2、3、4具有高于節(jié)點(diǎn)1的覆蓋概率（計(jì)算過程將在下文給出），因此在圖1（b）中能夠?qū)Χ鄶?shù)高頻覆蓋節(jié)點(diǎn)添加更少的噪聲，對(duì)少數(shù)低頻覆蓋節(jié)點(diǎn)添加更多噪聲，從而降低整體區(qū)間計(jì)數(shù)查詢誤差。

Fig.1　Uniform/non-uniform private budget distribution圖1　同/異方差加噪下的隱私預(yù)算分配

定義3（查詢一致性約束[8]）在發(fā)布后的差分隱私區(qū)間樹T中，任意節(jié)點(diǎn)x的計(jì)數(shù)值應(yīng)與其兒子節(jié)點(diǎn)的計(jì)數(shù)值總和相等，稱為查詢一致性約束：

其中，hˉ代表最終發(fā)布后節(jié)點(diǎn)的計(jì)數(shù)值；Son(x)為節(jié)點(diǎn)x的兒子節(jié)點(diǎn)集合。

現(xiàn)有基于區(qū)間樹結(jié)構(gòu)的差分隱私直方圖發(fā)布方法大多采用同方差的加噪方式，少數(shù)采用異方差加噪的差分隱私直方圖發(fā)布方法對(duì)樹結(jié)構(gòu)有著嚴(yán)格的要求。為此，本文的研究問題及目標(biāo)是：對(duì)于給定的原始直方圖H，建立與其對(duì)應(yīng)的差分隱私區(qū)間樹T，并通過異方差方式進(jìn)行加噪；接著說明該加噪方式適用于任意區(qū)間樹結(jié)構(gòu)，并利用查詢一致性約束條件進(jìn)一步優(yōu)化區(qū)間計(jì)數(shù)查詢精度；最后提出異方差加噪下面向任意區(qū)間樹結(jié)構(gòu)的差分隱私直方圖發(fā)布算法LUE-DPTree，同時(shí)保證算法滿足ε-差分隱私。

3　異方差加噪下面向任意區(qū)間樹結(jié)構(gòu)的差分隱私直方圖發(fā)布算法

為實(shí)現(xiàn)異方差加噪，首先需要解決區(qū)間樹中節(jié)點(diǎn)的覆蓋概率計(jì)算問題，并據(jù)此進(jìn)行隱私預(yù)算分配。

3.1節(jié)點(diǎn)覆蓋概率計(jì)算

當(dāng)對(duì)區(qū)間樹進(jìn)行區(qū)間計(jì)數(shù)查詢時(shí)，其計(jì)數(shù)值為查詢區(qū)間[QL,QR]所覆蓋的多個(gè)節(jié)點(diǎn)計(jì)數(shù)值之和[8]。所覆蓋的節(jié)點(diǎn)互不相交，且并集等于查詢區(qū)間，因此被覆蓋節(jié)點(diǎn)x需滿足QL≤L(x)≤R(x)≤QR。同時(shí)，對(duì)任意一次查詢，若其父節(jié)點(diǎn)fx能被查詢區(qū)間覆蓋，節(jié)點(diǎn)x將被忽略，因此節(jié)點(diǎn)x被查詢區(qū)間覆蓋條件為：

當(dāng)x為根節(jié)點(diǎn)時(shí)，因其父節(jié)點(diǎn)fx不存在，令QL≤L(fx)≤R(fx)≤QR為假。

本文假定所有查詢區(qū)間的出現(xiàn)概率相等。由式（1）可得出節(jié)點(diǎn)覆蓋概率px的計(jì)算公式：

根據(jù)式（2），可由算法1計(jì)算節(jié)點(diǎn)覆蓋概率。

算法1 CNCP（calculate node coverage probability）

輸入：待計(jì)算節(jié)點(diǎn)x及其父節(jié)點(diǎn)fx。

輸出：區(qū)間樹中所有節(jié)點(diǎn)的覆蓋概率px。

1.若x為根節(jié)點(diǎn)：

2.若x為其他節(jié)點(diǎn)：

3.對(duì)所有y∈Son(x)，執(zhí)行CNCP(y,x)；

實(shí)際上，當(dāng)查詢區(qū)間滿足其他分布特性時(shí)，通過對(duì)式（2）的調(diào)整，其節(jié)點(diǎn)覆蓋概率亦可通過本算法進(jìn)行計(jì)算。算法1僅要求樹結(jié)構(gòu)滿足區(qū)間樹定義，因此適用于任意樹結(jié)構(gòu)的差分隱私區(qū)間樹。

3.2節(jié)點(diǎn)系數(shù)計(jì)算及隱私預(yù)算分配

在計(jì)算出節(jié)點(diǎn)覆蓋概率后，即可據(jù)此調(diào)整隱私預(yù)算，通過異方差加噪方式降低整體的查詢誤差。而在此之前，需分析如何保證異方差加噪后的差分隱私區(qū)間樹滿足ε-差分隱私。

證明 對(duì)任意節(jié)點(diǎn)x，設(shè)Sub(x)表示以節(jié)點(diǎn)x為根節(jié)點(diǎn)的子樹，A(x)表示對(duì)子樹Sub(x)進(jìn)行發(fā)布的算法，則：

根據(jù)結(jié)論1，若要保證異方差加噪后的區(qū)間樹滿足ε-差分隱私，需滿足以下條件：

則區(qū)間計(jì)數(shù)查詢誤差期望：

因此，在滿足ε-差分隱私的前提下，求解區(qū)間樹上各節(jié)點(diǎn)的差分隱私預(yù)算，從而最小化區(qū)間計(jì)數(shù)查詢誤差期望的問題，可轉(zhuǎn)化為以下最優(yōu)化問題：

其中，εˉ表示區(qū)間樹中節(jié)點(diǎn)的差分隱私預(yù)算向量。

下面通過定義4與結(jié)論2進(jìn)行求解。

定義4（路徑隱私預(yù)算和）

結(jié)論2為最小化區(qū)間計(jì)數(shù)查詢誤差期望（即求解式（3）），區(qū)間樹中差分隱私預(yù)算分配方案需滿足：

稱ax、bx為節(jié)點(diǎn)x的節(jié)點(diǎn)系數(shù)，有:

證明（1）若x為葉節(jié)點(diǎn)，則結(jié)論2顯然成立。

（2）若x為非葉節(jié)點(diǎn)，利用拉格朗日乘數(shù)法，可構(gòu)造如下函數(shù)：

其中，λ為引入的未知標(biāo)量。因目標(biāo)函數(shù) f(ε)為凸函數(shù)，同時(shí)求解式（3）與求解函數(shù)F(εˉ,λ)的全局最優(yōu)解等價(jià)，因此將F(εˉ,λ)對(duì)εˉ求導(dǎo)，得：

假設(shè)對(duì)于y∈Son(x)，結(jié)論均成立，則：

對(duì)于節(jié)點(diǎn)SonBound(x)和任意 y∈Son(x)，在式（3）約束條件下，任意葉節(jié)點(diǎn)到根節(jié)點(diǎn)路徑上的隱私預(yù)算和等于ε，因此：

由式（5）（6），得：

為滿足式（4），必有：

將式（7）代入式（8）可得：

因此：

令

綜合（1）（2），結(jié)論得證。

至此，可通過算法2計(jì)算節(jié)點(diǎn)系數(shù)ax、bx。

算法2 CNP（calculate node parameter）

輸入：待計(jì)算節(jié)點(diǎn)x。

輸出：區(qū)間樹中所有節(jié)點(diǎn)的節(jié)點(diǎn)系數(shù)ax、bx。

1.若x為葉節(jié)點(diǎn)：ax←1,bx←1；

2.若x為其他節(jié)點(diǎn)：

3.對(duì)于y∈Son(x),運(yùn)行CNP(y);

計(jì)算出節(jié)點(diǎn)系數(shù)ax、bx后，可通過算法3分配每個(gè)節(jié)點(diǎn)的差分隱私預(yù)算εx并進(jìn)行異方差加噪。

算法3 NPBD（non-uniform private budget distribution）

輸入：待加噪節(jié)點(diǎn)x，路徑隱私預(yù)算和psum(x)。

3.對(duì)所有y∈Son(x)，執(zhí)行：

本文以圖1所示差分隱私區(qū)間樹為例，分析異方差加噪對(duì)區(qū)間計(jì)數(shù)查詢精度的影響。

將圖1所示區(qū)間樹通過算法1及算法2進(jìn)行節(jié)點(diǎn)覆蓋概率和系數(shù)計(jì)算，結(jié)果如圖2所示。再通過算法3進(jìn)行隱私預(yù)算分配，得到各節(jié)點(diǎn)的隱私預(yù)算：

Fig.2　Example of non-uniform private budget distribution圖2　異方差加噪示例

該方案與圖1（b）所示一致。分別對(duì)圖1（a）、圖1 （b）中的隱私預(yù)算分配方案計(jì)算區(qū)間計(jì)數(shù)查詢誤差期望：

查詢誤差期望由原先同方差加噪的10.67，降低至異方差加噪的8.25，查詢精度得到提高。

3.3異方差加噪下面向任意區(qū)間樹結(jié)構(gòu)的差分隱私直方圖發(fā)布算法

上述步驟實(shí)現(xiàn)了對(duì)差分隱私區(qū)間樹進(jìn)行的異方差加噪。由于僅要求樹結(jié)構(gòu)滿足差分隱私區(qū)間樹定義，并無其他限定，該異方差加噪策略不僅適用于完全K叉樹，還能夠運(yùn)用在任意區(qū)間樹結(jié)構(gòu)上。

任意樹結(jié)構(gòu)的差分隱私區(qū)間樹示例如圖3所示。

Fig.3　Range tree with different structures圖3　不同樹結(jié)構(gòu)下的區(qū)間樹

圖3中，對(duì)于長度為22的直方圖數(shù)據(jù)集而言，可采用如圖3（a）的完全二叉樹進(jìn)行統(tǒng)計(jì)表示，也可用類似于圖3（b）的任意樹結(jié)構(gòu)差分隱私區(qū)間樹進(jìn)行表示。對(duì)其分別計(jì)算區(qū)間計(jì)數(shù)查詢誤差期望：

可以看出，采用任意區(qū)間樹結(jié)構(gòu)之后，可以對(duì)樹結(jié)構(gòu)進(jìn)行更靈活的調(diào)整，從而有效降低查詢誤差。結(jié)合異方差加噪方式，更能夠進(jìn)一步提升查詢精度。

任意樹結(jié)構(gòu)差分隱私區(qū)間樹的構(gòu)建算法如下：

算法4 TSC（tree structure construct）

輸入：待構(gòu)建子樹節(jié)點(diǎn)x，當(dāng)前區(qū)間[l,r]。

輸出：差分隱私區(qū)間樹T。

在算法4中，對(duì)分支數(shù)K的選擇和子區(qū)間長度的分配方式上進(jìn)行改變，均會(huì)導(dǎo)致樹結(jié)構(gòu)的變化。樹結(jié)構(gòu)構(gòu)建完成并進(jìn)行節(jié)點(diǎn)覆蓋概率計(jì)算（CNCP）、節(jié)點(diǎn)系數(shù)計(jì)算（CNP）和異方差加噪（NPBD）后，即可得到異方差加噪下的任意樹結(jié)構(gòu)差分隱私區(qū)間樹。

在建立任意區(qū)間樹并進(jìn)行異方差加噪后，可有效提高區(qū)間計(jì)數(shù)查詢精度。然而，通過如圖4的示例可以發(fā)現(xiàn)，加噪后的區(qū)間樹并不滿足一致性約束。

Fig.4　Example of consistency constraintafter adding noise圖4　加噪后造成的一致性約束問題示例

圖4中，未加噪?yún)^(qū)間樹（a）經(jīng)加噪后，變?yōu)榧釉雲(yún)^(qū)間樹（b），其父節(jié)點(diǎn)1的計(jì)數(shù)值10.5與子節(jié)點(diǎn)計(jì)數(shù)值之和9.3不同，不滿足一致性約束。以下將針對(duì)此問題，通過理論分析，證明異方差加噪下的任意區(qū)間樹，仍可利用一致性約束進(jìn)行最優(yōu)線性無偏估計(jì)優(yōu)化。

結(jié)論4差分隱私區(qū)間樹從葉節(jié)點(diǎn)w到根節(jié)點(diǎn)路徑上的節(jié)點(diǎn)線性無偏估計(jì)值hˉ滿足下列公式：

證明 式(9)可轉(zhuǎn)換為求解下式：

對(duì)于任意葉節(jié)點(diǎn)w，對(duì)hˉw求偏導(dǎo)：

結(jié)論5以節(jié)點(diǎn)x為根節(jié)點(diǎn)的子樹中，節(jié)點(diǎn)x的估計(jì)值hˉx、葉節(jié)點(diǎn)到節(jié)點(diǎn)x的估計(jì)值加權(quán)和gˉx，均是關(guān)于葉節(jié)點(diǎn)的線性方程：

其中：

Bound(x)是以x為根節(jié)點(diǎn)的子樹中第一個(gè)葉節(jié)點(diǎn)，w= SonBound(x)。

證明 定義節(jié)點(diǎn)高度：

（1）若節(jié)點(diǎn)x∈{y|Height(y)=0}，即x∈Leaf(root)，結(jié)論5顯然成立。

（2）假設(shè)對(duì)任意節(jié)點(diǎn)y∈{y|Height(y)≤n}，式（11）均成立。當(dāng)Height(x)=n+1時(shí)：

令hsum(x)表示從葉節(jié)點(diǎn)x到根節(jié)點(diǎn)路徑上節(jié)點(diǎn)集合的加噪值加權(quán)和，由結(jié)論4可知：

令w=SonBound(x)，由式（12）可知，對(duì)于節(jié)點(diǎn)y∈Son(x)，有Height(y)≤n，Height(w)≤n，且根據(jù)結(jié)論4，有：

代入式(11)可得：

由一致性約束可得：

綜合（1）（2），證明式（11）成立。

經(jīng)由以上結(jié)論及證明，通過維護(hù)參數(shù)(α,β,c,d)的值，并利用式（11）進(jìn)行估計(jì)值計(jì)算，設(shè)計(jì)了對(duì)差分隱私區(qū)間樹加噪后，在任意區(qū)間樹結(jié)構(gòu)下，利用最優(yōu)線性無偏估計(jì)進(jìn)行調(diào)整的優(yōu)化算法。

算法5 PA_BLUE（parameter adjust using best linear unbiased estimate）

輸入：待計(jì)算發(fā)布計(jì)數(shù)值的節(jié)點(diǎn)x。

輸出：區(qū)間樹所有節(jié)點(diǎn)的參數(shù)(α,β,c,d)。

1.若x為葉節(jié)點(diǎn)，更新：

并結(jié)束算法

計(jì)算參數(shù)(α,β,c,d)后，通過算法6計(jì)算優(yōu)化后的最終發(fā)布值。

算法6 CRC（calculate range count）

輸入：待計(jì)算發(fā)布計(jì)數(shù)值的節(jié)點(diǎn)x，令tot為

輸出：區(qū)間樹所有節(jié)點(diǎn)的發(fā)布計(jì)數(shù)值hˉx。

通過以上步驟，本文提出了異方差加噪下，面向任意區(qū)間樹結(jié)構(gòu)進(jìn)行最優(yōu)線性無偏估計(jì)優(yōu)化的差分隱私直方圖發(fā)布算法。

算法7 LUE-DPTree（linear unbiased estimator for differential private tree）

輸入：原始直方圖H，差分隱私參數(shù)ε。

輸出：異方差加噪，任意樹結(jié)構(gòu)的ε-差分隱私區(qū)間樹T_Publish。

下面對(duì)算法7的差分隱私保障和算法復(fù)雜度進(jìn)行分析證明。

結(jié)論6算法7所生成的差分隱私區(qū)間樹T_publish滿足ε-差分隱私。

證明 對(duì)于區(qū)間樹T_Publish，由式（3）中的約束條件可知，在計(jì)算各節(jié)點(diǎn)隱私預(yù)算εx時(shí)，始終在該約束下進(jìn)行：

由結(jié)論1可知，整體發(fā)布過程滿足ε-差分隱私。

結(jié)論7算法7的算法時(shí)間復(fù)雜度、空間復(fù)雜度均為O(n)。

證明 在算法7中，各步驟均為對(duì)區(qū)間樹進(jìn)行一次掃描，時(shí)間復(fù)雜度為O(n)。在CNCP、CNP和PA_BLUE算法中，分別需存儲(chǔ)各節(jié)點(diǎn)的節(jié)點(diǎn)覆蓋概率、節(jié)點(diǎn)系數(shù)等值，空間復(fù)雜度為O(n)。在TSC、NPBC、CRC算法中，分別對(duì)樹節(jié)點(diǎn)的發(fā)布值進(jìn)行計(jì)算及改變，空間復(fù)雜度同樣為O(n)。因此，算法7的時(shí)間、空間復(fù)雜度均為O(n)，為線性復(fù)雜度。

4　實(shí)驗(yàn)結(jié)果與分析

本文從區(qū)間計(jì)數(shù)查詢精度和算法運(yùn)行效率兩方面與同類代表算法Boost[8]進(jìn)行對(duì)比分析。在文獻(xiàn)[10]中，提出了在區(qū)間樹的不同層次間進(jìn)行異方差分配的迭代方法，本文將其應(yīng)用于Boost算法中，并標(biāo)識(shí)為Boost-UN。同時(shí)，為了更好地體現(xiàn)本文算法的有效性，實(shí)驗(yàn)也與基于小波變換的Privelet[15]算法進(jìn)行了比較分析。同樣采用了異方差加噪方式的算法DP-tree[11]，由于并未給出具體算法描述，從而未與其進(jìn)行實(shí)驗(yàn)對(duì)比。在實(shí)驗(yàn)中，隱私參數(shù)ε取值分別為{1.0，0.1，0.01}。采用如式（13）所示的平均方差進(jìn)行誤差衡量。為使實(shí)驗(yàn)結(jié)果更具一般性，取算法執(zhí)行50次的平均值作為最終結(jié)果。

其中，q(T)為區(qū)間計(jì)數(shù)查詢的真實(shí)結(jié)果；q(T′)為區(qū)間計(jì)數(shù)查詢的加噪計(jì)數(shù)值； ||Q為查詢集大小。

4.1實(shí)驗(yàn)環(huán)境

為便于對(duì)比分析，采用了與文獻(xiàn)[8]相同的實(shí)驗(yàn)數(shù)據(jù)集Social Network、Search Logs、NetTrace進(jìn)行實(shí)驗(yàn)。Social Network數(shù)據(jù)集記錄了某在線社交平臺(tái)的用戶關(guān)系無向圖中具有特點(diǎn)度的用戶數(shù)。Search Logs數(shù)據(jù)集統(tǒng)計(jì)了2004年1月至2009年8月期間，關(guān)于“Obama”關(guān)鍵詞的搜索頻率。NetTrace數(shù)據(jù)集對(duì)某大學(xué)在一個(gè)時(shí)間段內(nèi)的IP數(shù)據(jù)包信息進(jìn)行了記錄。其數(shù)據(jù)規(guī)模如表1所示。

實(shí)驗(yàn)硬件環(huán)境為：Intel Core i7 930 2.8 GHz處理器，4 GB內(nèi)存，Windows 7操作系統(tǒng)。算法實(shí)現(xiàn)采用C++語言，由Matlab生成實(shí)驗(yàn)圖表。

Table 1　Dataset size表1 數(shù)據(jù)集規(guī)模

4.2查詢精度

本文通過與Boost、Privelet等算法的對(duì)比，分析LUE-DPTree在區(qū)間計(jì)數(shù)查詢精度上的表現(xiàn)。并通過對(duì)樹結(jié)構(gòu)的調(diào)整，分析不同樹結(jié)構(gòu)對(duì)查詢精度的影響。

4.2.1與Boost、Privelet等算法的對(duì)比

本文分別采用隨機(jī)任意長度區(qū)間和隨機(jī)固定長度區(qū)間兩種方式，對(duì)算法查詢精度進(jìn)行檢驗(yàn)。其中，任意長度區(qū)間隨機(jī)生成1 000條，區(qū)間的起點(diǎn)L和終點(diǎn)R隨機(jī)生成，且L≤R。隨機(jī)固定長度的區(qū)間，區(qū)間大小分別取20,21，…，213，…，每種長度隨機(jī)生成1 000條查詢區(qū)間?？紤]到Boost和Privelet算法適用于2的整數(shù)冪的數(shù)據(jù)規(guī)模，在這部分實(shí)驗(yàn)中，僅選取Search Logs和NetTrace為實(shí)驗(yàn)數(shù)據(jù)集。

在圖5和圖6的實(shí)驗(yàn)對(duì)比結(jié)果中，隨隱私參數(shù)ε的減小，平均誤差約按102的量級(jí)增長。在4種算法中，LUE-DPTree算法的查詢精度較優(yōu)。說明異方差加噪策略和一致性約束下的最優(yōu)線性無偏估計(jì)優(yōu)化，有效提高了算法的區(qū)間計(jì)數(shù)查詢精度。

在圖7和圖8中，固定區(qū)間大小的隨機(jī)查詢，其誤差隨區(qū)間大小增加而增大。在各區(qū)間長度下，LUE-DPTree算法的查詢精度均優(yōu)于Boost和Privelet算法。而Boost-UN算法中，采用異方差加噪方式，僅在不同層次中進(jìn)行了隱私預(yù)算分配，而在同一層次的節(jié)點(diǎn)中，仍采用了相同的隱私預(yù)算，因此查詢精度介于Boost和LUE-DPTree算法之間。該實(shí)驗(yàn)結(jié)果說明，LUE-DPTree算法中的隱私預(yù)算分配策略，在能夠適用于任意區(qū)間樹結(jié)構(gòu)，提供更高靈活度的同時(shí)，還能更有效地提升查詢精度。

綜合上述實(shí)驗(yàn)分析表明，相比其他兩種算法，LUE-DPTree算法具有更高的數(shù)據(jù)發(fā)布質(zhì)量。

4.2.2不同區(qū)間樹結(jié)構(gòu)對(duì)精度的影響

為觀察不同區(qū)間樹結(jié)構(gòu)對(duì)查詢精度的影響，選取了4種樹結(jié)構(gòu)：2叉樹、3叉樹、4叉樹和任意叉樹（每次隨機(jī)分2～4叉）分別標(biāo)識(shí)為LUE-DPTree-2、LUE-DPTree-3、LUE-DPTree-4、LUE-DPTree-R。為方便起見，這部分實(shí)驗(yàn)僅選取ε=1.0時(shí)，LUE-DPTree算法在Social Network和NetTrace兩個(gè)數(shù)據(jù)集上的結(jié)果進(jìn)行對(duì)比。

Fig.5　Comparison of random range queries error in Search Logs圖5　隨機(jī)任意長度區(qū)間的查詢誤差對(duì)比(Search Logs)

Fig.6　Comparison of random range queries error in NetTrace圖6　隨機(jī)任意長度區(qū)間的查詢誤差對(duì)比(NetTrace)

Fig.7　Comparison of random range queries error under different lengths in Search Logs圖7　不同區(qū)間大小下的查詢誤差曲線圖(Search Logs)

Fig.8　Comparison of random range queries error under different lengths in NetTrace圖8　不同區(qū)間大小下的查詢誤差曲線圖(NetTrace)

從圖9中可以觀察到，在Social Network數(shù)據(jù)集上，不同樹結(jié)構(gòu)的查詢精度差別較大，相比其他結(jié)構(gòu)，任意叉樹結(jié)構(gòu)的查詢精度更高；而在NetTrace數(shù)據(jù)上，精度差別較小，2叉樹結(jié)構(gòu)相比其他結(jié)構(gòu)有更小的誤差。結(jié)果說明，對(duì)于不同特征的數(shù)據(jù)集，若要更好地提高數(shù)據(jù)發(fā)布質(zhì)量，需要建立不同的樹結(jié)構(gòu)，包括任意區(qū)間樹結(jié)構(gòu)。Boost算法僅適用于完全K叉樹的情況，使得人們無法通過改變樹結(jié)構(gòu)來降低查詢誤差。而LUE-DPTree算法則可以適用于任意區(qū)間樹結(jié)構(gòu)，使得人們可以有更大的調(diào)整空間，能夠?qū)ふ腋训臉?gòu)建方式來進(jìn)一步提高直方圖發(fā)布的質(zhì)量。

Fig.9　Comparison of random range queries error of LUE-DPTree under different range tree structures圖9　LUE-DPTree算法在不同區(qū)間樹結(jié)構(gòu)下的查詢誤差

Fig.10　Comparison of average running time under differentε圖10　不同隱私參數(shù)ε下的平均運(yùn)行時(shí)間

4.3算法運(yùn)行效率

本文通過以下方案對(duì)比分析4種算法在不同情況下的運(yùn)行效率：（1）在樹結(jié)構(gòu)相同，數(shù)據(jù)集和隱私參數(shù)取值不同的情況下分析4者的運(yùn)行效率。（2）在隱私參數(shù)和數(shù)據(jù)集相同，樹結(jié)構(gòu)不同的情況下分析LUE-DPTree算法的運(yùn)行效率。同樣考慮到Boost和Privelet算法對(duì)樹結(jié)構(gòu)的要求，在實(shí)驗(yàn)（1）中僅采用Search Logs和NetTrace兩個(gè)數(shù)據(jù)集。在實(shí)驗(yàn)（1）中，隱私參數(shù)ε分別取值1.0、0.1、0.01，在實(shí)驗(yàn)（2）中取值1.0。為使結(jié)果更具可比性，在實(shí)驗(yàn)（1）中樹結(jié)構(gòu)采用完全2叉樹結(jié)構(gòu)，在實(shí)驗(yàn)（2）中LUE-DPTree分別選擇2叉樹、3叉樹、4叉樹和任意叉樹（每次隨機(jī)分2～4叉）。運(yùn)行時(shí)間不包含數(shù)據(jù)讀入和查詢時(shí)間。實(shí)驗(yàn)結(jié)果分別如圖10和圖11所示。

Fig.11　Comparison of average running time of LUEDPTree under different tree structures圖11 不同樹結(jié)構(gòu)下LUE-DPTree算法的平均運(yùn)行時(shí)間

從圖10中可以得出：（1）4種算法的運(yùn)行時(shí)間均隨著數(shù)據(jù)規(guī)模的增大而增大，與數(shù)據(jù)規(guī)模成比例增加。（2）由于4種算法的運(yùn)行效率與隱私參數(shù)無關(guān)，運(yùn)行時(shí)間基本不隨隱私預(yù)算改變而變化。相比其他算法，LUE-DPTree算法多進(jìn)行了一次隱私預(yù)算分配的過程，因此運(yùn)行時(shí)間稍長于另外3種算法。

從圖11中可以看出，LUE-DPTree算法的運(yùn)行時(shí)間隨著樹結(jié)構(gòu)的變動(dòng)而變動(dòng)，基本與差分隱私區(qū)間樹的節(jié)點(diǎn)數(shù)量成正相關(guān)，與結(jié)論7所分析的線性復(fù)雜度相符。

總體來說，LUE-DPTree算法與Boost、Privelet算法均具有較高的運(yùn)行效率。LUE-DPTree算法的運(yùn)行效率雖略差于同類經(jīng)典算法，但仍具較高的性能。

5　結(jié)束語

本文提出了一種異方差加噪下面向任意區(qū)間樹結(jié)構(gòu)的差分隱私直方圖發(fā)布算法，該算法能夠在保證運(yùn)行效率的前提下，有效降低查詢誤差。相比采用特定區(qū)間樹結(jié)構(gòu)的發(fā)布算法，該算法適用于任意區(qū)間樹結(jié)構(gòu)，在樹結(jié)構(gòu)上有更大的調(diào)整靈活度，而異方差加噪方式，也為在不同的查詢規(guī)律、數(shù)據(jù)特性下進(jìn)行查詢精度提升提供了更大的優(yōu)化空間，因此該算法具有更好的靈活性。同時(shí)，由于任意樹結(jié)構(gòu)放寬了對(duì)數(shù)據(jù)集長度的限制，提高了算法的適用范圍，使得算法具有更高的實(shí)用性。

在接下來的研究工作中，將考慮如何更加合理地通過數(shù)據(jù)分布情況和查詢區(qū)間規(guī)律，設(shè)計(jì)啟發(fā)式的區(qū)間樹構(gòu)建方法與隱私預(yù)算分配方式，進(jìn)一步提高發(fā)布數(shù)據(jù)的質(zhì)量。

References:

[1]Zhou Shuigeng,Li Feng,Tao Yufei,et al.Privacy preservation in database applications:a survey[J].Chinese Journal of Computers,2009,32(5):847-861.

[2]Xiong Ping,Zhu Tianqing,Wang Xiaofeng.A survey on diafaferential privacy and applications[J].Chinese Journal of Computers,2014,37(1):101-122.

[3]Zhang Xiaojian,Meng Xiaofeng.Differential privacy in data publication and analysis[J].Chinese Journal of Computers, 2014,37(4):927-949.

[4]Sweeney L.k-anonymity:a model for protecting privacy[J]. International Journal on Uncertainty,Fuzziness and Knowledge Based Systems,2002,10(5):557-570.

[5]Machanavajjhala A,Gehrke J,Kifer D,et al.l-diversity:privacy beyond k-anonymity[C]//Proceedings of the 22nd International Conference on Data Engineering,Atlanta,USA, Apr 3-8,2006.Piscataway,USA:IEEE,2006:24-35.

[6]Dwork C.Differential privacy[C]//Proceedings of the 33rd International Colloquium on Automata,Languages and Programming,Venice,Italy,Jul 10-14,2006.Berlin,Heidelberg:Springer,2006:1-12.

[7]Acs G,Castelluccia C,Chen Rui.Differentially private histogram publishing through Lossy compression[C]//Proceedings of the 12th IEEE International Conference on Data Mining,Brussels,Belgium,Dec 10-13,2012.Piscataway, USA:IEEE,2012:84-95.

[8]Hay M,Rastogi V,Miklau G,et al.Boosting the accuracy of differentially private histograms through consistency[J]. Proceedings of the VLDB Endowment,2010,3(1):1021-1032.

[9]Xu Jia,Zhang Zhenjie,Xiao Xiaokui,et al.Differentially private histogram publication[J].The VLDB Journal,2013, 22(6):797-822.

[10]Qardaji W,Yang Weining,Li Ninghui.Understanding hierarchical methods for differentially private histograms[J]. Proceedings of the VLDB Endowment,2013,6(14):1954-1965.

[11]Peng Shangfu,Yang Yin,Zhang Zhenjie,et al.DP-tree:indexing multi-dimensional data under differential privacy[C]// Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data,Scottsdale,USA,May 20-24,2012.New York,USA:ACM,2012:864.

[12]Dwork C,McSherry F,Nissim K,et al.Calibrating noise to sensitivity in private data analysis[C]//LNCS 3876:Proceedings of the 3rd Theory of Cryptography Conference, New York,USA,Mar 4-7,2006.Berlin,Heidelberg:Springer, 2006:265-284.

[13]McSherry F,Talwar K.Mechanism design via differential privacy[C]//Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science,Providence, USA,Oct 21-23,2007.Piscataway,USA:IEEE,2007:94-103.

[14]Ghosh A,Roughgarden T,Sundararajan M.Universally utility-maximizing privacy mechanisms[C]//Proceedings of the 41st Annual ACM Symposium on Theory of Computing,Betheda,USA,May 31-Jun 2,2009.New York,USA: ACM,2009:351-360.

[15]Xiao Xiaokui,Wang Guozhang,Gehrke J.Differential privacyviawavelettransforms[J].IEEETransactionson Knowledge and Data Engineering,2011,23(8):1200-1214.

附中文參考文獻(xiàn)：

[1]周水庚,李豐,陶宇飛,等.面向數(shù)據(jù)庫應(yīng)用的隱私保護(hù)研究綜述[J].計(jì)算機(jī)學(xué)報(bào),2009,32(5):847-861.

[2]熊平,朱天清,王曉峰.差分隱私保護(hù)及其應(yīng)用[J].計(jì)算機(jī)學(xué)報(bào),2014,37(1):101-122.

[3]張嘯劍,孟小峰.面向數(shù)據(jù)發(fā)布和分析的差分隱私保護(hù)[J]計(jì)算機(jī)學(xué)報(bào),2014,37(4):927-949.

KANG Jian was born in 1989.He is an M.S candidate at College of Mathematics and Computer Science,Fuzhou University.His research interest is differential privacy preserving.

康健（1989—），男，福建漳州人，福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)椴罘蛛[私保護(hù)。

WU Yingjie was born in 1979.He received the Ph.D.degree in computer science from Southeast University in 2012.Now he is an associate professor at Fuzhou University.His research interests include data mining,data security and privacy preserving,etc.

吳英杰（1979—），男，2012年于東南大學(xué)計(jì)算機(jī)科學(xué)專業(yè)獲得博士學(xué)位，現(xiàn)為福州大學(xué)副教授，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘，數(shù)據(jù)安全與隱私保護(hù)等。

HUANG Siyong was born in 1989.He received the M.S.degree from Fuzhou University in 2015.His research interest is differential privacy preserving.

黃泗勇（1989—），男，福建漳州人，2015年于福州大學(xué)獲得碩士學(xué)位，主要研究領(lǐng)域?yàn)椴罘蛛[私保護(hù)。

CHEN Hong was born in 1989.He received the M.S.degree from Fuzhou University in 2014.His research interest is differential privacy preserving.

陳鴻（1989—），男，福建長樂人，2014年于福州大學(xué)獲得碩士學(xué)位，主要研究領(lǐng)域?yàn)椴罘蛛[私保護(hù)。

SUN Lan was born in 1978.She received the M.S.degree from Xi’an Jiaotong University in 2003.Now she is a lecturer at Fuzhou University.Her research interests include data security and privacy preserving.

孫嵐（1978—），女，陜西西安人，2003年于西安交通大學(xué)獲得碩士學(xué)位，現(xiàn)為福州大學(xué)講師，主要研究領(lǐng)域?yàn)閿?shù)據(jù)安全與隱私保護(hù)。

*The National Natural Science Foundation of China under Grant No.61300026(國家自然科學(xué)基金);the Natural Science Foundation of Fujian Province under Grant No.2014J01230(福建省自然科學(xué)基金).

Received 2015-07,Accepted 2015-09.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2015-09-15,http://www.cnki.net/kcms/detail/11.5602.TP.20150915.1630.010.htmlqueries and the algorithm efficiency.The experimental results show that LUE-DPTree is effective and feasible.

+Corresponding author:E-mail:yjwu@fzu.edu.cn

文獻(xiàn)標(biāo)志碼：A

中圖分類號(hào)：TP311

doi:10.3778/j.issn.1673-9418.1507067

Algorithm for Differential Privacy Histogram Publication with Non-uniform Private Budget?

KANG Jian,WU Yingjie+,HUANG Siyong,CHEN Hong,SUN Lan
College of Mathematics and Computer Science,Fuzhou University,Fuzhou 350116,China

Abstract:Most of existing methods for differential privacy histogram publication based on range tree adopt a uniform private budget.However,it is found that the accuracy of range queries can be further enhanced if using a non-uniform private budget.Unfortunately,current techniques for differential privacy histogram publication with non-uniform private budget require strict range tree structure,which lowers its flexibility and practicability.This paper proposes an algorithm LUE-DPTree(linear unbiased estimator for differential private tree)for differential privacy histogram publication with non-uniform private budget under arbitrary range tree structure.The key idea of LUE-DPTree is to firstly calculate the query coverage probability of range tree nodes based on the distribution of range counting queries so as to allocate the non-uniform private budget.After that,it is shown by further analysis that the strategy of non-uniform private budget can be used in arbitrary range tree.Furthermore,it is indicated by theoretical proof that,after allocated non-uniform private budget under arbitrary range tree structure,the error of range counting queries still can be further reduced by solving the best linear unbiased estimators of the tree nodes’values through consistency constraint.The experimental analysis is designed by comparing LUE-DPTree and the traditional algorithms on the accuracy of range counting

Key words:privacy preserving;differential privacy;histogram publication;non-uniform private budget;range tree