隨機森林

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

這個術語是 1995 年由貝爾實驗室的何天琴所提出的**隨機決策森林**（**random decision forests**）而來的。

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

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

## 歷史

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

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

## 演算法

### 預備：決策樹學習

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

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

### Bagging

隨機森林訓練演算法把 bagging 的一般技術應用到樹學習中。給定訓練集 X = x1, ..., xn 和目標 Y = y1, ..., yn，bagging 方法重複（_B_ 次）從訓練集中有放回地採樣，然後在這些樣本上訓練樹模型：

　
: For b = 1, ..., B:

1. Sample, with replacement, n training examples from X, Y; call these Xb, Yb.
2. Train a classification or regression tree fb on Xb, Yb.

在訓練結束之後，對未知樣本 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 抽樣導致的樹的相關性：如果有一些特徵預測目標值的能力很強，那麼這些特徵就會被許多樹所選擇，這樣就會導致樹的強相關性。何天琴分析了不同條件下 bagging 和隨機子空間投影對精度提高的影響。

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

### 極限樹

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

## 性質

### 特徵的重要性

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

度量資料集 ${\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._ 給出。

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

### 與最近鄰演算法的關係

Lin 和 Jeon 在 2002 年指出了隨機森林演算法和 K - 近鄰演算法 (k-NN) 的關係。 事實證明，這兩種演算法都可以被看作是所謂的「加權鄰居的方案」。這些在資料集 $\{(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 演算法，如果 xi 是距離 x' 最近的 k 個點之一，則 $W(x_{i},x')={\frac {1}{k}}$ ，否則為 0。
* 對於樹，如果 xi 與 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' 的鄰居。

## 基於隨機森林的非監督學習

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

## 學習演算法

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

1. 用 _N_ 來表示訓練用例（樣本）的個數，_M_ 表示特徵數目。
2. 輸入特徵數目 _m_，用於確定決策樹上一個節點的決策結果；其中 _m_ 應遠小於 _M_。
3. 從 _N_ 個訓練用例（樣本）中以有放回抽樣的方式，取樣 _N_ 次，形成一個訓練集（即 bootstrap 取樣），並用未抽到的用例（樣本）作預測，評估其誤差。
4. 對於每一個節點，隨機選擇 _m_ 個特徵，決策樹上每個節點的決定都是基於這些特徵確定的。根據這 m 個特徵，計算其最佳的分裂方式。
5. 每棵樹都會完整成長而不會剪枝（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.

## 參閱

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

## 參考文獻

## 外部連結

* （英文）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）