基于差分隱私下包外估計的隨機森林算法

李玉強，陳鋆昊，李 琦，劉愛華

(1.武漢理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，武漢 430063； 2.武漢理工大學(xué) 能源與動力工程學(xué)院，武漢 430063)

隨著大數(shù)據(jù)時代的來臨，在利用各種新技術(shù)把生活中豐富的數(shù)據(jù)搜集存儲起來，以便于進行研究的同時，個人隱私數(shù)據(jù)的泄露也成為了當(dāng)今社會的一大問題[1].近年來，隱私泄露事故的不斷發(fā)生在國內(nèi)外都造成了很大的社會恐慌，如2018年3月15日，F(xiàn)acebook被曝涉嫌泄露用戶隱私數(shù)據(jù)，帶來了嚴重的經(jīng)濟問題和不良的社會影響.于是，隱私保護問題引起了人們的高度重視，尤其在數(shù)據(jù)挖掘領(lǐng)域，當(dāng)數(shù)據(jù)挖掘者對數(shù)據(jù)進行研究處理并獲取有價值的信息時，必然會給數(shù)據(jù)集中的隱私信息帶來泄露的風(fēng)險[2-3].因此差分隱私[4]以其嚴格性在數(shù)據(jù)挖掘領(lǐng)域得到了廣泛的應(yīng)用[5].其中隨機森林作為數(shù)據(jù)挖掘領(lǐng)域中一種重要的分類方法，在數(shù)據(jù)預(yù)測分析中起著關(guān)鍵作用[6]，將差分隱私技術(shù)應(yīng)用到隨機森林算法中可以保護數(shù)據(jù)的隱私性，但是這樣必然會造成算法分類準確率的大幅度下降，尤其是對高維數(shù)據(jù)進行分類的時候，對此研究者們做了許多工作.

Jagannathan等[7]最早將差分隱私保護應(yīng)用在隨機森林中， Patil 和Singh[8]進一步提出了一種保證差分隱私條件下的多類別分類算法(DiffPRF)，但是沒有提出進一步的改進方法.穆海蓉等[9]在此基礎(chǔ)上對算法進行了改進，提出了一種面向隨機森林的差分隱私保護算法(DiffPRFs)，該算法利用指數(shù)機制在結(jié)點劃分時選擇分裂特征和分裂值，從而降低了因離散化預(yù)處理而產(chǎn)生的系統(tǒng)性能消耗，但是兩次調(diào)用指數(shù)機制使得隱私預(yù)算過小，導(dǎo)致噪聲過大，從而降低了隨機森林的分類準確率.為了提高算法的分類準確率，Xin等[10]通過劃分不相交的子集，再利用差分隱私的并行組合性提高決策樹的隱私預(yù)算，提出了差分隱私貪婪決策森林算法(DPGDF).但是子集數(shù)量受到數(shù)據(jù)數(shù)量和隱私預(yù)算限制，在子集數(shù)量很小的情況下此算法會退化為決策樹算法，這也意味著該算法本質(zhì)上為決策樹算法，不具備隨機森林算法的隨機性.在前人研究的基礎(chǔ)上，Xiang等[11]提出了差分隱私下的協(xié)作隨機森林算法(CRFsDP)，該算法用驗證集來計算決策樹權(quán)重，并對決策樹進行后剪枝處理，將剪掉的分支的隱私預(yù)算分配給父結(jié)點以達到減少噪聲、提升分類性能的效果.但是需要先生成滿二叉樹，這使得算法的時間復(fù)雜度較高，另外通過驗證集得到的決策樹權(quán)重不能精確地估計決策樹的分類效果.

因此，在決策樹權(quán)重計算和剪枝方式上還有待改進，這也導(dǎo)致這些算法在具有高維度的數(shù)據(jù)集上的分類效果仍然不太理想.而如何在差分隱私下對具有高維度的數(shù)據(jù)集進行更精確地分類，一直是研究者們研究的重點[12].

針對未添加差分隱私的隨機森林算法中特征篩選和決策樹篩選的方面，Paul 等[13]提出了一種改進的隨機森林算法(IRF)，利用包外估計[14]計算決策樹權(quán)重和特征權(quán)重，然后通過不斷迭代更新，選擇表現(xiàn)良好的特征以及決策樹.但是該算法沒有應(yīng)用差分隱私保護，不受隱私預(yù)算限制，可以不斷迭代.而在差分隱私保護機制下需要預(yù)先向決策樹分配隱私預(yù)算，所以需要在有限的迭代次數(shù)中完成；同時為了保護數(shù)據(jù)隱私，包外估計也更需要加入差分隱私保護.

鑒于此，本文通過引入差分隱私下的包外估計，計算決策樹權(quán)重以及特征權(quán)重，從而提出一種基于差分隱私下包外估計的隨機森林算法(RFDP_OOB).一方面利用特征權(quán)重減少決策結(jié)點上非重要特征的使用，并以此來指導(dǎo)先剪枝操作，進而在較低時間復(fù)雜度的前提下提高決策樹的分類準確率；另一方面利用決策樹權(quán)重進行集成提升，從而提高整個隨機森林的分類準確率.

1 算法相關(guān)定義

1.1 差分隱私及其特性

定義1(差分隱私)對于一個算法M，若其滿足ε-差分隱私，則

Pr[M(D)∈Sm]≤eεPr[M(D′)∈Sm].

(1)

式中：Sm為算法M可以輸出的所有值集合的任意子集，D和D′為差別至多為一條記錄的兩個數(shù)據(jù)集，ε為隱私保護預(yù)算.

差分隱私保護技術(shù)本身蘊含著序列組合性與并行組合性兩種重要的組合性質(zhì)[15].這兩種性質(zhì)在證明算法的隱私性以及隱私預(yù)算分配過程中起著重要作用.

性質(zhì)1(序列組合性)[15]給定數(shù)據(jù)庫D與n個隨機算法A1，…，An，且Ai(1≤i≤n)滿足εi-差分隱私，則{A1，…，An}在D上的序列組合滿足ε-差分隱私，其中ε=∑εi.

性質(zhì)2(并行組合性)[15]設(shè)D為一個隱私數(shù)據(jù)庫，被劃分成n個不相交的子集，D={D1，…，Dn}，設(shè)A為任一個隨機算法滿足ε-差分隱私.則算法A在{D1，…，Dn}上的系列操作滿足ε-差分隱私.

1.2 差分隱私下的包外估計及其應(yīng)用

1.2.1 差分隱私下的包外估計

在生成每棵決策樹時需要隨機且有放回地抽取樣本，因此會有大概1/3的數(shù)據(jù)未抽取到，這些數(shù)據(jù)就是該決策樹的包外數(shù)據(jù).在隨機森林算法下，數(shù)據(jù)集中特征的重要性、決策樹分類能力和相關(guān)性計算都依賴于包外數(shù)據(jù)[16].而用包外數(shù)據(jù)在該決策樹上進行決策，錯誤分類數(shù)據(jù)占包外數(shù)據(jù)總數(shù)的比率就是包外估計(out-of-bag estimate).經(jīng)驗證，包外估計是對集成分類器泛化誤差的無偏估計[14]，可以準確地估計決策樹的分類能力.但是為了保護包外數(shù)據(jù)的隱私，本文引入差分隱私下的包外估計，在計算包外估計時添加噪聲以滿足差分隱私條件，定義如下：

定義2(差分隱私下包外估計)對隨機森林中的一棵決策樹，差分隱私下的包外估計B為

(2)

式中：O為包外數(shù)據(jù)大小，M為錯誤分類數(shù)據(jù)大小，ε為該決策樹隱私預(yù)算，N(ε)為差分隱私噪聲函數(shù).

可以看出，加入的差分隱私噪聲N(ε)擾亂了真實的錯誤分類數(shù)據(jù)量，但是根據(jù)差分隱私定義，只需要添加少量的噪聲就可以達到保護隱私的目的，而不會使數(shù)據(jù)喪失可用性、失去規(guī)律，在本文中選用Laplace噪聲函數(shù).所以B越小，則代表該決策樹的分類準確率更高.

1.2.2 決策樹篩選

由于包外估計可以簡單有效地估計決策樹分類能力，本文參照Paul等[13]的方法計算決策樹權(quán)重，并用權(quán)重來代表該決策樹的分類能力，進而進行決策樹篩選.因此，將決策樹t的權(quán)重Wt定義為

(3)

式中Bt為該決策樹差分隱私下的包外估計.不難看出，決策樹權(quán)重越高，則代表著該決策樹分類時錯誤分類的包外數(shù)據(jù)量越少，也就代表著該決策樹的分類能力越好.

1.2.3 特征篩選

除了決策樹篩選，本文還利用包外估計可以有效地評估數(shù)據(jù)集中特征的重要性的能力，在決策樹構(gòu)成的過程中參照Paul等[13]提出的方法對數(shù)據(jù)集中的特征進行篩選.

1)特征權(quán)重.要進行特征篩選首先需要給出特征的評價標準，本文將其定義為特征權(quán)重.參照文獻[13]中的思想，首先定義特征在結(jié)點上的權(quán)重，其具體定義如下.

定義3(特征在結(jié)點上的權(quán)重)在決策樹中某個非葉子結(jié)點上，特征j在該結(jié)點上的權(quán)重為

Wj=1-G(j).

(4)

式中G(j)為基尼指數(shù).從基尼指數(shù)的定義可以知道，其值越小則表明按照此特征劃分的效果越好.所以當(dāng)特征權(quán)重越大時，代表著基尼指數(shù)越小，分類效果越好.而一棵決策樹上有多個結(jié)點，為了更好地衡量特征權(quán)重，取結(jié)點上特征權(quán)重的均值作為該特征在決策樹中的權(quán)重，定義如下.

定義4(特征在決策樹中的權(quán)重)特征j在決策樹中的權(quán)重為

(5)

式中：N為決策樹中非葉子結(jié)點數(shù)量，Wj為非葉子結(jié)點上特征j的特征權(quán)重.

但是每棵決策樹的分類性能各不相同，因此取決策樹中的特征權(quán)重的加權(quán)平均值，來衡量該特征在隨機森林算法中的重要性，定義如下.

定義5(特征在隨機森林算法中的權(quán)重)對t′棵決策樹，某特征在隨機森林算法中的權(quán)重為

(6)

2)特征劃分.在本文中用特征在隨機森林算法中的權(quán)重(以下簡稱特征權(quán)重)來衡量特征的重要性，并據(jù)此對特征進行劃分，找出非重要特征，進而對決策樹進行改進.而在劃分的過程中需要找出離群特征，定義如下.

定義6(離群特征)對已有權(quán)重的特征子集R，離群特征滿足條件

Wj< (μ-2σ).

(7)

式中：Wj為特征j的特征權(quán)重，μ為R中權(quán)重的平均值，σ為標準差.

從定義中可以看出，離群特征的權(quán)重較小，而且與特征權(quán)重的平均值都相差甚遠，所以在本文中將離群特征認定為相比于其他特征重要性更低的特征.進而可以根據(jù)特征的權(quán)重值對特征進行劃分

Г=Г-A.

(8)

R=R+A.

(9)

式中：Г為權(quán)重前f大的特征集，其中f為決策樹特征數(shù)量，R為Г的補集，A為Г中的離群特征集.然后找出R中的離群特征，記為非重要特征Г′.這些特征一旦被標記為重要特征或非重要特征，標記將不會被改變.

在隨機森林生成的過程中，需要更新重要特征Г和非重要特征Г′，即：保持Г和Г′中已有特征不變，對其余特征R，將特征放入重要特征集Г中，若其滿足

Wj>Wmin.

(10)

式中Wj為特征j的特征權(quán)重，Wmin為重要特征Г中的最小權(quán)重.然后取出R中的離群特征，放入非重要特征集Г′中.

3)特征篩選下決策樹的生成.在對特征進行了劃分后，就可以利用非重要特征在決策樹構(gòu)成的過程中對數(shù)據(jù)集中的特征進行篩選.在決策樹生成過程中，如果某個結(jié)點最優(yōu)決策特征是非重要特征，則將該結(jié)點變?yōu)槿~子結(jié)點，所有隱私預(yù)算用于葉子結(jié)點上計數(shù)值的加噪，使得噪聲總量減小，從而提高分類準確率.

如圖1所示，左側(cè)為不進行特征篩選時生成的決策樹，此時在根結(jié)點的右孩子結(jié)點上，最優(yōu)決策特征是一個非重要特征.如果進行特征篩選，則會在該結(jié)點上停止子結(jié)點的生成，即將該結(jié)點變?yōu)槿~子結(jié)點，并將該結(jié)點所有的隱私預(yù)算對計數(shù)值添加噪聲，最后得到如圖1中右側(cè)所示的決策樹.

圖1 特征篩選下決策樹的生成

從圖1中可以看出，若不進行特征篩選，根結(jié)點的右孩子結(jié)點消耗的隱私預(yù)算為ε/4，剩下的隱私預(yù)算將會被分配到它的子結(jié)點中；而通過特征篩選可以知道該結(jié)點使用的特征為非重要特征，此時如果繼續(xù)根據(jù)此特征劃分子結(jié)點，分類效果并不理想，而且隱私預(yù)算會因為分配到子結(jié)點中而變小，根據(jù)差分隱私定義可知，當(dāng)隱私預(yù)算越小時，加入的噪聲量越大，分類的準確率就會降低，因此將該結(jié)點變?yōu)槿~子結(jié)點可以提高分類準確率.

另外，不難看出，本文提出的特征篩選屬于預(yù)剪枝策略，即不需要生成完整的決策樹.而如CRFsDP算法[11]中使用的后剪枝策略則需要先生成一棵完整的決策樹，然后自底向上的對決策樹進行剪枝.因此在執(zhí)行效率方面，本文提出的特征篩選具有相對較好的性能.

2 算法實現(xiàn)及分析

2.1 RFDP_OOB算法描述

RFDP_OOB算法的主要思想是先在差分隱私保護下生成一部分的隨機森林，同時根據(jù)加入噪聲的包外估計計算決策樹權(quán)重以及特征權(quán)重，并根據(jù)特征權(quán)重劃分出重要特征與非重要特征，接著根據(jù)特征篩選生成剩下的隨機森林，最后根據(jù)決策樹權(quán)重進行分類預(yù)測，具體步驟如下.

1)將隱私預(yù)算平均分配到每棵決策樹上，生成一部分隨機森林.對決策樹中的結(jié)點判斷：若該結(jié)點不是葉子結(jié)點，則取一半當(dāng)前隱私預(yù)算對決策結(jié)果加噪；若該結(jié)點是葉子結(jié)點，用當(dāng)前隱私預(yù)算對計數(shù)值添加噪聲，確定分類類別.在構(gòu)建完成后計算決策樹中的特征權(quán)重、差分隱私下的包外估計以及決策樹權(quán)重.

2)對于已生成的一部分隨機森林，獲得隨機森林中的特征權(quán)重之后，對特征進行劃分，找出非重要特征.

3)根據(jù)非重要特征構(gòu)建決策樹：對非葉子結(jié)點，若該結(jié)點的最優(yōu)劃分特征在非重要特征集中，則該結(jié)點變?yōu)槿~子結(jié)點，并用當(dāng)前隱私預(yù)算對計數(shù)值添加噪聲，確定分類類別.同時對非重要特征集進行更新.

4)將所有決策樹以及對應(yīng)的權(quán)重組合成隨機森林.對要預(yù)測的數(shù)據(jù)，用隨機森林中每棵決策樹對其進行分類預(yù)測：從根結(jié)點開始，根據(jù)當(dāng)前結(jié)點的分類屬性決定該條數(shù)據(jù)應(yīng)該進入到哪一個子結(jié)點，直到達到葉子結(jié)點，然后獲得葉子結(jié)點的標簽.將其相應(yīng)決策樹的權(quán)重線性相加，取權(quán)重最大的那個分類結(jié)果作為整個隨機森林算法的分類結(jié)果.

算法偽代碼如下：

2.2 算法分析

2.2.1 隱私性分析

RFDP_OOB算法中有t棵決策樹，每棵決策樹分配到的隱私預(yù)算ε′=ε/t，用來保護兩部分的數(shù)據(jù)隱私.

1)用來生成決策樹的訓(xùn)練數(shù)據(jù).對決策樹中同一層的不同結(jié)點，消耗當(dāng)前一半隱私預(yù)算εh=ε′/2h+1，其中h為結(jié)點的深度，所以這些結(jié)點是符合εh-差分隱私要求的.又因為這些結(jié)點的數(shù)據(jù)都是不相交的，根據(jù)差分隱私的并行組合性，將數(shù)據(jù)不相交的結(jié)點組合后仍然滿足εh-差分隱私.

而決策樹中不同層結(jié)點的數(shù)據(jù)存在交叉，因此根據(jù)差分隱私的序列組合性，將其組合滿足的差分隱私所要求的隱私預(yù)算為各層隱私預(yù)算之和，即∑εh=ε′.所以用來生成決策樹的訓(xùn)練數(shù)據(jù)是符合ε′-差分隱私的.

2)用來計算決策樹包外估計的包外數(shù)據(jù).用包外數(shù)據(jù)計算單棵決策樹的包外估計時，用分配的隱私預(yù)算ε′對分類結(jié)果正確的計數(shù)進行加噪，所以也是滿足ε′-差分隱私的.

由此這兩部分數(shù)據(jù)都滿足ε′-差分隱私，又由包外估計定義可知，包外數(shù)據(jù)為生成決策樹的訓(xùn)練數(shù)據(jù)的補集，兩者之間不存在交叉，所以根據(jù)差分隱私的并行組合性可知，將這兩部分數(shù)據(jù)組合的決策樹符合ε′-差分隱私.

最后，由于每棵樹所用的訓(xùn)練數(shù)據(jù)是隨機選擇的，因此所用數(shù)據(jù)會有交叉，根據(jù)序列組合性，整個隨機森林消耗的隱私預(yù)算為每棵決策樹消耗隱私預(yù)算的疊加，即為t*ε′=ε，所以RFDP_OOB算法滿足ε-差分隱私.

2.2.2 執(zhí)行效率分析

算法先生成一部分隨機森林，即t′棵決策樹.對每棵決策樹，深度為d，數(shù)據(jù)量大小為X，f是特征的數(shù)量.決策樹生成時，把所有特征值都作為分裂候選，為其添加噪聲并計算基尼指數(shù).令特征j值的種類為V(j)，則每層時間復(fù)雜度為O(X*∑fV(j))，其中V(j)最小為常數(shù)，最大為數(shù)據(jù)量大小X.所以d層的決策樹生成的時間復(fù)雜度是O(d*X*∑fV(j)).

決策樹生成后計算包外估計，因為包外數(shù)據(jù)期望值為原始數(shù)據(jù)的1/3，所以計算包外估計的時間復(fù)雜度為O(X)，遠小于決策樹生成時間，而添加噪聲只需要O(1)的時間復(fù)雜度，所以不影響時間復(fù)雜度的規(guī)模.

綜上可知，這一部分的時間復(fù)雜度為O(t′*d*X*∑fV(j)).

接著需要計算全局特征權(quán)重并劃分特征，而全局特征權(quán)重只與特征數(shù)量和決策樹權(quán)重有關(guān)，所以時間復(fù)雜度為O(t′*f)；得到全局特征權(quán)重之后進行特征劃分，時間復(fù)雜度為O(min(t′*f,F))，其中F為原始數(shù)據(jù)中的特征數(shù)，這里因為用到的特征數(shù)量t′*f不會超過原始數(shù)據(jù)中的特征數(shù)量F，所以取較小的值.所以這一部分的時間復(fù)雜度為兩者累加，故而取較大的值，即為O(max(t′*f,F)).

最后根據(jù)特征篩選生成剩下隨機森林，即Δt=t-t′棵決策樹.與之前決策樹生成的不同點在于每個結(jié)點處分裂特征進行篩選，如果是非重要特征則不繼續(xù)分裂，所以此時要對特征進行查找，時間復(fù)雜度為O(min(t′*f,F))，仍然遠小于決策樹生成時間，并且進行了篩選的決策樹達到不了深度d，執(zhí)行時間會減少.至于包外估計和權(quán)重更新不再贅述，消耗時間仍會遠小于決策樹生成時間.所以特征篩選下的隨機森林的時間復(fù)雜度為O(Δt*d*X*∑fV(j)).

將以上3部分的時間復(fù)雜度累加可以得出，此算法的時間復(fù)雜度為

O(t*d*X*∑fV(j)).

式中：t為隨機森林中決策樹數(shù)量，d為決策樹深度，X為數(shù)據(jù)量大小，f是特征的數(shù)量，V(j)是特征j中值的種類.

可以看出，算法的主要模塊，無論是包外估計的計算還是特征的篩選都不影響算法時間復(fù)雜度的規(guī)模，與DiffPRFs[9]算法具有相同的時間復(fù)雜度，與CRFsDP算法[11]最好情況下即不進行剪枝的情況下的時間復(fù)雜度相同，所以此算法具有較高的性能.

3 實驗結(jié)果

3.1 實驗環(huán)境

本文實驗操作系統(tǒng)為Windows 10，CPU為i5-3230M @2.6 GHz，內(nèi)存為8 G，使用PyCharm 2018，Python 3.7.實驗使用3個不同的高維度數(shù)據(jù)集，都是來自UCI數(shù)據(jù)庫的真實數(shù)據(jù)集，而且數(shù)據(jù)集中都有一些隱私信息，因此選用這些數(shù)據(jù)集進行實驗在一定程度上體現(xiàn)了本研究的現(xiàn)實意義.第1個數(shù)據(jù)集是羅徹斯特理工學(xué)院在2017年發(fā)布的關(guān)于癲癇病發(fā)作識別的數(shù)據(jù)集，共有11 500條數(shù)據(jù)，每條數(shù)據(jù)有179個特征，判定類別為癲癇病是否發(fā)作，以下記為ES.第2個數(shù)據(jù)集是伊斯坦布爾大學(xué)醫(yī)學(xué)院神經(jīng)病學(xué)系2018年發(fā)布的,記錄了帕金森患者的基本信息及語音記錄，共有756 條數(shù)據(jù)，經(jīng)過預(yù)處理刪除id屬性后共有754個特征，可以根據(jù)特征判定該人員是否患有帕金森，以下記為PDC.第3個數(shù)據(jù)集是互聯(lián)網(wǎng)廣告數(shù)據(jù)集，刪除不完整數(shù)據(jù)后共有2 359條，每條數(shù)據(jù)有1 558個特征，可以根據(jù)數(shù)據(jù)判斷它是否為廣告，以下記為ADS.

本實驗采用F1作為評價隨機森林性能的指標，它能綜合衡量準確率P和召回率R，其取值范圍為[0,1]，定義如下：

(9)

實驗中使用該指標衡量融合分類器在測試集上的準確度.F1值越高，表明準確率和召回率越高，分類器正確分類能力越強.

RFDP_OOB算法的目的在于高維數(shù)據(jù)下保證數(shù)據(jù)隱私性的同時提高隨機森林算法的分類準確率，因此實驗中主要對隨機森林算法的分類準確率進行對比驗證.所以首先考慮RFDP_OOB算法中獨有的參數(shù)預(yù)生成決策樹數(shù)量t′對算法分類準確率的影響，找出最優(yōu)值.然后根據(jù)文獻[11]中的設(shè)定，分別在不同決策樹深度和隱私預(yù)算下，將RFDP_OOB算法與其他差分隱私隨機森林算法進行對比，觀察算法的分類準確率，其中包括穆海蓉等[9]提出的DiffPRFs算法、Xiang等[11]提出的CRFsDP算法.為減少隨機性帶來的影響，對每組實驗進行100 次，取F1值的平均值作為最終結(jié)果.另外通過比較RFDP_OOB算法與DiffPRFs算法[9]、CRFsDP算法[11]的執(zhí)行時間，來驗證RFDP_OOB算法的執(zhí)行效率.同樣進行100 次實驗，比較平均執(zhí)行時間.

3.2 實驗結(jié)果

3.2.1 參數(shù)與算法分類性能關(guān)系

圖2 3個數(shù)據(jù)集下的t′對分類準確率的影響

從圖2中可看出，隨著預(yù)生成決策樹數(shù)量t′的增加，F(xiàn)1值先上升后下降，在t′/t=1/3的時候F1值最大，而當(dāng)t′/t=1時F1值最小.這是因為，當(dāng)預(yù)生成決策樹數(shù)量過小時，使用的特征數(shù)量較小，不利于劃分特征，從而不能充分利用特征篩選對決策樹進行改進，進而降低了RFDP_OOB算法的分類準確率.而當(dāng)預(yù)生成決策樹數(shù)量過大時，則可以利用特征篩選進行改進的決策樹數(shù)量過小，尤其是t′/t=1時，沒有可以根據(jù)特征篩選構(gòu)建的決策樹，因此無法利用特征篩選達到改進的效果.綜上所述，為了使RFDP_OOB算法達到最優(yōu)，令預(yù)生成決策樹t′為隨機森林中決策樹數(shù)量的1/3.

3.2.2 算法分類性能對比

根據(jù)文獻[11]中的設(shè)定，令決策樹數(shù)量t=100，隱私預(yù)算ε=1，決策樹深度d為3～7之間時，將提出的算法RFDP_OOB與CRFsDP算法[11]、DiffPRFs算法[9]在3個數(shù)據(jù)集上進行對比，實驗結(jié)果見圖3.

圖3 不同深度下的分類性能

從圖3中可以看出，RFDP_OOB算法在ES和ADS數(shù)據(jù)集上的F1值最高達到0.85，在PDC數(shù)據(jù)集上最高為0.75，并且在相同條件下比CRFsDP算法[11]提高了5%，比DiffPRFs算法[9]提高了20%.這是因為RFDP_OOB算法和CRFsDP算法[11]都進行了剪枝操作以及集成提升，所以在高維數(shù)據(jù)下仍具有良好的性能.而且普遍來看，RFDP_OOB算法的分類效果要高于CRFsDP算法[11]，這也驗證了RFDP_OOB算法的有效性.

另外，3種算法具有相似的趨勢，隨著決策樹深度的增加，這3個算法的分類準確率先增加后不變甚至下降，這也是隱私預(yù)算導(dǎo)致的.由前文分析可知，決策樹的高度越高時雖然有利于對數(shù)據(jù)進一步分類，但是也導(dǎo)致最底層葉子結(jié)點的隱私預(yù)算越小，從而使得加入噪聲總量更大，分類結(jié)果發(fā)生改變.

接下來仍然參照文獻[11]中的設(shè)定，比較不同隱私預(yù)算下算法的分類準確率，令決策樹數(shù)量t=100，決策樹深度d=5，隱私預(yù)算ε=0.1、0.25、0.5、1，分別在3個數(shù)據(jù)集上進行實驗.實驗結(jié)果如圖4 所示.

從圖4中可看出，RFDP_OOB算法的F1值在ES數(shù)據(jù)集上最高為0.836，在PDC數(shù)據(jù)集上最高為0.74，在ADS數(shù)據(jù)集上最高為0.844.并且在相同隱私預(yù)算下RFDP_OOB算法比CRFsDP算法[11]的F1值要高3%～6%，比DiffPRFs算法[9]的F1值高20%.而且3種算法的F1值都隨著隱私預(yù)算的增加而增大，這是因為隱私預(yù)算越大則添加的噪聲量越小，從而提高決策樹的分類準確率，進而提高隨機森林算法的分類準確率.

圖4 不同隱私預(yù)算下的分類性能

綜上所述，無論是不同決策樹深度還是不同隱私預(yù)算，在其他參數(shù)相同的情況下，RFDP_OOB算法的分類準確率都是要高于CRFsDP算法[11]和DiffPRFs算法[9]的，由此可見，RFDP_OOB算法在相同的隱私保護程度下，能夠有效提高分類的準確率，也再次驗證了本文改進思路的有效性.

3.2.3 算法執(zhí)行效率對比

最后驗證算法的執(zhí)行效率，仍然參照文獻[11]中的設(shè)定，令決策樹數(shù)量t=100、隱私預(yù)算ε=1，決策樹深度d為3～7之間，測試3種算法的執(zhí)行效率，實驗結(jié)果見表2～4.

表2 ES數(shù)據(jù)集下的執(zhí)行效率

表3 PDC數(shù)據(jù)集下的執(zhí)行效率

表4 ADS數(shù)據(jù)集下的執(zhí)行效率

綜合表2～4可以看出，RFDP_OOB算法的運行時間差別較大，在ADS數(shù)據(jù)集上只需要7 s，而在ES數(shù)據(jù)集上卻需要10 min.這是因為，根據(jù)前面執(zhí)行效率的分析可知，執(zhí)行效率與數(shù)據(jù)量大小、特征數(shù)量以及特征值種類有關(guān)，而ES數(shù)據(jù)集雖然特征數(shù)量較少，但是數(shù)據(jù)量以及特征值種類都遠遠大于另外兩個數(shù)據(jù)集，因此時間復(fù)雜度較高.而ADS數(shù)據(jù)集中很多特征只有0和1兩種值，所以執(zhí)行時間反而是最短的.

另外容易看出，RFDP_OOB算法和DiffPRFs算法[9]的執(zhí)行時間要低于CRFsDP算法[11]，這是因為CRFsDP算法[11]中需要先生成滿二叉樹再使用后剪枝方法來改進決策樹，所以時間復(fù)雜度較高.RFDP_OOB算法與DiffPRFs算法[9]具有相近的執(zhí)行效率，這與之前所分析的它們具有相同規(guī)模的時間復(fù)雜度相符合，進一步驗證了RFDP_OOB算法的可行性.

4 結(jié) 論

本文引入了差分隱私下的包外估計來計算特征權(quán)重以及決策樹權(quán)重，從而提出了一種基于差分隱私下包外估計的隨機森林算法RFDP_OOB，并給出了算法的具體思想與描述.然后針對RFDP_OOB算法的隱私性進行了理論分析，再通過對比實驗驗證了算法的可行性及有效性.這種算法能夠進行有效的特征篩選、集成提升，從而提高差分隱私隨機森林算法的分類準確率，但在特定數(shù)據(jù)集上執(zhí)行時間過長，而特征篩選模塊又無法應(yīng)用到并行方法下.因此，如何在并行模式下進行特征篩選，從而提高算法的執(zhí)行效率，是日后需要研究的重點.