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

第3章分布式隨機(jī)森林框架的構(gòu)建大規(guī)模數(shù)據(jù)的出現(xiàn)對(duì)數(shù)據(jù)的存儲(chǔ)和處理能力提出了新的挑戰(zhàn)，傳統(tǒng)基于單機(jī)的方法已無(wú)法滿足大數(shù)據(jù)的需要，所以基于分布式的數(shù)據(jù)存儲(chǔ)與處理框架被提出本章節(jié)提出了分布式交替方向乘子法用于處理不平衡大數(shù)據(jù)的分布式優(yōu)化問(wèn)題，將數(shù)據(jù)不平衡問(wèn)題轉(zhuǎn)化為兩個(gè)子問(wèn)題，即單節(jié)點(diǎn)正負(fù)樣本不平衡問(wèn)題與節(jié)點(diǎn)間數(shù)據(jù)樣本不平衡問(wèn)題。本文在單節(jié)點(diǎn)內(nèi)部使用隨機(jī)森林作為分類(lèi)器，在節(jié)點(diǎn)間使用ADMM算法的全局一致性框架解決不平衡大數(shù)據(jù)分類(lèi)問(wèn)題。分布式隨機(jī)森林算法框架隨著大數(shù)據(jù)的興起，分布式機(jī)器學(xué)習(xí)算法作為機(jī)器學(xué)習(xí)算法的擴(kuò)展被提出。往往因?yàn)榇髷?shù)據(jù)的數(shù)量巨大，結(jié)構(gòu)復(fù)雜等特性，傳統(tǒng)的機(jī)器學(xué)習(xí)算法已不再能夠滿足其需求。分布式機(jī)器學(xué)習(xí)通過(guò)分布式與并行化處理大數(shù)據(jù)的全局優(yōu)化問(wèn)題，將一個(gè)全局任務(wù)分割為若干個(gè)不同的小規(guī)模任務(wù)，在各節(jié)點(diǎn)并行化的基礎(chǔ)上，通過(guò)建立全局一致性框架來(lái)得到最終模型。目前采用的分布式機(jī)器學(xué)習(xí)算法往往基于各節(jié)點(diǎn)之間的全局一致性，即在各節(jié)點(diǎn)獨(dú)立計(jì)算的基礎(chǔ)上添加一致性約束，因此在各節(jié)點(diǎn)得到自身局部變量后，通過(guò)節(jié)點(diǎn)間的協(xié)調(diào)一致來(lái)實(shí)現(xiàn)全局優(yōu)化。圖3.1為本文提出的分布式隨機(jī)森林算法框架。圖3.1分布式隨機(jī)森林算法框架如上文所說(shuō)構(gòu)建本文的分布式隨機(jī)森林框架，如圖，各子節(jié)點(diǎn)內(nèi)采取上文中代價(jià)敏感隨機(jī)森林算法進(jìn)行局部樣本子集分類(lèi)，從而得到局部變量w，然后在i各子節(jié)點(diǎn)之間應(yīng)用交替方向乘子法，通過(guò)更新局部變量得到全局變量Z,并通過(guò)不斷迭代得到全局最優(yōu)值。3.2基于CS-ADMM的全局一致性框架ADMM算法在進(jìn)行機(jī)器學(xué)習(xí)過(guò)程中，是一種非常常見(jiàn)的優(yōu)化方法，能夠用來(lái)處理攜帶約束最小化問(wèn)題，因?yàn)樵摲ň邆淇煞纸庑院蛢?yōu)秀的收斂性，從而被用于求解分布式優(yōu)化問(wèn)題。其通過(guò)將原始問(wèn)題分解為若干個(gè)較小的子問(wèn)題，并通過(guò)子問(wèn)題之間的協(xié)調(diào)一致實(shí)現(xiàn)全局優(yōu)化。本章節(jié)將對(duì)ADMM算法的分解過(guò)程進(jìn)行具體論述。原始ADMM主要用于求解兩個(gè)函數(shù)之和最小化的凸優(yōu)化問(wèn)題，且函數(shù)之間具有一定線性約束。在分布式ADMM中,原始問(wèn)題應(yīng)該是可分解的，假設(shè)此時(shí)兩個(gè)目標(biāo)函數(shù)為f(x)和Q(x)，且兩個(gè)目標(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)本文采用代價(jià)敏感隨機(jī)森林算法作為分類(lèi)模型，由于對(duì)損失函數(shù)的重新構(gòu)造,原始問(wèn)題可表示為：min1IIWII2+C(c工 g+c工g)w2 pxjeD+jnxjeDrj其中C是懲罰參數(shù)且大于0，g表示誤分類(lèi)樣本x的代價(jià)，c和c分別是j j p n正樣本和負(fù)樣本的誤分類(lèi)代價(jià)參數(shù)。通過(guò)將原始問(wèn)題轉(zhuǎn)化為全局一致性問(wèn)題，原始問(wè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的全局一致性?？梢酝ㄟ^(guò)增廣拉格朗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是對(duì)偶變量，p是增廣拉格朗日函數(shù)的懲罰系數(shù)。將一次項(xiàng)和二次項(xiàng)合并,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)是子問(wèn)題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基于對(duì)偶坐標(biāo)下降法的子節(jié)點(diǎn)優(yōu)化在本章內(nèi)容中，本文采用對(duì)偶坐標(biāo)下降法算法進(jìn)行子節(jié)點(diǎn)的優(yōu)化，這一種算法主要是由子問(wèn)題逐漸轉(zhuǎn)變成對(duì)偶問(wèn)題［25］，按照對(duì)偶變量來(lái)對(duì)問(wèn)題進(jìn)行優(yōu)化處理進(jìn)而實(shí)現(xiàn)子問(wèn)題的局部變量更新。一般來(lái)說(shuō)，原始問(wè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個(gè)變量分別進(jìn)行求導(dǎo)其中a和B是拉格朗日乘子，l是數(shù)據(jù)集D中樣本的個(gè)數(shù)，對(duì)于w和g兩jj個(gè)變量分別進(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)的公式合并，可以將原始問(wèn)題的拉格朗日函數(shù)寫(xiě)為L(zhǎng)(w,g)=--^工為aayyxtx+ylia(1-yvTx)pi 2p jtjtjt j jijTOC\o"1-5"\h\zj=1t=1 j=1對(duì)偶坐標(biāo)下降法的優(yōu)化過(guò)程首先將上式改寫(xiě)為其對(duì)偶問(wèn)題，可得到minf(a)=—aTQa-bra,a 2ps.t?0<a<C, j=1,???,ljj i其中Q=yyxTx。當(dāng)x為正樣本時(shí)，誤分類(lèi)代價(jià)參數(shù)C=c*C；為負(fù)樣jtjtjt j jp本時(shí)，C=c*C。對(duì)于上式的優(yōu)化，對(duì)偶坐標(biāo)下降法通過(guò)控制對(duì)偶變量的其他jn維度來(lái)優(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ù)局部變量和其對(duì)偶變量對(duì)全局變量進(jìn)行更新。在分布式ADMM算法中，全局變量zk+1的目標(biāo)函數(shù)可表示為：zk+1=argming(z)+ 乙IIwk+1一z+耳k||22 i iz i=1(3.15)因此，通過(guò)對(duì)ws和耳s兩個(gè)變量的簡(jiǎn)單平均，可以全局變量zk+1。顯然，目標(biāo)i i函數(shù)對(duì)于全局變量應(yīng)該是可微的，因此，通過(guò)對(duì)其目標(biāo)函數(shù)求關(guān)于zk+1的偏導(dǎo)，則可由wk+1和qk兩個(gè)變量的加權(quán)之和得到全局變量：zk+1=工(wk+1+qk)(3.16)很顯然，本文提出的對(duì)偶問(wèn)題(3.10)和文獻(xiàn)［25］中提出的SVM-ADMM算法的對(duì)偶問(wèn)題具有一定相似性。同時(shí)一些研究［25-26］己經(jīng)證明了對(duì)偶坐標(biāo)下降算法夠在o(log(1/Y))迭代中收斂到y(tǒng)精度，即f(a)<f(a*)+Y。所以本文通過(guò)將單節(jié)點(diǎn)的對(duì)偶問(wèn)題(3.10)和對(duì)文獻(xiàn)的分析成果相聯(lián)系，然后在子問(wèn)題的優(yōu)化過(guò)程中，對(duì)偶坐標(biāo)下降法同樣可以獲得y精度的收斂結(jié)果。第4章分布式隨機(jī)森林框架的應(yīng)用數(shù)據(jù)集與實(shí)驗(yàn)環(huán)境在實(shí)驗(yàn)部分，本文采用公開(kāi)廣泛使用的不平衡數(shù)據(jù)集dosvsnormal,并從這些數(shù)據(jù)集里面隨機(jī)選擇一個(gè)二分類(lèi)數(shù)據(jù)集來(lái)為分類(lèi)提供研究。此數(shù)據(jù)集共包含4856151個(gè)樣本，共有41維特征，正負(fù)樣本的不平衡率為3.99。本文使用Hadoop與KVM虛擬化平臺(tái)搭建虛擬化集群環(huán)境，實(shí)驗(yàn)環(huán)境共包括五個(gè)節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)的內(nèi)存為4GB,操作系統(tǒng)為CentOS6.2,節(jié)點(diǎn)間采用MPI并行化接口。分布式框架中各節(jié)點(diǎn)可以采取不同的體系結(jié)構(gòu),即節(jié)點(diǎn)之間的邏輯結(jié)構(gòu)。也可以采取不同的通信協(xié)議。體系結(jié)構(gòu)和通信協(xié)議影響著節(jié)點(diǎn)間的消息傳遞機(jī)制和通信。本文采用基于同步通信模式的中心化網(wǎng)絡(luò)結(jié)構(gòu),如圖4.1所示。圖4.1節(jié)點(diǎn)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖所示,中心化結(jié)構(gòu)采取主從模式,即節(jié)點(diǎn)體系結(jié)構(gòu)中有4個(gè)從節(jié)點(diǎn)和一個(gè)主節(jié)點(diǎn),通過(guò)從節(jié)點(diǎn)之間的傳遞信息以及主節(jié)點(diǎn)進(jìn)行調(diào)控。每個(gè)從節(jié)點(diǎn)自行進(jìn)行分類(lèi)任務(wù),后將自身局部變量傳遞至主節(jié)點(diǎn),主節(jié)點(diǎn)基于所有子節(jié)點(diǎn)的局部變量進(jìn)行全局變量的優(yōu)化,后廣播至所有節(jié)點(diǎn),此過(guò)程在得到全局最優(yōu)解之前將不斷迭代。同步通信是分布式ADMM的通信協(xié)議之一，同步通信要求主節(jié)點(diǎn)在接收到所有從節(jié)點(diǎn)的局部變量之后,才進(jìn)行全局變量的更新。這是一種較為嚴(yán)苛的全局約束,因?yàn)樗缶W(wǎng)絡(luò)中的所有節(jié)點(diǎn)采用協(xié)作的模式,同步的執(zhí)行子問(wèn)題的優(yōu)化。

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