基于屬性分割的差分隱私異構(gòu)多屬性數(shù)據(jù)發(fā)布①

張小玉,沈國華,3,楊 陽

1(南京航空航天大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,南京 211106)

2(南京航空航天大學(xué) 高安全系統(tǒng)的軟件開發(fā)與驗證技術(shù)工業(yè)和信息化部重點實驗室,南京 211106)

3(南京大學(xué) 軟件新技術(shù)與產(chǎn)業(yè)化協(xié)同創(chuàng)新中心,南京 210093)

1 引言

近年來,互聯(lián)網(wǎng)應(yīng)用的逐步普及,帶來便利的同時,大量數(shù)據(jù)信息通過個人用戶、企業(yè)單位、研究機(jī)構(gòu)等源源不斷地產(chǎn)生.對產(chǎn)生的數(shù)據(jù)進(jìn)行數(shù)據(jù)分析,挖掘事物潛在的關(guān)聯(lián),再反饋給互聯(lián)網(wǎng)應(yīng)用商,可以為大眾提供更好的服務(wù).然而,這些數(shù)據(jù)中不乏個人隱私數(shù)據(jù),諸如醫(yī)療信息、金融信息、軌跡數(shù)據(jù)等,直接向外界發(fā)布原始數(shù)據(jù)存在著巨大的隱私泄露風(fēng)險.因此,對外發(fā)布數(shù)據(jù)時,需要采取一些隱私保護(hù)措施來保障數(shù)據(jù)安全.

K-匿名[1]及其相關(guān)擴(kuò)展L-Diversity[2]、T-closeness[3]是隱私保護(hù)的重要方法,其主要思想是將待發(fā)布數(shù)據(jù)劃分為多個等價類,等價類內(nèi)的k個實體無法相互區(qū)分,通過限制數(shù)據(jù)發(fā)布實現(xiàn)數(shù)據(jù)隱私保護(hù).然而,一旦攻擊者具有相當(dāng)?shù)谋尘爸R,K-匿名就無法提供很好的隱私保護(hù)效果,而且無法就其隱私保護(hù)程度進(jìn)行定量分析.差分隱私[4-9]作為一種嚴(yán)格可證的新興隱私保護(hù)模型,其前提是假設(shè)數(shù)據(jù)攻擊者具有的背景知識最大化.通過向輸出中添加隨機(jī)擾動,盡可能減小單個記錄對輸出的影響,保證攻擊者無法通過觀察不同的輸出結(jié)果重構(gòu)真實的數(shù)據(jù)信息,實現(xiàn)了單個記錄是否參與數(shù)據(jù)集的不可區(qū)分性.

從已有的研究可以看出,差分隱私在低維數(shù)據(jù)發(fā)布方面做了諸多努力,但在實際場景中,更為常見的卻是多屬性數(shù)據(jù)集,即高維數(shù)據(jù)集.如果將以往的低維數(shù)據(jù)發(fā)布算法直接應(yīng)用于多屬性數(shù)據(jù)發(fā)布,存在查詢敏感度大、隱私預(yù)算消耗過快等問題,導(dǎo)致數(shù)據(jù)發(fā)布效用低.

針對高維數(shù)據(jù)發(fā)布場景,常見方法有: 1)根據(jù)樹結(jié)構(gòu)劃分高維數(shù)據(jù)集,通過平衡分區(qū)的近似誤差和數(shù)據(jù)的擾動誤差來提高數(shù)據(jù)發(fā)布精度; 2)通過構(gòu)建數(shù)據(jù)集的概率圖模型計算屬性間的條件分布,通過噪聲條件分布近似原始數(shù)據(jù)集的聯(lián)合分布,以此生成新的合成數(shù)據(jù)集,避免直接對原始數(shù)據(jù)擾動產(chǎn)生巨大的擾動誤差; 3)利用數(shù)據(jù)降維技術(shù),將高維數(shù)據(jù)轉(zhuǎn)化成近似的低維數(shù)據(jù),對轉(zhuǎn)化后的低維數(shù)據(jù)添加噪聲擾動,減少擾動噪聲量.

在利用樹結(jié)構(gòu)發(fā)布高維數(shù)據(jù)集的研究中,文獻(xiàn)[10]借助細(xì)粒度單元劃分和kd-樹劃分兩種分區(qū)策略,實現(xiàn)了差分隱私多維直方圖發(fā)布.文獻(xiàn)[11]利用kd-樹和quad-tree 設(shè)計混合數(shù)據(jù)結(jié)構(gòu)實現(xiàn)多維數(shù)據(jù)劃分,從而減少了注入的噪聲量.文獻(xiàn)[12]提出了差分隱私泛化數(shù)據(jù)發(fā)布算法DiffGen,通過構(gòu)建決策樹的過程完成數(shù)據(jù)的差分隱私保護(hù).基于概率圖模型的研究也有所成果,文獻(xiàn)[13]提出數(shù)據(jù)發(fā)布方案PrivBayes,該方案通過構(gòu)建原始數(shù)據(jù)集的貝葉斯網(wǎng)絡(luò)模型,分析原始數(shù)據(jù)屬性之間的依賴關(guān)系,學(xué)習(xí)提取近似噪聲條件分布,采樣生成新的合成數(shù)據(jù)集.文獻(xiàn)[14] 提出聯(lián)合樹算法Jtree,根據(jù)樣本數(shù)據(jù)屬性之間的關(guān)聯(lián)構(gòu)建依賴關(guān)系圖,結(jié)合聯(lián)合樹的推理基礎(chǔ),從邊緣關(guān)系圖中學(xué)習(xí)一組噪聲邊緣表,以此近似原始數(shù)據(jù)集的聯(lián)合分布.通過數(shù)據(jù)降維來近似高維數(shù)據(jù)發(fā)布的研究中,文獻(xiàn)[15,16] 利用主成分分析技術(shù)識別高維數(shù)據(jù)的近似低維,實現(xiàn)了高維數(shù)據(jù)向低維的轉(zhuǎn)化,并基于低維數(shù)據(jù)實現(xiàn)差分隱私保護(hù).文獻(xiàn)[17]提出了差分隱私數(shù)據(jù)發(fā)布算法DPPro,該算法利用隨機(jī)投影技術(shù),完成高維數(shù)據(jù)在低維上的映射,保證了高維數(shù)據(jù)發(fā)布效用.文獻(xiàn)[18]提出PriView方法,通過構(gòu)建一組含噪聲擾動的低維View 視圖,提取 α-邊際分布,生成合成數(shù)據(jù)集.

然而,前文提到的各種方法對不同屬性的隱私保護(hù)處理大多隱含地假設(shè)同構(gòu)性,即不考慮屬性數(shù)據(jù)敏感性的異構(gòu),不同屬性的隨機(jī)干擾程度均相同.由于不同屬性攜帶的信息量不同,從而對攻擊者推理目標(biāo)對象隱私信息的貢獻(xiàn)不同,即隱私泄露風(fēng)險與屬性敏感性呈正相關(guān).例如,性別屬性只有兩個屬性值,與年齡屬性相比,攜帶的信息量更少,對目標(biāo)對象的刻畫程度較淺,對攻擊者推理敏感信息的貢獻(xiàn)較少,需要的隱私保護(hù)強(qiáng)度相對較低,相應(yīng)的屬性敏感性也就較低.不考慮屬性信息量差異帶來的敏感性異構(gòu),會導(dǎo)致沒有充分保護(hù)高敏感屬性數(shù)據(jù),或者過度丟失低敏感屬性數(shù)據(jù)的信息.

文獻(xiàn)[19]提出了一種加權(quán)貝葉斯網(wǎng)絡(luò)數(shù)據(jù)發(fā)布方法,雖然該方法是根據(jù)屬性的多樣性分配權(quán)重,但其目標(biāo)是借助屬性權(quán)重構(gòu)建更好的貝葉斯網(wǎng)絡(luò).文獻(xiàn)[20,21]均在基于貝葉斯網(wǎng)絡(luò)的數(shù)據(jù)發(fā)布算法中引入屬性聚類,以屬性關(guān)聯(lián)強(qiáng)弱分割屬性集,在減少隱私預(yù)算分割次數(shù)的基礎(chǔ)上提高算法計算效率.然而,兩者在隱私預(yù)算的分配上依然采取等分措施,沒有兼顧屬性敏感性差異.

針對已有方法的不足之處,本文提出了一種基于屬性分割的差分隱私異構(gòu)多屬性數(shù)據(jù)發(fā)布算法HMPriv-Bayes (heterogeneous multi-attribute private data publishing via Bayesian networks),主要貢獻(xiàn)包括以下3 個方面:

1)根據(jù)屬性之間的關(guān)聯(lián)程度,引入最大信息系數(shù)量化屬性之間的相關(guān)關(guān)系,設(shè)計滿足差分隱私的譜聚類算法分割屬性集,能在一定程度上縮減貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)空間,提高算法計算效率.

2)針對構(gòu)建貝葉斯網(wǎng)絡(luò)隨機(jī)選取首個屬性可能降低數(shù)據(jù)發(fā)布質(zhì)量的問題,以屬性信息熵為權(quán)重選擇屬性,盡可能提高數(shù)據(jù)發(fā)布質(zhì)量,保留數(shù)據(jù)實用價值.

3)考慮到屬性攜帶的信息量的不同,基于貝葉斯網(wǎng)絡(luò)提取屬性條件分布時,以屬性歸一化風(fēng)險熵為權(quán)重分配隱私預(yù)算,實現(xiàn)異構(gòu)多屬性保護(hù).

2 基礎(chǔ)知識

2.1 差分隱私

差分隱私(differential privacy,DP)保護(hù)模型保證在數(shù)據(jù)集中對一條記錄進(jìn)行增、刪、改操作后,查詢返回的擾動輸出沒有明顯差異,以至于攻擊者不能推斷出目標(biāo)記錄是否在發(fā)布的數(shù)據(jù)集中,即數(shù)據(jù)集中單個記錄對輸出的影響有限,從而實現(xiàn)保護(hù)個體隱私.

定義1.ε-差分隱私[4].設(shè)D1和D2為任意兩個相鄰數(shù)據(jù)集,即它們彼此相差1 條記錄,Range(M)是隨機(jī)算法M的取值范圍,若算法M在數(shù)據(jù)集D1和D2上的任意輸出S∈Range(M),滿足:

則稱算法M滿足ε-差分隱私.其中,隱私預(yù)算ε與隱私保護(hù)程度呈負(fù)相關(guān),與隱私泄露風(fēng)險呈正相關(guān).Pr(M(D1)∈S)和Pr(M(D2)∈S)表示算法M在數(shù)據(jù)集D1和D2上輸出為S的概率.

任何滿足定義1 的噪音機(jī)制都可以視為差分隱私機(jī)制,差分隱私中常見噪音機(jī)制有Laplace 機(jī)制[22]和指數(shù)機(jī)制[23],其噪聲擾動大小與隨機(jī)函數(shù)的敏感度以及隱私預(yù)算參數(shù)密切相關(guān).

定義2.全局敏感度[5].設(shè)查詢函數(shù)f:D→Rn,f的全局敏感度定義如下:

其中,D1和D2表示任意兩個相鄰數(shù)據(jù)集,全局敏感度Δf由查詢函數(shù)f決定.

定義3.Laplace 機(jī)制[22].對任意數(shù)據(jù)集D和查詢函數(shù)f:D→Rn,若算法M的輸出結(jié)果滿足:

則算法M實現(xiàn)了ε-差分隱私.其中,Lap(Δf/ε)表示添加的噪聲量,噪聲量與 Δf成正比,與ε成反比.Laplace機(jī)制主要用于處理數(shù)值型數(shù)據(jù).

定義4.指數(shù)機(jī)制[23].對任意數(shù)據(jù)集D,給定評分函數(shù)u:(D,r)→R,若算法M滿足:

則算法M實現(xiàn)了ε-差分隱私.其中,Δu為u(D,r)的全局敏感度,Pr[r∈O]為評分函數(shù)u輸出r的概率,評分越高,r被輸出的概率越高.指數(shù)機(jī)制通常用于處理非數(shù)值型數(shù)據(jù).

對于一組滿足差分隱私的隨機(jī)獨立算法,差分隱私的串行組合性質(zhì)和并行組合性質(zhì)[24]可以用于證明整體算法滿足差分隱私保護(hù).

性質(zhì)1.串行組合[24].給定數(shù)據(jù)集D和D上1 組隨機(jī)獨立算法M1(D),M2(D),···,Mm(D),其中每個算法Mi(D)滿足εi-差分隱私,則M={M1,M2,···,Mm}滿足-差分隱私.

串行組合表明,當(dāng)一系列差分隱私機(jī)制應(yīng)用于同一數(shù)據(jù)集時,隱私預(yù)算和噪聲數(shù)量呈線性累積.

性質(zhì)2.并行組合[24].給定數(shù)據(jù)集D,將D分割成m個互不相交的子集D={D1,D2,···,Dm}.每個子集中的隨機(jī)獨立算法M1(D1),···,Mm(Dm)均滿足εi-差分隱私,則組合算法M={M1,M2,···,Mm}滿足max(εi)-差分隱私.

并行組合表明,當(dāng)一系列差分隱私機(jī)制應(yīng)用于數(shù)據(jù)集的不同子集時,隱私保護(hù)的程度取決于 εi的最大值.

2.2 譜聚類

譜聚類(spectral clustering,SC)[25]是利用圖論中的圖分割完成數(shù)據(jù)聚類的算法.它的主要思想是先將數(shù)據(jù)集映射成一張帶權(quán)無向圖,基于兩點之間的距離計算頂點相似度,通過最優(yōu)劃分準(zhǔn)則分割圖中結(jié)點,最大化子圖內(nèi)部的相似度,實現(xiàn)數(shù)據(jù)聚類.標(biāo)準(zhǔn)的譜聚類算法實現(xiàn)流程如算法1 所示.

算法1.譜聚類算法輸入: 數(shù)據(jù)集,降維后的維度k1,聚類方法,簇數(shù)量k C(c1,c2,···,ck)D={x1,x2,···,xn}輸出: 簇劃分1.計算n×n 的相似矩陣S: ;wij=exp sij=‖xi-x j‖2)2.根據(jù)相似矩陣S 構(gòu)建鄰接矩陣W:(-sij 2σ2 3.計算n×n 的度矩陣B: ;bij=■■■■■■■■■∑dk=1 wik,i=j 0,i≠j L=B-1/2(B-W)B-1/2 4.計算并標(biāo)準(zhǔn)化拉普拉斯矩陣;5.計算L 最小的k1 個特征值以及各自對應(yīng)的特征向量;6.將特征向量組成矩陣并按行進(jìn)行標(biāo)準(zhǔn)化,最終組成n×k1 維的特征矩陣U;7.將U 中的每一行作為一個k1 維的樣本,按照輸入的聚類方式進(jìn)行聚類,聚類維數(shù)為k;C(c1,c2,···,ck)u1,u2,···,uk1 8.返回簇劃分.

在本文中,譜聚類主要用于屬性聚類,即根據(jù)屬性之間的關(guān)聯(lián)程度分割屬性集.本文選用最大信息系數(shù)(maximal information coefficient,MIC)[26]度量屬性之間關(guān)聯(lián)程度.在此之前,互信息是常用的屬性關(guān)聯(lián)度量手段,然而,互信息需要考慮連續(xù)屬性的離散化,而且不同數(shù)據(jù)集上的互信息計算結(jié)果無法相互比較.MIC利用網(wǎng)格劃分屬性值域,結(jié)合屬性互信息,可以更準(zhǔn)確地識別出大數(shù)據(jù)集中屬性間的線性或非線性關(guān)系,以及非函數(shù)依賴關(guān)系.

定義5.最大信息系數(shù)[26].給定屬性X,Y和有序?qū)Γ糰,b＞,樣本數(shù)量為N,將當(dāng)前二維空間在x,y方向上劃分為a×b的網(wǎng)格G,將屬性數(shù)據(jù)點離散落入網(wǎng)格G中,屬性X和Y的最大信息系數(shù)計算如下:

其中,B為網(wǎng)格劃分a×b的上限值,通常取值N0.6或N0.55,I(X,Y)為屬性X和Y的互信息值,具體計算如下:

其中,Pr(xi,yj)表示屬性X,Y取值xi,yj的聯(lián)合分布.

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

貝葉斯網(wǎng)絡(luò)(Bayesian network)是常用的概率圖模型之一,用來表示一組隨機(jī)變量(屬性)之間的依賴關(guān)系.形式上,貝葉斯網(wǎng)絡(luò)N可以表示為N=(G,θ).其中,G表示有向無環(huán)圖,圖中節(jié)點代表隨機(jī)變量,節(jié)點之間的有向邊代表隨機(jī)變量之間的依賴關(guān)系.在G中,若存在一條從Xj到Xi的有向邊,則稱Xj為Xi的父節(jié)點.Xi的所有父節(jié)點構(gòu)成Xi的父節(jié)點集合,表示為θ表示N的參數(shù)集合,θ包含每個節(jié)點Xi的條件分布,表示為對于一個包含屬性集X={X1,X2,···,Xd}的貝葉斯網(wǎng)絡(luò)N,N可以近似表示X的聯(lián)合概率分布,具體為圖1 表示包含屬性節(jié)點{X1,X2,···,X5}的貝葉斯網(wǎng)絡(luò),圖中所有屬性節(jié)點的聯(lián)合概率分布為Pr(X1,X2,X3,X4,X5)=Pr(X1)Pr(X2|X1)Pr(X3|X2)Pr(X4|X1,X2)Pr(X5|X3,X4).

圖1 含5 個節(jié)點的貝葉斯網(wǎng)絡(luò)示例

3 基于屬性分割的差分隱私異構(gòu)多屬性數(shù)據(jù)發(fā)布

3.1 HMPrivBayes 算法概述

HMPrivBayes 算法的整體流程如圖2 所示,包括4 個階段: 屬性聚類劃分、構(gòu)建差分隱私貝葉斯網(wǎng)絡(luò)、生成屬性加噪條件分布、生成待發(fā)布數(shù)據(jù)集.為了方便描述,本文假設(shè)所有屬性均是二進(jìn)制屬性.對于非二進(jìn)制屬性,利用文獻(xiàn)[13]提出的等寬法將非二進(jìn)制屬性轉(zhuǎn)化成一組二進(jìn)制屬性.由于等寬法的轉(zhuǎn)化過程只依賴非二進(jìn)制屬性的值域,且屬性的值域是公開信息,不涉及隱私數(shù)據(jù).因此,屬性轉(zhuǎn)化過程不存在隱私泄露問題.

圖2 HMPrivBayes 算法流程圖

HMPrivBayes 算法的實現(xiàn)過程如算法2 所示.

算法2.HMPrivBayes 算法輸入: 數(shù)據(jù)集,屬性集,屬性簇個數(shù)k,隱私預(yù)算ε輸出: 數(shù)據(jù)集D 滿足差分隱私的合成數(shù)據(jù)集D′D={x1,x2,···,xn}X={X1,X2,···,Xd}1.初始化D′= ;2.分配隱私預(yù)算ε1+ε2+ε3=ε;?3.執(zhí)行算法3,返回聚類結(jié)果;D={D1,···,Dk}C={C1,C2,···,Ck}4.依據(jù)C 劃分原始數(shù)據(jù)集;5.for i=1 to k do執(zhí)行算法4,求貝葉斯網(wǎng)絡(luò)Ni;P*iD′i D′基于 計算Ni 的帶噪聯(lián)合分布,采樣得到合成數(shù)據(jù)集 ,并加入 ;P*i執(zhí)行算法5,求帶噪條件分布 ;end for D′6.返回 .

3.2 差分隱私譜聚類算法

譜聚類算法是根據(jù)數(shù)據(jù)點之間相似性程度進(jìn)行數(shù)據(jù)集聚類,對于關(guān)聯(lián)程度不高的屬性對,其相似值相應(yīng)較小,從而分割至不同的子集.本文采用最大信息系數(shù)作為屬性之間關(guān)聯(lián)程度衡量指標(biāo),MIC 不僅能高效檢測大數(shù)據(jù)集中不同類型屬性之間關(guān)聯(lián)關(guān)系,而且不需要進(jìn)行歸一化處理.選用K-means++聚類算法實現(xiàn)特征矩陣U的聚類劃分,K-means++算法選擇初始的聚類中心時,要求各聚類中心之間的相互距離要盡可能的遠(yuǎn).初始點選擇的優(yōu)化,使得K-means++算法在聚類結(jié)果準(zhǔn)確性上有較大提升.差分隱私譜聚類算法DPSC如算法3 所示.

算法3.DPSC 算法輸入: 數(shù)據(jù)集,屬性集,尺度參數(shù) ,降維后的維度 ,聚類后的維度,隱私預(yù)算X C′={C1,C2,···,Ck}輸出: 屬性集 聚類劃分結(jié)果D={x1,x2,···,xn}X={X1,X2,···,Xd}σ k1kε1(Δm·d(d-1)■■■■■■■■■)1.計算的相似矩陣:2.執(zhí)行算法1 的步驟2-步驟6;d×dS sij=MIC(Xi,Xj)+Lap ,i≠j 0,i=j ε1·(2images/BZ_231_2132_2125_2223_2167.png);3.使用K-means++算法對新樣本點進(jìn)行聚類劃分得到劃分結(jié)果 ;C′={C1,C2,···,Ck}4.返回屬性聚類結(jié)果.U={u1,u2,···,uk1}C

由于在計算屬性關(guān)聯(lián)程度時涉及到了原始數(shù)據(jù)集D的使用,為了保護(hù)數(shù)據(jù)集中的數(shù)據(jù)隱私不被泄露,采用Laplace 機(jī)制對計算結(jié)果添加噪聲.

首先計算屬性間的最大信息系數(shù)的全局敏感度Δm,由式(5)可知,MIC 的計算取決于屬性間的互信息,故計算相似矩陣S的全局敏感度Δm=ΔI.由文獻(xiàn)[13]可知,

從算法3 可以看出, Laplace 機(jī)制是通過多次擾動加噪過程實現(xiàn)的, 每次加噪都需要消耗部分隱私預(yù)算ε1. 由定義可知, 相似矩陣S是一個對稱矩陣, 且對角線元素不需要計算, 所以計算d(d-1)/2個不同元素的值就可以得到矩陣S. 每次訪問數(shù)據(jù)集D可以計算對屬性對之間的MIC, 因此, 對數(shù)據(jù)集D的訪問次數(shù), 即擾動總次數(shù)為d(d-1)/(2), 每次擾動添加的噪聲量為Lap((Δm·d(d-1))/(ε1·(2))). 由定義3 和性質(zhì)1 可知, 算法3 滿足 ε1-差分隱私.

3.3 差分隱私貝葉斯網(wǎng)絡(luò)算法

在基于貝葉斯網(wǎng)絡(luò)構(gòu)建數(shù)據(jù)發(fā)布模型的現(xiàn)有研究中,大多以文獻(xiàn)[13]中的PrivBayes 為參照進(jìn)一步改進(jìn)貝葉斯網(wǎng)絡(luò)的構(gòu)建設(shè)計發(fā)布算法[19-21].由于PrivBayes在構(gòu)建貝葉斯網(wǎng)絡(luò)時,隨機(jī)選取首個屬性加入父節(jié)點集合,這樣構(gòu)建的貝葉斯網(wǎng)絡(luò)不一定能真實反映原始數(shù)據(jù)集.與此同時,通過枚舉的方式選取互信息最大的對會造成大量無意義的計算,影響貝葉斯網(wǎng)絡(luò)的構(gòu)建速度.基于此,本文提出改進(jìn)的貝葉斯網(wǎng)絡(luò)構(gòu)建算法IBayes,IBayes 引入信息熵作為選取首個屬性的依據(jù),同時縮減候選屬性的對,以此達(dá)到快速構(gòu)建“最合適”的貝葉斯網(wǎng)絡(luò)的目的.IBayes 的實現(xiàn)過程如算法4 所示.

算法4.IBayes 算法輸入: 數(shù)據(jù)子集,屬性子集,最大父節(jié)點數(shù),隱私預(yù)算DiNi Di={x1,x2,···,xn}Ci={X1,X2,···,X|Ci|}l ε2輸出: 數(shù)據(jù)子集 的貝葉斯網(wǎng)絡(luò)1.初始化,;CiXj(X j,?)Ni X jV Ni=?V=?2.使用指數(shù)機(jī)制從 中選取信息熵最大的屬性 ,將加入 ,將 加入 ;t=2 |C?|3.for to do Ω=?初始化;Xs∈CiV for V′=V令;S i(Xs,Xc)=0Xc∈V′If 且XcV′Πs∈■■■■■■■■V′將 從 中移除,且;(Xs,∏s)Ω將加入 ;l■■■■■■■■end for使用指數(shù)機(jī)制從 中選擇互信息最大的加入 ,同時 加入 ;Ω(Xt,Πt)NiXtV end for 4.返回 .Ni

信息熵是對信息不確定性的度量,與信息的不確定性呈正相關(guān).信息熵越大,攜帶的信息量越多,能更多地反映出數(shù)據(jù)的多樣性,增加數(shù)據(jù)的實用價值,反之亦然.因此,引入信息熵作為選取首個屬性的依據(jù)是合理的.

對于數(shù)據(jù)集Di中的每個屬性Xj,其信息熵H(Xj)計算如下:

根據(jù)式(7)可知,當(dāng)取不同值的概率相等時信息熵最大,即Xj中有n個不同的取值時H(Xj)取得最大值,為

通過圖3 的實例可以說明屬性信息熵的最大差異.

圖3 信息熵差異實例

根據(jù)圖3(a)取值概率分布計算H(Xj)的值為0,通過圖3(b)計算H(Xj)的值為.在此基礎(chǔ)上,可以得出屬性信息熵的全局敏感度ΔH為:

PrivBayes 通過枚舉選擇互信息最大的屬性對時,候選對越多,對算法的時間復(fù)雜的影響越大.因此,本文在求解候選屬性的父節(jié)點集時,篩選關(guān)聯(lián)程度弱的屬性對,減少對互信息的計算量.篩選操作通過關(guān)聯(lián)矩陣Si實現(xiàn).從相似矩陣S中提取出相關(guān)屬性子集的最大信息系數(shù),根據(jù)式(9)得到Si:

IBayes算法使用指數(shù)機(jī)制選取加入Ni中的首個屬性節(jié)點,同時從 Ω中選擇對加入Ni,評分函數(shù)分別采用屬性信息熵和互信息.由于Δu=ΔI=ΔH,除選取加入Ni中的首個屬性節(jié)點外,選擇需要執(zhí)行|Ci|-1次,故將 ε2平均分為|Ci|份.因此,結(jié)合差分隱私指數(shù)機(jī)制,選擇的概率表達(dá)式如式(10):

IBayes 算法最終輸出一個貝葉斯網(wǎng)絡(luò)Ni,除了使用指數(shù)機(jī)制選取首個屬性節(jié)點和對之外,其他步驟均無需訪問原始數(shù)據(jù)集D.在構(gòu)建貝葉斯網(wǎng)絡(luò)之前,HMPrivBayes 算法已經(jīng)通過算法3 將原始數(shù)據(jù)集D劃分為k個獨立數(shù)據(jù)子集D1,···,Dk.根據(jù)定義4 和性質(zhì)1,指數(shù)機(jī)制exp(ε2u(Di,r)/(2|Ci|Δu))滿足 ε2-差分隱私,因此IBayes 算法滿足 ε2-差分隱私.

3.4 差分隱私異構(gòu)條件分布計算

通過貝葉斯網(wǎng)絡(luò)計算屬性的聯(lián)合分布,生成合成數(shù)據(jù)集,可以近似原始數(shù)據(jù)集.盡管貝葉斯網(wǎng)絡(luò)的構(gòu)建過程滿足差分隱私保護(hù),但仍存在隱私泄露的可能.因此,需要對計算出來的屬性聯(lián)合分布添加噪聲擾動,以進(jìn)一步保護(hù)隱私數(shù)據(jù).之前的研究均通過均分隱私預(yù)算實現(xiàn)聯(lián)合分布噪聲擾動,這種方式?jīng)]有考慮到屬性敏感性差異.屬性攜帶的信息量越多,幫助攻擊者推出目標(biāo)信息的貢獻(xiàn)越大,也就意味著它對外發(fā)布的敏感性越高.基于此,本文提出差分隱私異構(gòu)條件分布計算算法HnoisyConditionals,具體實現(xiàn)過程如算法5所示.

算法5.HnoisyConditionals 算法輸入: 數(shù)據(jù)集,貝葉斯網(wǎng)絡(luò) ,隱私預(yù)算NiP*i輸出: 根據(jù) 生成的帶噪聲的條件分布集Di={x1,x2,···,xn}Niε3 P*i=?l′=min(|Ci|-1,d)1.初始化,令;j=l′+1 |Ci|2.for to do X jPr(X j,∏)構(gòu)建 的聯(lián)合分布;j■■■■■■■■■■2 Lap∑|Ci|j=l′+1 exp(-OE j)■■■■■■■■■■nε3×加入拉普拉斯噪聲,實現(xiàn)差分隱私;Pr*(X j,∏j)Pr*(X j,∏)exp(-OE j)j中的負(fù)值歸0 并正常化;Pr*(X j,∏j)Pr*(X j|∏j)P*i從中提取并加入 ;設(shè)end for j=1l′3.for to do Pr*(Xl′+1,∏l′+1)Pr*(X j|∏j)P*i從中提取加入 ;end for P*i 4.返回 .

根據(jù)式(7),歸一化風(fēng)險熵計算公式如下:

在算法5 中,向聯(lián)合分布注入噪聲不再采取均分策略,而是以歸一化風(fēng)險熵為權(quán)重分配隱私預(yù)算.由文獻(xiàn)[13]可知,聯(lián)合分布全局敏感度為 2/n.因此,每次對聯(lián)合分布添加的拉普拉斯噪聲大小為:

其中,屬性歸一化風(fēng)險熵OEj越大,屬性敏感性越高,需要的隱私保護(hù)強(qiáng)度越大,分配的隱私預(yù)算也就越小.由定義3 和性質(zhì)1 可知,算法5 滿足 ε3-差分隱私.

3.5 隱私分析

定理1.HMPrivBayes 算法滿足ε-差分隱私.

證明: 在HMPrivBayes 的整個執(zhí)行過程中,其中有3 步涉及原始數(shù)據(jù)集的訪問,分別是屬性分割、構(gòu)建差分隱私貝葉斯網(wǎng)絡(luò)和提取屬性噪聲條件分布,下面分別討論這3 步的隱私保護(hù)強(qiáng)度.

對于屬性分割,需要重復(fù)訪問數(shù)據(jù)集D計算屬性對的MIC,每次訪問數(shù)據(jù)集D可以計算對屬性對的MIC,相似矩陣S中有d(d-1)/2個不同的MIC 值需要計算,因此,需訪問d(d-1)/(2)次數(shù)據(jù)集D.MIC計算的敏感度為Δm,故每次擾動添加的噪聲量為Lap((Δm·d(d-1))/(ε1·(2))),進(jìn)而屬性分割滿足ε1-差分隱私.

在貝葉斯網(wǎng)絡(luò)構(gòu)建階段,需要借助指數(shù)機(jī)制exp(ε2H(Xj)/(2|Ci|ΔH))從數(shù)據(jù)子集Di中選取加入Ni的首個屬性節(jié)點.指數(shù)機(jī)制用于選擇互信息最大的對加入Ni,執(zhí)行|Ci|-1次,因此貝葉斯網(wǎng)絡(luò)構(gòu)建滿足 ε2-差分隱私.

從貝葉斯網(wǎng)絡(luò)Ni中提取屬性條件分布時,需要往|Ci|-l′個屬性聯(lián)合分布中添加噪聲擾動,進(jìn)一步保護(hù)數(shù)據(jù)隱私.為了兼顧屬性敏感性的差異,隱私預(yù)算根據(jù)屬性Xj的歸一化風(fēng)險熵OEj異構(gòu)分配,添加的噪聲量為,其中聯(lián)合分布計算的敏感度為 2/n.因此,屬性條件分布計算滿足 ε3-差分隱私.

綜上,HMPrivBayes 算法滿足 ε-差分隱私,其中ε1+ε2+ε3=ε.

4 實驗評估

4.1 實驗設(shè)置

本次實驗使用Python 編程語言來實現(xiàn)所有的方法,其中貝葉斯網(wǎng)絡(luò)模型部分的實現(xiàn)參考了Zhang 等人[13]論文的實驗相關(guān)代碼.實驗的硬件環(huán)境為AMD Ryzen7 4800H (2.90 GHz),操作系統(tǒng)為Windows 10(64 位),內(nèi)存為16 GB.

實驗采用兩個公開可用的數(shù)據(jù)集Adult[27]和Big5[28].其中,Adult 為美國人口普查數(shù)據(jù)集,包含45 222 條個體信息記錄,每條記錄包含15 個屬性.Big5是包含19 719條人口普查記錄的信息集合,每條記錄包含57 個屬性.利用等寬法完成屬性轉(zhuǎn)化后,二進(jìn)制屬性的數(shù)量分別為52 和175.兩個數(shù)據(jù)集的詳細(xì)信息如表1 所示.

表1 數(shù)據(jù)集屬性信息描述

對于這兩個數(shù)據(jù)集,隱私預(yù)算分配策略為ε1=a1/aε,ε2=a2/aε,ε3=a3/aε,其中a=a1+a2+a3,屬性分類簇個數(shù)k默認(rèn)值為3,貝葉斯網(wǎng)絡(luò)的最大入度數(shù)l默認(rèn)值為3.

4.2 評價指標(biāo)

本文通過 α-邊際分布[29]和SVM (support vector machine)分類[30]來評估算法的性能.實驗選取2-邊際分布和3-邊際分布作為 α-邊際分布評估的實例,通過計算生成的噪聲邊際分布和原始邊際分布的平均變量距離(average variation distance,AVD)[31]確性.L1距離的一半:

其中,P(ω)和Q(ω)分別表示加噪前后的邊際分布,?表示邊際分布集合.

實驗通過度量SVM 分類的準(zhǔn)確性,分析生成的噪聲數(shù)據(jù)集的有效性.本組實驗在噪聲數(shù)據(jù)集上同時訓(xùn)練2 個分類器,通過分析合成數(shù)據(jù)集的其他屬性預(yù)測目標(biāo)屬性的分類結(jié)果.對于Adult 數(shù)據(jù)集,選取salary作為分類實例,預(yù)測個體每年收入是否超過50k.對于Big5 數(shù)據(jù)集,選取age 作為分類實例,預(yù)測個體年齡是否在50 歲以下.每個分類任務(wù),將合成數(shù)據(jù)集按照8:2 分為訓(xùn)練數(shù)據(jù)集和測試數(shù)據(jù)集,重復(fù)運行50 次,并記錄實驗結(jié)果的平均值.

4.3 實驗結(jié)果

本文將通過3 個不同的實驗來分析HMPrivBayes算法的可用性和高效性.為了更好地評估HMPrivBayes方案的性能,本節(jié)采用的對比算法包括: PrivSCBN、PrivBayes、Jtree、NoPrivacy.其中,PrivSCBN 算法[20]、PrivBayes 算法[13]均是基于貝葉斯網(wǎng)絡(luò)的數(shù)據(jù)發(fā)布算法,Jtree[14]是基于聯(lián)合樹的數(shù)據(jù)發(fā)布算法,NoPrivacy是HMPrivBayes 不添加噪聲擾動的數(shù)據(jù)發(fā)布情況.

第1 個實驗是為了驗證HMPrivBayes 算法的安全性,比較在不同記錄數(shù)量下,敏感屬性隱私泄露的可能性.在Adult 數(shù)據(jù)集原有的45 222 條記錄的基礎(chǔ)上,隨機(jī)產(chǎn)生54 778 條記錄,生成包含100 000 條記錄的數(shù)據(jù)集,并將salary 作為敏感屬性.由于隱私預(yù)算ε不是該實驗關(guān)心的變量,故將ε固定為0.2.實驗結(jié)果如圖4 所示,從圖中可以看出,隨著記錄數(shù)的增加隱私泄露概率逐漸下降,即攻擊者根據(jù)其他屬性信息推斷出salary 屬性值的概率逐漸下降,而且HMPrivBayes算法安全性高于PrivBayes 算法和PrivSCBN 算法.這是因為,HMPrivBayes 算法根據(jù)屬性敏感性決定隱私預(yù)算分配大小,能對多屬性數(shù)據(jù)發(fā)布提供更安全的隱私保護(hù).

圖4 數(shù)據(jù)安全性分析

第2 個實驗是對HMPrivBayes 算法數(shù)據(jù)性能的分析,圖5(a)-圖5(d)分別對比了在不同ε取值下,算法HMPrivBayes、PrivSCBN、PrivBayes、Jtree 的合成數(shù)據(jù)集的邊際分布與原始數(shù)據(jù)集邊際分布之間AVD 的變化.圖5(e)-圖5(f)顯示了算法HMPrivBayes、PrivSCBN、PrivBayes、Jtree 的合成數(shù)據(jù)集訓(xùn)練2 個分類器的誤分類率在不同ε取值下的變化趨勢.

圖5 算法HMPrivBayes、PrivSCBN、PrivBayes、Jtree 在不同隱私預(yù)算下的性能分析

可以看出,對于NoPrivacy,邊際分布之間的AVD和分類器的誤分類率均與隱私預(yù)算 ε的取值無關(guān),且NoPrivacy 的性能均優(yōu)于其他方法的性能.隨著隱私預(yù)算ε取值的增大,隱私保護(hù)強(qiáng)度下降,合成數(shù)據(jù)的兩項指標(biāo)越來越接近NoPrivacy 的情況,這符合差分隱私的規(guī)律.在多數(shù)情況下,HMPrivBayes 的性能均優(yōu)于PrivSCBN、PrivBayes、Jtree 的性能,僅當(dāng)隱私預(yù)算ε足夠大時,HMPrivBayes 與PrivSCBN 性能趨于接近.這說明本文提出的各種貝葉斯網(wǎng)絡(luò)改進(jìn)策略以及異構(gòu)屬性發(fā)布策略是有效的.

第3 個實驗是對HMPrivBayes 算法計算效率的分析,比較在貝葉斯網(wǎng)絡(luò)不同最大入度數(shù)l下,算法的整體運行時間.由于隱私預(yù)算ε不是該實驗關(guān)心的變量,故將ε固定為0.2.實驗結(jié)果如圖6 所示,隨著最大入度數(shù)l的增加,整體運行時間大幅上升.比較圖6(a)-圖6(b)可以看出,隨著屬性數(shù)目的增加,算法整體運行時間也大幅增加.不過,HMPrivBayes 的運行時間遠(yuǎn)低于PrivBayes 算法,而且屬性越多,兩者運行時間的差距越大,這說明HMPrivBayes 的效率得到了較好的提升.效率的提升一方面在于,HMPrivBayes 利用聚類算法分割屬性集,縮減了單個貝葉斯網(wǎng)絡(luò)的節(jié)點空間; 另一方面在于,借助屬性關(guān)聯(lián)強(qiáng)度,縮減了候選屬性對集合.

圖6 算法運行時間分析

5 結(jié)束語

針對差分隱私異構(gòu)多屬性數(shù)據(jù)發(fā)布問題,本文提出了一種基于屬性分割的異構(gòu)多屬性數(shù)據(jù)差分隱私發(fā)布方法HMPrivBayes.與已有多屬性數(shù)據(jù)發(fā)布算法不同的是,HMPrivBayes 基于屬性敏感性差異給予屬性數(shù)據(jù)相對應(yīng)的隱私保護(hù)強(qiáng)度,避免了多屬性數(shù)據(jù)隱私保護(hù)不均勻的問題,進(jìn)而提高數(shù)據(jù)可用性.與此同時,該方法通過引入屬性分割、改進(jìn)貝葉斯構(gòu)建過程等都實現(xiàn)了算法整體計算效率的提升.在不破壞屬性關(guān)聯(lián)的前提下,以屬性歸一化風(fēng)險熵為權(quán)重分配隱私預(yù)算,實現(xiàn)異構(gòu)多屬性數(shù)據(jù)發(fā)布.理論證明,HMPrivBayes 滿足ε-差分隱私.實驗結(jié)果表明,HMPrivBayes 方法在提升算法整體計算效率的基礎(chǔ)上,保證了數(shù)據(jù)發(fā)布的可用性在未來的研究中,我們將考慮基于差分隱私的分布式異構(gòu)多屬性數(shù)據(jù)發(fā)布,即如何在多方設(shè)置中實現(xiàn)異構(gòu)多屬性數(shù)據(jù)發(fā)布.