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

朱 徐 亞

(安徽理工大學 計算機科學與工程學院， 安徽 淮南 232001)

近年來，個人隱私泄露問題開始引發(fā)人們的擔憂，數(shù)據(jù)隱私保護成為計算機學科的熱門領(lǐng)域。其中，高維合成數(shù)據(jù)集的隱私保護數(shù)據(jù)發(fā)布問題是一個巨大的挑戰(zhàn)。一般的高維數(shù)據(jù)集發(fā)布算法會出現(xiàn)計算復(fù)雜度過高的問題，若直接使用擾動策略對數(shù)據(jù)集加噪，會因為注入過多的噪聲導致數(shù)據(jù)的可用性降低。目前最流行的解決方案是采用差分隱私機制[1]。Mohammed等[2]提出了一種針對決策樹分析的差分隱私合成數(shù)據(jù)發(fā)布算法DiffGen。Chen等[3]提出了一種基于新型稀疏向量技術(shù)合成數(shù)據(jù)集的方法，結(jié)合差分隱私分析所有屬性之間的成對關(guān)系生成無向的依賴關(guān)系圖，并由此得到聯(lián)合樹模型。然而該新型向量技術(shù)中的隱私分析過程是錯誤的[4]，無法實現(xiàn)預(yù)期的隱私保障。Li等[5]提出了一個利用高斯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)性衡量標準所帶來的數(shù)據(jù)信噪比低的問題，本文提出基于差分隱私采樣機制的DPSM-Bayes算法，通過采樣機制調(diào)整數(shù)據(jù)量的大小，能夠使數(shù)據(jù)集獲得最優(yōu)可用性，提出一種改進的Laplace機制替換原本的差分隱私Laplace機制，可以有效地降低在較低的概率分布上添加正的Laplace噪聲所引起的系統(tǒng)偏差，在隱私保護程度不變的情況下，進一步提高數(shù)據(jù)集的可用性。

1 基本概念

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

1.1 差分隱私

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

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

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

(1)

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

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

(2)

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

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

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

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

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

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

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

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

(3)

也稱貝葉斯網(wǎng)絡(luò)的鏈式法則[14]，貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學習領(lǐng)域就是專門研究這個問題的[15]。

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

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

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

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

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

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

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

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

(1)計算采樣率α；

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

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

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

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

(6)fori=2 tod;

(7)初始化Ω=?；

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

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

(11)end for;

(12)returnN。

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

(4)

其中：1

2.2 基于改進的Laplace機制對邊緣分布加噪

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

(1)初始化P*=?；

(2)fori=1 tod；

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

(5)根據(jù)Pr*(Xi,Π(Xi))計算閾值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計算是IMLaplace機制的核心，t的計算公式為

(5)

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

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

3 實驗評估

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

表1 實驗選用的數(shù)據(jù)集

3.1 IMLaplace機制的性能

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

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

表3 Wasserstein距離 單位：%

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

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

3.2 DPSM-Bayes算法的性能

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

隨著隱私預(yù)算ε的增加，在NLTCS和ACS兩個數(shù)據(jù)集上的分類準確度均逐漸增加，表明隱私保護程度和數(shù)據(jù)的可用性是矛盾的，隱私保護程度越高，數(shù)據(jù)集的可用性就越低。因此，在實際應(yīng)用中要在隱私保護程度和數(shù)據(jù)可用性之間尋求一個平衡點。另外，相對于NLTCS數(shù)據(jù)集，ACS數(shù)據(jù)集上2種算法的分類準確度與基準分類準確度的距離明顯更大。在圖6和圖7中，DPSM-Bayes算法生成數(shù)據(jù)集的分類準確度均高于PrivBayes算法的分類準確度，表明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é) 語

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