一種基于Spark的改進隨機森林算法

段文杰 童孟軍

1(浙江農林大學信息工程學院 浙江 杭州 311300)2(浙江省林業智能監測與信息技術研究重點實驗室 浙江 杭州 311300)

0 引 言

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

1 相關技術

1.1 隨機森林算法

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

圖1 隨機森林算法流程

1.2 Spark

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

1.3 ROC和AUC

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

1.4 AUC的計算方法

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

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

(1)

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

(2)

1.5 加權投票法

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

(3)

式中：C為所有分類標簽的集合；li為集合C中第i個分類標簽；I(fj(x)=li)為示性函數，當決策樹f(x)的預測結果為分類標簽li時示性函數等于1，否則等于0;Aj為第j棵決策樹在投票過程中的權重AUC值;ci為第i個分類標簽所獲得的加權投票的結果[9]。

2 基于Spark的并行隨機森林算法

2.1 DIS數據索引抽樣

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

表1 DIS索引表

2.2 RFI隨機特征索引

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

表2 RFI索引表

2.3 SP-RF并行化流程

1) 創建一個DIS索引表來存儲每次抽樣過程中得到的對應于原始數據的索引號。

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

3) 將DIS表和RFI表一起分配給Spark集群里的Slaver計算節點，使每個計算節點上有一個或多個DIS表和RFI表。

4) 在各個分布式計算節點上采用C4.5算法構建決策樹，執行信息增益比的計算任務。

5) 將各個分布式計算節點的中間結果進行匯總，提交給Master節點執行后續決策樹的構建任務[11]，SP-RF并行化流程如圖2所示，其中DIS_RDD和RFI_RDD表示將訓練樣本和特征數組分別放到兩個RDD存儲單元中。

2.4 算法流程

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

圖3 基于Spark的改進隨機森林算法流程

3 實 驗

3.1 實驗環境

本實驗中的軟件環境為：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臺虛擬機，其中3臺作為Slaver計算節點，1臺Master主控節點負責與各個計算節點通信和資源分配。

本實驗中的硬件環境為：處理器Intel(R) Core(TM) i7-8700M，主頻3.20 GHz，內存為16 GB。

3.2 評價指標

由于本次實驗研究的是一個二分類問題，而且樣本的分布比較均衡，故使用精準率作為評價指標，精準率的定義為在所有被預測為正的樣本中實際為正的樣本的概率，其公式如下：

式中：TP表示預測類別是正例，真實類別也是正例；FP表示預測類別是正例，真實類別是反例。

3.3 實驗數據

本文實驗使用的數據集是UCI Machine Learning Repository: Data sets下載的4個二分類數據集，包括titanic、spambase、mushrom、banknote等,如表3所示。

表3 實驗數據集說明

3.4 實驗結果

從圖4中可以看出在Spark集群上SP-RF算法要優于傳統RF算法，特別是在titanic和mushroom數據集上提升較為明顯，這是因為傳統隨機森林算法在titanic和mushroom數據集上分類精度還有較大提升空間，因此經過加權投票后的效果較好。從圖5可以看出，SP-RF算法在各個數據集上的運行時間較傳統RF算法均有較大減少，這是因為經過優化后的SP-RF算法減少了Spark進程等待的時間[16-18]。

圖4 算法分類精度對比 圖5 算法運行時間對比

圖6為SP-RF算法在Python平臺和Spark平臺上的運行時間對比，可以看出SP-RF算法在Spark平臺上的運行時間要遠低于Python平臺，主要是因為其利用被緩存進內存的中間計算結果，在各個分區上多線程的并行計算節省了大部分時間。由于本文實驗設備條件有限，只搭建了三個Slaver計算節點，可預見當增加計算節點的數量后，在進行更大數據量的實驗中算法的運行效率將會比傳統算法有指數級的提升[19-20]。

圖6 SP-RF算法在各平臺的運行時間

4 結 語

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