分布式隨機森林框架的構(gòu)建

第3章分布式隨機森林框架的構(gòu)建大規(guī)模數(shù)據(jù)的出現(xiàn)對數(shù)據(jù)的存儲和處理能力提出了新的挑戰(zhàn)，傳統(tǒng)基于單機的方法已無法滿足大數(shù)據(jù)的需要，所以基于分布式的數(shù)據(jù)存儲與處理框架被提出本章節(jié)提出了分布式交替方向乘子法用于處理不平衡大數(shù)據(jù)的分布式優(yōu)化問題，將數(shù)據(jù)不平衡問題轉(zhuǎn)化為兩個子問題，即單節(jié)點正負(fù)樣本不平衡問題與節(jié)點間數(shù)據(jù)樣本不平衡問題。本文在單節(jié)點內(nèi)部使用隨機森林作為分類器，在節(jié)點間使用ADMM算法的全局一致性框架解決不平衡大數(shù)據(jù)分類問題。分布式隨機森林算法框架隨著大數(shù)據(jù)的興起，分布式機器學(xué)習(xí)算法作為機器學(xué)習(xí)算法的擴展被提出。往往因為大數(shù)據(jù)的數(shù)量巨大，結(jié)構(gòu)復(fù)雜等特性，傳統(tǒng)的機器學(xué)習(xí)算法已不再能夠滿足其需求。分布式機器學(xué)習(xí)通過分布式與并行化處理大數(shù)據(jù)的全局優(yōu)化問題，將一個全局任務(wù)分割為若干個不同的小規(guī)模任務(wù)，在各節(jié)點并行化的基礎(chǔ)上，通過建立全局一致性框架來得到最終模型。目前采用的分布式機器學(xué)習(xí)算法往往基于各節(jié)點之間的全局一致性，即在各節(jié)點獨立計算的基礎(chǔ)上添加一致性約束，因此在各節(jié)點得到自身局部變量后，通過節(jié)點間的協(xié)調(diào)一致來實現(xiàn)全局優(yōu)化。圖3.1為本文提出的分布式隨機森林算法框架。圖3.1分布式隨機森林算法框架如上文所說構(gòu)建本文的分布式隨機森林框架，如圖，各子節(jié)點內(nèi)采取上文中代價敏感隨機森林算法進(jìn)行局部樣本子集分類，從而得到局部變量w，然后在i各子節(jié)點之間應(yīng)用交替方向乘子法，通過更新局部變量得到全局變量Z,并通過不斷迭代得到全局最優(yōu)值。3.2基于CS-ADMM的全局一致性框架ADMM算法在進(jìn)行機器學(xué)習(xí)過程中，是一種非常常見的優(yōu)化方法，能夠用來處理攜帶約束最小化問題，因為該法具備可分解性和優(yōu)秀的收斂性，從而被用于求解分布式優(yōu)化問題。其通過將原始問題分解為若干個較小的子問題，并通過子問題之間的協(xié)調(diào)一致實現(xiàn)全局優(yōu)化。本章節(jié)將對ADMM算法的分解過程進(jìn)行具體論述。原始ADMM主要用于求解兩個函數(shù)之和最小化的凸優(yōu)化問題，且函數(shù)之間具有一定線性約束。在分布式ADMM中,原始問題應(yīng)該是可分解的，假設(shè)此時兩個目標(biāo)函數(shù)為f(x)和Q(x)，且兩個目標(biāo)函數(shù)之一f(x)是可分解的，那么可以得到原始目標(biāo)函數(shù):(3.1)min工f(x)+o(z)(3.1)iixiA,xn,xAls.t.Ax+Bz=C,i=1,2,K,n.i其中x=(x,A,x)。函數(shù)(3.15)即為分布式ADMM的全局目標(biāo)函數(shù)。其最優(yōu)解1 n可表示為：(3.2)p*=inf{f(x)+0(z)IAx+Bz=C}(3.2)本文采用代價敏感隨機森林算法作為分類模型，由于對損失函數(shù)的重新構(gòu)造,原始問題可表示為：min1IIWII2+C(c工 g+c工g)w2 pxjeD+jnxjeDrj其中C是懲罰參數(shù)且大于0，g表示誤分類樣本x的代價，c和c分別是j j p n正樣本和負(fù)樣本的誤分類代價參數(shù)。通過將原始問題轉(zhuǎn)化為全局一致性問題，原始問題可以重構(gòu)為：min1IIzII2+C工(c工g+c工g) (3.3)2w. WnzP j n ji=1 xgD+ xeD~ji jis.t.w=z,i=1,2,...,n.i其中w為局部變量，應(yīng)滿足全局變量z的全局一致性?？梢酝ㄟ^增廣拉格朗i日函數(shù)可將上式表示為:TOC\o"1-5"\h\z\o"CurrentDocument"Lp(w,z,九)=—IIzII2+C工(c +c) (3.4)2 pjnji=1 xgD+ xgD_ji ji+工(Xt(w一z)+—IIw一zII2)ii 2ii=1其中X是對偶變量，p是增廣拉格朗日函數(shù)的懲罰系數(shù)。將一次項和二次項合并,i上式可以重新表示為：TOC\o"1-5"\h\z\o"CurrentDocument"Lp(w,z,u)=0(z)+Z(f(w)+PIIw-z+qII2) (3.5)ii2i ii=1其中f(w)是子問題i的數(shù)據(jù)集D在當(dāng)前訓(xùn)練模型下的損失函數(shù)。因此可得到ii iCS-ADMM框架的優(yōu)化步驟為：wk+1=argminf(w)+PIIw一zk+耳kII2i wjii2i i\o"CurrentDocument"zk+1=argming(z)+-P^nIIwk+1一z+耳kII2 (3.6)z 2 i=1i i耳k+1=耳k+wk+1—zk+1i i iCS-ADMM算法的大概流程如算法1所示：_算法1CS-ADMM Input:Output:optimizationvariables,1：fork=0,l,...,do5:endfor3.3基于對偶坐標(biāo)下降法的子節(jié)點優(yōu)化在本章內(nèi)容中，本文采用對偶坐標(biāo)下降法算法進(jìn)行子節(jié)點的優(yōu)化，這一種算法主要是由子問題逐漸轉(zhuǎn)變成對偶問題［25］，按照對偶變量來對問題進(jìn)行優(yōu)化處理進(jìn)而實現(xiàn)子問題的局部變量更新。一般來說，原始問題的拉格朗日函數(shù)可以表示為：3.7)Lp(w,g)=EIIw-vII2+3.7)i 2ii pj njxgD+ xgD-jiji+ylia(1-g-ywx)-ylipgj jjij jjTOC\o"1-5"\h\zj=1 j=1jj個變量分別進(jìn)行求導(dǎo)其中a和B是拉格朗日乘子，l是數(shù)據(jù)集D中樣本的個數(shù)，對于w和g兩jj個變量分別進(jìn)行求導(dǎo)ol(w,g) / 、y一pi二p(w-v)-2Layx二0,ow ii jjji j=13.8)3.9)3.10)o3.8)3.9)3.10)p二c*C-a-p二0,xgD+,og p jj jijoL(w,g)p二c*C-a-p二0,xgD-.Og n jjjij將上述求偏導(dǎo)的公式合并，可以將原始問題的拉格朗日函數(shù)寫為L(w,g)=--^工為aayyxtx+ylia(1-yvTx)pi 2p jtjtjt j jijTOC\o"1-5"\h\zj=1t=1 j=1對偶坐標(biāo)下降法的優(yōu)化過程首先將上式改寫為其對偶問題，可得到minf(a)=—aTQa-bra,a 2ps.t?0<a<C, j=1,???,ljj i其中Q=yyxTx。當(dāng)x為正樣本時，誤分類代價參數(shù)C=c*C；為負(fù)樣jtjtjt j jp本時，C=c*C。對于上式的優(yōu)化，對偶坐標(biāo)下降法通過控制對偶變量的其他jn維度來優(yōu)化某一特定維度。因此在第k次迭代中，關(guān)于a的偏導(dǎo)為：

(3.11)Vf(w)二1史wQ-b二ywrx-1

j p (3.11)然后將Vf(ar)在ar的取值范圍內(nèi)進(jìn)行映射，由此可得a的更新可以表示為:Vf(ak)ak+i=min(max(ak一j,0),C).

j j為:Vf(ak)ak+i=min(max(ak一j,0),C).

j jQ j(3.12)映射梯度可以重構(gòu)為:Vf(ak)=ywkx一1(3.13)因此可以得到局部變量w的更新步驟:wk+1=wk+(ak+1—ak)yx(3.14)得到局部變量后，根據(jù)局部變量和其對偶變量對全局變量進(jìn)行更新。在分布式ADMM算法中，全局變量zk+1的目標(biāo)函數(shù)可表示為：zk+1=argming(z)+ 乙IIwk+1一z+耳k||22 i iz i=1(3.15)因此，通過對ws和耳s兩個變量的簡單平均，可以全局變量zk+1。顯然，目標(biāo)i i函數(shù)對于全局變量應(yīng)該是可微的，因此，通過對其目標(biāo)函數(shù)求關(guān)于zk+1的偏導(dǎo)，則可由wk+1和qk兩個變量的加權(quán)之和得到全局變量：zk+1=工(wk+1+qk)(3.16)很顯然，本文提出的對偶問題(3.10)和文獻(xiàn)［25］中提出的SVM-ADMM算法的對偶問題具有一定相似性。同時一些研究［25-26］己經(jīng)證明了對偶坐標(biāo)下降算法夠在o(log(1/Y))迭代中收斂到y(tǒng)精度，即f(a)<f(a*)+Y。所以本文通過將單節(jié)點的對偶問題(3.10)和對文獻(xiàn)的分析成果相聯(lián)系，然后在子問題的優(yōu)化過程中，對偶坐標(biāo)下降法同樣可以獲得y精度的收斂結(jié)果。第4章分布式隨機森林框架的應(yīng)用數(shù)據(jù)集與實驗環(huán)境在實驗部分，本文采用公開廣泛使用的不平衡數(shù)據(jù)集dosvsnormal,并從這些數(shù)據(jù)集里面隨機選擇一個二分類數(shù)據(jù)集來為分類提供研究。此數(shù)據(jù)集共包含4856151個樣本，共有41維特征，正負(fù)樣本的不平衡率為3.99。本文使用Hadoop與KVM虛擬化平臺搭建虛擬化集群環(huán)境，實驗環(huán)境共包括五個節(jié)點。每個節(jié)點的內(nèi)存為4GB,操作系統(tǒng)為CentOS6.2,節(jié)點間采用MPI并行化接口。分布式框架中各節(jié)點可以采取不同的體系結(jié)構(gòu),即節(jié)點之間的邏輯結(jié)構(gòu)。也可以采取不同的通信協(xié)議。體系結(jié)構(gòu)和通信協(xié)議影響著節(jié)點間的消息傳遞機制和通信。本文采用基于同步通信模式的中心化網(wǎng)絡(luò)結(jié)構(gòu),如圖4.1所示。圖4.1節(jié)點網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖所示,中心化結(jié)構(gòu)采取主從模式,即節(jié)點體系結(jié)構(gòu)中有4個從節(jié)點和一個主節(jié)點,通過從節(jié)點之間的傳遞信息以及主節(jié)點進(jìn)行調(diào)控。每個從節(jié)點自行進(jìn)行分類任務(wù),后將自身局部變量傳遞至主節(jié)點,主節(jié)點基于所有子節(jié)點的局部變量進(jìn)行全局變量的優(yōu)化,后廣播至所有節(jié)點,此過程在得到全局最優(yōu)解之前將不斷迭代。同步通信是分布式ADMM的通信協(xié)議之一，同步通信要求主節(jié)點在接收到所有從節(jié)點的局部變量之后,才進(jìn)行全局變量的更新。這是一種較為嚴(yán)苛的全局約束,因為它要求網(wǎng)絡(luò)中的所有節(jié)點采用協(xié)作的模式,同步的執(zhí)行子問題的優(yōu)化。

實驗結(jié)果分析為了評估本文提出的基于代價敏感的隨機森林算法(CSRF)對于不平衡數(shù)據(jù)樣本的分類有效性，本文在單節(jié)點上進(jìn)行了分類實驗，與原始隨機森林算法圖4.2CSRF與RF算法對比(RF)進(jìn)行了對比。實驗設(shè)置節(jié)點內(nèi)樣本個數(shù)為10a5不變，采用隨機抽樣的方法，分別抽取正負(fù)樣本的不平衡率為1,1.5,2,2.5,3,3.5,4。誤分類代價參數(shù)(c,c)按照經(jīng)驗設(shè)置為(IR,圖4.2CSRF與RF算法對比如圖所示，隨著不平衡率的增加，原始隨機森林算法(RF)與代價敏感隨機森林算法(CSRF)的分類準(zhǔn)確度都有所下降，但是CSRF算法的F-值始終高于RF算法。而且當(dāng)不平衡率為2.5至4時，CSRF算法的F-值只有輕微下降，證明了該算法具有一定的魯棒性?？梢?，本文提出的代價敏感隨機森林算法在不平衡分類任務(wù)上是更有效的?；诖私Y(jié)果，本文在多節(jié)點環(huán)境中評估了分布式框架對于不平衡大數(shù)據(jù)的分類效果。以證明本文所提及的CS-ADMM算法的分類效果，把幾種ADMM算法和本論文中的算法進(jìn)行比對。對比分布式算法的具體情況為：ADMM—DCD:在分布式ADMM算法中，對偶坐標(biāo)下降算法被用來解決子問題的優(yōu)化。ADMM—TRON:在分布式ADMM算法中，對于優(yōu)化子問題，選擇信任域牛頓法。CS—ADMM—DCD：在分布式ADMM中，采用擴展對偶坐標(biāo)下降對子問題進(jìn)行優(yōu)化，同時子節(jié)點內(nèi)部采用基于代價敏感的隨機森林算法。CS—ADMM—TRON:在分布式ADMM算法中，通過信任域牛頓法對子問題進(jìn)行優(yōu)化，同時子節(jié)點內(nèi)部采用基于代價敏感的隨機森林算法。實驗中設(shè)置每個節(jié)點的樣本數(shù)量為5x10a5不變，且在每個節(jié)點內(nèi)部抽取正負(fù)樣本比率為3:1，實驗反復(fù)進(jìn)行十次，主要是為了提高研究結(jié)果的準(zhǔn)確性，并且最終選擇最終結(jié)果的平均值，對本文的算法和其他對比算法的分類性能進(jìn)行對比。本文采用幾何平均值(GeometricMean，GM)和卩-F值(F-Measure，F(xiàn)M)作為準(zhǔn)確度評估標(biāo)準(zhǔn)，采用訓(xùn)練時間作為算法效率評估指標(biāo)，其中訓(xùn)練時間包括節(jié)點內(nèi)部的計算時間與節(jié)點之間的通信時間。實驗結(jié)果如表4.1所示。表4.1CS-ADMM算法實驗結(jié)果ADMM-DCDADMM-TRONCS-ADMM-DCDCS-ADMM-TRONFM(%):F-值95.7694.9296.9395.57GM(%):幾何平均數(shù)96.9195.0797.2596.33Ttim(s):訓(xùn)練時間72.5071.7479.1780.25由實驗結(jié)果可得，DCD算法的精度相對TRON相對較高，且具有較少的訓(xùn)練時間，即可證明此算法對于不平衡大數(shù)據(jù)分類的有效性。因為在進(jìn)行優(yōu)化時，對偶坐標(biāo)下降法的時間復(fù)雜度是O(nk),nk是所有訓(xùn)練樣本中非零元素之和。但是信任域牛頓法算法的復(fù)雜度是O(dnk)，其中d代表共軛梯度的迭代次數(shù)。而且，牛頓法采用海森矩陣，但是在樣本數(shù)量較大時，海森矩陣是一個龐大的方陣，對其計算需要花費巨大開銷。綜上所述，使用牛頓法來解決大規(guī)模數(shù)據(jù)的分布式分類問題的局限性。對于超參數(shù)的取值，本文通過五折交叉驗證從區(qū)間2i(i=-3，..,8)選取超參數(shù)C。另外，為了驗證超參數(shù)對CS-ADMM-DCD算法的影響，本文分析了超參數(shù)C的取值從2-3到28，GM和FM曲線的變化趨勢，實驗結(jié)果如圖4.3。當(dāng)超參數(shù)C逐漸變大，F(xiàn)M和GM值也隨之變大，波動逐漸平緩?？偠灾疚奶岢龅幕趯ε甲鴺?biāo)下降法的CS-ADMM框架在不平衡大數(shù)據(jù)分類上效果較好，具有一定的魯棒性。圖4.3F值和幾何平均數(shù)隨著超參數(shù)C的變化趨勢算法魯棒性分析如前文提到的，在實際生活中，數(shù)據(jù)來源復(fù)雜混亂，本身具有一定的不平衡性。在將數(shù)據(jù)