基于聯合樹的隱私高維數據發布方法

張嘯劍 陳 莉 金凱忠 孟小峰

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

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

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

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

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

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

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

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

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

1 相關工作

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

2 定義與問題

2.1 差分隱私

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

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

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

(1)

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

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

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

(2)

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

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

定理1[6]. 設f為某個查詢函數，且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]提出的指數機制主要處理抽樣算法的輸出為非數值型的結果.該機制的關鍵技術是如何設計打分函數u(ei).設H為指數機制下的某個隱私方法，則H在打分函數作用下的輸出結果為

(4)

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

2.2 聯合樹

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

(5)

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

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

2.3 問題描述

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

3 基于聯合樹的精確發布方法

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

3.1 PrivHD算法概述

PrivHD算法利用Markov網對高維數據進行降維，利用滿足差分隱私的聯合樹生成團和分割頂點的噪音邊緣分布，最后生成合成高維數據集進行發布，該算法的描述如算法1所示：

算法1. PrivHD算法.

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

①ε=ε1+ε2；

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

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

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

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

3.2 Build-Noisy-MN算法

結合屬性集合構建Markov網G=(V,E)，頂點集合V代表屬性，邊集合E代表2個屬性之間的聯系.本文利用互信息度量2個屬性之間的關聯性.給定屬性ak，al，兩者之間的互信息為I(ak,al)：

(6)

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

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

(7)

其中，n=|D|.

(8)

結合上述分析，Build-Noisy-MN的實現細節如算法2所示：

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

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

輸出：生成滿足差分隱私的Markov網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算法中，行⑤～⑩部分實現對原始候選空間的壓縮.獲得候選邊集合Eset后，利用指數機制挑選合適的邊添加到G中(行～)，進而形成滿足差分隱私的Markov網G.

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

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

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

(9)

(10)

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

(11)

根據不等式

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

(12)

證畢.

3.3 Build-Noisy-JunctionTree算法

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

算法3.Triangulation-Partition算法.

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

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

①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；*根據頂點消除順序找團*

⑧CL←CL∪C；

⑨ endfor

⑩ returnG′，CL.

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

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

Fig. 2 Construction of junction tree on complete clique graph圖2 基于完全團圖的聯合樹構建

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

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

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

輸出：聯合樹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中團的個數*

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

⑦ whileT.V≠CG.CLdo*構建聯合樹*

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

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

⑩ ifCk∈T.VandCl?T.Vthen

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

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

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

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

證畢.

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

(13)

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

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

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

算法5. Bigger-Clique算法.

輸入：由Triangulation-Partition算法產生的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網中，為了充分三角化操作，頂點a6與頂點a3之間也引入了弦.依據頂點消除順序 ，獲得更大的團{a3,a4,a5,a6}.最終形成的團CL={C1={a1,a3,a5},C2={a2,a5},C3={a3,a4,a5,a6}}，此時m=3.根據式(13)可知Lerror(CL)=1296相比2304充分三角化操作能夠比較明顯地降低噪音誤差.然后利用Build-Noisy-JunctionTree算法獲得的聯合樹如圖3(b)所示.

Fig. 3 Construction of junction tree on bigger complete graph圖3 基于更大完全團圖的聯合樹構建

3.4 Build-Noisy-Marginals算法

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

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

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

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

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

(14)

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

例如給定團C2={a2,a5}和團C3={a3,a4,a5}，以及二者的交集I={a5}，假設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中的一致性值.接下來是根據ccntI(i)來調整團C1,C2…,Ck中的ncnt值進行調整.令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，具體結果如圖4中(a)部分所示.同理可以對圖4中(c)部分中的ncnt值進行調整.

因此，根據式(14)和式(15)可以對團和分割頂點的邊緣分布表進行一系列后置處理.然而在調整過程中，后置處理后的值有可能發生沖突.例如，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步中計數的不一致性，其原因是C3和C4一致性處理改變了{a5}的分布.如果首先C1∩C3∩C4在{a5}上進行了互一致性處理，則第2步不會改變第1步中的一致性結果[2].

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

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

Fig. 5 Construction of Hasse diagram圖5 哈斯圖構建

3.5 Clique-Join算法

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

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

證畢.

4 實驗結果與分析

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

Table 1 Description of Five Datasets表1 5種數據集信息描述

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

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

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

Fig. 6 Result of k-way marginals on five datasets圖6 5種數據集下k-way查詢結果

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

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

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

Fig. 7 Result of SVM classifiers on three datasets
圖7 3種數據集下SVM分類結果

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

5 結束語

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