一種基于ExtraTrees的差分隱私保護(hù)算法

李 楊,陳子彬,謝光強(qiáng)

(廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院,廣州 510006)

0 概述

隨著計(jì)算機(jī)存儲(chǔ)數(shù)據(jù)成本的不斷降低以及云計(jì)算、大數(shù)據(jù)、移動(dòng)互聯(lián)網(wǎng)等技術(shù)的廣泛應(yīng)用和普及,企業(yè)、政府組織的信息系統(tǒng)存儲(chǔ)了海量數(shù)據(jù),如社交網(wǎng)絡(luò)公司的社交數(shù)據(jù)、各大電商平臺(tái)的顧客購(gòu)買數(shù)據(jù)以及醫(yī)院的病人醫(yī)療數(shù)據(jù)等,這些隱私數(shù)據(jù)常被用于分析、統(tǒng)計(jì)和挖掘。從這些數(shù)據(jù)中發(fā)現(xiàn)潛在的商業(yè)價(jià)值和規(guī)律,同時(shí)保證不泄露用戶敏感信息,引起了數(shù)據(jù)挖掘和隱私保護(hù)領(lǐng)域相關(guān)學(xué)者的廣泛關(guān)注。

在早期的相關(guān)研究中,數(shù)據(jù)隱私保護(hù)的方法主要是k-anonymity[1]及其擴(kuò)展模型,如l-diversity[2]、t-closeness[3]和(α,k)-anonymity[4]等。盡管這些模型能夠在一定程度上保護(hù)數(shù)據(jù)中用戶的敏感信息,但是它們的共同缺點(diǎn)是需要假設(shè)攻擊者擁有的背景知識(shí)和特定的攻擊模型,導(dǎo)致其應(yīng)用場(chǎng)景受到很多制約。在這種背景下,DWORK C等學(xué)者[5-6]在2006年提出具有嚴(yán)格理論證明的差分隱私保護(hù)模型,該模型為保護(hù)數(shù)據(jù)隱私帶來了一種新的解決思路。在差分隱私保護(hù)的定義下,即便攻擊者擁有除目標(biāo)用戶以外的全部其他信息,用戶仍然能夠防御攻擊并且不會(huì)泄露敏感信息。差分隱私保護(hù)通過在針對(duì)某個(gè)數(shù)據(jù)集上的查詢結(jié)果添加噪聲來提供保護(hù),且基于差分隱私保護(hù)的算法在輸出結(jié)果上添加的噪聲獨(dú)立于數(shù)據(jù)集的規(guī)模,添加少量的噪聲能夠保證隱私數(shù)據(jù)的安全性以及輸出結(jié)果的可用性。

目前,差分隱私保護(hù)的研究方向集中在差分隱私數(shù)據(jù)發(fā)布[7-9](延伸至社交網(wǎng)絡(luò)[10]、軌跡數(shù)據(jù)[11])、社交網(wǎng)絡(luò)研究[12-13]、查詢處理[14-15]以及和數(shù)據(jù)挖掘相結(jié)合(如聚類[16]、分類[17-19]、集成學(xué)習(xí)[20])等方面,而在回歸分析上的研究則相對(duì)較少。進(jìn)行差分隱私保護(hù)回歸分析研究的難點(diǎn)在于求解回歸目標(biāo)函數(shù)的敏感度很大,難以保證回歸準(zhǔn)確度。

ExtraTrees作為一種使用頻率較高的集成學(xué)習(xí)模型,能夠應(yīng)用于決策樹分類和回歸分析中,本文提出一種基于ExtraTrees的差分隱私保護(hù)算法。在決策樹分類上,利用ExtraTrees算法2次隨機(jī)選擇的特性,提高指數(shù)機(jī)制在同等隱私預(yù)算下的使用效率,通過將基尼指數(shù)作為指數(shù)機(jī)制在分類樹特征選擇上的可用性函數(shù)來降低敏感度,從而減少所添加的噪聲量。在回歸樹上,選擇最佳分裂特征和分裂點(diǎn)時(shí)將方差作為指數(shù)機(jī)制的可用性函數(shù),標(biāo)記葉子節(jié)點(diǎn)時(shí)對(duì)其均值添加拉普拉斯噪聲。

1 相關(guān)工作

1.1 差分隱私的定義

定義1(ε-差分隱私) 設(shè)有2個(gè)數(shù)據(jù)集D1和D2,兩者的屬性結(jié)構(gòu)相同,不同的記錄數(shù)量為|D1ΔD2|。當(dāng)|D1ΔD2|=1時(shí),設(shè)一個(gè)隨機(jī)化算法為M,RRange(M)代表算法M的所有輸出構(gòu)成的集合體,S是RRange(M)中的一個(gè)子集,若算法M提供ε-差分隱私保護(hù),則對(duì)于所有的S∈RRange(M),有:

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

(1)

其中,Pr[]代表某個(gè)事件泄露隱私的概率,其由算法M本身的性質(zhì)所決定,ε稱為隱私保護(hù)預(yù)算，是由數(shù)據(jù)提供者視隱私保護(hù)程度所給定的參數(shù),隱私保護(hù)程度與ε的取值成反比,ε通常取小于1的常數(shù)。式(1)表示對(duì)算法M的任何一個(gè)輸出結(jié)果,不管函數(shù)的輸入是D1還是D2,最后得到這個(gè)輸出結(jié)果的概率差別很小。

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

差分隱私保護(hù)的實(shí)現(xiàn)原理是通過添加噪聲來提供保護(hù),經(jīng)常使用的2種噪聲模型為拉普拉斯機(jī)制[21]和指數(shù)機(jī)制[22]。某個(gè)算法提供差分隱私保護(hù)所添加噪聲的多少與全局敏感度有關(guān)。

定義2(全局敏感度) 設(shè)函數(shù)f:D→Rd的輸入為數(shù)據(jù)集D,輸出為任一實(shí)體對(duì)象,數(shù)據(jù)集D1和D2之間不同的記錄個(gè)數(shù)不大于1,則f的全局敏感度定義為:

(2)

其中,‖f(D1)-f(D2)‖1表示f(D1)和f(D2)之間的1-階范數(shù)距離。

定義3(拉普拉斯機(jī)制) 對(duì)于數(shù)據(jù)集D上的任一函數(shù)f:D→Rd,算法M添加由拉普拉斯分布產(chǎn)生的相互獨(dú)立的噪聲變量,以提供ε-差分隱私保護(hù),具體如下:

(3)

定義4(指數(shù)機(jī)制) 設(shè)算法M的輸入為數(shù)據(jù)集D,輸出為一個(gè)具體對(duì)象r∈RRange(M),q(D,r)為可用性函數(shù),Δq為函數(shù)q(D,r)的敏感度。如果輸出結(jié)果滿足式(4),則稱算法M提供ε-差分隱私保護(hù)。

(4)

1.3 差分隱私的性質(zhì)

定義5(并行組合性)[22]設(shè)算法M提供ε-差分隱私保護(hù),給定數(shù)據(jù)集D被切割成互不相交的子集D1,D2,…,Dn,則M作用在{D1,D2,…,Dn}上的組合算法{M(D1),M(D2),…,M(Dn)}具有ε-差分隱私。

1.4 ExtraTrees算法

ExtraTrees是一種集成學(xué)習(xí)算法,包含眾多決策樹,分類結(jié)果最終由其包含的眾多決策樹的輸出結(jié)果共同投票決定,回歸則由這些決策樹輸出值的均值來決定。ExtraTrees算法最大的特點(diǎn)是在分裂特征的選擇上采用隨機(jī)的方式,隨機(jī)選擇某個(gè)特征的某個(gè)取值作為該特征的分裂點(diǎn)。由于這2個(gè)隨機(jī)性特點(diǎn),使得ExtraTrees算法泛化能力較強(qiáng),具有抵抗噪聲的能力。

1.5 已有相關(guān)研究

在差分隱私保護(hù)決策樹分類算法研究中,文獻(xiàn)[24]提出了基于線性查詢函數(shù)的分類器算法SuLQ-based ID3。文獻(xiàn)[25]為解決SuLQ-based ID3算法添加噪聲過多的問題,提出一種基于決策樹建造的差分隱私保護(hù)算法DiffP-C4.5。文獻(xiàn)[26]沿用數(shù)據(jù)泛化的思想,在決策樹的基礎(chǔ)上,提出一種非交互式的差分隱私數(shù)據(jù)發(fā)布算法DiffGen。實(shí)驗(yàn)結(jié)果表明,在隱私預(yù)算相同的情況下,DiffGen的實(shí)驗(yàn)效果相較于其他算法更好。文獻(xiàn)[27]在DiffGen算法的基礎(chǔ)上,通過對(duì)細(xì)分方案進(jìn)行改進(jìn),為連續(xù)型數(shù)值加上權(quán)重,從而更充分地利用隱私預(yù)算,相較于DiffGen具有更好的分類效果。文獻(xiàn)[28]將差分隱私和隨機(jī)決策樹模型相結(jié)合,提出了RDT算法,但是該算法僅使用拉普拉斯機(jī)制,在葉子節(jié)點(diǎn)的向量添加噪聲。文獻(xiàn)[29]提出了差分隱私隨機(jī)森林算法,該算法的缺點(diǎn)在于僅適合標(biāo)稱型屬性的數(shù)據(jù)集,對(duì)于包含連續(xù)屬性的數(shù)據(jù)集需要先將連續(xù)屬性轉(zhuǎn)化成離散屬性,然后對(duì)數(shù)據(jù)集進(jìn)行分類。

在差分隱私保護(hù)回歸分析算法研究中,文獻(xiàn)[30]提出了一個(gè)利用拉普拉斯機(jī)制和指數(shù)機(jī)制進(jìn)行統(tǒng)計(jì)分析的總體框架,但是該框架要求統(tǒng)計(jì)分析的輸出空間有界,導(dǎo)致不適用于線性回歸,并且其直接在計(jì)算結(jié)果上添加拉普拉斯噪聲,雖然在一定程度上保護(hù)了用戶隱私,但是由于添加過多的噪聲,造成計(jì)算結(jié)果的可用性非常低。文獻(xiàn)[31-32]研究表明,當(dāng)回歸任務(wù)的成本函數(shù)是凸函數(shù)并且可微時(shí),回歸才能滿足差分隱私保護(hù)。相較于文獻(xiàn)[30]直接在輸出結(jié)果上添加噪聲,文獻(xiàn)[31-32]在n個(gè)目標(biāo)函數(shù)的輸出平均值上添加噪聲以實(shí)現(xiàn)隱私保護(hù),其添加的噪聲量有所減少,但該方法普適性較低。文獻(xiàn)[33]為了解決回歸結(jié)果誤差大的問題,提出了一種函數(shù)機(jī)制(Functional Mechanism，F(xiàn)M)。FM機(jī)制不是在輸出結(jié)果上添加噪聲,而是通過對(duì)回歸的目標(biāo)函數(shù)添加噪聲,得到加噪的目標(biāo)函數(shù),然后求解出最優(yōu)回歸模型參數(shù)。因此,該機(jī)制普適性較高,在多種回歸模型上都能應(yīng)用。但是,由于其計(jì)算出來的全局敏感度與數(shù)據(jù)集的維度成正比,造成噪聲添加過多,使得回歸結(jié)果誤差大。文獻(xiàn)[34]提出了一種根據(jù)回歸目標(biāo)函數(shù)敏感度大小來分配隱私預(yù)算的算法Diff-LR。該算法將線性回歸分析的目標(biāo)函數(shù)拆分成不同的模塊,再分別求解出不同模塊的敏感度。對(duì)模塊分配隱私預(yù)算時(shí),敏感度大的模塊分派隱私預(yù)算多,敏感度小的模塊分派隱私預(yù)算少。雖然相對(duì)于函數(shù)機(jī)制FM,該算法有效降低了敏感度,但是其敏感度依然和數(shù)據(jù)集維度正相關(guān),導(dǎo)致在數(shù)據(jù)集維度較大的情況下帶來過多的噪聲。

2 DiffPETs算法的框架描述與分析

本文提出一種基于ExtraTrees的差分隱私保護(hù)算法DiffPETs,并將其應(yīng)用于決策樹分類和回歸分析。

2.1 算法描述

DiffPETs差分隱私算法偽代碼如下:

算法1DiffPETs(D,A,Pε,t,h)

輸入數(shù)據(jù)集D,特征集A,總隱私預(yù)算Pε,產(chǎn)生決策樹的個(gè)數(shù)t,單棵樹的高度h

輸出滿足ε-差分隱私的學(xué)習(xí)器T={T1,T2,…,Tt}

3.for i = 1 to t:

4.從D中有放回地隨機(jī)抽樣大小為|D|的訓(xùn)練集D(i)

5.調(diào)用算法2生成樹Ti=Build_DiffPET(D(i),A,ε2,1)

6.end for

7.返回提供ε-差分隱私的學(xué)習(xí)器T={T1,T2,…,Tt}

算法2Build_DiffPET(D,A,ε,h)

輸入數(shù)據(jù)集D,特征集A,隱私預(yù)算ε,單棵樹的高度h

輸出滿足ε-差分隱私的學(xué)習(xí)器Ti

終止條件節(jié)點(diǎn)全部記錄的標(biāo)簽一致,誤差達(dá)到閾值或樹達(dá)到最大高度h

1.if節(jié)點(diǎn)達(dá)到了終止條件:

2.返回葉子節(jié)點(diǎn)ND=Noise(|D|)

3.end if

5.從K個(gè)特征中分別隨機(jī)選擇K個(gè)分裂點(diǎn){s1,s2,…,sK}

6.從K個(gè)特征和分裂點(diǎn)中,使用指數(shù)機(jī)制用以下概率選擇最優(yōu)特征和分裂點(diǎn):

其中,q(D,A′)表示可用性函數(shù),Δq為可用性函數(shù)的敏感度.

7.根據(jù)最佳分裂特征和分裂點(diǎn)將當(dāng)前數(shù)據(jù)集分割成2個(gè)子集Dl和Dr

8.在最佳分裂特征和分裂點(diǎn)的基礎(chǔ)上分別建立左右子樹tl=Build_DiffPET(Dl,A,ε,h+1),tr=Build_DiffPET(Dr,A,ε,h+1)

9.返回提供ε-差分隱私的學(xué)習(xí)器Ti

算法1展示了DiffPETs的基本框架,其涉及5個(gè)主要的輸入?yún)?shù):數(shù)據(jù)集D,特征集A,隱私預(yù)算Pε,產(chǎn)生決策樹的數(shù)目t和單棵樹的高度h。DiffPETs首先根據(jù)生成決策樹的數(shù)量t和樹的高度h將隱私預(yù)算Pε進(jìn)行分配(第1～第2行),然后根據(jù)生成決策樹的數(shù)量t循環(huán)建立單棵決策樹,每次建立單棵決策樹時(shí)使用不同的抽樣樣本,以提高算法的泛化能力(第3～第6行)。算法2展示了生成單棵決策樹的詳細(xì)步驟,首先根據(jù)如下規(guī)則判斷當(dāng)前節(jié)點(diǎn)是否達(dá)到終止條件:1)分類樹上節(jié)點(diǎn)所屬記錄的分類特征是否相同;2)回歸樹上節(jié)點(diǎn)誤差是否小于閾值;3)樹是否達(dá)到最大高度h。當(dāng)滿足終止條件以后,使用拉普拉斯機(jī)制返回添加了噪聲的葉子節(jié)點(diǎn)(第1～第3行),然后從特征集A中隨機(jī)選擇K個(gè)特征和分裂點(diǎn),使用指數(shù)機(jī)制選擇最佳分裂特征和分裂點(diǎn)(第4～第6行)。本文指數(shù)機(jī)制的選擇方法為:將算法2第6行計(jì)算出的各概率值按順序排列放在坐標(biāo)軸上,分別對(duì)應(yīng)0～1上的某個(gè)區(qū)間,之后隨機(jī)生成一個(gè)0～1之間的數(shù),隨機(jī)數(shù)對(duì)應(yīng)哪個(gè)區(qū)間,指數(shù)機(jī)制就挑選相應(yīng)備選項(xiàng)作為輸出。最后,根據(jù)最佳分裂特征和分裂點(diǎn)遞歸構(gòu)造左右子樹,返回單棵決策樹Ti(第7～第9行)。

2.2 算法隱私性分析

DiffPETs算法首先將總隱私預(yù)算Pε平均分配給每一棵決策樹ε1=Pε/t。根據(jù)差分隱私的性質(zhì)[22],由于單棵樹的樣本有交集,因此算法耗費(fèi)的隱私預(yù)算為單棵決策樹耗費(fèi)隱私預(yù)算的總和,然后按照同樣規(guī)則遞歸產(chǎn)生每一棵決策樹。具體步驟如下:首先從D中有放回地抽取大小為|D|的訓(xùn)練集D(i),隨后將單棵樹的隱私預(yù)算平均分配給各層ε2=ε1/(2(h+1)),每層的隱私預(yù)算平均分成兩部分,一部分應(yīng)用拉普拉斯機(jī)制對(duì)劃分到該節(jié)點(diǎn)的樣本數(shù)添加噪聲,然后判斷是否滿足終止條件,若滿足則將此節(jié)點(diǎn)標(biāo)記為葉子節(jié)點(diǎn),若沒有達(dá)到終止條件,隨機(jī)地從|A|個(gè)特征集中選擇K個(gè)特征,之后再隨機(jī)產(chǎn)生K個(gè)分裂點(diǎn),利用指數(shù)機(jī)制和剩余的隱私預(yù)算選擇最佳分裂特征和分裂點(diǎn)。因此,算法所耗費(fèi)的全部隱私預(yù)算是Pε,提供ε-差分隱私保護(hù)。在分類中,指數(shù)機(jī)制中的可用性函數(shù)為基尼指數(shù),而在回歸中其可用性函數(shù)為方差。

2.3 敏感度分析

2.3.1 基尼指數(shù)的敏感度

(5)

(6)

2.3.2 均值的敏感度

2.3.3 方差的敏感度

決策樹方差的定義如下:

(7)

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

本文分類器訓(xùn)練算法、測(cè)試算法和數(shù)據(jù)處理均通過Python3.5版本實(shí)現(xiàn),無差分隱私的算法調(diào)用scikit-learn庫(kù)實(shí)現(xiàn)。硬件環(huán)境為Intel(R)Core(TM)i5 2.5 GHz,內(nèi)存為8 GB 1 600 MHz DDR3。為檢驗(yàn)DiffPETs算法的性能,采取如下5個(gè)UCI公開數(shù)據(jù)集進(jìn)行實(shí)驗(yàn):1)Mushroom數(shù)據(jù)集,根據(jù)蘑菇的各種特征預(yù)測(cè)蘑菇是否可以食用;2)Nursery數(shù)據(jù)集,根據(jù)家庭背景等特征預(yù)測(cè)申請(qǐng)幼兒園的等級(jí);3)Congressional Vote Records(CongVote)數(shù)據(jù)集,美國(guó)國(guó)會(huì)投票記錄,預(yù)測(cè)共和黨或民主黨是否能夠當(dāng)選;4)WineQuality數(shù)據(jù)集,根據(jù)物理化學(xué)特性預(yù)測(cè)紅葡萄酒的質(zhì)量;5)Daily_Demand數(shù)據(jù)集,預(yù)測(cè)巴西某一家物流公司訂單的總量。表1所示為5個(gè)數(shù)據(jù)集的基本信息。

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

3.1 分類實(shí)驗(yàn)結(jié)果

為驗(yàn)證DiffPETs算法在分類預(yù)測(cè)中的性能表現(xiàn),分別令ε={0.50,0.75,1.00}(其對(duì)應(yīng)森林中樹的個(gè)數(shù)分別為t={10,10,5}),設(shè)置每棵樹的高度為h=k/2,k為對(duì)應(yīng)數(shù)據(jù)集的維度,可用性函數(shù)為基尼指數(shù)。本文首先利用DiffPETs算法在訓(xùn)練集上生成算法模型,之后在不同的隱私預(yù)算、樹的棵數(shù)和單棵樹的高度下進(jìn)行實(shí)驗(yàn),最后在測(cè)試集上作預(yù)測(cè),并計(jì)算相應(yīng)的準(zhǔn)確率。每組實(shí)驗(yàn)進(jìn)行10次,以平均實(shí)驗(yàn)結(jié)果作為最后的準(zhǔn)確率,將DiffPETs算法與無差分隱私、RDT[28]和DiffPRF[29]算法進(jìn)行比較,實(shí)驗(yàn)結(jié)果如圖1～圖4所示。

圖1 不同隱私預(yù)算下的分類結(jié)果

圖2 Mushroom數(shù)據(jù)集在不同隱私預(yù)算下的實(shí)驗(yàn)結(jié)果

Fig.2 Experimental results of Mushroom dataset under different privacy budgets

圖3 Nursery數(shù)據(jù)集在不同隱私預(yù)算下的實(shí)驗(yàn)結(jié)果

Fig.3 Experimental results of Nursery dataset under different privacy budgets

圖4 CongVote數(shù)據(jù)集在不同隱私預(yù)算下的實(shí)驗(yàn)結(jié)果

Fig.4 Experimental results of CongVote dataset under different privacy budgets

從圖1可以看出,在隱私預(yù)算較小時(shí),DiffPETs算法的準(zhǔn)確性不高,可以理解為為了實(shí)現(xiàn)高級(jí)別的隱私保護(hù),算法不得不做出一些犧牲。隨著隱私預(yù)算的增加,DiffPETs算法的準(zhǔn)確率逐漸提高,原因是添加到算法中的噪聲量逐漸減少。通過與DiffPRF和RDT算法進(jìn)行對(duì)比可以看出,本文算法在同等隱私預(yù)算下能夠?qū)崿F(xiàn)較低的分類誤差。

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

在回歸實(shí)驗(yàn)中,本文采用均方誤差(MSE)來判斷算法的性能,其定義如下:

(8)

和分類實(shí)驗(yàn)一樣,令ε={0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1.0},森林中對(duì)應(yīng)樹的個(gè)數(shù)為t=10。每組實(shí)驗(yàn)重復(fù)10次,采用最后的平均誤差為實(shí)驗(yàn)結(jié)果,并將本文算法與無差分隱私、FM[33]、Diff_LR[34]算法進(jìn)行比較,實(shí)驗(yàn)結(jié)果如圖5、圖6所示。

圖5 WineQuality數(shù)據(jù)集的均方誤差

圖6 Daily_Demand數(shù)據(jù)集的均方誤差

從圖5、圖6可以看出,在同等隱私預(yù)算ε的條件下,本文DiffPETs算法相比于FM和Diff_LR均方誤差更小。隨著ε的增加,DiffPETs算法的均方誤差與未加噪聲的模型逐漸接近。此外,可以看出,沒有添加噪聲的模型產(chǎn)生的均方誤差與隱私預(yù)算ε的大小無關(guān)。

4 結(jié)束語

本文提出一種基于ExtraTrees的差分隱私保護(hù)算法DiffPETs,并將其應(yīng)用于分類和回歸分析。在決策樹分類時(shí),采取隨機(jī)的方式選擇特征使算法的泛化能力得到有效提升。在回歸中,算法的全局敏感度與所添加的噪聲均較低,回歸預(yù)測(cè)的結(jié)果更準(zhǔn)確。實(shí)驗(yàn)結(jié)果表明,DiffPETs算法具有較高的可行性與準(zhǔn)確性。下一步考慮將本文算法應(yīng)用于交通、醫(yī)療等大數(shù)據(jù)問題。