Bagging策略

1.總樣本數(shù)量是n個，從樣本中重采樣(有放回的)選出n個樣本 ，會有約33.2%的樣本不會被抽到

2.在所有屬性上對這n個樣本建立分類器(比如決策樹，svm，lr)

3.重復(fù)步驟1和2m次，建立了m個分類器

4.將數(shù)據(jù)放在這m個分類器上，根據(jù)這m個分類器的投票結(jié)果決定數(shù)據(jù)屬于哪一類

隨機森林--在Bagging基礎(chǔ)上做了改進

1.從樣本中重采樣(有放回的)選出n個樣本，與bagging相同

2.從屬性中選出k個屬性，選擇最佳分割屬性作為節(jié)點建立CART決策樹，假設(shè)有F個特征，k一般取log2F

3.重復(fù)步驟1和2m次，建立了m個決策樹分類器

4.這m個決策樹構(gòu)成了隨機森林，根據(jù)投票結(jié)果決定數(shù)據(jù)屬于哪一類

隨機森林和bagging主要是降低方差。在隨機森林中也可以使用svm、lr等其他的分類器。

隨機森林中oob error的計算：

對于每棵樹來說，樣本集采樣都是放回采樣，所以必然有一些樣本沒有被采樣到，沒有被采樣到的樣本稱為袋外數(shù)據(jù)(out of bag)。(1-1/M)^M求極限得1/e,也就是有大約 1/e的數(shù)據(jù)沒有被采樣到。可以利用oob來驗證隨機森林的性能。

如上圖，*表示該樣本沒有被gt采樣到，比如(xn,yn)假設(shè)它只沒有被g2,g3,gT采樣到，對于這個樣本可以讓g2,g3,gT分類，取投票結(jié)果，如果與其真實分類不同，則錯誤樣本數(shù)加一。

同樣的對于所有的樣本，將他們用沒有使用它們的樹集合來分類，統(tǒng)計他們的錯誤數(shù)，然后除以總的樣本數(shù)，也就是oob error了。公式如下圖所示：

隨機森林進行特征重要性度量的詳細說明--可以借此進行特征選擇

特征選擇方法中，有一種方法是利用隨機森林，進行特征的重要性度量，選擇重要性較高的特征。下面對如何計算重要性進行說明。

1 特征重要性?度量

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

1)對每一顆決策樹，選擇相應(yīng)的袋外數(shù)據(jù)(out of bag，OOB)?計算袋外數(shù)據(jù)誤差，記為errOOB1.

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

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

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

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

?2 特征選擇

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

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

2)確定要剔除的比例，依據(jù)特征重要性剔除相應(yīng)比例的特征，得到一個新的特征集

3)用新的特征集重復(fù)上述過程，直到剩下m個特征(m為提前設(shè)定的值)。

4)根據(jù)上述過程中得到的各個特征集和特征集對應(yīng)的袋外誤差率，選擇袋外誤差率最低的特征集。

AdaBoosting (Adaptive Boosting)

提高前一輪被弱分類器錯誤分類樣本的權(quán)重，降低那些正確分類的樣本的權(quán)值

加權(quán)多數(shù)表決：加大分類誤差小的分類器的權(quán)值，減小分類誤差大的分類器的權(quán)值

AdaBoost算法是模型為加法模型、損失函數(shù)為指數(shù)函數(shù)、學(xué)習(xí)算法為前向分布算法的二類學(xué)習(xí)算法。

AdaBoost算法可以看做是采用指數(shù)損失函數(shù)的提升方法，每個基函數(shù)的學(xué)習(xí)算法為前向分步算法。

AdaBoost的訓(xùn)練誤差是以指數(shù)速率下降的，不需要事先知道下界，具有自適應(yīng)性，它能自適應(yīng)弱分類器的訓(xùn)練誤差。

boosting的思想主要是降低偏差。

GBDT(Gradient Bossting Decision Tree)

提升樹是以分類樹或回歸樹最為基本分類器的提升方法。

簡單的損失函數(shù)優(yōu)化比較簡單，可以使用殘差作為擬合的目標，對于一般的損失函數(shù)來說，利用損失函數(shù)的負梯度在當(dāng)前模型的值作為殘差的近似值

對于決策樹，其實可以把它表示為下式，即是把特征空間劃分為多個區(qū)域，每個區(qū)域返回某個值作為決策樹的預(yù)測值

gbdt算法的步驟

隨機森林與gbdt的異同

隨機森林的優(yōu)點：

實現(xiàn)簡單，訓(xùn)練速度快，泛化能力強，可以并行實現(xiàn)，因為訓(xùn)練時樹與樹之間是相互獨立的；

相比單一決策樹，能學(xué)習(xí)到特征之間的相互影響，且不容易過擬合；

能處理高維數(shù)據(jù)(即特征很多)，并且不用做特征選擇，因為特征子集是隨機選取的；

對于不平衡的數(shù)據(jù)集，可以平衡誤差；

相比SVM，不是很怕特征缺失，因為待選特征也是隨機選取；

訓(xùn)練完成后可以給出哪些特征比較重要。

隨機森林的缺點：

在噪聲過大的分類和回歸問題還是容易過擬合；

相比于單一決策樹，它的隨機性讓我們難以對模型進行解釋。

GBDT和隨機森林的相同點：

1、都是集成算法，都是由多棵樹組成

2、最終的結(jié)果都是由多棵樹一起決定

GBDT和隨機森林的不同點：

1、組成隨機森林的樹可以是分類樹，也可以是回歸樹；而GBDT只由回歸樹組成

2、組成隨機森林的樹可以并行生成；而GBDT只能是串行生成

3、對于最終的輸出結(jié)果而言，隨機森林采用多數(shù)投票等；而GBDT則是將所有結(jié)果累加起來，或者加權(quán)累加起來

4、隨機森林對異常值不敏感，GBDT對異常值非常敏感

5、隨機森林對訓(xùn)練集一視同仁，GBDT是基于權(quán)值的弱分類器的集成

6、隨機森林是通過減少模型方差提高性能，GBDT是通過減少模型偏差提高性能

gbdt正則化的幾個參數(shù)

Shrinkage

Shrinkage就是將每棵樹的輸出結(jié)果乘一個因子(0

fm(x)=fm?1(x)+ν?ΣJmj=1γjmI(x∈Rjm)fm(x)=fm?1(x)+ν?Σj=1JmγjmI(x∈Rjm)

ESL書中這樣講：

The parameter?νν?can be regarded as controlling the leanring rate of the boosting procedure

νν和迭代輪數(shù)M(樹個數(shù))是一個tradeoff，推薦的是νν值設(shè)置小一點(如0.1)，而M設(shè)置大一些。這樣一般能有比較好的準確率，代價是訓(xùn)練時間變長(與M成比例)。

Subsampling

Subsampling其實源于bootstrap averaging(bagging)思想，GBDT里的做法是在每一輪建樹時，樣本是從訓(xùn)練集合中無放回隨機抽樣的ηη部分，典型的ηη值是0.5。這樣做既能對模型起正則作用，也能減少計算時間。

事實上，XGBoost和Sklearn的實現(xiàn)均借鑒了隨機森林，除了有樣本層次上的采樣，也有特征采樣。也就是說建樹的時候只從隨機選取的一些特征列尋找最優(yōu)分裂。

Tree ensemble算法的特征重要度計算

集成學(xué)習(xí)因具有預(yù)測精度高的優(yōu)勢而受到廣泛關(guān)注，尤其是使用決策樹作為基學(xué)習(xí)器的集成學(xué)習(xí)算法。樹的集成算法的著名代碼有隨機森林和GBDT。隨機森林具有很好的抵抗過擬合的特性，并且參數(shù)(決策樹的個數(shù))對預(yù)測性能的影響較小，調(diào)參比較容易，一般設(shè)置一個比較大的數(shù)。GBDT具有很優(yōu)美的理論基礎(chǔ)，一般而言性能更有優(yōu)勢。

基于樹的集成算法還有一個很好的特性，就是模型訓(xùn)練結(jié)束后可以輸出模型所使用的特征的相對重要度，便于我們選擇特征，理解哪些因素是對預(yù)測有關(guān)鍵影響，這在某些領(lǐng)域(如生物信息學(xué)、神經(jīng)系統(tǒng)科學(xué)等)特別重要。本文主要介紹基于樹的集成算法如何計算各特征的相對重要度。

使用boosted tree作為學(xué)習(xí)算法的優(yōu)勢：

使用不同類型的數(shù)據(jù)時，不需要做特征標準化/歸一化

可以很容易平衡運行時效率和精度；比如，使用boosted tree作為在線預(yù)測的模型可以在機器資源緊張的時候截斷參與預(yù)測的樹的數(shù)量從而提高預(yù)測效率

學(xué)習(xí)模型可以輸出特征的相對重要程度，可以作為一種特征選擇的方法

模型可解釋性好

對數(shù)據(jù)字段缺失不敏感

能夠自動做多組特征間的interaction，具有很好的非性線性

特征重要度的計算

Friedman在GBM的論文中提出的方法：

特征j[Math Processing Error]的全局重要度通過特征j[Math Processing Error]在單顆樹中的重要度的平均值來衡量：

J2j^=1M∑m=1MJ2j^(Tm)

[Math Processing Error]

其中，M是樹的數(shù)量。特征j[Math Processing Error]在單顆樹中的重要度的如下：

J2j^(T)=∑t=1L?1i2t^1(vt=j)

[Math Processing Error]

其中，L[Math Processing Error]為樹的葉子節(jié)點數(shù)量，L?1[Math Processing Error]即為樹的非葉子節(jié)點數(shù)量(構(gòu)建的樹都是具有左右孩子的二叉樹)，vt[Math Processing Error]是和節(jié)點t[Math Processing Error]相關(guān)聯(lián)的特征，i2t^[Math Processing Error]是節(jié)點t[Math Processing Error]分裂之后平方損失的減少值。

實現(xiàn)代碼片段

為了更好的理解特征重要度的計算方法，下面給出scikit-learn工具包中的實現(xiàn)，代碼移除了一些不相關(guān)的部分。

下面的代碼來自于GradientBoostingClassifier對象的feature_importances屬性的計算方法：

def feature_importances_(self):

total_sum = np.zeros((self.n_features, ), dtype=np.float64)

for tree in self.estimators_:

total_sum += tree.feature_importances_

importances = total_sum / len(self.estimators_)

return importances

其中，self.estimators_是算法構(gòu)建出的決策樹的數(shù)組，tree.feature_importances_ 是單棵樹的特征重要度向量，其計算方法如下：

cpdef compute_feature_importances(self, normalize=True):

"""Computes the importance of each feature (aka variable)."""

while node != end_node:

if node.left_child != _TREE_LEAF:

# ... and node.right_child != _TREE_LEAF:

left = &nodes[node.left_child]

right = &nodes[node.right_child]

importance_data[node.feature] += (

node.weighted_n_node_samples * node.impurity -

left.weighted_n_node_samples * left.impurity -

right.weighted_n_node_samples * right.impurity)

node += 1

importances /= nodes[0].weighted_n_node_samples

return importances

上面的代碼經(jīng)過了簡化，保留了核心思想。計算所有的非葉子節(jié)點在分裂時加權(quán)不純度的減少，減少得越多說明特征越重要。

總結(jié)

以上是生活随笔為你收集整理的gbdt 算法比随机森林容易_随机森林与GBDT的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。