荊靜　祝永志

摘 要：如何在各式大數(shù)據(jù)中更快更準(zhǔn)確地挖掘有用信息是研究熱點。隨機森林算法作為一種重要的機器學(xué)習(xí)算法，適用于大部分?jǐn)?shù)據(jù)集。隨機森林算法可以并行運行，這是隨機森林算法處理大數(shù)據(jù)集時的優(yōu)勢。將隨機森林算法應(yīng)用在大數(shù)據(jù)處理框架Spark上，提高了隨機森林算法處理大數(shù)據(jù)集時的速度。首先對隨機森林進行參數(shù)調(diào)優(yōu)，找到當(dāng)前數(shù)據(jù)集的最優(yōu)參數(shù)組合，采用隨機森林模型對特征進行重要度計算，篩選掉噪聲數(shù)據(jù);然后采用卡方檢驗對數(shù)據(jù)集的特征進行分層，實現(xiàn)分層子空間隨機森林并驗證準(zhǔn)確率和袋外精度;最后在傳統(tǒng)分層子空間隨機森林基礎(chǔ)上對分層子空間進行加權(quán)改進。實驗證明改進后的隨機森林算法準(zhǔn)確率提高了3%，袋外估計精度提高了1%。

關(guān)鍵詞：隨機森林;Spark;大數(shù)據(jù)處理;特征選擇

DOI：10. 11907/rjdk. 191691

中圖分類號：TP312 ? 文獻標(biāo)識碼：A ??????????????? 文章編號：1672-7800（2020）003-0120-05

Research of Random Forest Algorithm Using Weighted Stratified Subspace

Based on Spark Platform

JING Jing，ZHU Yong-zhi

（School of Information Science and Engineering，Qufu Normal University，Rizhao 276826，China）

Abstract：How to find useful information out of all kinds of big data faster and more accurately becomes an import problem in the time. As an important machine learning algorithm， random forest algorithm is flexible and suitable for most data sets. The random forest algorithm can run in parallel，this is an advantage when dealing with large data sets. The application of random forest algorithm to big data processing framework Spark can greatly improve the speed of running and processing big data of random forest algorithm. Firstly，the parameter of the random forest were optimized to find the optimal combination of parameters of the current data set. The importance of features are calculated to delete the useless feature by random forest model. Then， chi-square test is used to stratify the features of the data set to achieve the verification accuracy and out-of-bag accuracy of random forest using stratified subspace. Finally， on the basis of the traditional random forest using stratified subspace， the stratified subspace is improved by weighting. The experimental results show that the improved random forest algorithm improves the prediction accuracy by 3% and the out-of-bag estimation accuracy by 1%.

Key Words：random forest; Spark; big data processing; feature selection

0 引言

大數(shù)據(jù)具有數(shù)據(jù)量大、類型多樣和價值密度低等特點，如何在大數(shù)據(jù)中快速且準(zhǔn)確地挖掘信息成為亟待解決的問題。決策樹算法作為一種經(jīng)典的數(shù)據(jù)挖掘算法，既可作為分類算法，又可作為回歸算法，但是單一的決策樹在處理數(shù)據(jù)時容易產(chǎn)生過擬合問題，因此在2001年出現(xiàn)了隨機森林算法。對運行在單機上的隨機森林算法研究已經(jīng)相對成熟，近年來的研究是將隨機森林并行運行以提高其性能。Apache Spark是大數(shù)據(jù)機器學(xué)習(xí)中最受歡迎的平臺之一，它受益于分布式架構(gòu)和自動數(shù)據(jù)并行化。Apache Spark MLlib為各種機器學(xué)習(xí)任務(wù)提供支持，包括回歸、降維、分類、聚類和規(guī)則提取[1]。

文獻[2]將隨機森林算法應(yīng)用在Spark平臺，并在投票時根據(jù)不同決策樹預(yù)測準(zhǔn)確度對其進行加權(quán)，有效提高了算法準(zhǔn)確度。但是對于具有高維特征的大數(shù)據(jù)，隨機森林在處理數(shù)據(jù)時運行時間過長，而且噪聲數(shù)據(jù)也會對結(jié)果準(zhǔn)確率產(chǎn)生影響;文獻[3]在Spark平臺上運用隨機森林算法進行特征選擇，對冗余數(shù)據(jù)和噪聲數(shù)據(jù)進行篩選，并采用方差分析和后向序列選擇進行降維，提高了隨機森林算法的準(zhǔn)確度。但方差分析和后向序列選擇方法在進行特征篩選時，要自身把握度量標(biāo)準(zhǔn)，因而容易將有用特征刪除;文獻[4]針對不平衡大數(shù)據(jù)提出一種啟發(fā)式自舉抽樣方法，結(jié)合保險大數(shù)據(jù)在Spark平臺上實驗，證明具有良好性能。但其只針對保險大數(shù)據(jù)集進行改進，只對某一類大數(shù)據(jù)集有效;文獻[5]提出了一種基于Flayed邊界點的隨機森林算法，這種算法在處理具有離散連續(xù)屬性的樣本時可降低時間復(fù)雜度;文獻[6]提出了基于粗糙集的隨機森林算法，將粗糙集理論應(yīng)用于特征選擇中，但是仍然無法完全消除噪聲數(shù)據(jù)的影響;文獻[7]提出用分層子空間方式處理高維大數(shù)據(jù)，將特征分為強特征層和弱特征層，然后在不同的特征層進行取樣，預(yù)測結(jié)果準(zhǔn)確率有一定提高。但是其對不同層采用了等比例方式進行采樣，也容易產(chǎn)生噪聲數(shù)據(jù)。本文首先在Spark平臺上對隨機森林算法進行參數(shù)調(diào)優(yōu)，采用特征評估方法對特征進行重要度計算，并刪除噪聲特征，然后對傳統(tǒng)分層子空間進行實驗，驗證其準(zhǔn)確率。針對傳統(tǒng)分層子空間等比例抽樣所得結(jié)果受噪聲數(shù)據(jù)影響較大從而影響準(zhǔn)確度的不足，對分層子空間進行加權(quán)，并對加權(quán)分層子空間隨機森林的準(zhǔn)確率與原始分層子空間隨機森林算法準(zhǔn)確率進行比較，發(fā)現(xiàn)加權(quán)抽樣時所得結(jié)果最優(yōu)。實驗證明經(jīng)過加權(quán)的隨機森林算法準(zhǔn)確率提升了3%，袋外估計準(zhǔn)確率也有提升。

1 隨機森林算法

隨機森林（Random Forest，RF）是一種組合分類器，它首先訓(xùn)練多棵決策樹，訓(xùn)練完成后將其組合成隨機森林模型，然后運用隨機森林模型進行預(yù)測。隨機森林應(yīng)用廣泛，如用于預(yù)測疾病風(fēng)險[8]、遙感社區(qū)[9]和保險[10]等等。

1.1 決策樹

決策樹（decision tree）指以樹的形式進行分類預(yù)測的模型。決策樹在節(jié)點劃分時就是要尋找一種最純凈的劃分方法，在數(shù)學(xué)中稱之為純度，分裂屬性使得孩子節(jié)點的數(shù)據(jù)劃分得最純。

1.1.1 熵

熵（entroy）表示數(shù)據(jù)的混亂程度，熵與混亂程度呈正比，熵變大時混亂程度也變高。

定義1：對類別為隨機變量X的樣本集合D，假設(shè)X有k個類別，每個類別的概率為[CkD]，其中[Ck]表示類別k的樣本個數(shù)，[D]表示樣本總數(shù)，則樣本集合D的熵公式如下：

1.1.2 基尼值

定義2：設(shè)[pi]為類別i在樣本D中出現(xiàn)的概率，基尼指數(shù)公式如下：

基尼指數(shù)被定義用來衡量節(jié)點純度，基尼指數(shù)與純度成反比關(guān)系，即基尼指數(shù)變大時節(jié)點純度會變低。

決策樹理解起來比較簡單，但是它可能會出現(xiàn)過度分割樣本空間問題，導(dǎo)致決策樹算法復(fù)雜度很高，并且會出現(xiàn)過擬合。為了解決這些問題，針對決策樹缺點提出隨機森林算法。隨機森林算法是對決策樹算法的一種集成，可以有效避免過擬合。

1.2 隨機森林

定義3：假設(shè)數(shù)據(jù)集為D={Xi，Yj}，Xi∈R，Yi∈{1，2，…，C}，隨機森林是在數(shù)據(jù)集上以M個決策樹{g（D，θm}，m=1，2，…，M}為基分類器進行集成學(xué)習(xí)后得到的一個組合分類器。

隨機森林算法創(chuàng)建過程分為3個步驟：①劃分訓(xùn)練樣本子集;②訓(xùn)練隨機森林;③預(yù)測。隨機森林算法的隨機性體現(xiàn)在它不僅在取樣時采用隨機取樣，在特征選擇時也是隨機抽取，然后從中采用最佳屬性進行分裂。

1.2.1 卡方檢驗

卡方檢驗是衡量兩個變量相關(guān)性的一種檢驗方法[11]。

定義4：對于數(shù)據(jù)集D，使用[X={x1，？，xk}]表示樣本，使用[Y={y1，？，yq}]表示類別，使用[A={A1，？，AM}]表示特征，而對于每一個特征，假設(shè)特征[Ai]有p個不同取值，當(dāng)[Ai=al]時， [Y=yj（j=1，？，q）]的D子集大小為[vallj]，特征[Ai]與類別之間的信息量公式如下：

其中，[vallj]為觀察頻數(shù)，即表示為實際發(fā)生的頻數(shù)，[tlj]為期望頻數(shù)。期望函數(shù)取值為：

特征和類別之間的相關(guān)性越強，特征分類新事物的能力也越強，因此將卡方檢驗應(yīng)用在隨機森林算法的特征選擇中，檢測特征與類別之間的關(guān)系。根據(jù)相關(guān)性將特征劃分為強特征和弱特征層，在進行特征選擇時在不同層進行抽樣，增強單棵樹的分類強度，不增加樹之間的相關(guān)性。

傳統(tǒng)的分層子空間隨機森林算法在不同層進行等比例取樣，能保證結(jié)果最優(yōu)。

1.2.2 隨機森林特征評估

大數(shù)據(jù)價值很高，但也有許多問題，其中最重要的是降維，特別是特征選擇[12]。對高維樣本進行降維方法有多種，如T-test檢測、序列后向選擇[13]等，本文采用隨機森林模型進行特征篩選，特征評估衡量標(biāo)準(zhǔn)為Gini指數(shù)變化量。

定義5：特征Xi在節(jié)點m上的重要性即節(jié)點m分枝前后的Gini指數(shù)變化量，其公式如下：

其中GIl和GIr分別表示以特征m進行分裂后左右兩個孩子節(jié)點的Gini指數(shù)。

在使用卡方檢驗將特征子空間分層后，對每個特征進行特征評估得到一個評估值，對層內(nèi)每個特征的重要度進行累加得到層的權(quán)重。

定義6：設(shè)每層有r個特征[Ai]（i=1，…r），定義層權(quán)重公式為：

1.2.3 袋外估計

袋外數(shù)據(jù)（OOB，out-of-bag）即未被抽取到的訓(xùn)練數(shù)據(jù)[14]。對隨機森林每棵樹而言，建樹時采用隨機并且有放回地進行抽取，所以每棵樹大約有1/3的數(shù)據(jù)未被抽到，這些數(shù)據(jù)稱為袋外數(shù)據(jù)。因為未參與建模過程，因此用這些數(shù)據(jù)對隨機森林模型進行評估結(jié)果較為可信。

使用袋外數(shù)據(jù)進行評估得到的正確率稱為袋外正確率。袋外估計可以作為泛化誤差估計的一部分，使得隨機森林算法不再需要交叉驗證。

1.3 隨機森林算法特點

現(xiàn)實生活中的大多數(shù)數(shù)據(jù)分析都是分類和回歸問題，而隨機森林算法既可作為分類算法，又可作為回歸算法。近年來隨機森林算法廣受歡迎，應(yīng)用在各種領(lǐng)域，如銀行、股票市場和醫(yī)藥行業(yè)等等。隨機森林在處理各種問題時發(fā)揮著強大的優(yōu)勢，它的優(yōu)點主要有：①具有良好的準(zhǔn)確率;②訓(xùn)練速度快，能夠運行在大數(shù)據(jù)集上;③能夠處理高維特征樣本;④可以評估特征在模型中的重要程度;⑤可以在模型生成過程中取得真實誤差的無偏統(tǒng)計;⑥容易并行化。

2 Spark

2.1 Spark介紹

因為數(shù)據(jù)量超過了單機所能處理的極限，所以用戶需要新的架構(gòu)將計算擴展到多個節(jié)點進行，以應(yīng)對不同工作負(fù)載的新集群編程模型數(shù)量的飛速增長[15]。Spark自2010年發(fā)布以來已成為最活躍的大數(shù)據(jù)處理計算引擎，廣泛應(yīng)用在金融、生物技術(shù)和天文學(xué)等多個領(lǐng)域[16]。

Spark基于彈性分布式數(shù)據(jù)集（RDD）[17]。RDD是一種可并行計算的集合，它不可變并且可被分區(qū)，可以由存儲的數(shù)據(jù)或其它RDD生成，是最基本的數(shù)據(jù)抽象。RDD？有轉(zhuǎn)化和行動兩種類型操作，轉(zhuǎn)化操作主要由一個已知RDD轉(zhuǎn)化為一個新的RDD。行動操作在應(yīng)用一組操作后將記錄/值返回給主程序。這兩個操作之間的主要區(qū)別在于它們何時以及如何應(yīng)用于數(shù)據(jù)。

Spark提供一系列組件支持?jǐn)?shù)據(jù)處理。Spark shell提供多個API使得交互式數(shù)據(jù)分析更方便快捷。Spark SQL提供交互式查詢。Spark streaming用于處理實時數(shù)據(jù)組件，提供流式數(shù)據(jù)計算;Mllib庫支持?jǐn)?shù)據(jù)分析等，包含大量機器學(xué)習(xí)算法[18];GraphX對圖計算提供支持。這些組件提供給用戶的都是jar包，使用時無需部署、維護等復(fù)雜操作，在Spark平臺上可直接使用，充分體現(xiàn)了Spark的通用性。Spark可以獨立安裝使用，也可與其它平臺配合使用。Spark架構(gòu)如圖1所示。

2.2 基于Spark的隨機森林算法

由于隨機森林算法基于多個獨立樹定義，因此可以直接并行隨機森林方法并更快地將其實現(xiàn)，其中許多樹在不同的核上并行構(gòu)建[19]。隨機森林模型如圖2所示。

基于Spark的隨機森林建模過程：①從hdfs讀取訓(xùn)練數(shù)據(jù)集并將其設(shè)置為廣播變量，壓縮為一個forest列表;②將不同的訓(xùn)練樣本子集分發(fā)給不同的從機進行決策樹訓(xùn)練。主機從各個從機收集訓(xùn)練完成的子森林組合成隨機森林，將測試集分成一定大小的塊并分發(fā)給從機進行預(yù)測，主機收集并返回預(yù)測結(jié)果。

基于Spark平臺的隨機森林主要對訓(xùn)練過程和預(yù)測過程進行并行化[20]，這樣不僅增大了可處理的數(shù)據(jù)量，也加快了運行速度。

3 實驗

3.1 實驗數(shù)據(jù)與環(huán)境

本文采用Semeion手寫字?jǐn)?shù)據(jù)集，該數(shù)據(jù)每個記錄代表一個手寫字，有256個特征。實驗環(huán)境為Windows上的ubuntu虛擬hadoop集群，集群包含3個節(jié)點，采用HDFS存儲文件，集群管理器為YARN，編程語言為Python。

3.2 實驗結(jié)果與分析

將數(shù)據(jù)集以7∶3拆分為訓(xùn)練集和測試集。對隨機森林進行參數(shù)調(diào)優(yōu)，包括控制樹的數(shù)量和選擇合適的特征比例兩個方面，實驗準(zhǔn)確率如圖3所示。

分別選取隨機森林規(guī)模為10，50和100，特征選取比例分別為0.1，0.5和0.8進行實驗。從實驗結(jié)果可以看出，當(dāng)特征比選為0.5時，隨機森林預(yù)測準(zhǔn)確度達到最高，當(dāng)特征比例選擇更大時，準(zhǔn)確率不升反降，此時準(zhǔn)確率可能受到噪聲數(shù)據(jù)的影響。對隨機森林規(guī)模選取進行測試，發(fā)現(xiàn)隨著隨機森林規(guī)模的變大準(zhǔn)確率也會上升，但對于當(dāng)前數(shù)據(jù)而言，隨機森林規(guī)模在50和100的準(zhǔn)確率并未增長，反而增加了程序運行時間，所以對特定數(shù)據(jù)集選取合適的森林規(guī)模對算法性能有很重要的影響。

對數(shù)據(jù)集進行特征評估操作，將評估結(jié)果歸一化，對每個特征評估出一個重要度，所有特征重要度相加為1，計算出一些特征為0的噪聲特征，將這些特征刪除。有效降維使算法的準(zhǔn)確度和運行時間都有提升，有利于提升算法性能。

降維后開始進行分層子空間隨機森林實驗。該實驗分3組進行，分別為：①強弱特征層等比例抽樣;②僅在強特征層抽樣;③僅在弱特征層抽樣。驗證3組實驗結(jié)果準(zhǔn)確率，如圖4所示。

從實驗結(jié)果可以看出，強特征層和弱特征層的結(jié)果相差較大，在強特征層進行抽樣時的實驗結(jié)果優(yōu)于等比例抽樣，所以在強弱特征層進行等比例抽樣算法有待優(yōu)化。

對不同層進行特征重要度計算，然后記為層重要度，根據(jù)重要度比例進行抽樣，實驗結(jié)果與原始結(jié)果對比見圖5。

從實驗結(jié)果可以看出，加權(quán)后的分層子空間隨機森林算法較原始隨機森林算法準(zhǔn)確度有所提升，袋外準(zhǔn)確度也有提升。

由以上實驗可知，優(yōu)化后的隨機森林算法預(yù)測精度有一定提升，有效降維減少了算法運行時間，提高了算法性能。將優(yōu)化后的隨機森林算法應(yīng)用在Spark平臺上，可對大數(shù)據(jù)進行高效處理。

4 結(jié)語

本文首先對隨機森林進行參數(shù)調(diào)優(yōu)，找到最合適的參數(shù)組合。在調(diào)參過程中發(fā)現(xiàn)過大的特征比使噪聲對隨機森林準(zhǔn)確率有明顯影響;然后使用隨機森林模型對數(shù)據(jù)集進行特征評估，去除掉一些噪聲數(shù)據(jù)，對篩選后的特征進行卡方檢驗操作，將特征分為強弱特征層;分層后對不同層進行權(quán)重計算，按照權(quán)重比例取樣，訓(xùn)練隨機森林模型，進行分類預(yù)測。實驗結(jié)果表明隨機森林預(yù)測準(zhǔn)確度明顯提升，袋外正確率也有一定提升。

本文在進行特征分層時沒有考慮冗余數(shù)據(jù)影響，因為特征維度較大，冗余數(shù)據(jù)的計算量也較大。下一步將研究一種優(yōu)化的冗余特征處理方式。

參考文獻：

[1]ASSEFI M，BEHRAVESH E. Big data machine learning using Apache Spark MLLIB[C]. 2017 IEEE International Conference on Big Data （Big Data）.? IEEE， 2017： 3492-3498.

[2]CHEN J， LI K， TANG Z， et al. A parallel random forest algorithm for big data in a spark cloud computing environment[J]. IEEE Transactions on Parallel and Distributed Systems， 2017， 28（4）： 919-933.

[3]SUN K， MIAO W， ZHANG X， et al. An improvement to feature selection of random forests on spark[C]. 2014 IEEE 17th International Conference on Computational Science and Engineering，2014：774-779.

[4]DEL RíO S， LóPEZ V， BENíTEZ J M， et al. On the use of mapreduce for imbalanced big data using random forest[J]. Information Sciences， 2014（285）： 112-137.

[5]XY Y. Research and implementation of improved random forest algorithm based on spark[C]. 2017 IEEE 2nd International Conference on Big Data Analysis，2017： 499-503.

[6]羅元帥.? 基于隨機森林和Spark的并行文本分類算法研究[D]. 成都：西南交通大學(xué)，2016.

[7]牛志華.? 基于Spark分布式平臺的隨機森林分類算法研究[D]. 天津：中國民航大學(xué)，2017.

[8]KHALILIA M，CHAKRABORTY S，POPESCU M. Predicting disease risks from highly imbalanced data using random forest[J].? BMC Medical Informatics and Decision Making， 2011， 11（1）： 51-59.

[9]BELGIU M，DRAGUT L.Random forest in remote sensing： a review of applications and future directions[J]. ISPRS Journal of Photogrammetry and Remote Sensing， 2016（114）： 24-31.

[10]LIN W， WU Z， LIN L， et al. An ensemble random forest algorithm for insurance big data analysis[J]. IEEE Access， 2017（5）： 16568-16575.

[11]張思琪. 基于改進貝葉斯分類的Android惡意軟件檢測[J]. 無線電通信技術(shù)，2014，40（6）：73-76.

[12]DAGDIA Z C， ZARGES C，BECK G，et al. A distributed rough set theory based algorithm for an efficient big data pre-processing under the Spark framework[C]. 2017 IEEE International Conference on Big Data （Big Data）.? IEEE， 2017： 911-916.

[13]RUAN F， QI J， YAN C， et al. Quantitative detection of harmful elements in alloy steel by LIBS technique and sequential backward selection-random forest （SBS-RF）[J]. Journal of Analytical Atomic Spectrometry，2017，32（11）： 2194-2199.

[14]馬曉東. 基于加權(quán)決策樹的隨機森林模型優(yōu)化[D]. 武漢：華中師范大學(xué)，2017.

[15]ZAHARIA M， XIN R S， WENDELL P， et al. Apache Spark： a unified engine for big data processing[J]. Communications of the ACM， 2016， 59（11）： 56-65.

[16]梁彥.? 基于分布式平臺Spark和YARN的數(shù)據(jù)挖掘算法的并行化研究[D]. 廣州：中山大學(xué)，2014.

[17]遲玉良，祝永志. 項目相似度與ALS結(jié)合的推薦算法研究[J]. 軟件導(dǎo)刊，2018，17（6）：81-84.

[18]唐振坤. 基于Spark的機器學(xué)習(xí)平臺設(shè)計與實現(xiàn)[D]. 廈門：廈門大學(xué)，2014.

[19]GENUER R，POGGI J M，TULEAUL C， et al. Random forests for big data[J].? Big Data Research， 2017（9）： 28-46.

[20]孫科.? 基于Spark的機器學(xué)習(xí)應(yīng)用框架研究與實現(xiàn)[D]. 上海：上海交通大學(xué)，2015.

（責(zé)任編輯：杜能鋼）

收稿日期：2019-05-13

基金項目：山東省自然科學(xué)基金項目（ZR2013FL015）;山東省研究生教育創(chuàng)新資助計劃項目（SDYY12060）

作者簡介：荊靜（1995-），女，曲阜師范大學(xué)信息科學(xué)與工程學(xué)院碩士研究生，研究方向為分布式計算、大數(shù)據(jù);祝永志（1964-），男，曲阜師范大學(xué)信息科學(xué)與工程學(xué)院教授、碩士生導(dǎo)師，研究方向為并行與分布式計算、網(wǎng)絡(luò)數(shù)據(jù)庫。