基于加權貝葉斯網絡的隱私數(shù)據(jù)發(fā)布方法

王 良 王偉平 孟 丹

1(中國科學院信息工程研究所 北京 100093)2(中國科學院大學 北京 100049) (wangliang@iie.ac.cn)

?

基于加權貝葉斯網絡的隱私數(shù)據(jù)發(fā)布方法

王 良1,2王偉平1孟 丹1

1(中國科學院信息工程研究所 北京 100093)2(中國科學院大學 北京 100049) (wangliang@iie.ac.cn)

數(shù)據(jù)發(fā)布中的隱私保護問題是目前信息安全領域的一個研究熱點.如何有效地防止敏感隱私信息泄露已成為信息安全領域的重要課題.差分隱私保護技術是最新發(fā)展起來的隱私保護技術，它的最大優(yōu)點是不對攻擊者的背景知識做任何特定假設，該技術不但能為隱私數(shù)據(jù)發(fā)布提供強有力的安全防護，而且在實踐中也得到了廣泛應用.現(xiàn)有的差分隱私保護技術并不能全面有效地處理高維隱私數(shù)據(jù)的發(fā)布問題，雖然基于貝葉斯網絡的隱私數(shù)據(jù)發(fā)布方法(PrivBayes)有效地處理了高維數(shù)據(jù)集轉化為低維數(shù)據(jù)集的發(fā)布問題，但這種方法也存在一定的缺陷和不足.基于對貝葉斯網絡的隱私數(shù)據(jù)發(fā)布方法的分析研究和改進優(yōu)化，建立了加權貝葉斯網絡隱私數(shù)據(jù)發(fā)布方法(加權PrivBayes)，通過理論分析和實驗評估，該方法不僅能保證原始隱私發(fā)布數(shù)據(jù)集的隱私安全性，同時又能大幅提升原始隱私發(fā)布數(shù)據(jù)集的數(shù)據(jù)精確性.

數(shù)據(jù)隱私；貝葉斯網絡；隱私保護；數(shù)據(jù)發(fā)布；差分隱私

當前，許多特定的數(shù)據(jù)組織機構需要將組織機構內的原始數(shù)據(jù)(例如醫(yī)院醫(yī)療數(shù)據(jù)、民意調查數(shù)據(jù)等)發(fā)布出去，以供其他組織科研機構進行研究分析或進行其他目的的應用.發(fā)布出去的原始數(shù)據(jù)集中可能包含著敏感的個人隱私信息(例如疾病、收入、存款等).數(shù)據(jù)組織機構需要將隱私數(shù)據(jù)經過特殊保護技術處理后發(fā)布出去.這些隱私保護處理技術大致分為3類：1)基于數(shù)據(jù)失真的發(fā)布技術.它能夠使隱私數(shù)據(jù)失真但又保持原有數(shù)據(jù)的某些特性，例如:隨機化操作、隨機擾動[1-3]、凝聚[4-5]、關聯(lián)規(guī)則挖掘[6]、向數(shù)據(jù)注入噪聲[7-8]、交換技術[9]等.2)基于數(shù)據(jù)加密的發(fā)布技術.數(shù)據(jù)加密技術已經有了成熟的發(fā)展，例如DES加密、RSA加密等.3)基于限制條件的發(fā)布技術.根據(jù)原始數(shù)據(jù)的特性，有選擇性地發(fā)布局部特性數(shù)據(jù)，例如:k-匿名隱私保護方法[10-13]、l-多樣性模型[14]、t-近似模型[15].

差分隱私保護技術是基于數(shù)據(jù)失真的發(fā)布技術，該數(shù)據(jù)發(fā)布技術已經得到了深入的研究和廣泛的發(fā)展，但這些技術并不能有效地處理高維數(shù)據(jù)集的發(fā)布，特別是當發(fā)布的數(shù)據(jù)集中包含大量的屬性字段時，已有的發(fā)布技術[16-21]需要向數(shù)據(jù)集中注入大量的噪聲信息，可能導致發(fā)布的數(shù)據(jù)集失去應用價值.Zhang等人[22]提出了PrivBayes數(shù)據(jù)發(fā)布方法，該方法基于貝葉斯網絡選取高維發(fā)布數(shù)據(jù)集的屬性字段，實現(xiàn)高維數(shù)據(jù)集向低維數(shù)據(jù)集的轉化，即降低原始發(fā)布數(shù)據(jù)集中屬性字段個數(shù)，以達到減小發(fā)布數(shù)據(jù)集體積的目的，同時在低維發(fā)布數(shù)據(jù)集中采用差分隱私保護處理技術，最終實現(xiàn)高維數(shù)據(jù)集的安全發(fā)布.雖然PrivBayes方法能夠保證高維數(shù)據(jù)集的安全發(fā)布，但也存在缺陷和不足，見2.1節(jié)所述，針對這些缺陷和不足，我們改進后提出了一種新的基于貝葉斯網絡的隱私數(shù)據(jù)發(fā)布方法，并命名為基于加權貝葉斯網絡的隱私數(shù)據(jù)發(fā)布方法，也稱為加權PrivBayes方法.加權PrivBayes方法繼承了PrivBayes方法的優(yōu)點，又彌補了其在選擇隱私發(fā)布數(shù)據(jù)集屬性字段方面的缺陷和不足，通過實驗結果證明，加權PrivBayes方法既顯著提升了隱私數(shù)據(jù)集發(fā)布的數(shù)據(jù)精確性又有效提高了隱私數(shù)據(jù)集發(fā)布的安全性，該方法也很好地兼顧了隱私數(shù)據(jù)泄露的安全防護和發(fā)布數(shù)據(jù)應用的價值這2個方面的問題.

本文主要探討加權PrivBayes方法是如何提高高維數(shù)據(jù)集的發(fā)布數(shù)據(jù)的精確性和保障隱私數(shù)據(jù)的安全性，同時給出了具體的改進算法和實驗證明.

1 相關工作

隨著數(shù)據(jù)發(fā)布領域中對個人隱私信息安全防護級別要求的不斷提升，差分隱私保護方法自從創(chuàng)立后，便得到了廣泛的應用和快速的發(fā)展.差分隱私保護方法業(yè)已成為數(shù)據(jù)發(fā)布領域中最重要的隱私保護方法之一.

1.1 差分隱私保護方法

為了防范統(tǒng)計數(shù)據(jù)庫中個人隱私信息泄露的安全風險，Dwork等人[23-25]提出了一種新的隱私保護方法，并命名為差分隱私保護方法，該方法能為發(fā)布數(shù)據(jù)集中的個人隱私信息提供強有力的安全保護.

定義1. 差分隱私(differential privacy)[23].對于任意2個鄰近的數(shù)據(jù)集D1和D2，二者僅相差一個數(shù)據(jù)元組，Range(G)表示一個隨機函數(shù)G的取值范圍，Pr[Es]表示事件Es的信息安全披露風險，若隨機函數(shù)G滿足：

Pr[G[D1]∈S]≤eε×Pr[G[D2]∈S]，

(1)

并且S?Range(G)，那么隨機函數(shù)G提供ε-差分隱私保護，其中參數(shù)ε為隱私保護預算.

差分隱私保護方法通過向發(fā)布數(shù)據(jù)集中注入適量的干擾噪聲來實現(xiàn)發(fā)布數(shù)據(jù)集中數(shù)據(jù)元組隱私信息的安全防護，其統(tǒng)計學模型如圖1所示:

Fig. 1 The statistical model of differential privacy.圖1 差分隱私的統(tǒng)計學模型

差分隱私保護方法的主要優(yōu)點是：1)不對攻擊者的能力(數(shù)據(jù)分析、推理、背景知識等)做任何特定假設；2)具有嚴謹?shù)慕y(tǒng)計學模型.缺點是：1)差分隱私只考慮了在個體元組中加入適量的干擾噪聲；2)參數(shù)ε沒有恒定的度量標準.

差分隱私保護方法[16,26-27]的實現(xiàn)方法有很多種，其中最著名的且被廣泛使用的2種方法是：1)拉普拉斯機制(Laplace mechanism)[24]，只適用于操作發(fā)布數(shù)據(jù)集中屬性值為數(shù)字類型的元組；2)指數(shù)機制(exponential mechanism)[28]，僅適用于數(shù)據(jù)查詢的返回值為實數(shù)值的場合.

定義2. 敏感度(sensitivity)[23].給定F是將一個數(shù)據(jù)集映射到一個固定大小實數(shù)向量的函數(shù)，那么函數(shù)F的敏感度定義為

(2)

其中,D1和D2為任意2個鄰近數(shù)據(jù)集，二者僅相差一個數(shù)據(jù)元組.

函數(shù)的敏感度是由函數(shù)本身決定的，不同的函數(shù)有不同的敏感度.敏感度過低會使發(fā)布數(shù)據(jù)集安全性得不到保障，敏感度過高會使發(fā)布數(shù)據(jù)集的發(fā)布結果實用性降低.參數(shù)ε的確定標準仍然是一個未決的問題[24]，在實際應用中，參數(shù)ε的取值一直缺乏一個廣泛認可的標準.

1.2 貝葉斯網絡

設A是原始數(shù)據(jù)集D的屬性字段集合.

定義3. 貝葉斯網絡N是一個有向無環(huán)圖.貝葉斯網絡N中的每一個結點都代表著原始數(shù)據(jù)集D中的某一個屬性字段，即屬性字段集合A中的某一個元素.如果N中某2個屬性字段結點之間存在著直接依賴關系，則2個屬性字段結點之間用一條弧(或有向邊)進行直接連接.例如圖2是一個具有5個屬性字段結點的貝葉斯網絡.

Fig. 2 A Bayesian network N over five attributes.圖2 5個屬性字段結點的貝葉斯網絡N

定義4. 結點的入度.在貝葉斯網絡N中，以某一個結點為弧頭，終止于該結點弧的數(shù)目稱為該結點的入度.

定義5. 結點的出度.在貝葉斯網絡N中，以某一個結點為弧尾，起始于該結點弧的數(shù)目稱為該結點的出度.

在貝葉斯網絡N中，若存在一條從x屬性字段結點到y(tǒng)屬性字段結點的有向邊，x屬性字段結點為弧尾，y屬性字段結點為弧頭，我們稱x屬性字段結點為y屬性字段結點的父結點.

在圖2的貝葉斯網絡N中，5個屬性字段結點分別是Age,Workclass,Education,Occupation,Income.對于圖2中任意2個屬性字段結點x,y∈A，x與y之間的關系存在3種可能性：

1) 直接依賴關系.即x屬性字段結點與y屬性字段結點之間存在一條有向邊.例如從Age屬性字段結點到Workclass屬性字段結點之間有一條有向邊，Age屬性字段結點稱為弧尾，Workclass屬性字段結點稱為弧頭，也就是說Workclass屬性字段的屬性值直接依賴于Age屬性字段的屬性值.

2) 間接依賴關系.即x屬性字段結點與y屬性字段結點之間不存在一條有向邊，但x屬性字段結點與y屬性字段結點可以通過其他結點，用一條有向邊路徑連接起來.例如從Education屬性字段結點到Income屬性字段結點之間不存在一條直接有向邊，但是Education屬性字段結點與Income屬性字段結點，可以通過Workclass屬性字段結點或Occupation屬性字段結點用一條有向邊路徑連接起來，即Education屬性字段結點與Income屬性字段結點之間存在2條有向邊路徑.換句話說，Income屬性字段的屬性值間接依賴于Education屬性字段的屬性值.Income屬性字段結點的父結點集合為{Workclass,Occupation}.

3) 無依賴關系.即x屬性字段結點與y屬性字段結點之間不存在一條有向邊或有向邊路徑.例如Workclass屬性字段結點與Occupation屬性字段結點之間就不存在任何依賴關系.

定義6. 一個具有d個屬性字段結點的貝葉斯網絡N可以用一個(屬性字段結點，父結點集合)對集合來表示，即{(A1,Π1),(A2,Π2),…,(Ad,Πd)}.

從該定義中，我們可以得到：

1)Ai(i∈d)為屬性字段集合A中的某一個元素，即某一個屬性字段.

2)Πi(i∈d)為屬性字段Ai父結點的集合.

3) 貝葉斯網絡N中任意2個結點Ai,Aj(1≤i≤j≤d)，如果Aj?Πi，那么從Aj結點到Ai結點不存在一條有向邊或有向邊路徑.

我們將數(shù)據(jù)集D中的元組分布記作Dt[A]，我們定義一種方法利用貝葉斯網絡N中d個屬性字段的Dt(A1,Π1),Dt(A2,Π2),…,Dt(Ad,Πd)無限接近Dt[A].尤其是在假設條件下，對于任意Ai,Aj且Aj?Πi無依賴關系，則可以得到：

Dt[A]=Dt[A1,A2,…,Ad-1,Ad]=Dt[A1]×

Dt[A2|A1]×…×Dt[Ad|A1,A2,…,Ad-1]=

算法1. GreedyBayes.

輸入：數(shù)據(jù)集D、參數(shù)k；

輸出：貝葉斯網絡N.

步驟1. 初始化N=?，V=?；

步驟2. 從屬性字段集合A中隨機選取一個屬性字段X1，加(X1，?)入N，加X1入V.

步驟3. ① fori=2 toddo

② 初始化Ω=?;

④ 加(X,Π)入集合Ω;

⑤ end for

⑥ 從集合Ω中選擇最大交互信息對(Xi,Πi)；

⑦ 將(Xi,Πi)加入貝葉斯網絡N，將屬性字段結點Xi加入V；

⑧ end for

步驟4. 返回貝葉斯網絡N.

2 貝葉斯網絡算法的局限性

2.1 貝葉斯網絡算法描述

Zhang等人[22]在PrivBayes模型中利用算法1來構建貝葉斯網絡.算法1描述了如何將高維數(shù)據(jù)集D中的屬性字段集合構建成為一個貝葉斯網絡.

在算法1中，步驟2隨機選擇一個屬性字段加入貝葉斯網絡N，步驟3利用貪婪算法從屬性字段集合中選擇d-1個屬性字段結點(該屬性字段結點具有最大交互信息，即入度最大的結點)加入貝葉斯網絡N，步驟4輸出貝葉斯網絡N.

通過對算法1的分析研究，我們得出貝葉斯網絡算法在對高維數(shù)據(jù)集進行發(fā)布時，存在4個缺陷和不足：

1) PrivBayes模型只考慮了屬性字段之間的關系

PrivBayes模型在選取屬性字段時只考慮數(shù)據(jù)集D中屬性字段之間的關系，并沒有考慮屬性字段值的屬性，這種忽略了屬性字段值的設計方案，嚴重影響發(fā)布數(shù)據(jù)集的質量和安全.如果某-個屬性字段的屬性值多樣性稀少，即屬性值存在大量重復值的情況，發(fā)布出去的數(shù)據(jù)集將存在隱私數(shù)據(jù)泄露的安全隱患，嚴重威脅到發(fā)布信息的安全，或者發(fā)布出去的數(shù)據(jù)集的數(shù)據(jù)信息重復單一，失去實際應用價值.

2) PrivBayes模型選取首個屬性字段的方法隨機

發(fā)布的貝葉斯網絡N中，屬性字段的結點是有限的，這就要求N中的任何一個結點都能夠真實、全面、盡可能地反映原始數(shù)據(jù)集.因此第1個屬性字段不能隨機選擇，如果這樣操作，將嚴重影響到發(fā)布數(shù)據(jù)集的數(shù)據(jù)質量.

3) PrivBayes模型缺乏敏感屬性字段的首選機制

如果原始數(shù)據(jù)集D中存在敏感屬性，那么敏感屬性字段一定要出現(xiàn)在發(fā)布數(shù)據(jù)集中.在大多數(shù)情況下，缺少敏感屬性字段的發(fā)布數(shù)據(jù)集是無任何應用價值.

4) PrivBayes模型不能解決屬性字段結點在入度相同的條件下，如何選擇出最優(yōu)的屬性字段結點的問題.

在算法1中，k值是被PrivBayes模型自動生成并且是一個非常小的值.在多個屬性字段結點的入度q(1≤q≤k)值相同時，PrivBayes模型不能選擇出最優(yōu)的屬性字段結點.

例1. 在圖2的貝葉斯網絡N中，一共有5個屬性字段結點，它的(屬性字段結點，父結點集合)對如表1所示.如果使用算法1的貪婪算法在表1中發(fā)布3個屬性字段的結點時，算法1會自動生成{Income,Workclass,Education}或{Income,Workclass,Occupation}三個屬性字段結點的貝葉斯網絡進行數(shù)據(jù)發(fā)布，我們經過分析發(fā)現(xiàn)，這種選擇算法僅側重考慮了屬性字段結點間交互信息的最大化，并沒有充分考慮到發(fā)布數(shù)據(jù)集中數(shù)據(jù)的多樣性和實際應用意義.本實例中，Age屬性字段在現(xiàn)實生活中具有重要的實際應用價值，它能夠真實反應出Income屬性字段屬性值分布的情況和數(shù)據(jù)的實際應用價值，因此Age屬性字段結點在發(fā)布數(shù)據(jù)時是必須要進行選擇的.我們依據(jù)圖2中的貝葉斯網絡N，人工進行選擇屬性字段結點發(fā)布時，會選擇生成含有{Income,Occupation,Age}三個屬性字段結點的貝葉斯網絡進行數(shù)據(jù)發(fā)布，因為這樣選擇，既能增加發(fā)布數(shù)據(jù)集的數(shù)據(jù)多樣性，同時還能增加發(fā)布數(shù)據(jù)集的實際應用價值.人工生成時，為什么沒有選擇Workclass屬性字段，而選擇Occupation屬性字段呢？是因為Occupation屬性字段值更能體現(xiàn)Income屬性字段的屬性值.另外，Age屬性字段也能對Education,Occupation屬性字段進行替換，也就是說Age屬性字段值也能從側面反映出這個個體的Education,Occupation情況.這種人工選擇方案明顯優(yōu)于貪婪算法的選擇方案.我們通過為貝葉斯網絡N中的屬性字段結點增加權重值的方法能夠模擬人工選擇方案，得到人工選擇的結果，從而彌補算法1中選擇屬性字段結點方法的缺陷和不足.

Table1 The Attribute-Parent Pairs from N

5) PrivBayes模型沒有考慮貝葉斯網絡N中存在多個連通分量的情況.

在算法1中，如果屬性字段結點的關系是緊密的，并且存在唯一的連通分量，那么輸出的貝葉斯網絡N會滿足完整性約束條件.但是當存在多個連通分量時，輸出的貝葉斯網絡N應用價值會存在降低的情況.

例2. 圖3是一個具有9個屬性字段結點的貝葉斯網絡，它的(屬性字段結點，父結點集合)對如表2所示.如果使用算法1從表2中生成5個屬性字段結點的貝葉斯網絡時，算法1會自動選擇{B,E,F,H,I}這5個屬性字段結點，我們經過分析研究后發(fā)現(xiàn)，圖3中包含著2個連通分量，自動選擇{B,E,F,H,I}五個屬性字段結點，全部來自第1個連通分量，而第2連通分量{C,D}中沒有一個屬性字段結點被選擇出來.從發(fā)布數(shù)據(jù)集數(shù)據(jù)的整體性、全面性和代表性方面考慮，第2連通分量{C,D}中，至少應該有一個屬性字段結點被選擇發(fā)布出去.在實際的隱私數(shù)據(jù)發(fā)布處理過程中，構建的貝葉斯網絡可能包含著多個連通分量，當其中某一個連通分量中各屬性字段結點關系緊密時，可能會造成發(fā)布的數(shù)據(jù)集中屬性字段結點相對集中.我們通過優(yōu)化，計算貝葉斯網絡中每個連通分量中元素的個數(shù)與所有連通分量中元素的個數(shù)總數(shù)占比來確定此連通分量中應被選擇元素的個數(shù)，以達到數(shù)據(jù)均衡發(fā)布的目的.

Fig. 3 A Bayesian network M over nine attributes.圖3 9個屬性結點的貝葉斯網絡M

iAiΠi1A?2B{A,H}3C?4D{C}5E{B,F}6F{A,I}7G{A}8H{G,I}9I{A,G}

算法2. NoisyConditionals.

輸入：數(shù)據(jù)集D、貝葉斯網絡N、參數(shù)k；

輸出：低維數(shù)據(jù)集P*.

步驟1. 初始化P*=?.

步驟2. ① fori=k+1 toddo

② 構建屬性結點Xi的聯(lián)合分布

Dt[Xi,Πi];

④ 設Dt*[Xi,Πi]中的負值歸0并正常化;

⑤ 從Dt*[Xi,Πi]提取Dt*[Xi|Πi]并加入P*;

⑥ end for

步驟3. ① fori=1 tokdo

② 從Dt*[Xk+1,Πk+1]中提取Dt*[Xi|Πi]并加入P*;

③ end for

步驟4. 返回k度的低維數(shù)據(jù)集P*.

2.2 貝葉斯網絡加入噪聲處理的算法

算法2展現(xiàn)了PrivBayes模型加入噪聲的邏輯處理框架，它通過構建d-k個噪聲條件分布Dt*[Xi|Πi],i∈[k+1,d]并且滿足(ε2)-差分隱私，實現(xiàn)高維數(shù)據(jù)集的隱私安全發(fā)布.

算法2也存在缺陷和不足:

1) PrivBayes模型并沒有考慮加入噪聲處理時，屬性字段結點的加入順序.

2) 當PrivBayes模型在低維數(shù)據(jù)集中加入噪聲時，并沒有考慮屬性字段屬性值的多樣性.如果某一個屬性字段屬性值過于單一，加入過多的噪聲并不能提高該屬性字段的安全性.相反，如果某一個屬性字段的屬性值過于豐富，加入過少的噪聲并不能提高該屬性字段的安全性.這類操作會影響到發(fā)布數(shù)據(jù)集的整體安全性.

總之，PrivBayes模型在原始數(shù)據(jù)集D中根據(jù)最大交互信息選擇d個屬性字段，并不能最大化相似(或接近)原始數(shù)據(jù)集，因為屬性字段的屬性值多樣性也影響著發(fā)布數(shù)據(jù)集的數(shù)據(jù)精確性.

3 加權貝葉斯網絡算法

在貝葉斯網絡N中，如何在屬性字段結點交互信息相同的情況下選擇一個最優(yōu)的屬性字段結點，可以通過為屬性字段結點加入權重值的方法進行解決.在理想的情況下，原始數(shù)據(jù)的所有者能夠正常區(qū)分每一個屬性字段的重要性，并分析所有數(shù)據(jù)元組給每一個屬性字段加入一個權重值進行區(qū)分.但是，在現(xiàn)實情況下，我們所面對的是海量數(shù)據(jù)，要分析所有元組數(shù)據(jù)是一個不可能的任務.屬性字段屬性值的多樣性，即屬性字段屬性值的不同有效值是可以通過分析有限的元組數(shù)據(jù)來獲得一個非常接近最終結果值的近似值.用這種方法替代屬性字段的重要程度是一個不錯的選擇，在實踐中也是可行的.

3.1 權重值

定義7. 權重值.在一個具有d個屬性字段結點的貝葉斯網絡N中，為了表示每一個屬性字段結點在發(fā)布數(shù)據(jù)集中的重要程度，為每一個屬性字段結點增加一個數(shù)值，稱為該屬性字段結點的權重值或靜態(tài)權重值.

圖4是圖2中屬性字段結點加入權重值的貝葉斯網絡N.

Fig. 4 A Bayesian network N over five weighted attributes.圖4 5個加權屬性字段結點的貝葉斯網絡N

定義8. 權重值計算方法.在一個具有n個屬性字段的數(shù)據(jù)集D中，由其構建的d個屬性字段的貝葉斯網絡N中，屬性字段Ai的權重值=屬性字段Ai屬性值的多樣性÷(屬性字段A1的屬性值的多樣性+…+屬性字段An屬性值的多樣性,1≤i≤d.

當原始數(shù)據(jù)集D中的元組較少時，貝葉斯網絡N中的權重值可以通過定義8計算得出.如果原始數(shù)據(jù)D的元組不可計數(shù)時，屬性字段屬性值的多樣性可以通過計算有限的元組獲得接近的近似值.

例3. 在圖4的貝葉斯網絡N中，Age屬性字段結點的權重值計算方法是：Age屬性字段結點的權重值=Age屬性字段屬性值的多樣性÷(屬性字段A1屬性值多樣性+…+屬性字段An屬性值多樣性)=73÷(73+8+16 +7+14+6+5+2+41+2)≈0.4195.其中，A1,A2,…,An為Adult數(shù)據(jù)集中所有屬性字段.其他屬性字段結點的權重值計算方法相同，Adult數(shù)據(jù)集中所有屬性字段的權重值如表3所示.在表3中，列1為序號字段，列2為屬性字段，列3為該屬性字段屬性值多樣性的總數(shù)，列4為計算后的屬性字段結點權重值.

Table 3 The Weights Table of Adult Data Set

定義9. 結點的動態(tài)權重值.在貝葉斯網絡N中，某一個屬性字段結點的權重值與該屬性字段結點所有入度結點權重值平均值之差，與該屬性字段結點所有出度結點權重值平均值之和，稱為該屬性字段結點的動態(tài)權重值.

動態(tài)權重值是我們評估貝葉斯網絡N中屬性字段結點的重要性的一個工具.當前屬性結點的所有入度之和代表當前屬性字段結點對其他結點的依賴性，該屬性字段結點的出度之和代表這個屬性字段結點對其他結點的貢獻.

例4. 在圖4的貝葉斯網絡N中，屬性字段結點Age的入度為0，出度為2，Age屬性字段結點的動態(tài)權重值=0.4195-0+(0.0460+0.0920)2=0.4885,Workclass屬性字段結點的動態(tài)權重值=0.0460-(0.4195+ 0.0920)2+0.0115=-0.19825,其他屬性字段結點的動態(tài)權重值如表4所示:

Table 4 The Dynamic Weights Table of N

在進行隱私數(shù)據(jù)集發(fā)布時，我們要盡可能地增加發(fā)布數(shù)據(jù)數(shù)值的多樣性，增強發(fā)布數(shù)據(jù)的實際應用性，也就是說我們發(fā)布的低維數(shù)據(jù)集不僅要盡可能地接近原始高維數(shù)據(jù)集，而且要具有更大的應用價值.因此，我們在發(fā)布數(shù)據(jù)集時，盡可能選擇具有實際代表性的數(shù)據(jù)屬性字段，盡可能選擇屬性值豐富的屬性字段，即動態(tài)權重值更大的屬性字段，確保發(fā)布后的數(shù)據(jù)集無限接近原始數(shù)據(jù)集.

算法3. IAGreedyBayes.

輸入：數(shù)據(jù)集D、參數(shù)k；

輸出：貝葉斯網絡N.

步驟1. 初始化N=?，Z=?；

步驟2. 計算原始數(shù)據(jù)集D中所有屬性字段A1,A2,…,An的動態(tài)權重值，并標記敏感屬性字段；

步驟3.m←計算屬性字段集合中所有的連通分量；

步驟4. ① fori=1 tomdo

②Ci,Vi←根據(jù)d值確定每個連通分量中應該選擇的屬性字段結點總數(shù)，每個連通分量中屬性字段結點的集合;

③ end for

步驟5. ① fori=1 tomdo

②U=?;

③ forj=1 toCido

⑤ 將(Xi,Πi)加入N，Xi加入Z;

⑥ end for

⑦ end for

步驟6. 返回貝葉斯網絡N.

3.2 加權貝葉斯網絡算法描述

由于貝葉斯網絡算法存在2.1節(jié)中所描述的缺陷和不足，我們基于貝葉斯網絡算法提出了一個新的算法，并命名為加權貝葉斯網絡算法，它不僅同時考慮了屬性字段結點之間的交互信息也兼顧了屬性字段屬性值的多樣性，并在貝葉斯網絡結點中加入權重值,該算法的詳細描述如算法3所示.

步驟2通過屬性字段結點的權重值計算動態(tài)權重值并標記所有敏感屬性;步驟3計算屬性字段集合中所有的連通分量;步驟4根據(jù)輸出貝葉斯網絡網絡中屬性字段結點數(shù)d值，計算每個連通分量中應該輸出的屬性字段結點數(shù)目，并記錄每個連通分量中的屬性字段結點集合;步驟5從每個連通分量中選擇出最優(yōu)的屬性字段結點.最后，輸出貝葉斯網絡.

使用算法3，對圖4中的貝葉斯網絡N發(fā)布3個屬性字段結點時，貝葉斯網絡N中所有結點的動態(tài)權重值如表4所示.貝葉斯網絡N中只有一個連通分量，首先選擇權重值最大的屬性字段結點Age，發(fā)布{Age}；其次選擇動態(tài)權重值最大的屬性字段結點，由于N中有敏感屬性字段結點Income,因此要優(yōu)先選擇發(fā)布{Income},然后發(fā)布{Age,Income}；再選擇動態(tài)權重值最大的屬性字段結點Occupation,發(fā)布{Age,Income,Occupation},所以最終發(fā)布的貝葉斯網絡屬性字段結點集合為{Age,Income,Occupation},與我們人工選擇方案相一致，是一種最優(yōu)的選擇發(fā)布方案.

改進后的算法3，將原始高維數(shù)據(jù)集D轉化為低維數(shù)據(jù)集D′，低維數(shù)據(jù)集D′能夠最大化地貼近原始高維數(shù)據(jù)集D，使發(fā)布數(shù)據(jù)集D′的數(shù)據(jù)更具多樣性，更能保留原始數(shù)據(jù)集的實際應用價值.

算法4. IANoisyConditionals.

輸入：數(shù)據(jù)集D、貝葉斯網絡N、參數(shù)k;

輸出：低維數(shù)據(jù)集P*.

步驟1. 初始化P*=?；

步驟2. ① fori=k+1 toddo

② 構建屬性結點Xi的聯(lián)合分布Pr[Xi,Πi]；

④ 設Pr*[Xi,Πi]中的負值歸0并正常化；

⑤ 從Pr*[Xi,Πi]提取Pr*[Xi|Πi]并加入P*；

⑥ end for

步驟3. ① fori=1 tokdo

② 從Pr*[Xk+1,Πk+1]中提取Pr*[Xi|Πi]并加入P*；

③ end for

步驟4. 返回k度的低維數(shù)據(jù)集P*.

3.3 差分隱私處理過程優(yōu)化

原始高維數(shù)據(jù)集D通過構建的貝葉斯網絡轉化成低維數(shù)據(jù)集D′，低維數(shù)據(jù)集D′加入差分隱私算法處理后，生成最終的發(fā)布數(shù)據(jù)集.新的發(fā)布數(shù)據(jù)集與原始數(shù)據(jù)集無限接近，并且經過差分隱私保護技術處理后增強了發(fā)布數(shù)據(jù)集的安全性.Zhang等人[22]提出的算法2通過加入噪聲來保障低維發(fā)布數(shù)據(jù)集的安全性.雖然此種方法能夠保證發(fā)布數(shù)據(jù)集的安全性，但也存在缺陷和不足，例如在性別的屬性字段中加入過量的噪聲，對原有性別屬性字段屬性值的影響不大，可以忽略不計，在實際應用過程起到的安全防護作用并不明顯，不會影響攻擊者對該屬性字段值的推測.如果在年齡的屬性字段中加過少的噪聲，會顯著地影響年齡屬性字段屬性值的安全性，容易使攻擊者在更大概率地推測出年齡屬性字段屬性值，在實際應用過程中造成該屬性字段屬性值信息泄露的安全風險.因此，需要對這個處理過程進行優(yōu)化，在我們的具體實驗中，對原算法2中的步驟2中第②步進行了優(yōu)化處理，其他實現(xiàn)步驟與原算法保持一致.實驗中我們使用了拉普拉斯算法，將貝葉斯網絡中所有屬性字段結點按動態(tài)權重值服從拉普拉斯分布進行重新序列排列，并依次加入噪聲.通過這種改進，明顯改善了發(fā)布數(shù)據(jù)集的安全性.

算法4使用了一個k度的貝葉斯網絡N，將原始高維數(shù)據(jù)集D利用(ε2)-差分隱私保護方法，生成了低維發(fā)布數(shù)據(jù)集D′，低維發(fā)布數(shù)據(jù)集D′的安全性有充分保障.

4 實 驗

我們根據(jù)實驗測試結果，評估了加權貝葉斯網絡隱私保護方法(加權PrivBayes)的算法運行時間；分析了經該算法處理后的發(fā)布數(shù)據(jù)集隱私信息泄露的可能性；并對該算法發(fā)布數(shù)據(jù)集的精確性進行了深入分析.同時我們也將該模型與貝葉斯網絡隱私保護方法(PrivBayes)在算法運行時間、敏感隱私信息泄露的可能性、發(fā)布數(shù)據(jù)集的精確性3方面進行了對比分析.

本實驗中，我們采用美國UCI(University of California，Irvine)所提供的機器學習庫中的成人數(shù)據(jù)集，該數(shù)據(jù)集由美國人口普查數(shù)據(jù)組成，共計32 561個元組.在該數(shù)據(jù)集中一共選取了10個屬性字段:Age，Workclass，Education，Marital-status，Race，Occupation，Relationship，Sex，Native-Country，Income.實驗中所使用的軟硬件參數(shù)如下: 1)操作系統(tǒng):Windows7 x64 Professional Edition; 2)硬件參數(shù):Intel CoreTMi3-370M 2.4 GHz CPU，6 GB DDR內存; 3)編譯環(huán)境:Microsoft Visual Studio 2012 C++.此外，Laplace實現(xiàn)代碼參考了Zhang等人[22]通過構建貝葉斯網絡實現(xiàn)發(fā)布高維數(shù)據(jù)集論文實驗相關代碼.

4.1 安全性分析

在實驗中，我們采用了差別度量方法，將加權PrivBayes隱私保護方法與PrivBayes隱私保護方法進行了數(shù)據(jù)泄露可能性對比分析，其中d=6,ε=(0.05, 0.2).d取固定值6是因為在實驗中所使用的成人數(shù)據(jù)集中一共有15個屬性字段，去掉5個無發(fā)布意義(多個屬性字段含義相同而表示方法不同)的屬性字段，剩余10個屬性字段，我們認為取大于屬性字段總數(shù)一半的最小值進行對比分析比較合理.原始數(shù)據(jù)集元組大小為1×105，按元組增量每104為一個度量點進行敏感屬性信息泄露可能性比較，對比分析結果如圖5所示.根據(jù)實驗測試的數(shù)據(jù)結果，我們對比分析了這2種模型方法在數(shù)據(jù)泄露可能性方面的差異，可以得出加權PrivBayes隱私保護方法，在ε預算開銷恒定的情況下，其數(shù)據(jù)泄露的可能性明顯低于PrivBayes隱私保護方法，其中差分隱私保護方法(Laplace)向發(fā)布數(shù)據(jù)集注入噪聲的優(yōu)化和貝葉斯網絡中屬性結點的權重值計算選擇起到了決定性的作用.從實驗結果我們可以分析得出，加權PrivBayes隱私保護方法能夠對高維數(shù)據(jù)集的發(fā)布提供更安全的防護.

Fig. 5 The possibility of data leakage.圖5 數(shù)據(jù)泄露可能性分析

4.2 時間性能分析

在實驗中，我們將加權PrivBayes隱私保護方法(ε=0.05)與PrivBayes隱私保護方法(ε=0.05)按發(fā)布數(shù)據(jù)集屬性字段總數(shù)由小到大進行了運行時間的對比分析，對比分析結果如圖6所示.通過對運行時間的對比分析，我們發(fā)現(xiàn)加權PrivBayes隱私保護方法運行時間相對PrivBayes隱私保護方法運行時間較長，究其原因是由于該模型算法是構建在貝葉斯網絡基礎上，增加了對貝葉斯網絡所有連通分量的遍歷，增加了對貝葉斯網絡中屬性字段結點權重值的計算以及對選擇最優(yōu)發(fā)布屬性字段的選取的判斷，增加了對差分隱私保護(Laplace)向發(fā)布數(shù)據(jù)集注入噪聲屬性字段的優(yōu)化.加權PrivBayes隱私保護方法在總體運行時間上并不優(yōu)于PrivBayes隱私保護方法，它的總體運行時間相對較長.參數(shù)ε預算開銷值的變化，對其整體運行時間影響非常小，可以忽略.加權PrivBayes隱私保護方法增加了系統(tǒng)運行時間，但卻提高了發(fā)布數(shù)據(jù)集的實際應用價值和安全性，其所增加的時間是在系統(tǒng)使用用戶可接受的范圍內.

Fig. 6 The performance of the algorithms.圖6 算法性能

4.3 數(shù)據(jù)質量分析

發(fā)布數(shù)據(jù)集的精確度也是衡量隱私保護方法優(yōu)劣的一個極其重要指標.在本實驗中，我們對原始數(shù)據(jù)集進行了降維和差分隱私保護方法(Laplace)加噪聲處理，采用直接比較的方法[29-30]，對處理后的數(shù)據(jù)集信息丟失率進行精確度測算.為了對比分析處理前后數(shù)據(jù)的真實對應關系，我們對原始數(shù)據(jù)進行了改造，添加了唯一標識信息，使得匿名化處理后的數(shù)據(jù)能夠通過唯一標識信息找到原始數(shù)據(jù)，然后進行信息丟失率計算.對差分隱私模型處理后數(shù)據(jù)的精確度的計算，我們采用四舍五入取相鄰最近數(shù)據(jù)值的方法，雖然數(shù)據(jù)的計算結果有一定誤差，但根據(jù)實驗后的統(tǒng)計分析，數(shù)據(jù)計算損失率比較低，對分析對比結果沒有實質的影響，可以忽略不計，不影響實驗對比結果圖.實驗中將d取值為2,3,4,5,6,7,8進行多批數(shù)據(jù)信息丟失率對比，結果如圖7所示.從圖7中可以得出隨著d值的逐漸增大，發(fā)布的低維數(shù)據(jù)集數(shù)據(jù)信息精確度也逐漸增大.從圖7中我們能觀察到一種有趣的現(xiàn)象，PrivBayes的精確度是一條向下凹的弧線，隨著d值的逐漸增大逐漸向上延伸，原因是PrivBayes選擇的屬性字段是隨機的，也有交互信息最大的，這些屬性字段信息反映原始數(shù)據(jù)集的數(shù)據(jù)精確度低.而加權PrivBayes的精確度是一條向上凸的弧線，隨著d值的逐漸增大逐漸向上緩慢延伸，這是因為加權PrivBayes選擇的屬性字段從一開始就考慮了屬性字段屬性值的多樣性，這些屬性字段屬性值能最大化貼近原始數(shù)據(jù)集，因此這些屬性字段信息反映原始數(shù)據(jù)集的數(shù)據(jù)精確度高.通過實驗對比分析結果，加權PrivBayes隱私保護方法在發(fā)布數(shù)據(jù)集的精確性上明顯優(yōu)于PrivBayes隱私保護方法.

Fig. 7 The accuracy of published dataset.圖7 發(fā)布數(shù)據(jù)集精確性對比

5 結束語

本文闡述了PrivBayes模型的實現(xiàn)方法，并分析了PrivBayes模型存在的缺陷和不足.針對PrivBayes模型不能保證發(fā)布高質量的數(shù)據(jù)集、不能有效地防止敏感屬性信息泄露的問題,我們對PrivBayes模型進行了優(yōu)化處理，提出了加權PrivBayes隱私保護方法，該方法考慮了屬性字段屬性值的多樣性，對貝葉斯網絡中的結點增加權重值，優(yōu)化選擇的屬性字段結點加入噪聲時的順序服從拉普拉斯分布.我們通過樣例分析和真實的實驗數(shù)據(jù)結果證明，加權PrivBayes模型較之PrivBayes模型在發(fā)布數(shù)據(jù)集的數(shù)據(jù)精確性和安全性方面都有顯著的提升.

我們將在下一步的實驗工作中在研究內容和研究方向進行擴展，首先，我們將與更多的隱私保護模型進行實驗對比分析，本文僅限于與PrivBayes模型的對比;其次，我們將對更多的實驗測試數(shù)據(jù)集進行實驗對比分析;最后，我們將利用海量原始數(shù)據(jù)集的所有元組統(tǒng)計分析結果替代屬性字段屬性值的多樣性，研究這種替代方法是否具有更高的發(fā)布數(shù)據(jù)集數(shù)據(jù)精確性、安全性和可行性.

[1]Muralidhar K, Sarathy R. Security of random data perturbation methods[J]. ACM Trans on Database Systems, 1999, 24(4): 487-493

[2]Kargupta H, Datta S, Wang Q, et al. On the privacy preserving properties of random data perturbation techniques[C] //Proc of the 3rd Int Conf on Data Mining. Piscataway, NJ: IEEE, 2003: 99-106

[3]Chen K, Liu L. Privacy preserving data classification with rotation perturbation[C] //Proc of the 5th Int Conf on Data Mining. Piscataway, NJ: IEEE, 2005: 4

[4]Aggarwal C C, Philip S Y. A condensation approach to privacy preserving data mining[C] //Proc of Int Conf on Extending Database Technology. Berlin: Springer, 2004: 183-199

[5]Aggarwal C C, Yu P S. On static and dynamic methods for condensation-based privacy-preserving data mining[J]. ACM Trans on Database Systems, 2008, 33(1): 41-79

[6]Evfimievski A, Srikant R, Agrawal R, et al. Privacy preserving mining of association rules[J]. Information Systems, 2004, 29(4): 343-364

[7]Zhang X, Wu Y, Wang X. Differential privacy data release through adding noise on average value[G] //Network and System Security. Berlin: Springer, 2012: 417-429

[8]Dwork C, McSherry F, Nissim K, et al. Calibrating noise to sensitivity in private data analysis[G] //Theory of Cryptography. Berlin: Springer, 2006: 265-284

[9]Li M, Sampigethaya K, Huang L, et al. Swing & swap: User-centric approaches towards maximizing location privacy[C] //Proc of the 5th ACM Workshop on Privacy in Electronic Society. New York: ACM, 2006: 19-28

[10]Sweeney L.k-anonymity: A model for protecting privacy[J]. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2002, 10(5): 557-570[11]Sweeney L. Achievingk-anonymity privacy protection using generalization and suppression[J]. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2002, 10(5): 571-588

[12]Wong R C W, Li J, Fu A W C, et al. (α,k)-anonymity: An enhancedk-anonymity model for privacy preserving data publishing[C] //Proc of the 12th Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2006: 754-759

[13]Xiao X, Tao Y. Personalized privacy preservation[C] //Proc of the 2006 Int Conf on Management of Data. New York: ACM, 2006: 229-240

[14]Machanavajjhala A, Kifer D, Gehrke J, et al.l-diversity: Privacy beyondk-anonymity[J]. ACM Trans on Knowledge Discovery from Data, 2007, 1(1): 3

[15]Li N, Li T, Venkatasubramanian S.t-closeness: Privacy beyondk-anonymity andl-diversity[C] //Proc of the 23rd Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2007: 106-115

[16]Xiao X, Wang G, Gehrke J. Differential privacy via wavelet transforms[J]. IEEE Trans on Knowledge and Data Engineering, 2011, 23(8): 1200-1214

[17]Barak B, Chaudhuri K, Dwork C, et al. Privacy, accuracy, and consistency too: A holistic solution to contingency table release[C] //Proc of the 26th Symp on Principles of Database Systems. New York: ACM, 2007: 273-282

[18]LeFevre K, DeWitt D J, Ramakrishnan R. Incognito: Efficient full-domaink-anonymity[C] //Proc of the 2005 Int Conf on Management of Data. New York: ACM, 2005: 49-60

[19]Xiao X, Wang G, Gehrke J. Interactive anonymization of sensitive data[C] //Proc of the 2009 Int Conf on Management of Data. New York: ACM, 2009: 1051-1054

[20]McSherry F, Talwar K. Mechanism design via differential privacy[C] //Proc of the 48th Annual IEEE Symp on Foundations of Computer Science. Piscataway, NJ: IEEE, 2007: 94-103

[21]Nissim K, Smorodinsky R, Tennenholtz M. Approximately optimal mechanism design via differential privacy[C] //Proc of the 3rd Innovations in Theoretical Computer Science Conf. New York: ACM, 2012: 203-213

[22]Zhang J, Cormode G, Procopiuc C M, et al. PrivBayes: Private data release via Bayesian networks[C] //Proc of the 2014 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2014: 1423-1434

[23]Dwork C. Differential privacy: A survey of results[G] //Proc of Int Conf on Theory and Applications of Models of Computation. Berlin: Springer, 2008: 1-19

[24]Dwork C. Differential Privacy[M]. Berlin: Springer, 2011: 338-340

[25]Dwork C, McSherry F, Nissim K, et al. Calibrating noise to sensitivity in private data analysis[G] //Theory of cryptography. Berlin: Springer, 2006: 265-284

[26]Ding B, Winslett M, Han J, et al. Differentially private data cubes: Optimizing noise sources and consistency[C] //Proc of the 2011 Int Conf on Management of Data. New York: ACM, 2011: 217-228

[27]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-2): 1021-1032

[28]Cormode G, Procopiuc C, Srivastava D, et al. Differentially private spatial decompositions[C] //Porc of the 28th Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2012: 20-31

[29]Navarro-Arribas G, Torra V, Erola A, et al. Userk-anonymity for privacy preserving data mining of query logs[J]. Information Processing & Management, 2012, 48(3): 476-487

[30]Lixia W, Jianmin H. Utility evaluation ofk-anonymous data by microaggregation[C] //Proc of the 2009 Int Conf on Communication System, Networks and Applications. Piscataway, NJ: IEEE, 2009: 381-384

Wang Liang, born in 1975. PhD candidate of the Institute of Information Engineering, Chinese Academy of Sciences. Member of China Computer Federation. His main research interests include information security, and process of big data.

Wang Weiping, born in 1975. PhD. Professor of the Institute of Information Engineering, Chinese Academy of Sciences. Member of China Computer Federation. His main research interests include database technologies, storage and process of big data, and cloud computing(wangweiping@iie.acn.cn).

Meng Dan, born in 1965. PhD. Professor of the Institute of Information Engineering, Chinese Academy of Sciences. Fellow member of China Computer Federation. His main research interests include cloud computing and system security(mengdan@iie.ac.cn).

Privacy Preserving Data Publishing via Weighted Bayesian Networks

Wang Liang1,2, Wang Weiping1, and Meng Dan1

1(InstituteofInformationEngineering,ChineseAcademyofSciences,Beijing100093)2(UniversityofChineseAcademyofSciences,Beijing100049)

Privacy preserving in data publishing is a hot topic in the field of information security currently. How to effectively prevent the disclosure of sensitive information has become a major issue in enabling public access to the published dataset that contain personal information. As a newly developed notion of privacy preserving, differential privacy can provide strong security protection due to its greatest advantage of not making any specific assumptions on the attacker's background, and has been extensively studied. The existing approaches of differential privacy cannot fully and effectively solve the problem of releasing high-dimensional data. Although the PrivBayes can transform high-dimensional data to low-dimensional one, but cannot prevent attributes disclosure on certain conditions, and also has some limitations and shortcomings. In this paper, to solve these problems, we propose a new and powerful improved algorithm for data publishing called weighted PrivBayes. In this new algorithm, thorough both theoretical analysis and experiment evaluation, not only guarantee the security of the published dataset but also significantly improve the data accuracy and practical value than PrivBayes.

data privacy; Bayesian network; privacy preserving; data publishing; differential privacy

2016-06-20；

2016-08-15

國家“八六三”高技術研究發(fā)展計劃基金項目(2013AA013204);中國科學院戰(zhàn)略性先導科技專項課題(XDA06030200)

TP309.2

This work was supported by the National High Technology Research and Development Program of China (863 Program) (2013AA013204) and the State Priority Research Program of the Chinese Academy of Sciences (XDA06030200).