論文筆記 ─ 隨機森林

隨機森林(Random Forest):

※特點：

1. 用隨機的方式建立一個森林
2. 森林由很多的決策樹組成
3. 決策樹之間是沒有關聯的
4. 類似分類演算法
5. 在得到森林之後，當有一個新的輸入樣本進入的時候，就讓森林中的每一棵決策樹分別進行一下判斷，看看這個樣本應該屬於哪一類，然後看看哪一類被選擇最多，就預測這個樣本為那一類。

※建樹：

    在建立每一棵決策樹的過程中，有兩點需要注意 - 採樣與完全分裂。
    首先是兩個隨機採樣的過程，random forest對輸入的資料要進行行、列的採樣。對於行採樣，採用有放回的方式，也就是在採樣得到的樣本集合中，可能有重複的樣本。假設輸入樣本為N個，那麼採樣的樣本也為N個。這樣使得在訓練的時候，每一棵樹的輸入樣本都不是全部的樣本，使得相對不容易出現over-fitting。
     然後進行列採樣，從M個feature中，選擇m個(m << M)。之後就是對採樣之後的資料使用完全分裂的方式建立出決策樹，這樣決策樹的某一個葉子節點要麼是無法繼續分裂的，要麼裡面的所有樣本的都是指向的同一個分類。
一般很多的決策樹演算法都一個重要的步驟 - 剪枝，但是這裡不這樣幹，由於之前的兩個隨機採樣的過程保證了隨機性，所以就算不剪枝，也不會出現over-fitting。

（1）隨機採樣

首先是兩個隨機採樣的過程，random forest對輸入的資料要進行行、列的採樣。

對於行採樣，採用有放回的方式，也就是在採樣得到的樣本集合中，可能有重複的樣本。假設輸入樣本為N個，那麼採樣的樣本也為N個，這選擇好了的N個樣本用來訓練一個決策樹，作為決策樹根節點處的樣本，同時使得在訓練的時候，每一棵樹的輸入樣本都不是全部的樣本，使得相對不容易出現over-fitting。

對於列採樣，從M個feature中，選擇m個(m << M)，即：當每個樣本有M個屬性時，在決策樹的每個節點需要分裂時，隨機從這M個屬性中選取出m個屬性，滿足條件m << M。

（2）完全分裂

對採樣之後的資料使用完全分裂的方式建立出決策樹，這樣決策樹的某一個葉子節點要麼是無法繼續分裂的，要麼裡面的所有樣本的都是指向的同一個分類。分裂的辦法是：採用上面說的列採樣的過程從這m個屬性中採用某種策略（比如說資訊增益）來選擇1個屬性作為該節點的分裂屬性。

決策樹形成過程中每個節點都要按完全分裂的方式來分裂，一直到不能夠再分裂為止（如果下一次該節點選出來的那一個屬性是剛剛其父節點分裂時用過的屬性，則該節點已經達到了葉子節點，無須繼續分裂了）。

※優點：

1.         在資料集上表現良好
2.     在當前的很多資料集上，相對其他演算法有著很大的優勢
3.     它能夠處理很高維度（feature很多）的資料，並且不用做特徵選擇
4.     在訓練完後，它能夠給出哪些feature比較重要
5.     在創建隨機森林的時候，對generlization error使用的是無偏估計
6.     訓練速度快
7.     在訓練過程中，能夠檢測到feature間的互相影響
8.     容易做成並行化方法
9.     實現比較簡單

(來源：http://www.cnblogs.com/LeftNotEasy/archive/2011/03/07/random-forest-and-gbdt.html)
random forst 講解影片：https://www.youtube.com/watch?v=NgYj_cSIJeA
decision tree ：https://www.youtube.com/watch?v=-dCtJjlEEgM

影片How Random Forest algorithm workshttps://www.youtube.com/watch?v=loNcrMjYh64