ML筆記 | 零基礎學懂機器學習（六）

隨機森林（random Forest）

決策樹有許多優點：訓練時間複雜度低、預測過程比較快速、模型展示容易（容易將得到的決策樹做成圖片展示出來）等。但同時，單決策樹又有些不好的地方：容易過擬合。常用的減輕過擬合的方法有剪枝，但還是不夠。

a) 模型組合（例boosting，bagging等）與決策樹相關的演算法比較多，這些演算法最終生成N(可能會有幾百棵以上）棵樹，這樣可以大大的減少單決策樹帶來的毛病，有點類似於三個臭皮匠等於一個諸葛亮的做法，雖然這幾百棵決策樹中的每一棵都很簡單（相對於C4.5這種單決策樹來說），但是他們組合起來確是很強大。

Boostrap提供了一種組合方法的思想，就是將基分類器的訓練結果進行綜合分析，而其它的名稱如Bagging。Boosting是對組合方法的具體演繹。

組合方法總體上可以分為兩種。

第一種，通過處理訓練數據集。這種方法根據某種抽樣分布，通過對原始數據集進行再抽樣來得到多個數據集。抽樣分布決定了一個樣本被選作訓練的可能性大小，然後使用特定的學習演算法為每個訓練集建立一個分類器。Bagging袋裝和Boosting提升都是這樣的思想。Adaboost是Boosting當中比較出眾的一個演算法。

第二種，通過處理輸入特徵。在這種方法中，通過選擇輸入特徵的子集來形成每個訓練集。隨機森林就是通過處理輸入特徵的組合方法，並且它的基分類器限制成了決策樹。

具體方法參見http://blog.csdn.net/zjsghww/article/details/51591009

b) 在最近幾年的paper上，如iccv這種重量級的會議，iccv 09年（http://www.cvpapers.com/iccv2009.html）的裡面有不少的文章都是與Boosting與隨機森林相關的。模型組合+決策樹相關的演算法有兩種比較基本的形式 - 隨機森林與GBDT((Gradient Boost Decision Tree)，其他的比較新的模型組合+決策樹的演算法都是來自這兩種演算法的延伸。

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

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

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

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

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

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

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

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

　　為什麼要有放回地抽樣？

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

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

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

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

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

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

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

GBDT(gradient boost decision tree)

　　GBDT也是集成學習Boosting家族的成員，但是卻和傳統的Adaboost有很大的不同。在GBDT的迭代中，假設我們前一輪迭代得到的強學習器是ft?1(x), 損失函數是L(y,ft?1(x)), 我們本輪迭代的目標是找到一個CART回歸樹模型的弱學習器ht(x)，讓本輪的損失損失L(y,ft(x)=L(y,ft?1(x)+ht(x))最小。也就是說，本輪迭代找到決策樹，要讓樣本的損失盡量變得更小。

　　GBDT的思想可以用一個通俗的例子解釋，假如有個人30歲，我們首先用20歲去擬合，發現損失有10歲，這時我們用6歲去擬合剩下的損失，發現差距還有4歲，第三輪我們用3歲擬合剩下的差距，差距就只有一歲了。如果我們的迭代輪數還沒有完，可以繼續迭代下面，每一輪迭代，擬合的歲數誤差都會減小。

　　更多可以參考https://toutiao.io/posts/u52t61/preview及http://www.cnblogs.com/pinard/p/6140514.html