馬蘇杭,龍士工,劉 海,彭長(zhǎng)根,李思雨

1(貴州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,貴陽(yáng) 550025)

2(貴州大學(xué) 貴州省公共大數(shù)重點(diǎn)實(shí)驗(yàn)室,貴陽(yáng) 550025)

1 引 言

隨著移動(dòng)互聯(lián)網(wǎng)的發(fā)展,數(shù)據(jù)規(guī)模也以前所未有的速度不斷增長(zhǎng),數(shù)據(jù)屬性之間的相互關(guān)系變得復(fù)雜多樣,高維數(shù)據(jù)已是一種常見(jiàn)的數(shù)據(jù)發(fā)布類型.隨著數(shù)據(jù)挖掘和分析技術(shù)的發(fā)展,高維數(shù)據(jù)的發(fā)布具有更高的信息價(jià)值,但高維數(shù)據(jù)中通常包含大量隱私信息,如果使用不當(dāng)將造成隱私泄露[1,2].為了保證高維數(shù)據(jù)發(fā)布過(guò)程中不會(huì)泄露隱私信息,在發(fā)布之前使用差分隱私[3,4]保護(hù)技術(shù)進(jìn)行處理.如果直接對(duì)高維數(shù)據(jù)進(jìn)行差分隱私處理,存在添加噪音過(guò)多,數(shù)據(jù)可用性差等問(wèn)題.其中差分隱私預(yù)算的分配方式直接影響數(shù)據(jù)的可用性與安全性關(guān)系,而不同數(shù)據(jù)機(jī)構(gòu)對(duì)于發(fā)布數(shù)據(jù)集安全性和可用性之間的關(guān)系需求各不相同,數(shù)據(jù)保護(hù)級(jí)別更高的數(shù)據(jù)機(jī)構(gòu)更注重?cái)?shù)據(jù)的安全性;而主要提供數(shù)據(jù)進(jìn)行應(yīng)用的數(shù)據(jù)機(jī)構(gòu)則更傾向于數(shù)據(jù)的可用性.

目前已有的面向高維數(shù)據(jù)發(fā)布的差分隱私算法有概率圖模型[5–7]、閾值過(guò)濾技術(shù)[8]以及投影技術(shù)[9],這些技術(shù)通過(guò)維度轉(zhuǎn)換達(dá)到降維效果,減少噪音添加對(duì)數(shù)據(jù)可用性的影響.降維效果的好壞直接影響數(shù)據(jù)的可用性,而閾值過(guò)濾技術(shù)和投影技術(shù)忽略了高維屬性之間普遍存在依賴關(guān)系,采用直接截?cái)嗟慕稻S方法,大大降低了數(shù)據(jù)的可用性.文獻(xiàn)[5–7]利用指數(shù)機(jī)制[3,10]挑選屬性關(guān)系對(duì),受候選空間大小和隱私預(yù)算分配方式的影響,空間越大挑選的屬性關(guān)系對(duì)越不準(zhǔn)確.同時(shí),單一的隱私預(yù)算分配方式為敏感性不同的屬性數(shù)據(jù)分配相同的隱私預(yù)算,導(dǎo)致隱私預(yù)算無(wú)法根據(jù)數(shù)據(jù)可用性與安全性的個(gè)性化需求合理分配,存在隱私浪費(fèi)的問(wèn)題.

基于在高維數(shù)據(jù)發(fā)布過(guò)程中,數(shù)據(jù)安全性與可用性受降維算法效果和隱私預(yù)算分配方式的影響,為滿足發(fā)布數(shù)據(jù)集安全性與可用性的個(gè)性化需求,本文提出個(gè)性化隱私預(yù)算分配(Personnalized Privacy Budget Allocation,PPBA)算法,主要內(nèi)容如下.

(1)對(duì)基于概率圖模型的貝葉斯網(wǎng)絡(luò)算法進(jìn)行優(yōu)化,引入最大支撐樹(shù)和最大權(quán)重值,減少指數(shù)機(jī)制挑選屬性關(guān)系對(duì)的搜索空間,避免敵手進(jìn)行多次查詢對(duì)比分析,泄露隱私信息.提高數(shù)據(jù)可用性和安全性.

(2)依據(jù)動(dòng)態(tài)權(quán)重值確定貝葉斯網(wǎng)絡(luò)中低維屬性集合敏感性由大到小的排序.受文獻(xiàn)[11–13]啟發(fā),根據(jù)不同用戶數(shù)據(jù)可用性與安全性需要,個(gè)性化設(shè)置隱私預(yù)算分配比值常數(shù)q,為不同敏感性的屬性集合合理分配差分隱私(Laplace[10])噪聲.

(3)理論證明所提出的PPBA 算法滿足ε-差分隱私,并在真實(shí)數(shù)據(jù)集上進(jìn)行性能評(píng)估.實(shí)驗(yàn)結(jié)果表明能夠滿足數(shù)據(jù)可用性與安全性個(gè)性化需求,同時(shí)降低了時(shí)間復(fù)雜度.

2 相關(guān)工作

數(shù)據(jù)獨(dú)立發(fā)布算法和數(shù)據(jù)相關(guān)發(fā)布算法是主要的2 類面向高維數(shù)據(jù)發(fā)布的差分隱私算法.獨(dú)立發(fā)布算法的典型代表是PriVew[14],該算法假設(shè)所有屬性都是相互獨(dú)立的,這在真實(shí)數(shù)據(jù)集中是不存在的,且缺少正式的推理機(jī)制.而PrivBayes 算法[5]、加權(quán)貝葉斯網(wǎng)絡(luò)算法[6]、聯(lián)合樹(shù)算法[7]是典型的數(shù)據(jù)相關(guān)發(fā)布算法.

PrivBayes 算法利用指數(shù)機(jī)制挑選屬性關(guān)系對(duì)形成貝葉斯網(wǎng)絡(luò),對(duì)聯(lián)合分布概率進(jìn)行推理,存在候選空間較大,數(shù)據(jù)可用性和安全性得不到保障的問(wèn)題.文獻(xiàn)[6]對(duì)貝葉斯網(wǎng)絡(luò)進(jìn)行優(yōu)化,利用最大權(quán)重值提高貝葉斯網(wǎng)絡(luò)推理的準(zhǔn)確性,但仍然存在挑選屬性關(guān)系對(duì)候選空間較大的問(wèn)題.文獻(xiàn)[7]通過(guò)指數(shù)機(jī)制構(gòu)造Markov網(wǎng),引入高通濾波技術(shù)縮減指數(shù)機(jī)制搜索空間.并結(jié)合相應(yīng)的后置技術(shù)對(duì)Markov 網(wǎng)分割來(lái)獲得完全團(tuán)圖,生成滿足差分隱私的聯(lián)合樹(shù),利用聯(lián)合樹(shù)中各個(gè)團(tuán)后置處理之后的聯(lián)合分布表合成最終的高維數(shù)據(jù).文獻(xiàn)[5–7]在高維數(shù)據(jù)相關(guān)發(fā)布得到廣泛的應(yīng)用,但在面對(duì)不同數(shù)據(jù)機(jī)構(gòu)對(duì)于數(shù)據(jù)安全性與可用性的個(gè)性化需求,缺少個(gè)性化的隱私預(yù)算分配策略.

針對(duì)不同數(shù)據(jù)類型關(guān)于隱私預(yù)算分配問(wèn)題,為了兼顧數(shù)據(jù)安全性與可用性的效率,文獻(xiàn)[11]以差分隱私保護(hù)結(jié)合主流決策樹(shù)分類方法,提出等差分配隱私預(yù)算的方式,改善決策樹(shù)的分類準(zhǔn)確率.文獻(xiàn)[12]針對(duì)樹(shù)索引結(jié)構(gòu)提出等差數(shù)列分配和等比數(shù)列分配兩種方式.避免對(duì)樹(shù)的某一層分配過(guò)小,數(shù)據(jù)可用性過(guò)低;分配過(guò)大,不能對(duì)這層數(shù)據(jù)提供足夠安全保障的問(wèn)題.

3 基礎(chǔ)知識(shí)

本節(jié)內(nèi)容主要對(duì)面向高維數(shù)據(jù)發(fā)布的個(gè)性化差分隱私算法所使用的貝葉斯網(wǎng)絡(luò)、差分隱私概念進(jìn)行說(shuō)明.

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

文章在論述過(guò)程中涉及較多數(shù)學(xué)符號(hào),為了更好地對(duì)下文相關(guān)內(nèi)容進(jìn)行解釋,給出相關(guān)符號(hào)定義,如表1所示.

表1 符號(hào)定義表

定義1.貝葉斯網(wǎng)絡(luò).貝葉斯網(wǎng)絡(luò)N為一個(gè)有向無(wú)環(huán)圖,N中每一個(gè)節(jié)點(diǎn)代表高維數(shù)據(jù)集D中一個(gè)字段屬性,如果N中兩個(gè)屬性節(jié)點(diǎn)之間存在著直接依賴關(guān)系,則兩個(gè)屬性字段節(jié)點(diǎn)之間用一條弧(或有向邊)直接相連.貝葉斯網(wǎng)絡(luò)N使用(屬性字段節(jié)點(diǎn),屬性字段節(jié)點(diǎn)的父節(jié)點(diǎn)集合)對(duì)來(lái)表示.

通過(guò)挑選屬性間的依賴關(guān)系,實(shí)現(xiàn)高維數(shù)據(jù)的維度轉(zhuǎn)換,構(gòu)建貝葉斯網(wǎng)絡(luò)進(jìn)行聯(lián)合分布的推理.通過(guò)例子解釋說(shuō)明,高維數(shù)據(jù)集屬性集合為Ar1,有A、B、C、D共4個(gè)屬性,未進(jìn)行維度轉(zhuǎn)換形成貝葉斯網(wǎng)絡(luò)時(shí),其聯(lián)合分布的計(jì)算如下式所示:

若在屬性依賴關(guān)系的挑選中使用最大父節(jié)點(diǎn)個(gè)數(shù)值即度值為2的貝葉斯網(wǎng)絡(luò)算法對(duì)該數(shù)據(jù)集進(jìn)行處理,形成如圖1所示4個(gè)屬性字段節(jié)點(diǎn)構(gòu)成的2 度貝葉斯網(wǎng)絡(luò)圖.

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

則該貝葉斯網(wǎng)絡(luò)用4個(gè)相對(duì)獨(dú)立的低維屬性集合(A,?),(B,{A}),(C,{A,B}),(D,{A,C}),來(lái)表示,其中聯(lián)合分布P rN[Ar1]的計(jì)算如式(2)所示.

未進(jìn)行維度轉(zhuǎn)化處理之前該數(shù)據(jù)集屬性之間存在6 種屬性關(guān)系,當(dāng)使用2 度貝葉斯網(wǎng)絡(luò)算法之后降低到5 種屬性關(guān)系.P rN[Ar1] 相 比P r[Ar1]在數(shù)據(jù)量較多的情況下具有更低的計(jì)算復(fù)雜度,為多個(gè)相對(duì)獨(dú)立的低維屬性集合加入更少的噪聲.

3.2 差分隱私

差分隱私保護(hù)技術(shù)通過(guò)向原始數(shù)據(jù)集添加滿足差分隱私的噪音生成鄰近數(shù)據(jù)集,使得原始數(shù)據(jù)集與鄰近數(shù)據(jù)集在查詢輸出中具有概率不可區(qū)分性.

定義2.ε-差分隱私[10].對(duì)于任意兩個(gè)相鄰數(shù)據(jù)集D1和D2,它們之間相差最多為一條記錄,若一個(gè)隨機(jī)函數(shù)A滿足ε-差分隱私保護(hù),Range(A)表示隨機(jī)函數(shù)A的取值范圍,則對(duì)于所有的S?Range(A)有:

其中,P r[E]表示事件E的披露風(fēng)險(xiǎn),ε為隱私預(yù)算參數(shù),代表了差分隱私保護(hù)水平,其值越小,不可區(qū)分性越大,隱私保護(hù)級(jí)別越高.

定義3.敏感度[10].敏感度是由函數(shù)本身決定的,不同函數(shù)具有不同的敏感度,敏感度過(guò)低會(huì)使發(fā)布數(shù)據(jù)集的安全性得不到保障,敏感度過(guò)高則使發(fā)布數(shù)據(jù)集的發(fā)布結(jié)果實(shí)用性降低.

給定F是將一個(gè)數(shù)據(jù)集映射到一個(gè)固定大小實(shí)數(shù)向量的函數(shù),那么函數(shù)F的敏感度為:

其中,D1和D2為任意兩個(gè)鄰近數(shù)據(jù)集,二者僅相差一個(gè)數(shù)據(jù)元組.

為了在給定的隱私預(yù)算內(nèi),將全部隱私預(yù)算合理分配到多個(gè)相對(duì)獨(dú)立的低維屬性集合中,使整個(gè)數(shù)據(jù)發(fā)布過(guò)程中滿足差分隱私,可以利用差分隱私的序列組合性質(zhì).

性質(zhì)1.差分隱私序列組合性[11].給定數(shù)據(jù)集D,相互獨(dú)立的差分隱私隨機(jī)算法A1,A2,···,Ai分別滿足 εi-差分隱私,其中1≤i≤d,則序列組合{A1,A2,···,Ai}滿足ε-差分隱私,其中

定義4.互信息函數(shù).1948年香農(nóng)提出信息熵[14]的概念,屬性之間互信息I的大小代表屬性之間的關(guān)聯(lián)程度.高維數(shù)據(jù)集D屬性節(jié)點(diǎn)X與Y之間的互信息I如式(5)所示.

其中,滿足差分隱私的噪音機(jī)制主要有指數(shù)機(jī)制、Laplace機(jī)制.

命題1.基于互信息函數(shù)的指數(shù)機(jī)制.指數(shù)機(jī)制[10]主要用于處理輸出結(jié)果為非數(shù)值型結(jié)果.在維度轉(zhuǎn)換過(guò)程中,屬性節(jié)點(diǎn)的關(guān)聯(lián)程度作為指數(shù)機(jī)制挑選屬性關(guān)系對(duì)的依據(jù),打分函數(shù)為屬性間的互信息函數(shù)I,其中?I(X:Y)為互信息函數(shù)I的敏感度,以正比于exp的概率挑選出具有最大依賴關(guān)系的維度屬性,組成多個(gè)滿足ε 差分隱私的相對(duì)獨(dú)立的低維屬性集合.其中文獻(xiàn)[5]中給出了維度轉(zhuǎn)換過(guò)程中互信息敏感度的計(jì)算方法,見(jiàn)式(6);由于在指數(shù)機(jī)制挑選過(guò)程中,除挑選屬性關(guān)系對(duì)外無(wú)其它隱私消耗,由差分隱私組合性質(zhì)[11],該過(guò)程滿足對(duì)應(yīng)ε-差分隱私.

命題2.基于聯(lián)合分布的拉普拉斯機(jī)制.拉普拉斯機(jī)制[11]通過(guò)Laplace 分布產(chǎn)生噪聲擾動(dòng)真實(shí)值達(dá)到差分隱私保護(hù).在貝葉斯網(wǎng)絡(luò)中對(duì)多個(gè)相對(duì)獨(dú)立的低維屬性集合,計(jì)算其聯(lián)合分布P.P?=P+Z為向其聯(lián)合分布概率中添加拉普拉斯噪音Z,其中?f為聯(lián)合分布函數(shù)敏感度,Z～Lap(?f/ε)為服從尺度參數(shù)?f/ε,方差為2?f2/ε2的Laplace 分布.由于在該過(guò)程中除為聯(lián)合分布添加拉普拉斯噪音外無(wú)其它隱私消耗,由差分隱私組合性質(zhì)[11]滿足對(duì)應(yīng)ε 值的差分隱私.

4 PPBA 算法

4.1 最大支撐樹(shù)

本節(jié)對(duì)最大支撐樹(shù)的定義和構(gòu)建過(guò)程進(jìn)行解釋說(shuō)明,通過(guò)最大支撐樹(shù)限制指數(shù)機(jī)制挑選屬性關(guān)系對(duì)的候選空間.撐樹(shù)減少挑選屬性關(guān)系對(duì)的候選空間,確定貝葉斯網(wǎng)絡(luò)度值K.

命題3.最大支撐樹(shù).利用高維數(shù)據(jù)屬性之間的互信息得到的一種樹(shù)狀網(wǎng)絡(luò)結(jié)構(gòu),通過(guò)依次計(jì)算兩兩屬性間的互信息,只保留與該屬性具有最大互信息的屬性之間的無(wú)向邊,完成最大支撐樹(shù)的建立.根據(jù)最大支

算法1.最大支撐樹(shù)輸入:Data D VT輸出:T=?VT=?1.Initialize:,;id 2.①for=1 to jdj≠i for=1 to and I(Xi,X j)I(Xi,X j)T Compute,add to I(Xi,X j)(Xi,Xj)VT②Select Max,add to ;VT 3.Return ;

根據(jù)算法1 輸出的VT集合,其中VT集合用于存儲(chǔ)最大支撐樹(shù)的無(wú)向邊 (Xi,Xj),以圖1為例將圖中有向邊轉(zhuǎn)化為無(wú)向邊,由連接關(guān)系可知A、B、C、D四個(gè)屬性節(jié)點(diǎn)無(wú)向邊個(gè)數(shù)分別為3、3、2、2 其中最大值為3,則選取K值為3.

4.2 個(gè)性化比例分配

本節(jié)內(nèi)容主要對(duì)個(gè)性化比例分配方法所涉及的敏感性排序和比例分配的計(jì)算過(guò)程進(jìn)行解釋.

(1)依據(jù)動(dòng)態(tài)權(quán)重值對(duì)低維屬性集合進(jìn)行敏感性排序

在文獻(xiàn)[6]中分別給出了CM、WV、DWV值的計(jì)算方法,根據(jù)文獻(xiàn)[6]中對(duì)屬性節(jié)點(diǎn)動(dòng)態(tài)權(quán)重值的定義,動(dòng)態(tài)權(quán)重值可以很好地代表屬性節(jié)點(diǎn)在貝葉斯網(wǎng)絡(luò)中的重要性,重要性越高,對(duì)于貝葉斯網(wǎng)絡(luò)精確度和數(shù)據(jù)集的可用性影響越大,該屬性值隱私泄露對(duì)數(shù)據(jù)集的安全性影響越大.故選取動(dòng)態(tài)權(quán)重值作為敏感性的衡量依據(jù).

假設(shè)圖1中各屬性CM值如表2中所示,則由文獻(xiàn)[6]的計(jì)算方法,對(duì)圖1中4個(gè)屬性權(quán)重值計(jì)算結(jié)果如表2所示.

表2 屬性權(quán)重值計(jì)算結(jié)果表

根據(jù)動(dòng)態(tài)權(quán)重值大小進(jìn)行排序,則屬性節(jié)點(diǎn)的敏感性排序?yàn)锳、C、B、D.

(2)個(gè)性化比例分配計(jì)算

高維數(shù)據(jù)集經(jīng)貝葉斯網(wǎng)絡(luò)處理之后,將數(shù)據(jù)集劃分為d個(gè)相對(duì)獨(dú)立的低維屬性集合,依據(jù)屬性節(jié)點(diǎn)的動(dòng)態(tài)權(quán)重值對(duì)低維屬性集合進(jìn)行敏感性由大到小排序,根據(jù)隱私預(yù)算分配策略將總的隱私預(yù)算合理分配到每個(gè)低維屬性集合.通過(guò)個(gè)性化設(shè)置分配比值常數(shù)q(q>1),從敏感性最高的低維屬性集合起,使該節(jié)點(diǎn)低維屬性集合與前一個(gè)敏感性更高的低維屬性集合分配的隱私預(yù)算大小比值為常數(shù)q(q>1),從而將隱私預(yù)算 ε 劃分為ε1,ε2,···,εd分別分配至d個(gè)低維屬性集合.

由圖1中屬性節(jié)點(diǎn)的低維屬性集合敏感性由大到小的排序?yàn)锳、C、B、D.總隱私預(yù)算 ε大小,根據(jù)需要設(shè)置的比值常數(shù)為q(q≥1).

由等比數(shù)列性質(zhì)式(7)、式(8):

得:

取ε=0.5 時(shí),分別設(shè)q值為1、1.1、1.3,則A、B、C、D各屬性節(jié)點(diǎn)分配的ε 值由式(9),式(10)計(jì)算結(jié)果如表3所示.

表3 ε 分配表

由以上分析和表3可知,當(dāng)給定總的隱私預(yù)算和低維屬性集合按敏感性由高到低的排序,用戶只需調(diào)整q值,就可以改變隱私預(yù)算的分配方式.當(dāng)q=1時(shí),每個(gè)低維屬性集合分配的隱私預(yù)算相同,即均勻分配隱私預(yù)算.當(dāng)q>1時(shí),按低維屬性集合排序,每個(gè)集合分配的隱私預(yù)算以q倍增加,隨著q值的增加,越重要的低維屬性集合分配的隱私預(yù)算越小,對(duì)應(yīng)的保護(hù)強(qiáng)度越高,數(shù)據(jù)的可用性則相應(yīng)降低.不難理解只要稍微改變q值,就可以改變隱私預(yù)算分配方式.

4.3 PPBA 算法實(shí)現(xiàn)

本節(jié)描述PPBA 算法的具體實(shí)現(xiàn)細(xì)節(jié)如算法2.

算法2.PPBA 算法D Kqε輸入:、、、N D?輸出:、N ?V ?1.Initialize:=,=;X1 X1 VX1 ? N 2.Select ;add to ;add (,)to ;id 3.① for=2 to Ω ?② Initialize =;X∈Ar/V③ for 每一個(gè)屬性字段,并且(X,M)Ω④ add to ⑤ end for Ω exp(εiI(Xi,Mi)2?I(Xi,Mi))(Xi,Mi)(Xi,Mi) NXiV⑥ 從中選擇使 最大的;add to ;add to ;⑦ end for N 4.Return ;N DWV 5.依據(jù),計(jì)算低維屬性集合屬性節(jié)點(diǎn)的值;DWV εi 6.根據(jù) 值,將低維屬性集合敏感性由大到小排序,計(jì)算為每個(gè)集合分配的值id 7.① for=1 to do λi=?f εiP(Xi|Mi)② Add to ;P?(Xi,Mi)③ return ;④ end for D?8.Return

PPBA 算法主要分為兩個(gè)部分,1–4 步為算法第一部分,實(shí)現(xiàn)滿足 ε/2-差分隱私的貝葉斯網(wǎng)絡(luò).由最大支撐樹(shù)確定貝葉斯網(wǎng)絡(luò)的度值K,第2 步選擇具有最大權(quán)重值的屬性節(jié)點(diǎn)作為貝葉斯網(wǎng)絡(luò)的首節(jié)點(diǎn).第3 步以互信息函數(shù)為滿足 ε/2-差分隱私指數(shù)機(jī)制的打分函數(shù),從屬性字段集合中選擇d–1個(gè)低維屬性集合對(duì)加入貝葉斯網(wǎng)絡(luò)N,其中V用于存儲(chǔ)屬性節(jié)點(diǎn),V表示的所有子集元素個(gè)數(shù)為m in(K,|V|).第4 步返回滿足差分隱私的貝葉斯網(wǎng)絡(luò)N.

算法第2 部分,合成滿足ε-差分隱私的發(fā)布數(shù)據(jù)集.5–7 步根據(jù)數(shù)據(jù)可用性和安全性需求設(shè)置q值,為每個(gè)屬性集合分配滿足 ε/2-差分隱私Laplace 機(jī)制的隱私預(yù)算.為屬性節(jié)點(diǎn)Xi的條件分布P(Xi|Mi)加入服從Laplace 分布的噪音,得到P?(Xi|Mi).第8 步根據(jù)P?(Xi|Mi)形成原始數(shù)據(jù)集的近似聯(lián)合分布,抽樣合成滿足ε-差分隱私的合成發(fā)布數(shù)據(jù)集D?.

4.4 滿足差分隱私證明

證明.在PPBA 算法中,根據(jù)命題1和命題2在指數(shù)機(jī)制挑選屬性關(guān)系對(duì)和對(duì)條件分布添加拉普拉斯噪音的過(guò)程中由差分隱私序列組合性質(zhì)[11]分別滿足 ε/2-差分隱私保護(hù),其它行為不會(huì)產(chǎn)生額外的隱私預(yù)算.根據(jù)差分隱私組合性質(zhì)中的序列組合性[11],證得PPBA算法滿足ε-差分隱私.

5 實(shí)驗(yàn)與分析

根據(jù)實(shí)驗(yàn)測(cè)試結(jié)果,對(duì)比分析PPBA 算法、加權(quán)PrivBayes 算法、PrivBayes 算法的數(shù)據(jù)可用性、數(shù)據(jù)安全性與可用性之間個(gè)性化平衡需求的實(shí)驗(yàn)以及算法時(shí)間性能3個(gè)方面.

5.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)中,采用美國(guó)UCI (University of California,Irvine)所提供的機(jī)器學(xué)習(xí)庫(kù)中的成人數(shù)據(jù)集,該數(shù)據(jù)集由美國(guó)人口普查數(shù)據(jù)組成,共計(jì)32561個(gè)元組.在該數(shù)據(jù)集中一共選取了10個(gè)屬性字段:Age,Workclass,Educatio,Maritalstatus,Race,Occupation,Relationship,Sex,Native,Country,Income.在實(shí)驗(yàn)之前將數(shù)據(jù)集劃分為測(cè)試數(shù)據(jù)集和訓(xùn)練數(shù)據(jù)集,并對(duì)數(shù)據(jù)集做刪除缺省值,屬性離散化等數(shù)據(jù)預(yù)處理操作.

實(shí)驗(yàn)中所使用的軟硬件參數(shù)如下:

(1)操作系統(tǒng):Windows10;

(2)硬件參數(shù):IntelCoreTM I5,2.4 GHz CPU,8 GB DDR 內(nèi)存;

(3)編譯環(huán)境及工具:Python3.6,Pycharm.

5.2 貝葉斯網(wǎng)絡(luò)精確度分析

貝葉斯網(wǎng)絡(luò)與原始數(shù)據(jù)的擬合度直接影響發(fā)布數(shù)據(jù)的可用性.在貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)中使用K2[15]算法中的評(píng)分函數(shù)確定網(wǎng)絡(luò)結(jié)構(gòu)的好壞,本實(shí)驗(yàn)選擇K2Score函數(shù)分別對(duì)3個(gè)算法生成的貝葉斯網(wǎng)絡(luò)進(jìn)行評(píng)分,評(píng)分越高,貝葉斯網(wǎng)絡(luò)與原始數(shù)據(jù)擬合度越高.其中由于K2函數(shù)公式特性計(jì)算網(wǎng)絡(luò)評(píng)分值均為負(fù)值.實(shí)驗(yàn)分別選取1000、5000、10000、15000、20000、25000、30000大小數(shù)據(jù)集對(duì)比3個(gè)算法生成的貝葉斯網(wǎng)絡(luò)的精確度,結(jié)果如圖2所示.

從圖2可以看出隨著數(shù)據(jù)集不斷增大,PPBA 算法生成的貝葉斯網(wǎng)絡(luò)的精確性高于PrivBayes 算法,原因是隨著數(shù)據(jù)集不斷增大,屬性維度之間的依賴關(guān)系越來(lái)越復(fù)雜,相較于加權(quán)PrivBayes 算法和PrivBayes算法,PPBA 算法利用最大支撐樹(shù),將指數(shù)機(jī)制屬性關(guān)系對(duì)的挑選空間控制在較優(yōu)的范圍,提高貝葉斯網(wǎng)絡(luò)的精確度,在數(shù)據(jù)集不斷增大,屬性關(guān)系越來(lái)越復(fù)雜的情況下,優(yōu)勢(shì)更為明顯.

5.3 個(gè)性化分配隱私預(yù)算下數(shù)據(jù)可用性與數(shù)據(jù)安全性分析

PPBA 算法將實(shí)驗(yàn)數(shù)據(jù)集低維屬性集合按敏感性由大到小排序,取q值大小分別為1.0、1.2、1.3、1.5、1.6、1.8、2.0.觀察取不同q值下,將ε=0.5的隱私預(yù)算分配給低維屬性集合,結(jié)果如圖3所示.圖3橫坐標(biāo)為按敏感性由大到小進(jìn)行排序的低維屬性集合的屬性節(jié)點(diǎn),1為敏感性最高的低維屬性集合的節(jié)點(diǎn),以此類推.從圖3看出,在q值為1.0 時(shí)各屬性集合分配均等的隱私預(yù)算.隨著q值不斷增大,越敏感的屬性集合分配的隱私預(yù)算越小,對(duì)其隱私保護(hù)強(qiáng)度越大,反之,敏感性越小屬性分配的隱私預(yù)算越大,隱私保護(hù)強(qiáng)度越小.從而實(shí)現(xiàn)隱私預(yù)算合理分配.

圖2 貝葉斯網(wǎng)絡(luò)精確度對(duì)比圖

圖3 敏感性排序下為屬性集合分配的隱私預(yù)算

發(fā)布數(shù)據(jù)集所需的可用性與安全性之間的個(gè)性化平衡是衡量隱私預(yù)算分配優(yōu)劣極重要指標(biāo).選取訓(xùn)練數(shù)據(jù)集大小分別為1000、5000、10000、15000、20000、25000、30000的數(shù)據(jù),使用加權(quán)PrivBayes (ε=1.0)算法,PrivBayes (ε=1.0 )算法,以及q取值1.0、1.1、1.2、1.3、1.5 下的PPBA (ε=1.0 )算法生成滿足ε-差分隱私的合成發(fā)布數(shù)據(jù)集.使用以上算法生成的合成發(fā)布數(shù)據(jù)集訓(xùn)練SVM 分類模型,利用SVM 分類模型[16]對(duì)測(cè)試數(shù)據(jù)集進(jìn)行測(cè)試.選取訓(xùn)練得到的SVM 模型分類器對(duì)測(cè)試數(shù)據(jù)集中“Sex”屬性進(jìn)行分類.SVM 分類的結(jié)果以及q值分別選取1.0、1.1、1.3、1.5 時(shí)通過(guò)Laplace 方差計(jì)算隱私損失所得的隱私保護(hù)強(qiáng)度結(jié)果分別如圖4、圖5所示.從圖4看出q值逐漸增大,在數(shù)據(jù)集不大的情況下,會(huì)出現(xiàn)PPBA 算法SVM 準(zhǔn)確率低于加權(quán)PrivBayes 算法和PrivBayes 算法的現(xiàn)象,但隨著數(shù)據(jù)集的不斷增大,PPBA 算法的分類準(zhǔn)確率均高于加權(quán)PrivBayes 算法和PrivBayes 算法,更進(jìn)一步的說(shuō)明PPBA 算法更適用于高維數(shù)據(jù)集的情況下.從圖5看出q值越大,隱私保護(hù)強(qiáng)度越高.結(jié)合圖4、圖5,根據(jù)用戶對(duì)發(fā)布數(shù)據(jù)集安全性與可用性的需求,當(dāng)用戶數(shù)據(jù)集元組大于15000的情況下,對(duì)SVM 分類準(zhǔn)確率要求為80%與82%之間,但同時(shí)要求隱私保護(hù)強(qiáng)度不低于0.001%與0.002%之間,根據(jù)圖4,q取值1.2 可以達(dá)到數(shù)據(jù)可用性與安全性的最優(yōu)平衡需求.當(dāng)用戶對(duì)隱私要求保護(hù)強(qiáng)度為0.007%與0.008%之間,數(shù)據(jù)可用性需求為79%到80%之間,結(jié)合圖4,圖5,可個(gè)性化設(shè)置q取值為1.5.從而證明PPBA 算法可以根據(jù)用戶需要滿足數(shù)據(jù)可用性與隱私保護(hù)強(qiáng)度之間個(gè)性化選擇的平衡.

圖4 Sex 屬性下SVM 分類準(zhǔn)確率

5.4 時(shí)間性能對(duì)比分析

在實(shí)驗(yàn)中,將PPBA 隱私保護(hù)算法(ε=1.0,q=1.0)、加權(quán)PrivBayes 隱私保護(hù)算法(ε=1.0)和PrivBayes隱私保護(hù)算法(ε=1.0)在合成發(fā)布數(shù)據(jù)集過(guò)程中,按照訓(xùn)練數(shù)據(jù)集由小到大進(jìn)行運(yùn)行時(shí)間對(duì)比分析.由于加權(quán)PrivBayes 隱私保護(hù)算法、PrivBayes 隱私保護(hù)算法隨機(jī)生成貝葉斯網(wǎng)絡(luò),運(yùn)行時(shí)間具有不確定性,實(shí)驗(yàn)選擇每個(gè)數(shù)據(jù)集下運(yùn)行10 次取平均值的方式衡量時(shí)間性能.對(duì)比分析結(jié)果如圖6所示,PPBA 算法運(yùn)行時(shí)間相對(duì)PrivBayes 算法、加權(quán)PrivBayes 算法時(shí)間更短,究其原因PPBA 算法利用屬性節(jié)點(diǎn)權(quán)重值確定首節(jié)點(diǎn),最大支撐樹(shù)確定最大父節(jié)點(diǎn)個(gè)數(shù)K值,減少屬性關(guān)系候選空間,避免K值過(guò)大,內(nèi)存資源的浪費(fèi),具有更優(yōu)的時(shí)間性能.但由于實(shí)驗(yàn)計(jì)算機(jī)性能有限,數(shù)據(jù)預(yù)處理工作量大等問(wèn)題,整體耗時(shí)較長(zhǎng),實(shí)驗(yàn)結(jié)果有待改進(jìn).

圖5 不同q 值下隱私保護(hù)強(qiáng)度

圖6 時(shí)間性能對(duì)比圖

6 總結(jié)與展望

面向高維數(shù)據(jù)隱私發(fā)布,不同數(shù)據(jù)發(fā)布用戶對(duì)于數(shù)據(jù)安全性和可用性的個(gè)性化需求,本文提出個(gè)性化差分隱私預(yù)算分配算法(PPBA),通過(guò)最大權(quán)重值和最大支撐樹(shù),降低屬性關(guān)系對(duì)的挑選空間,構(gòu)建更優(yōu)的貝葉斯網(wǎng)絡(luò),按照高維數(shù)據(jù)隱私保護(hù)強(qiáng)度和數(shù)據(jù)可用性間的平衡需要,個(gè)性化設(shè)置比例常數(shù)q值,依據(jù)集合的敏感性排序,為低維屬性集合分配合理的隱私預(yù)算,合成發(fā)布滿足差分隱私數(shù)據(jù)集.通過(guò)實(shí)驗(yàn)驗(yàn)證PPBA 算法形成的貝葉斯網(wǎng)絡(luò)更優(yōu),具有更低的時(shí)間復(fù)雜度,且滿足根據(jù)用戶需求,個(gè)性化實(shí)現(xiàn)隱私預(yù)算分配.接下來(lái)的研究工作會(huì)圍繞整個(gè)算法過(guò)程中差分隱私預(yù)算分配策略再利用,延長(zhǎng)隱私預(yù)算使用周期,提高發(fā)布數(shù)據(jù)的可用性等問(wèn)題進(jìn)行研究.