隨機森林再複習

這裡只是準備簡單談談基礎的內容，主要參考一下別人的文章，對於隨機森林與GBDT，有兩個地方比較重要，首先是information gain，其次是決策樹。這裡特別推薦Andrew Moore大牛的Decision Trees Tutorial，與Information Gain Tutorial。Moore的Data Mining Tutorial系列非常贊，看懂了上面說的兩個內容之後的文章才能繼續讀下去。

決策樹實際上是將空間用超平面進行劃分的一種方法，每次分割的時候，都將當前的空間一分為二，比如說下面的決策樹：

就是將空間劃分成下面的樣子：n

這樣使得每一個葉子節點都是在空間中的一個不相交的區域，在進行決策的時候，會根據輸入樣本每一維feature的值，一步一步往下，最後使得樣本落入N個區域中的一個（假設有N個葉子節點）

隨機森林(Random Forest):

隨機森林是一個最近比較火的演算法，它有很多的優點：

在數據集上表現良好

在當前的很多數據集上，相對其他演算法有著很大的優勢

它能夠處理很高維度（feature很多）的數據，並且不用做特徵選擇

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

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

訓練速度快

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

容易做成並行化方法

實現比較簡單

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

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

按這種演算法得到的隨機森林中的每一棵都是很弱的，但是大家組合起來就很厲害了。我覺得可以這樣比喻隨機森林演算法：每一棵決策樹就是一個精通於某一個窄領域 的專家（因為我們從M個feature中選擇m讓每一棵決策樹進行學習），這樣在隨機森林中就有了很多個精通不同領域的專家，對一個新的問題（新的輸入數 據），可以用不同的角度去看待它，最終由各個專家，投票得到結果。

隨機森林的過程請參考Mahout的random forest 。這個頁面上寫的比較清楚了，其中可能不明白的就是Information Gain，可以看看之前推薦過的文章

推薦閱讀：