一種基于隱樹模型的滿足差分隱私的高維數(shù)據(jù)發(fā)布算法

蘇煒航，程 祥

1(中國人民大學(xué) 附屬中學(xué)，北京 100080) 2(北京郵電大學(xué) 網(wǎng)絡(luò)與交換技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，北京 100876) E-mail：chengxiang@bupt.edu.cn

1 引 言

隨著大數(shù)據(jù)時(shí)代的到來，不同部門、不同地區(qū)間的信息共享需求逐步增加.數(shù)據(jù)發(fā)布是打破信息孤島，實(shí)現(xiàn)信息共享的一種重要手段.由于高維數(shù)據(jù)(例如，醫(yī)療健康數(shù)據(jù)、金融數(shù)據(jù)等)中蘊(yùn)含著豐富的信息，分析或挖掘高維數(shù)據(jù)能夠提供有效的決策支持.現(xiàn)如今，高維數(shù)據(jù)已經(jīng)成為數(shù)據(jù)發(fā)布的重要數(shù)據(jù)類型.然而，如果所發(fā)布的高維數(shù)據(jù)涉及個(gè)人敏感信息，直接發(fā)布這些數(shù)據(jù)會(huì)造成嚴(yán)重的個(gè)人隱私泄露.

近年來提出的差分隱私[1](Differential Privacy)技術(shù)為解決數(shù)據(jù)分析、數(shù)據(jù)發(fā)布帶來的個(gè)人隱私泄露問題提供了一種可行的方案[2-6].與傳統(tǒng)的基于匿名的隱私保護(hù)模型(例如，k-匿名[7]和l-多樣性[8])不同，差分隱私提供了一種嚴(yán)格、可量化的隱私保護(hù)手段，并且所提供的隱私保護(hù)強(qiáng)度并不依賴于攻擊者所掌握的背景知識.差分隱私通過在數(shù)據(jù)處理過程中添加隨機(jī)噪音以達(dá)到隱私保護(hù)的目的，并確保在數(shù)據(jù)集中插入或刪除某一條記錄不會(huì)顯著地影響輸出結(jié)果.因此，即使攻擊者獲得了數(shù)據(jù)集中除一條記錄之外的其他所有記錄的信息，差分隱私仍可以保證攻擊者不能通過所掌握的其他記錄信息推斷出該條記錄中蘊(yùn)含的敏感信息，從而有效地保護(hù)了數(shù)據(jù)集中包含的個(gè)人隱私信息.正是因?yàn)樯鲜鰞?yōu)點(diǎn)，差分隱私技術(shù)已經(jīng)得到了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注.

本文提出了一種基于隱樹模型的滿足差分隱私的高維數(shù)據(jù)發(fā)布算法(記為LTMDP).該算法通過隱變量生成、隱樹結(jié)構(gòu)學(xué)習(xí)、隱樹參數(shù)學(xué)習(xí)和數(shù)據(jù)生成四個(gè)階段實(shí)現(xiàn)了滿足差分隱私的高維數(shù)據(jù)發(fā)布.特別地，在該算法中，為了在顯變量分組及生成隱變量的過程中保護(hù)隱私，本文提出了一種滿足差分隱私的隱變量生成方法(記為DPLAG).此外，為了在構(gòu)建隱樹的過程中保護(hù)隱私，我們提出了一種滿足差分隱私的隱樹模型結(jié)構(gòu)學(xué)習(xí)方法(記為DPSL).理論分析表明所提出的LTMDP算法滿足ε-差分隱私.實(shí)驗(yàn)結(jié)果表明，與現(xiàn)有研究工作相比，所提出的LTMDP算法可以在保證相同隱私強(qiáng)度的情況下獲得更好的數(shù)據(jù)效用.

2 相關(guān)工作

針對滿足差分隱私的數(shù)據(jù)發(fā)布問題，國內(nèi)外研究人員已經(jīng)取得了一定成果. 其中，Qi[2]等人提出了PCA-based PPDP算法，該算法采用拉普拉斯機(jī)制，直接分解原始數(shù)據(jù)的協(xié)方差矩陣，隨后在投影矩陣上添加噪音，并基于線性判別分析對發(fā)布數(shù)據(jù)的分類問題進(jìn)行了優(yōu)化.然而，使用該方法所發(fā)布的數(shù)據(jù)集只支持分類任務(wù).Day[9]等人提出了DPSense算法，該算法引入低敏感度質(zhì)量函數(shù)，將敏感度限制在一定的范圍內(nèi)，并引入了一個(gè)比例因子，用于糾正限制敏感度所引起的誤差.然而，該算法只適用于發(fā)布數(shù)據(jù)的統(tǒng)計(jì)信息，因此，并不適用于本文的問題場景.

特別地，針對滿足差分隱私的高維數(shù)據(jù)發(fā)布問題，Zhang[10]等人提出了PrivBayes算法，該算法在滿足差分隱私的條件下使用貝葉斯網(wǎng)絡(luò)模型近似高維數(shù)據(jù)屬性間的聯(lián)合概率分布，然后利用所學(xué)習(xí)的貝葉斯網(wǎng)生成高維數(shù)據(jù)集.此外，Chen[11]等人提出了JTree算法，該算法利用高維數(shù)據(jù)屬性間的依賴關(guān)系構(gòu)建屬性依賴圖，并根據(jù)該圖所確定的邊際分布表來估計(jì)屬性間的聯(lián)合概率分布.與上述兩種算法不同，本文基于隱樹模型提出了一種滿足差分隱私的高維數(shù)據(jù)發(fā)布算法LTMDP.與上述兩種算法相比，采用隱樹模型對高維數(shù)據(jù)進(jìn)行建?？梢源罅繙p少所需計(jì)算關(guān)聯(lián)強(qiáng)度的屬性對數(shù)量，從而減少噪音的攝入量，獲得更好的數(shù)據(jù)效用.

3 預(yù)備知識

3.1 差分隱私

給定任意兩個(gè)數(shù)據(jù)集D和D′，假設(shè)D和D′相差且僅相差一條記錄，稱這兩個(gè)數(shù)據(jù)集為相鄰數(shù)據(jù)集.差分隱私保護(hù)模型的具體定義如下.

定義1(ε-差分隱私).給定算法A，假設(shè)數(shù)據(jù)集D和D′為任意相鄰數(shù)據(jù)集.對于算法A的任意可能輸出結(jié)果S，如果算法A在數(shù)據(jù)集D中輸出S的概率與算法A在數(shù)據(jù)集D′中輸出S的概率的比值滿足

Pr[A(D)∈S]≤exp(ε)×Pr([A(D′)∈S])

(1)

我們稱算法A滿足ε-差分隱私.

在數(shù)據(jù)集D中加入或者刪除一條記錄后，函數(shù)f輸出結(jié)果的最大改變量稱為函數(shù)f的敏感度，其定義如下.

定義2(敏感度).對于函數(shù)f，其敏感度為：

Δf=max‖f(D)-f(D′)‖

(2)

其中，數(shù)據(jù)集D和D′是任意相鄰數(shù)據(jù)集.

定理1(拉普拉斯機(jī)制).對于敏感度為Δf的函數(shù)f，隨機(jī)算法A(D)=f(D)+Lap(λ)滿足ε-差分隱私，其中Lap(λ)是服從λ=Δf/ε的拉普拉斯分布.

定理2(指數(shù)機(jī)制).給定數(shù)據(jù)集D，輸出空間R和打分函數(shù)u，對于一個(gè)隨機(jī)算法A，如果

(3)

則算法A滿足ε-差分隱私，其中Δu是打分函數(shù)u的敏感度.

定理4(并行性質(zhì)).給定k個(gè)滿足差分隱私的算法A1,…，Ak.其中，任意算法Ai滿足εi-差分隱私.如果算法A1,…，Ak分別作用于不相交的數(shù)據(jù)集D1,…，Dk上，那么算法A1,…，Ak構(gòu)成的組合算法滿足max{ε1,…,εk} -差分隱私.

3.2 隱樹模型

隱樹模型[12]是一種樹狀的概率圖模型，它能夠體現(xiàn)一系列隨機(jī)變量的聯(lián)合概率分布情況.在隱樹模型中，葉子節(jié)點(diǎn)代表數(shù)據(jù)中的可見屬性(即顯變量)，內(nèi)部節(jié)點(diǎn)代表隱含屬性(即隱變量).顯變量X={X1,…,Xm}和隱變量Y={Y1,…,Yn}所代表的節(jié)點(diǎn)一起組成了頂點(diǎn)集V={V1,…,Vn,Vn+m}，頂點(diǎn)之間的邊E代表了頂點(diǎn)之間的依賴關(guān)系.如果頂點(diǎn)Vj到頂點(diǎn)Vi之間存在一條有向邊，那么定義頂點(diǎn)Vj是頂點(diǎn)Vi的父節(jié)點(diǎn)，Vj也可以用Πi表示.圖1給出了一個(gè)隱樹模型的例子.樹結(jié)構(gòu)T滿足以下獨(dú)立性假設(shè)：對于每個(gè)節(jié)點(diǎn)Vi，給定父節(jié)點(diǎn)Πi，Vi與Πi的他的子節(jié)點(diǎn)獨(dú)立.隱樹模型中涉及的所有變量的聯(lián)合概率分布可以表示為：

圖1 隱樹模型示例圖 Fig.1 Example latent tree model

(4)

通過公式(4)，可以進(jìn)一步得到顯變量之間的聯(lián)合概率分布

PrT(X)≈∑y1∈ΩY1…∑ym∈ΩYmPr(V)

(5)

其中ΩYi是Yi的取值空間.

學(xué)習(xí)隱樹模型的基本步驟如下：1)根據(jù)顯變量之間的關(guān)聯(lián)強(qiáng)度對顯變量進(jìn)行分組，并為每一個(gè)分組產(chǎn)生一個(gè)隱變量；2)根據(jù)隱變量之間的關(guān)聯(lián)強(qiáng)度構(gòu)建隱樹；3)對于隱樹中除根節(jié)點(diǎn)外的每一個(gè)節(jié)點(diǎn)Vi，計(jì)算條件概率分布Pr(Vi|Πi).

我們通常把步驟2稱為隱樹模型的結(jié)構(gòu)學(xué)習(xí)階段，把步驟3稱作隱樹模型的參數(shù)學(xué)習(xí)階段.

給定高維數(shù)據(jù)集D和其屬性集X，通過在D上學(xué)習(xí)隱樹模型可以近似表示數(shù)據(jù)集D上所有屬性的聯(lián)合概率分布.

4 LTMDP算法

4.1 LTMDP算法概述

為了降低在高維數(shù)據(jù)發(fā)布過程中加入的噪音量，提高所發(fā)布數(shù)據(jù)的效用，同時(shí)滿足差分隱私保護(hù)，我們提出了一種基于隱樹模型的滿足差分隱私的高維數(shù)據(jù)發(fā)布算法(記作 LTMDP).

LTMDP算法由隱變量生成、隱樹結(jié)構(gòu)學(xué)習(xí)、隱樹參數(shù)學(xué)習(xí)、數(shù)據(jù)生成四個(gè)階段組成.其中前三個(gè)階段需要直接或者間接地訪問原始數(shù)據(jù)集，因此需要在這三個(gè)階段中提供差分隱私保護(hù).特別地，我們將總體隱私參數(shù)ε分為三個(gè)部分(ε1=ε2=ε3=ε/3)，分別用于這三個(gè)階段.LTMDP算法四個(gè)階段的概述如下.

1)隱變量生成.在此階段中，我們首先計(jì)算顯變量X={X1，…,Xm}之間的互信息作為它們之間的關(guān)聯(lián)強(qiáng)度，對顯變量進(jìn)行分組，然后為每一個(gè)分組生成一個(gè)隱變量，從而得到隱變量組成的數(shù)據(jù)集D*.為了在滿足差分隱私的條件下對顯變量進(jìn)行分組并生成隱變量，我們提出了一種滿足差分隱私的隱變量生成方法(記作DPLAG)，詳見章節(jié)4.2.

2)隱樹模型結(jié)構(gòu)學(xué)習(xí).此階段完成隱樹模型結(jié)構(gòu)的構(gòu)建.為此，我們提出了一種滿足差分隱私的隱樹模型結(jié)構(gòu)學(xué)習(xí)方法(記作DPSL).在該方法中，我們首先在滿足差分隱私的條件下計(jì)算隱變量Y={Y1，…，Yn}之間的互信息作為它們之間的關(guān)聯(lián)強(qiáng)度，然后以隱變量之間的關(guān)聯(lián)強(qiáng)度作為隱變量間所連邊的權(quán)值，構(gòu)建一棵最大生成樹.最后，我們隨機(jī)選擇一個(gè)隱變量作為根節(jié)點(diǎn)，并根據(jù)各個(gè)隱變量與根節(jié)點(diǎn)的距離確定各個(gè)隱變量之間的父子關(guān)系，從而得到隱樹結(jié)構(gòu)，詳見章節(jié)4.3.

3)隱樹模型參數(shù)學(xué)習(xí).在滿足差分隱私的條件下，對于隱樹中的每一個(gè)顯變量節(jié)點(diǎn)，我們計(jì)算在給定其父節(jié)點(diǎn)條件下的概率分布.特別地，我們首先統(tǒng)計(jì)每個(gè)顯變量節(jié)點(diǎn)與其父節(jié)點(diǎn)的聯(lián)合概率分布，并在計(jì)算過程中加入拉普拉斯噪聲.然后，我們利用帶有噪音的聯(lián)合分布計(jì)算出除根節(jié)點(diǎn)外的每一個(gè)節(jié)點(diǎn)在給定其父節(jié)點(diǎn)條件下的概率分布.

4)數(shù)據(jù)生成.通過學(xué)習(xí)到的隱樹模型，我們采用自頂向下的方式對隱變量和顯變量的取值進(jìn)行采樣，從而生成滿足差分隱私保護(hù)的高維數(shù)據(jù)集.

4.2 滿足差分隱私的隱變量生成方法

為了在滿足差分隱私的條件下生成隱變量，我們提出了滿足差分隱私的隱變量生成方法(記作DPLAG).該方法在滿足差分隱私的條件下，對顯變量X={X1，…，Xm}進(jìn)行分組，并生成隱變量Y={Y1，…，Yn}.

在不考慮隱私保護(hù)的場景下，Steeg等人[13]提出了Corex方法來生成隱變量.對于一組顯變量X，Corex方法通過計(jì)算它們之間的互信息來度量它們之間的關(guān)聯(lián)強(qiáng)度TC(X)：

(6)

其中H(·)代表了熵值計(jì)算函數(shù)，m為X中顯變量的個(gè)數(shù).對于一組顯變量X，在給定一個(gè)隱變量Yj的條件下，它們之間的關(guān)聯(lián)強(qiáng)度為：

(7)

隱變量Yj與一組顯變量X之間的關(guān)聯(lián)強(qiáng)度可以通過以下方式計(jì)算：

(8)

為一組顯變量X={X1，…，Xm}生成隱變量Y={Y1，…，Yn}，可以看作是對式(8)的優(yōu)化過程：

(9)

其中，Gj是X的一個(gè)子集，它對應(yīng)于隱變量Yj.

Corex方法的目標(biāo)是為每個(gè)顯變量找到合適的分組Gj和相應(yīng)的隱變量Yj，使得隱變量Yj能夠很好的表示Gj中的顯變量.Corex方法交替更新分組關(guān)系{G1，…，Gn}和隱變量{Y1，…，Yn}，多次迭代直至式(9)的值達(dá)到收斂.

為了使上述過程滿足差分隱私，一種簡單的方法是在迭代的過程中直接加入拉普拉斯噪音.然而，由于高維數(shù)據(jù)集屬性數(shù)量多，該方法需要多次訪問原始數(shù)據(jù)集，并在每次訪問過程中加入噪音來保證差分隱私.因此，這種簡單的方法會(huì)嚴(yán)重影響數(shù)據(jù)效用.

我們觀察到，由于對于每一個(gè)顯變量Xi∈Gj，Xi和Gj中其它節(jié)點(diǎn)的關(guān)聯(lián)強(qiáng)度應(yīng)比Xi和其他分組中節(jié)點(diǎn)的關(guān)聯(lián)強(qiáng)度高，因此，我們可以依據(jù)顯變量之間的關(guān)聯(lián)強(qiáng)度提前確定分組關(guān)系.基于以上觀察，我們提出了滿足差分隱私的隱變量生成方法(記作DPLAG).在DPLAG方法中，我們不再交替優(yōu)化顯變量分組結(jié)果和隱變量生成結(jié)果，而是將生成隱變量的過程分為確定顯變量分組和隱變量生成兩個(gè)步驟.算法1給出了滿足差分隱私的隱變量生成方法DPLAG的細(xì)節(jié).

算法1. 滿足差分隱私的隱變量生成

輸入：高維數(shù)據(jù)集D和其屬性集X，每個(gè)分組中變量的最大個(gè)數(shù)c，隱私參數(shù)ε1

輸出：顯變量分組集合G，隱變量集合Y，隱變量數(shù)據(jù)集D*

1：初始化X′=X，G=?，Y=?；

2：m=|X|，n=「m/c?，k=0，j=0；

3：whilej≤ndo

4：Gj=?；

5：j++；

6：endwhile

7：j=0；

8：whilek

9：ifk可以被c整除then

10：j++；

11： 從X′中隨機(jī)選出顯變量Xr；

12：else

13：for每一個(gè)顯變量Xi∈X′do

14： 計(jì)算Xi與Gj的互信息I(Xi;Gj)；

15：endfor

17：endif

18：Gj=Gj∪{Xr}；

19：G=G∪Gj；

20：X′=X′/{Xr}；

21：k++；

22：endwhile

23：根據(jù)G，生成隱變量所對應(yīng)的數(shù)據(jù)集D*；

24：returnG,YandD*；

在DPLAG 算法的第一階段(第8 行到第22 行)，我們首先以顯變量之間的互信息作為衡量指標(biāo)，將數(shù)據(jù)集中的顯變量X={X1，…,Xm}分為多組，并使得同一組內(nèi)的顯變量之間具有較高的關(guān)聯(lián)強(qiáng)度.為了滿足ε-差分隱私保護(hù)，我們在對顯變量進(jìn)行分組的過程中應(yīng)用差分隱私指數(shù)機(jī)制.在DPLAG 算法的第二階段(第23 行)，我們基于拉格朗日優(yōu)化方法，為每個(gè)確定的顯變量分組Gj∈G，生成一個(gè)對應(yīng)的隱變量Yj，從而得到隱變量對應(yīng)的集合D*.

4.3 滿足差分隱私的隱樹模型結(jié)構(gòu)學(xué)習(xí)

為了在滿足差分隱私的條件下，利用已生成的隱變量構(gòu)建隱樹，我們提出一種滿足差分隱私的隱樹模型結(jié)構(gòu)學(xué)習(xí)方法(記作DPSL).在DPSL 方法中，我們采用互信息作為隱變量間關(guān)聯(lián)強(qiáng)度的衡量標(biāo)準(zhǔn)，并在隱變量互信息計(jì)算過程中加入拉普拉斯噪聲來保證差分隱私.特別地，對于每個(gè)顯變量，我們將其所在分組對應(yīng)的隱變量作為它的父節(jié)點(diǎn)；對于任意兩個(gè)隱變量，我們將它們之間的互信息作為它們之間連接邊的權(quán)值.接著，我們采用最大生成樹算法得到隱樹結(jié)構(gòu)T，并隨機(jī)選擇一個(gè)隱變量作為T的根節(jié)點(diǎn).算法2給出了滿足差分隱私的隱樹模型結(jié)構(gòu)學(xué)習(xí)方法DPSL的細(xì)節(jié).

算法2. 滿足差分隱私的隱樹模型結(jié)構(gòu)學(xué)習(xí)

輸入：隱變量數(shù)據(jù)集D*和其屬性集Y，隱私參數(shù)ε2

輸出：隱樹模型的結(jié)構(gòu)T

1：for每兩個(gè)隱變量Yi,Yj∈Ydo

3： 根據(jù)Pr(Yi，Yj)計(jì)算Yi與Yj的互信息I(Yi；Yj) ；

4：endfor

5： 將所有隱變量之間邊的權(quán)值設(shè)置為它們的互信息；

6： 采用最大生成樹算法生成隱樹模型的結(jié)構(gòu)T；

7： 從Y中隨機(jī)選擇一個(gè)隱變量做為T的根節(jié)點(diǎn)R；

8：returnT；

4.4 隱私分析

引理1.隱變量生成方法DPLAG 滿足ε1-差分隱私.

引理2.隱樹模型結(jié)構(gòu)學(xué)習(xí)方法DPSL滿足ε2-差分隱私.

證明：隱樹模型結(jié)構(gòu)學(xué)習(xí)方法包括隱變量互信息計(jì)算和隱樹結(jié)構(gòu)生成兩個(gè)階段.其中，隱樹結(jié)構(gòu)生成這一階段并不需要訪問原始數(shù)據(jù)集D或隱變量數(shù)據(jù)集D*，因此無須提供差分隱私保護(hù)D*.然而，在隱變量互信息計(jì)算階段，我們需要訪問隱變量數(shù)據(jù)集 獲得任意兩個(gè)隱變量的聯(lián)合分布.在此過程中，我們需要提供差分隱私保護(hù).

給定一個(gè)轉(zhuǎn)換函數(shù)Γ：D*=Γ(D)，和一個(gè)統(tǒng)計(jì)函數(shù)S：Pr(Y)=S(D*)，存在一個(gè)函數(shù)滿足φ=s°Γ且Pr(Y)=φ(D)，其中，D和D*分別由顯變量X={X1，…，Xm}的取值和隱變量Y={Y1，…，Yn}的取值組成.因此，隱變量的聯(lián)合分布可以通過在數(shù)據(jù)集D上執(zhí)φ行函數(shù)來得到.對于任意兩個(gè)相鄰數(shù)據(jù)集D和D′，函數(shù)φ的敏感度是：

S(φ) =‖φ(D)-φ(D′)‖

=‖Pr(Y|D)-Pr(Y|D′)‖

=∑y∈ΩY|Pr(y|D)-Pr(y|D′)|≤4/|D*|

(10)

引理3.隱樹模型參數(shù)學(xué)習(xí)階段滿足ε3-差分隱私.

定理5.所提出的算法LTMDP 滿足ε-差分隱私.

證明:LTMDP 算法由四個(gè)階段組成，其中數(shù)據(jù)生成階段不需要訪問原始數(shù)據(jù)集D或隱變量數(shù)據(jù)集D*，因此不需要提供差分隱私保護(hù).由引理1、引理2 和引理3 可知，LTMDP算法的隱變量生成階段、隱樹模型結(jié)構(gòu)學(xué)習(xí)階段和隱樹模型參數(shù)學(xué)習(xí)階段分別滿足ε1-差分隱私、ε2-差分隱私和ε3-差分隱私.根據(jù)差分隱私的串行性質(zhì)，LTMDP滿足ε-差分隱私，其中ε=ε1+ε2+ε3.

5 實(shí)驗(yàn)評估

5.1 實(shí)驗(yàn)設(shè)置

為了驗(yàn)證LTMDP算法的性能，本文將文獻(xiàn)[10]中提出的PrivBayes算法作為對比算法，并分別在TPC-E[14]和Big5[14]兩個(gè)真實(shí)數(shù)據(jù)集上對這兩個(gè)算法進(jìn)行了性能測試.TPC-E數(shù)據(jù)集共含有40000條記錄，每條記錄包含24個(gè)屬性的信息，其中，一部分屬性的取值是離散值，另一部分屬性的取值是連續(xù)值；Big5數(shù)據(jù)集共含有19719條記錄，每條記錄包含57個(gè)屬性的信息，每個(gè)屬性反映某一個(gè)體對問卷調(diào)查中的相關(guān)問題的態(tài)度，共有五種可能的取值：同意，輕微同意，中立，輕微反對，反對.

在實(shí)驗(yàn)之前，本文進(jìn)行了以下預(yù)處理過程：采用文獻(xiàn)[15]中的方法將非二進(jìn)制屬性轉(zhuǎn)換為多個(gè)二進(jìn)制屬性.經(jīng)過轉(zhuǎn)換，TPC-E和Big5兩個(gè)真實(shí)數(shù)據(jù)集中每條記錄包含的二進(jìn)制屬性個(gè)數(shù)分別為77個(gè)和175個(gè).因?yàn)樵撧D(zhuǎn)換操作只與屬性的公共取值空間有關(guān)，因此，轉(zhuǎn)換過程中沒有涉及任何敏感信息，不需要考慮隱私泄露問題.

為了評估算法所生成數(shù)據(jù)集的效用，本文在生成的數(shù)據(jù)集上測試了兩種分析任務(wù)的性能.第一個(gè)分析任務(wù)是α-邊際分布(α-way marginal)計(jì)算.在實(shí)驗(yàn)中，本文分別在兩個(gè)數(shù)據(jù)集上進(jìn)行了2-邊際分布測試.具體地講，我們計(jì)算生成數(shù)據(jù)集中各屬性與原始數(shù)據(jù)集中各屬性的2-邊際分布的總邊際距離[16](total variation distance)，并將所有屬性的2-邊際分布的平均邊際距離(average variation distance)作為衡量標(biāo)準(zhǔn)，來評估生成數(shù)據(jù)集的α-邊際分布的準(zhǔn)確性.第二個(gè)分析任務(wù)是SVM分類.具體地講，本文在生成的數(shù)據(jù)集上訓(xùn)練多個(gè)SVM分類器，在每個(gè)SVM分類器中，取一個(gè)屬性作為分類結(jié)果，并用其他所有屬性作為特征來訓(xùn)練SVM分類器，從而對該屬性的取值進(jìn)行預(yù)測.另外，對于每個(gè)分類任務(wù)，我們采用生成數(shù)據(jù)集中80%的數(shù)據(jù)作為訓(xùn)練集，剩下20%的數(shù)據(jù)作為測試集.進(jìn)一步，本文采用誤分類率(misclassification rate)作為衡量標(biāo)準(zhǔn)，來評估生成數(shù)據(jù)集的SVM分類任務(wù)的準(zhǔn)確性.

所有的實(shí)驗(yàn)在一臺配置為Intel Core I7 2.7GHZ CPU、12GB RAM的PC機(jī)上運(yùn)行.由于測試算法均為隨機(jī)算法，本文將每種分析任務(wù)運(yùn)行20次，并將每次輸出結(jié)果的平均值作為最終的實(shí)驗(yàn)結(jié)果.

5.2 實(shí)驗(yàn)結(jié)果

圖2和圖3分別展示了PrivBayes算法和LTMDP算法在TPC-E數(shù)據(jù)集上的2-邊際分布的平均邊際距離結(jié)果和誤分類率結(jié)果.TPC-E數(shù)據(jù)集的屬性個(gè)數(shù)有24個(gè)，對非二進(jìn)制屬性進(jìn)行二進(jìn)制轉(zhuǎn)化之后，二進(jìn)制屬性共有77個(gè).隨著屬性個(gè)數(shù)的增加，LTMDP算法的優(yōu)勢逐漸顯現(xiàn)了出來，在隱私參數(shù)相同時(shí)，LTMDP算法的平均邊際距離和誤分類率均小于PrivBayes算法.這說明LTMDP算法可以獲得更高的數(shù)據(jù)效用.

圖2 TPC-E數(shù)據(jù)集上SVM分類結(jié)果Fig.2 ResultsofSVMonTPC-E圖3 Big5數(shù)據(jù)集上SVM分類結(jié)果Fig.3 ResultsofSVMonBig5

圖4和圖5分別展示了PrivBayes算法和LTMDP算法在Big5數(shù)據(jù)集上的2-邊際分布的平均邊際距離結(jié)果和誤分類率結(jié)果.與TPC-E數(shù)據(jù)集相比，Big5數(shù)據(jù)集維度更高，屬性個(gè)數(shù)有57個(gè)，對非二進(jìn)制屬性進(jìn)行二進(jìn)制轉(zhuǎn)化之后，二進(jìn)制屬性共有175個(gè).可以看出，在更高維度的數(shù)據(jù)集上，LTMDP算法的優(yōu)勢更加明顯，平均邊際距離和誤分類率明顯小于PrivBayes算法.這是因?yàn)殡S著屬性個(gè)數(shù)的增加，PrivBayes算法在構(gòu)建貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)(結(jié)構(gòu)學(xué)習(xí)階段)時(shí)，構(gòu)造出的屬性-父節(jié)點(diǎn)對(attribute-parent pair)的數(shù)量呈平方級增長，而在構(gòu)造每個(gè)屬性-父節(jié)點(diǎn)對時(shí)，都需要訪問原始數(shù)據(jù)集計(jì)算其關(guān)聯(lián)強(qiáng)度，這個(gè)過程中需要添加大量的噪聲，導(dǎo)致數(shù)據(jù)效用偏低.而對于LTMDP算法，在結(jié)構(gòu)學(xué)習(xí)階段構(gòu)建隱樹模型時(shí)，只需要確定少量隱含屬性的連接結(jié)構(gòu)，進(jìn)一步使參數(shù)學(xué)習(xí)階段需要計(jì)算關(guān)聯(lián)強(qiáng)度的屬性對數(shù)量大大減少，從而保證了良好的數(shù)據(jù)效用.

圖4 TPC-E數(shù)據(jù)集上2-邊際分布結(jié)果Fig.4 Resultsof2-waymarginalsonTPC-E圖5 Big5數(shù)據(jù)集上2-邊際分布結(jié)果Fig.5 Resultsof2-waymarginalsonBig5

6 結(jié)束語

隱私保護(hù)的高維數(shù)據(jù)發(fā)布具有重要的理論和現(xiàn)實(shí)意義.基于隱樹模型，本文提出了一種新的滿足差分隱私的高維數(shù)據(jù)發(fā)布算法LTMDP.分析結(jié)果表明LTMDP算法滿足-差分隱私.在真實(shí)數(shù)據(jù)集上獲得的實(shí)驗(yàn)結(jié)果表明，與現(xiàn)有算法相比，本文提出的算法能夠在相同的隱私保護(hù)強(qiáng)度下獲得更好的數(shù)據(jù)效用.

[1] Dwork C，McSherry F，Nissim K，et al.Calibrating noise to sensitivity in private data analysis[C].Theory of Cryptography Conference，2006:265-284.

[2] Qi Ming-yu，Huang Liu-sheng，Lu Xiao-rong，et al.Differential privacy data publish algorithm with compont analysis[J].Journal of Chinese Computer Systems，2017，38(3)：437-443.

[3] Lu Ye，Lu Jing.Differential privacy and prefix tree based research for search log privacy protection[J].Journal of Chinese Computer Systems，2016，37(3)：540-544.

[4] Ye Yun，Yu Yong，Huang Liu-sheng，et al.Privacy-preserving top-m DK-Outlier based outlier detection[J].Journal of Chinese Computer Systems，2016，37(12)：2638-2642.

[5] Gan Wen-yong，Wu Ying-jie，Sun Lan，et al.Frequent pattern mining with differential privacy based on transaction truncation[J].Journal of Chinese Computer Systems，2015，36(11)：2583-2587.

[6] Li Yang，Hao Zhi-feng，Xiao Yan-shan，et al.Multidimensional data visualization using aggregation method of differential privacy equipartition k-means[J].Journal of Chinese Computer Systems，2013，34(7)：1637-1640.

[7] Sweeney L.K-Anonymity：a model for protecting privacy[J].International Journal of Uncertainty，F(xiàn)uzziness and Knowledge-Based Systems，2002，10(5)：557-570.

[8] Machanavajjhala A，Gehrke J，Kifer D，et al.L-Diversity：Privacy beyond k-anonymity[J].ACM Transactions on Knowledge Discovery from Data，2007，1(1)：3.

[9] Day W，Li N.Differentially private publishing of high-dimensional data using sensitivity control[C].Symposium on Information，Computer and Communications Security，2015:451-462.

[10] Zhang J，Cormode G，Procopiuc C，et al.Privbayes：private data release via bayesian networks[C].Special Interest Group on Management of Data，2014，1423-1434.

[11] Chen R，Xiao Q，Zhang Y.Differentially private high-dimensional data publication via sampling-based inference[C].International Conference on Knowledge Discovery and Data Mining，2015:129-138.

[12] Choi M，Tan V，Anandkumar A，et al.Learning latent tree graphical models[J].Journal of Machine Learning Research，2011，12(5)：1771-1812.

[13] Steeg G V，Galstyan A.Discovering structure in high-dimensional data through correlation explanation[C].Annual Conference on Neural Information Processing Systems，2014:577-585.

[14] Bache K，Lichman M.Uci machine learning repository[C].The Principles of Database Systems Symposium，2013.

[15] Yaroslavtsev G，Cormode G，Srivastava D.Accurate and efficient private release of datacubes and contingency tables[C].International Conference on Data Engineering，2013:745-756.

[16] Tsybakov A.Introduction to nonparametric estimation[M].Springer Series in Statistics,Berlin，Springer，2009.

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

[2] 戚名鈺，黃劉生，陸瀟榕，等.采用成分分析的差分隱私數(shù)據(jù)發(fā)布算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2017，38(3)：437-443.

[3] 陸 葉，盧 菁.基于差分隱私與前綴樹的搜索日志隱私保護(hù)研究[J].小型微型計(jì)算機(jī)系統(tǒng)，2016，37(3)：540-544.

[4] 葉 云，余 勇，黃劉生，等.一種基于top-m DK-Outlier的隱私保護(hù)異常數(shù)據(jù)檢測算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2016，37(12)：2638-2642.

[5] 甘文勇，吳英杰，孫 嵐，等.基于事務(wù)截?cái)嗟牟罘蛛[私頻繁模式挖掘算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2015，36(11)：2583-2587.

[6] 李 楊，郝志峰，肖燕珊，等.差分隱私DPE k-means數(shù)據(jù)聚合下的多維數(shù)據(jù)可視化[J].小型微型計(jì)算機(jī)系統(tǒng)，2013，34(7)：1637-1640.