杭琦 楊敬輝

摘要

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2泛化誤差

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

4結(jié)語

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

參考文獻(xiàn)

[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]吳瓊，李運(yùn)田，鄭獻(xiàn)衛(wèi)，面向非平衡訓(xùn)練集分類的隨機(jī)森林算法優(yōu)化[J]，工業(yè)控制計(jì)算機(jī)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]雍凱，隨機(jī)森林的特征選擇和模型優(yōu)化算法研究[D].哈爾濱工業(yè)大學(xué)，2008.

[9]孫麗麗，基于屬性組合的隨機(jī)森林[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ī)森林算法[J].數(shù)理統(tǒng)計(jì)與管理，2010， 29 （05）： 805-811.

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

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