改進貝葉斯網(wǎng)絡(luò)的個性化隱私數(shù)據(jù)發(fā)布方法

陳思陽

（山東科技大學計算機科學與工程學院，山東青島 266590）

0 引言

在大數(shù)據(jù)時代，數(shù)據(jù)開放與共享已成為必然趨勢［1］。為了方便研究與應用，許多機構(gòu)和組織會公開發(fā)布數(shù)據(jù)，然而這些數(shù)據(jù)可能包含個人敏感信息，如果直接發(fā)布會導致用戶隱私泄露。例如，疾病預防控制中心需要從各種醫(yī)療機構(gòu)收集病例，若未經(jīng)處理便發(fā)布了原始信息，患者個人信息可能會被非法利用，對其日常生活造成嚴重影響［2］。為解決該問題，諸多學者對隱私保護數(shù)據(jù)發(fā)布（Privacy-Preserving Data Publishing，PPDP）方法［3］進行了研究，目的是保護原始數(shù)據(jù)的隱私信息，同時為后續(xù)數(shù)據(jù)分析保留盡可能多的數(shù)據(jù)效用。

k-匿名模型［4］是PPDP 領(lǐng)域提出的第一個隱私保護模型，由于其簡單性和有效性而得到廣泛應用［5］。k-匿名模型雖然可以防止身份泄露，但不足以防御屬性泄露。因此，若干種擴展k-匿名模型被提出，如l-多樣性［6］、t-緊密度［7］、（k，l）-多樣性［8］、（α，ε）-匿名［9］、p-敏感度k-匿名［10］，以及各種改進的匿名模型［11-13］。這些模型大多是基于k-匿名模型的傳統(tǒng)隱私保護技術(shù)，需要特殊的背景攻擊假設(shè)，不能提供嚴格有效的數(shù)學證明，從而降低了隱私保護的可靠性。

差分隱私保護方法由Dwork［14］提出，其克服了傳統(tǒng)隱私保護方法的主要缺陷，無需考慮攻擊者擁有的背景知識，并使用嚴格的數(shù)學推理證明對隱私保護模型進行量化。該方法要求在查詢結(jié)果中添加噪聲，因此主要應用于查詢結(jié)果的發(fā)布中［15］?；诖耍琀asan 等［16］提出一種非交互式保護框架，通過轉(zhuǎn)換或壓縮原始數(shù)據(jù)向查詢結(jié)果中添加噪聲以滿足ε-差分隱私。非交互式隱私保護模型可以發(fā)布經(jīng)過離線處理且滿足差分隱私的數(shù)據(jù)集，用戶可以直接在數(shù)據(jù)集上執(zhí)行查詢操作，解決了交互式場景下受到查詢接口限制的問題［17］。Zhang 等［18］提出的PrivBayes 是隱私保護數(shù)據(jù)發(fā)布方法的典型代表，該方法通過構(gòu)建貝葉斯網(wǎng)絡(luò)保持屬性間概率的一致性，同時保留了原始數(shù)據(jù)的固有特征，后續(xù)許多學者在此基礎(chǔ)上進行了改進。例如，王良等［19］提出加權(quán)PrivBayes 方法，其考慮到字段屬性值的多樣性，優(yōu)化選擇了屬性字段結(jié)點加入噪聲的順序，以構(gòu)建更優(yōu)的貝葉斯網(wǎng)絡(luò)；Li 等［20］提出平滑PrivBayes 方法，引入平滑敏感度機制，可以在實現(xiàn)差分隱私的同時減少噪聲，從而提高聯(lián)合分布的精度。

然而以上算法均未對實現(xiàn)差分隱私時屬性的敏感程度作出討論，因此本文提出一種改進貝葉斯網(wǎng)絡(luò)的個性化隱私數(shù)據(jù)發(fā)布算法CSAPrivBayes。該法通過關(guān)聯(lián)敏感屬性程度劃分屬性區(qū)域進而分配隱私預算，同時改進了貝葉斯網(wǎng)絡(luò)的初始結(jié)點隨機選擇機制，在保護隱私的同時保證了數(shù)據(jù)可用性。

1 差分隱私與貝葉斯網(wǎng)絡(luò)

1.1 差分隱私

差分隱私保護模型定義了極其嚴格的攻擊模型，成為數(shù)據(jù)發(fā)布領(lǐng)域最重要的隱私保護方法之一。

對于只有一個元組不同的兩個數(shù)據(jù)集D1和D2，如果隨機算法G滿足ε-差分隱私［14］，則對于隨機算法G，任何可能的輸出O滿足：

式中，Pr[?]為事件發(fā)生的概率，參數(shù)ε為隱私保護預算。F為將數(shù)據(jù)集映射到固定大小實數(shù)向量的函數(shù)。函數(shù)F的敏感度［21］定義為：

給定數(shù)據(jù)集D和查詢函數(shù)f:D→Rd，f的敏感度為S(f)。算法M(D)=f(D)+η通過向f(D)輸出的每個值添加隨機噪聲η來實現(xiàn)ε-差分隱私的Laplace 機制［21］。隨機噪聲η的概率密度函數(shù)為：

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

設(shè)A為數(shù)據(jù)集D上的一組屬性，Pr[A]為A上的聯(lián)合概率分布，屬性集A上的貝葉斯網(wǎng)絡(luò)描述了A中某些屬性之間的條件獨立性。貝葉斯網(wǎng)絡(luò)為有向無環(huán)圖，其將A中的每個屬性表示為一個結(jié)點，使用有向邊對A中屬性之間的條件獨立性進行建模。圖1 展示了具有5 個屬性的集合A上的貝葉斯網(wǎng)絡(luò)。

Fig.1 Bayesian network圖1 貝葉斯網(wǎng)絡(luò)

Pr[A]表示數(shù)據(jù)集D的全分布，貝葉斯網(wǎng)絡(luò)實質(zhì)上是用d 個條件分布Pr[X1|Π1],Pr[X2|Π2],…,Pr[Xd|Πd]以近似全分布Pr[A]。在給定Xi的屬性父結(jié)點集Πi的情況下，任意Xi和Xj?Πi是條件獨立的，可得到：

2 基于貝葉斯網(wǎng)絡(luò)的個性化差分隱私算法

2.1 PrivBayes 算法

PrivBayes 是一種用于發(fā)布高維數(shù)據(jù)的差分隱私方法，主要包括以下3 個步驟，分別為構(gòu)建貝葉斯網(wǎng)絡(luò)、擾動概率分布和隨機取樣［18］。

（1）在構(gòu)建貝葉斯網(wǎng)絡(luò)階段，從屬性集合中隨機選擇一個屬性作為貝葉斯網(wǎng)絡(luò)的起點，采用貪心算法從剩余屬性中選擇出具有最大互信息的父子結(jié)點對，并將其添加到貝葉斯網(wǎng)絡(luò)中。當所有結(jié)點被添加到貝葉斯網(wǎng)絡(luò)中后，輸出構(gòu)造完成的貝葉斯網(wǎng)絡(luò)。

（2）在擾動概率分布階段，首先根據(jù)構(gòu)建的貝葉斯網(wǎng)絡(luò)計算屬性的聯(lián)合概率分布P[Xi,Πi]，然后將拉普拉斯噪聲注入P[Xi,Πi] 以獲得 噪聲分 布P*[Xi,Πi]。添加到P[Xi,Πi]的拉普拉斯噪聲比例設(shè)定為4(d-k)/nε，確保P*[Xi,Πi]的生成滿足(ε/2(d-k))-差分隱私，P[Xi,Πi]具有的敏感度。

（3）在隨機取樣階段，首先將第一個屬性結(jié)點按照屬性取值劃分概率區(qū)間，生成一個隨機數(shù)，根據(jù)其所在的取值區(qū)間確定X1的取樣值。對于剩余屬性結(jié)點，在給定父結(jié)點下按照屬性取值劃分聯(lián)合概率區(qū)間，再根據(jù)生成隨機數(shù)所在概率區(qū)間確定X的取樣值。

2.2 CSAPrivBayes 算法

PrivBayes 算法解決了高維數(shù)據(jù)的發(fā)布安全問題，但也存在一些不足。該算法隨機選取了首個屬性，通過向?qū)傩缘牡途S聯(lián)合分布概率加入拉普拉斯機制實現(xiàn)差分隱私保護，并沒有考慮敏感屬性和一般屬性，可能導致敏感屬性隱私泄露以及一般屬性隱私保護過度。為此，本文提出CSAPrivBayes 算法，首先定義靜態(tài)權(quán)重值作為選取首個網(wǎng)絡(luò)結(jié)點的依據(jù)以提高貝葉斯網(wǎng)絡(luò)精度，再根據(jù)準標識符屬性關(guān)聯(lián)敏感屬性的程度進行區(qū)域劃分，進而采用不同隱私預算，實現(xiàn)個性化差分隱私保護。算法具體步驟如下：

（1）輸入：數(shù)據(jù)集D、參數(shù)k、閾值θ。

（2）輸出：低維帶噪數(shù)據(jù)集D'。

（3）對數(shù)據(jù)集D進行預處理，采用二分k均值算法將連續(xù)屬性離散化。

（4）計算數(shù)據(jù)集D中所有屬性X的靜態(tài)權(quán)重值W，選取W值最大的屬性作為X1，將其添加到網(wǎng)絡(luò)N中。對于有d個屬性的數(shù)據(jù)集，屬性Xi的靜態(tài)權(quán)重值為：

（5）使用貪婪搜索策略選擇最大的互信息對(Xi,Πi)，將其添加到貝葉斯網(wǎng)絡(luò)N中。

（6）重復步驟（5）直至選擇出(d-1)個AP對。

（7）計算N中屬性結(jié)點Xi的聯(lián)合概率分布P[Xi,Πi]。

（8）計算N中所有屬性與敏感屬性的互信息I(Xi,S)。數(shù)據(jù)集D中的準標識符屬性Qi與敏感屬性S的互信息為：

（9）如果屬性Xi的I(Xi,S)≥閾值θ，則將其劃分到區(qū)域A，否則劃分到區(qū)域B。

（12）將加噪的聯(lián)合分布P*[Xi,Πi]中的負值歸零并歸一化。

（13）從P*[Xi,Πi]中隨機采樣P*[Xi|Πi]生成低維帶噪數(shù)據(jù)集D'。

（14）輸出低維帶噪數(shù)據(jù)集D'。

3 實驗與結(jié)果分析

3.1 實驗環(huán)境與數(shù)據(jù)集

硬件環(huán)境：Intel（R）Core（TM）i5-5200U CPU@ 2.20 GHz，內(nèi)存8G，操作系統(tǒng)Win7_64 位旗艦版；軟件環(huán)境：使用Python 編程語言實現(xiàn)，IDE 開發(fā)工具為Pycharm。使用美國人口普查數(shù)據(jù)集，隨機選擇24 000 條數(shù)據(jù)，其中選取6 個離散屬性，4 個連續(xù)屬性，具體信息如表1 所示。

Table 1 Dataset information表1 數(shù)據(jù)集信息

3.2 評價指標

使用誤分類率評估所發(fā)布合成數(shù)據(jù)集的可用性，誤分類率越小，數(shù)據(jù)集的可用性越高。設(shè)FN為實際為正例且被分類器分為負例的個數(shù)，F(xiàn)P為實際為負例且被分類器分為正例的個數(shù)，P為實際的正例個數(shù)，N為實際的負例個數(shù)，則誤分類率的計算公式為：

使用分類準確率評估所生成貝葉斯網(wǎng)絡(luò)分類的精確度，分類準確率越高，貝葉斯網(wǎng)絡(luò)的精確度越好。設(shè)TP為實際為正例且被分類器分為正例的個數(shù)，TN為實際為負例且被分類器分為負例的個數(shù)，則分類準確率的計算公式為：

3.3 實驗結(jié)果分析

使用SVM 算法評估發(fā)布數(shù)據(jù)的可用性，分類變量為salary 屬性，將Adult 數(shù)據(jù)集的80%作為訓練集，20%作為測試集。實驗采用交叉驗證比較PrivBayes 與CSAPrivBayes算法的平均誤分類率，結(jié)果如圖2 所示。

由圖2 可以看出，隨著隱私預算的增加，加入的噪聲變小，數(shù)據(jù)的可用性變好，兩種算法的誤分類率均呈下降趨勢。然而，CSAPrivBayes 算法考慮了屬性敏感程度，合理分配隱私預算，誤分類率降至15%，遠低于PrivBayes 算法，在數(shù)據(jù)可用性方面也表現(xiàn)更佳。

采用分類準確率評估PrivBayes 與CSAPrivBayes 算法的貝葉斯網(wǎng)絡(luò)質(zhì)量，取k值為3，ε值為1.6，跟隨數(shù)據(jù)量的變化比較兩種算法的表現(xiàn)。如圖3 所示，通過PrivBayes 和CSAPrivBayes 兩種算法構(gòu)建了不同的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)，隨著訓練數(shù)據(jù)量的增加，兩種貝葉斯網(wǎng)絡(luò)的分類準確率均逐步提高。CSAPrivBayes 算法根據(jù)屬性結(jié)點的重要程度確定首選結(jié)點，分類準確率達到84%，構(gòu)建的貝葉斯網(wǎng)絡(luò)質(zhì)量優(yōu)于PrivBayes 算法。

Fig.2 Comparison of attribute misclassification rate of the two algorithms on Adult dataset圖2 Adult 數(shù)據(jù)集上兩種算法的錯誤分類率比較

Fig.3 Accuracy comparison of the two algorithms on Adult dataset with ε=1.6圖3 ε=1.6 時兩種算法在Adult 數(shù)據(jù)集上的準確率比較

4 結(jié)語

為解決PrivBayes 算法隨機選擇首選結(jié)點與無法合理分配隱私預算的問題，本文提出一種改進的隱私數(shù)據(jù)發(fā)布方法CSAPrivBayes。其通過對屬性結(jié)點添加權(quán)重值確定首選機制，根據(jù)關(guān)聯(lián)敏感屬性程度分配隱私預算實現(xiàn)個性化隱私保護。實驗結(jié)果表明，CSAPrivBayes 算法可以提高所構(gòu)建貝葉斯網(wǎng)絡(luò)的精度以及合成數(shù)據(jù)的可用性。在后續(xù)研究中，可通過使用不同的啟發(fā)式算法構(gòu)建貝葉斯網(wǎng)絡(luò)，進一步優(yōu)化CSAPrivBayes 算法的性能。