Bagging之随機森林

随機森林（Random Forest）是一種Bagging（Bootstrap Aggregating）內建算法，在樣本随機（樣本擾動）的基礎上，進一步運用特征随機（屬性擾動）的機制，得到比一般的Bagging內建更好的效果。

要了解随機森林，需要了解以下幾點：

1、什麼是自助采樣（Bootstrap Sampling）？

2、什麼是Bagging內建？

3、随機森林的基學習器是什麼

4、随機森林的“随機”展現在哪裡？

5、随機森林如何防止過拟合？

一、自助采樣

自助采樣是用自助法進行模型評估時用到的采樣方法。我們知道，在模型初步訓練完成後，需要用測試集對學習器的泛化誤差進行評估，這就涉及到如何産生測試樣本的問題。比如有一個包含m個樣本的資料集D={(x1, y1),(x2, y2),...,(xm, ym)}，用什麼方法對D進行适當地處理，從中産生訓練集D'和測試集D\D'呢？需要注意的是，産生的測試集要盡可能和訓練集互斥。

常見的産生測試集的方法有留出法（hold out）、交叉驗證法（cross validation）和自助法（bootstrapping），而自助采樣（bootstrap sampling）是自助法中的采樣方法。留出法和交叉驗證法的問題在于保留了一部分樣本用于測試，是以訓練集比樣本集小，進而會導緻一定的估計偏差。而采用自助法，訓練集和樣本集的樣本量是一樣的，就可以減少訓練規模不同造成的影響。

那自助采樣具體是怎樣進行的呢？自助采樣是一種有放回的抽樣，如果給定一個包含m個樣本的資料集D，那麼訓練集D'是這樣産生的：每次随機地從樣本集D中取出一個樣本，放入到訓練集D'中，然後把這個樣本放回原來的樣本集中，繼續進行随機抽取；這樣有放回地抽樣m次，就得到了包含m個樣本的訓練集D'，于是訓練集和樣本集的大小就一樣了。

顯然訓練集D'中有部分樣本是重複的，而D中有一部分樣本卻不在訓練集中。經過估計，樣本在m次采樣中始終不被抽取到的機率大概是36.8%，也就是說通過自助采樣，初始樣本集D中大約有36.8%的樣本不在訓練集D'中。把不在訓練集中出現的樣本記作：D\D'，作為測試集。于是，自助采樣中的測試集就這樣産生了。而用這約占資料總量36.8%、未在訓練集中出現的樣本集作為測試集，用于評估模型泛化誤差的做法，叫做“包外估計”（out of bag estimate）。

以上是一次自助采樣的結果，也就是産生了一個包含m個樣本的訓練集，以及包含大約占樣本總量36.8%且未在訓練集中出現的樣本的測試集。

在內建學習的Bagging模型中，如果打算訓練K個學習器，那麼以上的采樣過程要重複K次，也就是從初始樣本集中産生K個訓練集，再用這K個訓練集來訓練出K個學習器。

到此就了解了，自助采樣是一種有放回的随機采樣，是Bagging內建中的采樣方法，能夠産生一個和原始樣本集同樣大小的訓練集，以及一個和訓練集互斥且樣本量約占總樣本36.8%的測試集。

二、Bagging模型

Bagging（Bootstrap Aggregating）是并行式內建學習方法中最著名的代表，它是基于自助采樣法進行模型訓練和模型評估的方法。Bagging的基本思想可以了解為，在分類問題中，将若幹個弱分類器的分類結果進行投票選擇，進而組成一個強分類器。它的基本流程是：通過T次自助采樣，采樣出T個與原始樣本集規模一樣的訓練集，然後基于T個訓練集學習到T個基學習器，再将這些基學習器進行結合，并用包外估計進行模型評估。是以可以從自助采樣、學習器結合和包外估計這三個步驟來了解Bagging。

1、自助采樣

通過一次自助采樣，對于包含m個樣本的原始資料集，我們可以得到包含m個樣本的訓練集，訓練集與原始資料集大小一緻。這樣做有什麼好處呢？

在內建學習中，如果希望個體學習器能夠形成泛化性能較強的內建，那麼一方面要求每個個體學習器自身的效果比較好，另一方面要求個體學習器之間盡可能具有較大的差異。而通過自助采樣，一方面訓練集的樣本規模和原始資料集的大小一緻，個體學習器能夠進行比較充分的學習，性能比較好。另一方面多次自助采樣後産生的多個訓練集是不同的（盡管也有重疊的樣本），是以從每個訓練集中學習到的個體學習器之間有比較大的差異，我們可以把這種機制叫做樣本擾動。基于這兩點，Bagging內建的泛化性能是比較強的。

2、學習器結合

對學習好的T個基學習器進行結合，其實就是對預測輸出進行結合，在分類任務中，Bagging使用簡單投票法，在回歸任務中使用簡單平均法。如果在分類預測時出現兩個類獲得的票數相同，那麼可以随機地二選一，或者進一步考察基學習器投票的置信度來确定。

3、包外估計

通過自助采樣得到的訓練集，對其去重後得到的樣本量約為原始資料集的63.2%，那麼剩下約36.8%的樣本正好可以用來作為驗證集，評估模型的泛化誤差，這種評估方法就叫做包外估計。

具體怎麼得到Bagging的泛化誤差的包外估計呢？對于某一個樣本（xi, yi），它大約會被63.2%的基學習器進行訓練，而大約36.8%的基學習器未使用它進行學習。于是就用這36.8%的基學習器對這個樣本進行預測，并把預測結果結合起來，與真實的标記yi進行對比，如果預測錯誤，就把對比結果記為1，預測正确，則記為0。對原始樣本集D中的所有樣本(m個)都進行這種操作，并把對比結果累加起來（誤分類樣本個數），再除以樣本總數，就得到了泛化誤差的包外估計。

好，了解以上這三點，差不多也就了解了Bagging的思想。再補充以下幾點：

一是由于Bagging屬于并行內建，是以訓練一個Bagging內建與直接使用基學習算法訓練一個基學習器的複雜度同階，這表明Bagging是一個非常高效的內建學習算法。

二是與标準的AdaBoost隻适用于二分類任務不同，Bagging可以不經調整就用于多分類和回歸任務。

三是從偏差-方差分解的角度來看，與GBDT關注于降低偏差不同，Bagging主要關注降低方差，是以在不剪枝決策樹、神經網絡等容易受到樣本擾動的學習器上效果更明顯。

了解了這些，接下來了解随機森林就水到渠成了。

三、随機森林

随機森林（Random Forest，簡稱RF），是以決策樹為基學習器的Bagging內建算法，是Bagging內建算法中性能最強的。要了解随機森林，就要從它的名稱入手，拆成“随機”和“森林”兩個詞，分别來了解。

首先森林兩個字是非常好了解的，随機森林的基學習器是決策樹，成百上千棵決策樹就構成了一個森林，這是一種形象的說法。學習到多棵決策樹之後，再按照上面所寫的Bagging中基學習器的結合方法，就可以得到分類或回歸的最終預測結果。

再來了解随機二字。随機森林中運用了兩個“随機”，一是樣本随機，也就是一般的Bagging內建中通過自助采樣所得到的效果，也叫做樣本擾動，這展現了随機森林繼承性的一面。二是特征随機，也叫屬性擾動，展現了随機森林創新的一面。假設訓練資料集中的樣本有d個屬性（特征），構成一個屬性集合，那麼随機森林在建構一棵決策樹的過程中，在每一個結點上選擇屬性進行分裂時，都先從屬性集合中随機選擇一個包含k個屬性的屬性子集（k<d），再從這個子集中選擇一個最優屬性進行分裂。回想一下傳統的決策樹建構過程，在每一個結點上都是從完整的屬性集合（包含d個屬性）中，選擇最佳的屬性進行分裂。一般情況下，推薦k的值取

。

是以随機森林中每棵樹生成的規則是：

1、對于包含m個樣本的原始資料集，通過自助采樣得到同樣包含m個樣本的訓練集；

2、每個樣本有d個特征，那麼選擇一個小于d的整數k，随機地從d個特征中選擇k個特征，然後決策樹在每個結點上進行分裂時，從k個特征中選擇最優的；

3、每棵樹都生長到最大深度，不進行剪枝。

以上就是随機森林的思想和操作流程，幾乎沒有公式（如果已經學習了決策樹），非常簡單是不是，簡直不敢相信！

随機森林隻是對Bagging做了一個小改動，與一般Bagging內建中基學習器的“多樣性”僅來自于樣本擾動不同，随機森林再加入了屬性擾動的機制。可别小看了這一個小改動，它使得基學習器之間的差異度進一步增加，進而進一步提高了內建的泛化性能，并且由于随機森林在建構決策樹時隻考察一個屬性子集，與一般Bagging內建考察全部屬性相比，訓練效率高得多。

也正因為屬性擾動機制非常重要，是以選擇多少個屬性（k的值）構成屬性子集，就成了一個至關重要的問題，這也是随機森林中唯一的參數。

四、随機森林總結

随機森林中的決策樹是不需要進行剪枝的，卻一般不會過拟合，原因就在于兩個随機：樣本随機和特征随機，使得生成的各決策樹之間存在較大的差異性，哪怕單獨的一棵樹是過拟合的，內建之後也可以消除這種影響。

随機森林的優點非常明顯：

1、能夠有效地運作在大規模資料集上；

2、能夠處理具有高維特征的輸入樣本，而不需要降維；

3、抗噪能力強，能夠很好地處理缺失值問題；

4、能夠評估各個特征在分類問題上的重要性；

5、随機森林抗過拟合的能力比較強，生成的決策樹不需要進行剪枝；

6、在決策樹生成的過程中，就能夠通過包外估計，對泛化誤差建立一個無偏估計。

參考資料：

1、周志華：《機器學習》

2、https://www.cnblogs.com/maybe2030/p/4585705.html