隨機森林

隨機森林指的是利用多棵樹對樣本進行訓練並預測的一種分類器。該分類器最早由Leo Breiman和Adele Cutler提出，並被註冊成了商標。

基本介紹

• 中文名：隨機森林
• 外文名：Random forest
• 領域：數理科學
• 提出時間：1995年
• 套用：機器學習
• 相關人物：Leo Breiman;Adele Cutler

定義

在機器學習中，隨機森林是一個包含多個決策樹的分類器， 並且其輸出的類別是由個別樹輸出的類別的眾數而定。 Leo Breiman和Adele Cutler發展出推論出隨機森林的算法。 而 "Random Forests" 是他們的商標。 這個術語是1995年由貝爾實驗室的Tin Kam Ho所提出的隨機決策森林（random decision forests）而來的。這個方法則是結合 Breimans 的 "Bootstrap aggregating" 想法和 Ho 的"random subspace method"以建造決策樹的集合。

學習算法

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

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

優點

隨機森林的優點有：

1）對於很多種資料，它可以產生高準確度的分類器；

2）它可以處理大量的輸入變數；

3）它可以在決定類別時，評估變數的重要性；

4）在建造森林時，它可以在內部對於一般化後的誤差產生不偏差的估計；

5）它包含一個好方法可以估計遺失的資料，並且，如果有很大一部分的資料遺失，仍可以維持準確度；

6）它提供一個實驗方法，可以去偵測variable interactions；

7）對於不平衡的分類資料集來說，它可以平衡誤差；

8）它計算各例中的親近度，對於數據挖掘、偵測離群點（outlier）和將資料視覺化非常有用；

9）使用上述。它可被延伸套用在未標記的資料上，這類資料通常是使用非監督式聚類。也可偵測偏離者和觀看資料；

10）學習過程是很快速的。

相關概念

1.分裂：在決策樹的訓練過程中，需要一次次的將訓練數據集分裂成兩個子數據集，這個過程就叫做分裂。

2.特徵：在分類問題中，輸入到分類器中的數據叫做特徵。以上面的股票漲跌預測問題為例，特徵就是前一天的交易量和收盤價。

3.待選特徵：在決策樹的構建過程中，需要按照一定的次序從全部的特徵中選取特徵。待選特徵就是在目前的步驟之前還沒有被選擇的特徵的集合。例如，全部的特徵是 ABCDE，第一步的時候，待選特徵就是ABCDE，第一步選擇了C，那么第二步的時候，待選特徵就是ABDE。

4.分裂特徵：接待選特徵的定義，每一次選取的特徵就是分裂特徵，例如，在上面的例子中，第一步的分裂特徵就是C。因為選出的這些特徵將數據集分成了一個個不相交的部分，所以叫它們分裂特徵。

決策樹構建

要說隨機森林，必須先講決策樹。決策樹是一種基本的分類器，一般是將特徵分為兩類（決策樹也可以用來回歸，不過本文中暫且不表）。構建好的決策樹呈樹形結構，可以認為是if-then規則的集合，主要優點是模型具有可讀性，分類速度快。

我們用選擇量化工具的過程形象的展示一下決策樹的構建。假設現在要選擇一個優秀的量化工具來幫助我們更好的炒股，怎么選呢？
第一步：看看工具提供的數據是不是非常全面，數據不全面就不用。
第二步：看看工具提供的API是不是好用，API不好用就不用。
第三步：看看工具的回測過程是不是靠譜，不靠譜的回測出來的策略也不敢用啊。
第四步：看看工具支不支持模擬交易，光回測只是能讓你判斷策略在歷史上有用沒有，正式運行前起碼需要一個模擬盤吧。

這樣，通過將“數據是否全面”，“API是否易用”，“回測是否靠譜”，“是否支持模擬交易”將市場上的量化工具貼上兩個標籤，“使用”和“不使用”。
上面就是一個決策樹的構建，邏輯可以用圖1表示：

圖1.決策樹構建1

在圖1中，綠顏色框中的“數據”“API”“回測”“模擬交易”就是這個決策樹中的特徵。如果特徵的順序不同，同樣的數據集構建出的決策樹也可能不同。特徵的順序分別是“數據”“API”“回測”“模擬交易”。如果我們選取特徵的順序分別是“數據”“模擬交易”“API”“回測”，那么構建的決策樹就完全不同了。

可以看到，決策樹的主要工作，就是選取特徵對數據集進行劃分，最後把數據貼上兩類不同的標籤。如何選取最好的特徵呢？還用上面選擇量化工具的例子：假設現在市場上有100個量化工具作為訓練數據集，這些量化工具已經被貼上了“可用”和“不可用”的標籤。

我們首先嘗試通過“API是否易用”將數據集分為兩類；發現有90個量化工具的API是好用的，10個量化工具的API是不好用的。而這90個量化工具中，被貼上“可以使用”標籤的占了40個，“不可以使用”標籤的占了50個，那么，通過“API是否易用”對於數據的分類效果並不是特別好。因為，給你一個新的量化工具，即使它的API是易用的，你還是不能很好貼上“使用”的標籤。

圖2.決策樹的構建2

再假設，同樣的100個量化工具，通過“是否支持模擬交易”可以將數據集分為兩類，其中一類有40個量化工具數據，這40個量化工具都支持模擬交易，都最終被貼上了“使用”的標籤，另一類有60個量化工具，都不支持模擬交易，也都最終被貼上了“不使用”的標籤。如果一個新的量化工具支持模擬交易，你就能判斷這個量化工具是可以使用。我們認為，通過“是否支持模擬交易”對於數據的分類效果就很好。

在現實套用中，數據集往往不能達到上述“是否支持模擬交易”的分類效果。所以我們用不同的準則衡量特徵的貢獻程度。主流準則的列舉3個：ID3算法（J. Ross Quinlan於1986年提出）採用信息增益最大的特徵；C4.5算法（J. Ross Quinlan於1993年提出）採用信息增益比選擇特徵；CART算法（Breiman等人於1984年提出）利用基尼指數最小化準則進行特徵選擇。

隨機森林構建

決策樹相當於一個大師，通過自己在數據集中學到的知識對於新的數據進行分類。但是俗話說得好，一個諸葛亮，玩不過三個臭皮匠。隨機森林就是希望構建多個臭皮匠，希望最終的分類效果能夠超過單個大師的一種算法。

那隨機森林具體如何構建呢？有兩個方面：數據的隨機性選取，以及待選特徵的隨機選取。

1.數據的隨機選取：

首先，從原始的數據集中採取有放回的抽樣，構造子數據集，子數據集的數據量是和原始數據集相同的。不同子數據集的元素可以重複，同一個子數據集中的元素也可以重複。第二，利用子數據集來構建子決策樹，將這個數據放到每個子決策樹中，每個子決策樹輸出一個結果。最後，如果有了新的數據需要通過隨機森林得到分類結果，就可以通過對子決策樹的判斷結果的投票，得到隨機森林的輸出結果了。如下圖，假設隨機森林中有3棵子決策樹，2棵子樹的分類結果是A類，1棵子樹的分類結果是B類，那么隨機森林的分類結果就是A類。

圖3.數據的隨機選取

2.待選特徵的隨機選取

與數據集的隨機選取類似，隨機森林中的子樹的每一個分裂過程並未用到所有的待選特徵，而是從所有的待選特徵中隨機選取一定的特徵，之後再在隨機選取的特徵中選取最優的特徵。這樣能夠使得隨機森林中的決策樹都能夠彼此不同，提升系統的多樣性，從而提升分類性能。

下圖中，藍色的方塊代表所有可以被選擇的特徵，也就是目前的待選特徵。黃色的方塊是分裂特徵。左邊是一棵決策樹的特徵選取過程，通過在待選特徵中選取最優的分裂特徵（別忘了前文提到的ID3算法，C4.5算法，CART算法等等），完成分裂。右邊是一個隨機森林中的子樹的特徵選取過程。

圖4.待選特徵的隨機選取