Bagging與随機森林算法原理小結（詳解）

出處：http://www.cnblogs.com/pinard/p/6156009.html

在內建學習原理小結中，我們講到了內建學習有兩個流派，一個是boosting派系，它的特點是各個弱學習器之間有依賴關系。另一種是bagging流派，它的特點是各個弱學習器之間沒有依賴關系，可以并行拟合。本文就對內建學習中Bagging與随機森林算法做一個總結。

　　　　随機森林是內建學習中可以和梯度提升樹GBDT分庭抗禮的算法，尤其是它可以很友善的并行訓練，在如今大資料大樣本的的時代很有誘惑力。

1.  bagging的原理

　　　　在內建學習原理小結中，我們給Bagging畫了下面一張原理圖。

　　　　從上圖可以看出，Bagging的弱學習器之間的确沒有boosting那樣的聯系。它的特點在“随機采樣”。那麼什麼是随機采樣？

　　　　随機采樣(bootsrap)就是從我們的訓練集裡面采集固定個數的樣本，但是每采集一個樣本後，都将樣本放回。也就是說，之前采集到的樣本在放回後有可能繼續被采集到。對于我們的Bagging算法，一般會随機采集和訓練集樣本數m一樣個數的樣本。這樣得到的采樣集和訓練集樣本的個數相同，但是樣本内容不同。如果我們對有m個樣本訓練集做T次的随機采樣，，則由于随機性，T個采樣集各不相同。

　　　　注意到這和GBDT的子采樣是不同的。GBDT的子采樣是無放回采樣，而Bagging的子采樣是放回采樣。

　　　　對于一個樣本，它在某一次含m個樣本的訓練集的随機采樣中，每次被采集到的機率是

。不被采集到的機率為

    。如果m次采樣都沒有被采集中的機率是

   。當

  時，

。也就是說，在bagging的每輪随機采樣中，訓練集中大約有36.8%的資料沒有被采樣集采集中。

　　　　對于這部分大約36.8%的沒有被采樣到的資料，我們常常稱之為袋外資料(Out Of Bag, 簡稱OOB)。這些資料沒有參與訓練集模型的拟合，是以可以用來檢測模型的泛化能力。

　　　　bagging對于弱學習器沒有限制，這和Adaboost一樣。但是最常用的一般也是決策樹和神經網絡。

　　　　bagging的集合政策也比較簡單，對于分類問題，通常使用簡單投票法，得到最多票數的類别或者類别之一為最終的模型輸出。對于回歸問題，通常使用簡單平均法，對T個弱學習器得到的回歸結果進行算術平均得到最終的模型輸出。

　　　　由于Bagging算法每次都進行采樣來訓練模型，是以泛化能力很強，對于降低模型的方差很有作用。當然對于訓練集的拟合程度就會差一些，也就是模型的偏倚會大一些。

2.  bagging算法流程

　　　　上一節我們對bagging算法的原理做了總結，這裡就對bagging算法的流程做一個總結。相對于Boosting系列的Adaboost和GBDT，bagging算法要簡單的多。

　　　　輸入為樣本集

，弱學習器算法, 弱分類器疊代次數T。

　　　　輸出為最終的強分類器

　　　　1）對于t=1,2...,T:

　　　　　　a)對訓練集進行第t次随機采樣，共采集m次，得到包含m個樣本的采樣集

　　　　　　b)用采樣集

訓練第m個弱學習器

　　　　2) 如果是分類算法預測，則T個弱學習器投出最多票數的類别或者類别之一為最終類别。如果是回歸算法，T個弱學習器得到的回歸結果進行算術平均得到的值為最終的模型輸出。

3. 随機森林算法

　　　　了解了bagging算法，随機森林(Random Forest,以下簡稱RF)就好了解了。它是Bagging算法的進化版，也就是說，它的思想仍然是bagging,但是進行了獨有的改進。我們現在就來看看RF算法改進了什麼。　　　

　　　　首先，RF使用了CART決策樹作為弱學習器，這讓我們想到了梯度提示樹GBDT。第二，在使用決策樹的基礎上，RF對決策樹的建立做了改進，對于普通的決策樹，我們會在節點上所有的n個樣本特征中選擇一個最優的特征來做決策樹的左右子樹劃分，但是RF通過随機選擇節點上的一部分樣本特征，這個數字小于n，假設為

，然後在這些随機選擇的

個樣本特征中，選擇一個最優的特征來做決策樹的左右子樹劃分。這樣進一步增強了模型的泛化能力。　　　　

　　　　如果

，則此時RF的CART決策樹和普通的CART決策樹沒有差別。

   越小，則模型約健壯，當然此時對于訓練集的拟合程度會變差。也就是說

   越小，模型的方差會減小，但是偏倚會增大。在實際案例中，一般會通過交叉驗證調參擷取一個合适的

的值。

　　　　除了上面兩點，RF和普通的bagging算法沒有什麼不同， 下面簡單總結下RF的算法。

　　　　輸入為樣本集

，弱分類器疊代次數T。

　　　　輸出為最終的強分類器

　　　　1）對于t=1,2...,T:

　　　　　　a)對訓練集進行第t次随機采樣，共采集m次，得到包含m個樣本的采樣集

　　　　　　b)用采樣集

訓練第m個決策樹模型

，在訓練決策樹模型的節點的時候， 在節點上所有的樣本特征中選擇一部分樣本特征， 在這些随機選擇的部分樣本特征中選擇一個最優的特征來做決策樹的左右子樹劃分

　　　　2) 如果是分類算法預測，則T個弱學習器投出最多票數的類别或者類别之一為最終類别。如果是回歸算法，T個弱學習器得到的回歸結果進行算術平均得到的值為最終的模型輸出。

4. 随機森林的推廣

　　　　由于RF在實際應用中的良好特性，基于RF，有很多變種算法，應用也很廣泛，不光可以用于分類回歸，還可以用于特征轉換，異常點檢測等。下面對于這些RF家族的算法中有代表性的做一個總結。

 4.1 extra trees

　　　　extra trees是RF的一個變種, 原理幾乎和RF一模一樣，僅有差別有：

　　　　1） 對于每個決策樹的訓練集，RF采用的是随機采樣bootstrap來選擇采樣集作為每個決策樹的訓練集，而extra trees一般不采用随機采樣，即每個決策樹采用原始訓練集。

　　　　2） 在標明了劃分特征後，RF的決策樹會基于資訊增益，基尼系數，均方差之類的原則，選擇一個最優的特征值劃分點，這和傳統的決策樹相同。但是extra trees比較的激進，他會随機的選擇一個特征值來劃分決策樹。

　　　　從第二點可以看出，由于随機選擇了特征值的劃分點位，而不是最優點位，這樣會導緻生成的決策樹的規模一般會大于RF所生成的決策樹。也就是說，模型的方差相對于RF進一步減少，但是偏倚相對于RF進一步增大。在某些時候，extra trees的泛化能力比RF更好。

4.2 Totally Random Trees Embedding

　　　　Totally Random Trees Embedding(以下簡稱 TRTE)是一種非監督學習的資料轉化方法。它将低維的資料集映射到高維，進而讓映射到高維的資料更好的運用于分類回歸模型。我們知道，在支援向量機中運用了核方法來将低維的資料集映射到高維，此處TRTE提供了另外一種方法。

　　　　TRTE在資料轉化的過程也使用了類似于RF的方法，建立T個決策樹來拟合資料。當決策樹建立完畢以後，資料集裡的每個資料在T個決策樹中葉子節點的位置也定下來了。比如我們有3顆決策樹，每個決策樹有5個葉子節點，某個資料特征

劃分到第一個決策樹的第2個葉子節點，第二個決策樹的第3個葉子節點，第三個決策樹的第5個葉子節點。則x映射後的特征編碼為(0,1,0,0,0,     0,0,1,0,0,     0,0,0,0,1), 有15維的高維特征。這裡特征次元之間加上空格是為了強調三顆決策樹各自的子編碼。

　　　　映射到高維特征後，可以繼續使用監督學習的各種分類回歸算法了。

4.3 Isolation Forest

　　　　Isolation Forest（以下簡稱IForest）是一種異常點檢測的方法。它也使用了類似于RF的方法來檢測異常點。

　　　　對于在T個決策樹的樣本集，IForest也會對訓練集進行随機采樣,但是采樣個數不需要和RF一樣，對于RF，需要采樣到采樣集樣本個數等于訓練集個數。但是IForest不需要采樣這麼多，一般來說，采樣個數要遠遠小于訓練集個數？為什麼呢？因為我們的目的是異常點檢測，隻需要部分的樣本我們一般就可以将異常點差別出來了。

　　　　對于每一個決策樹的建立， IForest采用随機選擇一個劃分特征，對劃分特征随機選擇一個劃分門檻值。這點也和RF不同。

　　　　另外，IForest一般會選擇一個比較小的最大決策樹深度max_depth,原因同樣本采集，用少量的異常點檢測一般不需要這麼大規模的決策樹。

　　　　對于異常點的判斷，則是将測試樣本點

拟合到T顆決策樹。計算在每顆決策樹上該樣本的葉子節點的深度

  。，進而可以計算出平均高度h(x)。此時我們用下面的公式計算樣本點

  的異常機率:

　　　　其中，m為樣本個數。

的表達式為：

為歐拉常數 

　　　　s(x,m)的取值範圍是[0,1],取值越接近于1，則是異常點的機率也越大。

5. 随機森林小結

　　　　RF的算法原理也終于講完了，作為一個可以高度并行化的算法，RF在大資料時候大有可為。 這裡也對正常的随機森林算法的優缺點做一個總結。

　　　　RF的主要優點有：

　　　　1） 訓練可以高度并行化，對于大資料時代的大樣本訓練速度有優勢。個人覺得這是的最主要的優點。

　　　　2） 由于可以随機選擇決策樹節點劃分特征，這樣在樣本特征次元很高的時候，仍然能高效的訓練模型。

　　　　3） 在訓練後，可以給出各個特征對于輸出的重要性

　　　　4） 由于采用了随機采樣，訓練出的模型的方差小，泛化能力強。

　　　　5） 相對于Boosting系列的Adaboost和GBDT， RF實作比較簡單。

　　　　6） 對部分特征缺失不敏感。

　　　　RF的主要缺點有：

　　　　1）在某些噪音比較大的樣本集上，RF模型容易陷入過拟合。

　　　　2) 取值劃分比較多的特征容易對RF的決策産生更大的影響，進而影響拟合的模型的效果。