差分隱私保護(hù)約束下集成分類算法的研究

賈俊杰,邱萬(wàn)勇*,馬慧芳,2

1西北師范大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 蘭州 中國(guó) 730070

2桂林電子科技大學(xué) 廣西可信軟件重點(diǎn)實(shí)驗(yàn)室 桂林 中國(guó) 541004

1 引言

互聯(lián)網(wǎng)“顛覆性”的發(fā)展,使各種信息系統(tǒng)采集且積累了豐富的數(shù)據(jù)。機(jī)器學(xué)習(xí)即對(duì)海量的數(shù)據(jù)進(jìn)行分析以獲得各類可用的數(shù)據(jù)模型[1]。而數(shù)據(jù)集中通常都含有私有或敏感信息,如醫(yī)療診斷信息、電子商務(wù)購(gòu)物信息等,由此引發(fā)人們對(duì)自身隱私泄露的擔(dān)憂。

隱私保護(hù)技術(shù)[2-4]能有效處理數(shù)據(jù)模型發(fā)布當(dāng)中個(gè)人隱私信息泄露問(wèn)題。匿名技術(shù)依賴于攻擊者的背景知識(shí),所提供的隱私是“無(wú)法保證的”。Dwork等人[5]提出差分隱私定義,解決了傳統(tǒng)隱私保護(hù)模型的兩個(gè)缺陷: 1)差分隱私保護(hù)與背景知識(shí)無(wú)關(guān); 2)差分隱私建立在嚴(yán)格的數(shù)學(xué)基礎(chǔ)上,對(duì)隱私保護(hù)提供了量化的評(píng)估方法。差分隱私的核心概念涵蓋了從隱私保護(hù)領(lǐng)域到數(shù)據(jù)科學(xué)(如機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、統(tǒng)計(jì)和學(xué)習(xí)理論)等領(lǐng)域的一系列研究[6-10]。

針對(duì)機(jī)器學(xué)習(xí)中數(shù)據(jù)模型發(fā)布、分析時(shí)的個(gè)人隱私泄露問(wèn)題,在特定算法中引入差分隱私,保護(hù)數(shù)據(jù)私有或敏感信息的同時(shí),使得發(fā)布的模型發(fā)揮其最大的可用性[7-8]。差分隱私數(shù)據(jù)分析的基本任務(wù)是將現(xiàn)有的非隱私算法擴(kuò)展到差分隱私算法。在集中學(xué)習(xí)模式下,基于數(shù)據(jù)分析的差分隱私模型研究中,由于模型本身會(huì)泄露訓(xùn)練數(shù)據(jù)中個(gè)體屬性或敏感信息。對(duì)此,需設(shè)計(jì)相應(yīng)擾動(dòng)機(jī)制使模型訓(xùn)練過(guò)程實(shí)現(xiàn)差分隱私保護(hù)。一般為輸入擾動(dòng)、目標(biāo)擾動(dòng)、梯度擾動(dòng)和輸出擾動(dòng)等[8,11]。

差分隱私已被廣泛應(yīng)用于傳統(tǒng)機(jī)器學(xué)習(xí)中,如邏輯回歸、支持向量機(jī)以及決策樹[12-14]等分類模型,并能較好的平衡可用性和隱私性。本文以決策樹作為基分類器進(jìn)行差分隱私約束下的集成分類模型研究,表1匯總了差分隱私約束下基于決策樹分類方法的相關(guān)研究[12-18]。在集成學(xué)習(xí)中,Patil和Singh[15]將差分隱私引入隨機(jī)森林并提出 DiffPRF算法,其使用ID3作為基分類器且只能處理離散屬性。穆海蓉等人[16]對(duì)其改進(jìn)并提出DiffPRFs算法,引入指數(shù)機(jī)制處理連續(xù)屬性。差分隱私保護(hù)下的集成分類模型 DP-AdaBoost[18]只能處理離散屬性的ID3決策樹,算法以決策樹樁作為基分類器并在葉結(jié)點(diǎn)添加相應(yīng)噪聲,沒有考慮樹深度與隱私保護(hù)下分類模型的關(guān)系。

表1 差分隱私約束下基于決策樹分類方法對(duì)比Table 1 Comparison of classification methods based on decision tree under differential privacy constraints

本文在分析已有差分隱私保護(hù)決策樹相關(guān)研究的基礎(chǔ)上構(gòu)建CART提升樹,提出一種基于差分隱私保護(hù)的 AdaBoost集成分類模型 CARTDPsAdaBoost(CART-Differential Privacy structure of AdaBoost),在樹深度增加而模型復(fù)雜度增加的情況下,分析不同隱私保護(hù)水平對(duì)集成模型分類性能的影響,通過(guò)合理分配利用隱私預(yù)算,設(shè)計(jì)分類性能良好且安全有效的隱私保護(hù)集成模型。

本文的主要貢獻(xiàn)包括3個(gè)方面:

1) 算法在Boosting過(guò)程中結(jié)合Bagging的思想和屬性擾動(dòng)中的隨機(jī)子空間算法,增加基分類器多樣性的同時(shí)使迭代過(guò)程中每個(gè)元組被選中的概率由它的權(quán)重決定。若添加噪聲大小小于樣本和特征采樣的隨機(jī)性,噪聲對(duì)隱私的影響微乎其微。該方法對(duì)大數(shù)據(jù)集、高維度屬性數(shù)據(jù)分類效率較好。

2) 算法構(gòu)建CART提升樹作為集成學(xué)習(xí)的基分類器,在建樹過(guò)程中利用指數(shù)機(jī)制選擇連續(xù)特征分裂點(diǎn),利用Gini指數(shù)選擇最佳分裂特征,并保證隱私預(yù)算的合理分配與利用。

3) 算法無(wú)需對(duì)數(shù)據(jù)進(jìn)行離散化預(yù)處理,降低了分類系統(tǒng)性能的消耗。在滿足差分隱私保護(hù)的需求下,分析最佳參數(shù)域,保持較高分類準(zhǔn)確率,保證分類模型的隱私性。

本文第 2節(jié)描述差分隱私理論基礎(chǔ)和改進(jìn)后的CART提升樹算法以及集成學(xué)習(xí)AdaBoost理論背景; 接下來(lái),第 3節(jié)給出本文算法框架,并詳細(xì)討論提出的CART-DPsAdaBoost算法,對(duì)其隱私性進(jìn)行合理證明與分析; 第4節(jié)提供完整的檢驗(yàn)和討論結(jié)果,這些結(jié)果來(lái)自兩個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集上的一系列實(shí)驗(yàn)分析; 文章結(jié)論部分總結(jié)了該方法的優(yōu)點(diǎn)和局限性,并期待進(jìn)一步的研究。

2 定義與理論基礎(chǔ)

2.1 差分隱私理論基礎(chǔ)

2.1.1 差分隱私定義

定義1.ε-差分隱私[5-6]。給定相鄰數(shù)據(jù)集D和D′至多相差一條記錄,即設(shè)有隨機(jī)機(jī)制M,Range(M )為M的值域,M的任意輸出結(jié)果 O (O ? Range(M ))若滿足下列不等式,則M滿足ε-差分隱私:

其中 P r[?]表示隱私被披露的風(fēng)險(xiǎn),隱私預(yù)算ε也稱隱私保護(hù)水平指數(shù)。ε越小數(shù)據(jù)安全需求越高。

定義 2.全局敏感度[5-6]。對(duì)于任意滿足的相鄰數(shù)據(jù)集D和D′,給定查詢函數(shù)f:D→Rd,函數(shù) f的敏感度為:

2.1.2 噪聲機(jī)制

定義 3.Laplace機(jī)制[5-6].給定任意函數(shù)f:D →Rd,表達(dá)式 K (D)的輸出滿足下列等式,則 K (D )滿足ε-差分隱私。

Laplace機(jī)制通過(guò)Laplace分布產(chǎn)生的噪聲,擾動(dòng)真實(shí)輸出值來(lái)實(shí)現(xiàn)差分隱私保護(hù),Laplace機(jī)制僅適用于對(duì)數(shù)值結(jié)果的保護(hù)。對(duì)于非數(shù)值型數(shù)據(jù),例如實(shí)體對(duì)象,McSherry等人[6,11]提出了指數(shù)機(jī)制。

定義 4.指數(shù)機(jī)制[5-6].給定一個(gè)效用函數(shù)q : (D × O ) → r (r ? R ange),函數(shù) F (D ,q)滿足下列等式,則 F (D ,q)滿足ε-差分隱私。

其中輸入為數(shù)據(jù)集D,輸出為實(shí)體對(duì)象r,Δq是效用函數(shù) q (D ,r)的全局敏感度。函數(shù)F以正比于的概率從Range中選擇并輸出r。

2.1.3 相關(guān)性質(zhì)

性質(zhì) 1.序列組合性[5-6]。設(shè)有算法M1,M2,? ??,Mn其隱私預(yù)算分別為 ε1,ε2,? ? ?,εn,對(duì)于同一數(shù)據(jù)集D,由這些算法構(gòu)成的組合算法-差分隱私保護(hù)。

性質(zhì) 2.并行組合性[5-6]。設(shè)有算法M1,M2,? ??,Mn其 隱 私 預(yù) 算 分 別 為 ε1,ε2,? ??,εn,對(duì)于不相交的數(shù)據(jù)集 D1,D2,? ??,Dn,由這些算法構(gòu)成的組合算法 M (M1( D1) ,M2(D2),? ??,Mn(Dn))提供(m axεi)-差分隱私保護(hù)。

2.2 分類與回歸樹

構(gòu)建CART提升樹

CART(Classification and Regression Tree)分類與回歸樹[1,14]。本文以增加模型的多樣性來(lái)提高基分類器一定程度的準(zhǔn)確率,使基分類器“好而不同”,對(duì)此引入樣本擾動(dòng)和特征擾動(dòng)兩類隨機(jī)性方案,即在集成算法迭代的過(guò)程中引入自適應(yīng)采樣方案,以及在特征選擇中使用隨機(jī)子空間算法來(lái)構(gòu)建 CART提升樹。穆海蓉等人[16]提出一種基于差分隱私的隨機(jī)森林算法 DiffPRFs,在樹的構(gòu)建過(guò)程中采用指數(shù)機(jī)制選擇分裂點(diǎn)和分裂特征,并根據(jù)Laplace機(jī)制添加噪聲。該算法雖無(wú)需對(duì)數(shù)據(jù)進(jìn)行離散化預(yù)處理,但每次迭代需調(diào)用兩次指數(shù)機(jī)制,導(dǎo)致大量隱私預(yù)算消耗。

本文以改進(jìn)后的 CART提升樹作為集成學(xué)習(xí)的基分類器。對(duì)于連續(xù)特征使用指數(shù)機(jī)制選擇分裂點(diǎn),使用Gini指數(shù)選擇分裂特征,迭代中只需調(diào)用一次指數(shù)機(jī)制,整個(gè)算法保證了隱私預(yù)算的充分利用。

假設(shè)有樣本集 D (i),樣本數(shù)N,屬性集合Λ( A ?Λ),類標(biāo)簽集 Y (? y?Y ) ,分類類別數(shù)k,實(shí)體對(duì)象r,記錄屬于類別 k (k ?K ) 的概率Prk,概率分布的 Gini值為 Gini(Pr)=則本文 CART提升樹的構(gòu)建如算法1所示。

?

~ ： ,類計(jì)數(shù)加噪D PartitionD y Y y y y =(i ,? ? =[]i )N NoisyCountD y =;6.ELSE節(jié)點(diǎn)未達(dá)到中止條件:THEN劃分當(dāng)前分裂節(jié)點(diǎn),添加噪聲量為( )( )y■ ■■ ■■max ,Laplace 12 ti■ ■,噪聲量為( )( )ω ε′■Laplace ti ■ ■■ ■′max ,;■ω ε■7.IF 子空間Λ包含n個(gè)連續(xù)屬性,執(zhí)行步驟8;8.( )ε ′′′= +ε 2n1 9.用以下概率選擇每個(gè)連續(xù)屬性分裂點(diǎn):exp ,2■qDA R q ■′( )■■Δi ■i ■∑i i i exp ,2′′■■ε ε′qDA R q ■ Δ( )■■■qDA為效用性函數(shù),Δq為效用性函數(shù)的全局敏感度,/*其中 ( ),i R為區(qū)間集合的大i Di劃分為兩個(gè)子集 ()小*/10.END IF 11.將數(shù)據(jù)集 ()l D i;12.建立左右子樹:r Di和()t Build DPTreeDiΛε d l =_(l (),,,+1 Dl )t Build DPTreeD iΛε d r=_(r (),,,+1 Dr )13.END IF 14.UNTIL節(jié)點(diǎn)達(dá)到中止條件即全部記錄標(biāo)簽一致;達(dá)到最大深度d;隱私預(yù)算耗盡;15.RETURN ()g x t

2.3 集成學(xué)習(xí)之AdaBoost

AdaBoost[1,19]核心思想是針對(duì)同一數(shù)據(jù)分布將逐步強(qiáng)化生成的多個(gè)弱分類器進(jìn)行集成,最終構(gòu)成一個(gè)分類效果較好的強(qiáng)分類器。而強(qiáng)化的過(guò)程即算法核心步驟如下所述: 給定訓(xùn)練集,初始化樣本分布,調(diào)用弱學(xué)習(xí)算法獲得基分類器,根據(jù)其誤差率調(diào)整訓(xùn)練樣本權(quán)重?；诟淖兊臉颖痉植?經(jīng)過(guò)多次迭代,得到一組具有互補(bǔ)性的基分類器并將其線性組合成強(qiáng)分類器,以提高集成模型的準(zhǔn)確性和穩(wěn)定性。具體如算法2所示。

算法2.AdaBoost輸入: ( )( ) ( )｛｝1 1 2 2,,,,,,n n D xy xy xy=???~;基學(xué)習(xí)算法L;訓(xùn)練輪數(shù)T~;1.初始化樣本權(quán)重分布: ()1 1 Dx=n~ ;2.FOR t=1 TO T~ DO 3.調(diào)用算法L生成基分類器: ( ),t t g DD= ~~~ L ;4.估計(jì)g~t的誤差: ( () )t t t i xD P g x y τ= ≠~~ ~ ;5.IF 0.5 tτ﹥THEN 6.break;7.END IF 8.確定g~t的權(quán)重:~1 1ln 2 t t t α τ■ ■-τ=■■■ ■;9.更新樣本分布:() ()( ) ()() ()() ()( )exp ,if exp ,if expt t t i t t t i t t ti t t D x g x y D x g x y Z D x yg x Z α α α+1■ - == ×■ ≠■=~~ ~~~ ~~ ~ ~其中Zt是規(guī)范化因子,以確保Dt+1~ 是一個(gè)分布;10.END FOR輸出: () ()( )sign T t t t=1 Gx αgx= ∑~~~~

3 CART-DPsAdaBoost算法

發(fā)布最終的集成分類模型,要確?；诸惼骷礇Q策樹的結(jié)構(gòu)不被泄露,因?yàn)闃浣Y(jié)構(gòu)含有核心的分類規(guī)則和結(jié)果。假設(shè)數(shù)據(jù)分析者對(duì)數(shù)據(jù)集有完全訪問(wèn)的權(quán)限,則可以在基分類器的生成過(guò)程加入噪聲。即在構(gòu)建 CART提升樹過(guò)程中向分裂節(jié)點(diǎn)及葉結(jié)點(diǎn)添加相應(yīng)的Laplace機(jī)制噪聲,并合理分配隱私預(yù)算來(lái)控制噪聲量大小,最后進(jìn)行隱私性的合理證明和適用性分析,以完善算法性能評(píng)估,分析隱私保護(hù)與模型效用之間的平衡。

3.1 算法與模型

給定算法的迭代次數(shù)為T,總的隱私預(yù)算為pε,每迭代一次生成新的基分類器。

步驟1,初始化數(shù)據(jù)樣本權(quán)重分布。

步驟2,遞歸的使用采樣策略,并根據(jù)權(quán)值分布找出最大的權(quán)重值作為敏感度參數(shù)。調(diào)用算法1在生成基分類器的過(guò)程中,根據(jù)噪聲公式計(jì)算每個(gè)分裂節(jié)點(diǎn)和葉結(jié)點(diǎn)所需的噪聲值并加入到基分類器中,得到滿足差分隱私的基分類器。

步驟3,對(duì)生成的基分類器即決策樹進(jìn)行剪枝操作,計(jì)算被剪枝子樹的隱私預(yù)算總量,并將其添加到被剪枝子樹的父節(jié)點(diǎn)中。

步驟4,計(jì)算錯(cuò)誤分類的數(shù)據(jù)比例,并根據(jù)誤差率計(jì)算該基分類器在總體分類器中對(duì)應(yīng)的權(quán)重系數(shù)。

步驟5,依據(jù)誤差率更新數(shù)據(jù)樣本的權(quán)值分布。

步驟6,判斷當(dāng)前迭代次數(shù)是否已滿足設(shè)定值,若滿足則終止,否則執(zhí)行下一步。

步驟7,返回步驟2,繼續(xù)構(gòu)建新的基分類器。

步驟8,將所得到的基分類器進(jìn)行線性組合,得到最終滿足差分隱私保護(hù)的集成分類器。

通過(guò)上述步驟生成的強(qiáng)分類器即為帶差分隱私保護(hù)的集成分類算法的分類模型,可以直接發(fā)布給數(shù)據(jù)挖掘工作者而不用擔(dān)心隱私的泄露。

算法3.CART-DPsAdaBoost輸入: ( )( ) ( )｛｝1 1 2 2,,,,,,n n D xy xy xy=??? ;i x?Λ; ｛ ｝1,1 i y?-;迭代次數(shù)T;隱私預(yù)算pε;輸出: 滿足pε-差分隱私保護(hù)的集成分類器()Gx;1.初始化權(quán)重分布: ()[ ]1 1,1,D i i n n=? ;2.損失函數(shù):(() ) ()( ),,exp i i Egx yi ygx= - ;3.ε()logα p c t T ε= -4.FOR t=1 TO T DO 5.從D中采樣選取大小為D的訓(xùn)練集()Di;6.調(diào)用算法1生成基分類器 ()t g x() (() )_,,,t c g x Build DPTreeDiΛεd;=7.對(duì)生成的決策樹進(jìn)行剪枝:() (())_t t g x CART Prungx′ = ;8.計(jì)算被剪枝子樹的隱私預(yù)算總量,并將其添加到被剪枝的子樹的父節(jié)點(diǎn)中;

9.計(jì)算 ()t t t i i τ ω ■ ■′=;10.IF 0.5 t∑g′x的誤差率:() () [ ],1,iIg x y i n≠ ?■■tτ﹥THEN 11.break;12.END IF 13.計(jì)算 ()g′x的權(quán)重系數(shù):α τ■ ■=■■■ ■1-τt t t 1ln 2;t 14.更新樣本權(quán)重分布:() () ()Di yg x D i Z tit i t t t exp(-α ′)+1=其中 Zt是規(guī)范化因子 ()Z Diexp?t t i=1=∑n( )α ′-ti t i ;15.END FOR 16.RETURN () ()yg (x)Gx αg x= ∑sign T( )t t t= ′1

通過(guò) Laplace噪聲機(jī)制對(duì)隱私信息進(jìn)行保護(hù),噪聲量大小由隱私預(yù)算ε來(lái)控制.計(jì)算噪聲時(shí)需考慮每一條記錄權(quán)重值 ωt(i ),使得差分隱私噪聲計(jì)算公式中函數(shù)敏感度動(dòng)態(tài)變化[18],根據(jù)敏感度公式得出 Δ f = m ax ( ωt,i ),同時(shí) Laplace機(jī)制噪聲公式轉(zhuǎn)化為 K (D)= f(x)+ (Laplace ( Δ f ε))d。算法中指數(shù)機(jī)制的效用函數(shù)使用Gini指數(shù).最小化Gini指數(shù)等價(jià)于最大化 G iniΛ( D ),其敏感度 Δ qGini= 2 ,選擇 Gini指數(shù)作為效用函數(shù)敏感度較低使得指數(shù)機(jī)制的效率有所增高[12]。本文預(yù)先指定迭代次數(shù),在隱私預(yù)算分配中同時(shí)考慮每個(gè)弱分類器的權(quán)重值tα,即每個(gè)弱分類器分配到的預(yù)算為log(αt)。

3.2 分類

對(duì)新樣本集中的每一條記錄,應(yīng)用最終的集成模型進(jìn)行分類。最終分類結(jié)果是加入差分隱私噪聲的每個(gè)基分類器結(jié)果與權(quán)重的乘積線性組合?；诸惼鞯臉?gòu)建包含建樹和剪枝兩步驟。算法的集成分類器簡(jiǎn)化模型如圖1所示。對(duì)新樣本分類過(guò)程見算法4。

圖1 差分隱私保護(hù)下的集成分類模型結(jié)構(gòu)圖Figure 1 Structure diagram of ensemble classification model under differential privacy protection

算法4.使用 ()Gx對(duì)新樣本分類輸入: 預(yù)測(cè)集?M;滿足pε-差分隱私的集成

分類器 ()Gx輸出: 預(yù)測(cè)集中樣本的分類結(jié)果1.REPEAT 2.對(duì)每條待分類樣本;3.FOR i=1 TO m DO 4.從當(dāng)前樹的根節(jié)點(diǎn)開始,根據(jù)當(dāng)前節(jié)點(diǎn)類型,判斷進(jìn)入哪個(gè)子節(jié)點(diǎn),直至到達(dá)葉子結(jié)點(diǎn);5.得到當(dāng)前樹的預(yù)測(cè)結(jié)果與其權(quán)重值相乘;6.線性組合每棵樹的結(jié)果: sign();7.END FOR 8.UNTIL到達(dá)葉子結(jié)點(diǎn)9.RETURN輸出樣本集?M的分類結(jié)果(?)YM■ ■′■ ■■ ■∑T t t t αg x=1

通過(guò)本文算法構(gòu)建滿足隱私保護(hù)的集成分類器模型 G (x),可將該分類模型直接發(fā)布給數(shù)據(jù)挖掘工作者而不必?fù)?dān)心數(shù)據(jù)集中的個(gè)體信息會(huì)被泄露。

3.3 算法的性能

隱私性

集成分類器生成過(guò)程中,預(yù)先定義了算法的迭代次數(shù),故采用層次均分的方法[16-20]。首先將總的隱私預(yù)算pε平均分配給每一棵樹基于Bagging思想采樣的每棵樹樣本集有交集,根據(jù)差分隱私性質(zhì)1,總的隱私預(yù)算為每棵樹消耗預(yù)算的疊加。對(duì)于每一棵樹將隱私預(yù)算平均分配到每一層由于每層節(jié)點(diǎn)樣本之間不相交,根據(jù)差分隱私性質(zhì)2,每個(gè)節(jié)點(diǎn)預(yù)算為用每個(gè)節(jié)點(diǎn)預(yù)算的一半來(lái)估計(jì)該節(jié)點(diǎn)實(shí)例數(shù),之后判斷是否到達(dá)終止條件,若滿足則標(biāo)記為葉結(jié)點(diǎn)并用另一半預(yù)算確定葉結(jié)點(diǎn)類計(jì)數(shù)。若當(dāng)前節(jié)點(diǎn)有n個(gè)連續(xù)屬性,則將另一半的預(yù)算均分為n+1份,用于選擇每個(gè)連續(xù)屬性的分裂點(diǎn),每次指數(shù)機(jī)制消耗預(yù)算為,由序列組合性可知,多次指數(shù)機(jī)制消耗的預(yù)算為各次的疊加。

性質(zhì)3.G (x)提供εp-差分隱私保護(hù)。

證明:

1) 對(duì)于每個(gè)連續(xù)屬性有 ri種劃分方法,ri被以指數(shù)機(jī)制選中的概率為其中 E (D ,ri)表示以 p (ri)為權(quán)重,則連續(xù)屬性劃分方案 ri以正比于 p (ri)E(D ,ri)的概率參與全局選擇。

2) 對(duì)于離散屬性使用 Gini指數(shù)劃分,若屬性A有v個(gè)值,則有個(gè)劃分子集,以屬性A劃分所計(jì)算Gini指標(biāo)值為:

其中N1、N2為不相交的子集,根據(jù)差分隱私性質(zhì)1得。則Gini指數(shù)的差分隱私預(yù)算可根據(jù)性質(zhì)2轉(zhuǎn)化為:

根據(jù)差分隱私性質(zhì)1,每棵樹的隱私保護(hù)程度為:

因此,提供εc-差分隱私保護(hù)。

3) 對(duì)于集成分類模型 G (x),總的差分隱私預(yù)算滿足:

因此,G (x)提供εp-差分隱私保護(hù)。得證。

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

4.1 實(shí)驗(yàn)數(shù)據(jù)

分類器訓(xùn)練、預(yù)測(cè)及數(shù)據(jù)預(yù)處理均使用python3.7實(shí)現(xiàn),編輯器為 PyCharm。采用 UCI Machine Learning Repository中的Adult數(shù)據(jù)集設(shè)計(jì)對(duì)照實(shí)驗(yàn),并在Census Income大規(guī)模、高維度數(shù)據(jù)集上驗(yàn)證算法的有效性。表2展示了相關(guān)數(shù)據(jù)集的基本信息。

表2 實(shí)驗(yàn)數(shù)據(jù)集Table 2 Experimental data set

Adult數(shù)據(jù)集包含6個(gè)連續(xù)屬性、8個(gè)離散屬性,類別屬性為income lever,類別值為“<=50K”“>50K”;Adult_Train共 32561個(gè)元組,其中 70%作為訓(xùn)練集,30%作為測(cè)試集對(duì)訓(xùn)練模型進(jìn)行剪枝操作;Adult_Predict為預(yù)測(cè)數(shù)據(jù)集其包含 16281個(gè)元組。Census Income共41個(gè)屬性,其中8個(gè)數(shù)值屬性,33個(gè)離散屬性,Census Income_Train共 199523個(gè)元組,Census Income_Predict共99763個(gè)元組。為檢驗(yàn)算法的有效性,設(shè)置ε= ( 0.05,0.1,0.25,0.5,0.75,1),決策樹數(shù)量T=10,每棵樹的深度d= ( 2 ,3,4,5,6),效用函數(shù)使用Gini指數(shù),隨機(jī)子空間算法中節(jié)點(diǎn)分裂時(shí)隨機(jī)選取的特征數(shù)為k=5進(jìn)行多組實(shí)驗(yàn)。

4.2 實(shí)驗(yàn)結(jié)果

1) 噪聲對(duì)模型分類準(zhǔn)確率的影響

圖2 不同隱私水平下隨樹深度的增加分類準(zhǔn)確率變化情況Figure 2 Changes in classification accuracy with increasing tree depth under different privacy levels

2) 樹深度對(duì)模型分類準(zhǔn)確率的影響

在隱私預(yù)算ε不變的情況下,隨著樹深度的增加,集成模型的準(zhǔn)確率呈現(xiàn)上升趨勢(shì),這是因?yàn)闃湓缴罱⒌囊?guī)則越精確分類誤差便降低。當(dāng)然,隨著樹深度的增加,集成模型復(fù)雜度也隨之增大,圖2(a)在Adult數(shù)據(jù)集上當(dāng)d﹥4時(shí),模型已發(fā)生過(guò)擬合。實(shí)驗(yàn)以樣本量與模型分類準(zhǔn)確率變化情況做進(jìn)一步解析。

3) 兩個(gè)數(shù)據(jù)集上模型最優(yōu)樹深值的分析圖3(a-f)實(shí)驗(yàn)中取值為ε=1,T=10。一個(gè)共同趨勢(shì)是樣本量較少時(shí)訓(xùn)練集模型準(zhǔn)確率較高,測(cè)試集模型準(zhǔn)確率低,隨著樣本量增加初始的過(guò)擬合現(xiàn)象逐漸好轉(zhuǎn),模型準(zhǔn)確率逐漸趨于平穩(wěn)。此外,兩個(gè)數(shù)據(jù)集上隨樹深度的增加分類模型波動(dòng)隨之增大,這是由于模型越復(fù)雜所添加的噪聲越多干擾越明顯。Census Income數(shù)據(jù)集上的噪聲干擾總體上較大,這是由于該數(shù)據(jù)集屬性維度較高,建樹相比較復(fù)雜從而使得噪聲的影響更加顯著。

如圖3(a~c)在 Adult數(shù)據(jù)集上,模型準(zhǔn)確率從35%上升到了 81%左右,當(dāng)隱私預(yù)算越大即ε? [ 0.75,1]時(shí)越趨近于未加噪的模型準(zhǔn)確率。對(duì)于Census Income高維度數(shù)據(jù)集從60%上升到了80%左右,由于該數(shù)據(jù)集特征數(shù)量較多模型更易于學(xué)習(xí),400左右樣本量已達(dá)到模型的最優(yōu)值,準(zhǔn)確率為80%左右。該算法在大規(guī)模、高維度數(shù)據(jù)集上表現(xiàn)更佳,時(shí)間效率更好,具有較好的數(shù)據(jù)擴(kuò)展性。

圖3 兩個(gè)數(shù)據(jù)集上不同樹深度的模型在訓(xùn)練集和測(cè)試集上樣本量與模型準(zhǔn)確率的關(guān)系Figure 3 The relationship between the sample size of the models with different tree depths on the training set and the test set and the accuracy of the model

綜上實(shí)驗(yàn)進(jìn)一步分析,在 Adult數(shù)據(jù)集上,模型分類準(zhǔn)確率穩(wěn)定在81%左右。而由圖2(a)實(shí)驗(yàn)數(shù)據(jù)分析可知,當(dāng)隱私預(yù)算不變時(shí)d=4模型準(zhǔn)確率達(dá)到最佳,為0.8081813156441。在Census Income數(shù)據(jù)集上,準(zhǔn)確率穩(wěn)定在 80%左右,由圖2(b)實(shí)驗(yàn)數(shù)據(jù)可知,d= 5 模型準(zhǔn)確率達(dá)到最佳,為0.7993123634249。

4.2.1 評(píng)估

F-Measure[1,19]是用來(lái)評(píng)價(jià)分類器性能的常用指標(biāo),綜合衡量模型的精準(zhǔn)度和召回率,定義如下:

其中β為調(diào)節(jié)Precision和Recall相對(duì)重要性的系數(shù)(取1即為F1Score)。 F1Score的取值范圍為[0,1],該值越大算法可用性越好。

同時(shí)使用 ROC[13-14,19](Receiver Operating Characteristic)曲線下的 AUC(Area Under Curve)值來(lái)評(píng)估分類器泛化性能。該值越大分類器泛化性能越高,AUC取值范圍為[0,1]。兩個(gè)數(shù)據(jù)集上實(shí)驗(yàn)結(jié)果如圖4-5以及表3-4所示。

表3 隨隱私水平ε的變化Precision,Recall, F1Scores值的變化情況Table 3 How Precision,Recall,and F1Scores vary withε

樹深度設(shè)定為 d = ( 2 ,3,4,5,6),分配的隱私預(yù)算為 ε =(0.1,0.25,0.5,0.75,1)。圖4(a~c)為 Adult數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果,圖4(a)當(dāng)d固定ε越大Precision值也隨著增大。此外,如圖4(a)(d)所示,Adult數(shù)據(jù)集上d=4時(shí)Precision最佳,Census Income數(shù)據(jù)集上d=5時(shí)Precision最佳。如圖4(b)(e)所示為模型在數(shù)據(jù)集上的召回率變化情況,隨著d的變化模型精準(zhǔn)度和召回率互相影響,Precision值大時(shí)Recall較小,反之亦然。圖4(c)(f)為F1Score值的變化情況,F1Score綜合衡量了Precision和Recall的結(jié)果,ε≥ 0.25時(shí),F1Score值在86%上下波動(dòng),模型的可用性較好。如圖5(a) Adult數(shù)據(jù)集實(shí)驗(yàn)結(jié)果顯示ε? [ 0.1,0.5]AUC變化波動(dòng)較大,這是由于Adult數(shù)據(jù)集特征數(shù)量較少,調(diào)節(jié)隱私水平對(duì)AUC產(chǎn)生的擾動(dòng)較大。而圖5(b)所示在Census Income特征維度高的數(shù)據(jù)集上AUC表現(xiàn)較好。

圖4 不同隱私水平下隨樹深度的增加Precision/Recall/F1Score值的變化情況Figure 4 The change of Precision/Recall/F1Score with the increase of tree depth at different privacy levels

4.2.2 對(duì)比

由于同類算法DP-AdaBoost是樹深度為1的集成分類模型,相關(guān)對(duì)比實(shí)驗(yàn)設(shè)定ε=0.05,0.1,0.25,0.5,0.75,1,T=10,d=1,在不同隱私水平下,模型分類準(zhǔn)確率比較結(jié)果如圖5(c)所示。

表4 AUC性能對(duì)比Table 4 AUC performance comparison

圖5 模型的ROC曲線部分圖示以及同類算法對(duì)比Figure 5 Part of the model's ROC curve diagram and comparison of similar algorithms

當(dāng)d=1時(shí),相比 DP-AdaBoost同類算法旨在葉結(jié)點(diǎn)添加相應(yīng)的噪聲,本文算法在樹的構(gòu)建過(guò)程中對(duì)分裂節(jié)點(diǎn)和葉結(jié)點(diǎn)同時(shí)添加相應(yīng)的 Laplace噪聲,樹深度較低時(shí)對(duì)模型分類性能影響較大,即以犧牲一定的模型準(zhǔn)確率來(lái)?yè)Q取更佳的數(shù)據(jù)隱私性。同時(shí)本文在研究不同樹深度下隱私水平對(duì)分類模型的影響時(shí),通過(guò)相關(guān)實(shí)驗(yàn)結(jié)果表明,算法在隱私保護(hù)策略下選擇最優(yōu)樹深及隱私域時(shí)模型可以達(dá)到較好的分類效果。在分類樹構(gòu)建過(guò)程中消耗了一部分隱私預(yù)算用于處理連續(xù)特征,但無(wú)需對(duì)連續(xù)特征進(jìn)行離散化預(yù)處理,一定程度上提高了分類效率。

5 結(jié)束語(yǔ)

在已有差分隱私?jīng)Q策樹各類算法基礎(chǔ)上,研究了差分隱私保護(hù)下 AdaBoost集成分類算法,保護(hù)數(shù)據(jù)隱私信息的同時(shí)保持集成模型較高的分類性能。實(shí)驗(yàn)表明,在集成當(dāng)中提高了隱私預(yù)算的利用和算法的執(zhí)行效率,能有效處理大規(guī)模、高維度數(shù)據(jù)分類問(wèn)題。此外由于其可擴(kuò)展性,該方法將可以適用于大數(shù)據(jù)環(huán)境.存在的不足之處: (1)隱私保護(hù)水平采用隱私預(yù)算ε定量分析,但實(shí)際算法和應(yīng)用中的取值缺乏一個(gè)標(biāo)準(zhǔn); (2)通常差分隱私假設(shè)數(shù)據(jù)記錄相互獨(dú)立,但在實(shí)際中數(shù)據(jù)庫(kù)的記錄可能存在關(guān)聯(lián)性,會(huì)增加隱私泄露的風(fēng)險(xiǎn)。在接下來(lái)的工作中,會(huì)繼續(xù)對(duì)算法做進(jìn)一步優(yōu)化,提升泛化性能。該研究的實(shí)驗(yàn)數(shù)據(jù)集和程序代碼將在GitHub平臺(tái)更新。

致 謝本課題得到國(guó)家自然科學(xué)基金項(xiàng)目(No.61967013),甘肅省高等學(xué)校創(chuàng)新能力提升項(xiàng)目(No.2019A-006),的資助,在此表示感謝。