基于聯(lián)合樹的隱私高維數(shù)據(jù)發(fā)布方法

張嘯劍 陳 莉 金凱忠 孟小峰

1(河南財經(jīng)政法大學計算機與信息工程學院 鄭州 450002) 2(河南財經(jīng)政法大學網(wǎng)絡(luò)信息安全研究所 鄭州 450046) 3 (中國人民大學信息學院 北京 100872)

近年來，基于差分隱私的數(shù)據(jù)發(fā)布已成為隱私保護領(lǐng)域重要研究點.目前大多數(shù)研究均聚焦于低維數(shù)據(jù)或者一維數(shù)據(jù)的發(fā)布.高維數(shù)據(jù)在現(xiàn)實生活中普遍存在，例如個人購物數(shù)據(jù)、移動軌跡數(shù)據(jù)等.通過對這些高維數(shù)據(jù)發(fā)布與分析可以產(chǎn)生更加有意義的模式.由于高維數(shù)據(jù)通常蘊含大量個人隱私信息(例如購物記錄中的敏感商品)，直接發(fā)布將泄露個人敏感信息.然而如何在高維數(shù)據(jù)中得到統(tǒng)計結(jié)果的同時，又要保護原始數(shù)據(jù)隱私是個非常具有挑戰(zhàn)性問題.其主要原因是隨著維度與維度值域的增加，所形成的發(fā)布空間呈指數(shù)增長.例如設(shè)某數(shù)據(jù)集擁有1 000萬條記錄，每條記錄的維度(或者屬性)為10，每個維度有20個取值，對于全分布的域大小則有2010≈10TB個單元.如果直接利用噪音機制對10TB的輸出單元添加噪音，則所需隱私預(yù)算、存儲空間以及計算代價非常高.此外，每個單元的信息量非常小，假設(shè)1 000萬條記錄的大小為10 MB，則每個單元的真實信息量為10 MB/10TB=10-6.若設(shè)定隱私預(yù)算ε=0.01，利用拉普拉斯機制[1]產(chǎn)生的噪音約等于125(lap(1/0.01)≈125).如果直接為每個單元添加125大小的噪音，則該噪音值極大地扭曲了每個單元中的真實值(即125+10-6)，發(fā)布結(jié)果的可用性極差.

目前已有少數(shù)基于概率圖模型[2-3]、閾值過濾技術(shù)[4]以及投影技術(shù)[5]的高維數(shù)據(jù)發(fā)布方法，利用維度轉(zhuǎn)換達到降維效果以及減少噪音對發(fā)布結(jié)果的影響，這些方法存在2個問題：

1) 文獻[2-3]中的基于概率圖模型方法通常利用指數(shù)機制[6]與稀疏向量[7]技術(shù)挑選屬性關(guān)系對.然而，文獻[2]中基于指數(shù)機制的屬性對挑選方法受到候選空間大小的影響.如果候選空間非常大，所挑選的屬性對越來越不準確，進而導致基于所選屬性對構(gòu)建的概率圖不準確；文獻[3]中采用稀疏向量技術(shù)挑選屬性對，然而該技術(shù)并不滿足差分隱私，進而導致文獻[3]中整個高維數(shù)據(jù)發(fā)布方法不滿足差分隱私.

2) 文獻[4-5]中的基于閾值過濾與投影技術(shù)沒有顧及到屬性之間的依賴關(guān)系，利用閾值對維度直接截斷達到降維效果.然而高維數(shù)據(jù)的屬性之間普遍存在依賴關(guān)系，文獻[4-5]中方法的實際可用性比較低.

總而言之，目前還沒有一個行之有效的高維數(shù)據(jù)發(fā)布方法同時克服上述2種問題帶來的不足.為此，本文基于聯(lián)合樹提出一種高效的高維數(shù)據(jù)發(fā)布技術(shù).本文主要貢獻包括3個方面：

1) 為了挑選出彼此關(guān)聯(lián)的候選屬性對，提出一種基于高通濾波的閾值過濾技術(shù)來縮減候選空間；

2) 結(jié)合縮減后的屬性對候選空間，利用指數(shù)機制提出一種屬性依賴圖生成方法.結(jié)合屬性依賴圖，提出一種基于最大生成樹技術(shù)的聯(lián)合樹生成方法.利用聯(lián)合樹推理出整體高維數(shù)據(jù)的聯(lián)合分布，進而得到滿足差分隱私的高維數(shù)據(jù)發(fā)布結(jié)果.

3) 理論證明所提出的高維數(shù)據(jù)發(fā)布方法滿足ε-差分隱私.在5種真實數(shù)據(jù)集上進行了可用性評估實驗.實驗結(jié)果表明：PrivHD算法均優(yōu)于PrivBayes與JTree算法.

1 相關(guān)工作

目前，基于差分隱私的高維數(shù)據(jù)發(fā)布方法主要分為2類：數(shù)據(jù)獨立發(fā)布方法與數(shù)據(jù)相關(guān)發(fā)布方法.PriView[8]是數(shù)據(jù)獨立發(fā)布方法的典型代表.該方法均等地處理所有的屬性對，通過選擇k(1

2 定義與問題

2.1 差分隱私

差分隱私保護模型[13-14]的精髓是確保在數(shù)據(jù)集中插入或者刪除一條記錄的操作不會影響任何計算的輸出.相比于傳統(tǒng)的隱私保護模型，差分隱私保護模型具有2個顯著的特點：1)不依賴于攻擊者的背景知識；2)具有嚴謹?shù)慕y(tǒng)計學模型，能夠提供可量化的隱私保證.

定義1. 設(shè)高維數(shù)據(jù)D與D′彼此相差1條記錄，互為近鄰關(guān)系.給定一個高維數(shù)據(jù)發(fā)布算法H，Range(H)為H的輸出范圍，若算法H在D和D′上 任意輸出結(jié)果X∈Range(H)滿足:

Pr[H(D)=X]≤exp(ε)×Pr[H(D′)=X],

(1)

則H滿足ε-差分隱私.式(1)中,ε表示隱私預(yù)算，其值越小則算法H的隱私保護程度越高;Pr[H(D)=X]表示算法H基于D輸出X的概率.

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

定義2. 設(shè)f為某一個查詢，且f:D→d，f的全局敏感性為

(2)

其中,D與D′互為近鄰，為映射的實數(shù)空間，d為f的查詢維度.

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

定理1[6]. 設(shè)f為某個查詢函數(shù)，且f:D→d，若方法H符合:

H(D)=f(D)+
[lap1(Δfε),lap2(Δfε),…,lapd(Δfε)],

(3)

則H滿足ε-差分隱私.式(2)中,lapi(Δfε)(1≤i≤d)為相互獨立的拉普拉斯噪音變量，噪音量大小與Δf成正比、與ε成反比.因此，查詢f的全局敏感性越大，所需的噪音越多.

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

(4)

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

2.2 聯(lián)合樹

給定高維數(shù)據(jù)集D，且D具有d個屬性，即A={a1,a2,…,ad}，每個屬性的值域為Ωi(1≤i≤d).因此，整個值域的輸出域為Ω1×Ω2×…×Ωd.在實際應(yīng)用中，條件獨立性在高維屬性之間普遍存在，概率圖模型是探索這種關(guān)系的主要技術(shù)，因此，本文采用聯(lián)合樹發(fā)掘低維屬性構(gòu)成的團和分割頂點的邊緣分布，進而推理出來整體屬性的聯(lián)合分布.高維屬性A的聯(lián)合分布:

(5)

其中，Pr(A)表示屬性集合A的聯(lián)合分布概率;T表示聯(lián)合樹，Ci表示T中第i個團，Pr(Ci)表示團Ci的邊緣分布概率;Si j表示團Ci與團Cj之間的分割頂點，Pr(Si j)表示Si j的邊緣分布概率.

采用Markov網(wǎng)表示屬性對之間的關(guān)聯(lián)關(guān)系，對Markov網(wǎng)進行三角化操作后獲得團圖.基于團圖進行頂點消除來構(gòu)建聯(lián)合樹.例如設(shè)A={a1,a2,a3,a4,a5,a6}，結(jié)合A所對應(yīng)的Markov網(wǎng)G如圖1(a)所示，三角化操作結(jié)果如圖1(b)所示.依據(jù)屬性下標順序進行頂點消除，所得到的聯(lián)合樹如圖1(c)所示.由上述例子可以看出，結(jié)合聯(lián)合樹獲得團和分割頂點的邊緣分布之后，可以利用式(5)推理出整個高維屬性的聯(lián)合分布.

2.3 問題描述

給定具有高維屬性A的數(shù)據(jù)集D，結(jié)合屬性集合A構(gòu)建Markov網(wǎng)G.基于G構(gòu)建聯(lián)合樹T，結(jié)合T生成團和分割頂點的邊緣分布.基于式(5)生成屬性A的聯(lián)合分布Pr(A).為了使高維數(shù)據(jù)發(fā)布滿足差分隱私，聯(lián)合樹的構(gòu)建過程需要滿足差分隱私.即：Markov網(wǎng)G的構(gòu)建、團和分割頂點的邊緣分布生成過程均需要滿足差分隱私.因此，本文的問題是滿足差分隱私的情況下如何發(fā)布比較精確的高維數(shù)據(jù).

3 基于聯(lián)合樹的精確發(fā)布方法

本節(jié)主要介紹PrivHD算法的概述以及該算法的具體實現(xiàn)細節(jié)，其中包括滿足差分隱私的Markov網(wǎng)構(gòu)建方法、Markov網(wǎng)的三角化方法、聯(lián)合樹的生成方法、邊緣分布表的后置處理方法以及判斷PrivHD算法是否滿足ε-差分隱私.

3.1 PrivHD算法概述

PrivHD算法利用Markov網(wǎng)對高維數(shù)據(jù)進行降維，利用滿足差分隱私的聯(lián)合樹生成團和分割頂點的噪音邊緣分布，最后生成合成高維數(shù)據(jù)集進行發(fā)布，該算法的描述如算法1所示：

算法1. PrivHD算法.

輸入：高維數(shù)據(jù)集D、屬性A={a1,a2,…,ad}、隱私預(yù)算ε；

①ε=ε1+ε2；

②G←Build-Noisy-MN(D,A,ε1)；*生成噪音Markov網(wǎng)*

③T←Build-Noisy-JunctionTree(G,ε2)；

④Pr(·)←Build-Noisy-Marginals(T)；

給定一個具有高維屬性A的數(shù)據(jù)集D和相應(yīng)的參數(shù)，PrivHD算法首先利用Build-Noisy-MN方法生成滿足差分隱私的噪音Markov網(wǎng)(行②).然后，通過對噪音Markov網(wǎng)三角化操作、完全團圖構(gòu)建操作，以及利用最大生成樹方法生成聯(lián)合樹和團的邊緣分布(行③).結(jié)合聯(lián)合樹所產(chǎn)生的團和分割頂點，生成每個團和分割頂點的邊緣概率分布(行④).最后，通過對每個團的噪音邊緣分布進行連接，生成最終的合成高維數(shù)據(jù)集進行發(fā)布.

3.2 Build-Noisy-MN算法

結(jié)合屬性集合構(gòu)建Markov網(wǎng)G=(V,E)，頂點集合V代表屬性，邊集合E代表2個屬性之間的聯(lián)系.本文利用互信息度量2個屬性之間的關(guān)聯(lián)性.給定屬性ak，al，兩者之間的互信息為I(ak,al)：

(6)

其中，i∈dom(ak)，j∈dom(al)，dom(ak)，dom(al)分別表示屬性ak和al的取值范圍;Pr(ak=i,al=j)表示屬性的聯(lián)合分布,Pr(ak=i)，Pr(al=j)分別表示ak與al的邊緣分布.

由上述分析可知，G中2個屬性的互信息決定著兩者之間是否存在一條邊.然而，計算2個屬性之間的互信息是數(shù)據(jù)相關(guān)的，因此，需在滿足差分隱私的情況下獲得該信息.由于噪音機制的介入，首先需要計算出互信息的敏感度ΔI：

(7)

其中，n=|D|.

(8)

結(jié)合上述分析，Build-Noisy-MN的實現(xiàn)細節(jié)如算法2所示：

算法2. Build-Noisy-MN算法.

輸入：高維數(shù)據(jù)集D、屬性A={a1,a2,…,ad}、隱私預(yù)算ε1、過濾閾值θ；

輸出：生成滿足差分隱私的Markov網(wǎng)G.

①ε1=ε11+ε12；

②Eset←?；

③ 初始化G=(V,E),V={a1,a2,…,ad},E←?；

⑤ for each (ak,al) do

⑧Eset←Eset∪(ak,al)；

⑨ endif

⑩ endfor

在Build-Noisy-MN算法中，行⑤～⑩部分實現(xiàn)對原始候選空間的壓縮.獲得候選邊集合Eset后，利用指數(shù)機制挑選合適的邊添加到G中(行～)，進而形成滿足差分隱私的Markov網(wǎng)G.

定理2. Build-Noisy-MN算法滿足ε1-差分隱私.

證明. 給定2個近鄰D與D′，令lap為噪音變量.給定一個屬性對(ak,al)，在D與D′上所對應(yīng)的噪音互信息分別是：

根據(jù)上述推理過程可知不等式(9)與不等式(10)成立：

(9)

(10)

令M(Eset|D)表示在邊集合Eset中選擇邊操作.根據(jù)指數(shù)機制以及不等式(9)和不等式(10)可證明不等式成立：

(11)

根據(jù)不等式

可知，不等式(11)滿足條件：

(12)

證畢.

3.3 Build-Noisy-JunctionTree算法

基于Markov網(wǎng)G的聯(lián)合樹構(gòu)建通常包括G的三角化(如圖1(b)所示)、生成完全團圖、生成聯(lián)合樹3個過程.結(jié)合Build-Noisy-MN算法產(chǎn)生的Markov網(wǎng)G，三角化操作過程如算法3所示：

算法3.Triangulation-Partition算法.

輸入：Markov網(wǎng)G=(V,E)、頂點消除順序φ；

輸出：包含所有團的集合CL、三角化后Markov網(wǎng).

①G′←G，CL←?；

② for each nodeu∈φdo

③ if不存在邊(v1,v2)∈neibors(u) then

④ (v1,v2).mark=true；

⑤G′.E←G′.E∪(v1,v2)；

⑥ endif

⑦C←neibors(u)∪u；*根據(jù)頂點消除順序找團*

⑧CL←CL∪C；

⑨ endfor

⑩ returnG′，CL.

在Triangulation-Partition算法中，行②～⑨是根據(jù)頂點消除順序?qū)ふ宜袌F的過程.Markov網(wǎng)G=(V,E)中的團是一個頂點子集，其中每一對頂點之間均有一條邊相連，即一個團是G的一個完全子圖.例如給定φ={a1,a2,a3,a4,a5,a6}，按照所設(shè)定的頂點消除順序，所形成的如圖1(b)所示.所形成的團分別是C1={a1,a3,a5}，C2={a2,a5}，C3={a3,a4,a5}，C4={a4,a5,a6}.行③～⑥是對G三角化的過程.所謂三角化操作是對所有長度大于3的環(huán)引入弦的過程.例如，圖1(b)中虛線即為三角化后的弦.

根據(jù)所獲得的團構(gòu)建完全團圖CG=(CL,E)，其中CL表示所有團的集合，E表示團之間存在的邊.每一條邊(Ci,Cj)∈E，都有一個權(quán)重w(Ci,Cj)，并且w(Ci,Cj)=size(Ci∩Cj).即2個團的交集大小為邊的權(quán)重.例如根據(jù)Triangulation-Partition算法獲得CL={C1,C2,C3,C4}，相應(yīng)的權(quán)重分別為w(C1,C2)=1，w(C1,C3)=2，w(C1,C4)=1，w(C2,C3)=1，w(C2,C4)=1，w(C3,C4)=2，所產(chǎn)生的完全團圖如圖2(a)所示：

Fig. 2 Construction of junction tree on complete clique graph圖2 基于完全團圖的聯(lián)合樹構(gòu)建

結(jié)合上述生成的完全團圖CG構(gòu)建聯(lián)合樹.構(gòu)建聯(lián)合樹的性能瓶頸在于團的大小，而基于最小數(shù)量的團構(gòu)建聯(lián)合樹是個NP難問題.因此，本文基于CG設(shè)計一種類似于最大生成樹的貪心算法，具體細節(jié)如算法4所示：

算法4. Build-Noisy-JunctionTree算法.

輸入：完全團圖CG=(CL,E)、隱私預(yù)算ε2；

輸出：聯(lián)合樹T.

①T=(V,E)；

②T.V←?,T.E←?；

③visited(CG.E)=false；*CG的邊均未被訪問過*

④T.V←C,C∈CG.CL；*選擇最大的團*

⑤m←size(CG.CL)；*m為CG中團的個數(shù)*

⑥noisy-count(Tab(C)←count(Tab(C))+lap(mε2)*Tab(C)表示團C的邊緣分布表*

⑦ whileT.V≠CG.CLdo*構(gòu)建聯(lián)合樹*

⑧ for each (Ci,Cj)∈CG.Eandvisited(Ci,Cj)=false do

⑨ (Ck,Cl)←max(w(Ci,Cj))；*選擇權(quán)重最大的邊*

⑩ ifCk∈T.VandCl?T.Vthen

count(Tab(Cl))+lap(mε2)；

在Build-Noisy-JunctionTree算法中，首先選擇CG中規(guī)模最大的團開始聯(lián)合樹的構(gòu)建(行④).針對所挑選的團，構(gòu)建該團的邊緣分布表，利用拉普拉斯機制對該表添加噪音(行⑤～⑥).在行⑧～的for循環(huán)中，先選擇權(quán)重最大的邊，再判斷團Ck與Cl是否分別滿足條件.如果是，把團Cl添加聯(lián)合樹的頂點集合中，把邊(Ck,Cl)添加聯(lián)合樹的邊集合中.對于貪心搜索到的團Cl，利用拉普拉斯機制對其邊緣分布表添加噪音(行).例如CL={C1,C2,C3,C4}.選擇C3={a3,a4,a5}作為開始頂點，以最大生成樹方法貪心地生成聯(lián)合樹，如圖2(b)所示，使得最終的權(quán)重之和最大.

定理3. Build-Noisy-JunctionTree算法滿足ε2-差分隱私.

證明. 由Build-Noisy-JunctionTree算法可知，產(chǎn)生m個團之后，分別對這些團添加獨立的拉普拉斯噪音.在原始數(shù)據(jù)D中去掉或者添加1條記錄，最多影響m個團的計數(shù)，因此，為每個團添加噪音的大小為lap(mε2).根據(jù)定理1和差分隱私序列組合性質(zhì)可知，Build-Noisy-JunctionTree算法滿足ε2-差分隱私.

證畢.

由Build-Noisy-JunctionTree算法中的行⑥與行可知，最終形成的聯(lián)合分布精度如何，直接受到聯(lián)合樹T中團個數(shù)m的約束.如果采用噪音方差(2(Δfε2)2)度量每個團產(chǎn)生的誤差，則m個團產(chǎn)生的誤差總和:

(13)

其中，Ωj表示屬性aj的值域，|Ωj|表示該值域大小.

例如由圖2(b)可知CL={C1,C2,C3,C4}，即m=4.設(shè)置A中6個屬性的值域大小分別為{2,2,3,3,2,2}.根據(jù)式(13)可知Lerror(CL)=2304

由式(13)可知，每個團的邊緣分布表噪音誤差的高低直接與團的個數(shù)m相關(guān)，m越少最終的聯(lián)合分布越精確.Triangulation-Partition算法產(chǎn)生的團通常只包含3個屬性頂點，而仔細觀察可以發(fā)現(xiàn)，該算法的三角化操作并不充分，而三角化操作要求所有長度大于3的環(huán)均要引入弦.為此，本文設(shè)計一種Bigger-Clique算法來構(gòu)建更大的團圖，具體細節(jié)如算法5所示：

算法5. Bigger-Clique算法.

輸入：由Triangulation-Partition算法產(chǎn)生的G′=(V,E)；

輸出：包含所有團的集合CL.

①VS←?,UV←G′.V；*VS表示訪問過的頂點集合，UV表示未被訪問過的頂點集合*

②max_label=1；

③ 隨機選擇一個頂點u∈G′.V,labeled(u)=max_label；

④VS←VS∪u；

⑤UV←UV-u；

⑥ whileUV≠? do

⑦ for eachv∈G′.Vandv∈neibors(VS) do

⑧n_v←max_labeled_neibors(v)；

⑨labeled(n_v)←max_label+1；

⑩ endfor

例如在圖3(a)所示的Markov網(wǎng)中，為了充分三角化操作，頂點a6與頂點a3之間也引入了弦.依據(jù)頂點消除順序 ，獲得更大的團{a3,a4,a5,a6}.最終形成的團CL={C1={a1,a3,a5},C2={a2,a5},C3={a3,a4,a5,a6}}，此時m=3.根據(jù)式(13)可知Lerror(CL)=1296相比2304充分三角化操作能夠比較明顯地降低噪音誤差.然后利用Build-Noisy-JunctionTree算法獲得的聯(lián)合樹如圖3(b)所示.

Fig. 3 Construction of junction tree on bigger complete graph圖3 基于更大完全團圖的聯(lián)合樹構(gòu)建

3.4 Build-Noisy-Marginals算法

由Build-Noisy-JunctionTree算法行⑥與行可知，對每一個團的邊緣分布表均添加lap(mε2)，進而保證每個邊緣分布表滿足差分隱私.根據(jù)聯(lián)合樹的執(zhí)行相交性質(zhì)(如性質(zhì)1)可知，對于任意分割頂點Si j，則滿足Si j=Ci∩Cj.因此，對于聯(lián)合樹中的任意分割頂點，通過團邊緣分布表投影的方法可以獲得它們的噪音邊緣分布表.當獲得所有團和所有分割頂點的邊緣分布之后，利用式(5)可以計算出所有屬性的聯(lián)合分布Pr(A).

性質(zhì)1. 執(zhí)行相交性質(zhì).給定1棵聯(lián)合樹T以及T中任意頂點對Ci與Cj，如果有變量X滿足X∈Ci∩Cj，則X也在Ci與Cj之間唯一路徑的每個頂點中.那么T具有執(zhí)行相交性質(zhì).

例如在圖2(b)中獲得Tab(C2={a5,a2})和Tab(C3={a5,a4,a3})之后，通過投影可以獲得分割頂點{a5}的邊緣分布.假設(shè)a2,a3,a4,a5均為二進制屬性，相應(yīng)的噪音邊緣分布如圖4中(a)部分與圖4中(c)部分所示.由于分割頂點{a5}=C2∩C3，可以利用團C2或者團C3來獲得{a5}的邊緣分布.然而，通過圖4中(b)部分與圖4中(d)部分的噪音值ncnt可以發(fā)現(xiàn)，分割頂點{a5}在團C2與團C3中獲得的邊緣分布互相不一致.而互不一致性直接導致最終所有屬性的聯(lián)合分布不準確.為了處理這種不一致性，本文基于文獻[3,8,15]中的互一致性方法來后置處理團和分割頂點上的邊緣分布不一致性.

Fig. 4 Mutual consistency processing on clique and separator圖4 團與分割頂點的互一致性處理

設(shè)Tab(C1),Tab(C2),…,Tab(Ck)為團C1,C2…,Ck所對應(yīng)的噪音邊緣分布表.令I(lǐng)=C1∩C2∩…∩Ck.后置處理的目標是對于任意2個團Cx,Cy∈{C1,C2,…,Ck}，使得TabCx(i)=TabCy(i)成立，其中i是I值域中一個可能的取值.令ccntI(i)表示I經(jīng)過處理后的噪音計數(shù)(例如圖4(b)中ccnt的值).ccntI(i)表示形式為

(14)

其中，Ij表示Cl中除I之外的屬性，|Ωj|表示Ij的值域大小.

例如給定團C2={a2,a5}和團C3={a3,a4,a5}，以及二者的交集I={a5}，假設(shè)a2,a3,a4,a5均為二進制屬性.TabC2(i=0)=4，TabC2(i=1)=5(如圖4中(b)部分中的ncnt所示)，TabC3(i=0)=6，TabC3(i=1)=7(如圖4中(d)部分中的ncnt所示).利用式(14)可以計算出ccntI(i=0)=4.33，ccntI(i=1)=5.67(如圖4中(b)部分和圖4中(d)部分所示).

利用式(14)可以獲得I在C1,C2…,Ck中的一致性值.接下來是根據(jù)ccntI(i)來調(diào)整團C1,C2…,Ck中的ncnt值進行調(diào)整.令ccntCl(c|i)表示I取值為i時團Cl的后置處理值，具體表示形式為

(15)

例如給定團C2，C3，其邊緣分布表如圖4中(a)部分與圖4中(c)部分所示.由式(15)可知ccntC2(C1|i=0)=1.33，ccntC2(C2|i=0)=3.33，ccntC2(C1|i=1)=2.34，ccntC2(C2|i=1)=3.34，具體結(jié)果如圖4中(a)部分所示.同理可以對圖4中(c)部分中的ncnt值進行調(diào)整.

因此，根據(jù)式(14)和式(15)可以對團和分割頂點的邊緣分布表進行一系列后置處理.然而在調(diào)整過程中，后置處理后的值有可能發(fā)生沖突.例如，C1∩C3={a3,a5}，C3∩C4={a4,a5}.如果第1步先對團C1和C3進行一致性處理，則Tab(C1)和Tab(C3)在屬性{a4,a5}達成一致性.第2步對團C3和C4一致性處理，則Tab(C3)和Tab(C4)在屬性{a4,a5}達成一致性.然而，第2步的一致性處理可能導致第1步中計數(shù)的不一致性，其原因是C3和C4一致性處理改變了{a5}的分布.如果首先C1∩C3∩C4在{a5}上進行了互一致性處理，則第2步不會改變第1步中的一致性結(jié)果[2].

根據(jù)上述的例子可知，互一致性處理的先后順序至關(guān)重要.因此，本文結(jié)合分割頂點上存在的偏斜關(guān)系給出一個全序的拓撲序列，進而獲得互一致性處理的先后關(guān)系.令S={s1,s2,…,sk}為部分分割頂點的集合，根據(jù)S上的偏序關(guān)系S,?形成哈斯圖，然而結(jié)合哈斯圖進行拓撲排序.本文利用分割頂點之間的覆蓋關(guān)系表示?.對于任意2個分割頂點si與sj，若sj覆蓋si，則sisj∧?sl(sl∈S∧sislsj)成立.sj覆蓋si使得si與sj之間存在一條無向邊，且si在sj的下方.

例如根據(jù)圖2(b)所示，S={{a5},{a3,a5},{a4,a5}}，根據(jù)S,?所形成的哈斯圖如圖5所示：

Fig. 5 Construction of Hasse diagram圖5 哈斯圖構(gòu)建

3.5 Clique-Join算法

定理4. PrivHD算法滿足ε-差分隱私.

證明. 在PrivHD算法中，行②利用指數(shù)機制挑選屬性對來形成Markov網(wǎng)，定理3已證明該步驟滿足ε1-差分隱私.行③利用拉普拉斯機制為每個團的邊緣分布表添加噪音，根據(jù)定理1與定理4可知，行③滿足滿足ε2-差分隱私.根據(jù)定理6差分隱私的順序組合性質(zhì)可知，PrivHD滿足(ε1+ε2)-差分隱私.由于ε=ε1+ε2，則PrivHD算法滿足ε-差分隱私.

證畢.

4 實驗結(jié)果與分析

為了對PrivHD算法的可用性進行分析，本節(jié)將通過具體的實驗進行驗證與說明.實驗平臺是4核Intel i7-4790 CPU(4 GHz)，8 GB內(nèi)存，Windows 7操作系統(tǒng)，部分實驗在Intel E5-2600 CPU，32 GB內(nèi)存，Linux平臺上運行.所涉及代碼用R語言及Matlab實現(xiàn).實驗所采用的5個數(shù)據(jù)集BR2000，Adult，NLTCS，TPC-E，TIC均被廣泛使用于高維數(shù)據(jù)發(fā)布.其中BR2000來自于2000年巴西全國人口普查數(shù)據(jù)，該數(shù)據(jù)包含38 000條記錄；Adult源自于美國人口普查中心，包含45 222條個人信息；NLTCS源自于美國護理調(diào)查中心，記錄了21 574名殘疾人不同時間段的日?；顒?；TPC-E來自于TPC開發(fā)的在線事務(wù)處理程序，記錄了包含交易、交易類型、證券、證券狀態(tài)等信息的40 000條數(shù)據(jù)；TIC為Coil網(wǎng)站數(shù)據(jù)分析競賽所用數(shù)據(jù)集，記錄了某保險公司包括客戶購買產(chǎn)品信息以及客戶社交信息在內(nèi)的98 220條信息.數(shù)據(jù)集的具體細節(jié)如表1所示：

Table 1 Description of Five Datasets表1 5種數(shù)據(jù)集信息描述

結(jié)合上述5種數(shù)據(jù)集，分別用k-way查詢與SVM分類度量PrivHD，PrivBayes，JTree算法發(fā)布高維數(shù)據(jù)的準確性與可用性.k-way查詢k的取值為2，3，5，6，并使用平均方差(average variation)度量查詢結(jié)果的準確性；在合成數(shù)據(jù)集上構(gòu)建SVM分類模型并做出預(yù)測，使用誤分類率(misclassification rate)度量分類結(jié)果的準確性.隱私預(yù)算參數(shù)ε的取值為0.05,0.1，0.2，0.4，0.8，1.6.分配策略為ε1=0.1，ε2=ε-0.1，即隱私預(yù)算ε1=0.1用于構(gòu)建聯(lián)合樹，剩余的隱私預(yù)算用于產(chǎn)生噪音邊緣分布，當ε取值為0.05，0.1時，ε1=12ε，ε2=12ε.每個算法重復(fù)實驗50次，取度量指標的平均值作為實驗結(jié)果.

1) 基于參數(shù)ε和k-way查詢范圍的變化，對比PrivHD，PrivBayes，JTree算法的k-way查詢結(jié)果.

由圖6可發(fā)現(xiàn)，在大多數(shù)情況下，PrivHD優(yōu)于JTree和PrivBayes，在ε<0.2的情況下，PrivBayes的平均方差是PrivHD的2倍多.尤其是k=5或6的情況下，PrivHD明顯優(yōu)于JTree和PrivBayes，在維度比較大的TPC-E數(shù)據(jù)集上，JTree的平均方差是PrivHD的1倍多.在維度很大的TIC數(shù)據(jù)集上，由于PrivHD采用基于更大團的聯(lián)合樹構(gòu)建方法的緣故，其平均方差同樣小于JTree和PrivBayes，尤其是在k=5或k=6的情況下，PrivBayes的平均方差最壞情況下大概是PrivHD的1倍多.

Fig. 6 Result of k-way marginals on five datasets圖6 5種數(shù)據(jù)集下k-way查詢結(jié)果

k-way查詢的平均方差值越小表示發(fā)布高維數(shù)據(jù)的可用性越高，隨著k值的增大，3種算法的平均方差也越來越大，其原因是較大的k-way查詢會造成拉普拉斯噪音的累積，進而造成可用性降低.但是在較大的k-way查詢下，PrivHD的表現(xiàn)仍然好于JTree和PrivBayes，其原因是PrivHD采用了更優(yōu)的聯(lián)合樹構(gòu)建方法以及后置處理技術(shù)，進一步說明了PrivHD的高可用性.在數(shù)據(jù)集維度較低的NLTCS數(shù)據(jù)集上，PrivHD表現(xiàn)仍好于JTree，PrivBayes，而3種算法差別不大的原因是NLTCS數(shù)據(jù)集維度比較小，且為二進制數(shù)據(jù).

2) 基于參數(shù)ε的變化，對比PrivHD，PrivBayes，JTree，NoPrivacy算法的SVM分類結(jié)果.

本組實驗在Adult，NLTCS和TIC數(shù)據(jù)集上進行分析.首先分別根據(jù)PrivHD，PrivBayes，JTree算法產(chǎn)生合成數(shù)據(jù)集，然后在合成數(shù)據(jù)集上構(gòu)建SVM分類模型.對于Adult數(shù)據(jù)集，依據(jù)某個人:1)是否是男性(如圖7(b)中Y=gender);2)是否有大專學位;3)年薪是否大于5萬;4)是否已婚做出預(yù)測.對于NLTCS數(shù)據(jù)集，依據(jù)某個人:1)是否能夠外出;2)是否能夠管理資金;3)是否能夠游泳;4)是否能夠旅行做出預(yù)測.對于TIC數(shù)據(jù)集，依據(jù)某個人:1)是否擁有轎車;2)是否擁有房子;3)家庭平均年收入是否大于3萬;4)是否已婚做出預(yù)測.其中NoPrivacy算法是在原始數(shù)據(jù)集上構(gòu)建SVM分類模型并做出預(yù)測.本文將數(shù)據(jù)的20%作為測試集，將80%作為訓練集.

Fig. 7 Result of SVM classifiers on three datasets
圖7 3種數(shù)據(jù)集下SVM分類結(jié)果

由圖7可以發(fā)現(xiàn)，PrivHD算法的SVM分類結(jié)果優(yōu)于JTree和PrivBayes算法，在Adult數(shù)據(jù)集上，最壞情況下，PrivBayes的誤分類率是PrivHD的將近3倍，JTree的誤分類率也明顯高于PrivHD.在數(shù)據(jù)維度很高的TIC數(shù)據(jù)集上，PrivBayes和JTree的誤分類率同樣高于PrivHD.隨著參數(shù)ε從0.05變化到1.6，PrivHD，JTree，PrivBayes算法的誤分類率在相應(yīng)降低，其原因是小的ε值會引入更多的拉普拉斯噪音，進而增加拉普拉斯誤差.

5 結(jié)束語

針對差分隱私行下高維數(shù)據(jù)發(fā)布問題，本文首先對現(xiàn)有高維數(shù)據(jù)發(fā)布方法進行分析，并在此基礎(chǔ)上提出基于聯(lián)合樹的發(fā)布算法PrivHD，引入滿足差分隱私的高通濾波與后置機制.在過濾的基礎(chǔ)上提出了基于指數(shù)機制的Markov網(wǎng)構(gòu)建方法以及基于最大生成樹的聯(lián)合樹構(gòu)建方法.從理論角度進行對比分析的結(jié)果顯示，PrivHD優(yōu)于同類算法.最后，通過真實數(shù)據(jù)集的實驗結(jié)果表明PrivHD能夠在滿足差分隱私的同時輸出比較精確的k-way查詢與SVM分類結(jié)果.今后的工作需要考慮在數(shù)據(jù)流環(huán)境中發(fā)布高維數(shù)據(jù).