機器器學習算法系列列（1）：随機森林

随機森林原理

顧名思義，是用随機的方式建立一個森林，森林裡面有很多的決策樹組成，随機森林的每一棵決 策樹之間是沒有關聯的。在得到森林之後，當有一個新的輸入樣本進入的時候，就讓森林中的每 一棵決策樹分别進行一下判斷，看看這個樣本應該屬于哪一類（對于分類算法），然後看看哪一 類被選擇最多，就預測這個樣本為那一類。

我們可以這樣⽐比喻随機森林算法：每一棵決策樹就是一個精通于某一個窄領域的專家（因為我們 從M個特征中選擇m個讓每一棵決策樹進行行學習），這樣在随機森林中就有了了很多個精通不不同領 域的專家，對一個新的問題（新的輸⼊入資料），可以用不不同的角度去看待它，最終由各個專家， 投票得到結果。

随機森林算法有很多優點：

在資料集上表現良好

在目前的很多資料集上，相對其他算法有着很⼤大的優勢

它能夠處理理很高次元（feature很多）的資料，并且不不用做特征選擇

在訓練完後它能夠給出哪些feature比較重要

在建立随機森林的時候，對generlization error使用的是無偏估計

訓練速度快

在訓練過程中，能夠檢測到feature間的互相影響

容易易做成并行行化方法

實作比較簡單

随機森林的生成

2.1 生成步驟

步驟如下：

1）如果訓練集大小為 N，對于每棵樹而言，随機且有放回地從訓練集中抽取N個訓練樣本（bootstrap抽樣方法），作為該樹的訓練集；每棵樹的訓練集都是不不同的，但裡面包含重 複的訓練樣本

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

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

2.2 影響分類效果的參數

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

1）森林中任意兩棵樹的相關性：相關性越大，錯誤率越大

2）森林中每棵樹的分類能力：每棵樹的分類能力越強，整個森林的錯誤率越低

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

2.3 袋外誤差率

如何選擇最優的特征個數m，要解決這個問題，我們主要依據計算得到的袋外錯誤率oob error（out-of-bag error）。

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

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

袋外錯誤率（oob error）計算⽅方式如下：

1）對每個樣本計算它作為oob樣本的樹對它的分類情況

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

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

随機采樣與完全分裂

在建立每一棵決策樹的過程中，有兩點需要注意，分别是采樣與完全分裂。

3.1 随機采樣

首先是兩個随機采樣的過程，random forest對輸入的資料要進行、列的采樣。對于行采樣，采用有放回的方式，也就是在采樣得到的樣本集合中，可能有重複的樣本。假設輸入樣本為N個，那麼采樣的樣本也為N個。這樣使得在訓練的時候，每一棵樹的輸入樣本都不是全部的樣本，使得相對不不容易易出現over-fitting。然後進⾏列采樣，從M個feature中，選擇m個(m << M)。

• 有放回抽樣的解釋

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

• 對Bagging的改進

  随機森林對Bagging的改進就在于随機采用的不同，即以下兩點：

  1）Random forest是選與輸入樣本的數目相同多的次數（可能一個樣本會被選取多次，同時 也會造成一些樣本不會被選取到），而bagging一般選取比輸入樣本的數目少的樣本；

  2）bagging是用全部特征來得到分類器器，而Random forest是需要從全部特征中選取其中的一部分來訓練得到分類器器；一般Random forest效果比bagging效果好！

3.2 完全分裂

之後就是對采樣之後的資料使用完全分裂的方式建立出決策樹，這樣決策樹的某一個葉子節點要麼是無法繼續分裂的，要麼裡面的所有樣本的都是指向的同一個分類。一般很多的決策樹算法都一個重要的步驟 - 剪枝，但是這里不這樣幹，由于之前的兩個随機采樣的過程保證 了随機性，是以就算不剪枝，也不會出現over-fitting。 按這種算法得到的随機森林中的每一 棵都是很弱的，但是組合起來就很厲害了。

随機森林的變體

也可以使用SVM、Logistic回歸等其他分類器，習慣上這些分類器器組成的“總分類器器”，仍然叫 做随機森林。