機器學習-随機森林

• 随機森林的定義
• 随機森林的特點
• 随機森林的生成
• • 1）每棵樹随機抽取訓練樣本
  • • 為什麼要随機抽樣訓練集？
    • 為什麼要有放回地抽樣？
  • 2）每棵樹随機選擇訓練特征
  • 3）每棵樹都盡最大程度的生長，并且沒有剪枝過程。
  • • 随機森林分類效果（錯誤率）與兩個因素有關：
• 袋外錯誤率（oob error）

随機森林的定義

随機森林就是通過內建學習的思想将多棵樹內建的一種算法，它的基本單元是決策樹，而它的本質屬于機器學習的一大分支——內建學習（Ensemble Learning）方法。

其實從直覺角度來解釋，每棵決策樹都是一個分類器（假設現在針對的是分類問題），那麼對于一個輸入樣本，N棵樹會有N個分類結果。而随機森林內建了所有的分類投票結果，将投票次數最多的類别指定為最終的輸出，這就是一種最簡單的 Bagging 思想。

随機森林的特點

• 在目前所有算法中，具有極好的準确率
• 能夠有效地運作在大資料集上
• 能夠處理具有高維特征的輸入樣本，而且不需要降維
• 能夠評估各個特征在分類問題上的重要性
• 在生成過程中，能夠擷取到内部生成誤差的一種無偏估計
• 對于預設值問題也能夠獲得很好得結果

随機森林的生成

随機森林中有許多的分類樹。要将一個輸入樣本進行分類，需要将輸入樣本輸入到每棵樹中進行分類。

打個形象的比喻：森林中召開會議，讨論某個動物到底是老鼠還是松鼠，每棵樹都要獨立地發表自己對這個問題的看法，也就是每棵樹都要投票。該動物到底是老鼠還是松鼠，要依據投票情況來确定，獲得票數最多的類别就是森林的分類結果。森林中的每棵樹都是獨立的，99.9%不相關的樹做出的預測結果涵蓋所有的情況，這些預測結果将會彼此抵消。少數優秀的樹的預測結果将會超脫于芸芸“噪音”，做出一個好的預測。将若幹個弱分類器的分類結果進行投票選擇，進而組成一個強分類器，這就是随機森林bagging的思想（關于bagging的一個有必要提及的問題：bagging的代價是不用單棵決策樹來做預測，具體哪個變量起到重要作用變得未知，是以bagging改進了預測準确率但損失了解釋性。）。下圖可以形象地描述這個情況：

有了樹我們就可以分類了，但是森林中的每棵樹是怎麼生成的呢？

每棵樹的按照如下規則生成：

1）每棵樹随機抽取訓練樣本

如果訓練集大小為N，對于每棵樹而言，随機且有放回地從訓練集中的抽取N個訓練樣本（這種采樣方式稱為bootstrap sample方法），作為該樹的訓練集；

從這裡我們可以知道：每棵樹的訓練集都是不同的，而且裡面包含重複的訓練樣本（了解這點很重要）。

為什麼要随機抽樣訓練集？

如果不進行随機抽樣，每棵樹的訓練集都一樣，那麼最終訓練出的樹分類結果也是完全一樣的，這樣的話完全沒有bagging的必要；

為什麼要有放回地抽樣？

如果不是有放回的抽樣，那麼每棵樹的訓練樣本都是不同的，都是沒有交集的，這樣每棵樹都是"有偏的"，都是絕對"片面的"（當然這樣說可能不對），也就是說每棵樹訓練出來都是有很大的差異的；而随機森林最後分類取決于多棵樹（弱分類器）的投票表決，這種表決應該是"求同"，是以使用完全不同的訓練集來訓練每棵樹這樣對最終分類結果是沒有幫助的，這樣無異于是"盲人摸象"。

2）每棵樹随機選擇訓練特征

如果每個樣本的特征次元為M，指定一個常數m<<M，随機地從M個特征中選取m個特征子集，每次樹進行分裂時，從這m個特征中選擇最優的；

3）每棵樹都盡最大程度的生長，并且沒有剪枝過程。

一開始我們提到的随機森林中的“随機”就是指的這裡的兩個随機性。兩個随機性的引入對随機森林的分類性能至關重要。由于它們的引入，使得随機森林不容易陷入過拟合，并且具有很好得抗噪能力（比如：對預設值不敏感）。

随機森林分類效果（錯誤率）與兩個因素有關：

• 森林中任意兩棵樹的相關性：相關性越大，錯誤率越大；
• 森林中每棵樹的分類能力：每棵樹的分類能力越強，整個森林的錯誤率越低。

減小特征選擇個數m，樹的相關性和分類能力也會相應的降低；增大m，兩者也會随之增大。是以關鍵問題是如何選擇最優的m（或者是範圍），這也是随機森林唯一的一個參數。

袋外錯誤率（oob error）

上面我們提到，建構随機森林的關鍵問題就是如何選擇最優的m，要解決這個問題主要依據計算袋外錯誤率oob error（out-of-bag error）。

随機森林有一個重要的優點就是，沒有必要對它進行交叉驗證或者用一個獨立的測試集來獲得誤差的一個無偏估計。它可以在内部進行評估，也就是說在生成的過程中就可以對誤差建立一個無偏估計。

我們知道，在建構每棵樹時，我們對訓練集使用了不同的bootstrap sample（随機且有放回地抽取）。是以對于每棵樹而言（假設對于第k棵樹），大約有1/3的訓練執行個體沒有參與第k棵樹的生成，它們稱為第k棵樹的oob樣本。

而這樣的采樣特點就允許我們進行oob估計，它的計算方式如下：

（note：以樣本為機關）

1）對每個樣本，計算它作為oob樣本的樹對它的分類情況（約1/3的樹）；

2）然後以簡單多數投票作為該樣本的分類結果；

3）最後用誤分個數占樣本總數的比率作為随機森林的oob誤分率。
           

oob誤分率是随機森林泛化誤差的一個無偏估計，它的結果近似于需要大量計算的k折交叉驗證。