段文杰 童孟軍

1(浙江農(nóng)林大學(xué)信息工程學(xué)院 浙江 杭州 311300)2(浙江省林業(yè)智能監(jiān)測(cè)與信息技術(shù)研究重點(diǎn)實(shí)驗(yàn)室 浙江 杭州 311300)

0 引 言

隨機(jī)森林算法是一種基于樹模型的集成學(xué)習(xí)算法，通過訓(xùn)練多棵決策樹以獲得最終的預(yù)測(cè)結(jié)果，并且在訓(xùn)練過程中對(duì)輸入特征和樣本進(jìn)行隨機(jī)抽樣，增加了一定的隨機(jī)性，避免了高相關(guān)性的特征在多次訓(xùn)練中造成的干擾，因此具有較好的泛化能力。然而，傳統(tǒng)隨機(jī)森林算法沒有對(duì)分類能力不同的決策樹進(jìn)行區(qū)分，導(dǎo)致分類能力好的決策樹和分類能力不好的決策樹具有相同的投票能力，而且在訓(xùn)練過程中需要生成多棵決策樹，導(dǎo)致算法的運(yùn)行時(shí)間較長(zhǎng)。彭徵等[1]提出了基于隨機(jī)森林的文本分類并行化研究，通過對(duì)訓(xùn)練樣本進(jìn)行欠取樣來減少不平衡數(shù)據(jù)對(duì)隨機(jī)森林算法的影響，提高了隨機(jī)森林算法的分類精度，并結(jié)合Spark并行化方法減少了算法的運(yùn)行時(shí)間，但并沒有在Spark層面上進(jìn)行改進(jìn)，僅僅只是應(yīng)用了Spark并行化的特點(diǎn)。王日升[2]進(jìn)行了基于Spark的一種改進(jìn)的隨機(jī)森林算法研究，通過設(shè)置閾值來剔除那些分類能力弱的決策樹從而改進(jìn)隨機(jī)森林算法并在Spark單機(jī)模式下進(jìn)行實(shí)驗(yàn)，但通過簡(jiǎn)單設(shè)置閾值的方式可能會(huì)導(dǎo)致部分有用的決策樹被剔除，影響最終結(jié)果，而且僅僅只是在Spark單機(jī)模式下進(jìn)行實(shí)驗(yàn)，沒有達(dá)到Spark并行化運(yùn)行的條件。Chen等[3]進(jìn)行了分布式并行隨機(jī)森林算法在生物醫(yī)學(xué)上的應(yīng)用研究，提出了一種通過袋外測(cè)試的方法對(duì)隨機(jī)森林算法進(jìn)行加權(quán)投票，并提出了利用垂直數(shù)據(jù)劃分的方法來降低Spark分布式計(jì)算節(jié)點(diǎn)之間的數(shù)據(jù)通信成本。但是袋外測(cè)試的分類準(zhǔn)確率不高，而垂直數(shù)據(jù)劃分的方法太過復(fù)雜，實(shí)現(xiàn)成本過高。結(jié)合相關(guān)學(xué)者們的成果和自己的實(shí)驗(yàn)研究，本文提出一種基于Spark加權(quán)投票的隨機(jī)森林算法，通過計(jì)算隨機(jī)森林中決策樹的AUC值來為每棵決策樹分配投票權(quán)重，提高隨機(jī)森林算法的分類精度，并提出一種數(shù)據(jù)索引抽樣表和隨機(jī)特征索引表來減少Spark與磁盤數(shù)據(jù)交互的次數(shù)，加快隨機(jī)森林算法的并行化進(jìn)程，從而提高運(yùn)行效率。

1 相關(guān)技術(shù)

1.1 隨機(jī)森林算法

隨機(jī)森林算法原理如圖1 所示。采用Bagging抽樣的方法從原始數(shù)據(jù)集中隨機(jī)地、有放回地抽取一定數(shù)據(jù)組成若干訓(xùn)練子集，隨機(jī)挑選特征屬性來訓(xùn)練這些子集得到相對(duì)應(yīng)的決策樹，然后將測(cè)試集分別導(dǎo)入到?jīng)Q策樹中得到對(duì)應(yīng)分類結(jié)果，最后通過投票選出最終分類結(jié)果[4-5]。

圖1 隨機(jī)森林算法流程

1.2 Spark

Spark是一種基于Hadoop的分布式計(jì)算框架，它改進(jìn)了在Hadoop中基于磁盤運(yùn)算的缺陷，使用基于內(nèi)存的計(jì)算方式大大提高了并行化的效率。并且Spark能夠與Hadoop提供的分布式文件系統(tǒng)HDFS相結(jié)合，使用其現(xiàn)有的集群資源管控系統(tǒng)作為數(shù)據(jù)存儲(chǔ)的持久層。Spark還提供了一個(gè)機(jī)器學(xué)習(xí)庫Spark-MLlib，其中包含了一系列常用機(jī)器學(xué)習(xí)算法的API，如邏輯回歸、決策樹、隨機(jī)森林、K-mean聚類等[6-7]。

1.3 ROC和AUC

ROC曲線(Receiver Operating Characteristic curve)又稱接受者操作特征曲線，用于評(píng)估一個(gè)分類器的性能好壞，AUC值定義為ROC曲線下的面積，因此AUC值介于0～1之間。在實(shí)際應(yīng)用過程中通過觀察ROC曲線并不能準(zhǔn)確地區(qū)分兩個(gè)分類器的性能好壞，而是通過計(jì)算AUC值來判斷，AUC值越大，則對(duì)應(yīng)的分類器的性能越好。

1.4 AUC的計(jì)算方法

(1) 根據(jù)AUC的定義可以計(jì)算 ROC 曲線下的面積來得到AUC的值。但由于測(cè)試集的數(shù)量有限，最終得到的ROC曲線不是光滑的曲線而是階梯形的，所以計(jì)算結(jié)果存在誤差。

(2) 根據(jù)AUC的物理意義計(jì)算取到正例比取到負(fù)例大的概率。取N×M(N為正樣本數(shù)，M為負(fù)樣本數(shù))正負(fù)樣本對(duì)，比較score(概率得分)，最后得到AUC。時(shí)間復(fù)雜度為O(N×M)。

(1)

(3) 第三種方法與第二種方法類似，但是復(fù)雜度減小了。它首先對(duì)數(shù)據(jù)按概率得分從小到大進(jìn)行排序，然后將概率得分最小的rank設(shè)為1，以此類推，然后把所有的正類樣本的rank相加，再減去M-1種兩個(gè)正樣本組合的情況。得到的就是所有的樣本中正樣本的score大于負(fù)樣本score的個(gè)數(shù)。最后再除以M×N。公式為：

(2)

1.5 加權(quán)投票法

在傳統(tǒng)隨機(jī)森林算法中，沒有考慮到出現(xiàn)兩種或兩種以上票數(shù)相同的情況[8]，由于AUC值介于0～1之間，所以通過AUC加權(quán)投票后的總票數(shù)也是實(shí)數(shù)，因此可以有效避免票數(shù)相同的情況發(fā)生。在實(shí)驗(yàn)中，首先通過傳統(tǒng)的隨機(jī)森林算法訓(xùn)練出各棵決策樹模型{f1(x)，f2(x)，…,fk(x)},然后計(jì)算出每棵決策樹的AUC值{A1，A2，…,Ak}，那么最終模型的預(yù)測(cè)結(jié)果可以表示為：

(3)

式中：C為所有分類標(biāo)簽的集合；li為集合C中第i個(gè)分類標(biāo)簽；I(fj(x)=li)為示性函數(shù)，當(dāng)決策樹f(x)的預(yù)測(cè)結(jié)果為分類標(biāo)簽li時(shí)示性函數(shù)等于1，否則等于0;Aj為第j棵決策樹在投票過程中的權(quán)重AUC值;ci為第i個(gè)分類標(biāo)簽所獲得的加權(quán)投票的結(jié)果[9]。

2 基于Spark的并行隨機(jī)森林算法

2.1 DIS數(shù)據(jù)索引抽樣

在傳統(tǒng)隨機(jī)森林算法中，Bagging抽樣的時(shí)間會(huì)隨著數(shù)據(jù)集規(guī)模的增大而呈指數(shù)級(jí)上升，并且Spark在這個(gè)過程中會(huì)分配額外的存儲(chǔ)空間存儲(chǔ)抽樣后形成的訓(xùn)練集，同時(shí)會(huì)進(jìn)行大量的磁盤數(shù)據(jù)交互，降低算法并行化的效率。因此，本文提出一種數(shù)據(jù)索引抽樣表DIS(Data Index Sampling)，通過抽樣后獲取抽樣數(shù)據(jù)在原始數(shù)據(jù)集下的索引號(hào)，將索引號(hào)記錄在DIS表中，而不需要真正進(jìn)行空間分配和數(shù)據(jù)劃分。DIS索引表示例如表1所示。

表1 DIS索引表

2.2 RFI隨機(jī)特征索引

隨機(jī)森林算法中的“隨機(jī)”不但體現(xiàn)在隨機(jī)抽樣形成訓(xùn)練數(shù)據(jù)集，而且還體現(xiàn)在隨機(jī)選擇特征屬性構(gòu)建決策樹，考慮到空間分配和Spark與磁盤交互的問題[10]，我們把所有的特征名稱按順序放入一個(gè)數(shù)組中，然后隨機(jī)挑選特征名稱并將對(duì)應(yīng)的索引號(hào)(數(shù)組下標(biāo))放入一個(gè)隨機(jī)特征索引表RFI(Random Feature Index)中，再把RFI和DIS一起分配給Slaver計(jì)算節(jié)點(diǎn)訓(xùn)練決策樹。由于隨機(jī)森林算法中決策樹的構(gòu)造過程是相互獨(dú)立、互不影響的，所以可以并行生成多棵決策樹。RFI索引表示如表2所示。

表2 RFI索引表

2.3 SP-RF并行化流程

1) 創(chuàng)建一個(gè)DIS索引表來存儲(chǔ)每次抽樣過程中得到的對(duì)應(yīng)于原始數(shù)據(jù)的索引號(hào)。

2) 將所有的特征名稱按順序放入一個(gè)數(shù)組中，然后每次抽取一定數(shù)量的特征名稱以數(shù)組下標(biāo)的形式保存在RFI索引表中。

3) 將DIS表和RFI表一起分配給Spark集群里的Slaver計(jì)算節(jié)點(diǎn)，使每個(gè)計(jì)算節(jié)點(diǎn)上有一個(gè)或多個(gè)DIS表和RFI表。

4) 在各個(gè)分布式計(jì)算節(jié)點(diǎn)上采用C4.5算法構(gòu)建決策樹，執(zhí)行信息增益比的計(jì)算任務(wù)。

5) 將各個(gè)分布式計(jì)算節(jié)點(diǎn)的中間結(jié)果進(jìn)行匯總，提交給Master節(jié)點(diǎn)執(zhí)行后續(xù)決策樹的構(gòu)建任務(wù)[11]，SP-RF并行化流程如圖2所示，其中DIS_RDD和RFI_RDD表示將訓(xùn)練樣本和特征數(shù)組分別放到兩個(gè)RDD存儲(chǔ)單元中。

2.4 算法流程

SP-RF算法在Spark框架上并行化運(yùn)行的流程如圖3所示，整個(gè)流程可以分為Map和Reduce兩個(gè)階段[12-14]。在Map階段主要是對(duì)原始數(shù)據(jù)和特征名稱進(jìn)行索引抽樣，然后把對(duì)應(yīng)的索引記錄分別保存在兩個(gè)data_RDD和feature_RDD中，當(dāng)進(jìn)程讀到索引表里的記錄時(shí)，再返回到原始數(shù)據(jù)集和特征數(shù)組里抽取訓(xùn)練數(shù)據(jù)和特征組存放到D1_RDD和F1_RDD中。在Reduce階段主要是將得到的D1_RDD和F1_RDD的數(shù)據(jù)和特征進(jìn)行計(jì)算構(gòu)建相應(yīng)的決策樹，并計(jì)算每棵決策樹的AUC值作為加權(quán)投票的權(quán)重，組成一個(gè)隨機(jī)森林，然后對(duì)導(dǎo)入的測(cè)試集進(jìn)行分類，統(tǒng)計(jì)投票結(jié)果得到最終的分類結(jié)果。圖3中：實(shí)線箭頭表示訓(xùn)練階段；虛線箭頭表示測(cè)試階段；虛線框內(nèi)表示并行化部分[15]。

圖3 基于Spark的改進(jìn)隨機(jī)森林算法流程

3 實(shí) 驗(yàn)

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

本實(shí)驗(yàn)中的軟件環(huán)境為：VMware Workstation12.5.7；Ubuntu16.0.4；Spark-2.1.0；Hadoop-2.7.0；Java-1.8.0_181；Scala-2.10.0；搭建了4臺(tái)虛擬機(jī)，其中3臺(tái)作為Slaver計(jì)算節(jié)點(diǎn)，1臺(tái)Master主控節(jié)點(diǎn)負(fù)責(zé)與各個(gè)計(jì)算節(jié)點(diǎn)通信和資源分配。

本實(shí)驗(yàn)中的硬件環(huán)境為：處理器Intel(R) Core(TM) i7-8700M，主頻3.20 GHz，內(nèi)存為16 GB。

3.2 評(píng)價(jià)指標(biāo)

由于本次實(shí)驗(yàn)研究的是一個(gè)二分類問題，而且樣本的分布比較均衡，故使用精準(zhǔn)率作為評(píng)價(jià)指標(biāo)，精準(zhǔn)率的定義為在所有被預(yù)測(cè)為正的樣本中實(shí)際為正的樣本的概率，其公式如下：

式中：TP表示預(yù)測(cè)類別是正例，真實(shí)類別也是正例；FP表示預(yù)測(cè)類別是正例，真實(shí)類別是反例。

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

本文實(shí)驗(yàn)使用的數(shù)據(jù)集是UCI Machine Learning Repository: Data sets下載的4個(gè)二分類數(shù)據(jù)集，包括titanic、spambase、mushrom、banknote等,如表3所示。

表3 實(shí)驗(yàn)數(shù)據(jù)集說明

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

從圖4中可以看出在Spark集群上SP-RF算法要優(yōu)于傳統(tǒng)RF算法，特別是在titanic和mushroom數(shù)據(jù)集上提升較為明顯，這是因?yàn)閭鹘y(tǒng)隨機(jī)森林算法在titanic和mushroom數(shù)據(jù)集上分類精度還有較大提升空間，因此經(jīng)過加權(quán)投票后的效果較好。從圖5可以看出，SP-RF算法在各個(gè)數(shù)據(jù)集上的運(yùn)行時(shí)間較傳統(tǒng)RF算法均有較大減少，這是因?yàn)榻?jīng)過優(yōu)化后的SP-RF算法減少了Spark進(jìn)程等待的時(shí)間[16-18]。

圖4 算法分類精度對(duì)比 圖5 算法運(yùn)行時(shí)間對(duì)比

圖6為SP-RF算法在Python平臺(tái)和Spark平臺(tái)上的運(yùn)行時(shí)間對(duì)比，可以看出SP-RF算法在Spark平臺(tái)上的運(yùn)行時(shí)間要遠(yuǎn)低于Python平臺(tái)，主要是因?yàn)槠淅帽痪彺孢M(jìn)內(nèi)存的中間計(jì)算結(jié)果，在各個(gè)分區(qū)上多線程的并行計(jì)算節(jié)省了大部分時(shí)間。由于本文實(shí)驗(yàn)設(shè)備條件有限，只搭建了三個(gè)Slaver計(jì)算節(jié)點(diǎn)，可預(yù)見當(dāng)增加計(jì)算節(jié)點(diǎn)的數(shù)量后，在進(jìn)行更大數(shù)據(jù)量的實(shí)驗(yàn)中算法的運(yùn)行效率將會(huì)比傳統(tǒng)算法有指數(shù)級(jí)的提升[19-20]。

圖6 SP-RF算法在各平臺(tái)的運(yùn)行時(shí)間

4 結(jié) 語

本文提出一種基于Spark的并行隨機(jī)森林算法。采用加權(quán)投票的方式提高隨機(jī)森林算法的分類精度，并結(jié)合Spark并行化的特點(diǎn)，提出了利用數(shù)據(jù)索引抽樣(DIS)和隨機(jī)特征索引(RFI)的方法提高隨機(jī)森林算法在Spark上并行化運(yùn)行的效率。實(shí)驗(yàn)結(jié)果表明SP-RF算法無論是在分類精度還是運(yùn)行時(shí)間上都比傳統(tǒng)隨機(jī)森林算法更勝一籌。在以后的研究中，將進(jìn)一步對(duì)隨機(jī)森林算法在特征選擇、決策樹之間相似度等方面進(jìn)行改進(jìn)從而提高隨機(jī)森林算法的分類精度，并且結(jié)合Spark并行化的特點(diǎn)對(duì)隨機(jī)森林算法進(jìn)行優(yōu)化，使隨機(jī)森林算法在Spark平臺(tái)上運(yùn)行得更加高效。