面向差分隱私保護的隨機森林算法

李遠航,陳先來,劉 莉,安 瑩,李忠民

(中南大學 a.計算機學院; b.醫療大數據應用技術國家工程實驗室; c.信息安全與大數據研究院,長沙 410083)

0 概述

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

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

本文將差分隱私保護與隨機森林算法相結合,構造滿足差分隱私保護要求的隨機森林算法,以在保護數據中隱私信息的同時,使隨機森林算法仍然保持較高的分類準確率。

1 相關工作

在數據挖掘中,應用差分隱私保護的目的是在提取有價值信息的同時不泄露敏感隱私信息。決策樹是一類常見的分類模型[14],在數據挖掘分析中起著至關重要的作用。在決策樹中應用差分隱私保護,可以在分類的同時保護數據中的隱私信息[15]。

文獻[16]提出了應用差分隱私保護的決策樹構建算法SuLQ-based ID3,其主要思想是在每次計算特征的信息增益時使用Laplace機制添加噪聲,然后生成決策樹,但在加入噪音后導致了預測結果準確率大幅下降。文獻[17]對SuLQ-based ID3做了改進,提出了PINQ-based ID3算法。該算法使用Partition算子將數據集分割成不相交的子集,利用其計算時并行組合性的特點,提高隱私保護預算的利用率。該算法直接利用噪聲計數值評估信息增益,再使用ID3算法生成決策樹。由于需要對每個特征計算信息增益的計數值,因此需要將隱私保護預算分配到每次查詢中,導致每次查詢的隱私保護預算較小,當數據集較大時會引入大量噪聲。

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

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

決策樹的構建雖然比較簡單,但是其結果可能不穩定,數據中一個很小的變化可能會導致生成一個完全不同的樹[22],即對數據集的依賴性較強,極容易出現過擬合問題,擴展性較差。為了避免該問題,文獻[23]在決策樹的基礎上提出了隨機森林算法。隨機森林以決策樹為基學習器,利用Bagging集成的思想,在決策樹的訓練過程中引入了隨機選擇特征。它結合分類器組合的思想,由多個決策樹構成隨機森林[24]。由于在構建的過程中采用了隨機采樣和隨機選擇特征,訓練出的模型方差小,泛化能力強。為了在滿足隱私保護的情況下發揮隨機森林在分類方面的良好性能,將隨機森林與差分隱私保護相結合引起研究人員的廣泛關注。

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

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

2 預備知識

2.1 差分隱私保護的定義及相關概念

設數據集D1和D2具有相同的屬性結構,兩者的對稱差記作D1ΔD2,s|D1ΔD2|表示D1ΔD2中的記錄數量。如果|D1ΔD2|=1,則稱D1和D2為鄰近數據集。

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

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

(1)

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

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

(2)

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

2.2 差分隱私保護的實現機制

差分隱私的主要實現機制是噪聲機制,Laplace機制和指數機制是最常用的2種差分隱私保護實現機制。噪聲機制受到全局敏感度和隱私保護預算的制約,噪聲過多將導致數據可用性下降,噪聲過少將導致數據安全性下降。

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

2.3 基尼指數

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

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

(3)

對于二分類問題,若樣本點屬于第1類的概率是p,則概率分布的基尼指數為:

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

(4)

對于給定的樣本集D,其基尼指數為:

(5)

其中,Ck是D中屬于第k類的樣本子集,K是類的個數。

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

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

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

(6)

基尼指數GGini(D)表示集合的不確定性,GGini(D,A)表示經A(x)=a分割后集合D的不確定性。基尼指數值越大,樣本集合的不確定性就越大。

2.4 CART決策樹

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

算法1CART分類樹生成算法

輸入訓練數據集D,樣本個數和基尼指數的停止分裂閾值

輸出CART分類樹

停止條件節點中的樣本個數小于預定閾值,或樣本集的基尼指數小于預定閾值,或節點上的全部樣本分類一致,或沒有更多特征

步驟1判斷是否達到停止條件。若是,執行步驟5;否則,執行步驟2。

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

步驟3在所有可能的特征A及它們所有可能的分裂點a中,選擇基尼指數最小的特征及其對應的分裂點作為最佳分裂特征與最佳分裂點。根據最佳分裂特征和最佳分裂點將訓練數據集分配到2個子節點中。

步驟4對2個子節點遞歸執行步驟1～步驟3。

步驟5生成CART分類樹。

2.5 隨機森林

隨機森林[23]是BREIMAN等人提出的一種集成學習算法,它的核心思想是對訓練集進行自助采樣,組成多個訓練集,每個訓練集生成一棵決策樹,所有決策樹組成隨機森林。在分類時,隨機森林中的所有決策樹通過投票的方式進行決策,其輸出的類別由所有決策樹輸出的類別的眾數決定。隨機森林的生成流程見算法2。

算法2隨機森林生成算法

輸入訓練數據集D,特征集F,特征集標簽FFlag(離散型/連續型),決策樹數量T,決策樹的最大深度d,分裂時隨機選擇特征的個數m

輸出隨機森林

停止條件節點上的全部樣本分類一致,或達到決策樹的最大深度d

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

步驟2對于當前訓練集Dc,從特征集F中隨機抽取m個不同的特征(Fc),其中,Dc是Dt的子集,m=「lbM?(向上取整),M=|F|。

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

步驟4重復步驟1～步驟3T次,得到T個訓練子集D1,D2,…,DT,并生成T棵決策樹tree1,tree2,…,treeT,將T棵決策樹組合起來形成隨機森林。

在隨機森林生成完成后,對新樣本s進行分類,令每棵決策樹分別對s進行分類,然后采用多數投票法對分類結果投票,最終決定s的分類。相比其他算法,隨機森林具有如下優點:

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

2)對數據集的適應能力強,既能處理離散型數據,又能處理連續型數據。

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

4)由于采用了隨機采樣,訓練出的模型方差小,泛化能力強。

5)容易改進為并行化方法。

6)實現比較簡單。

3 算法描述及性能分析

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

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

3.1 算法描述

本文提出的面向差分隱私保護的隨機森林算法RFDPP-Gini,使用CART分類樹作為隨機森林中的單個決策樹,將差分隱私保護與隨機森林相結合,從而保護數據集中的隱私信息,并對數據的可用性和分類準確率形成較小影響。面向差分隱私保護的隨機森林算法建立過程如算法3所示。

算法3滿足ε-差分隱私保護的隨機森林建立算法

輸入訓練數據集D,特征集F,特征集標簽FFlag(離散型/連續型),隱私保護預算B,決策樹數量T,決策樹的最大深度d,分裂時隨機選擇特征的個數m

輸出滿足ε-差分隱私保護的隨機森林

停止條件節點上的全部樣本分類一致,或達到決策樹的最大深度d,或隱私保護預算耗盡

步驟3fort= 1 toT

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

2)遞歸執行以下步驟建立隨機森林中的決策樹RFTt:

(1)如果節點達到停止條件,設置當前節點為葉子節點,并使用Laplace機制添加噪聲,對當前節點進行分類。

(2)計算當前節點訓練集Dc中的樣本數量,使用Laplace機制添加噪聲NDc=NoisyCount(|Dc|),其中,Dc是Dt的子集。

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

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

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

其中,q(Dc,F)是基尼指數,Δq是基尼指數的全局敏感度,R是由數據集中出現的值構成的區間集合,|Ri|是區間大小。

(6)計算Fc中各離散型特征以不同分裂方式進行分裂時對應的基尼指數,與最佳的連續型特征對應的基尼指數進行比較,選擇使Fc中基尼指數最小的分裂特征和分裂點,根據該特征及其最佳分裂點,將當前節點分為2個子節點,并對每個子節點執行步驟(1)～步驟(6)。

在使用算法3生成滿足ε-差分隱私保護的隨機森林后,就可利用生成的隨機森林對新樣本進行分類。對新樣本進行分類的過程如算法4所示。

算法4利用滿足ε-差分隱私保護的隨機森林對新樣本進行分類的算法

輸入待分類樣本s,滿足ε-差分隱私保護的隨機森林

輸出待分類樣本s的分類結果

停止條件到達葉子節點

步驟1對于隨機森林中的每棵樹Rt:

1)輸入樣本s。

2)從Rt的根節點開始,根據當前節點的類型(葉子節點/中間節點)、最佳分裂特征的類別(離散/連續)及其分裂點、s在當前節點最佳分裂特征上的取值,來判斷進入哪一個子節點,直到到達某個葉子節點。

3)得到Rt對s的分類結果Ct(s)。

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

3.2 算法的性能分析

3.2.1 隱私性

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

3.2.2 分類準確率

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

3.2.3 適用性

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

4 實驗結果與分析

4.1 實驗設計

本文用Python語言實現面向差分隱私保護的隨機森林算法RFDPP-Gini。在實驗數據方面,采用了UCI機器學習數據庫中的Adult數據集和Mushroom數據集,如表1所示。

表1 實驗數據集信息

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

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

4.2 實驗結果

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

表2 Adult數據集的分類準確率

表3 Mushroom數據集的分類準確率

圖1 Adult數據集分類準確率隨樹深度的變化情況

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

圖2 Mushroom數據集分類準確率隨樹深度的變化情況

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

圖3 Adult數據集分類準確率隨隱私保護預算的變化情況

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

圖4 Mushroom數據集分類準確率隨隱私保護預算的變化情況

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

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

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

圖5 2種算法在Adult數據集上的分類準確率對比

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

5 分析與討論

根據ε-差分隱私保護的定義和實現機制,隱私保護預算ε的大小決定了所添加噪聲的大小。噪聲的大小與ε成反比,ε越大,添加的噪聲越小,隱私保護能力越差;ε越小,添加的噪聲越大,隱私保護能力越強。在決策樹中,決策樹的深度越大,分支越多,對數據集的劃分程度越細,劃分結果越準確。因此,面向差分隱私保護的隨機森林算法RFDPP-Gini的分類準確率受隱私保護預算ε和決策樹深度d的雙重影響。

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

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

6 結束語

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