Spark下基于PCA和分層選擇的隨機森林算法

雷 晨，毛伊敏

江西理工大學 信息工程學院，江西 贛州 341000

隨機森林算法是機器學習領域中的一種集成學習方法[1]，它通過集成多個決策樹的分類效果來組成一個整體意義上的分類器。隨機森林算法相比其他分類算法而言具有諸多優勢，分類效果上的優勢體現在分類準確度高、泛化誤差小而且有能力處理高維數據，訓練過程的優勢體現在算法學習過程快速而且易于并行化。基于這兩大優勢，隨機森林算法受到人們廣泛關注。

隨著互聯網信息技術的不斷發展以及大數據時代的到來，使得大數據相較于傳統數據，具有了體積大（Volume）、種類多（Variety）、速度快（Velocity）、價值高（Value）的“4V”特性[2]。但是傳統的隨機森林算法所需的時間復雜度較高，只適用于較小規模的數據集，而在處理大數據時，無疑會產生巨額的計算復雜度[3]。所以，如何降低隨機森林算法的計算復雜度，使其能處理大數據，是個關鍵性的難題。

近年來，隨著Google公司開發的Spark架構的廣泛應用，以Spark為代表的分布式計算架構受到了越來越多的關注[4-5]。為了進一步降低隨機森林算法的計算復雜度，通過改進傳統的隨機森林算法，并與分布式計算架構相結合成為當前隨機森林算法的研究熱點。Wu等人[6]最早提出了大數據下基于Spark的可擴展隨機森林算法，為解決隨機森林算法處理大規模數據時，迭代頻繁和性能較低的問題，該算法利用Spark框架實現了計算任務的緩存式執行，消除了迭代依賴，但是該算法在特征變換過程中未考慮到冗余特征過多所引起的協方差矩陣規模過大的問題，對此，Ahmad等人[7]在Spark框架下提出了一種基于知識約簡的并行隨機森林算法，使用粗糙集理論對數據集進行先壓縮，后填補，降低非信息特征，提高了特征信息濃度；Bania等人[8]在基于優勢關系的粗糙集模型的基礎上，提出了基于相似優勢關系的隨機森林算法PRF，并將其基于Spark實現了并行化。雖然這些算法進行了一定的冗余特征剔除，壓縮了特征集的規模，但是并沒有完全解決協方差矩陣規模較大的問題。此外，這些算法在計算節點上構建特征子空間時，都是以均勻隨機的方式選取特征，未考慮到分布式環境下子空間特征信息覆蓋不足的問題。

如何解決子空間特征信息覆蓋不足的問題，一直是并行隨機森林算法的重要研究內容。為了處理這個問題，Galicia等人[9]提出了一種基于子空間加權選擇的并行隨機森林算法WECRF，在子空間選擇過程中，給予低信息素特征較低的選擇權重，降低其被選取的概率；Lulli等人[10]提出一種Spark環境下基于子空間分層選擇的并行隨機森林算法DRF，應用一個統計準則把特征分為三個部分，然后，使用分層抽樣的方式構造特征子空間。雖然這些算法都對均勻選取特征子空間的方式進行了改進，但是沒有完全解決子空間特征信息覆蓋不足的問題。除此之外，這些算法都未考慮并行化訓練決策樹的過程中，由于特征信息利用率過低，引起節點通信開銷過大的問題，于是，Morfino等人[11]在Spark環境下提出了一種數據并行化的隨機森林算法Spark-MLRF，設計了一種RDD數據劃分策略并結合分區采樣的方式來減少數據的傳輸操作，但是由于其使用的是水平劃分方式，雖然減少了局部通信頻率，但全局通信開銷并未降低，而且該算法隨著森林規模k的繼續增大，訓練決策樹時的數據通信過程的操作量會呈線性增加，并未從根本上解決決策樹訓練過程中通信開銷大的問題。

針對上述三個問題，本文提出了基于PCA和分層抽樣的并行隨機森林算法PLA-PRF（PCA and subspace layer sampling on Parallel random forest algorithm），主要貢獻如下：（1）提出了“MFS”策略獲取主成分特征，有效避免了特征變換過程中協方差矩陣規模較大的問題；（2）提出了“EHSCA”策略，將所獲得的主成分特征進行分層選擇，解決子空間特征信息覆蓋不足的問題；（3）在Spark環境下訓練決策樹的過程中，設計了數據復用策略“DRS”，提高分布式環境中的特征利用率，有效降低了分布式環境下決策樹訓練過程中的節點通信開銷，實驗結果表明，PLA-PRF算法的分類效果更佳。

1 相關技術介紹

1.1 分布式計算平臺—Spark

Spark是一種基于內存的分布式計算平臺[12]，旨在簡化集群上并行程序的編寫，Spark繼承了MapReduce的線性擴展性和容錯性，同時也改進了MapReduce必須先映射（Map），再規約（Reduce）的串行機制，Spark通過有向無環圖（directed acyclic graph，DAG）算子將中間結果直接移交給作業的下一階段，所有中間過程都是在內存中進行緩存，不必像MapReduce那樣每次迭代都要從磁盤重新加載數據。在Spark中，核心抽象概念就是彈性分布式數據對象RDD（resilient distributed datasets），Spark中計算任務的組織、運算、調度、錯誤恢復都是以RDD為單元進行的，Spark的任務工作流如圖1所示。

圖1 Spark的任務調度流程圖Fig.1 Spark task scheduling flowchart

在圖1中，各個RDD之間存在著依賴關系，通過這些依賴關系形成有向無環圖DAG；DAGshedule負責將DAG作業分解成多個Stage，每個Stage則根據RDD的Partition個數決定Task的個數，然后生成相應的TaskSet交給TaskShedule容器，TaskShedule容器負責將Task發送給clusterManager進行任務監測和加載，隨后將其交由worker線程池調度執行，若執行失敗，則重新加載，并將失敗日志返回給DAGshedule。

1.2 PCA

主成分分析（principal component analysis，PCA）[13]是一種將原有的多個變量通過線性變換轉換為少數綜合變量的統計分析方法，其基本數學原理如下：

設n維向量w是低維映射空間的一個映射向量，則經過最大化數據映射后其方差公式如下：

式（1）中m是參與降維的數據個數，xi是隨機數據i的具體向量表達，xˉ是所有參與降維的數據的平均向量。

假定W是由包含所有特征映射向量的列向量所組成的矩陣，該矩陣可以較好地保留數據中的信息，該矩陣經過代數的線性變換可以得到一個優化的目標函數如下：

式（2）中tr是矩陣的跡，A是協方差矩陣，表達式如下：

PCA的輸出：Y=W′X，最優的W是由協方差矩陣中前k個最大的特征值所對應的特征向量作為列向量構成，通過該過程將X的原始維度降低到了k維。

1.3 誤差約束分層

定義1（誤差約束分層）[14]假定數據源為d(d有 ||d個元組和n個屬性A={A1,A2,…,An})、分層屬性集合Φ∈A。在d的所有元組中，d(Φ)為屬性集合Φ上不同值x的集合，且對應于每個x都有d中的元組集合d(x)={t:t∈d且t在屬性集合Φ上取值為x}，記d中屬性集Φ上分組數量為 ||d(Φ)。給定相對誤差ε＞0，從d中選擇樣本S(d)?d，對每個具體的層次d(x)，存在對應的樣本集合Sx(d)?S(d)為d(x)的子集。

1.4 KD樹

KD樹[15]被定義為一棵節點均為k維向量的二叉樹，是一種用于分割k維數據空間的數據結構。KD樹的所有非葉子節點均可以視作一個超平面，該超平面可以將空間中的數據分成兩個部分，通過選定k維數據中的某一維度，并按照左小右大的方式來劃分數據，落在超平面左側的點被分到結點的左子樹上，右側的點則被分到節點的右子樹上。

2 PLA-PRF算法

2.1 算法思想

PLA-PRF算法主要包括三個階段：特征變換、子空間選擇和并行訓練決策樹。（1）在特征變換階段：提出“MFS”策略，使用特征矩陣分解方程“CMDE”（characteristic matrix decomposition equation）降低協方差矩陣的計算代價，獲得變換后的主分成特征，有效避免了協方差矩陣規模過大的問題；（2）在子空間選擇階段：提出“EHSCA”策略，使用誤差約束公式“ECF”（error constraint formula）對主成分特征進行分層選擇，提高子空間特征信息覆蓋度；（3）并行訓練決策樹階段：在Spark環境下設計了一種RDD數據復用策略“DRS”，垂直劃分RDD數據并將其索引保存在DSI（data search index）表中，實現特征信息的重復利用，降低節點通信開銷。

2.2 特征變換

目前，基于特征子空間改進的并行隨機森林算法通常采用主成分分析法進行特征變換，然而該方法在面對冗余特征過多的大數據集時，存在協方差矩陣規模較大的問題。針對這一問題，提出了“MFS”策略，壓縮原始特征集，解決協方差矩陣規模較大的問題。“MFS”策略如下：

（1）對于原始數據集D={(Xi,Yi),Xi∈?D,Yi∈y}Ni=1,使用Bootstrap抽樣算法[16]獲得訓練子集Dm(m=1,2,…,M)的特征集F,并將F劃分為L個特征子集F(l)(l=1,2,…,L)。

（2）使用公式（3）構造F(l)的協方差矩陣S，并計算S的特征矩陣A,提出特征矩陣分解方程“CMDE”（characteristic matrix decomposition equation）對A進行分解。

定義2（特征矩陣分解方程CMDE）。若矩陣A是一個N×F(l)的實數矩陣，其中N表示樣本個數，F(l)表示特征數，UN×N和VF(l)×F(l)均為單位正交陣，Σ僅在主對角線上有值(σ)，且維度分別為U∈RN×N,Σ∈RN×F(l),V∈RF(l)×F(l),則特征矩陣A分解方程如下所示：

證明設，存在m×n的矩陣A且存在一組正交基，使得經過矩陣A分解變換后還是正交的，這組正交基為{v1,v2,…,vn}。

其中，V表示ATA所分解出的特征向量矩陣，ΣTΣ是ATA的特征值矩陣，當特征值λi越小，其所對應的特征向量ui對分類的重要性越低，λi被剔除的可能性越高，反之，被剔除的可能越低。

（4）最后，按照特征值{}λ將特征向量{}u由大到小排序，在滿足算法預期性能的情況下，對特征值較低的特征向量進行剔除，得到特征子集F′(l)，統計所有特征子集，得到變換后的主成分特征

2.3 子空間選擇

目前，基于特征子空間改進的并行隨機森林算法，通常采用隨機均勻的方式構建特征子空間，然而該方式未考慮特征間的信息差異，這導致子空間特征信息覆蓋不足，針對此問題，基于主成分特征D(l)m′，設計了“EHSCA”策略，分層選取特征子空間，提高子空間特征信息覆蓋度。“EHSCA”策略如下：

（1）根據特征分割參數R，將主成分特征集D(l)m′的前r個特征分配給高信息素空間A1，將后F(l)-r個特征分配給低信息素空間A2，特征分割參數定義如下：

（3）分別從A1和A2中抽取特征，提出誤差約束公式“ECF”（error constraint formula）確定在A1和A2中抽取的特征數量，誤差約束公式定義如下：

定義4（誤差約束公式ECF）。若NA1和NA2分別表示是來自兩個層次A1和A2的特征樣本數量，δ表示給定置信度，ε代表查詢Q(d(x))的誤差，則誤差約束公式“ECF”如下所示：

（4）根據NA1和NA2分別在層次A1和A2中進行隨機抽樣，得到包含所有信息的特征子空間。

使用“EHSCA”策略構建特征子空間的偽代碼如算法1所示：

2.4 并行訓練決策樹

目前，在Spark環境下，基于特征子空間改進的并行隨機森林算法雖然保證了分類準率，但是這些算法在并行化訓練決策樹的過程中未考慮到分布式環境中的數據量會隨森林規模增大而線性增加[18]，使得特征信息利用率較低，進而導致節點通信開銷大的問題，針對此問題，本文在并行化訓練決策樹的過程中設計RDD數據復用策略“DRS”，通過垂直劃分RDD數據并結合索引表，實現數據復用，降低了節點通信開銷，“DRS”策略如下：

（1）根據RDD特征空間構建KD樹，根節點指向整個特征空間并存放所有的數據記錄N,每個葉子節點記錄劃分后的輸入特征變量以及輸入特征變量所包含的特征屬性yi，選取數據空間離散系數（coefficient of variation，CV）[19]最大的維度作為KD樹的劃分維度d，該維度下的數據均值作為KD樹的分割節點w，根據d和w提出劃分準則函數（partition criterion function，PCF），其定義如下：

定義5（劃分準則函數PCF）。若RDD數據中第i維度下的均方差為Si，均值為μ，KD樹中劃分維度d下的記錄個數為num，則PCF函數計算如下：

（2）使用“PCF”函數獲取KD樹的分割維度和劃分節點后，對當前空間數據進行判斷，若數據在當前分割維度d中小于分割節點w，則將此數據yi與目標特征yM-1鏈接作為一個垂直數據塊RDDFSJ，否則繼續遍歷KD樹。重復此過程，直到劃分出(M-1)個數據分區R DDFSjj∈[0,M-2]，M為Slave節點數量，劃分過程如圖2所示。

圖2 垂直數據劃分Fig.2 Vertical data partition

（3）完成RDD數據對象垂直劃分后，將這些RDDFS特征子集發送給分布式Spark集群中的各slave，并通過dataAllocation( )和persisit( )函數存儲在Spark集群中。接著，在每個slave中創建一個DSI表存儲采樣過程中生成的數據索引，例如：若森林規模為k，則對于訓練數據集，存在k個采樣周期，并且在每個采樣周期中都會記錄下N個數據索引，形成k行N列的DIS索引表，如表1所示。

表1 DSI索引表Table 1 DSI index table

（4）每棵決策樹訓練過程中所需的計算任務都通過DSI表從同一特征子集RDDFS中加載相應的數據，例如：在增益比計算過程中，每個增益比計算任務都會訪問DIS表以獲得相關索引，并根據索引從同一特征子集中獲得特征記錄，從而快速的訪問特征子集，進行決策樹分裂，完成決策樹并行訓練，具體過程如圖3所示。

圖3中每個TGR代表增益比計算任務，首先，根據特征子集RDDFS1、RD DFS2、RDDFS3分別向Slave站點中分配增益計算任務{TGR1.1,TGR1.2,TGR1.3}、{TGR2.1,TGR2.2,TGR2.3}、{TGR3.1,TGR3.2,TGR3.3}每個站點中的增益計算任務分別屬于Decisi onTree1、DecisionTree2、DecisionTree3；其次，根據TGR需求，通過DSI索引從RDDFS特征子集中獲取特征記錄，為決策樹計算特征變量的增益比；最后，使用{TGR1.1,TGR2.1,TGR3.1}進行DecisionTree1的節點拆分，使用{TGR1.2,TGR2.2,TGR3.2}和{TGR3.1,TGR3.2,TGR3.3}分別進行DecisionTree2和DecisionTree3的拆分。

圖3 決策樹并行訓練過程Fig.3 Decision tree parallel training process

決策樹并行訓練過程的偽代碼如算法2所示：

2.5 PLA-PRF算法步驟

PLA-PRF算法的具體實現步驟如下所示：

步驟1輸入原始數據，將其劃分成大小相同的RDD數據塊；對于每個RDD數據塊的特征集，調用“MFS”策略進行特征變換，剔除冗余特征，獲得主成分特征，將其存入每個任務節點。

步驟2根據“EHSCA”算法在主成分特征中進行子空間分層選擇，生成特征子空間。

步驟3依據特征子空間，使用“DRS”策略并行訓練決策樹，生成相應的DAG任務，最后，將DAG中的任務提交給Spark的任務調度程序以完成所有模型訓練。

2.6 時間復雜度分析

PLA-PRF算法的時間復雜度主要由特征變換、子空間選擇、決策樹并行化訓練這幾個步驟組成，分別記為T1、T2、T3。

特征變換階段時間花銷主要體現在協方差矩陣的計算中，假設預訓練樣本數為n，特征數量為m，則特征變換的時間復雜度為：

在子空間選擇階段，假設節點數為a，“EHSCA”算法的每一次誤差約束計算都要查詢一次當前數據庫中的某個特征屬性值，假設在完成n次迭代后，達到指定置信度δ，則子空間選擇的時間復雜度為：

在決策樹并行化訓練階段，其時間復雜度主要取決于TGR（增益比計算）任務和TNS（節點拆分）任務的計算時間，分別表示為TG和TN，假設決策樹數量為k，則增益比計算任務的時間復雜度為：

由于大數據環境下訓練RF時T3?T1和T2，而且通過數據復用技術直接提升了分布式環境中的數據利用率，即T3-Spark-MLRF?T3-PLA-PRF，因此PLA-PRF算法時間復雜度遠低于算法Spark-MLRF。

3 實驗結果以及分析

3.1 實驗環境

為了驗證PLA-PRF算法的分類性能，本文設計了相關實驗。硬件方面：所有的實驗都在Atlas（Atlas-2.2.1.el6.x86_64.rpm）研究組集群中進行，該集群由12節點組成，每個節點有2個Inter E5-2620微處理器（2 GHz，15 MB緩存）和64 MB主存，1 Gb/s的以太網鏈接。在軟件方面，每個節點安裝的操作系統為Ubuntu 18.04，Spark架構為Spark-Scala-Intellij，軟件編程環境為Java JDK 1.8.0。節點具體配置情況如表2所示。

表2 節點基本配置表Table 2 Basic node configuration

3.2 數據來源

PLA-PRF算法采用的實驗數據為四個來自UCI公共數據庫的真實數據集（http：//www.ics.uci.edu/～mlearn/MLRepository.html），分別是URL Reputation（URL）、You Tube Video Games（Games）、Bag of Words（Words）和Gas sensor arrays（Gas）。URL是模式識別文獻中最著名的數據集，包含924 472條數據，具有數據量小等特點；Games是從IT公司使用的ServiceNowTM平臺實例的審計系統收集的數據，該數據集有3 013 883條實例，具有多元、記錄長度長等特點；Words是一組有關粒子加速器探測粒子的數據，該數據集有5 000 000條記錄，具有數據量大，數據均勻等特點；Gas包含11 000 000條數據，具有數據量大，數據離散等特點。數據集的詳細信息如表3所示。

表3 UCI機器學習庫中數據集Table 3 Datasets from UCI machine learning repository

3.3 評價指標

本文采用Kappa系數作為指標來衡量算法對大數據集的分類準確率[20]。假設每一類真實樣本的個數分別為a1,a2,…,ac，而預測出來的每一類樣本個數分別為b1,b2,…,bc，總樣本個數為n，則Kappa系數計算方式如下：

其中，p0表示總體分類精度。通常情況下，k值落在0～1之間，可分為5組來表示不同的一致性級別，一致性越高，表示分類準確率越高，如表4所示。

表4 一致性級別表Table 4 Consistency level table

3.4 算法的分類準確率分析

3.4.1 不同森林規模下的算法準確率分析

為驗證PLA-PRF算法的分類準確率，本文使用URL數據集進行對比實驗，根據算法在不同決策樹規模下的平均分類精度與PRF[8]、DRF[10]、Spark-MLRF[11]算法進行綜合比較。實驗結果如圖4所示。

圖4 各算法在不同森林規模下的平均分類準確率Fig.4 Average classification accuracy of each algorithm under different forest scales

從圖4可以看出，當決策樹的數量等于10時，所有比較算法的平均分類精度都較低，隨著決策樹數量的增加，這些算法的平均分類精度逐漸呈波動型增加，當決策樹數量增加到1 300時，與PRF和DRF算法相比，PLA-PRF算法的平均分類精度高出大約6.1%和10.6%，當決策樹數量達到1 500時，PLA-PRF算法比Spark-MLRF的分類準確率高約4.6%，可以看出，隨著決策樹規模的增加，PLA-PRF算法的精度增益明顯高于其他三個算法，這是因為PLA-PRF算法使用“EHSCA”策略提升了子空間特征信息覆蓋度，從而提高了分類準確率，因此可以得出結論，在森林規模較大的情況下，PLA-PRF算法精度最高。

3.4.2 不同數據集下的算法準確率分析

為驗證PLA-PRF算法在不同數據集下的分類準確率，本文分別在四個數據集上進行實驗，根據Kappa值，分別與PRF、DRF算法和Spark-MLRF算法進行綜合比較，實驗結果如圖5所示。

從圖5中可以看到，相比于DRF算法，PLA-PRF、Spark-MLRF和PRF算法在四個數據集上表現較好，Kappa值分別平均提升約3.13%、2.56%和1.98%，而DRF算法在樣本規模較少的情況下，分類準確率較高，而隨著樣本規模的增加，分類精度逐漸降低，是因為該算法在子空間構建過程中，舍棄了一些高信息素特征，使得特征新空間信息不足，導致決策樹訓練過程中未學習到被拋棄的數據內在規律。從URL、Games和Words中可以看出，在特征數量較少且復雜度較低數據集上，Spark-MLRF算法表現略優于PLA-PRF和PRF算法，而在特征數量較多的數據集Gas上，PLA-PRF算法的平均準確率比Spark-MLRF和PRF分別高3.1%和5.9%，而在樣本規模達到65 000時，PLA-PRF分類準確率要高出8.9%和15.6%。這是因為，PRF算法在子空間構造過程中使用了維度縮減算法，雖然保留了主要成分特征的，但是在后續的子空間選擇時并沒有進行分層抽取，導致特征子空間信息不均，在面對特征較多的大數據集時，隨著數據劃分次數的增加，訓練子集的信息缺失越發嚴重，進而降低了分類準確率；Spark-MLRF算法雖然通過分層抽取的方式一定程度上解決了PRF的子空間信息缺失問題，但由于其對每個分區都進行單獨采樣，隨著數據集規模的增大，數據集的隨機選擇比例增加，分類準確率有所下降；而PLA-PRF算法使用了“EHSCA”策略進行子空間選擇，充分保證了特征子空間的信息覆蓋度，最終提高了模型的分類準確率。綜上所述，可得，PLA-PRF算法適用于處理規模較大，特征復雜數據集。

圖5 各算法在四個數據集上的平均分類精度Fig.5 Average classification accuracy of each algorithm on four data sets

3.5 算法性能比較

為驗證PLA-PRF算法的性能，本文與Spark-MLRF和DRF算法進行對照實驗，實驗中使用了4組數據集（URL、Games、Words、Gas），每種算法在實驗過程中，決策樹規模均設定為500，Spark站點數量設置為10，實驗結果如圖6所示。

圖6為PLA-PRF、Spark-MLRF和DRF算法在四個數據集上的執行結果。從圖中可以看出，當數據規模小于1 GB時，PLA-PRF和Spark-MLRF算法執行時間比DRF長，平均約為DRF的138%，原因是將算法提交到Spark集群并配置程序需要固定的時間，在數據量較小時，該時間在算法運行時間中所占比重較大，但是當數據量從1 GB增長到500 GB時，DRF的平均執行時間從19.9 s增長到517.8 s，而Spark-MLRF的平均執行時間從24.8 s增加到186.2 s，PLA-PRF的平均執行時間從23.5 s增加到101.3 s。由此，可以看出，在大數據集下PLA-PRF與Spark-MLRF和DRF相比具有更快的執行速度，而且隨著數據量的增大，優勢更加明顯，這是因為PLA-PRF在并行化的過程中使用了數據復用策略“DRS”，減少了分布式環境中的數據通信開銷，提升了算法的并行化效率。

圖6 各算法在四個數據集上的平均運行時間Fig.6 Average running time of each algorithm on four data sets

4 結語

為解決傳統隨機森林算法在大數據環境下，分類結果準確率低，并行化效率差的問題，本文提出了一種基于PCA和分層子空間抽樣的并行隨機森林算法。面對并行隨機森林算法在特征變換過程中協方差矩陣過大的問題，提出一種基于PCA的特征變換方法，接著，對于所得主成分特征，提出了一種誤差約束的分層子空間構造算法，優化特征子空間，解決子空間特征信息覆蓋不足的問題。最后，在Spark環境下并行化訓練決策樹的過程中，設計了一種數據復用技術，有效減少了分布式環境中的節點通信開銷，提高了并行效率。實驗結果表明，在數據規模較大且特征維度較高的情況下，本文算法可以更高效地完成分類過程。雖然PLA-PRF算法在分類準確率和并行效率方面取得一些進步，但依然存在一定的提升空間，一方面，在特征變換過程中能否適當引入群智能算法來優化原始特征集，提高特征集的尋優精度；另一方面，在處理集群計算任務時，Spark平臺的TaskScheduler模塊會根據不同的任務資源需求使用不同的調度方式，因此，在調度DAG的過程中，可以考慮對信息增益任務和節點拆分任務分別給出不同的調度策略，從而進一步提高算法的資源利用率，提升并行效率，這些將是本文今后的重點研究內容。