杭琦 楊敬輝

摘要

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

【關鍵詞】機器學習 集成學習 隨機森林

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

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

1隨機森林算法的構建過程

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

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

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

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

從隨機森林三個評估過程中可以看出。隨機森林的構建過程中摻入了隨機性，從而降低了隨機森林過擬合現象的產生。

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

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

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

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

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

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

針對算法自身構建過程的改進主要表現在降低泛化誤差，減少每顆決策樹之間的相關性。

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

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

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

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

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

3隨機森林算法的性能指標研究

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

3.1分類效果指標

隨機森林算法的應用場景最多的還是出現在預測和分類模型中，表1中的混淆矩陣是二分類中經常用到的評估分類效果的指標。

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

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

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

3.2泛化誤差

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

4結語

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

參考文獻

[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)，面向非平衡訓練集分類的隨機森林算法優(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è)大學，2008.

[9]孫麗麗，基于屬性組合的隨機森林[D]，河北大學，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]馬景義，吳喜之，謝邦昌，擬自適應分類隨機森林算法[J].數理統(tǒng)計與管理，2010， 29 （05）： 805-811.

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

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