隨機森林

在機器學習中，隨機森林是一個包含多個決策樹的分類器，並且其輸出的類別是由個別樹輸出的類別的眾數而定。

這個術語是1995年^[1]由貝爾實驗室的何天琴（英語：Tin Kam Ho）所提出的隨機決策森林（random decision forests）而來的。^[2]^[3]

然後Leo Breiman（英語：Leo Breiman）和Adele Cutler（英語：Adele Cutler）發展出推論出隨機森林的演算法。而"Random Forests"是他們的商標。

這個方法則是結合Breimans的"Bootstrap aggregating"想法和Ho的"random subspace method"以建造決策樹的集合。

歷史[編輯]

隨機森林的引入最初是由華裔美國人何天琴（英語：Tin Kam Ho）於1995年^[1]先提出的。^[2]然後隨機森林由Leo Breiman於2001年在一篇論文中提出的。^[4]這篇文章描述了一種結合隨機節點優化和bagging，利用類CART過程構建不相關樹的森林的方法。此外，本文還結合了一些已知的、新穎的、構成了現代隨機森林實踐的基礎成分，特別是

使用out-of-bag誤差來代替泛化誤差
通過排列度量變量的重要性

算法[編輯]

預備：決策樹學習[編輯]

決策樹是機器學習的常用方法。 Hastie等說：「樹學習是如今最能滿足於數據挖掘的方法，因為它在特徵值的縮放和其他各種轉換下保持不變，對無關特徵是穩健的，而且能生成可被檢查的模型。然而，它通常並不準確。」^[5]

特別的，生長很深的樹容易學習到高度不規則的模式，即過學習，在訓練集上具有低偏差和高變異數的特點。隨機森林是平均多個深決策樹以降低變異數的一種方法，其中，決策樹是在一個數據集上的不同部分進行訓練的。^[5]這是以偏差的小幅增加和一些可解釋性的喪失為代價的，但是在最終的模型中通常會大大提高性能。

Bagging[編輯]

隨機森林訓練算法把bagging的一般技術應用到樹學習中。給定訓練集 $X=x_{1},\dots ,x_{n}$ 和目標 $Y=y_{1},\dots ,y_{n}$ ，bagging方法重複（ $B$ 次）從訓練集中有放回地採樣，然後在這些樣本上訓練樹模型：

For

b

= 1, ...,

B

:

Sample, with replacement, $n$ training examples from $X$ , $Y$ ; call these $X b$ , $Y b$ .
Train a classification or regression tree $f b$ on $X b$ , $Y b$ .

在訓練結束之後，對未知樣本x的預測可以通過對x上所有單個回歸樹的預測求平均來實現：

{\hat {f}}={\frac {1}{B}}\sum _{b=1}^{B}f_{b}(x')

或者在分類任務中選擇多數投票的類別。

這種bagging方法在不增加偏置的情況下降低了方差，從而帶來了更好的性能。這意味着，即使單個樹模型的預測對訓練集的噪聲非常敏感，但對於多個樹模型，只要這些樹並不相關，這種情況就不會出現。簡單地在同一個數據集上訓練多個樹模型會產生強相關的樹模型（甚至是完全相同的樹模型）。Bootstrap抽樣是一種通過產生不同訓練集從而降低樹模型之間關聯性的方法。

此外， $x'$ 上所有單個回歸樹的預測的標準差可以作為預測的不確定性的估計：

\sigma ={\sqrt {\frac {\sum _{b=1}^{B}(f_{b}(x')-{\hat {f}})^{2}}{B-1}}}.

樣本或者樹的數量B是一個自由參數。通常使用幾百到幾千棵樹，這取決於訓練集的大小和性質。使用交叉驗證，或者透過觀察out-of-bag誤差（那些不包含 $xᵢ$ 的抽樣集合在樣本 $xᵢ$ 的平均預測誤差），可以找到最優的B值。當一些樹訓練到一定程度之後，訓練集和測試集的誤差開始趨於平穩。

從 bagging 到隨機森林[編輯]

上面的過程描述了樹的原始的 bagging 算法。隨機森林與這個通用的方案只有一點不同:它使用一種改進的學習算法，在學習過程中的每次候選分裂中選擇特徵的隨機子集。這個過程有時又被稱為「特徵 bagging」。這樣做的原因是 bootstrap 抽樣導致的樹的相關性：如果有一些特徵預測目標值的能力很強，那麼這些特徵就會被許多樹所選擇，這樣就會導致樹的強相關性。何天琴（英語：Tin Kam Ho）分析了不同條件下 bagging 和隨機子空間投影對精度提高的影響。^[3]

典型地，對於一個包含 $p$ 個特徵的分類問題，可以在每次劃分時使用 ${\sqrt {p}}$ 個特徵^[5]^:592。對於回歸問題，作者推薦 $p/3$ 但不少於 5 個特徵^[5]^:592。

極限樹[編輯]

再加上一個隨機化步驟，就會得到極限隨機樹（extremely randomized trees），即極限樹。與普通的隨機森林相同，他們都是單個樹的集成，但也有不同：首先，每棵樹都使用整個學習樣本進行了訓練，其次，自上而下的劃分是隨機的。它並不計算每個特徵的最優劃分點（例如，基於信息熵或者基尼不純度），而是隨機選擇劃分點。該值是從特徵經驗範圍內均勻隨機選取的。在所有隨機的劃分點中，選擇其中分數最高的作為結點的劃分點。與普通的隨機森林相似，可以指定每個節點要選擇的特徵的個數。該參數的默認值，對於分類問題，是 ${\sqrt {n}}$ ，對於回歸問題，是 $n$ ，其中 $n$ 是模型的特徵個數。^[6]

性質[編輯]

特徵的重要性[編輯]

隨機森林天然可用來對回歸或分類問題中變量的重要性進行排序。下面的技術來自Breiman的論文，R語言包randomForest包含它的實現。^[7]

度量數據集 ${\mathcal {D}}_{n}=\{(X_{i},Y_{i})\}_{i=1}^{n}$ 的特徵重要性的第一步是，使用訓練集訓練一個隨機森林模型。在訓練過程中記錄下每個數據點的out-of-bag誤差，然後在整個森林上進行平均。

為了度量第 $j$ 個特徵的重要性，第 $j$ 個特徵的值在訓練數據中被打亂，並重新計算打亂後的數據的out-of-bag誤差。則第 $j$ 個特徵的重要性分數可以通過計算打亂前後的out-of-bag誤差的差值的平均來得到，這個分數通過計算這些差值的標準差進行標準化。

產生更大分數的特徵比小分數的特徵更重要。這種特徵重要性的度量方法的統計定義由Zhu et al.^[8]給出。

這種度量方法也有一些缺陷。對於包含不同取值個數的類別特徵，隨機森林更偏向於那些取值個數較多的特徵，partial permutations^[9]^[10]、growing unbiased trees^[11]^[12]可以用來解決這個問題。如果數據包含一些相互關聯的特徵組，那麼更小的組更容易被選擇。^[13]

與最近鄰算法的關係[編輯]

Lin和Jeon在2002年指出了隨機森林算法和K-近鄰算法( $k$ -NN)的關係。^[14] 事實證明，這兩種算法都可以被看作是所謂的「加權鄰居的方案」。這些在數據集 $\{(x_{i},y_{i})\}_{i=1}^{n}$ 上訓練的模型通過查看一個點的鄰居來計算一個新點 $x'$ 的預測值 ${\hat {y}}$ ，並且使用權重函數 $W$ 對這些鄰居進行加權:

{\hat {y}}=\sum _{i=1}^{n}W(x_{i},x')\,y_{i}.

其中， $W(x_{i},x')$ 是第 $i$ 個點在同一棵樹中相對於新的數據點 $x'$ 的非負權重。對於任一特定的點 $x'$ ， $x_{i}$ 的權重的和必須為1。權重函數設定如下：

對於 $k$ -NN算法，如果 $x i$ 是距離 $x'$ 最近的 $k$ 個點之一，則 $W(x_{i},x')={\frac {1}{k}}$ ，否則為0。
對於樹，如果 $x i$ 與 $x'$ 屬於同一個包含 $k'$ 個點的葉結點，則 $W(x_{i},x')={\frac {1}{k'}}$ ，否則為0。

因為森林平均了 $m$ 棵樹的預測，且這些樹具有獨立的權重函數 $W_{j}$ ，故森林的預測值是：

{\hat {y}}={\frac {1}{m}}\sum _{j=1}^{m}\sum _{i=1}^{n}W_{j}(x_{i},x')\,y_{i}=\sum _{i=1}^{n}\left({\frac {1}{m}}\sum _{j=1}^{m}W_{j}(x_{i},x')\right)\,y_{i}.

上式表明了整個森林也採用了加權的鄰居方案，其中的權重是各個樹的平均。在這裡， $x'$ 的鄰居是那些在任一樹中屬於同一個葉節點的點 $x_{i}$ 。只要 $x_{i}$ 與 $x'$ 在某棵樹中屬於同一個葉節點， $x_{i}$ 就是 $x'$ 的鄰居。

基於隨機森林的非監督學習[編輯]

作為構建的一部分，隨機森林預測器自然會導致觀測值之間的不相似性度量。還可以定義未標記數據之間的隨機森林差異度量：其思想是構造一個隨機森林預測器，將「觀測」數據與適當生成的合成數據區分開來。^[4]^[15] 觀察到的數據是原始的未標記數據，合成數據是從參考分布中提取的。隨機森林的不相似性度量之所以吸引人，是因為它能很好地處理混合變量類型，對輸入變量的單調變換是不敏感的，而且在存在異常值的情況下度量結果依然可靠。由於其固有變量的選擇，隨機森林不相似性很容易處理大量的半連續變量。

學習演算法[編輯]

根據下列演算法而建造每棵樹：

用 $N$ 來表示訓練用例（樣本）的個數， $M$ 表示特徵數目。
輸入特徵數目 $m$ ，用於確定決策樹上一個節點的決策結果；其中 $m$ 應遠小於 $M$ 。
從 $N$ 個訓練用例（樣本）中以有放回抽樣的方式，取樣 $N$ 次，形成一個訓練集（即bootstrap取樣），並用未抽到的用例（樣本）作預測，評估其誤差。
對於每一個節點，隨機選擇 $m$ 個特徵，決策樹上每個節點的決定都是基於這些特徵確定的。根據這 $m$ 個特徵，計算其最佳的分裂方式。
每棵樹都會完整成長而不會剪枝（Pruning，這有可能在建完一棵正常樹狀分類器後會被採用）。

優點[編輯]

隨機森林的優點有：

對於很多種資料，它可以產生高準確度的分類器。
它可以處理大量的輸入變數。
它可以在決定類別時，評估變數的重要性。
在建造森林時，它可以在內部對於一般化後的誤差產生不偏差的估計。
它包含一個好方法可以估計遺失的資料，並且，如果有很大一部分的資料遺失，仍可以維持準確度。
它提供一個實驗方法，可以去偵測variable interactions。
對於不平衡的分類資料集來說，它可以平衡誤差。
它計算各例中的親近度，對於數據挖掘、偵測離群點（outlier）和將資料視覺化非常有用。
使用上述。它可被延伸應用在未標記的資料上，這類資料通常是使用非監督式聚類。也可偵測偏離者和觀看資料。
學習過程是很快速的。

開源實現[編輯]

The Original RF （頁面存檔備份，存於網際網路檔案館） by Breiman and Cutler written in Fortran 77.
ALGLIB （頁面存檔備份，存於網際網路檔案館） contains a modification of the random forest in C#, C++, Pascal, VBA.
party （頁面存檔備份，存於網際網路檔案館） Implementation based on the conditional inference trees in R.
randomForest （頁面存檔備份，存於網際網路檔案館） for classification and regression in R.
Python implementation （頁面存檔備份，存於網際網路檔案館） with examples in scikit-learn.
Orange data mining suite includes random forest learner and can visualize the trained forest.
Matlab （頁面存檔備份，存於網際網路檔案館） implementation.
SQP （頁面存檔備份，存於網際網路檔案館） software uses random forest algorithm to predict the quality of survey questions, depending on formal and linguistic characteristics of the question.
Weka RandomForest （頁面存檔備份，存於網際網路檔案館） in Java library and GUI.
ranger （頁面存檔備份，存於網際網路檔案館） A C++ implementation of random forest for classification, regression, probability and survival. Includes interface for R.

參閱[編輯]

機器學習
提升方法 - 機器學習方法
決策樹學習 - 機器學習算法
集成學習 - 統計與機器學習技術
無母數統計
隨機化算法 - 將一定程度的隨機性作為其邏輯或程序的一部分的算法

參考文獻[編輯]

^ ^1.0 ^1.1 Tin Kam Ho. Random decision forests. Proceedings of 3rd International Conference on Document Analysis and Recognition (Montreal, Que., Canada: IEEE Comput. Soc. Press). 1995, 1: 278–282 [2020-03-04]. ISBN 978-0-8186-7128-9. doi:10.1109/ICDAR.1995.598994. （原始內容存檔於2021-03-03）.
^ ^2.0 ^2.1 Tin Kam Ho. The random subspace method for constructing decision forests. IEEE Transactions on Pattern Analysis and Machine Intelligence. Aug./1998, 20 (8): 832–844 [2020-03-04]. doi:10.1109/34.709601. （原始內容存檔於2021-03-08）. 請檢查|date=中的日期值 (幫助)
^ ^3.0 ^3.1 Ho, Tin Kam. A Data Complexity Analysis of Comparative Advantages of Decision Forest Constructors (PDF). Pattern Analysis and Applications. 2002: 102–112 [2019-02-16]. （原始內容 (PDF)存檔於2016-04-17）.
^ ^4.0 ^4.1 RandomForest2001 (PDF). [2019-07-26]. （原始內容 (PDF)存檔於2021-04-03）.
^ ^5.0 ^5.1 ^5.2 ^5.3 Template:ElemStatLearn
^ Geurts P, Ernst D, Wehenkel L. Extremely randomized trees (PDF). Machine Learning. 2006, 63: 3–42 [2019-02-16]. doi:10.1007/s10994-006-6226-1. （原始內容 (PDF)存檔於2017-10-31）.
^ Liaw A. Documentation for R package randomForest (PDF). 16 October 2012 [15 March 2013]. （原始內容 (PDF)存檔於2021-03-19）.
^ Zhu R, Zeng D, Kosorok MR. Reinforcement Learning Trees. Journal of the American Statistical Association. 2015, 110 (512): 1770–1784. PMC 4760114 . PMID 26903687. doi:10.1080/01621459.2015.1036994.
^ Deng,H.; Runger, G.; Tuv, E. Bias of importance measures for multi-valued attributes and solutions (PDF). Proceedings of the 21st International Conference on Artificial Neural Networks (ICANN): 293–300. 2011 [2019-02-16]. （原始內容 (PDF)存檔於2018-08-09）.
^ Altmann A, Toloşi L, Sander O, Lengauer T. Permutation importance: a corrected feature importance measure. Bioinformatics. May 2010, 26 (10): 1340–7 [2019-02-16]. PMID 20385727. doi:10.1093/bioinformatics/btq134. （原始內容存檔於2016-11-08）.
^ Strobl C, Boulesteix AL, Augustin T. Unbiased split selection for classification trees based on the Gini index (PDF). Computational Statistics & Data Analysis. 2007: 483–501 [2019-02-16]. （原始內容 (PDF)存檔於2020-11-12）.
^ Painsky A, Rosset S. Cross-Validated Variable Selection in Tree-Based Methods Improves Predictive Performance. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2017, 39 (11): 2142–2153. PMID 28114007. arXiv:1512.03444 . doi:10.1109/tpami.2016.2636831.
^ Tolosi L, Lengauer T. Classification with correlated features: unreliability of feature ranking and solutions. Bioinformatics. July 2011, 27 (14): 1986–94 [2019-02-16]. PMID 21576180. doi:10.1093/bioinformatics/btr300. （原始內容存檔於2015-08-31）.
^ Lin, Yi; Jeon, Yongho. Random forests and adaptive nearest neighbors (技術報告). Technical Report No. 1055. University of Wisconsin. 2002 [2019-02-16]. （原始內容存檔於2013-06-30）.
^ Shi, T., Horvath, S. Unsupervised Learning with Random Forest Predictors. Journal of Computational and Graphical Statistics. 2006, 15 (1): 118–138 . CiteSeerX 10.1.1.698.2365 . JSTOR 27594168. doi:10.1198/106186006X94072.

外部連結[編輯]

（英文）Ho, Tin Kam (1995). "Random Decision Forest". Proc. of the 3rd Int'l Conf. on Document Analysis and Recognition, Montreal, Canada, August 14-18, 1995, 278-282（Preceding Work）
（英文）Ho, Tin Kam (1998). "The Random Subspace Method for Constructing Decision Forests". IEEE Trans. on Pattern Analysis and Machine Intelligence 20 (8), 832-844（Preceding Work）
（英文）Deng, H; Runger, G; Tuv, Eugene (2011). Bias of importance measures for multi-valued attributes and solutions, Proceedings of the 21st International Conference on Artificial Neural Networks (ICANN2011)
（英文）Amit, Yali and Geman, Donald (1997) "Shape quantization and recognition with randomized trees". Neural Computation 9, 1545-1588. （頁面存檔備份，存於網際網路檔案館）（Preceding work）
（英文）Breiman, Leo "Looking Inside The Black Box". Wald Lecture II（Lecture）
（英文）Breiman, Leo (2001). "Random Forests". Machine Learning 45 (1), 5-32^{[永久失效連結]}（Original Article）
（英文）Random Forest classifier description（Site of Leo Breiman）
（英文）Liaw, Andy & Wiener, Matthew "Classification and Regression by randomForest" R News (2002) Vol. 2/3 p. 18 （頁面存檔備份，存於網際網路檔案館）（Discussion of the use of the random forest package for R）
（英文）Ho, Tin Kam (2002). "A Data Complexity Analysis of Comparative Advantages of Decision Forest Constructors". Pattern Analysis and Applications 5, p. 102-112 （頁面存檔備份，存於網際網路檔案館）（Comparison of bagging and random subspace method）

[:0-1] 1.0 ^1.1 Tin Kam Ho. Random decision forests. Proceedings of 3rd International Conference on Document Analysis and Recognition (Montreal, Que., Canada: IEEE Comput. Soc. Press). 1995, 1: 278–282 [2020-03-04]. ISBN 978-0-8186-7128-9. doi:10.1109/ICDAR.1995.598994. （原始內容存檔於2021-03-03）.

[:1-2] 2.0 ^2.1 Tin Kam Ho. The random subspace method for constructing decision forests. IEEE Transactions on Pattern Analysis and Machine Intelligence. Aug./1998, 20 (8): 832–844 [2020-03-04]. doi:10.1109/34.709601. （原始內容存檔於2021-03-08）. 請檢查|date=中的日期值 (幫助)

[ho2002-3] 3.0 ^3.1 Ho, Tin Kam. A Data Complexity Analysis of Comparative Advantages of Decision Forest Constructors (PDF). Pattern Analysis and Applications. 2002: 102–112 [2019-02-16]. （原始內容 (PDF)存檔於2016-04-17）.

[#1-4] 4.0 ^4.1 RandomForest2001 (PDF). [2019-07-26]. （原始內容 (PDF)存檔於2021-04-03）.

[elemstatlearn-5] 5.0 ^5.1 ^5.2 ^5.3 Template:ElemStatLearn

[6] Geurts P, Ernst D, Wehenkel L. Extremely randomized trees (PDF). Machine Learning. 2006, 63: 3–42 [2019-02-16]. doi:10.1007/s10994-006-6226-1. （原始內容 (PDF)存檔於2017-10-31）.

[rpackage-7] Liaw A. Documentation for R package randomForest (PDF). 16 October 2012 [15 March 2013]. （原始內容 (PDF)存檔於2021-03-19）.

[8] Zhu R, Zeng D, Kosorok MR. Reinforcement Learning Trees. Journal of the American Statistical Association. 2015, 110 (512): 1770–1784. PMC 4760114 . PMID 26903687. doi:10.1080/01621459.2015.1036994.

[9] Deng,H.; Runger, G.; Tuv, E. Bias of importance measures for multi-valued attributes and solutions (PDF). Proceedings of the 21st International Conference on Artificial Neural Networks (ICANN): 293–300. 2011 [2019-02-16]. （原始內容 (PDF)存檔於2018-08-09）.

[10] Altmann A, Toloşi L, Sander O, Lengauer T. Permutation importance: a corrected feature importance measure. Bioinformatics. May 2010, 26 (10): 1340–7 [2019-02-16]. PMID 20385727. doi:10.1093/bioinformatics/btq134. （原始內容存檔於2016-11-08）.

[11] Strobl C, Boulesteix AL, Augustin T. Unbiased split selection for classification trees based on the Gini index (PDF). Computational Statistics & Data Analysis. 2007: 483–501 [2019-02-16]. （原始內容 (PDF)存檔於2020-11-12）.

[12] Painsky A, Rosset S. Cross-Validated Variable Selection in Tree-Based Methods Improves Predictive Performance. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2017, 39 (11): 2142–2153. PMID 28114007. arXiv:1512.03444 . doi:10.1109/tpami.2016.2636831.

[13] Tolosi L, Lengauer T. Classification with correlated features: unreliability of feature ranking and solutions. Bioinformatics. July 2011, 27 (14): 1986–94 [2019-02-16]. PMID 21576180. doi:10.1093/bioinformatics/btr300. （原始內容存檔於2015-08-31）.

[linjeon02-14] Lin, Yi; Jeon, Yongho. Random forests and adaptive nearest neighbors (技術報告). Technical Report No. 1055. University of Wisconsin. 2002 [2019-02-16]. （原始內容存檔於2013-06-30）.

[15] Shi, T., Horvath, S. Unsupervised Learning with Random Forest Predictors. Journal of Computational and Graphical Statistics. 2006, 15 (1): 118–138 . CiteSeerX 10.1.1.698.2365 . JSTOR 27594168. doi:10.1198/106186006X94072.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]