朱 徐 亞

(安徽理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 安徽 淮南 232001)

近年來，個(gè)人隱私泄露問題開始引發(fā)人們的擔(dān)憂，數(shù)據(jù)隱私保護(hù)成為計(jì)算機(jī)學(xué)科的熱門領(lǐng)域。其中，高維合成數(shù)據(jù)集的隱私保護(hù)數(shù)據(jù)發(fā)布問題是一個(gè)巨大的挑戰(zhàn)。一般的高維數(shù)據(jù)集發(fā)布算法會(huì)出現(xiàn)計(jì)算復(fù)雜度過高的問題，若直接使用擾動(dòng)策略對(duì)數(shù)據(jù)集加噪，會(huì)因?yàn)樽⑷脒^多的噪聲導(dǎo)致數(shù)據(jù)的可用性降低。目前最流行的解決方案是采用差分隱私機(jī)制[1]。Mohammed等[2]提出了一種針對(duì)決策樹分析的差分隱私合成數(shù)據(jù)發(fā)布算法DiffGen。Chen等[3]提出了一種基于新型稀疏向量技術(shù)合成數(shù)據(jù)集的方法，結(jié)合差分隱私分析所有屬性之間的成對(duì)關(guān)系生成無向的依賴關(guān)系圖，并由此得到聯(lián)合樹模型。然而該新型向量技術(shù)中的隱私分析過程是錯(cuò)誤的[4]，無法實(shí)現(xiàn)預(yù)期的隱私保障。Li等[5]提出了一個(gè)利用高斯Copula函數(shù)的差分隱私數(shù)據(jù)合成器DPSynthesizer。Zhang等[6]提出了一種基于貝葉斯網(wǎng)絡(luò)的高維合成數(shù)據(jù)集生成算法PrivBayes，目前流行的GAN模型的結(jié)構(gòu)化數(shù)據(jù)生成算法仍處于起步階段，存在諸多缺陷[7-8]。

為了解決PrivBayes在貝葉斯網(wǎng)絡(luò)建模階段使用互信息作為屬性相關(guān)性衡量標(biāo)準(zhǔn)所帶來的數(shù)據(jù)信噪比低的問題，本文提出基于差分隱私采樣機(jī)制的DPSM-Bayes算法，通過采樣機(jī)制調(diào)整數(shù)據(jù)量的大小，能夠使數(shù)據(jù)集獲得最優(yōu)可用性，提出一種改進(jìn)的Laplace機(jī)制替換原本的差分隱私Laplace機(jī)制，可以有效地降低在較低的概率分布上添加正的Laplace噪聲所引起的系統(tǒng)偏差，在隱私保護(hù)程度不變的情況下，進(jìn)一步提高數(shù)據(jù)集的可用性。

1 基本概念

假設(shè)數(shù)據(jù)持有方A將數(shù)據(jù)發(fā)布給數(shù)據(jù)使用方B，數(shù)據(jù)使用方B希望從數(shù)據(jù)中學(xué)到盡可能多的知識(shí)，與此同時(shí)，A不希望B學(xué)到任何的個(gè)體信息。假設(shè)數(shù)據(jù)持有方A持有的數(shù)據(jù)集為高維列表數(shù)據(jù)集，數(shù)據(jù)集D由d個(gè)屬性或隨機(jī)變量組成，即X={X1,X2,…,Xd}，數(shù)據(jù)集包含n條元組且符合獨(dú)立同分布。算法實(shí)現(xiàn)的目標(biāo)是采用非交互式查詢框架，直接發(fā)布一個(gè)滿足差分隱私保護(hù)的脫敏的合成數(shù)據(jù)集。

1.1 差分隱私

2006年，Dwork等[9]提出差分隱私的概念，要求所發(fā)布數(shù)據(jù)集的任何信息必須要經(jīng)過一個(gè)隨機(jī)化算法的處理，保障數(shù)據(jù)集中的任何一條記錄的個(gè)體信息不被泄露。差分隱私擁有嚴(yán)格的統(tǒng)計(jì)學(xué)定義，能夠?qū)﹄[私保護(hù)水平進(jìn)行量化評(píng)估。

定義1ε-差分隱私[9]：假設(shè)有隨機(jī)化算法G，O為G的任意可能輸出，若對(duì)于任意兩個(gè)至多相差一條元組的相鄰數(shù)據(jù)集D1和D2，滿足：

Pr[G(D1)=O]≤eε·Pr[G(D2)=O]

(1)

則稱算法G滿足ε-差分隱私保護(hù)。其中:參數(shù)ε為隱私保護(hù)預(yù)算；Pr[·]表示事件發(fā)生的概率。

定義2 全局敏感度[9]：設(shè)有函數(shù)f:D→Rd，輸入為一數(shù)據(jù)集，輸出為一個(gè)d維實(shí)數(shù)向量，對(duì)于任意的相鄰數(shù)據(jù)集D1和D2，

(2)

稱為函數(shù)f的全局敏感度。

定義3 Laplace機(jī)制[9]：設(shè)有函數(shù)f:D→Rd，函數(shù)的敏感度為Δf，若Y～Lap(Δf/ε)為加入的隨機(jī)噪聲，則算法G(D)=f(D)+Y滿足ε-差分隱私保護(hù)。

定義5 序列組合性[11]：設(shè)有一個(gè)隨機(jī)化算法序列G1,G2,…,Gm，算法Gi符合εi-差分隱私保護(hù)，則算法序列Gi(D)滿足(∑iεi)-差分隱私保護(hù)。

定義6 并行組合性[12]：設(shè)有一組隨機(jī)化算法G1,G2,…,Gm，算法Gi符合εi-差分隱私保護(hù)，對(duì)于任意不相交的數(shù)據(jù)集D1,D2,…,Dm，則由這些算法組成的組合算法G(G1(D1),G2(D2),…Gm(Dm))滿足(maxεi)-差分隱私保護(hù)。

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

貝葉斯網(wǎng)絡(luò)[13]又被稱為信念網(wǎng)絡(luò)，是一種概率圖型模型，是一個(gè)有向無環(huán)圖如圖1所示。對(duì)于數(shù)據(jù)集D，D中的每個(gè)屬性被表示為一個(gè)節(jié)點(diǎn)，數(shù)據(jù)集中屬性間的相互關(guān)系被表示為有向邊的形式。

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

貝葉斯網(wǎng)絡(luò)為概率分布提供了一種簡潔的表示方式，可以使用貝葉斯網(wǎng)絡(luò)來描述概率分布中隨機(jī)變量之間的相互依賴關(guān)系，從而描述一個(gè)概率分布。假設(shè)有一個(gè)離散隨機(jī)變量集合X={X1,X2,…,Xd}，貝葉斯網(wǎng)絡(luò)可以將它們的聯(lián)合概率分布表示為

(3)

也稱貝葉斯網(wǎng)絡(luò)的鏈?zhǔn)椒▌t[14]，貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)領(lǐng)域就是專門研究這個(gè)問題的[15]。

2 差分隱私保護(hù)下的高維數(shù)據(jù)集發(fā)布算法

針對(duì)PrivBayes算法的缺點(diǎn)，本文提出一種新穎的差分隱私保護(hù)下的高維數(shù)據(jù)集發(fā)布算法DPSM-Bayes，實(shí)現(xiàn)流程圖如圖2所示。

圖2 差分隱私保護(hù)下的高維數(shù)據(jù)集發(fā)布算法流程圖

2.1 基于采樣機(jī)制構(gòu)建滿足差分隱私保護(hù)的貝葉斯網(wǎng)絡(luò)

為了降低計(jì)算復(fù)雜度，GreedyBayes算法將貝葉斯網(wǎng)絡(luò)的度k限制在一個(gè)較小的值，大大減少了時(shí)間開銷，使用互信息作為屬性間相關(guān)程度的評(píng)分函數(shù)，利用差分隱私指數(shù)機(jī)制，選擇出滿足差分隱私保護(hù)的最優(yōu)父節(jié)點(diǎn)集，進(jìn)而構(gòu)造出滿足差分隱私保護(hù)的貝葉斯網(wǎng)絡(luò)。

相比較于互信息I的值域，互信息的敏感度是一個(gè)不小的值，當(dāng)評(píng)分函數(shù)的敏感度較大時(shí)，很有可能添加的噪聲量覆蓋了原本的數(shù)據(jù)量，導(dǎo)致構(gòu)建的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)與數(shù)據(jù)集概率分布的擬合程度較差。因此，本文利用差分隱私采樣機(jī)制[16]滿足差分隱私保護(hù)的貝葉斯網(wǎng)絡(luò)構(gòu)建算法SMBayes。

定義7 采樣機(jī)制[16]：設(shè)有滿足ε-差分隱私的隨機(jī)化算法G，則對(duì)于這樣的一個(gè)算法Gα：首先以概率α對(duì)輸入數(shù)據(jù)集中每條元組獨(dú)立采樣，接著對(duì)采樣得到的數(shù)據(jù)集應(yīng)用算法G。則算法Gα為輸入數(shù)據(jù)集提供了ln(1+α(eε-1))-差分隱私保護(hù)。

本文提出基于差分隱私采樣機(jī)制的子算法SMBayes算法，輸入為原始數(shù)據(jù)集D、貝葉斯網(wǎng)絡(luò)的度k、隱私預(yù)算ε1，輸出為貝葉斯網(wǎng)絡(luò)N。該算法的具體描述步驟：

(1)計(jì)算采樣率α；

(2)以概率α對(duì)D中的元組采樣，得到輸入數(shù)據(jù)集D′；

(3)εα=ln(eε1-1+α)-lnα；

(4)初始化N=?，V=?；

(5)隨機(jī)選取X中的一個(gè)屬性作為貝葉斯網(wǎng)絡(luò)的首節(jié)點(diǎn)X1，將(X1,?)添加到N，將X1添加到V；

(6)fori=2 tod;

(7)初始化Ω=?；

(9)對(duì)輸入數(shù)據(jù)集D′，使用差分隱私指數(shù)機(jī)制，以互信息為評(píng)分函數(shù)，隱私預(yù)算為εα/(d-1)，從Ω中選出一個(gè)AP對(duì)(Xi,Π(Xi))；

(10)將選出的AP對(duì)(Xi,Π(Xi))添加到N，將Xi添加到V；

(11)end for;

(12)returnN。

通過分析不同數(shù)據(jù)集大小情況下，敏感度ΔI與采樣機(jī)制的隱私預(yù)算εα之間的關(guān)系，得到采樣輸入數(shù)據(jù)集D′最佳尺寸的計(jì)算公式：

(4)

其中：1

2.2 基于改進(jìn)的Laplace機(jī)制對(duì)邊緣分布加噪

本文提出改進(jìn)的Laplace機(jī)制IMLap-Noisy算法。該算法的輸入為原始數(shù)據(jù)集D、貝葉斯網(wǎng)絡(luò)N、隱私預(yù)算ε2，輸出為d個(gè)滿足差分隱私保護(hù)的邊緣條件概率分布。IMLap-Noisy算法具體描述步驟：

(1)初始化P*=?；

(2)fori=1 tod；

(3)由AP對(duì)(Xi,Π(Xi))和D實(shí)體化聯(lián)合概率分布Pr(Xi,Π(Xi))；

(5)根據(jù)Pr*(Xi,Π(Xi))計(jì)算閾值t；

(6)forpinPr*(Xi,Π(Xi));

(7)ifp

(8)end for;

(9)歸一化Pr*(Xi,Π(Xi))；

(10)由Pr*(Xi,Π(Xi))得到Pr*(Xi|Π(Xi))并將其添加到P*；

(11)end for;

(12)returnP*;

閾值t計(jì)算是IMLaplace機(jī)制的核心，t的計(jì)算公式為

(5)

其中:t=i/1 000，i∈*且0

從邊緣分布采樣生成合成數(shù)據(jù)集的過程相對(duì)于前兩個(gè)過程較為簡單，利用貝葉斯網(wǎng)絡(luò)的特點(diǎn)，采用邏輯采樣方法[17]。每次通過一個(gè)低維條件概率分布采樣出對(duì)應(yīng)的一個(gè)屬性值，作為其他屬性的父節(jié)點(diǎn)取值進(jìn)而確定下一個(gè)屬性的值。由于貝葉斯網(wǎng)絡(luò)是一個(gè)有向無環(huán)圖，當(dāng)我們對(duì)最后一個(gè)屬性進(jìn)行采樣時(shí)，在此之前的所有屬性都已經(jīng)采樣結(jié)束，即得到了一條完整的記錄。邏輯采樣可以生成任意數(shù)量的記錄，考慮到某些應(yīng)用需要合成數(shù)據(jù)集與原始數(shù)據(jù)集的記錄數(shù)量相似，同時(shí)有利于在實(shí)驗(yàn)評(píng)估階段對(duì)兩個(gè)數(shù)據(jù)集進(jìn)行對(duì)比分析，仍然選用n作為合成數(shù)據(jù)集的大小。

3 實(shí)驗(yàn)評(píng)估

實(shí)驗(yàn)選用的數(shù)據(jù)集的具體描述如表1所示，選用平均變分距離和Wasserstein距離作為概率分布間的距離度量，選用SVM分類準(zhǔn)確度作為合成數(shù)據(jù)集可用性的度量標(biāo)準(zhǔn)。

表1 實(shí)驗(yàn)選用的數(shù)據(jù)集

3.1 IMLaplace機(jī)制的性能

為了評(píng)估IMLaplace機(jī)制的性能，將IMLaplace機(jī)制與原始Laplace機(jī)制進(jìn)行對(duì)比，采用平均變分距離和Wasserstein距離作為加噪前后的概率分布的距離度量，評(píng)估兩種機(jī)制加入的噪聲對(duì)概率分布的影響；將由概率分布采樣出的數(shù)據(jù)集構(gòu)造的支持向量機(jī)(SVM)分類器模型的分類準(zhǔn)確度作為數(shù)據(jù)可用性的度量，一定程度上可以反映兩種加噪機(jī)制對(duì)數(shù)據(jù)集質(zhì)量的影響程度。實(shí)驗(yàn)中選用的數(shù)據(jù)集為Cancer、Sachs和Alarm，實(shí)驗(yàn)結(jié)果均為20次實(shí)驗(yàn)的平均值。實(shí)驗(yàn)結(jié)果如表2和表3所示。在平均變分距離和Wasserstein距離2種度量下，IMLaplace機(jī)制都取得了比原始的Laplace機(jī)制更好的效果。

表2 平均變分距離 單位：%

表3 Wasserstein距離 單位：%

在評(píng)估2種加噪機(jī)制對(duì)數(shù)據(jù)集質(zhì)量和可用性的影響，每個(gè)數(shù)據(jù)集分別選出兩個(gè)屬性作為兩組實(shí)驗(yàn)的類別屬性，其他屬性作為特征屬性，構(gòu)造SVM分類器模型，將原始數(shù)據(jù)集的20%作為測試集，驗(yàn)證2種機(jī)制下的分類準(zhǔn)確度。隱私預(yù)算ε設(shè)置為0.01～1.6，結(jié)果如圖3～圖5所示。NoLaplace表示不對(duì)概率分布進(jìn)行Laplace加噪處理，在圖中作為基準(zhǔn)分類準(zhǔn)確度。

(a) Cancer Y=Smoker (b) Cancer Y=Cancer

(a) Sachs Y=Mek (b) Sachs Y=Raf

(a) Alarm Y=LVEDVolume (b) Alarm Y=TPR

隨著隱私預(yù)算ε的增加，不同數(shù)據(jù)集上屬性的分類準(zhǔn)確度均逐漸增大因?yàn)殡[私預(yù)算增加時(shí)，對(duì)數(shù)據(jù)的隱私保護(hù)程度降低，對(duì)數(shù)據(jù)添加的噪聲擾動(dòng)較少，數(shù)據(jù)集的質(zhì)量和可用性提高。當(dāng)隱私預(yù)算ε的值較小時(shí)，能夠看到IMLaplace機(jī)制得到的數(shù)據(jù)集的分類準(zhǔn)確度明顯高于Laplace機(jī)制，并且隨著隱私預(yù)算ε的增加，兩者之間的差距呈現(xiàn)逐漸縮小的變化趨勢，直到接近基準(zhǔn)分類準(zhǔn)確度，因?yàn)樵陔[私預(yù)算ε的值較小的情況下，Laplace機(jī)制添加的噪聲值較大的概率最高，對(duì)較低的概率值添加正噪聲的概率也最高，IMLaplace機(jī)制能夠很好地解決該問題。

3.2 DPSM-Bayes算法的性能

為了驗(yàn)證和評(píng)估DPSM-Bayes算法的性能優(yōu)越性，選用PrivBayes算法作為對(duì)照組，分別讓兩種算法輸出的合成數(shù)據(jù)集執(zhí)行分類任務(wù)，選用SVM分類器作為分類模型，通過分類準(zhǔn)確度驗(yàn)證兩種算法生成的數(shù)據(jù)集的質(zhì)量和可用性，如圖6和圖7所示。

隨著隱私預(yù)算ε的增加，在NLTCS和ACS兩個(gè)數(shù)據(jù)集上的分類準(zhǔn)確度均逐漸增加，表明隱私保護(hù)程度和數(shù)據(jù)的可用性是矛盾的，隱私保護(hù)程度越高，數(shù)據(jù)集的可用性就越低。因此，在實(shí)際應(yīng)用中要在隱私保護(hù)程度和數(shù)據(jù)可用性之間尋求一個(gè)平衡點(diǎn)。另外，相對(duì)于NLTCS數(shù)據(jù)集，ACS數(shù)據(jù)集上2種算法的分類準(zhǔn)確度與基準(zhǔn)分類準(zhǔn)確度的距離明顯更大。在圖6和圖7中，DPSM-Bayes算法生成數(shù)據(jù)集的分類準(zhǔn)確度均高于PrivBayes算法的分類準(zhǔn)確度，表明DPSM-Bayes算法生成的數(shù)據(jù)集的質(zhì)量和可用性明顯優(yōu)于PrivBayes算法。

(a) NLTCS Y=Outside (b) NLTCS Y=Bathroom

(a) ACS Y=Mortgage (b) ACS Y=School

4 結(jié) 語

為了解決隱私保護(hù)高維數(shù)據(jù)集發(fā)布中存在的計(jì)算復(fù)雜度高和數(shù)據(jù)可用性低的問題，針對(duì)PrivBayes算法的缺陷，提出了DPSM-Bayes算法，優(yōu)化了互信息敏感度過高帶來的信噪比低的問題，利用差分隱私采樣機(jī)制選取更合適的數(shù)據(jù)集尺寸，從而緩解該問題。本文還提出了更適合于高維數(shù)據(jù)分布加噪的IMLaplace機(jī)制，能夠有效地緩解由于在較低的概率值上加入正噪聲所帶來的誤差。在相同的隱私保護(hù)程度下，DPSM-Bayes算法在數(shù)據(jù)生成質(zhì)量和可用性上明顯優(yōu)于PrivBayes算法，實(shí)現(xiàn)了隱私保護(hù)高維數(shù)據(jù)集發(fā)布在隱私性和可用性之間的平衡。