隨機森林(RF)的原理

集成學(xué)習(xí)有兩個流派，一個是boosting派系，它的特點是各個弱學(xué)習(xí)器之間有依賴關(guān)系。另一種是bagging流派，它的特點是各個弱學(xué)習(xí)器之間沒有依賴關(guān)系，可以并行擬合。本文就對集成學(xué)習(xí)中Bagging與隨機森林算法做一個總結(jié)。
隨機森林是集成學(xué)習(xí)中可以和梯度提升樹GBDT分庭抗禮的算法，尤其是它可以很方便的并行訓(xùn)練，在如今大數(shù)據(jù)大樣本的時代很有誘惑力。

bagging的原理

bagging集成學(xué)習(xí)方法可以利用下圖說明：

在這里插入圖片描述

bagging算法流程

上面我們對bagging算法的原理做了總結(jié)，這里就對bagging算法的流程做一個總結(jié)。相對于Boosting系列的Adaboost和GBDT，bagging算法要簡單的多。
輸入為樣本集D={(x1,y1),(x2,y2),...(xm,ym)}，弱學(xué)習(xí)器算法, 弱分類器迭代次數(shù)T。輸出為最終的強分類器f(x).
1）對于t=1,2...,T:

• 對訓(xùn)練集進(jìn)行第t次隨機采樣，共采集m次，得到包含m個樣本的采樣集Dm
• 用采樣集Dm訓(xùn)練m個弱學(xué)習(xí)器Gm(x)

2. 如果是分類算法預(yù)測，則T個弱學(xué)習(xí)器投出最多票數(shù)的類別或者類別之一為最終類別。如果是回歸算法，T個弱學(xué)習(xí)器得到的回歸結(jié)果進(jìn)行算術(shù)平均得到的值為最終的模型輸出。

隨機森林算法

理解了bagging算法，隨機森林(Random Forest,以下簡稱RF)就好理解了。它是Bagging算法的進(jìn)化版，也就是說，它的思想仍然是bagging,但是進(jìn)行了獨有的改進(jìn)。我們現(xiàn)在就來看看RF算法改進(jìn)了什么?！　　?br> 首先，RF使用了CART決策樹作為弱學(xué)習(xí)器，這讓我們想到了梯度提升樹GBDT。第二，在使用決策樹的基礎(chǔ)上，RF對決策樹的建立做了改進(jìn)，對于普通的決策樹，我們會在節(jié)點上所有的n個樣本特征中選擇一個最優(yōu)的特征來做決策樹的左右子樹劃分，但是RF通過隨機選擇節(jié)點上的一部分樣本特征，這個數(shù)字小于n，假設(shè)為nsub，然后在這些隨機選擇的nsub個樣本特征中，選擇一個最優(yōu)的特征來做決策樹的左右子樹劃分。這樣進(jìn)一步增強了模型的泛化能力。

如果nsub=nnsub=n，則此時RF的CART決策樹和普通的CART決策樹沒有區(qū)別。nsubnsub越小，則模型越健壯，當(dāng)然此時對于訓(xùn)練集的擬合程度會變差。也就是說nsubnsub越小，模型的方差會減小，但是偏倚會增大。在實際案例中，一般會通過交叉驗證調(diào)參獲取一個合適的nsubnsub的值。
除了上面兩點，RF和普通的bagging算法沒有什么不同， 下面簡單總結(jié)下RF的算法。
輸入為樣本集D={(x1,y1),(x2,y2),...(xm,ym)}，弱分類器迭代次數(shù)T。輸出為最終的強分類器f(x):

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

• a)對訓(xùn)練集進(jìn)行第t次隨機采樣，共采集m次，得到包含m個樣本的采樣集Dm
• b)用采樣集Dm訓(xùn)練m個決策樹模型Gm(x)，在訓(xùn)練決策樹模型的節(jié)點的時候， 在節(jié)點上所有的樣本特征中選擇一部分樣本特征，在這些隨機選擇的部分樣本特征中選擇一個最優(yōu)的特征來做決策樹的左右子樹劃分

2. 如果是分類算法預(yù)測，則T個弱學(xué)習(xí)器投出最多票數(shù)的類別或者類別之一為最終類別。如果是回歸算法，T個弱學(xué)習(xí)器得到的回歸結(jié)果進(jìn)行算術(shù)平均得到的值為最終的模型輸出。

隨機森林算法推廣

隨機森林算法推廣
由于RF在實際應(yīng)用中的良好特性，基于RF，有很多變種算法，應(yīng)用也很廣泛，不光可以用于分類回歸，還可以用于特征轉(zhuǎn)換，異常點檢測等。下面對于這些RF家族的算法中有代表性的做一個總結(jié)。

1. extra trees
   extra trees是RF的一個變種, 原理幾乎和RF一模一樣，僅有區(qū)別有：
   1）對于每個決策樹的訓(xùn)練集，RF采用的是隨機采樣bootstrap來選擇采樣集作為每個決策樹的訓(xùn)練集，而extra trees一般不采用隨機采樣，即每個決策樹采用原始訓(xùn)練集。
   2）在選定了劃分特征后，RF的決策樹會基于信息增益，基尼系數(shù)，均方差之類的原則，選擇一個最優(yōu)的特征值劃分點，這和傳統(tǒng)的決策樹相同。但是extra trees比較的激進(jìn)，他會隨機的選擇一個特征值來劃分決策樹。
   從第二點可以看出，由于隨機選擇了特征值的劃分點位，而不是最優(yōu)點位，這樣會導(dǎo)致生成的決策樹的規(guī)模一般會大于RF所生成的決策樹。也就是說，模型的方差相對于RF進(jìn)一步減少，但是偏倚相對于RF進(jìn)一步增大。在某些時候，extra trees的泛化能力比RF更好。
   Bootstrap(自助法)補充：
   Bootstrap是一種抽樣方法
   核心思想
   
   在這里插入圖片描述
   
   Bootstrap又稱自展法，是用小樣本估計總體值的一種非參數(shù)方法，在進(jìn)化和生態(tài)學(xué)研究中應(yīng)用十分廣泛。
   Bootstrap的思想，是生成一系列bootstrap偽樣本，每個樣本是初始數(shù)據(jù)有放回抽樣。通過對偽樣本的計算，獲得統(tǒng)計量的分布。
   栗子：我要統(tǒng)計魚塘里面的魚的條數(shù)，怎么統(tǒng)計呢？假設(shè)魚塘總共有魚1000條，我是開了上帝視角的，但是你是不知道里面有多少。
   步驟：

• 1.承包魚塘，不讓別人撈魚(規(guī)定總體分布不變)。
• 2.自己撈魚，撈100條，都打上標(biāo)簽(構(gòu)造樣本)
• 3.把魚放回魚塘，休息一晚(使之混入整個魚群，確保之后抽樣隨機)
• 4.開始撈魚，每次撈100條，數(shù)一下，自己昨天標(biāo)記的魚有多少條，占比多少(一次重采樣取分布)。
• 5.重復(fù)3，4步驟n次。建立分布。

假設(shè)一下，第一次重新捕魚100條，發(fā)現(xiàn)里面有標(biāo)記的魚12條，記下為12%，放回去，再捕魚100條，發(fā)現(xiàn)標(biāo)記的為9條，記下9%，重復(fù)重復(fù)好多次之后，假設(shè)取置信區(qū)間95%，你會發(fā)現(xiàn)，每次捕魚平均在10條左右有標(biāo)記，所以，我們可以大致推測出魚塘有1000條左右。其實是一個很簡單的類似于一個比例問題。這也是因為提出者Efron給統(tǒng)計學(xué)頂級期刊投稿的時候被拒絕的理由--"太簡單"。這也就解釋了，為什么在小樣本的時候，bootstrap效果較好，你這樣想，如果我想統(tǒng)計大海里有多少魚，你標(biāo)記100000條也沒用啊，因為實際數(shù)量太過龐大，你取的樣本相比于太過渺小，最實際的就是，你下次再捕100000的時候，發(fā)現(xiàn)一條都沒有標(biāo)記，，，這特么就尷尬了.

Bootstrap經(jīng)典語錄

• Bootstrap是現(xiàn)代統(tǒng)計學(xué)較為流行的一種統(tǒng)計方法，在小樣本時效果很好。通過方差的估計可以構(gòu)造置信區(qū)間等，其運用范圍得到進(jìn)一步延伸。
• 就是一個在自身樣本重采樣的方法來估計真實分布的問題
• 當(dāng)我們不知道樣本分布的時候，bootstrap方法最有用。
• 整合多個弱分類器，成為一個強大的分類器。

2. Totally Random Trees Embedding
   Totally Random Trees Embedding(以下簡稱 TRTE)是一種非監(jiān)督學(xué)習(xí)的數(shù)據(jù)轉(zhuǎn)化方法。它將低維的數(shù)據(jù)集映射到高維，從而讓映射到高維的數(shù)據(jù)更好的運用于分類回歸模型。我們知道，在支持向量機中運用了核方法來將低維的數(shù)據(jù)集映射到高維，此處TRTE提供了另外一種方法。
   TRTE在數(shù)據(jù)轉(zhuǎn)化的過程也使用了類似于RF的方法，建立T個決策樹來擬合數(shù)據(jù)。當(dāng)決策樹建立完畢以后，數(shù)據(jù)集里的每個數(shù)據(jù)在T個決策樹中葉子節(jié)點的位置也定下來了。比如我們有3顆決策樹，每個決策樹有5個葉子節(jié)點，某個數(shù)據(jù)特征xx劃分到第一個決策樹的第2個葉子節(jié)點，第二個決策樹的第3個葉子節(jié)點，第三個決策樹的第5個葉子節(jié)點。則x映射后的特征編碼為(0,1,0,0,0, 0,0,1,0,0, 0,0,0,0,1), 有15維的高維特征。這里特征維度之間加上空格是為了強調(diào)三顆決策樹各自的子編碼。
   映射到高維特征后，可以繼續(xù)使用監(jiān)督學(xué)習(xí)的各種分類回歸算法了。

隨機森林小結(jié)

作為一個可以高度并行化的算法，RF在大數(shù)據(jù)時候大有可為。這里也對常規(guī)的隨機森林算法的優(yōu)缺點做一個總結(jié)。
RF的主要優(yōu)點有：
1）訓(xùn)練可以高度并行化，對于大數(shù)據(jù)時代的大樣本訓(xùn)練速度有優(yōu)勢。
2）由于可以隨機選擇決策樹節(jié)點劃分特征，這樣在樣本特征維度很高的時候，仍然能高效的訓(xùn)練模型。
3）在訓(xùn)練后，可以給出各個特征對于輸出的重要性
4）由于采用了隨機采樣，訓(xùn)練出的模型的方差小，泛化能力強。
5）相對于Boosting系列的Adaboost和GBDT， RF實現(xiàn)比較簡單。
6）對部分特征缺失不敏感。
RF的主要缺點有：
1)在某些噪音比較大的樣本集上，RF模型容易陷入過擬合。
2)取值劃分比較多的特征容易對RF的決策產(chǎn)生更大的影響，從而影響擬合的模型的效果。

原文