Bootstrapping

Bootstrapping從字面意思翻譯是拔靴法，從其內容翻譯又叫自助法，是一種再抽樣的統計方法。自助法的名稱來源于英文短語“to?pull oneself up by one’s bootstrap”，表示完成一件不能自然完成的事情。1977年美國Standford大學統計學教授Efron提出了一種新的增廣樣本的統計方法，就是Bootstrap方法，為解決小子樣試驗評估問題提供了很好的思路。

算法流程

從N個樣本中有放回的隨機抽取n個樣本。

用n個樣本計算統計量

重復1，2步驟m次，得到統計量

計算統計量序列的方差，則可得到統計量方差的無偏估計。（均值也是，bootstrapping方法就是通過多次的隨機采樣得到可以代表母體樣本分布的子樣本分布）

Bagging策略(bootstrap aggregating)套袋法

從N個樣本中有放回的隨機抽取n個樣本。

用這n個樣本的所有屬性構建基分類器（LR,ID3,C4.5,SVM）

重復1,2兩步m次，構建m個基分類器

投票得出分類結果，哪個票最多就是哪一類。對回歸模型，取多有基分類器結果的均值。總而言之就是所有基分類器的權重相同。

隨機森林

bagging方法可以有效降低模型的方差。隨機森林每棵子樹不需要剪枝，是低偏差高方差的模型，通過bagging降低方差后使得整個模型有較高的性能。

隨機森林其實很簡單，就是在bagging策略上略微改動了一下。

從N個樣本中有放回的隨機抽樣n個樣本。

如果每個樣本的特征維度為M，指定一個常數m<<M，隨機地從M個特征中選取m個特征子集，每次樹（ID3,C4.5,CART）進行分裂時，從這m個特征中選擇最優的(信息增益，信息增益比率，基尼系數)；

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

最后采用投票表決的方式進行分類。

特征m個數的選取：

用作分類時，m默認取，最小取1.

用作回歸時，m默認取M/3，最小取5.

兩個隨機性的引入對隨機森林的分類性能至關重要。由于它們的引入，使得隨機森林不容易陷入過擬合，并且具有很好得抗噪能力（比如：對缺省值不敏感）。

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

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

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

OOB（Out Of Bag）袋外錯誤率

在bootstrapping的過程中，有些數據可能沒有被選擇，這些數據稱為out-of-bag(OOB) examples。

解釋一下上面這張圖。一眼看還是挺難理解的，用白話講一下。

是什么？

隨機森林中每一次樣本抽樣（不是特征抽樣），就是bootstrapping方法，是有放回的隨機抽樣，所以每一次抽的時候，對于一個特定的樣本，抽到它的概率就是，很好理解，N個樣本里隨機抽取一個，抽到的概率當然是，因為是有放回的抽樣，所以分母永遠是N。

是什么？

既然被抽到的概率是，那不被抽到的概率就是,很好理解。那指數大N又是什么呢？其實就是抽樣的次數。假設我們的隨機森林一共有A顆樹，每棵樹抽了B個樣本，那么指數大N就是，是不是感覺指數大N應該和分母的那個N一樣？其實這里只是為了方便，它表達的意思就是抽了很多次。

搞明白了那個公式之后，就可以開始計算了。要用到數學分析中的極限知識。一步步推一下。

這是基本公式：?后面的都是基于這個變形

這說明了什么呢？就是你隨機森林已經造好了，但是即使你的訓練集是整個樣本集，其中也會有的樣本你抽不到。為什么抽不到，上面的公式就是告訴你為什么抽不到。這些抽不到的樣本就叫做out-of-bag(OOB) examples

好了，到這里已經能搞懂什么是out-of-bag(OOB) examples了。那這些樣本能用來做什么呢？下面就介紹oob袋外錯誤率。

袋外錯誤率的應用

正常情況下，我們訓練一個模型，怎么驗證它好不好。是不是要拿出一部分的數據集當作驗證集，更好的還要拿出一部分當作測試集，一般是6:2:2。

在隨機森林中，有了out-of-bag(OOB) examples，我們就不需要拿出一部分數據了，out-of-bag(OOB) examples就是那部分沒有用到的數據，我們可以直接當成驗證集來使用。

obb error = 被分類錯誤數 / 總數

隨機森林算法中不需要再進行交叉驗證或者單獨的測試集來獲取測試集誤差的無偏估計。

Breiman [1996b]在對 bagged?分類器的錯誤率估計研究中,?給出實證證據顯示，out-of-bag?估計?和使用與訓練集大小一致的測試集所得到的錯誤率一樣精確. 所以, 使用out-of-bag error?估計可以不在另外建立一個測試集.

特征重要性度量

計算某個特征X的重要性時，具體步驟如下：

對整個隨機森林，得到相應的袋外數據（out of bag，OOB）?計算袋外數據誤差，記為errOOB1.

所謂袋外數據是指，每次建立決策樹時，通過重復抽樣得到一個數據用于訓練?決策樹，這時還有大約1/3的數據沒有被利用，沒有參與決策樹的建立。這部分數據可以用于對決策樹的性能進行評估，計算模型的預測錯誤率，稱為袋外數據誤差。

?這已經經過證明是無偏估計的,所以在隨機森林算法中不需要再進行交叉驗證或者單獨的測試集來獲取測試集誤差的無偏估計。

隨機對袋外數據OOB所有樣本的特征X加入噪聲干擾（可以隨機改變樣本在特征X處的值），再次計算袋外數據誤差，記為errOOB2。

?假設森林中有N棵樹，則特征X的重要性=（∑errOOB2?errOOB1）/N。這個數值之所以能夠說明特征的重要性是因為，如果加入隨機噪聲后，袋外數據準確率大幅度下降（即errOOB2上升），說明這個特征對于樣本的預測結果有很大影響，進而說明重要程度比較高。

特征選擇

在特征重要性的基礎上，特征選擇的步驟如下：

計算每個特征的重要性，并按降序排序

確定要剔除的比例，依據特征重要性剔除相應比例的特征，得到一個新的特征集

用新的特征集重復上述過程，直到剩下m個特征（m為提前設定的值）。

根據上述過程中得到的各個特征集和特征集對應的袋外誤差率，選擇袋外誤差率最低的特征集。?

優點

• 在數據集上表現良好
• 在當前的很多數據集上，相對其他算法有著很大的優勢
• 它能夠處理很高維度（feature很多）的數據，并且不用做特征選擇
• 在訓練完后，它能夠給出哪些feature比較重要
• 在創建隨機森林的時候，對generlization error使用的是無偏估計
• 訓練速度快
• 在訓練過程中，能夠檢測到feature間的互相影響
• 容易做成并行化方法
• 實現比較簡單
• 可以得到變量重要性排序（兩種：基于OOB誤分率的增加量和基于分裂時的GINI下降量）

隨機森林有許多優點：

• 具有極高的準確率
• 隨機性的引入，使得隨機森林不容易過擬合
• 隨機性的引入，使得隨機森林有很好的抗噪聲能力
• 能處理很高維度的數據，并且不用做特征選擇
• 既能處理離散型數據，也能處理連續型數據，數據集無需規范化
• 訓練速度快，可以得到變量重要性排序
• 容易實現并行化

隨機森林的缺點：

• 當隨機森林中的決策樹個數很多時，訓練時需要的空間和時間會較大
• 隨機森林模型還有許多不好解釋的地方，有點算個黑盒模型

總結

以上是生活随笔為你收集整理的【机器学习】集成学习ensemble之随机森林的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。