杭琦 楊敬輝

摘要

隨機森林（RF）是機器學(xué)習(xí)算法中的一種組合分類器，也是集成學(xué)習(xí)的代表性算法之一。它通過bagging算法集成多個決策樹并以投票的形式輸出結(jié)果，在學(xué)術(shù)界和工業(yè)界均取得了很好的評價。本文將具體介紹隨機森林算法的構(gòu)建過程，總結(jié)隨機森林算法在性能改進、性能指標(biāo)方面的研究，對目前隨機森林已經(jīng)有的理論和應(yīng)用研究做一個系統(tǒng)的總結(jié)和整理，以利于后續(xù)的算法優(yōu)化研究。

【關(guān)鍵詞】機器學(xué)習(xí) 集成學(xué)習(xí) 隨機森林

機器學(xué)習(xí)算法主要解決的是分類和聚類的問題。分類問題是根據(jù)用戶的分類數(shù)據(jù)得到預(yù)測的分類結(jié)果。根據(jù)分類器的個數(shù)，分類器又分為單分類器和多分類器。例如決策樹、貝葉斯都是傳統(tǒng)單分類算法。這些傳統(tǒng)的機器學(xué)習(xí)算法在一定程度上都促進了分類學(xué)習(xí)的發(fā)展，但由于單分類器有其自身的限制，容易產(chǎn)生過擬合等現(xiàn)象。故學(xué)者們提出集成多個分類器形成組合分類器，把一個學(xué)習(xí)問題分解到各個子學(xué)習(xí)器內(nèi)，讓其一起學(xué)習(xí)。多分類器的分類思想起源子集成學(xué)習(xí)，Boosting和Bagging是最早將集成學(xué)習(xí)思想應(yīng)用到機器學(xué)習(xí)分類算法里中兩種算法。隨著集成學(xué)習(xí)的發(fā)展，TinKam Ho在1995年提出了隨機決策森林的思想，1998年，他又提出了新的隨機子空間的集成方法，Breiman根據(jù)隨機子空間的思想在2001提出了隨機森林算法，從理論和實踐兩方面做了系統(tǒng)的闡述，自此隨機森林算法成為機器學(xué)習(xí)領(lǐng)域中的一個具有代表性的集成學(xué)習(xí)的方法。

本篇文章第一節(jié)針對隨機森林算法構(gòu)建過程進行簡單介紹;第二節(jié)介紹隨機森林在性能改進方面的研究;第三節(jié)針對隨機森林的性能指標(biāo)進行研究總結(jié);最后總結(jié)全文。

1隨機森林算法的構(gòu)建過程

隨機森林算法是一種集成分類模型，它的構(gòu)建過程主要由三個方面構(gòu)成，訓(xùn)練集的生成、決策樹的構(gòu)建和算法的產(chǎn)生。要構(gòu)建隨機森林首先要生成一個規(guī)模大小為N的隨機森林，就需要有N顆樹，因此需要N組訓(xùn)練集。故首先我們需要從原始數(shù)據(jù)中通過抽樣產(chǎn)生訓(xùn)練集。通過Bagging算法從原始數(shù)據(jù)集中抽取N個樣本。每個樣本都會生產(chǎn)一個決策樹，且生成的決策樹不需要做剪枝處理，從而建立起N棵決策樹形成森林。隨機森林生成過程中涉及到如下三個評估過程：

（1）指定m值，由于在每棵決策樹分裂的過程中，不是樣本中全部K個特征屬性都參與分裂，而是從中隨機抽取m個變量，同時分裂過程中特征屬性的選擇需滿足節(jié)點不純度最小原則。

（2）應(yīng)用Bagging隨機取樣法在原數(shù)據(jù)集中有放回地隨機抽取k個樣本集，組成k棵決策樹;

（3）根據(jù)k個決策樹組成的隨機森林對待分類樣本進行分類或預(yù)測，分類的結(jié)果由單顆決策樹的分類結(jié)果投票決定。

從隨機森林三個評估過程中可以看出。隨機森林的構(gòu)建過程中摻入了隨機性，從而降低了隨機森林過擬合現(xiàn)象的產(chǎn)生。

2隨機森林算法優(yōu)化方法研究

基于集成學(xué)習(xí)的隨機森林算法從根源上改善了決策樹容易過擬合的特性。但是該算法在算法處理不同類型數(shù)據(jù)集特別是不平衡數(shù)據(jù)集和算法分類精度的方面，還需要一定程度的改進。因此國內(nèi)外的學(xué)者專家們就隨機森林算法的優(yōu)化方面提出了很多的改進的方法，細分起來，它們可以分成以下三個主要的方面。

2.1結(jié)合數(shù)據(jù)預(yù)處理對隨機森林算法進行優(yōu)化

不平衡數(shù)據(jù)集的分類問題是當(dāng)前機器學(xué)習(xí)領(lǐng)域的一大挑戰(zhàn)。故針對隨機森林處理不平衡數(shù)據(jù)集上的分類問題上，學(xué)者專家們將數(shù)據(jù)預(yù)處理融入到隨機森林算法優(yōu)化的研究中來，通過數(shù)據(jù)預(yù)處理，隨機森林的性能得到了一定的提升。

文獻[4]提出代價敏感隨機森林算法，在隨機森林算法中引入代價敏感學(xué)習(xí)，讓分類器更偏向少數(shù)類，使得總的誤分類代價最小化。文獻[5]首次提出對原始數(shù)據(jù)進行NCL（Neighborhood Cleaning Rule）處理，并將處理過的數(shù)據(jù)結(jié)合隨機森林算法進行分類，實驗表明經(jīng)過NCL技術(shù)改進后的隨機森林算法擁有更好的分類精度。文獻[6]提出了分層抽樣的隨機森林算法，并且在節(jié)點分裂處采用支持向量機算法作為算法的基分類器，結(jié)果表明經(jīng)過改進的隨機森林算法在非平衡數(shù)據(jù)的處理效果比傳統(tǒng)的隨機森林、過采樣支持向量機、欠采樣支持向量機的都要好。

2.2針對隨機森林算法構(gòu)建過程的優(yōu)化

針對算法自身構(gòu)建過程的改進主要表現(xiàn)在降低泛化誤差，減少每顆決策樹之間的相關(guān)性。

由于傳統(tǒng)隨機森林算法中各個決策樹的之間的權(quán)重相同，故修改決策樹之間權(quán)重的思想被廣泛的用于隨機森林的改進。Li，Wang[7]等人根據(jù)袋外數(shù)據(jù)誤分率進行權(quán)重設(shè)置，用正確的分類與隨機森林分類器的結(jié)果進行比較，統(tǒng)計隨機森林分類器分類錯誤的數(shù)目。雍凱[8]利用卡方檢驗進行特征的相關(guān)性評估，依據(jù)評估的結(jié)果進行隨機特征選擇，該方法可以很好的降低隨機森林泛化誤差的上界，進而提高整體的分類精度。孫麗麗[9]等人根據(jù)由聚類數(shù)據(jù)構(gòu)建的多棵決策樹構(gòu)成的隨機森林來進行分類器的加權(quán)集成，通過加權(quán)集成可以很好的降低數(shù)據(jù)集的復(fù)雜性，提高整體的分類效率和分類準(zhǔn)確度。

2.3引入新算法進行隨機森林的優(yōu)化

Breiman根據(jù)隨機子空間的思想在2001提出了隨機森林算法。從本質(zhì)上講，該算法是Bagging方法和Random Subspace方法的組合。近幾年來對于隨機森林的改進方法的研究大部分在組合算法上，通過將優(yōu)秀的算法融入到隨機森林算法中，從而提升分類精度。

旋轉(zhuǎn)森林算法（Rotation Forests）[10]中引入了主成分分析算法進行特征向量的變換，通過把原始數(shù)據(jù)集上的原始向量通過坐標(biāo)變換旋轉(zhuǎn)到主成分所在的方向，再進行隨機森林的構(gòu)建。霍夫森林算法（Hough forests） [11]將霍夫變換引入到隨機森林的投票過程中，對隨機森林的投票機制進行了優(yōu)化。馬景義[12]等我國學(xué)者們將Adaboost算法與隨機森林算法進行組合，提出了一種改進的隨機森林算法算法一擬自適應(yīng)分類隨機森林算法，此算法不用區(qū)分數(shù)據(jù)集，通過發(fā)揮兩種算法各自的優(yōu)勢，得到了較好的分類效果。

從上文的三種優(yōu)化方法來看，對于隨機森林算法分類性能的提升，第一種改進方法主要側(cè)重于對于不平衡數(shù)據(jù)的優(yōu)化研究上;第二種改進方法主要集中于各種組合算法的研究上，這些組合算法一般都被用于某個特定的問題上;而第三個種優(yōu)化方式主要集中在算法本身的改進上，在權(quán)重的優(yōu)化方面改進較多，這類算法具有一定的通用性，可以在不同的領(lǐng)域中使用。

3隨機森林算法的性能指標(biāo)研究

隨機森林分類性能受外部因素和內(nèi)部因素的共同影響，從內(nèi)部因素來看，一般從每棵決策樹的最大樹深度、決策樹的分類強度和決策樹之間的相關(guān)性來考慮。從外部因素看，主要來自原始數(shù)據(jù)本身的分布情況，包括正負樣本的分類，樣本的規(guī)模等情況。評價隨機森林性能的指標(biāo)一般有兩種：分類效果指標(biāo)和泛化誤差。

3.1分類效果指標(biāo)

隨機森林算法的應(yīng)用場景最多的還是出現(xiàn)在預(yù)測和分類模型中，表1中的混淆矩陣是二分類中經(jīng)常用到的評估分類效果的指標(biāo)。

其中TP指被模型預(yù)測為正的正樣本數(shù)量TN指的是被模型預(yù)測為負的負樣本數(shù)量;FP指被模型預(yù)測為正的負樣本數(shù);FN指的是被模型預(yù)測出來為負的正樣本數(shù)。

精確率（ Precision），表示預(yù)測為正例的樣本中，真正為正例的比例計算公式為：

分類準(zhǔn)確率（Accuracy），表示分類模型總體的分類精度，計算公式為：

3.2泛化誤差

泛化能力（generalizadon ability）是指機器學(xué)習(xí)算法對新鮮樣本的適應(yīng)能力。即對于具有相同分布規(guī)律訓(xùn)練集以外的數(shù)據(jù)，該模型也能做出正確的判斷。在很多工業(yè)生產(chǎn)的應(yīng)用場景中，我們通常用泛化誤差（GeneralizationError）來評估機器學(xué)習(xí)算法的泛化能力，如果泛化誤差越大，那么該模型學(xué)習(xí)性能越差，反之則性能越好。泛化誤差從理論上來說可以通過公式直接計算出來的。但是從實際應(yīng)用來看我們無法獲得準(zhǔn)確的樣本分布情況和樣本的期望輸出。目前用來估計分類器的泛化誤差的方法主要有兩種，一種是分析模型（AnalyticalModel）還有一種是交叉驗證（Cross-validation，CV）。分析模型對于簡單的線性分析是比較有效的，但由于其難以對隨機森林的有效參數(shù)做出合理估計，所以對于非線性等復(fù)雜的問題難以突出其優(yōu)點。交叉驗證是通過把訓(xùn)練數(shù)據(jù)分成了訓(xùn)練集和測試集，用訓(xùn)練集來訓(xùn)練算法，再用測試集來驗證算法，從而通過驗證集來估計泛化誤差。而OOB估計是隨機森林算法的一種比較好的估計泛化誤差的方法。在構(gòu)建決策樹時需要對訓(xùn)練集進行隨機且有放回地抽取，故對于隨機森林模型中的初始訓(xùn)練集來說總會有一些原始數(shù)據(jù)沒有參加模型的訓(xùn)練，而這些沒有參加模型訓(xùn)練的樣本就是OBB數(shù)據(jù)。Breiman已經(jīng)在論文中用實例表明OOB估計與同樣誤差大小的測試集有著相同的分類精度，OBB估計可以作為隨機森林泛化誤差的一個無偏估計。

4結(jié)語

在如今，機器學(xué)習(xí)算法是被很多學(xué)者專家們追捧的學(xué)習(xí)方法，隨機森林也是在其中孕育而生的。隨機森林算法是集成學(xué)習(xí)中具有代表性的一個算法，它簡單高效、應(yīng)用廣泛，在金融學(xué)、醫(yī)學(xué)、生物學(xué)等眾多應(yīng)用領(lǐng)域均取得了很好的成績。故本文對隨機森林構(gòu)建過程做了研究，還通過其性能改進和性能指標(biāo)兩方面進行了總結(jié)。但作為學(xué)術(shù)界和工業(yè)界均應(yīng)用很廣的一個算法，我們還需要考慮在數(shù)據(jù)量日益增大的復(fù)雜分類任務(wù)中，在如何有效提升模型復(fù)雜度，如何處理非平衡數(shù)據(jù)、連續(xù)性數(shù)據(jù)以及如何提升算法的分類精度這些問題上都值得我們進行深入的探討。

參考文獻

[1]T.K. Ho. RandomDecision Forest [J]. InProceedings of the3rd InternationalConFerence on Document Analysisand Recognition. Montreal， Canada，1995，8：278-282.

[2]T. K. Ho， he Random Subspace Method for Constructing Decision Forests.[J].IEEE Transactions on PatternAnalysis and Machine Intelligence，1998， 20 （8）： 832-844.

[3]L. Breiman， Random Forests [J].MachineLearning， 2001，45 （1）： 5-32.

[4]houQ， Zhou H， Li T. Cost-sensitivefeature selection using randomforest： Selecting low-costsubsetsof

informa tivefeatures [J].Knowledge-Based Systems，2015： S0950705115004372.

[5]吳瓊，李運田，鄭獻衛(wèi)，面向非平衡訓(xùn)練集分類的隨機森林算法優(yōu)化[J]，工業(yè)控制計算機201213， 26 （07）： 89-90

[6]Wu Q， Ye Y， Zhang H， et al.ForesTexter： An efficient randomforest algorithm for imbalanced textcategorizat ion [J].

Knowledge-BasedSystems， 2014， 67 （3）： 105-116.

[7]L1 H B， Wang W， Ding H W， et al.Trees Weighting Random Forest Methodfor Classifying High-DimensionalNoisy Data [C]. IEEE InternationalConference on E-business Engineering.IEEE， 2011.

[8]雍凱，隨機森林的特征選擇和模型優(yōu)化算法研究[D].哈爾濱工業(yè)大學(xué)，2008.

[9]孫麗麗，基于屬性組合的隨機森林[D]，河北大學(xué)，2 011.

[10] Rodriguez J J， Kuncheva L I ，Alonso C J. Rotation Forest： A NewClassifier Ensemble Method[J]. IEEETrans Pattern Anal Mach Intell，2006， 28 （10）：1619-1630.

[ll]LempitskyV. Hough Forests for ObjectDetection， Tracking， and ActionRecognition[J]. IEEE Transactionson Pattern Analysis & MachineIntelligence， 2011， 33 （11）： 2188-2 02.

[12]馬景義，吳喜之，謝邦昌，擬自適應(yīng)分類隨機森林算法[J].數(shù)理統(tǒng)計與管理，2010， 29 （05）： 805-811.

[13] Cortes C. Prediction ofGeneralization Ability in LearningMachines [J]. 1995.

[14]劉凱，隨機森林自適應(yīng)特征選擇和參數(shù)優(yōu)化算法研究[D].長春工業(yè)大學(xué)，2018.