基于屬性分割的差分隱私異構多屬性數據發布①

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

1(南京航空航天大學 計算機科學與技術學院,南京 211106)

2(南京航空航天大學 高安全系統的軟件開發與驗證技術工業和信息化部重點實驗室,南京 211106)

3(南京大學 軟件新技術與產業化協同創新中心,南京 210093)

1 引言

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

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

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

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

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

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

文獻[19]提出了一種加權貝葉斯網絡數據發布方法,雖然該方法是根據屬性的多樣性分配權重,但其目標是借助屬性權重構建更好的貝葉斯網絡.文獻[20,21]均在基于貝葉斯網絡的數據發布算法中引入屬性聚類,以屬性關聯強弱分割屬性集,在減少隱私預算分割次數的基礎上提高算法計算效率.然而,兩者在隱私預算的分配上依然采取等分措施,沒有兼顧屬性敏感性差異.

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

1)根據屬性之間的關聯程度,引入最大信息系數量化屬性之間的相關關系,設計滿足差分隱私的譜聚類算法分割屬性集,能在一定程度上縮減貝葉斯網絡結構空間,提高算法計算效率.

2)針對構建貝葉斯網絡隨機選取首個屬性可能降低數據發布質量的問題,以屬性信息熵為權重選擇屬性,盡可能提高數據發布質量,保留數據實用價值.

3)考慮到屬性攜帶的信息量的不同,基于貝葉斯網絡提取屬性條件分布時,以屬性歸一化風險熵為權重分配隱私預算,實現異構多屬性保護.

2 基礎知識

2.1 差分隱私

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

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

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

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

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

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

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

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

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

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

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

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

串行組合表明,當一系列差分隱私機制應用于同一數據集時,隱私預算和噪聲數量呈線性累積.

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

并行組合表明,當一系列差分隱私機制應用于數據集的不同子集時,隱私保護的程度取決于 εi的最大值.

2.2 譜聚類

譜聚類(spectral clustering,SC)[25]是利用圖論中的圖分割完成數據聚類的算法.它的主要思想是先將數據集映射成一張帶權無向圖,基于兩點之間的距離計算頂點相似度,通過最優劃分準則分割圖中結點,最大化子圖內部的相似度,實現數據聚類.標準的譜聚類算法實現流程如算法1 所示.

算法1.譜聚類算法輸入: 數據集,降維后的維度k1,聚類方法,簇數量k C(c1,c2,···,ck)D={x1,x2,···,xn}輸出: 簇劃分1.計算n×n 的相似矩陣S: ;wij=exp sij=‖xi-x j‖2)2.根據相似矩陣S 構建鄰接矩陣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.計算并標準化拉普拉斯矩陣;5.計算L 最小的k1 個特征值以及各自對應的特征向量;6.將特征向量組成矩陣并按行進行標準化,最終組成n×k1 維的特征矩陣U;7.將U 中的每一行作為一個k1 維的樣本,按照輸入的聚類方式進行聚類,聚類維數為k;C(c1,c2,···,ck)u1,u2,···,uk1 8.返回簇劃分.

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

定義5.最大信息系數[26].給定屬性X,Y和有序對＜a,b＞,樣本數量為N,將當前二維空間在x,y方向上劃分為a×b的網格G,將屬性數據點離散落入網格G中,屬性X和Y的最大信息系數計算如下:

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

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

2.3 貝葉斯網絡

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

圖1 含5 個節點的貝葉斯網絡示例

3 基于屬性分割的差分隱私異構多屬性數據發布

3.1 HMPrivBayes 算法概述

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

圖2 HMPrivBayes 算法流程圖

HMPrivBayes 算法的實現過程如算法2 所示.

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

3.2 差分隱私譜聚類算法

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

算法3.DPSC 算法輸入: 數據集,屬性集,尺度參數 ,降維后的維度 ,聚類后的維度,隱私預算X C′={C1,C2,···,Ck}輸出: 屬性集 聚類劃分結果D={x1,x2,···,xn}X={X1,X2,···,Xd}σ k1kε1(Δm·d(d-1)■■■■■■■■■)1.計算的相似矩陣:2.執行算法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++算法對新樣本點進行聚類劃分得到劃分結果 ;C′={C1,C2,···,Ck}4.返回屬性聚類結果.U={u1,u2,···,uk1}C

由于在計算屬性關聯程度時涉及到了原始數據集D的使用,為了保護數據集中的數據隱私不被泄露,采用Laplace 機制對計算結果添加噪聲.

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

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

3.3 差分隱私貝葉斯網絡算法

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

算法4.IBayes 算法輸入: 數據子集,屬性子集,最大父節點數,隱私預算DiNi Di={x1,x2,···,xn}Ci={X1,X2,···,X|Ci|}l ε2輸出: 數據子集 的貝葉斯網絡1.初始化,;CiXj(X j,?)Ni X jV Ni=?V=?2.使用指數機制從 中選取信息熵最大的屬性 ,將加入 ,將 加入 ;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使用指數機制從 中選擇互信息最大的加入 ,同時 加入 ;Ω(Xt,Πt)NiXtV end for 4.返回 .Ni

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

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

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

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

圖3 信息熵差異實例

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

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

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

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

3.4 差分隱私異構條件分布計算

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

算法5.HnoisyConditionals 算法輸入: 數據集,貝葉斯網絡 ,隱私預算NiP*i輸出: 根據 生成的帶噪聲的條件分布集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,∏)構建 的聯合分布;j■■■■■■■■■■2 Lap∑|Ci|j=l′+1 exp(-OE j)■■■■■■■■■■nε3×加入拉普拉斯噪聲,實現差分隱私;Pr*(X j,∏j)Pr*(X j,∏)exp(-OE j)j中的負值歸0 并正?；?Pr*(X j,∏j)Pr*(X j|∏j)P*i從中提取并加入 ;設end for j=1l′3.for to do Pr*(Xl′+1,∏l′+1)Pr*(X j|∏j)P*i從中提取加入 ;end for P*i 4.返回 .

根據式(7),歸一化風險熵計算公式如下:

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

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

3.5 隱私分析

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

證明: 在HMPrivBayes 的整個執行過程中,其中有3 步涉及原始數據集的訪問,分別是屬性分割、構建差分隱私貝葉斯網絡和提取屬性噪聲條件分布,下面分別討論這3 步的隱私保護強度.

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

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

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

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

4 實驗評估

4.1 實驗設置

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

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

表1 數據集屬性信息描述

對于這兩個數據集,隱私預算分配策略為ε1=a1/aε,ε2=a2/aε,ε3=a3/aε,其中a=a1+a2+a3,屬性分類簇個數k默認值為3,貝葉斯網絡的最大入度數l默認值為3.

4.2 評價指標

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

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

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

4.3 實驗結果

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

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

圖4 數據安全性分析

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

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

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

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

圖6 算法運行時間分析

5 結束語

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