集成學習之隨機森林算法綜述

王奕森 夏樹濤

清華大學深圳研究生院/計算機科學與技術系深圳518055

引言

分類和回歸問題幾乎涵蓋了現實生活中所有的數據分析的情況，兩者的區別主要在于我們關心的預測值是離散的還是連續的。比如，預測明天下雨不下雨的問題就是一個分類問題，因為預測結果只有兩個值：下雨和不下雨(離散的)；預測中國未來的國民生產總值(GDP)就是一個回歸問題，因為預測結果是一個連續的數值。在一些情況下，通過把連續值進行離散化，回歸問題可以轉化為分類問題，因此，我們在這篇文章中將主要研究分類問題。傳統的分類的機器學習算法有很多[1]，比如決策樹算法(Decision Tree)[2-4]、支持向量機算法(Support Vector Machine)[5]等。這些算法都是單個分類器，他們有性能提升的瓶頸以及過擬合的問題；因此，集成多個分類器來提高預測性能的方法應運而生，這就是集成學習算法(Ensemble Learning)[6]。Bagging[7](并行)和Boosting[8](串行)是兩種常見的集成學習方法，這兩者的區別在于集成的方式是并行還是串行。隨機森林算法(Random Forests)[9]是Bagging集成方法里最具有代表性的一個算法，這也是本文重點總結的算法。

隨機森林是基于決策樹的一種集成學習算法。決策樹是廣泛應用的一種樹狀分類器，在樹的每個節點通過選擇最優的分裂特征不停地進行分類，直到達到建樹的停止條件，比如葉節點里的數據都是同一個類別的。當輸入待分類樣本時，決策樹確定一條由根節點到葉節點的唯一路徑，該路徑葉節點的類別就是待分類樣本的所屬類別。決策樹是一種簡單且快速的非參數分類方法，一般情況下，它有很好的準確率，然而當數據復雜時，決策樹有性能提升的瓶頸。隨機森林是2001年由Leo Breiman將Bagging集成學習理論[10]與隨機子空間方法[11]相結合，提出的一種機器學習算法。隨機森林是以決策樹為基分類器的一個集成學習模型，如圖1所示，它包含多個由Bagging集成學習技術訓練得到的決策樹，當輸入待分類的樣本時，最終的分類結果由單個決策樹的輸出結果投票決定。隨機森林解決了決策樹性能瓶頸的問題，對噪聲和異常值有較好的容忍性，對高維數據分類問題具有良好的可擴展性和并行性。此外，隨機森林是由數據驅動的一種非參數分類方法，只需通過對給定樣本的學習訓練分類規則，并不需要先驗知識。

圖1 隨機森林算法圖解(整體圖)

在Breiman提出隨機森林算法之后，由于其良好的性能表現，該算法被廣泛應用到諸如生物信息領域對基因序列的分類和回歸[12-13]、經濟金融領域對客戶信用的分析及反欺詐[14-15]、計算機視覺領域對人體的監測與跟蹤、手勢識別、動作識別、人臉識別、性別識別和行為與事件識別[16-17]，語音領域的語音識別與語音合成[18]、數據挖掘領域的異常檢測、度量學習[19-20]等實際領域。總結來看，在隨機森林研究領域，目前有三個方面的研究熱點。1)隨機森林算法在性能改進方面的研究，特別是在高維數據情況下，隨機森林算法的性能還有待提高。2)隨機森林算法在理論性質方面的研究，相比于隨機森林在應用方面的大量研究，其理論研究明顯滯后。隨機森林算法的一致性等還沒有被完全證明。3)同樣作為分層算法，隨機森林和目前最熱的深度學習有怎樣的區別和聯系，以及如何結合才能產生更好的算法，也是目前研究的一個熱點。本文將從以上三個方面對隨機森林算法領域的研究進行總結，期望能對新入行的讀者起到引導作用，及已經是該領域的學者產生啟發作用。

1 隨機森林算法簡介

1.1 決策樹

決策樹是一個無參有監督的機器學習算法。Quinlan提出了ID3決策樹算法[2]，Breiman等人提出了CART決策樹算法[4]，1993年Quinlan又提出了C4.5決策樹算法[3]，Wang和Xia又于2016年提出了Tsallis決策樹算法[21]。一般而言，決策樹的建樹最常見的是自下而上的方式。一個給定的數據集被分裂特征分成左和右子集，然后通過一個評價標準來選擇使平均不確定性降低最高的分裂方式，將數據集相應地劃分為兩個子節點，并通過使該節點成為兩個新創建的子節點的父節點來建樹。整個建樹過程是遞歸迭代進行的，直到達到停止條件，例如達到最大樹深度或最小葉尺寸。

決策樹的一個關鍵問題是節點分裂特征的選擇。至于分裂標準，一系列論文已經分析了它的重要性[22-23]。他們證明了不同的分裂標準對決策樹的泛化誤差有很大的影響；因此，根據不同的劃分標準，提出了大量的決策樹算法。例如，ID3算法基于香農熵；C4.5算法基于增益比；而CART算法基于Gini不純度。然而，在這些算法中，沒有一個算法總能在各種數據集上得到最好的結果。實際上，這反映了這種分類標準缺乏對數據集適應性的一個缺點。因此，已經有學者提出自適應熵估計的替代方法[24-25]，但是它們的統計熵估計過于復雜，使決策樹的簡單性和可理解性喪失。最近，Tsallis熵分裂準則被提出來統一通用分裂準則[21]，即統一了香農熵、增益比和Gini不純度。

決策樹不需要先驗知識，相比神經網絡等方法更容易解釋，但是由于決策樹在遞歸的過程中，可能會過度分割樣本空間，最終建立的決策樹過于復雜，導致過擬合的問題，使得分類精度降低。為避免過擬合問題，需要對決策樹進行剪枝[26]，根據剪枝順序不同，有事先剪枝方法和事后剪枝方法，但都會增加算法的復雜性。

1.2 隨機森林

決策樹是單個分類器，通過上述分析，可以看出其有性能提升的瓶頸。集成學習是將單個分類器聚集起來，通過對每個基本分類器的分類結果進行組合，來決定待分類樣本的歸屬類別。集成學習比單個分類器有更好的分類性能，可以有效地提高學習系統的泛化能力。

假定給定的數據集為D={Xi,Yi}，Xi∈RK，Yi∈{1,2,…,C}，隨機森林是在此數據集上以M個決策樹{g(D,θm),m=1,2,…,M}為基分類器，進行集成學習后得到的一個組合分類器。當輸入待分類樣本時，隨機森林輸出的分類結果由每個決策樹的分類結果進行多數投票決定。隨機森林里有兩個重要的隨機化，如圖2所示。

圖2 隨機森林算法流程圖(細節圖)

1)樣本Bagging：從原樣本集D中通過bootstrap有放回地隨機抽取M個與原樣本集同樣大小的訓練樣本集Dm，然后據此構建一個對應的決策樹。

2)特征的隨機子空間：在對決策樹每個節點進行分裂時，從全部K個特征中均勻隨機抽取一個特征子集(通常取log2K)，然后從這個子集中選擇一個最優分裂特征來建樹。

由于構建每個決策樹時，隨機抽取訓練樣本集和特征子集的過程都是獨立的，且總體都是一樣的，因此，{θm,m=1,2,…,M}是一個獨立同分布的隨機變量序列。由于各個決策樹的訓練相互獨立，因此，隨機森林的訓練可以通過并行處理來實現，該性質有效地保證了隨機森林算法的效率和可拓展性。

2 隨機森林算法的性能提升

根據Breiman給出的隨機森林泛化誤差的上界[9]：

我們可以看出隨機森林的泛化誤差界與單個決策樹的分類強度s成負相關，與決策樹之間的相關性成正相關，即分類強度越大，相關性越小，則泛化誤差界越小，隨機森林分類準確度越高。這也啟發我們，對隨機森林模型進行改進時，可以從兩方面著手：一是提高單棵決策樹的分類強度s，二是降低決策樹之間的相關性。隨機森林在高維數據上的表現并沒有它在中低維數據上的表現好，因此，有一系列的研究工作針對隨機森林在高維數據下的性能提升。

旋轉森林算法(Rotation Forests)[27]引入了主成分分析(Principal Component Analysis，PCA)[28]的特征變換，相當于把數據集上的原始特征旋轉到了主成分所在的方向，進而再進行后續的基于特征子空間的隨機森林的構建，這里的集成是建立在整個數據集的所有主成分之上的。此外，還有另外一些類似的方法應用到隨機森林里，比如，使用前S個主成分構建第一棵決策樹，接著用后續的S個主成分構建第二棵決策樹，這樣依次下去[29]。但是，這種方法會導致比較靠后的決策樹是在包含比較少的信息的特征子空間上構建的，會降低決策樹的性能，進而傷害集成之后的隨機森林的性能。此外，還有一些文獻把PCA作為特征提取和降維的預處理方法，這些算法只保留了很少的一些較大值的主成分，這導致他們有一個缺點就是由于只有少數主成分被保留，那些對應于小主成分值但是卻包含最相關的判別信息的特征可能被丟棄[30]。

此外，還有一些從特征子空間選擇的角度入手來提升隨機森林性能的。均勻隨機地選取部分特征構成特征子空間在高維數據的情況下，會導致隨機森林的性能下降，這是因為隨機選擇的特征子空間可能包含很少或者沒有信息量的特征，這會導致依賴于此特征子空間的決策樹的性能下降，進而影響集成的隨機森林的性能[31]；因此，有一系列的文獻采取了分層采樣的方法來解決這個問題，他們主要關注于如何把特征根據包含信息的多少分開，然后對不同信息量的特征采取分層采樣的方式構成特征子空間。分層隨機森林(Stratified Random Forests)[32]采用Fisher判別投影得到的權重把特征分為兩部分，即強信息特征和弱信息特征。子空間選擇隨機森林(Subspace Selection Random Forests)[33]應用一個統計準則把特征分為三部分。首先，應用p-value來衡量特征的重要性，把特征分為信息特征和非信息特征。其次，應用卡方統計量進一步把信息特征分為高信息特征和信息特征兩部分。基于主成分分析的分層采樣隨機森林(Principal Component Analysis and Stratified Sampling based Random Forests)[34]提出了一種根據PCA輸出的結果把特征劃分為信息特征和非信息特征的準則的一種方法。此外，還有一種對特征進行加權的方式來取代分層采樣[35]。他們首先計算特征與類別之間的相關性，并把這種相關性認為是該特征在特征子空間中被選到的概率，但是這種方式可能會引入更多強相關的決策樹，因為那些具有很大權重的特征很可能被重復多次地選到。

3 隨機森林算法的理論研究

與隨機森林在許多實際應用中展現出的非常有吸引力的實際性能相比，它們的理論性能還沒有完全建立，仍然是積極研究的課題。對于一個學習算法來說，一致性是最基本的理論性質，因為它確保了隨著數據增長到無限大而算法能收斂到最優解。一致性的定義如下：對于分類問題，給定訓練集D，對于一個(X,Y)的分布，我們說隨機森林分類器g具有一致性，如果

這里的L*代表貝葉斯風險，也就是(X，Y)的分布所能達到的最小風險。

隨機森林一致性的研究之所以難，原因在于隨機森林融合了隨機化的因素和確定性的建樹過程。具體來說，樣本bootstrap和特征子空間的機制是為了構建不那么依賴數據的決策樹，但是CART建樹的過程是依賴于Gini不純度的，這是完全依賴于數據的；因此，隨機森林一致性的研究基本都是從如何簡化這個確定性的建樹過程著手。簡化必然就會帶來性能的損失，所以該領域的研究目標是要做到一致性可以被證明但是性能也不能損失太多。

在一致性方面一個重要的理論突破是由Biau在2008年提出的[36]，他證明了一種原始隨機森林的最直接的簡化版本，即關于選取分裂特征和分裂值的時候，它是從所有特征里面隨機選一個作為分裂特征，同時，從該被選的特征值里隨機選一個值當作分裂值。這種簡化的隨機森林一致性是可以被證明的，但是實驗性能很差。緊接著到2012年，Biau把這個領域的研究又往前推進了一步[37]。首先，分裂特征的選擇和原始隨機森林一樣，采用同樣的方式構建特征子空間；其次，分裂值的選擇是各個特征所有值的中位數；最后，也是通過不純度下降最多的準則來選取最優的分裂特征和分裂值的組合。Denil等人在2014年提出了另外一種非常接近于原始隨機森林的具有一致性的版本[38]，區別點在于分裂值的選取，他們先隨機抽取一個所有該特征值的子集，然后在這個子集上尋找最優的分裂。Wang等人在2016年提出了一種概率優化的具有一致性的隨機森林，叫伯努利隨機森林(Bernoulli Random Forests)[39]。他們采取了兩個伯努利分布來控制分裂特征和分裂值的選擇，具體來說，以一個伯努利分布B1來控制隨機選一個特征或構建特征子空間，以另外一個伯努利分布B2來控制隨機選一個分裂值，或是遍歷全部分裂值選擇不純度下降最多的。他們提出的伯努利隨機森林是目前性能最好的并且具有一致性的隨機森林算法。

4 隨機森林算法與深度學習之間的關系

隨機森林是基于一種樹狀的分層結構，而深度學習中深度神經網絡(Deep Neural Networks)也是一種基于稠密連接的分層的網絡結果。我們這章將主要分析隨機森林算法與深度神經網絡之間的關系，以及把兩者相結合的一些研究。

首先，就深度神經網絡而言，它有很多層，也有很多參數，而且這些參數全部都會在測試的時候用到。深度神經網絡在最后一層分類器之前，我們一般認為它們是一個表示學習的過程，也就是說深度神經網絡的分類是基于學習到的特征的。深度神經網絡采用的是端到端的訓練方式，即基于損失函數的梯度下降。然而，就隨機森林而言，它也有很多層，很多參數，但是只有log2N個參數會被用于測試，因為測試樣本只會選擇唯一一條路徑。隨機森林的訓練是逐層進行的，沒有基于目標函數的梯度下降。而且隨機森林的建樹過程是邊建樹邊分類的，因此，幾乎沒有或者說有很有限的特征學習的過程。

深度神經網絡有很多超參數，調參費時費力，而隨機森林幾乎沒有超參數。深度神經網絡有一個很強大的表示學習過程，而隨機森林沒有。近年來，有一些工作嘗試把深度神經網絡和隨機森林結合在一起。Bulo和Kontschieder在2014年[40]提出了基于神經網絡的分裂函數取代之前的Gini不純度。Kontschieder等人又在2015年[41]進一步提出了深度神經決策森林，他們把隨機森林接在了深度神經網絡的表示學習過程的后面，把分裂函數變成了隨機決策的函數，使其能夠通過反向傳播來更新整個網絡的參數。這大大降低了深度神經網絡的參數復雜度，同時，也提升了隨機森林的性能。

此外，Zhi-Hua Zhou等人還提出了一種完全基于隨機森林的深度結構[42]，他們把隨機森林看作是深度神經網絡中的一個節點。具體來說，他們采取了級聯森林和多粒度掃描來構建深度森林。每個級是決策樹森林的一個集合，即集成的集成(ensemble of ensembles)。他們使用了兩個完全隨機的樹森林(complete-random tree forests)和兩個原始隨機森林。每個完全隨機的樹森林通過隨機選擇一個特征在樹的每個節點進行分割實現生成。類似地，每個原始隨機森林通過隨機選擇特征子空間，然后選擇具有最佳Gini值的特征作為分割。此外，他們應用了滑動窗口來掃描原始特征生成新的特征向量，這些特征向量用作深度森林的輸入，可以認為這是對原始特征做了特征變換之后再建樹。

5 結語

集成學習是一類非常重要而且實用的方法，它在稍微增加一點復雜度的情況下通常總能提升多個已有分類器的性能，從而在各大競賽及實際問題中被廣泛應用。隨機森林等Bagging算法是一種非常具有代表性的集成學習算法，它簡單高效、使用方便，在生物信息學、經濟學、計算機視覺等眾多應用領域取得了巨大的成功。本文從實驗性能和理論性質兩方面出發對已有的隨機森林算法研究進行了總結，最后還闡述了隨機森林算法與目前最火熱的深度學習之間的關系以及兩者相結合的一些工作。作為學術界和工業界均廣為應用的一個算法，隨機森林在理論性質和應用性能上都還有提升的空間，除了算法一致性仍未完全解決之外，還有以下研究方向，如：為應對日益復雜的分類任務，為充分利用已有的大數據和強大計算能力，如何有效提升模型復雜度、如何利用分層或迭代的方法給出性能更好的集成學習算法；隨機森林算法有算法復雜度低而且自帶并行化的優勢，如何把隨機森林算法中的這些思想融入到深度學習的研究當中，加快深度學習的訓練并提高其可解釋性等，都是值得我們探討的問題。

[1]Wu X,Kumar V,Quinlan JR,et al.Top 10 algorithms in data mining[J].Knowledge and information systems,2008,14(1):1-37

[2]Quinlan JR.Induction of decision trees[J].Machine learning,1986,1(1):81-106

[3]Quinlan JR.C4.5: programs for machine learning[M].Elsevier,2014

[4]Breiman L,Friedman J,Stone C J,et al.Classification and Regression Trees[M].CRC press,1984

[5]Cortes C,Vapnik V.Support vector machine[J].Machine learning,1995,20(3):273-97

[6]Zhou ZH.Ensemble methods: foundations and algorithms[M].CRC press,2012

[7]Breiman L.Bagging predictors[J].Machine learning,1996,24(2):123-40

[8]Freund Y,Schapire RE.A desicion-theoretic generalization of on-line learning and an application to boosting[C]//In European conference on computational learning theory,1995:23-37

[9]Breiman L.Random forests[J].Machine learning,2001,45(1):5-32

[10]Kwok SW,Carter C.Multiple decision trees[EB/OL].[2018-01-31].https://arxiv.org/abs/1304.2363

[11]Ho TK.The random subspace method for constructing decision forests[J].IEEE transactions on pattern analysis and machine intelligence,1998,20(8):832-44

[12]Acharjee A,Kloosterman B,Visser RG,Maliepaard C.Integration of multi-omics data for prediction of phenotypic traits using random forest[J].BMC bioinformatics,2016,17(5):180

[13]Svetnik V,Liaw A,Tong C,et al.Random forest: a classification and regression tool for compound classification and QSAR modeling[J].Journal of chemical information and computer sciences,2003,43(6):1947-58

[14]Prasad AM,Iverson LR,Liaw A.Newer classification and regression tree techniques: bagging and random forests for ecological prediction[J].Ecosystems,2006,9(2):181-99

[15]Cutler DR,Edwards TC,Beard KH,et al.Random forests for classification in ecology[J].Ecology,2007,88(11):2783-92

[16]Shotton J,Sharp T,Kipman A,et al.Real-time human pose recognition in parts from single depth images[J].Communications of the ACM,2013,56(1):116-24

[17]Lindner C,Bromiley PA,Ionita MC,et al.Robust and accurate shape model matching using random forest regression-voting[J].IEEE transactions on pattern analysis and machine intelligence,2015,37(9):1862-74[18]Baumann T.Decision tree usage for incremental parametric speech synthesis[C]//IEEE International Conference in Acoustics,Speech and Signal Processing.Italy:IEEE,2014:3819-3823

[19]Xiong C,Johnson D,Xu R,et al.Random forests for metric learning with implicit pairwise position dependence[C]//In ACM SIGKDD international conference on Knowledge discovery and data mining,2012:958-966

[20]Verikas A,Gelzinis A,Bacauskiene M.Mining data with random forests: A survey and results of new tests[J].Pattern Recognition,2011,44(2):330-49

[21]Wang Y,Xia ST.Unifying attribute splitting criteria of decision trees by Tsallis entropy[C]//In Acoustics,Speech and Signal Processing,IEEE International Conference,2017:2507-2511

[22]Buntine W,Niblett T.A further comparison of splitting rules for decision-tree induction[J].Machine Learning,1992,8(1):75-85

[23]Liu WZ,White AP.The importance of attribute selection measures in decision tree induction[J].Machine Learning,1994,15(1):25-41

[24]Nowozin S.Improved information gain estimates for decision tree induction[EB/OL].[2018-01-31].https://arxiv.org/abs/1206.4620

[25]Serrurier M,Prade H.Entropy evaluation based on confidence intervals of frequency estimates: Application to the learning of decision trees[C]//In International Conference on Machine Learning,2015:1576-1584

[26]Esposito F,Malerba D,Semeraro G,et al.A comparative analysis of methods for pruning decision trees[J].IEEE transactions on pattern analysis and machine intelligence,1997,19(5):476-91

[27]Wold S,Esbensen K,Geladi P.Principal component analysis[J].Chemometrics and intelligent laboratory systems,1987,2(1-3):37-52

[28]Rodriguez JJ,Kuncheva LI,Alonso CJ.Rotation forest:A new classifier ensemble method[J].IEEE transactions on pattern analysis and machine intelligence,2006,28(10):1619-30

[29]Skurichina M,Duin RP.Combining Feature Subsets in Feature Selection[J].Multiple classifier systems,2005,3541:165-75

[30]Mart'?nez M,Kak A C.Pca versus lda[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2001,23(2):228–233

[31]Guyon I,Elisseeff A.An introduction to variable and feature selection[J].Journal of machine learning research,2003,3(3):1157-82

[32]Ye Y,Wu Q,Huang J Z,et al.Stratified sampling for feature subspace selection in random forests for high dimensional data[J].Pattern Recognition,2013,46(3):769–787

[33]Nguyen T T,Zhao H,Huang J Z,et al.A new feature sampling method in random forests for predicting high- dimensional data[C]//In Advances in Knowledge Discovery and Data Mining,2015:459–470

[34]Wang Y,Xia S T.A novel feature subspace selection method in random forests for high dimensional data[C]//In International joint conference on neural networks,2016:4383–4389

[35]Amaratunga D,Cabrera J,Lee Y S.Enriched random forests[J].Bioinformatics,2008,24(18):2010–2014

[36]Biau G,Devroye L,Lugosi G.Consistency of random forests and other averaging classifiers[J].Journal of Machine Learning Research,2008,9(9):2015-2033

[37]Biau G.Analysis of a random forests model[J].Journal of Machine Learning Research,2012,13(4):1063-1095[38]Denil M,Matheson D,De Freitas N.Narrowing the gap: Random forests in theory and in practice[C]//In International conference on machine learning,2014

[39]Wang Y,Tang Q,Xia ST,et al.Bernoulli Random Forests:Closing the Gap between Theoretical Consistency and Empirical Soundness[C]//In International joint conference on artificial intelligence,2016:2167-2173

[40]Rota Bulo S,Kontschieder P.Neural decision forests for semantic image labelling[C]//In IEEE Conference on Computer Vision and Pattern Recognition,2014:81-88

[41]Kontschieder P,Fiterau M,Criminisi A,et al.Deep neural decision forests[C]//In IEEE International Conference on Computer Vision,2015:1467-1475

[42]Zhou ZH,Feng J.Deep forest:Towards an alternative to deep neural networks[EB/OL].[2018-01-31].https://arxiv.org/abs/1702.08835