雷 晨，毛伊敏

江西理工大學(xué) 信息工程學(xué)院，江西 贛州 341000

隨機森林算法是機器學(xué)習(xí)領(lǐng)域中的一種集成學(xué)習(xí)方法[1]，它通過集成多個決策樹的分類效果來組成一個整體意義上的分類器。隨機森林算法相比其他分類算法而言具有諸多優(yōu)勢，分類效果上的優(yōu)勢體現(xiàn)在分類準確度高、泛化誤差小而且有能力處理高維數(shù)據(jù)，訓(xùn)練過程的優(yōu)勢體現(xiàn)在算法學(xué)習(xí)過程快速而且易于并行化?；谶@兩大優(yōu)勢，隨機森林算法受到人們廣泛關(guān)注。

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

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

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

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

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

1.1 分布式計算平臺—Spark

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

圖1 Spark的任務(wù)調(diào)度流程圖Fig.1 Spark task scheduling flowchart

在圖1中，各個RDD之間存在著依賴關(guān)系，通過這些依賴關(guān)系形成有向無環(huán)圖DAG；DAGshedule負責(zé)將DAG作業(yè)分解成多個Stage，每個Stage則根據(jù)RDD的Partition個數(shù)決定Task的個數(shù)，然后生成相應(yīng)的TaskSet交給TaskShedule容器，TaskShedule容器負責(zé)將Task發(fā)送給clusterManager進行任務(wù)監(jiān)測和加載，隨后將其交由worker線程池調(diào)度執(zhí)行，若執(zhí)行失敗，則重新加載，并將失敗日志返回給DAGshedule。

1.2 PCA

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

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

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

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

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

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

1.3 誤差約束分層

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

1.4 KD樹

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

2 PLA-PRF算法

2.1 算法思想

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

2.2 特征變換

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

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

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

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

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

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

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

2.3 子空間選擇

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

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

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

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

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

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

2.4 并行訓(xùn)練決策樹

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

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

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

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

圖2 垂直數(shù)據(jù)劃分Fig.2 Vertical data partition

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

表1 DSI索引表Table 1 DSI index table

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

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

圖3 決策樹并行訓(xùn)練過程Fig.3 Decision tree parallel training process

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

2.5 PLA-PRF算法步驟

PLA-PRF算法的具體實現(xiàn)步驟如下所示：

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

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

步驟3依據(jù)特征子空間，使用“DRS”策略并行訓(xùn)練決策樹，生成相應(yīng)的DAG任務(wù)，最后，將DAG中的任務(wù)提交給Spark的任務(wù)調(diào)度程序以完成所有模型訓(xùn)練。

2.6 時間復(fù)雜度分析

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

特征變換階段時間花銷主要體現(xiàn)在協(xié)方差矩陣的計算中，假設(shè)預(yù)訓(xùn)練樣本數(shù)為n，特征數(shù)量為m，則特征變換的時間復(fù)雜度為：

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

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

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

3 實驗結(jié)果以及分析

3.1 實驗環(huán)境

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

表2 節(jié)點基本配置表Table 2 Basic node configuration

3.2 數(shù)據(jù)來源

PLA-PRF算法采用的實驗數(shù)據(jù)為四個來自UCI公共數(shù)據(jù)庫的真實數(shù)據(jù)集（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是模式識別文獻中最著名的數(shù)據(jù)集，包含924 472條數(shù)據(jù)，具有數(shù)據(jù)量小等特點；Games是從IT公司使用的ServiceNowTM平臺實例的審計系統(tǒng)收集的數(shù)據(jù)，該數(shù)據(jù)集有3 013 883條實例，具有多元、記錄長度長等特點；Words是一組有關(guān)粒子加速器探測粒子的數(shù)據(jù)，該數(shù)據(jù)集有5 000 000條記錄，具有數(shù)據(jù)量大，數(shù)據(jù)均勻等特點；Gas包含11 000 000條數(shù)據(jù)，具有數(shù)據(jù)量大，數(shù)據(jù)離散等特點。數(shù)據(jù)集的詳細信息如表3所示。

表3 UCI機器學(xué)習(xí)庫中數(shù)據(jù)集Table 3 Datasets from UCI machine learning repository

3.3 評價指標

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

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

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

3.4 算法的分類準確率分析

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

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

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

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

3.4.2 不同數(shù)據(jù)集下的算法準確率分析

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

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

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

3.5 算法性能比較

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

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

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

4 結(jié)語

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