基于目標(biāo)擾動(dòng)的AdaBoost 算法

張淑芬，董燕靈，徐精誠(chéng)，王豪石

（1.華北理工大學(xué)理學(xué)院，河北 唐山 063210；2.河北省數(shù)據(jù)科學(xué)與應(yīng)用重點(diǎn)實(shí)驗(yàn)室，河北 唐山 063210；3.唐山市大數(shù)據(jù)安全與智能計(jì)算重點(diǎn)實(shí)驗(yàn)室，河北 唐山 063210；4.唐山市數(shù)據(jù)科學(xué)重點(diǎn)實(shí)驗(yàn)室，河北 唐山 063210）

0 引言

大數(shù)據(jù)時(shí)代下，海量數(shù)據(jù)以及強(qiáng)大的數(shù)據(jù)分析與數(shù)據(jù)挖掘能力無不反映了數(shù)據(jù)的高價(jià)值性，然而由于一些數(shù)據(jù)發(fā)布者缺乏管理和保護(hù)數(shù)據(jù)的意識(shí)，使攻擊者有機(jī)可乘。雖然現(xiàn)有的隱私保護(hù)技術(shù)如數(shù)據(jù)脫敏[1]、k-匿名[2]、同態(tài)加密[3]等方法能在一定范圍內(nèi)保護(hù)數(shù)據(jù)中的隱私信息，但當(dāng)攻擊者擁有強(qiáng)大的背景知識(shí)時(shí)，同樣無法抵抗攻擊者的攻擊。于是，差分隱私保護(hù)技術(shù)[4-6]應(yīng)運(yùn)而生。差分隱私保護(hù)技術(shù)不需要假設(shè)攻擊者有背景知識(shí)，且成功地避免了攻擊者會(huì)因?yàn)樾聵颖镜某霈F(xiàn)而得到新的知識(shí)。該技術(shù)允許數(shù)據(jù)收集者采用拉普拉斯機(jī)制[7]、指數(shù)機(jī)制[8]或高斯機(jī)制[9]對(duì)數(shù)據(jù)添加噪聲進(jìn)行擾動(dòng)，從而使攻擊者無法辨別某一樣本是否在數(shù)據(jù)集中。

差分隱私通過添加噪聲來擾動(dòng)數(shù)據(jù)，使查詢結(jié)果具有一定的隨機(jī)性。主要的擾動(dòng)方式有輸入擾動(dòng)、輸出擾動(dòng)和目標(biāo)擾動(dòng)。輸入擾動(dòng)對(duì)原始數(shù)據(jù)直接添加噪聲，擾動(dòng)后的數(shù)據(jù)成為模型學(xué)習(xí)的輸入，直接參與之后的訓(xùn)練。輸出擾動(dòng)是指對(duì)模型的最終輸出添加噪聲，得到擾動(dòng)后的結(jié)果。目標(biāo)擾動(dòng)通過對(duì)目標(biāo)函數(shù)添加噪聲，使最終模型的輸出具有隨機(jī)性。

當(dāng)前，隨機(jī)森林[10-18]是將差分隱私應(yīng)用于集成學(xué)習(xí)中的主要研究方向，然而將差分隱私與AdaBoost 算法結(jié)合的研究卻甚少。這是因?yàn)椴罘蛛[私AdaBoost 算法面對(duì)的挑戰(zhàn)[19]主要是算法迭代引起的噪聲疊加造成最后模型無法收斂和分類準(zhǔn)確率較低。Gambs 等[20]提出了2 種隱私保護(hù)AdaBoost算法，適用于2 個(gè)或2 個(gè)以上參與者在不直接交流數(shù)據(jù)集的情況下保護(hù)參與者的數(shù)據(jù)隱私。Li 等[21]選取AdaBoost 算法作為每個(gè)參與者的本地學(xué)習(xí)器，提出一種基于集成策略的自適應(yīng)分布式隱私保護(hù)數(shù)據(jù)挖掘技術(shù)。沈思倩[22]分別研究了基于完全數(shù)據(jù)集和不完全數(shù)據(jù)集的差分隱私Adabooot 算法。賈俊杰等[23]進(jìn)一步將分類與回歸樹（CART）取代樹樁作為AdaBoost 算法的基分類樹。但上述研究都只是對(duì)弱學(xué)習(xí)器的類標(biāo)簽或類計(jì)數(shù)進(jìn)行了加噪，而且在敏感度的計(jì)算上也不夠嚴(yán)謹(jǐn)。Li 等[24]首次將梯度提升決策樹與差分隱私相結(jié)合，在敏感度的計(jì)算上更加精確。在這些已有的將差分隱私與AdaBoost算法結(jié)合的研究中，主要有3 個(gè)缺陷：一是隱私預(yù)算的分配不具有針對(duì)性，較泛化；二是在敏感度的計(jì)算上不夠嚴(yán)謹(jǐn)；三是在添加噪聲上，尚未解決AdaBoost 算法由于多輪迭代而放大噪聲的問題。為此，本文提出對(duì)每輪迭代過程中的最大最小樣本權(quán)值進(jìn)行加噪，針對(duì)該加噪對(duì)象提出一種動(dòng)態(tài)的隱私預(yù)算分配策略，嚴(yán)謹(jǐn)?shù)馗鶕?jù)敏感度定義計(jì)算了查詢函數(shù)最大變化范圍，并提出了3 種能有效控制噪聲疊加過大并提高模型可用性的方案。實(shí)現(xiàn)在保護(hù)數(shù)據(jù)的同時(shí)讓模型擁有更高的分類準(zhǔn)確率。具體來說，本文的主要工作如下。

1) 提出了一種基于目標(biāo)擾動(dòng)的AdaBoost 算法。根據(jù)AdaBoost 的目標(biāo)函數(shù)，提出本文實(shí)現(xiàn)AdaBoost 差分隱私保護(hù)的加噪時(shí)機(jī)。

2) 針對(duì)AdaBoost 算法每輪迭代的樣本權(quán)值分布，選取最具代表性的最大權(quán)值和最小權(quán)值，并通過動(dòng)態(tài)的隱私預(yù)算分配策略分配不同的隱私預(yù)算。

3) 根據(jù)敏感度定義，準(zhǔn)確計(jì)算最大權(quán)值和最小權(quán)值的動(dòng)態(tài)敏感度。

4) 為有效解決因每輪迭代加噪而引起的分類準(zhǔn)確率失真、模型不可用問題，提出基于擺動(dòng)數(shù)列、隨機(jī)響應(yīng)和改進(jìn)的隨機(jī)響應(yīng)3 種噪聲注入方案，并在真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，以評(píng)估不同算法的有效性。

1 差分隱私保護(hù)技術(shù)

差分隱私保護(hù)技術(shù)最早被應(yīng)用于數(shù)據(jù)庫(kù)安全領(lǐng)域，查詢2 個(gè)僅相差一條記錄的數(shù)據(jù)集，發(fā)現(xiàn)得到相同結(jié)果的概率非常接近，使攻擊者無法進(jìn)行差分攻擊。

1.1 差分隱私的定義及相關(guān)概念

設(shè)數(shù)據(jù)集D與具有相同屬性結(jié)構(gòu)的數(shù)據(jù)集D′的對(duì)稱差為DΔD′，|DΔD′|表示DΔD′中記錄的數(shù)量。若|DΔD′|= 1，則稱D和D′為鄰近數(shù)據(jù)集。

定義1差分隱私[4-6]。設(shè)有隨機(jī)算法M，PM為M所有可能的輸出構(gòu)成的集合。對(duì)于任意2 個(gè)鄰近數(shù)據(jù)集D和D′以及PM 的任何子集SM，若算法M滿足

則稱算法M提供ε-差分隱私保護(hù)，其中，參數(shù)ε為隱私預(yù)算，表示數(shù)據(jù)集中增加或減少一條記錄時(shí)，算法M的輸出結(jié)果一致的概率；Pr[·] 表示發(fā)生某一事件的概率。

定義2全局敏感度[7]。對(duì)于2 個(gè)鄰近數(shù)據(jù)集D和D′，查詢函數(shù)f最大的變化范圍為全局敏感度Δf，則Δf的計(jì)算式為

定義3串行組合[7]。差分隱私具有靈活的組合特性。假設(shè)有n個(gè)隨機(jī)算法K，其中Ki滿足εi-差分隱私，那么對(duì)于同一數(shù)據(jù)集，由{Ki（}1 ≤i≤n）組合后的算法滿足sum(εi)-差分隱私。

1.2 實(shí)現(xiàn)機(jī)制

拉普拉斯機(jī)制通過向查詢結(jié)果中添加隨機(jī)噪聲來實(shí)現(xiàn)差分隱私保護(hù)，并且添加的隨機(jī)噪聲是服從拉普拉斯分布的。設(shè)尺度參數(shù)為λ，位置參數(shù)μ=0，則該拉普拉斯分布為L(zhǎng)ap(λ)，它的概率密度函數(shù)為

不同尺度參數(shù) 的拉普拉斯分布如圖1 所示。

圖1 不同尺度參數(shù)λ 的拉普拉斯分布

定義4拉普拉斯機(jī)制[7]。給定數(shù)據(jù)集D和隱私預(yù)算ε，設(shè)有查詢函數(shù)f(D)，其敏感度為Δf，那么隨機(jī)算法M(D) =f(D)+Y提供ε-差分隱私保護(hù)。其中，為隨機(jī)噪聲，并服從尺度參數(shù)為的拉普拉斯分布。拉普拉斯機(jī)制的整體思想是以一定的概率輸出異常值。為了使加噪后的數(shù)據(jù)脫離真實(shí)值，需要提高輸出異常值的概率，即穩(wěn)定地得到一個(gè)異常值，因此當(dāng)拉普拉斯函數(shù)曲線越平緩時(shí)，異常值輸出的概率就越高，數(shù)據(jù)相對(duì)于正確的中心值更加分散。

2 AdaBoost 算法

AdaBoost[25-27]是前向分步加法算法的特例，通過迭代，將前一輪強(qiáng)學(xué)習(xí)器的學(xué)習(xí)結(jié)果與當(dāng)前一輪弱學(xué)習(xí)器的學(xué)習(xí)結(jié)果加權(quán)，來更新當(dāng)前的強(qiáng)學(xué)習(xí)器。在訓(xùn)練弱學(xué)習(xí)器時(shí)，減小上一輪樣本被正確分類的樣本權(quán)值，提高樣本被錯(cuò)誤分類的樣本權(quán)值。在最終加權(quán)組合成強(qiáng)學(xué)習(xí)器時(shí)，加大分類誤差率小的弱學(xué)習(xí)器的權(quán)重，減小分類誤差率大的弱學(xué)習(xí)器的權(quán)重。

本文使用的主要符號(hào)如表1 所示。

表1 主要符號(hào)

2.1 AdaBoost 目標(biāo)函數(shù)

AdaBoost 算法的損失函數(shù)為指數(shù)函數(shù)[28]，即定義損失函數(shù)為

將損失函數(shù)代入目標(biāo)函數(shù)中，則AdaBoost 的目標(biāo)函數(shù)為

由于AdaBoost 算法是前向分步算法，假設(shè)第k輪的強(qiáng)學(xué)習(xí)器為f k(x)，第k-1輪的強(qiáng)學(xué)習(xí)器為f k-1(x)，第k輪的弱學(xué)習(xí)器為Gk(x)，則有以下關(guān)系

AdaBoost 的目標(biāo)是使前向分步算法得到的αk和Gk(x)能讓f k(x)在訓(xùn)練集上的指數(shù)損失最小，即AdaBoost 的目標(biāo)是最小化目標(biāo)函數(shù)，表示為

2.2 AdaBoost 算法流程

算法1AdaBoost 算法

輸入訓(xùn)練集T，迭代次數(shù)m

輸出最終分類器G(x)

3 AdaBoost 算法的隱私保護(hù)

在AdaBoost 算法的實(shí)際應(yīng)用過程中，算法模型會(huì)在生命周期的各個(gè)階段面臨不同的安全威脅，導(dǎo)致模型的隱私信息被泄露，模型的可用性、完整性被破壞。為了減少此類現(xiàn)象的發(fā)生，需要對(duì)AdaBoost 算法進(jìn)行隱私保護(hù)。

從隱私保護(hù)的角度來看，根據(jù)注入噪聲的時(shí)機(jī)，實(shí)現(xiàn)差分隱私有輸入擾動(dòng)、輸出擾動(dòng)和目標(biāo)擾動(dòng)這3 種方法。本文選取目標(biāo)擾動(dòng)作為AdaBoost算法實(shí)現(xiàn)差分隱私保護(hù)的加噪時(shí)機(jī)，并根據(jù)2.1 節(jié)AdaBoost 目標(biāo)函數(shù)，取樣本權(quán)值作為加噪對(duì)象。

3.1 基于樣本權(quán)值的動(dòng)態(tài)隱私預(yù)算分配策略

在k輪迭代后，更新的樣本權(quán)值wk+1,i成為下一次迭代中計(jì)算錯(cuò)分樣本率的輸入。由于每一輪迭代過程中，權(quán)值小的樣本是前一輪被正確分類的樣本，前一輪被錯(cuò)分的樣本在下一輪中會(huì)被賦予更高的權(quán)值來加以重視。同時(shí)，為了能夠?qū)崿F(xiàn)AdaBoost算法的快速收斂，在添加差分隱私保護(hù)時(shí)，需對(duì)權(quán)值較大的樣本分配多的隱私預(yù)算，對(duì)權(quán)值較小的樣本分配較少的隱私預(yù)算。基于此，提出一種基于樣本權(quán)值的動(dòng)態(tài)隱私預(yù)算分配策略。

假設(shè)總的隱私預(yù)算為B，迭代次數(shù)為m，樣本數(shù)為N，對(duì)于第k輪更新后的權(quán)值分布Dk+1，尋找出最大權(quán)值和最小權(quán)值，分別為最大權(quán)值和最小權(quán)值添加噪聲。其中樣本的初始權(quán)值不需要添加噪聲，即。

此時(shí)，全局敏感度Δf是動(dòng)態(tài)變化的，根據(jù)定義2，計(jì)算最大權(quán)值的全局敏感度Δf為

算法2隱私預(yù)算分配算法DPweight_dynamic

輸入更新后的權(quán)值wk+1,i，迭代次數(shù)m，隱私預(yù)算B

輸出樣本權(quán)值

將DPweight_dynamic 算法與AdaBoost 算法結(jié)合，得到DPAda 算法。

算法3DPAda 算法

輸入訓(xùn)練集T，迭代次數(shù)m，隱私預(yù)算B

輸出最終分類器G(x)

3.2 迭代過程中的噪聲控制

若對(duì)每輪最大權(quán)值或最小權(quán)值wk+1,i都添加噪聲，則在多輪迭代后，當(dāng)前的噪聲會(huì)疊加到后續(xù)的分類器構(gòu)造中，累加后的噪聲會(huì)極大程度地影響最終分類器結(jié)果的質(zhì)量。

此外，AdaBoost 算法在第一輪迭代后，權(quán)值分布兩極化，即只有最大權(quán)值和最小權(quán)值。在對(duì)最大權(quán)值和最小權(quán)值添加2 種不同的噪聲時(shí)，由于拉普拉斯噪聲是隨機(jī)的，且有正有負(fù)，就可能造成最大權(quán)值添加了負(fù)噪聲，最小權(quán)值添加了正噪聲。但由于最小權(quán)值在添加了正噪聲后不可能超過權(quán)值均值，最大權(quán)值在添加了負(fù)噪聲后不可能小于權(quán)值均值，因此就會(huì)出現(xiàn)最小權(quán)值或最大權(quán)值變?yōu)榫档那闆r。為避免這種極端情況的發(fā)生，在后文的算法中均從第二輪開始加噪。

3.2.1 基于擺動(dòng)數(shù)列的噪聲注入

定義5擺動(dòng)數(shù)列[29]。一個(gè)數(shù)列從第2 項(xiàng)起，有些項(xiàng)大于它的前一項(xiàng)，有些項(xiàng)小于它的前一項(xiàng)，這樣的數(shù)列叫做擺動(dòng)數(shù)列。通過尋找擺動(dòng)的平衡位置與擺動(dòng)的振幅，可以得到擺動(dòng)數(shù)列的通項(xiàng)公式。

假設(shè)有數(shù)列a,b,a,b,…，則該數(shù)列的平衡位置為，振幅為，通過(-1)n或 (-1)n+1調(diào)節(jié)，則該數(shù)列的通項(xiàng)為

本文選取a= 0,b=1的擺動(dòng)數(shù)列，根據(jù)擺動(dòng)數(shù)列第n項(xiàng)的值，判斷是否為AdaBoost 算法的第n輪添加噪聲。此時(shí)該數(shù)列的通項(xiàng)為

將基于擺動(dòng)數(shù)列的噪聲注入與DPAda 算法結(jié)合，得到DPAda_Swing 算法。

算法4DPAda_Swing 生成算法

研究證明HPV的感染是可以預(yù)防的，并且宮頸癌可能成為第一個(gè)可以用疫苗預(yù)防的癌癥。研究發(fā)現(xiàn)，HPV的L1蛋白保守度高，因此可以作為HPV的特異性抗原用來研究制造病毒預(yù)防疫苗。目前市面上的預(yù)防疫苗都是利用重組的DNA分子所表達(dá)的病毒樣顆粒(virus-like particles， VLPs)制成的疫苗。

3.2.2 基于隨機(jī)響應(yīng)的噪聲注入

由于擺動(dòng)數(shù)列穩(wěn)定地、間隔性地輸出相同值，不具有隨機(jī)性，因此本文提出基于隨機(jī)響應(yīng)的噪聲注入。

定義6隨機(jī)響應(yīng)。一隨機(jī)實(shí)驗(yàn)在同樣的條件下重復(fù)并相互獨(dú)立地進(jìn)行，該隨機(jī)實(shí)驗(yàn)只有2 種可能結(jié)果：結(jié)果a和結(jié)果b。隨機(jī)數(shù)x在(a,b)上服從均勻分布，即x～ U(a,b)，，給定以下規(guī)則

則稱h(x)滿足隨機(jī)響應(yīng)，即隨機(jī)實(shí)驗(yàn)滿足隨機(jī)響應(yīng)。

本文在AdaBoost 算法的每輪迭代過程中，生成一隨機(jī)數(shù)x，其中x服從a=0，b=1標(biāo)準(zhǔn)均勻分布，即x～ U(0,1)，E(x)=0.5，則每輪迭代hk(x)滿足隨機(jī)響應(yīng)

根據(jù)隨機(jī)響應(yīng)第k輪迭代輸出的值，判斷是否為AdaBoost 算法的第k輪添加噪聲。

將基于隨機(jī)響應(yīng)的噪聲注入與DPAda 算法結(jié)合，得到DPAda_Random 算法。

算法5DPAda_Random 生成算法

3.2.3 基于改進(jìn)的隨機(jī)響應(yīng)的噪聲注入

由于隨機(jī)響應(yīng)在每輪迭代中較隨機(jī)地生成a和b，即可能出現(xiàn)連續(xù)幾輪的輸出值都為a或b，因此，本文提出了一種改進(jìn)的隨機(jī)響應(yīng)。根據(jù)第k輪迭代輸出的值，判斷是否為AdaBoost 算法的第k輪添加噪聲。

定義7改進(jìn)的隨機(jī)響應(yīng)。若第i次迭代的輸出值hi(x)=a，第i+1次迭代的輸出值hi+1(x)=b，且第i+2次～第j-1次迭代中(j＞i+2)，每次輸出值hk(x)均為b，直至第j次迭代的輸出值h j(x)=a，則將第i+2次～第j-1次迭代的輸出值hk(x)全置a。

取a= 0,b=1，將基于改進(jìn)的隨機(jī)響應(yīng)的噪聲注入與DPAda 算法結(jié)合，得到DPAda_Improved 算法。

算法6DPAda_Improved 生成算法

3.3 算法分析

3.3.1 加噪輪數(shù)分析

定理1令R為算法累計(jì)添加噪聲的輪數(shù)，則。

證明DPAda 算法具有從第二輪起每輪都添加拉普拉斯噪聲的特點(diǎn)，則

擺動(dòng)數(shù)列可以穩(wěn)定地輸出 0101…，則DPAda_Swing 算法具有間隔性添加拉普拉斯噪聲的特點(diǎn)，因此

隨機(jī)響應(yīng)在輸出0 與1 時(shí)太過隨機(jī)，因此，DPAda_Random 具有連續(xù)加噪或連續(xù)不加噪的特點(diǎn)，假設(shè)DPAda_Random 算法添加拉普拉斯噪聲共s次，則

改進(jìn)的隨機(jī)響應(yīng)有效規(guī)避了隨機(jī)響應(yīng)連續(xù)幾輪加噪或不加噪的缺點(diǎn)，且具有間隔隨機(jī)輪次加噪的優(yōu)點(diǎn)，因此假設(shè)DPAda_Improved 算法添加拉普拉斯噪聲共t次，則

因此可得

證畢。

3.3.2 算法時(shí)間復(fù)雜度分析

DPAda、DPAda_Swing、DPAda_Random 和DPAda_Improved 算法的時(shí)間復(fù)雜度估計(jì)為

其中，m為迭代次數(shù)，d為訓(xùn)練集中屬性數(shù)量，n為訓(xùn)練集中樣本個(gè)數(shù)。

3.3.3 算法隱私性分析

假設(shè)共有m輪迭代，對(duì)于第k輪迭代后更新的樣本權(quán)值為最大權(quán)值的個(gè)數(shù)，為最小權(quán)值的個(gè)數(shù)。

定理2DPAda、DPAda_Swing、DPAda_Random和DPAda_Improved 算法滿足B-差分隱私。

由定義3 差分隱私的串行組合性質(zhì)可知

因此，DPAda、DPAda_Swing、DPAda_Random和DPAda_Improved 算法滿足B-差分隱私。證畢。

4 實(shí)驗(yàn)及分析

4.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)所選數(shù)據(jù)集來源于公開的UCI 機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中的Adult 數(shù)據(jù)集和Bank Marketing 數(shù)據(jù)集，如表2 所示。

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

通過對(duì)Adult 數(shù)據(jù)集的屬性集進(jìn)行分析發(fā)現(xiàn)，屬性native-country 為非美國(guó)籍的樣本數(shù)僅占總樣本數(shù)的16%，因此本文實(shí)驗(yàn)僅選取美國(guó)籍的樣本記錄進(jìn)行訓(xùn)練、測(cè)試。此外，屬性fnlwgt 的值是通過對(duì)和當(dāng)前樣本具有相似人口特征的人進(jìn)行加權(quán)統(tǒng)計(jì)而得出的人口總數(shù)，該屬性對(duì)本文的實(shí)驗(yàn)結(jié)果無幫助，因此將它刪除。本文選取Adult_train 作為訓(xùn)練集，Adult_test 作為測(cè)試集，選取Bank Marketing數(shù)據(jù)集的70%作為訓(xùn)練集，30%作為測(cè)試集。

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

在相同參數(shù)下，每組實(shí)驗(yàn)重復(fù)運(yùn)行50 次取平均值來計(jì)算算法的平均分類準(zhǔn)確率。x軸為總的隱私預(yù)算ε=B，y軸為算法平均分類準(zhǔn)確率，其中B= 0.1,0.3,0.5,0.7,0.9,1.0,3.0,5.0，迭代次數(shù)m= 30,50,70,90,100。

圖2 和圖3 分別是不同數(shù)據(jù)集下DPAda_Swing算法、DPAda_Random 算法與DPAda_Improved 算法在不同迭代次數(shù)下的平均分類準(zhǔn)確率對(duì)比。觀察圖2和圖 3 不難發(fā)現(xiàn)，DPAda_Swing 算法與DPAda_Improved 算法的分類準(zhǔn)確率雖偶有波動(dòng)，但整體趨勢(shì)基本隨著ε的增加而增長(zhǎng)，而DPAda_Random 算法的平均分類準(zhǔn)確率波動(dòng)很大，且當(dāng)?shù)螖?shù)m較小時(shí)，波動(dòng)特別明顯。這是因?yàn)镈PAda_Random 算法在給樣本權(quán)值wk+1,i添加噪聲時(shí)，根據(jù)隨機(jī)響應(yīng)的輸出特點(diǎn)，在輸出0 與1 時(shí)太過隨機(jī)，即可能連續(xù)幾次迭代的輸出值都為1，從而連續(xù)加噪，因此無法有效控制是否對(duì)第k輪迭代進(jìn)行加噪。m越小，越難克服隨機(jī)性帶來的影響，當(dāng)m較大時(shí)，可以通過多輪迭代來減少隨機(jī)性帶來的影響。DPAda_Swing 算法能夠根據(jù)擺動(dòng)數(shù)列穩(wěn)定的輸出值0101…，來間隔性地添加噪聲。對(duì)于DPAda_Improved算法，雖然在輸出0 與1 時(shí)仍具有隨機(jī)性，但根據(jù)定義7，相較于DPAda_Random 算法中的隨機(jī)響應(yīng)，DPAda_Improved 算法使用改進(jìn)的隨機(jī)響應(yīng)，有效減少了添加噪聲的次數(shù)，達(dá)到了小于或等于DPAda_Swing算法中基于擺動(dòng)數(shù)列添加噪聲的輪數(shù)。觀察圖2(a)和圖3(c)、圖3(a)和圖3(c)可以看出，在不同迭代次數(shù)m下，DPAda_Improved算法的分類準(zhǔn)確率均高于DPAda_Swing 算法。

圖2 Adult 數(shù)據(jù)集下3 種算法的平均分類準(zhǔn)確率

圖3 Bank Marketing 數(shù)據(jù)集下3 種算法的平均分類準(zhǔn)確率

本文還設(shè)置了在m= 50,70,90和ε=0.1,0.3,0.5,0.7,0.9,1.0,3.0,5.0 條件下，將不結(jié)合差分隱私的AdaBoost 算法、給類標(biāo)簽添加差分隱私保護(hù)的DP-AdaBoost 算法[22]、給CART 樹的內(nèi)部節(jié)點(diǎn)和葉子節(jié)點(diǎn)添加差分隱私保護(hù)的CART-DPsAdaBoost 算法[30]、從第二輪起每輪添加差分隱私保護(hù)的DPAda算法與本文提出的DPAda_Swing、DPAda_Random、DPAda_Improved 算法進(jìn)行比較，實(shí)驗(yàn)結(jié)果如圖4～圖6 所示。

圖4 m=50 時(shí)不同算法平均分類準(zhǔn)確率

圖5 m=70 時(shí)不同算法平均分類準(zhǔn)確率

從圖4～圖6 可以看出，DPAda 算法的分類準(zhǔn)確率很低，并隨著迭代次數(shù)m的增加大體上呈下降趨勢(shì)。這是由于DPAda 算法除第一輪迭代外，對(duì)之后每輪迭代都連續(xù)加噪。因此，在迭代次數(shù)m增加時(shí)，噪聲便會(huì)隨著迭代數(shù)的增加而疊加，最后使DPAda 算法的分類準(zhǔn)確率不增反降。當(dāng)m一定時(shí)，DP-AdaBoost、CART-DPsAdaBoost、DPAda_Swing 和DPAda_Improved 算法的分類準(zhǔn)確率都隨著ε的增加而增加；但當(dāng)ε一定時(shí)，只有DP-AdaBoost 算法的分類準(zhǔn)確率隨著m的增加而下降。這是因?yàn)镈P-AdaBoost 算法[22]添加噪聲的對(duì)象為弱學(xué)習(xí)器的類標(biāo)簽，它并沒有參與迭代過程，因此當(dāng)ε一定時(shí)，隨著迭代次數(shù)m的增加，弱學(xué)習(xí)器越多，分配到每一輪迭代的隱私預(yù)算減小，加噪就越明顯，分類準(zhǔn)確率就越低。CART-DPsAdaBoost 算法[30]是在形成CART 基分類器的過程中，對(duì)CART 的葉子節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)進(jìn)行加噪，當(dāng)基分類器個(gè)數(shù)增加時(shí)，噪聲對(duì)構(gòu)造最終分類器的影響逐漸減小。因此，隨著m的增加，分類準(zhǔn)確率逐漸提升；而DPAda_Swing 和DPAda_Improved 算法中添加噪聲的對(duì)象為樣本權(quán)值，且結(jié)合的是動(dòng)態(tài)隱私預(yù)算分配策略DPweight_dynamic，該策略只對(duì)最大樣本權(quán)值和最小樣本權(quán)值加噪，保證了在添加噪聲的過程中，最大樣本權(quán)值在加噪后不會(huì)小于樣本權(quán)值均值，最小樣本權(quán)值在加噪后不會(huì)大于樣本權(quán)值均值，因此仍能保證樣本權(quán)值的主要分布。此外，DPAda_Swing 和DPAda_Improved 算法根據(jù)擺動(dòng)數(shù)列和改進(jìn)的隨機(jī)響應(yīng)，有效控制了加噪過程為非連續(xù)加噪，給予了弱學(xué)習(xí)器矯正收斂的機(jī)會(huì)，因此DPAda_Swing 和DPAda_Improved 算法的分類準(zhǔn)確率隨著迭代次數(shù)m的增加而增加。

圖6 m=90 時(shí)不同算法平均分類準(zhǔn)確率

通過觀察圖4～圖6 也不難看出，在不同迭代次數(shù)m和隱私預(yù)算ε下，在所有對(duì)比算法中，DPAda_Improved 算法在分類結(jié)果上表現(xiàn)得最穩(wěn)定，分類準(zhǔn)確率最接近不添加噪聲的AdaBoost算法，實(shí)現(xiàn)了在保護(hù)隱私的同時(shí)，仍擁有更高的分類準(zhǔn)確率。

綜上，DPAda_Improved 算法與對(duì)弱學(xué)習(xí)器類標(biāo)簽添加噪聲的DP-AdaBoost 算法[22]相比，不會(huì)有隨著迭代次數(shù)的增加準(zhǔn)確率反而下降的問題；在分類準(zhǔn)確率的整體表現(xiàn)上，優(yōu)于給CART 樹添加噪聲的CART-DPsAdaBoost 算法[30]；有效解決了DPAda 算法由于連續(xù)加噪帶來的噪聲不斷疊加、精確度極低、模型無法收斂導(dǎo)致模型不可用的問題；不僅在分類準(zhǔn)確率上表現(xiàn)得比其他算法要好，還保留了DPAda_Random 算法的隨機(jī)輪次加噪的特點(diǎn)，并有效地減少了隨機(jī)性帶來的影響，達(dá)到了小于或等于基于擺動(dòng)數(shù)列的DPAda_Swing算法中添加噪聲的輪數(shù)。最后，DPAda_Improved算法很好地做到了隱私保護(hù)與數(shù)據(jù)效用的均衡。

5 結(jié)束語(yǔ)

本文提出了一種基于目標(biāo)擾動(dòng)的差分隱私AdaBoost 算法，與現(xiàn)有的差分隱私AdaBoost 算法相比，本文算法的貢獻(xiàn)如下。1) 選擇了迭代過程中每個(gè)樣本的樣本權(quán)值作為添加差分隱私保護(hù)的對(duì)象，解決了在AdaBoost 算法多輪迭代過程中加噪的主要問題，即算法迭代帶來的噪聲疊加導(dǎo)致最終無法收斂，模型不可用，準(zhǔn)確率極低的問題。2) 設(shè)計(jì)了一種動(dòng)態(tài)的隱私預(yù)算分配策略。3) 給出了嚴(yán)謹(jǐn)?shù)拿舾卸扔?jì)算。4) 提出了3 種有效控制噪聲疊加過多的算法，并通過實(shí)驗(yàn)證明了相較于 DPAda_Random 算法和DPAda_Swing 算法，DPAda_Improved 算法在擁有更高的分類準(zhǔn)確率的同時(shí)，仍能實(shí)現(xiàn)數(shù)據(jù)的隱私保護(hù)。下一步，筆者將考慮把差分隱私應(yīng)用于其他集成學(xué)習(xí)算法。