作者：Poll的筆記
來源：http://www.cnblogs.com/maybe2030/
閱讀目錄
今天我們來談一談機(jī)器學(xué)習(xí)算法中的各種樹形算法，包括ID3、C4.5、CART以及基于集成思想的樹模型Random Forest和GBDT。本文對各類樹形算法的基本思想進(jìn)行了簡單的介紹，重點(diǎn)談一談被稱為是算法中的“戰(zhàn)斗機(jī)”，機(jī)器學(xué)習(xí)中的“屠龍刀”的GBDT算法。
決策樹是一種基本的分類與回歸方法，它可以被認(rèn)為是一種if-then規(guī)則的集合。決策樹由節(jié)點(diǎn)和有向邊組成，內(nèi)部節(jié)點(diǎn)代表了特征屬性，外部節(jié)點(diǎn)（葉子節(jié)點(diǎn)）代表了類別。
下圖為決策樹的一個(gè)圖例：
決策樹根據(jù)一步步地屬性分類可以將整個(gè)特征空間進(jìn)行劃分，從而區(qū)別出不同的分類樣本，如下圖所示：
根據(jù)上圖其實(shí)我們不難可以想到，滿足樣本劃分的決策樹有無數(shù)種，什么樣的決策樹才算是一顆好的決策樹呢？
性能良好的決策樹的選擇標(biāo)準(zhǔn)是一個(gè)與訓(xùn)練數(shù)據(jù)矛盾較小的決策樹，同時(shí)具有很好的泛化能力。言外之意就是說，好的決策樹不僅對訓(xùn)練樣本有著很好的分類效果，對于測試集也有著較低的誤差率。
一個(gè)完整的決策樹學(xué)習(xí)算法包含有三大步驟，分別為：
1) 特征的選擇；
2) 決策樹的生成；
3) 決策樹的剪枝。
在介紹決策樹學(xué)習(xí)算法之前，我們先簡單談幾個(gè)基本的概念：
1) 熵（entropy）
在信息論和概率統(tǒng)計(jì)中，熵是表示隨機(jī)變量不確定性的度量。設(shè)X是一個(gè)取有限個(gè)值的離散隨機(jī)變量，其概率分布為：
P(X=xi)=pi, i=1,2, ... , n
則隨機(jī)變量X的熵定義為：
H(X)=- ∑ pi * logpi, i=1,2, ... , n
熵只依賴X的分布，和X的取值沒有關(guān)系，熵是用來度量不確定性，當(dāng)熵越大，概率說X=xi的不確定性越大，反之越小，在機(jī)器學(xué)期中分類中說，熵越大即這個(gè)類別的不確定性更大，反之越小，當(dāng)隨機(jī)變量的取值為兩個(gè)時(shí)，熵隨概率的變化曲線如下圖：
當(dāng)p=0或p=1時(shí)，H(p)=0,隨機(jī)變量完全沒有不確定性，當(dāng)p=0.5時(shí)，H(p)=1,此時(shí)隨機(jī)變量的不確定性最大。
條件熵（conditional entropy）：表示在一直隨機(jī)變量X的條件下隨機(jī)變量Y的不確定性度量。
設(shè)隨機(jī)變量(X, Y)，其聯(lián)合概率分布為 P(X, Y) = pij(i=1,2, ... , n; j=1,2, ... , m)，隨機(jī)變量X給定的條件下隨機(jī)變量Y的條件熵H(Y|X)，定義為X給定條件下Y的條件概率分布的熵對X的數(shù)學(xué)期望：
H(Y|X)=∑ pi*H(Y|X=xi)
這里，pi=P(X=xi), i=1,2, ... , n.
2) 信息增益（information gain）
信息增益表示得知特征X的信息而使得類Y的信息的不確定性減少的程度。
特征A對訓(xùn)練數(shù)據(jù)集D的信息增益g(D, A)，定義為集合D的經(jīng)驗(yàn)熵H(D)與特征A給定條件下D的經(jīng)驗(yàn)條件熵H(D|A)之差，即
g(D, A)=H(D)-H(D|A)
信息增益大的特征具有更強(qiáng)的分類能力。
3) 信息增益比（information gain ratio）
信息增益比gR(D, A)定義為其信息增益g(D, A)與訓(xùn)練數(shù)據(jù)集D關(guān)于特征A的值的熵HA(D)之比，即
gR(D, A)=g(D, A)/HA(D)
其中，HA(D)=-∑|Di|/|D|*log2|Di|/|D|, n是特征A取值的個(gè)數(shù)。
4) 基尼指數(shù)（gini index）
分類問題中，假設(shè)有K個(gè)類，樣本屬于第k類的概率為pk，則概率分布的基尼指數(shù)定義為：
Gini(p)=∑pk(1-pk)=1-∑pk2
對于二分類問題，若樣本點(diǎn)屬于第1個(gè)類的概率是p，則概率分布的基尼指數(shù)為：
Gini(p)=2p(1-p)
對于給定的樣本集合D，其基尼指數(shù)為：
Gini(D)=1-∑(|Ck|/|D|)2
這里，Ck是D中屬于第k類的樣本子集，k是類的個(gè)數(shù)。
如果樣本集合D根據(jù)特征A是否取到某一可能值a被分割成D1和D2兩部分，則在特征A的條件下，集合D的基尼指數(shù)定義為：
Gini(D,A)=|D1|/|D|*Gini(D1) |D2|/|D|*Gini(D2)
基尼指數(shù)Gini(D)表示集合D的不確定性，基尼指數(shù)越大，樣本集合的不確定性也就越大，這一點(diǎn)與熵相似。
其實(shí)不同的決策樹學(xué)習(xí)算法只是它們選擇特征的依據(jù)不同，決策樹的生成過程都是一樣的（根據(jù)當(dāng)前環(huán)境對特征進(jìn)行貪婪的選擇）。
ID3算法的核心是在決策樹各個(gè)節(jié)點(diǎn)上應(yīng)用信息增益準(zhǔn)則選擇特征，每一次都選擇使得信息增益最大的特征進(jìn)行分裂，遞歸地構(gòu)建決策樹。
ID3算法以信息增益作為劃分訓(xùn)練數(shù)據(jù)集的特征，有一個(gè)致命的缺點(diǎn)。選擇取值比較多的特征往往會(huì)具有較大的信息增益，所以ID3偏向于選擇取值較多的特征。
針對ID3算法的不足，C4.5算法根據(jù)信息增益比來選擇特征，對這一問題進(jìn)行了校正。
CART指的是分類回歸樹，它既可以用來分類，又可以被用來進(jìn)行回歸。CART用作回歸樹時(shí)用平方誤差最小化作為選擇特征的準(zhǔn)則，用作分類樹時(shí)采用基尼指數(shù)最小化原則，進(jìn)行特征選擇，遞歸地生成二叉樹。
決策樹的剪枝：我們知道，決策樹在生成的過程中采用了貪婪的方法來選擇特征，從而達(dá)到對訓(xùn)練數(shù)據(jù)進(jìn)行更好地?cái)M合（其實(shí)從極端角度來看，決策樹對訓(xùn)練集的擬合可以達(dá)到零誤差）。而決策樹的剪枝是為了簡化模型的復(fù)雜度，防止決策樹的過擬合問題。具體的決策樹剪枝策略可以參見李航的《統(tǒng)計(jì)學(xué)習(xí)方法》。
隨機(jī)森林是一種集成學(xué)習(xí) 決策樹的分類模型，它可以利用集成的思想（投票選擇的策略）來提升單顆決策樹的分類性能（通俗來講就是“三個(gè)臭皮匠，頂一個(gè)諸葛亮”）。
集集成學(xué)習(xí)和決策樹于一身，隨機(jī)森林算法具有眾多的優(yōu)點(diǎn)，其中最為重要的就是在隨機(jī)森林算法中每棵樹都盡最大程度的生長，并且沒有剪枝過程。
隨機(jī)森林引入了兩個(gè)隨機(jī)性——隨機(jī)選擇樣本（bootstrap sample）和隨機(jī)選擇特征進(jìn)行訓(xùn)練。兩個(gè)隨機(jī)性的引入對隨機(jī)森林的分類性能至關(guān)重要。由于它們的引入，使得隨機(jī)森林不容易陷入過擬合，并且具有很好得抗噪能力（比如：對缺省值不敏感）。
迭代決策樹GBDT（Gradient Boosting Decision Tree）也被稱為是MART（Multiple Additive Regression Tree)）或者是GBRT（Gradient Boosting Regression Tree），也是一種基于集成思想的決策樹模型，但是它和Random Forest有著本質(zhì)上的區(qū)別。不得不提的是，GBDT是目前競賽中最為常用的一種機(jī)器學(xué)習(xí)算法，因?yàn)樗粌H可以適用于多種場景，更難能可貴的是，GBDT有著出眾的準(zhǔn)確率。這也是為什么很多人稱GBDT為機(jī)器學(xué)習(xí)領(lǐng)域的“屠龍刀”。
這么牛叉的算法，到底是怎么做到的呢？說到這里，就不得不說一下GBDT中的“GB”（Gradient Boosting）。Gradient Boosting的原理相當(dāng)?shù)膹?fù)雜，但是看不懂它也不妨礙我們對GBDT的理解和認(rèn)識(shí)，有關(guān)Gradient Boosting的詳細(xì)解釋請見wiki百科。
在這里引用另外一個(gè)網(wǎng)友的解釋來說明一下對GBDT中的Gradient Boosting的理解：
以下一段內(nèi)容引自《GBDT（MART） 迭代決策樹入門教程 | 簡介》。
“Boosting，迭代，即通過迭代多棵樹來共同決策。這怎么實(shí)現(xiàn)呢？難道是每棵樹獨(dú)立訓(xùn)練一遍，比如A這個(gè)人，第一棵樹認(rèn)為是10歲，第二棵樹認(rèn)為是0歲，第三棵樹認(rèn)為是20歲，我們就取平均值10歲做最終結(jié)論？當(dāng)然不是！且不說這是投票方法并不是GBDT，只要訓(xùn)練集不變，獨(dú)立訓(xùn)練三次的三棵樹必定完全相同，這樣做完全沒有意義。之前說過，GBDT是把所有樹的結(jié)論累加起來做最終結(jié)論的，所以可以想到每棵樹的結(jié)論并不是年齡本身，而是年齡的一個(gè)累加量。GBDT的核心就在于，每一棵樹學(xué)的是之前所有樹結(jié)論和的殘差，這個(gè)殘差就是一個(gè)加預(yù)測值后能得真實(shí)值的累加量。比如A的真實(shí)年齡是18歲，但第一棵樹的預(yù)測年齡是12歲，差了6歲，即殘差為6歲。那么在第二棵樹里我們把A的年齡設(shè)為6歲去學(xué)習(xí)，如果第二棵樹真的能把A分到6歲的葉子節(jié)點(diǎn)，那累加兩棵樹的結(jié)論就是A的真實(shí)年齡；如果第二棵樹的結(jié)論是5歲，則A仍然存在1歲的殘差，第三棵樹里A的年齡就變成1歲，繼續(xù)學(xué)。這就是Gradient Boosting在GBDT中的意義。”
其實(shí)從這里我們可以看出GBDT與Random Forest的本質(zhì)區(qū)別，GBDT不僅僅是簡單地運(yùn)用集成思想，而且它是基于對殘差的學(xué)習(xí)的。我們在這里利用一個(gè)GBDT的經(jīng)典實(shí)例進(jìn)行解釋。
假設(shè)我們現(xiàn)在有一個(gè)訓(xùn)練集，訓(xùn)練集只有4個(gè)人，A,B,C,D，他們的年齡分別是14,16,24,26。其中A、B分別是高一和高三學(xué)生；C,D分別是應(yīng)屆畢業(yè)生和工作兩年的員工。如果是用一棵傳統(tǒng)的回歸決策樹來訓(xùn)練，會(huì)得到如下圖1所示結(jié)果：
圖1
現(xiàn)在我們使用GBDT來做這件事，由于數(shù)據(jù)太少，我們限定葉子節(jié)點(diǎn)做多有兩個(gè)，即每棵樹都只有一個(gè)分枝，并且限定只學(xué)兩棵樹。我們會(huì)得到如下圖2所示結(jié)果：
圖2
在第一棵樹分枝和圖1一樣，由于A,B年齡較為相近，C,D年齡較為相近，他們被分為兩撥，每撥用平均年齡作為預(yù)測值。此時(shí)計(jì)算殘差（殘差的意思就是： A的預(yù)測值 A的殘差 = A的實(shí)際值），所以A的殘差就是16-15=1（注意，A的預(yù)測值是指前面所有樹累加的和，這里前面只有一棵樹所以直接是15，如果還有樹則需要都累加起來作為A的預(yù)測值）。進(jìn)而得到A,B,C,D的殘差分別為-1,1,-1,1。然后我們拿殘差替代A,B,C,D的原值，到第二棵樹去學(xué)習(xí)，如果我們的預(yù)測值和它們的殘差相等，則只需把第二棵樹的結(jié)論累加到第一棵樹上就能得到真實(shí)年齡了。這里的數(shù)據(jù)顯然是我可以做的，第二棵樹只有兩個(gè)值1和-1，直接分成兩個(gè)節(jié)點(diǎn)。此時(shí)所有人的殘差都是0，即每個(gè)人都得到了真實(shí)的預(yù)測值。
最后GBDT的預(yù)測結(jié)果為：
A: 14歲高一學(xué)生，購物較少，經(jīng)常問學(xué)長問題；預(yù)測年齡A = 15 – 1 = 14；
B: 16歲高三學(xué)生；購物較少，經(jīng)常被學(xué)弟問問題；預(yù)測年齡B = 15 1 = 16；
C: 24歲應(yīng)屆畢業(yè)生；購物較多，經(jīng)常問師兄問題；預(yù)測年齡C = 25 – 1 = 24；
D: 26歲工作兩年員工；購物較多，經(jīng)常被師弟問問題；預(yù)測年齡D = 25 1 = 26。
那么哪里體現(xiàn)了Gradient呢？其實(shí)回到第一棵樹結(jié)束時(shí)想一想，無論此時(shí)的cost function是什么，是均方差還是均差，只要它以誤差作為衡量標(biāo)準(zhǔn)，殘差向量(-1, 1, -1, 1)都是它的全局最優(yōu)方向，這就是Gradient。
注：圖1和圖2 最終效果相同，為何還需要GBDT呢？答案是過擬合。過擬合是指為了讓訓(xùn)練集精度更高，學(xué)到了很多“僅在訓(xùn)練集上成立的規(guī)律”，導(dǎo)致?lián)Q一個(gè)數(shù)據(jù)集當(dāng)前規(guī)律就不適用了。只要允許一棵樹的葉子節(jié)點(diǎn)足夠多，訓(xùn)練集總是能訓(xùn)練到100%準(zhǔn)確率的。在訓(xùn)練精度和實(shí)際精度（或測試精度）之間，后者才是我們想要真正得到的。我們發(fā)現(xiàn)圖1為了達(dá)到100%精度使用了3個(gè)feature（上網(wǎng)時(shí)長、時(shí)段、網(wǎng)購金額），其中分枝“上網(wǎng)時(shí)長>1.1h” 很顯然已經(jīng)過擬合了，這個(gè)數(shù)據(jù)集上A,B也許恰好A每天上網(wǎng)1.09h, B上網(wǎng)1.05小時(shí)，但用上網(wǎng)時(shí)間是不是>1.1小時(shí)來判斷所有人的年齡很顯然是有悖常識(shí)的；相對來說圖2的boosting雖然用了兩棵樹 ，但其實(shí)只用了2個(gè)feature就搞定了，后一個(gè)feature是問答比例，顯然圖2的依據(jù)更靠譜。
可見，GBDT同隨機(jī)森林一樣，不容易陷入過擬合，而且能夠得到很高的精度。
補(bǔ)充實(shí)例（2015-10-7）
在此引用李航博士《統(tǒng)計(jì)學(xué)習(xí)方法》中提升樹的實(shí)例來進(jìn)一步闡述GBDT的詳細(xì)流程。
一直認(rèn)為李航博士講的機(jī)器學(xué)習(xí)更加貼近算法的本質(zhì)，我們先來看一下他是如何對GBDT進(jìn)行定義的（在《統(tǒng)計(jì)學(xué)習(xí)方法中》，GBDT又被稱為是提升樹boosting tree）。
提升方法實(shí)際采用了加法模型（即基函數(shù)的線性組合）與前向分步算法。以決策樹為基函數(shù)的提升方法稱為提升樹，對分類問題決策樹是二叉分類樹，而對于回歸問題決策樹是二叉回歸樹。提升樹模型可以表示為決策樹的加法模型：
其中，表示決策樹；表示決策樹的參數(shù)；M為樹的個(gè)數(shù)。
針對不同問題的提升樹（GBDT），其主要區(qū)別在于使用的損失函數(shù)不同，包括用平方誤差損失函數(shù)的回歸問題，用指數(shù)損失函數(shù)的分類問題，以及用一般損失函數(shù)的一般決策問題。
提升樹的流程：
下面我們通過一個(gè)實(shí)例來透徹地來看一下提升樹（GDBT）到底是怎樣一步一步解決問題的。
[1] 李航《統(tǒng)計(jì)學(xué)習(xí)方法》
交流分享、謝謝支持！
<如果你覺得本文還不錯(cuò)，對你的學(xué)習(xí)帶來了些許幫助，請幫忙掃描二維碼，支持本公眾號(hào)的運(yùn)營>
聯(lián)系客服
