陳思陽(yáng)

（山東科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，山東青島 266590）

0 引言

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

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

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

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

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

1.1 差分隱私

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

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

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

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

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

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

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

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

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

2.1 PrivBayes 算法

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

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

（2）在擾動(dòng)概率分布階段，首先根據(jù)構(gòu)建的貝葉斯網(wǎng)絡(luò)計(jì)算屬性的聯(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）在隨機(jī)取樣階段，首先將第一個(gè)屬性結(jié)點(diǎn)按照屬性取值劃分概率區(qū)間，生成一個(gè)隨機(jī)數(shù)，根據(jù)其所在的取值區(qū)間確定X1的取樣值。對(duì)于剩余屬性結(jié)點(diǎn)，在給定父結(jié)點(diǎn)下按照屬性取值劃分聯(lián)合概率區(qū)間，再根據(jù)生成隨機(jī)數(shù)所在概率區(qū)間確定X的取樣值。

2.2 CSAPrivBayes 算法

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

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

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

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

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

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

（6）重復(fù)步驟（5）直至選擇出(d-1)個(gè)AP對(duì)。

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

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

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

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

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

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

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)環(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 編程語(yǔ)言實(shí)現(xiàn)，IDE 開發(fā)工具為Pycharm。使用美國(guó)人口普查數(shù)據(jù)集，隨機(jī)選擇24 000 條數(shù)據(jù)，其中選取6 個(gè)離散屬性，4 個(gè)連續(xù)屬性，具體信息如表1 所示。

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

3.2 評(píng)價(jià)指標(biāo)

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

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

3.3 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

4 結(jié)語(yǔ)

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