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

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

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

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

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

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

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

1 算法相關定義

1.1 差分隱私及其特性

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

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

(1)

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

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

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

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

1.2 差分隱私下的包外估計及其應用

1.2.1 差分隱私下的包外估計

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

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

(2)

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

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

1.2.2 決策樹篩選

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

(3)

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

1.2.3 特征篩選

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

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

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

Wj=1-G(j).

(4)

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

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

(5)

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

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

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

(6)

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

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

Wj< (μ-2σ).

(7)

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

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

Г=Г-A.

(8)

R=R+A.

(9)

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

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

Wj>Wmin.

(10)

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

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

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

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

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

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

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

2.1 RFDP_OOB算法描述

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

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

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

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

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

算法偽代碼如下：

2.2 算法分析

2.2.1 隱私性分析

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

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

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

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

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

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

2.2.2 執(zhí)行效率分析

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

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

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

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

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

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

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

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

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

3 實驗結果

3.1 實驗環(huán)境

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

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

(9)

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

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

3.2 實驗結果

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

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

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

3.2.2 算法分類性能對比

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

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

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

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

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

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

圖4 不同隱私預算下的分類性能

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

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

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

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

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

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

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

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

4 結 論

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