集成演算法與隨機森林

最新 06-25

上一次探討了決策樹的相關問題，這次跟大家說一下隨機森林。

其實說簡單點，隨機森林就是由若干棵樹組成的，但是組成的方法有很多種，所以在這裡首先要介紹下隨機森林的組成方法--集成演算法。

集成學習演算法本身不算一種單獨的機器學習演算法，而是通過構建並結合多個機器學習器來完成學習任務。可以說是集百家之所長，能在機器學習演算法中擁有較高的準確率，不足之處就是模型的訓練過程可能比較複雜，效率不是很高。

目前常見的集成學習演算法主要有2種：基於Bagging的演算法和基於Boosting的演算法，基於Bagging的代表演算法有隨機森林，而基於Boosting的代表演算法則有Adaboost、GBDT、XGBOOST等。

Bagging和Boosting都是將已有的分類或回歸演算法通過一定方式組合起來，形成一個性能更加強大的分類器，更準確的說這是一種分類演算法的組裝方法。即將弱分類器組裝成強分類器的方法。(我們要說的隨機森林就是Bagging的方法，也叫套袋法或者裝袋法)

Bagging演算法是bootstrapaggregating的縮寫，它主要對樣本訓練集合進行隨機化抽樣，通過反覆的抽樣訓練新的模型，最終在這些模型的基礎上取平均。

bagging的演算法過程如下：

從原始樣本集中使用Bootstraping方法隨機抽取n個訓練樣本，共進行k輪抽取，得到k個訓練集。（k個訓練集之間相互獨立，元素可以有重複）

對於k個訓練集，我們訓練k個模型（這k個模型可以根據具體問題而定，比如決策樹，knn等）

對於分類問題：由投票表決產生分類結果；對於回歸問題：由k個模型預測結果的均值作為最後預測結果。（所有模型的重要性相同）

bagging就是並聯的思想，如下圖：

Boosting（提升法）

boosting的演算法過程如下：

對於訓練集中的每個樣本建立權值wi，表示對每個樣本的關注度。當某個樣本被誤分類的概率很高時，需要加大對該樣本的權值。

進行迭代的過程中，每一步迭代都是一個弱分類器。我們需要用某種策略將其組合，作為最終模型。（例如AdaBoost給每個弱分類器一個權值，將其線性組合最為最終分類器。誤差越小的弱分類器，權值越大）

boosting就是串聯的思想，舉個例子：

比如實際一個人的最終的借款金額是10000元，我們根據一些變數去預測，

就是每一次根據預測誤差再去改善提升準確率

Bagging，Boosting的主要區別

樣本選擇上：Bagging採用的是Bootstrap隨機有放回抽樣；而Boosting每一輪的訓練集是不變的，改變的只是每一個樣本的權重。

樣本權重：Bagging使用的是均勻取樣，每個樣本權重相等；Boosting根據錯誤率調整樣本權重，錯誤率越大的樣本權重越大。

預測函數：Bagging所有的預測函數的權重相等；Boosting中誤差越小的預測函數其權重越大。

並行計算：Bagging各個預測函數可以並行生成；Boosting各個預測函數必須按順序迭代生成。

下面是將決策樹與這些演算法框架進行結合所得到的新的演算法：

1）Bagging+ 決策樹 =隨機森林

2）AdaBoost+ 決策樹 =提升樹

3）GradientBoosting + 決策樹 =GBDT

PS：集成演算法裡面還有一個比較厲害的就是Stacking模型，

Stacking:聚合多個分類或回歸模型，就是堆疊演算法，可以堆疊各種各樣的分類器(KNN,SVM,RF等等) ；

分兩個階段:第一階段得出各自結果，第二階段再用前一階段結果訓練

說白了就是用多種模型訓練，再把多種訓練的結果當作樣本再來訓練一遍。

這裡我們主要說隨機森林，所以不再過多的敘述。

隨機森林（Random Forests）

首先介紹下隨機森林：

隨機森林是一種重要的基於Bagging的集成學習方法，可以用來做分類、回歸等問題。

隨機森林由LeoBreiman（2001）提出，從原始訓練樣本集N中有放回地重複隨機抽取k個樣本生成新的訓練樣本集合，然後根據自助樣本集生成k個分類樹組成隨機森林，新數據的分類結果按分類樹投票多少形成的分數而定。其實質是對決策樹演算法的一種改進，將多個決策樹合併在一起，每棵樹的建立依賴於一個獨立抽取的樣品，森林中的每棵樹具有相同的分布，分類誤差取決於每一棵樹的分類能力和它們之間的相關性。特徵選擇採用隨機的方法去分裂每一個節點，然後比較不同情況下產生的誤差。能夠檢測到的內在估計誤差、分類能力和相關性決定選擇特徵的數目。單棵樹的分類能力可能很小，但在隨機產生大量的決策樹後，一個測試樣品可以通過每一棵樹的分類結果經統計後選擇最可能的分類。

?隨機森林演算法過程

?從訓練數據中選取n個數據作為訓練數據輸入，一般情況下n是遠小於整體的訓練數據N的，這樣就會造成有一部分數據是無法被取到的，這部分數據稱為袋外數據，可以使用袋外數據做誤差估計。

?選取了輸入的訓練數據的之後，需要構建決策樹，具體方法是每一個分裂結點從整體的特徵集M中選取m個特徵構建，一般情況下m遠小於M。

?在構造每棵決策樹的過程中，按照選取最小的基尼指數進行分裂節點的選取進行決策樹的構建。決策樹的其他結點都採取相同的分裂規則進行構建，直到該節點的所有訓練樣例都屬於同一類或者達到樹的最大深度。

?重複第2步和第3步多次，每一次輸入數據對應一顆決策樹，這樣就得到了隨機森林，可以用來對預測數據進行決策。

?輸入的訓練數據選擇好了，多棵決策樹也構建好了，對待預測數據進行預測，比如說輸入一個待預測數據，然後多棵決策樹同時進行決策，最後採用多數投票的方式進行類別的決策。

說白了，隨機森林的隨機主要是兩個方面，一個是隨機有放回的抽取樣本，一個是隨機選取特徵變數

隨機森林有許多優點：

?具有極高的準確率

?隨機性的引入，使得隨機森林不容易過擬合

?隨機性的引入，使得隨機森林有很好的抗雜訊能力

?能處理很高維度的數據，並且不用做特徵選擇

?既能處理離散型數據，也能處理連續型數據，數據集無需規範化

?訓練速度快，可以得到變數重要性排序

?容易實現並行化

隨機森林的缺點：

?當隨機森林中的決策樹個數很多時，訓練時需要的空間和時間會較大

?隨機森林模型還有許多不好解釋的地方，有點算個黑盒模型

下面我們就用python來實戰演練一下：

加上決策樹做一個對比：

用決策樹預測：

用隨機森林預測：

綜合看一下兩個預測結果的混淆矩陣

從兩個結果對比來看，隨機森林預測結果要好一點。

下面我們在介紹一個指標

當然要學習這個指標前一定要對混淆矩陣有一定的了解，不清楚的可以參考之前講邏輯回歸時的內容

ROC (Receiver OperatingCharacteristic) 曲線和 AUC (Area Under the Curve) 值常被用來評價一個二值分類器 (binary classifier) 的優劣。

ROC曲線：接收者操作特徵曲線（receiver operating characteristic curve），是反映敏感性和特異性連續變數的綜合指標，roc曲線上每個點反映著對同一信號刺激的感受性。

橫坐標：1-Specificity，偽正類率(False positive rate， FPR)，預測為正但實際為負的樣本占所有負例樣本的比例；

縱坐標：Sensitivity，真正類率(True positive rate， TPR)，預測為正且實際為正的樣本占所有正例樣本的比例。

在一個二分類模型中，假設採用邏輯回歸分類器，其給出針對每個實例為正類的概率，那麼通過設定一個閾值如0.6，概率大於等於0.6的為正類，小於0.6的為負類。對應的就可以算出一組(FPR,TPR)，在平面中得到對應坐標點。隨著閾值的逐漸減小，越來越多的實例被劃分為正類，但是這些正類中同樣也摻雜著真正的負實例，即TPR和FPR會同時增大。閾值最大時，對應坐標點為(0,0)，閾值最小時，對應坐標點(1,1)。

(a) 理想情況下，TPR應該接近1，FPR應該接近0。ROC曲線上的每一個點對應於一個threshold，對於一個分類器，每個threshold下會有一個TPR和FPR。比如Threshold最大時，TP=FP=0，對應於原點；Threshold最小時，TN=FN=0，對應於右上角的點(1,1)。

(b) P和N得分不作為特徵間距離d的一個函數，隨著閾值theta增加，TP和FP都增加。

橫軸FPR：1-TNR，1-Specificity，FPR越大，預測正類中實際負類越多。

縱軸TPR：Sensitivity(正類覆蓋率)，TPR越大，預測正類中實際正類越多。

理想目標：TPR=1，FPR=0，即圖中(0,1)點，故ROC曲線越靠攏(0,1)點，越偏離45度對角線越好，Sensitivity、Specificity越大效果越好。

AUC (Area Under Curve)被定義為ROC曲線下的面積，顯然這個面積的數值不會大於1。又由於ROC曲線一般都處於y=x這條直線的上方，所以AUC的取值範圍一般在0.5和1之間。使用AUC值作為評價標準是因為很多時候ROC曲線並不能清晰的說明哪個分類器的效果更好，而作為一個數值，對應AUC更大的分類器效果更好。

從AUC判斷分類器（預測模型）優劣的標準：

AUC = 1，是完美分類器，採用這個預測模型時，存在至少一個閾值能得出完美預測。絕大多數預測的場合，不存在完美分類器。

0.5

AUC = 0.5，跟隨機猜測一樣（例：丟銅板），模型沒有預測價值。

AUC