李玉強(qiáng)，陳鋆昊，李 琦，劉愛華

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

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

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

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

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

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

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

1.1 差分隱私及其特性

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

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

(1)

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

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

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

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

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

1.2.1 差分隱私下的包外估計(jì)

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

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

(2)

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

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

1.2.2 決策樹篩選

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

(3)

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

1.2.3 特征篩選

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

1)特征權(quán)重.要進(jìn)行特征篩選首先需要給出特征的評(píng)價(jià)標(biāo)準(zhǔn)，本文將其定義為特征權(quán)重.參照文獻(xiàn)[13]中的思想，首先定義特征在結(jié)點(diǎn)上的權(quán)重，其具體定義如下.

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

Wj=1-G(j).

(4)

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

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

(5)

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

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

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

(6)

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

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

Wj< (μ-2σ).

(7)

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

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

Г=Г-A.

(8)

R=R+A.

(9)

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

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

Wj>Wmin.

(10)

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

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

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

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

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

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

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

2.1 RFDP_OOB算法描述

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

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

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

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

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

算法偽代碼如下：

2.2 算法分析

2.2.1 隱私性分析

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

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

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

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

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

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

2.2.2 執(zhí)行效率分析

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

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

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

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

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

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

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

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

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

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

3.1 實(shí)驗(yàn)環(huán)境

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

本實(shí)驗(yàn)采用F1作為評(píng)價(jià)隨機(jī)森林性能的指標(biāo)，它能綜合衡量準(zhǔn)確率P和召回率R，其取值范圍為[0,1]，定義如下：

(9)

實(shí)驗(yàn)中使用該指標(biāo)衡量融合分類器在測試集上的準(zhǔn)確度.F1值越高，表明準(zhǔn)確率和召回率越高，分類器正確分類能力越強(qiáng).

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

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

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

圖2 3個(gè)數(shù)據(jù)集下的t′對(duì)分類準(zhǔn)確率的影響

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

3.2.2 算法分類性能對(duì)比

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

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

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

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

接下來仍然參照文獻(xiàn)[11]中的設(shè)定，比較不同隱私預(yù)算下算法的分類準(zhǔn)確率，令決策樹數(shù)量t=100，決策樹深度d=5，隱私預(yù)算ε=0.1、0.25、0.5、1，分別在3個(gè)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn).實(shí)驗(yàn)結(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àn)殡[私預(yù)算越大則添加的噪聲量越小，從而提高決策樹的分類準(zhǔn)確率，進(jìn)而提高隨機(jī)森林算法的分類準(zhǔn)確率.

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

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

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

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

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

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

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

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

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

4 結(jié) 論

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