賈俊杰,邱萬勇*,馬慧芳,2

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

2桂林電子科技大學(xué) 廣西可信軟件重點實驗室 桂林 中國 541004

1 引言

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

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

針對機(jī)器學(xué)習(xí)中數(shù)據(jù)模型發(fā)布、分析時的個人隱私泄露問題,在特定算法中引入差分隱私,保護(hù)數(shù)據(jù)私有或敏感信息的同時,使得發(fā)布的模型發(fā)揮其最大的可用性[7-8]。差分隱私數(shù)據(jù)分析的基本任務(wù)是將現(xiàn)有的非隱私算法擴(kuò)展到差分隱私算法。在集中學(xué)習(xí)模式下,基于數(shù)據(jù)分析的差分隱私模型研究中,由于模型本身會泄露訓(xùn)練數(shù)據(jù)中個體屬性或敏感信息。對此,需設(shè)計相應(yīng)擾動機(jī)制使模型訓(xùn)練過程實現(xiàn)差分隱私保護(hù)。一般為輸入擾動、目標(biāo)擾動、梯度擾動和輸出擾動等[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]對其改進(jìn)并提出DiffPRFs算法,引入指數(shù)機(jī)制處理連續(xù)屬性。差分隱私保護(hù)下的集成分類模型 DP-AdaBoost[18]只能處理離散屬性的ID3決策樹,算法以決策樹樁作為基分類器并在葉結(jié)點添加相應(yīng)噪聲,沒有考慮樹深度與隱私保護(hù)下分類模型的關(guān)系。

表1 差分隱私約束下基于決策樹分類方法對比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ù)水平對集成模型分類性能的影響,通過合理分配利用隱私預(yù)算,設(shè)計分類性能良好且安全有效的隱私保護(hù)集成模型。

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

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

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

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

本文第 2節(jié)描述差分隱私理論基礎(chǔ)和改進(jìn)后的CART提升樹算法以及集成學(xué)習(xí)AdaBoost理論背景; 接下來,第 3節(jié)給出本文算法框架,并詳細(xì)討論提出的CART-DPsAdaBoost算法,對其隱私性進(jìn)行合理證明與分析; 第4節(jié)提供完整的檢驗和討論結(jié)果,這些結(jié)果來自兩個標(biāo)準(zhǔn)數(shù)據(jù)集上的一系列實驗分析; 文章結(jié)論部分總結(jié)了該方法的優(yōu)點和局限性,并期待進(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)險,隱私預(yù)算ε也稱隱私保護(hù)水平指數(shù)。ε越小數(shù)據(jù)安全需求越高。

定義 2.全局敏感度[5-6]。對于任意滿足的相鄰數(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ī)制通過Laplace分布產(chǎn)生的噪聲,擾動真實輸出值來實現(xiàn)差分隱私保護(hù),Laplace機(jī)制僅適用于對數(shù)值結(jié)果的保護(hù)。對于非數(shù)值型數(shù)據(jù),例如實體對象,McSherry等人[6,11]提出了指數(shù)機(jī)制。

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

其中輸入為數(shù)據(jù)集D,輸出為實體對象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,對于同一數(shù)據(jù)集D,由這些算法構(gòu)成的組合算法-差分隱私保護(hù)。

性質(zhì) 2.并行組合性[5-6]。設(shè)有算法M1,M2,? ??,Mn其 隱 私 預(yù) 算 分 別 為 ε1,ε2,? ??,εn,對于不相交的數(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]。本文以增加模型的多樣性來提高基分類器一定程度的準(zhǔn)確率,使基分類器“好而不同”,對此引入樣本擾動和特征擾動兩類隨機(jī)性方案,即在集成算法迭代的過程中引入自適應(yīng)采樣方案,以及在特征選擇中使用隨機(jī)子空間算法來構(gòu)建 CART提升樹。穆海蓉等人[16]提出一種基于差分隱私的隨機(jī)森林算法 DiffPRFs,在樹的構(gòu)建過程中采用指數(shù)機(jī)制選擇分裂點和分裂特征,并根據(jù)Laplace機(jī)制添加噪聲。該算法雖無需對數(shù)據(jù)進(jìn)行離散化預(yù)處理,但每次迭代需調(diào)用兩次指數(shù)機(jī)制,導(dǎo)致大量隱私預(yù)算消耗。

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

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

?

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

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

AdaBoost[1,19]核心思想是針對同一數(shù)據(jù)分布將逐步強(qiáng)化生成的多個弱分類器進(jìn)行集成,最終構(gòu)成一個分類效果較好的強(qiáng)分類器。而強(qiáng)化的過程即算法核心步驟如下所述: 給定訓(xùn)練集,初始化樣本分布,調(diào)用弱學(xué)習(xí)算法獲得基分類器,根據(jù)其誤差率調(diào)整訓(xùn)練樣本權(quán)重?；诟淖兊臉颖痉植?經(jīng)過多次迭代,得到一組具有互補(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.估計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~ 是一個分布;10.END FOR輸出: () ()( )sign T t t t=1 Gx αgx= ∑~~~~

3 CART-DPsAdaBoost算法

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

3.1 算法與模型

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

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

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

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

步驟4,計算錯誤分類的數(shù)據(jù)比例,并根據(jù)誤差率計算該基分類器在總體分類器中對應(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ù)的集成分類器。

通過上述步驟生成的強(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.對生成的決策樹進(jìn)行剪枝:() (())_t t g x CART Prungx′ = ;8.計算被剪枝子樹的隱私預(yù)算總量,并將其添加到被剪枝的子樹的父節(jié)點中;

9.計算 ()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.計算 ()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

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

3.2 分類

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

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

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

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

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

3.3 算法的性能

隱私性

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

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

證明:

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

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

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

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

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

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

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

4 實驗結(jié)果與分析

4.1 實驗數(shù)據(jù)

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

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

Adult數(shù)據(jù)集包含6個連續(xù)屬性、8個離散屬性,類別屬性為income lever,類別值為“<=50K”“>50K”;Adult_Train共 32561個元組,其中 70%作為訓(xùn)練集,30%作為測試集對訓(xùn)練模型進(jìn)行剪枝操作;Adult_Predict為預(yù)測數(shù)據(jù)集其包含 16281個元組。Census Income共41個屬性,其中8個數(shù)值屬性,33個離散屬性,Census Income_Train共 199523個元組,Census Income_Predict共99763個元組。為檢驗算法的有效性,設(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é)點分裂時隨機(jī)選取的特征數(shù)為k=5進(jìn)行多組實驗。

4.2 實驗結(jié)果

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

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

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

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

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

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

圖3 兩個數(shù)據(jù)集上不同樹深度的模型在訓(xùn)練集和測試集上樣本量與模型準(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

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

4.2.1 評估

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

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

同時使用 ROC[13-14,19](Receiver Operating Characteristic)曲線下的 AUC(Area Under Curve)值來評估分類器泛化性能。該值越大分類器泛化性能越高,AUC取值范圍為[0,1]。兩個數(shù)據(jù)集上實驗結(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ù)集上的實驗結(jié)果,圖4(a)當(dāng)d固定ε越大Precision值也隨著增大。此外,如圖4(a)(d)所示,Adult數(shù)據(jù)集上d=4時Precision最佳,Census Income數(shù)據(jù)集上d=5時Precision最佳。如圖4(b)(e)所示為模型在數(shù)據(jù)集上的召回率變化情況,隨著d的變化模型精準(zhǔn)度和召回率互相影響,Precision值大時Recall較小,反之亦然。圖4(c)(f)為F1Score值的變化情況,F1Score綜合衡量了Precision和Recall的結(jié)果,ε≥ 0.25時,F1Score值在86%上下波動,模型的可用性較好。如圖5(a) Adult數(shù)據(jù)集實驗結(jié)果顯示ε? [ 0.1,0.5]AUC變化波動較大,這是由于Adult數(shù)據(jù)集特征數(shù)量較少,調(diào)節(jié)隱私水平對AUC產(chǎn)生的擾動較大。而圖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 對比

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

表4 AUC性能對比Table 4 AUC performance comparison

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

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

5 結(jié)束語

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

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