李遠(yuǎn)航,陳先來(lái),劉 莉,安 瑩,李忠民

(中南大學(xué) a.計(jì)算機(jī)學(xué)院; b.醫(yī)療大數(shù)據(jù)應(yīng)用技術(shù)國(guó)家工程實(shí)驗(yàn)室; c.信息安全與大數(shù)據(jù)研究院,長(zhǎng)沙 410083)

0 概述

目前,信息技術(shù)廣泛應(yīng)用于各行業(yè),使得醫(yī)療系統(tǒng)、社交網(wǎng)絡(luò)、電子商務(wù)系統(tǒng)、位置服務(wù)和教育系統(tǒng)都收集了海量的用戶數(shù)據(jù)[1]。同時(shí),由于數(shù)據(jù)發(fā)布、共享與分析的需求日益增多,個(gè)人隱私信息泄露的潛在概率不斷增加,使得隱私問(wèn)題受到越來(lái)越多的關(guān)注[2]。雖然刪除數(shù)據(jù)的標(biāo)志符屬性(如ID號(hào))或者隱藏?cái)?shù)據(jù)集中的敏感屬性(如姓名、住址)能夠在一定程度上保護(hù)個(gè)人隱私,但一些攻擊案例[3-5]表明,依據(jù)上述方法遠(yuǎn)不能滿足個(gè)人隱私保護(hù)的需求[6],還需要將敏感屬性值與特定的實(shí)體或個(gè)人關(guān)聯(lián)起來(lái),以避免由非敏感屬性信息推測(cè)出個(gè)人的真實(shí)身份[7]。

針對(duì)隱私泄露問(wèn)題,DWORK在2006年提出一種嚴(yán)格、可證明的隱私保護(hù)模型——差分隱私保護(hù)[8]。差分隱私保護(hù)作為一種新的隱私保護(hù)模型[9],與傳統(tǒng)的隱私保護(hù)模型相比,其具有4點(diǎn)優(yōu)勢(shì)。第一,差分隱私保護(hù)假設(shè)攻擊者擁有最大背景知識(shí),在這一假設(shè)下,其能應(yīng)對(duì)各種新型攻擊,無(wú)需考慮攻擊者所擁有的任何可能的背景知識(shí)[10]。第二,具有堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ),對(duì)隱私保護(hù)有嚴(yán)格的定義和可靠的量化評(píng)估方法,使得不同參數(shù)處理下的隱私保護(hù)水平具有可比性[11]。第三,差分隱私保護(hù)在大幅降低隱私泄露風(fēng)險(xiǎn)的同時(shí),極大地保證了數(shù)據(jù)的可用性[12]。第四,差分隱私保護(hù)雖然基于數(shù)據(jù)失真技術(shù),但所加入的噪聲量與數(shù)據(jù)集大小無(wú)關(guān),因此,對(duì)于大型數(shù)據(jù)集,該模型僅通過(guò)添加極少量的噪聲就能達(dá)到高級(jí)別的隱私保護(hù)水平[13]。

本文將差分隱私保護(hù)與隨機(jī)森林算法相結(jié)合,構(gòu)造滿足差分隱私保護(hù)要求的隨機(jī)森林算法,以在保護(hù)數(shù)據(jù)中隱私信息的同時(shí),使隨機(jī)森林算法仍然保持較高的分類準(zhǔn)確率。

1 相關(guān)工作

在數(shù)據(jù)挖掘中,應(yīng)用差分隱私保護(hù)的目的是在提取有價(jià)值信息的同時(shí)不泄露敏感隱私信息。決策樹(shù)是一類常見(jiàn)的分類模型[14],在數(shù)據(jù)挖掘分析中起著至關(guān)重要的作用。在決策樹(shù)中應(yīng)用差分隱私保護(hù),可以在分類的同時(shí)保護(hù)數(shù)據(jù)中的隱私信息[15]。

文獻(xiàn)[16]提出了應(yīng)用差分隱私保護(hù)的決策樹(shù)構(gòu)建算法SuLQ-based ID3,其主要思想是在每次計(jì)算特征的信息增益時(shí)使用Laplace機(jī)制添加噪聲,然后生成決策樹(shù),但在加入噪音后導(dǎo)致了預(yù)測(cè)結(jié)果準(zhǔn)確率大幅下降。文獻(xiàn)[17]對(duì)SuLQ-based ID3做了改進(jìn),提出了PINQ-based ID3算法。該算法使用Partition算子將數(shù)據(jù)集分割成不相交的子集,利用其計(jì)算時(shí)并行組合性的特點(diǎn),提高隱私保護(hù)預(yù)算的利用率。該算法直接利用噪聲計(jì)數(shù)值評(píng)估信息增益,再使用ID3算法生成決策樹(shù)。由于需要對(duì)每個(gè)特征計(jì)算信息增益的計(jì)數(shù)值,因此需要將隱私保護(hù)預(yù)算分配到每次查詢中,導(dǎo)致每次查詢的隱私保護(hù)預(yù)算較小,當(dāng)數(shù)據(jù)集較大時(shí)會(huì)引入大量噪聲。

為解決噪聲和隱私保護(hù)預(yù)算的問(wèn)題,文獻(xiàn)[18]基于指數(shù)機(jī)制提出了DiffP-ID3算法,指數(shù)機(jī)制在一次查詢時(shí)評(píng)估所有特征,減少了噪聲和隱私保護(hù)預(yù)算的消耗,但該算法主要用于處理離散型數(shù)據(jù)。為了處理連續(xù)型數(shù)據(jù),文獻(xiàn)[18]進(jìn)一步提出了DiffP-C4.5算法,但是該算法在每一次迭代中必須先用指數(shù)機(jī)制對(duì)所有連續(xù)型特征選擇分裂點(diǎn),然后將所得結(jié)果與全部離散型特征一起再次通過(guò)指數(shù)機(jī)制,接著選擇最終的分裂方案,由于每次迭代需要調(diào)用2次指數(shù)機(jī)制,因此消耗了過(guò)多的隱私保護(hù)預(yù)算[19]。

文獻(xiàn)[20]提出的DiffGen算法將泛化技術(shù)和自頂向下分割技術(shù)相結(jié)合,利用指數(shù)機(jī)制與信息增益來(lái)確定分裂特征[20]。雖然DiffGen算法的分類準(zhǔn)確率較高,但由于每一個(gè)特征對(duì)應(yīng)一個(gè)分類樹(shù),當(dāng)數(shù)據(jù)集中的特征維度非常大時(shí),該方法需要維護(hù)大量的分類樹(shù),導(dǎo)致基于指數(shù)機(jī)制的選擇方法效率很低,并且有可能耗盡隱私保護(hù)預(yù)算。文獻(xiàn)[21]改進(jìn)DiffGen算法后提出了DT-Diff算法,該算法設(shè)計(jì)了特征模型方法選擇策略,通過(guò)構(gòu)造特征模型對(duì)樣本進(jìn)行分組,然后向數(shù)據(jù)中添加噪聲。DT-Diff算法能夠充分利用隱私保護(hù)預(yù)算,提高分類準(zhǔn)確率,但隱私保護(hù)預(yù)算分配的主觀性較大。

決策樹(shù)的構(gòu)建雖然比較簡(jiǎn)單,但是其結(jié)果可能不穩(wěn)定,數(shù)據(jù)中一個(gè)很小的變化可能會(huì)導(dǎo)致生成一個(gè)完全不同的樹(shù)[22],即對(duì)數(shù)據(jù)集的依賴性較強(qiáng),極容易出現(xiàn)過(guò)擬合問(wèn)題,擴(kuò)展性較差。為了避免該問(wèn)題,文獻(xiàn)[23]在決策樹(shù)的基礎(chǔ)上提出了隨機(jī)森林算法。隨機(jī)森林以決策樹(shù)為基學(xué)習(xí)器,利用Bagging集成的思想,在決策樹(shù)的訓(xùn)練過(guò)程中引入了隨機(jī)選擇特征。它結(jié)合分類器組合的思想,由多個(gè)決策樹(shù)構(gòu)成隨機(jī)森林[24]。由于在構(gòu)建的過(guò)程中采用了隨機(jī)采樣和隨機(jī)選擇特征,訓(xùn)練出的模型方差小,泛化能力強(qiáng)。為了在滿足隱私保護(hù)的情況下發(fā)揮隨機(jī)森林在分類方面的良好性能,將隨機(jī)森林與差分隱私保護(hù)相結(jié)合引起研究人員的廣泛關(guān)注。

文獻(xiàn)[25]將差分隱私保護(hù)應(yīng)用在隨機(jī)森林中,提出了DiffPRF算法,但它基于ID3決策樹(shù),只能處理離散型特征。文獻(xiàn)[26]對(duì)隨機(jī)森林算法進(jìn)行修改,提出了一種面向隨機(jī)森林的差分隱私保護(hù)算法DiffPRFs,在每棵決策樹(shù)構(gòu)建過(guò)程中采用指數(shù)機(jī)制選擇分裂點(diǎn)和分裂特征,并使用Laplace機(jī)制添加噪聲。DiffPRFs雖然無(wú)需對(duì)數(shù)據(jù)進(jìn)行離散化預(yù)處理,但是和Diff-C4.5相似,每次迭代同樣要調(diào)用2次指數(shù)機(jī)制,消耗了較多的隱私保護(hù)預(yù)算,導(dǎo)致隱私保護(hù)預(yù)算的利用率較低。

本文提出一種面向差分隱私保護(hù)的隨機(jī)森林算法RFDPP-Gini,該算法使用CART分類樹(shù)作為隨機(jī)森林中的單棵決策樹(shù),在選擇分裂特征時(shí),利用指數(shù)機(jī)制和Laplace機(jī)制分別處理連續(xù)型特征和離散型特征。

2 預(yù)備知識(shí)

2.1 差分隱私保護(hù)的定義及相關(guān)概念

設(shè)數(shù)據(jù)集D1和D2具有相同的屬性結(jié)構(gòu),兩者的對(duì)稱差記作D1ΔD2,s|D1ΔD2|表示D1ΔD2中的記錄數(shù)量。如果|D1ΔD2|=1,則稱D1和D2為鄰近數(shù)據(jù)集。

定義1( ε-差分隱私)[27]設(shè)有隨機(jī)函數(shù)F,Pr[ ]表示隱私被泄露的風(fēng)險(xiǎn)(概率),RRange(F)表示F的取值范圍。對(duì)于任意2個(gè)鄰近數(shù)據(jù)集D1和D2以及RRange(F)的任何子集S,若F滿足式(1),則稱該算法提供ε-差分隱私保護(hù)。

Pr[F(D1)∈S]≤exp(ε)×Pr[F(D2)∈S]

(1)

其中,exp是以e為底的指數(shù)函數(shù),參數(shù)ε稱為隱私保護(hù)預(yù)算,ε越小,隱私保護(hù)程度越高。

定義2(全局敏感度)[27]給定一個(gè)任意函數(shù)f:D→Rd,輸入為一個(gè)數(shù)據(jù)集D,輸出為一個(gè)d維實(shí)數(shù)向量,對(duì)于任意的鄰近數(shù)據(jù)集D1和D2,有:

(2)

其中,Δf稱為f的全局敏感度,R表示映射的實(shí)數(shù)空間,‖f(D1)-f(D2)‖1是f(D1)和f(D2)之間的1-階范數(shù)距離。

2.2 差分隱私保護(hù)的實(shí)現(xiàn)機(jī)制

差分隱私的主要實(shí)現(xiàn)機(jī)制是噪聲機(jī)制,Laplace機(jī)制和指數(shù)機(jī)制是最常用的2種差分隱私保護(hù)實(shí)現(xiàn)機(jī)制。噪聲機(jī)制受到全局敏感度和隱私保護(hù)預(yù)算的制約,噪聲過(guò)多將導(dǎo)致數(shù)據(jù)可用性下降,噪聲過(guò)少將導(dǎo)致數(shù)據(jù)安全性下降。

定理1(Laplace機(jī)制)[28]給定數(shù)據(jù)集D,設(shè)函數(shù)f:D→Rd,其敏感度為Δf,則隨機(jī)算法F(D)=f(D)+Y提供ε-差分隱私保護(hù),其中,Y～LLap(Δf/ε)為隨機(jī)噪聲,服從尺度參數(shù)為Δf/ε的Laplace分布。噪聲量的大小與Δf成正比,與ε成反比。

2.3 基尼指數(shù)

在選擇最佳分裂特征時(shí),信息增益對(duì)可取值數(shù)目較多的特征有所偏好,信息增益率對(duì)可取值數(shù)目較少的特征有所偏好。為了避免這種偏好帶來(lái)的不利影響,本文使用基尼指數(shù)來(lái)選擇最佳分裂特征。

定義3(基尼指數(shù))[30]在分類問(wèn)題中,假設(shè)有K個(gè)類,樣本屬于第k類的概率為pk,則概率分布的基尼指數(shù)定義為:

(3)

對(duì)于二分類問(wèn)題,若樣本點(diǎn)屬于第1類的概率是p,則概率分布的基尼指數(shù)為:

GGini(p)=2p(1-p)

(4)

對(duì)于給定的樣本集D,其基尼指數(shù)為:

(5)

其中,Ck是D中屬于第k類的樣本子集,K是類的個(gè)數(shù)。

如果樣本集D根據(jù)特征A是否取某一可能值a被分割成D1和D2兩部分,即:

D1={(x,y)∈D|A(x)=a},D2=D-D1

則在特征A的條件下,樣本集D的基尼指數(shù)定義為:

(6)

基尼指數(shù)GGini(D)表示集合的不確定性,GGini(D,A)表示經(jīng)A(x)=a分割后集合D的不確定性?；嶂笖?shù)值越大,樣本集合的不確定性就越大。

2.4 CART決策樹(shù)

CART[30]又名分類與回歸樹(shù),由BREIMAN等人在1984年提出,是一種典型的二叉決策樹(shù),可以用于分類或者回歸。如果待預(yù)測(cè)結(jié)果是離散型數(shù)據(jù),則CART生成分類決策樹(shù),如果待預(yù)測(cè)結(jié)果是連續(xù)型數(shù)據(jù),則CART生成回歸決策樹(shù)。本文使用CART分類樹(shù)作為隨機(jī)森林中的決策樹(shù)。CART分類樹(shù)用基尼指數(shù)選擇最優(yōu)分裂特征,同時(shí)決定該特征的最佳二值分裂點(diǎn)。CART分類樹(shù)的生成算法偽代碼見(jiàn)算法1。

算法1CART分類樹(shù)生成算法

輸入訓(xùn)練數(shù)據(jù)集D,樣本個(gè)數(shù)和基尼指數(shù)的停止分裂閾值

輸出CART分類樹(shù)

停止條件節(jié)點(diǎn)中的樣本個(gè)數(shù)小于預(yù)定閾值,或樣本集的基尼指數(shù)小于預(yù)定閾值,或節(jié)點(diǎn)上的全部樣本分類一致,或沒(méi)有更多特征

步驟1判斷是否達(dá)到停止條件。若是,執(zhí)行步驟5;否則,執(zhí)行步驟2。

步驟2設(shè)節(jié)點(diǎn)的訓(xùn)練數(shù)據(jù)集為Dc,計(jì)算現(xiàn)有特征對(duì)該數(shù)據(jù)集的基尼指數(shù)。對(duì)于每一個(gè)特征A,對(duì)其可能取的每個(gè)值a,根據(jù)A(x)=a是否成立將Dc劃分成D1和D2兩部分,利用式(6)計(jì)算A(x)=a時(shí)的基尼指數(shù)。

步驟3在所有可能的特征A及它們所有可能的分裂點(diǎn)a中,選擇基尼指數(shù)最小的特征及其對(duì)應(yīng)的分裂點(diǎn)作為最佳分裂特征與最佳分裂點(diǎn)。根據(jù)最佳分裂特征和最佳分裂點(diǎn)將訓(xùn)練數(shù)據(jù)集分配到2個(gè)子節(jié)點(diǎn)中。

步驟4對(duì)2個(gè)子節(jié)點(diǎn)遞歸執(zhí)行步驟1～步驟3。

步驟5生成CART分類樹(shù)。

2.5 隨機(jī)森林

隨機(jī)森林[23]是BREIMAN等人提出的一種集成學(xué)習(xí)算法,它的核心思想是對(duì)訓(xùn)練集進(jìn)行自助采樣,組成多個(gè)訓(xùn)練集,每個(gè)訓(xùn)練集生成一棵決策樹(shù),所有決策樹(shù)組成隨機(jī)森林。在分類時(shí),隨機(jī)森林中的所有決策樹(shù)通過(guò)投票的方式進(jìn)行決策,其輸出的類別由所有決策樹(shù)輸出的類別的眾數(shù)決定。隨機(jī)森林的生成流程見(jiàn)算法2。

算法2隨機(jī)森林生成算法

輸入訓(xùn)練數(shù)據(jù)集D,特征集F,特征集標(biāo)簽FFlag(離散型/連續(xù)型),決策樹(shù)數(shù)量T,決策樹(shù)的最大深度d,分裂時(shí)隨機(jī)選擇特征的個(gè)數(shù)m

輸出隨機(jī)森林

停止條件節(jié)點(diǎn)上的全部樣本分類一致,或達(dá)到?jīng)Q策樹(shù)的最大深度d

步驟1從容量為N的訓(xùn)練集D中,采用自助采樣法有放回地抽取N個(gè)樣本,作為一個(gè)訓(xùn)練集Dt。

步驟2對(duì)于當(dāng)前訓(xùn)練集Dc,從特征集F中隨機(jī)抽取m個(gè)不同的特征(Fc),其中,Dc是Dt的子集,m=「lbM?(向上取整),M=|F|。

步驟3計(jì)算Fc中各特征的信息增益/信息增益率/基尼指數(shù),從中選擇最好的特征b作為分裂特征,將當(dāng)前節(jié)點(diǎn)上的樣本按照特征b的不同取值劃分到不用子節(jié)點(diǎn),從根節(jié)點(diǎn)開(kāi)始遞歸,自下而上生成一棵決策樹(shù)。

步驟4重復(fù)步驟1～步驟3T次,得到T個(gè)訓(xùn)練子集D1,D2,…,DT,并生成T棵決策樹(shù)tree1,tree2,…,treeT,將T棵決策樹(shù)組合起來(lái)形成隨機(jī)森林。

在隨機(jī)森林生成完成后,對(duì)新樣本s進(jìn)行分類,令每棵決策樹(shù)分別對(duì)s進(jìn)行分類,然后采用多數(shù)投票法對(duì)分類結(jié)果投票,最終決定s的分類。相比其他算法,隨機(jī)森林具有如下優(yōu)點(diǎn):

1)能夠處理高維度的數(shù)據(jù),并且不用做特征選擇。

2)對(duì)數(shù)據(jù)集的適應(yīng)能力強(qiáng),既能處理離散型數(shù)據(jù),又能處理連續(xù)型數(shù)據(jù)。

3)訓(xùn)練完成后可以得到特征重要性排序。

4)由于采用了隨機(jī)采樣,訓(xùn)練出的模型方差小,泛化能力強(qiáng)。

5)容易改進(jìn)為并行化方法。

6)實(shí)現(xiàn)比較簡(jiǎn)單。

3 算法描述及性能分析

隨機(jī)森林由多個(gè)決策樹(shù)構(gòu)成,目前主要決策樹(shù)有ID3、C4.5和CART。ID3決策樹(shù)可以有多個(gè)分支,但是不能處理連續(xù)型特征[31]。在選擇最佳分裂特征時(shí),ID3使用信息增益作為度量指標(biāo),信息增益反映在條件給定后不確定性減少的程度,分得越細(xì)的數(shù)據(jù)集確定性越高,因此,信息增益對(duì)可取值數(shù)目較多的特征有所偏好。為減少這種偏好帶來(lái)的不利影響,C4.5決策樹(shù)不直接使用信息增益,而使用信息增益率來(lái)選擇最佳分裂特征,但是信息增益率對(duì)可取值數(shù)目較少的特征有所偏好[32]。在構(gòu)造決策樹(shù)的過(guò)程中,需要多次對(duì)數(shù)據(jù)集進(jìn)行掃描和排序,因而降低了算法的效率。此外,ID3和C4.5根據(jù)特征取值分割數(shù)據(jù),之后該特征不會(huì)再起作用,這種快速分割的方式會(huì)影響算法的準(zhǔn)確率。

相比ID3和C4.5,CART決策樹(shù)是一棵二叉樹(shù),其采用二元切分法,每次將數(shù)據(jù)分成兩份,分別進(jìn)入左子樹(shù)和右子樹(shù)。CART決策樹(shù)既可以用于分類也可以用于回歸,故既能處理離散型特征又能處理連續(xù)型特征。在CART分類時(shí),使用基尼指數(shù)來(lái)選擇最佳分裂特征,避免由信息增益和信息增益率對(duì)特征取值數(shù)目有所偏好帶來(lái)的影響[29]。因此,使用CART算法構(gòu)建隨機(jī)森林比ID3、C4.5更有優(yōu)勢(shì)。

3.1 算法描述

本文提出的面向差分隱私保護(hù)的隨機(jī)森林算法RFDPP-Gini,使用CART分類樹(shù)作為隨機(jī)森林中的單個(gè)決策樹(shù),將差分隱私保護(hù)與隨機(jī)森林相結(jié)合,從而保護(hù)數(shù)據(jù)集中的隱私信息,并對(duì)數(shù)據(jù)的可用性和分類準(zhǔn)確率形成較小影響。面向差分隱私保護(hù)的隨機(jī)森林算法建立過(guò)程如算法3所示。

算法3滿足ε-差分隱私保護(hù)的隨機(jī)森林建立算法

輸入訓(xùn)練數(shù)據(jù)集D,特征集F,特征集標(biāo)簽FFlag(離散型/連續(xù)型),隱私保護(hù)預(yù)算B,決策樹(shù)數(shù)量T,決策樹(shù)的最大深度d,分裂時(shí)隨機(jī)選擇特征的個(gè)數(shù)m

輸出滿足ε-差分隱私保護(hù)的隨機(jī)森林

停止條件節(jié)點(diǎn)上的全部樣本分類一致,或達(dá)到?jīng)Q策樹(shù)的最大深度d,或隱私保護(hù)預(yù)算耗盡

步驟3fort= 1 toT

1)使用自助采樣法從D中選取大小為|D|的訓(xùn)練集Dt。

2)遞歸執(zhí)行以下步驟建立隨機(jī)森林中的決策樹(shù)RFTt:

(1)如果節(jié)點(diǎn)達(dá)到停止條件,設(shè)置當(dāng)前節(jié)點(diǎn)為葉子節(jié)點(diǎn),并使用Laplace機(jī)制添加噪聲,對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行分類。

(2)計(jì)算當(dāng)前節(jié)點(diǎn)訓(xùn)練集Dc中的樣本數(shù)量,使用Laplace機(jī)制添加噪聲NDc=NoisyCount(|Dc|),其中,Dc是Dt的子集。

(3)從特征集F中隨機(jī)選取m個(gè)特征(Fc)。

(4)若Fc中含有n(n>0)個(gè)連續(xù)屬性,執(zhí)行步驟(5);否則,執(zhí)行步驟(6)。

(5)將隱私保護(hù)預(yù)算分配到每個(gè)連續(xù)型特征,并保留一份給離散型特征,ε=ε/(n+1),用以下概率選擇最佳連續(xù)型特征及其分裂點(diǎn),并計(jì)算對(duì)應(yīng)的基尼指數(shù):

其中,q(Dc,F)是基尼指數(shù),Δq是基尼指數(shù)的全局敏感度,R是由數(shù)據(jù)集中出現(xiàn)的值構(gòu)成的區(qū)間集合,|Ri|是區(qū)間大小。

(6)計(jì)算Fc中各離散型特征以不同分裂方式進(jìn)行分裂時(shí)對(duì)應(yīng)的基尼指數(shù),與最佳的連續(xù)型特征對(duì)應(yīng)的基尼指數(shù)進(jìn)行比較,選擇使Fc中基尼指數(shù)最小的分裂特征和分裂點(diǎn),根據(jù)該特征及其最佳分裂點(diǎn),將當(dāng)前節(jié)點(diǎn)分為2個(gè)子節(jié)點(diǎn),并對(duì)每個(gè)子節(jié)點(diǎn)執(zhí)行步驟(1)～步驟(6)。

在使用算法3生成滿足ε-差分隱私保護(hù)的隨機(jī)森林后,就可利用生成的隨機(jī)森林對(duì)新樣本進(jìn)行分類。對(duì)新樣本進(jìn)行分類的過(guò)程如算法4所示。

算法4利用滿足ε-差分隱私保護(hù)的隨機(jī)森林對(duì)新樣本進(jìn)行分類的算法

輸入待分類樣本s,滿足ε-差分隱私保護(hù)的隨機(jī)森林

輸出待分類樣本s的分類結(jié)果

停止條件到達(dá)葉子節(jié)點(diǎn)

步驟1對(duì)于隨機(jī)森林中的每棵樹(shù)Rt:

1)輸入樣本s。

2)從Rt的根節(jié)點(diǎn)開(kāi)始,根據(jù)當(dāng)前節(jié)點(diǎn)的類型(葉子節(jié)點(diǎn)/中間節(jié)點(diǎn))、最佳分裂特征的類別(離散/連續(xù))及其分裂點(diǎn)、s在當(dāng)前節(jié)點(diǎn)最佳分裂特征上的取值,來(lái)判斷進(jìn)入哪一個(gè)子節(jié)點(diǎn),直到到達(dá)某個(gè)葉子節(jié)點(diǎn)。

3)得到Rt對(duì)s的分類結(jié)果Ct(s)。

步驟3輸出樣本s的分類結(jié)果C(s)。

3.2 算法的性能分析

3.2.1 隱私性

本文提出的面向差分隱私保護(hù)的隨機(jī)森林算法RFDPP-Gini,將給定的隱私保護(hù)預(yù)算B平均分配給隨機(jī)森林中的T棵樹(shù),ε′=B/T,由于每棵樹(shù)中的樣本是有放回隨機(jī)選擇的,因此會(huì)有一定的交叉,根據(jù)差分隱私保護(hù)的序列組合性,消耗的隱私保護(hù)預(yù)算為每棵決策樹(shù)消耗的隱私保護(hù)預(yù)算的疊加。樹(shù)中的每一層平均分配隱私保護(hù)預(yù)算ε′[18],即ε″=ε′/(d+1),而每層中的節(jié)點(diǎn)在不相交的數(shù)據(jù)集上進(jìn)行計(jì)數(shù)和分裂,因此,每個(gè)節(jié)點(diǎn)分到的隱私保護(hù)預(yù)算就是這一層的隱私保護(hù)預(yù)算,節(jié)點(diǎn)的隱私保護(hù)預(yù)算不進(jìn)行累加。分給每個(gè)節(jié)點(diǎn)的隱私保護(hù)預(yù)算再平均分成兩半,ε=ε″/2,一半用來(lái)估計(jì)訓(xùn)練集中的樣本數(shù)量,另一半根據(jù)該節(jié)點(diǎn)是中間節(jié)點(diǎn)還是葉子節(jié)點(diǎn)執(zhí)行不同的操作。如果該節(jié)點(diǎn)為葉子節(jié)點(diǎn),則用另一半隱私保護(hù)預(yù)算結(jié)合Laplace機(jī)制對(duì)計(jì)數(shù)值添加噪聲,確定葉子節(jié)點(diǎn)的類別;如果該節(jié)點(diǎn)為中間節(jié)點(diǎn),則用另一半隱私保護(hù)預(yù)算結(jié)合指數(shù)機(jī)制和Laplace機(jī)制選擇最佳分裂特征和最佳分裂點(diǎn)[18,25]。綜上所述,本文算法消耗的全部隱私保護(hù)預(yù)算不大于B,且能夠提供ε-差分隱私保護(hù)。

3.2.2 分類準(zhǔn)確率

隨機(jī)森林作為一種集成學(xué)習(xí)算法,在決策樹(shù)的基礎(chǔ)上結(jié)合了多個(gè)分類器的結(jié)果。在訓(xùn)練過(guò)程中,每次對(duì)訓(xùn)練集進(jìn)行重采樣,生成多個(gè)訓(xùn)練集,每個(gè)訓(xùn)練集生成一棵決策樹(shù)。由于訓(xùn)練集不同,因此生成的決策樹(shù)模型不同。而在選擇最佳分裂特征時(shí)引入了隨機(jī)選擇特征,使得相同的訓(xùn)練集生成的決策樹(shù)模型也可能不同。隨機(jī)森林中決策樹(shù)的多樣性不僅來(lái)自訓(xùn)練集中的隨機(jī)樣本,還來(lái)自隨機(jī)特征,這使得隨機(jī)森林的泛化性能可以通過(guò)決策樹(shù)之間的差異而進(jìn)一步提升,從而避免了單個(gè)決策樹(shù)容易出現(xiàn)過(guò)擬合的問(wèn)題。因此,隨機(jī)性的引入使得隨機(jī)森林具有較強(qiáng)的抗噪聲能力,在利用差分隱私保護(hù)實(shí)現(xiàn)機(jī)制添加噪聲后,隨機(jī)森林仍然具有良好的性能。綜上,使用本文RFDPP-Gini算法可以得到較高的分類準(zhǔn)確率。

3.2.3 適用性

ID3決策樹(shù)不能處理連續(xù)型特征,C4.5決策樹(shù)雖然可以處理連續(xù)型特征,但是其在選擇最佳分裂特征時(shí)選用的度量指標(biāo)(信息增益率)對(duì)取值數(shù)目較少的特征有所偏好。而CART決策樹(shù)既能處理離散型特征又能處理連續(xù)型特征,且消除了特征取值數(shù)目偏好的影響,因此,CART決策樹(shù)的適用性比ID3和C4.5更好。隨機(jī)森林無(wú)需進(jìn)行特征選擇就能處理很高維度的數(shù)據(jù)。因此,隨機(jī)森林、CART分類樹(shù)和差分隱私保護(hù)相結(jié)合,使得RFDPP-Gini算法能夠處理離散型數(shù)據(jù)、連續(xù)型數(shù)據(jù)和高維數(shù)據(jù),算法的適用性較強(qiáng)。

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

4.1 實(shí)驗(yàn)設(shè)計(jì)

本文用Python語(yǔ)言實(shí)現(xiàn)面向差分隱私保護(hù)的隨機(jī)森林算法RFDPP-Gini。在實(shí)驗(yàn)數(shù)據(jù)方面,采用了UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中的Adult數(shù)據(jù)集和Mushroom數(shù)據(jù)集,如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集信息

Adult數(shù)據(jù)集中包含48 842條樣本數(shù)據(jù),刪除含有缺失值的樣本后,得到45 222條樣本數(shù)據(jù),30 162條用于訓(xùn)練,15 060條用于測(cè)試。每條樣本含有14個(gè)分類特征和1個(gè)分類結(jié)果,其中包括6個(gè)連續(xù)型特征和8個(gè)離散型特征。Mushroom數(shù)據(jù)集中包含8 124條樣本數(shù)據(jù),含有22個(gè)分類特征和1個(gè)分類結(jié)果,全部都為離散型特征。

為檢驗(yàn)RFDPP-Gini算法的有效性,本文設(shè)置了多組對(duì)比:1)添加噪聲和不添加噪聲之間的對(duì)比;2)不同的決策樹(shù)深度之間的對(duì)比;3)不同的隱私保護(hù)預(yù)算(即添加不同噪聲)之間的對(duì)比;4)本文RFDPP-Gini算法與DiffPRFs算法[26]的對(duì)比。在實(shí)驗(yàn)參數(shù)方面,本文設(shè)置決策樹(shù)的數(shù)量T=25,節(jié)點(diǎn)分裂時(shí)隨機(jī)選擇特征的個(gè)數(shù)m=5。設(shè)置樹(shù)的深度(簡(jiǎn)寫(xiě)為d)分別為3、4、5、6、7、8、9和10,以比較決策樹(shù)的不同深度對(duì)分類準(zhǔn)確率的影響。為對(duì)比不同的隱私保護(hù)預(yù)算ε對(duì)分類準(zhǔn)確率的影響,將ε分別設(shè)置為0.05、0.10、0.25、0.50、0.75和1.00,計(jì)算ε取不同值時(shí)的分類準(zhǔn)確率[26]。

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

針對(duì)Adult數(shù)據(jù)集,在不同隱私保護(hù)預(yù)算(ε)和決策樹(shù)深度(d)情況下,使用本文RFDPP-Gini算法建立滿足ε-差分隱私保護(hù)的隨機(jī)森林,并用生成的隨機(jī)森林對(duì)測(cè)試數(shù)據(jù)集進(jìn)行分類,得到的最終分類準(zhǔn)確率(AAccuracy)如表2所示。Mushroom數(shù)據(jù)集使用RFDPP-Gini算法得到的分類準(zhǔn)確率如表3所示。其中,“no_noise”表示不添加噪聲。為更直觀地觀察分類準(zhǔn)確率的差別,根據(jù)表2、表3所示結(jié)果,繪制折線圖如圖1～圖4所示。

表2 Adult數(shù)據(jù)集的分類準(zhǔn)確率

表3 Mushroom數(shù)據(jù)集的分類準(zhǔn)確率

圖1 Adult數(shù)據(jù)集分類準(zhǔn)確率隨樹(shù)深度的變化情況

Fig.1 Classification accuracy of Adult dataset varying with the tree depth

圖2 Mushroom數(shù)據(jù)集分類準(zhǔn)確率隨樹(shù)深度的變化情況

Fig.2 Classification accuracy of Mushroom dataset varying with the tree depth

圖3 Adult數(shù)據(jù)集分類準(zhǔn)確率隨隱私保護(hù)預(yù)算的變化情況

Fig.3 Classification accuracy of Adult dataset varying with the privacy protection budget

圖4 Mushroom數(shù)據(jù)集分類準(zhǔn)確率隨隱私保護(hù)預(yù)算的變化情況

Fig.4 Classification accuracy of Mushroom dataset varying with the privacy protection budget

圖1是Adult數(shù)據(jù)集不添加噪聲(no_noise)和添加噪聲且隱私保護(hù)預(yù)算分別為0.05、0.10、0.25、0.50、0.75、1.00時(shí),在不同樹(shù)深度下的分類準(zhǔn)確率。圖2是Mushroom數(shù)據(jù)集不添加噪聲和添加噪聲且隱私保護(hù)預(yù)算分別為0.05、0.10、0.25、0.50、0.75、1.00時(shí),在不同樹(shù)深度下的分類準(zhǔn)確率。圖3是Adult數(shù)據(jù)集在樹(shù)的深度分別為3、4、5、6、7、8、9、10時(shí),在不同隱私保護(hù)預(yù)算ε下的分類準(zhǔn)確率。圖4是Mushroom數(shù)據(jù)集在樹(shù)深度分別為3、4、5、6、7、8、9、10時(shí),在不同隱私保護(hù)預(yù)算ε下的分類準(zhǔn)確率。

為評(píng)估本文算法的性能,將其與DiffPRFs算法在相同條件下對(duì)于Adult數(shù)據(jù)集的分類準(zhǔn)確率進(jìn)行對(duì)比。設(shè)置決策樹(shù)的數(shù)量T=25,決策樹(shù)的深度d=5,ε設(shè)置為0.10、0.25、0.50、0.75、1.00,分別計(jì)算RFDPP-Gini算法與DiffPRFs算法的分類準(zhǔn)確率,其中,DiffPRFs算法同等條件下的分類準(zhǔn)確率由文獻(xiàn)[26]提供,文獻(xiàn)[26]選擇了2個(gè)度量指標(biāo)來(lái)選擇最佳分裂特征:信息增益(DiffPRFs-IG)和Max Operator(DiffPRFs-Max)。實(shí)驗(yàn)結(jié)果如圖5所示。

圖5 2種算法在Adult數(shù)據(jù)集上的分類準(zhǔn)確率對(duì)比

Fig.5 Comparison of classification accuracy of 2 algorithms on the Adult dataset

5 分析與討論

根據(jù)ε-差分隱私保護(hù)的定義和實(shí)現(xiàn)機(jī)制,隱私保護(hù)預(yù)算ε的大小決定了所添加噪聲的大小。噪聲的大小與ε成反比,ε越大,添加的噪聲越小,隱私保護(hù)能力越差;ε越小,添加的噪聲越大,隱私保護(hù)能力越強(qiáng)。在決策樹(shù)中,決策樹(shù)的深度越大,分支越多,對(duì)數(shù)據(jù)集的劃分程度越細(xì),劃分結(jié)果越準(zhǔn)確。因此,面向差分隱私保護(hù)的隨機(jī)森林算法RFDPP-Gini的分類準(zhǔn)確率受隱私保護(hù)預(yù)算ε和決策樹(shù)深度d的雙重影響。

從表2、表3可以看出,樹(shù)的深度d=3,隱私保護(hù)預(yù)算ε分別為0.05、0.10、0.25、0.50、0.75、1.00時(shí),RFDPP-Gini算法對(duì)于Adult數(shù)據(jù)集的分類準(zhǔn)確率分別為84.162%、84.282%、84.299%、84.312%、84.363%、84.436%和84.590%,對(duì)于Mushroom數(shù)據(jù)集的分類準(zhǔn)確率分別為99.840%、99.914%、99.947%、99.954%、99.963%、99.965%和99.975%,都是逐步提高。當(dāng)樹(shù)為其他深度時(shí),該算法對(duì)于2個(gè)數(shù)據(jù)集的分類準(zhǔn)確率變化趨勢(shì)同樣如此。從中可以發(fā)現(xiàn),當(dāng)決策樹(shù)的深度相同時(shí),隱私保護(hù)預(yù)算ε越大,對(duì)數(shù)據(jù)的可用性影響越小,分類準(zhǔn)確率越高;反之,隱私保護(hù)預(yù)算ε越小,對(duì)數(shù)據(jù)的可用性影響越大,分類準(zhǔn)確率越低,如圖1、圖2所示。此外,表2、表3也顯示,當(dāng)隱私保護(hù)預(yù)算為0.05,樹(shù)的深度分別為3、4、5、6、7、8、9、10時(shí),RFDPP-Gini算法對(duì)于Adult數(shù)據(jù)集的分類準(zhǔn)確率分別為84.162%、84.603%、85.296%、85.589%、85.719%、85.902%、86.010%和86.120%,對(duì)于Mushroom數(shù)據(jù)集的分類準(zhǔn)確率分別為99.840%、99.951%、99.975%、99.999%、100.000%、100.000%、100.000%和100.000%,都是逐步提升并穩(wěn)定,當(dāng)隱私保護(hù)預(yù)算設(shè)置為其他值時(shí),情況也是如此。從中可以發(fā)現(xiàn),當(dāng)隱私保護(hù)預(yù)算ε相同時(shí),決策樹(shù)的深度越大,分類準(zhǔn)確率越高,如圖3、圖4所示。因此,當(dāng)隨機(jī)森林中決策樹(shù)的深度較小時(shí),由于決策樹(shù)對(duì)數(shù)據(jù)集的劃分比較粗糙,分類準(zhǔn)確率主要受隱私保護(hù)預(yù)算ε的影響,ε越小,添加的噪聲越大,對(duì)數(shù)據(jù)的可用性影響越大,分類準(zhǔn)確率越低,對(duì)隱私的保護(hù)程度越高;ε越大,添加的噪聲越小,對(duì)數(shù)據(jù)的可用性影響越小,分類準(zhǔn)確率越高,對(duì)隱私的保護(hù)程度越低。隨著決策樹(shù)深度的增加,決策樹(shù)對(duì)數(shù)據(jù)集的劃分越來(lái)越精細(xì),分類結(jié)果越來(lái)越準(zhǔn)確,導(dǎo)致分類準(zhǔn)確率主要受深度的影響,深度越大,分類準(zhǔn)確率越高。

給定訓(xùn)練數(shù)據(jù)集D和特征A,信息增益表示由于特征A而使得對(duì)數(shù)據(jù)集D的分類不確定性減少的程度。顯然,信息增益依賴于特征,特征的取值越多,在構(gòu)建決策樹(shù)時(shí)劃分得越細(xì),數(shù)據(jù)集的不確定性越低。因此,信息增益偏好可取值數(shù)目較多的特征,這種偏好可能會(huì)帶來(lái)不利的影響。Max Operator通過(guò)選擇具有最高頻率的類來(lái)選擇最佳分裂特征[33-34],即選擇使得某個(gè)分類結(jié)果具有最多樣本數(shù)量的特征。使用Laplace機(jī)制對(duì)樣本數(shù)量添加噪聲時(shí),樣本數(shù)量受噪聲的影響較大,導(dǎo)致生成的決策樹(shù)不能反映數(shù)據(jù)集的真實(shí)情況,分類準(zhǔn)確率較低。而基尼指數(shù)對(duì)特征的可取值數(shù)目沒(méi)有偏好,并且在計(jì)算過(guò)程中用到了多次相除運(yùn)算,相比Max Operator受噪聲的影響更小,因此,使用基尼指數(shù)作為選擇最佳分裂特征時(shí)的度量指標(biāo),可以取得比信息增益和Max Operator更好的結(jié)果。本文實(shí)驗(yàn)結(jié)果(圖5)反映出RFDPP-Gini算法具有更高的分類準(zhǔn)確率,說(shuō)明該算法具有良好的分類與隱私保護(hù)性能。

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

本文提出一種面向差分隱私保護(hù)的隨機(jī)森林算法RFDPP-Gini。在隨機(jī)森林中加入差分隱私保護(hù),可以在分類時(shí)保護(hù)數(shù)據(jù)中的隱私信息,并且對(duì)分類準(zhǔn)確率造成較小影響。通過(guò)將基尼指數(shù)作為分裂特征選擇時(shí)的度量指標(biāo)、CART分類樹(shù)作為隨機(jī)森林中的單個(gè)決策樹(shù),使RFDPP-Gini算法既能處理離散型特征又能處理連續(xù)型特征,并且消除了信息增益對(duì)可取值數(shù)目較多的特征有所偏好和信息增益率對(duì)可取值數(shù)目較少的特征有所偏好的影響。通過(guò)在處理連續(xù)型特征時(shí)只調(diào)用一次指數(shù)機(jī)制的方式,提高了隱私保護(hù)預(yù)算的利用率。實(shí)驗(yàn)結(jié)果驗(yàn)證了RFDPP-Gini算法良好的隱私保護(hù)性能。下一步將在AdaBoost、GBDT等其他集成學(xué)習(xí)算法中應(yīng)用差分隱私保護(hù),以獲得更高的分類準(zhǔn)確率。