面向高維數(shù)據(jù)發(fā)布的個性化差分隱私算法①

馬蘇杭,龍士工,劉 海,彭長根,李思雨

1(貴州大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,貴陽 550025)

2(貴州大學(xué) 貴州省公共大數(shù)重點實驗室,貴陽 550025)

1 引 言

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

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

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

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

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

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

2 相關(guān)工作

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

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

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

3 基礎(chǔ)知識

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

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

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

表1 符號定義表

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

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

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

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

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

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

3.2 差分隱私

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

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

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

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

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

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

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

性質(zhì)1.差分隱私序列組合性[11].給定數(shù)據(jù)集D,相互獨立的差分隱私隨機算法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é)點X與Y之間的互信息I如式(5)所示.

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

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

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

4 PPBA 算法

4.1 最大支撐樹

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

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

算法1.最大支撐樹輸入: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集合用于存儲最大支撐樹的無向邊 (Xi,Xj),以圖1為例將圖中有向邊轉(zhuǎn)化為無向邊,由連接關(guān)系可知A、B、C、D四個屬性節(jié)點無向邊個數(shù)分別為3、3、2、2 其中最大值為3,則選取K值為3.

4.2 個性化比例分配

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

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

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

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

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

根據(jù)動態(tài)權(quán)重值大小進行排序,則屬性節(jié)點的敏感性排序為A、C、B、D.

(2)個性化比例分配計算

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

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

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

得:

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

表3 ε 分配表

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

4.3 PPBA 算法實現(xiàn)

本節(jié)描述PPBA 算法的具體實現(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 每一個屬性字段,并且(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ù),計算低維屬性集合屬性節(jié)點的值;DWV εi 6.根據(jù) 值,將低維屬性集合敏感性由大到小排序,計算為每個集合分配的值id 7.① for=1 to do λi=?f εiP(Xi|Mi)② Add to ;P?(Xi,Mi)③ return ;④ end for D?8.Return

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

算法第2 部分,合成滿足ε-差分隱私的發(fā)布數(shù)據(jù)集.5–7 步根據(jù)數(shù)據(jù)可用性和安全性需求設(shè)置q值,為每個屬性集合分配滿足 ε/2-差分隱私Laplace 機制的隱私預(yù)算.為屬性節(jié)點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ù)機制挑選屬性關(guān)系對和對條件分布添加拉普拉斯噪音的過程中由差分隱私序列組合性質(zhì)[11]分別滿足 ε/2-差分隱私保護,其它行為不會產(chǎn)生額外的隱私預(yù)算.根據(jù)差分隱私組合性質(zhì)中的序列組合性[11],證得PPBA算法滿足ε-差分隱私.

5 實驗與分析

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

5.1 實驗環(huán)境

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

實驗中所使用的軟硬件參數(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]算法中的評分函數(shù)確定網(wǎng)絡(luò)結(jié)構(gòu)的好壞,本實驗選擇K2Score函數(shù)分別對3個算法生成的貝葉斯網(wǎng)絡(luò)進行評分,評分越高,貝葉斯網(wǎng)絡(luò)與原始數(shù)據(jù)擬合度越高.其中由于K2函數(shù)公式特性計算網(wǎng)絡(luò)評分值均為負(fù)值.實驗分別選取1000、5000、10000、15000、20000、25000、30000大小數(shù)據(jù)集對比3個算法生成的貝葉斯網(wǎng)絡(luò)的精確度,結(jié)果如圖2所示.

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

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

PPBA 算法將實驗數(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)為按敏感性由大到小進行排序的低維屬性集合的屬性節(jié)點,1為敏感性最高的低維屬性集合的節(jié)點,以此類推.從圖3看出,在q值為1.0 時各屬性集合分配均等的隱私預(yù)算.隨著q值不斷增大,越敏感的屬性集合分配的隱私預(yù)算越小,對其隱私保護強度越大,反之,敏感性越小屬性分配的隱私預(yù)算越大,隱私保護強度越小.從而實現(xiàn)隱私預(yù)算合理分配.

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

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

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

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

5.4 時間性能對比分析

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

圖5 不同q 值下隱私保護強度

圖6 時間性能對比圖

6 總結(jié)與展望

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