基于加權(quán)貝葉斯網(wǎng)絡(luò)的隱私數(shù)據(jù)發(fā)布方法

王 良 王偉平 孟 丹

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

?

基于加權(quán)貝葉斯網(wǎng)絡(luò)的隱私數(shù)據(jù)發(fā)布方法

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

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

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

數(shù)據(jù)隱私；貝葉斯網(wǎng)絡(luò)；隱私保護(hù)；數(shù)據(jù)發(fā)布；差分隱私

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

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

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

1 相關(guān)工作

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

1.1 差分隱私保護(hù)方法

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

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

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

(1)

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

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

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

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

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

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

(2)

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

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

1.2 貝葉斯網(wǎng)絡(luò)

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

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

Fig. 2 A Bayesian network N over five attributes.圖2 5個(gè)屬性字段結(jié)點(diǎn)的貝葉斯網(wǎng)絡(luò)N

定義4. 結(jié)點(diǎn)的入度.在貝葉斯網(wǎng)絡(luò)N中，以某一個(gè)結(jié)點(diǎn)為弧頭，終止于該結(jié)點(diǎn)弧的數(shù)目稱為該結(jié)點(diǎn)的入度.

定義5. 結(jié)點(diǎn)的出度.在貝葉斯網(wǎng)絡(luò)N中，以某一個(gè)結(jié)點(diǎn)為弧尾，起始于該結(jié)點(diǎn)弧的數(shù)目稱為該結(jié)點(diǎn)的出度.

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

在圖2的貝葉斯網(wǎng)絡(luò)N中，5個(gè)屬性字段結(jié)點(diǎn)分別是Age,Workclass,Education,Occupation,Income.對于圖2中任意2個(gè)屬性字段結(jié)點(diǎn)x,y∈A，x與y之間的關(guān)系存在3種可能性：

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

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

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

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

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

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

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

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

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

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；

輸出：貝葉斯網(wǎng)絡(luò)N.

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

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

步驟3. ① fori=2 toddo

② 初始化Ω=?;

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

⑤ end for

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

⑦ 將(Xi,Πi)加入貝葉斯網(wǎng)絡(luò)N，將屬性字段結(jié)點(diǎn)Xi加入V；

⑧ end for

步驟4. 返回貝葉斯網(wǎng)絡(luò)N.

2 貝葉斯網(wǎng)絡(luò)算法的局限性

2.1 貝葉斯網(wǎng)絡(luò)算法描述

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

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

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

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

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

2) PrivBayes模型選取首個(gè)屬性字段的方法隨機(jī)

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

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

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

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

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

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

Table1 The Attribute-Parent Pairs from N

5) PrivBayes模型沒有考慮貝葉斯網(wǎng)絡(luò)N中存在多個(gè)連通分量的情況.

在算法1中，如果屬性字段結(jié)點(diǎn)的關(guān)系是緊密的，并且存在唯一的連通分量，那么輸出的貝葉斯網(wǎng)絡(luò)N會滿足完整性約束條件.但是當(dāng)存在多個(gè)連通分量時(shí)，輸出的貝葉斯網(wǎng)絡(luò)N應(yīng)用價(jià)值會存在降低的情況.

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

Fig. 3 A Bayesian network M over nine attributes.圖3 9個(gè)屬性結(jié)點(diǎn)的貝葉斯網(wǎng)絡(luò)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、貝葉斯網(wǎng)絡(luò)N、參數(shù)k；

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

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

步驟2. ① fori=k+1 toddo

② 構(gòu)建屬性結(jié)點(diǎn)Xi的聯(lián)合分布

Dt[Xi,Πi];

④ 設(shè)Dt*[Xi,Πi]中的負(fù)值歸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 貝葉斯網(wǎng)絡(luò)加入噪聲處理的算法

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

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

1) PrivBayes模型并沒有考慮加入噪聲處理時(shí)，屬性字段結(jié)點(diǎn)的加入順序.

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

總之，PrivBayes模型在原始數(shù)據(jù)集D中根據(jù)最大交互信息選擇d個(gè)屬性字段，并不能最大化相似(或接近)原始數(shù)據(jù)集，因?yàn)閷傩宰侄蔚膶傩灾刀鄻有砸灿绊懼l(fā)布數(shù)據(jù)集的數(shù)據(jù)精確性.

3 加權(quán)貝葉斯網(wǎng)絡(luò)算法

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

3.1 權(quán)重值

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

圖4是圖2中屬性字段結(jié)點(diǎn)加入權(quán)重值的貝葉斯網(wǎng)絡(luò)N.

Fig. 4 A Bayesian network N over five weighted attributes.圖4 5個(gè)加權(quán)屬性字段結(jié)點(diǎn)的貝葉斯網(wǎng)絡(luò)N

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

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

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

Table 3 The Weights Table of Adult Data Set

定義9. 結(jié)點(diǎn)的動態(tài)權(quán)重值.在貝葉斯網(wǎng)絡(luò)N中，某一個(gè)屬性字段結(jié)點(diǎn)的權(quán)重值與該屬性字段結(jié)點(diǎn)所有入度結(jié)點(diǎn)權(quán)重值平均值之差，與該屬性字段結(jié)點(diǎn)所有出度結(jié)點(diǎn)權(quán)重值平均值之和，稱為該屬性字段結(jié)點(diǎn)的動態(tài)權(quán)重值.

動態(tài)權(quán)重值是我們評估貝葉斯網(wǎng)絡(luò)N中屬性字段結(jié)點(diǎn)的重要性的一個(gè)工具.當(dāng)前屬性結(jié)點(diǎn)的所有入度之和代表當(dāng)前屬性字段結(jié)點(diǎn)對其他結(jié)點(diǎn)的依賴性，該屬性字段結(jié)點(diǎn)的出度之和代表這個(gè)屬性字段結(jié)點(diǎn)對其他結(jié)點(diǎn)的貢獻(xiàn).

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

Table 4 The Dynamic Weights Table of N

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

算法3. IAGreedyBayes.

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

輸出：貝葉斯網(wǎng)絡(luò)N.

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

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

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

步驟4. ① fori=1 tomdo

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

③ end for

步驟5. ① fori=1 tomdo

②U=?;

③ forj=1 toCido

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

⑥ end for

⑦ end for

步驟6. 返回貝葉斯網(wǎng)絡(luò)N.

3.2 加權(quán)貝葉斯網(wǎng)絡(luò)算法描述

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

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

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

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

算法4. IANoisyConditionals.

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

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

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

步驟2. ① fori=k+1 toddo

② 構(gòu)建屬性結(jié)點(diǎn)Xi的聯(lián)合分布Pr[Xi,Πi]；

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

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

4 實(shí) 驗(yàn)

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

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

4.1 安全性分析

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

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

4.2 時(shí)間性能分析

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

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

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

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

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

5 結(jié)束語

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

我們將在下一步的實(shí)驗(yàn)工作中在研究內(nèi)容和研究方向進(jìn)行擴(kuò)展，首先，我們將與更多的隱私保護(hù)模型進(jìn)行實(shí)驗(yàn)對比分析，本文僅限于與PrivBayes模型的對比;其次，我們將對更多的實(shí)驗(yàn)測試數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)對比分析;最后，我們將利用海量原始數(shù)據(jù)集的所有元組統(tǒng)計(jì)分析結(jié)果替代屬性字段屬性值的多樣性，研究這種替代方法是否具有更高的發(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

國家“八六三”高技術(shù)研究發(fā)展計(jì)劃基金項(xiàng)目(2013AA013204);中國科學(xué)院戰(zhàn)略性先導(dǎo)科技專項(xiàng)課題(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).