關注數學，關注AI，關注我們公眾號ID：Math-AI

閱讀目錄

1. 決策樹的模型

2. 決策樹的基本知識

3. ID3、C4.5&CART

4. Random Forest

5. GBDT

6. 參考內容

　　今天我們來談一談機器學習算法中的各種樹形算法，包括ID3、C4.5、CART以及基于集成思想的樹模型Random Forest和GBDT。本文對各類樹形算法的基本思想進行了簡單的介紹，重點談一談被稱為是算法中的“戰斗機”，機器學習中的“屠龍刀”的GBDT算法。

1決策樹的模型

　　決策樹是一種基本的分類與回歸方法，它可以被認為是一種if-then規則的集合。決策樹由節點和有向邊組成，內部節點代表了特征屬性，外部節點(葉子節點)代表了類別。

　　下圖為決策樹的一個圖例：

　　決策樹根據一步步地屬性分類可以將整個特征空間進行劃分，從而區別出不同的分類樣本，如下圖所示：

　　根據上圖其實我們不難可以想到，滿足樣本劃分的決策樹有無數種，什么樣的決策樹才算是一顆好的決策樹呢？

　　性能良好的決策樹的選擇標準是一個與訓練數據矛盾較小的決策樹，同時具有很好的泛化能力。言外之意就是說，好的決策樹不僅對訓練樣本有著很好的分類效果，對于測試集也有著較低的誤差率。

2決策樹的基本知識

　　一個完整的決策樹學習算法包含有三大步驟，分別為：

　　1) 特征的選擇；

　　2)?決策樹的生成；

　　3) 決策樹的剪枝。

　　在介紹決策樹學習算法之前，我們先簡單談幾個基本的概念：

　　1) 熵(entropy)

　　在信息論和概率統計中，熵是表示隨機變量不確定性的度量。設X是一個取有限個值的離散隨機變量，其概率分布為：

P(X=x_i)=p_i, i=1,2, ... , n

則隨機變量X的熵定義為：

H(X)=-?∑?p_{i *?}logp_i,?i=1,2, ... , n

　　熵只依賴X的分布，和X的取值沒有關系，熵是用來度量不確定性，當熵越大，概率說X=xi的不確定性越大，反之越小，在機器學期中分類中說，熵越大即這個類別的不確定性更大，反之越小，當隨機變量的取值為兩個時，熵隨概率的變化曲線如下圖：

　　當p=0或p=1時，H(p)=0,隨機變量完全沒有不確定性，

? ? ? 當p=0.5時，H(p)=1,此時隨機變量的不確定性最大。

　　條件熵(conditional entropy)：表示在一直隨機變量X的條件下隨機變量Y的不確定性度量。

　　設隨機變量(X, Y)，其聯合概率分布為 P(X, Y) = p_ij(i=1,2, ... , n; j=1,2, ... , m)，隨機變量X給定的條件下隨機變量Y的條件熵H(Y|X)，定義為X給定條件下Y的條件概率分布的熵對X的數學期望：

H(Y|X)=∑ p_i*H(Y|X=x_i)

這里，p_i=P(X=x_i), i=1,2, ... , n.

　　2) 信息增益(information gain)

　　信息增益表示得知特征X的信息而使得類Y的信息的不確定性減少的程度。

　　特征A對訓練數據集D的信息增益g(D, A)，定義為集合D的經驗熵H(D)與特征A給定條件下D的經驗條件熵H(D|A)之差，即

g(D, A)=H(D)-H(D|A)

　　信息增益大的特征具有更強的分類能力。

　　3) 信息增益比(information gain ratio)

　　信息增益比g_R(D, A)定義為其信息增益g(D, A)與訓練數據集D關于特征A的值的熵H_A(D)之比，即

g_R(D, A)=g(D, A)/H_A(D)

其中，H_A(D)=-∑|D_i|/|D|*log₂|D_i|/|D|, n是特征A取值的個數。

　　4) 基尼指數(gini index)

　　分類問題中，假設有K個類，樣本屬于第k類的概率為p_k，則概率分布的基尼指數定義為：

Gini(p)=∑p_k(1-p_k)=1-∑p_k²

　　對于二分類問題，若樣本點屬于第1個類的概率是p，則概率分布的基尼指數為：

Gini(p)=2p(1-p)

　　對于給定的樣本集合D，其基尼指數為：

Gini(D)=1-∑(|C_k|/|D|)²

　　這里，C_k是D中屬于第k類的樣本子集，k是類的個數。

　　如果樣本集合D根據特征A是否取到某一可能值a被分割成D1和D2兩部分，則在特征A的條件下，集合D的基尼指數定義為：

Gini(D,A)=|D₁|/|D|*Gini(D₁)+|D₂|/|D|*Gini(D₂)

　　基尼指數Gini(D)表示集合D的不確定性，基尼指數越大，樣本集合的不確定性也就越大，這一點與熵相似。

3ID3、C4.5&CART

　　其實不同的決策樹學習算法只是它們選擇特征的依據不同，決策樹的生成過程都是一樣的(根據當前環境對特征進行貪婪的選擇)。

　　ID3算法的核心是在決策樹各個節點上應用信息增益準則選擇特征，每一次都選擇使得信息增益最大的特征進行分裂，遞歸地構建決策樹。

　　ID3算法以信息增益作為劃分訓練數據集的特征，有一個致命的缺點。選擇取值比較多的特征往往會具有較大的信息增益，所以ID3偏向于選擇取值較多的特征。

　　針對ID3算法的不足，C4.5算法根據信息增益比來選擇特征，對這一問題進行了校正。

　　CART指的是分類回歸樹，它既可以用來分類，又可以被用來進行回歸。CART用作回歸樹時用平方誤差最小化作為選擇特征的準則，用作分類樹時采用基尼指數最小化原則，進行特征選擇，遞歸地生成二叉樹。

　　決策樹的剪枝：我們知道，決策樹在生成的過程中采用了貪婪的方法來選擇特征，從而達到對訓練數據進行更好地擬合(其實從極端角度來看，決策樹對訓練集的擬合可以達到零誤差)。而決策樹的剪枝是為了簡化模型的復雜度，防止決策樹的過擬合問題。具體的決策樹剪枝策略可以參見李航的《統計學習方法》。

4Random Forest

　　隨機森林是一種集成學習+決策樹的分類模型，它可以利用集成的思想(投票選擇的策略)來提升單顆決策樹的分類性能(通俗來講就是“三個臭皮匠，頂一個諸葛亮”)。

　　集集成學習和決策樹于一身，隨機森林算法具有眾多的優點，其中最為重要的就是在隨機森林算法中每棵樹都盡最大程度的生長，并且沒有剪枝過程。

　　隨機森林引入了兩個隨機性——隨機選擇樣本(bootstrap sample)和隨機選擇特征進行訓練。兩個隨機性的引入對隨機森林的分類性能至關重要。由于它們的引入，使得隨機森林不容易陷入過擬合，并且具有很好得抗噪能力(比如：對缺省值不敏感)。

5GBDT

　　迭代決策樹GBDT(Gradient Boosting Decision Tree)也被稱為是MART(Multiple Additive Regression Tree))或者是GBRT(Gradient Boosting Regression Tree)，也是一種基于集成思想的決策樹模型，但是它和Random Forest有著本質上的區別。不得不提的是，GBDT是目前競賽中最為常用的一種機器學習算法，因為它不僅可以適用于多種場景，更難能可貴的是，GBDT有著出眾的準確率。這也是為什么很多人稱GBDT為機器學習領域的“屠龍刀”。

　　這么牛叉的算法，到底是怎么做到的呢？說到這里，就不得不說一下GBDT中的“GB”(Gradient Boosting)。Gradient Boosting的原理相當的復雜，但是看不懂它也不妨礙我們對GBDT的理解和認識，有關Gradient Boosting的詳細解釋請見wiki百科。

　　在這里引用另外一個網友的解釋來說明一下對GBDT中的Gradient Boosting的理解：

　　以下一段內容引自《GBDT(MART) 迭代決策樹入門教程 | 簡介》。

　　“Boosting，迭代，即通過迭代多棵樹來共同決策。這怎么實現呢？難道是每棵樹獨立訓練一遍，比如A這個人，第一棵樹認為是10歲，第二棵樹認為是0歲，第三棵樹認為是20歲，我們就取平均值10歲做最終結論？當然不是！且不說這是投票方法并不是GBDT，只要訓練集不變，獨立訓練三次的三棵樹必定完全相同，這樣做完全沒有意義。之前說過，GBDT是把所有樹的結論累加起來做最終結論的，所以可以想到每棵樹的結論并不是年齡本身，而是年齡的一個累加量。GBDT的核心就在于，每一棵樹學的是之前所有樹結論和的殘差，這個殘差就是一個加預測值后能得真實值的累加量。比如A的真實年齡是18歲，但第一棵樹的預測年齡是12歲，差了6歲，即殘差為6歲。那么在第二棵樹里我們把A的年齡設為6歲去學習，如果第二棵樹真的能把A分到6歲的葉子節點，那累加兩棵樹的結論就是A的真實年齡；如果第二棵樹的結論是5歲，則A仍然存在1歲的殘差，第三棵樹里A的年齡就變成1歲，繼續學。這就是Gradient Boosting在GBDT中的意義。”

　　其實從這里我們可以看出GBDT與Random Forest的本質區別，GBDT不僅僅是簡單地運用集成思想，而且它是基于對殘差的學習的。我們在這里利用一個GBDT的經典實例進行解釋。

　　假設我們現在有一個訓練集，訓練集只有4個人，A,B,C,D，他們的年齡分別是14,16,24,26。其中A、B分別是高一和高三學生；C,D分別是應屆畢業生和工作兩年的員工。如果是用一棵傳統的回歸決策樹來訓練，會得到如下圖1所示結果：

圖1

　　現在我們使用GBDT來做這件事，由于數據太少，我們限定葉子節點做多有兩個，即每棵樹都只有一個分枝，并且限定只學兩棵樹。我們會得到如下圖2所示結果：

圖2

　　在第一棵樹分枝和圖1一樣，由于A,B年齡較為相近，C,D年齡較為相近，他們被分為兩撥，每撥用平均年齡作為預測值。此時計算殘差(殘差的意思就是：A的預測值?+ A的殘差?= A的實際值)，所以A的殘差就是16-15=1(注意，A的預測值是指前面所有樹累加的和，這里前面只有一棵樹所以直接是15，如果還有樹則需要都累加起來作為A的預測值)。進而得到A,B,C,D的殘差分別為-1,1,-1,1。然后我們拿殘差替代A,B,C,D的原值，到第二棵樹去學習，如果我們的預測值和它們的殘差相等，則只需把第二棵樹的結論累加到第一棵樹上就能得到真實年齡了。這里的數據顯然是我可以做的，第二棵樹只有兩個值1和-1，直接分成兩個節點。此時所有人的殘差都是0，即每個人都得到了真實的預測值。

　　最后GBDT的預測結果為：

　　A: 14歲高一學生，購物較少，經常問學長問題；預測年齡A = 15 – 1 = 14；

　　B: 16歲高三學生；購物較少，經常被學弟問問題；預測年齡B = 15 + 1 = 16；

　　C: 24歲應屆畢業生；購物較多，經常問師兄問題；預測年齡C = 25 – 1 = 24；

　　D: 26歲工作兩年員工；購物較多，經常被師弟問問題；預測年齡D = 25 + 1 = 26。

　　那么哪里體現了Gradient呢？其實回到第一棵樹結束時想一想，無論此時的cost function是什么，是均方差還是均差，只要它以誤差作為衡量標準，殘差向量(-1, 1, -1, 1)都是它的全局最優方向，這就是Gradient。

　　注：

圖1和圖2 最終效果相同，為何還需要GBDT呢？答案是過擬合。過擬合是指為了讓訓練集精度更高，學到了很多“僅在訓練集上成立的規律”，導致換一個數據集當前規律就不適用了。只要允許一棵樹的葉子節點足夠多，訓練集總是能訓練到100%準確率的。在訓練精度和實際精度(或測試精度)之間，后者才是我們想要真正得到的。我們發現圖1為了達到100%精度使用了3個feature(上網時長、時段、網購金額)，其中分枝“上網時長>1.1h”?很顯然已經過擬合了，這個數據集上A,B也許恰好A每天上網1.09h, B上網1.05小時，但用上網時間是不是>1.1小時來判斷所有人的年齡很顯然是有悖常識的；相對來說圖2的boosting雖然用了兩棵樹?，但其實只用了2個feature就搞定了，后一個feature是問答比例，顯然圖2的依據更靠譜。

　　可見，GBDT同隨機森林一樣，不容易陷入過擬合，而且能夠得到很高的精度。

---

　　補充實例(2015-10-7)

　　在此引用李航博士《統計學習方法》中提升樹的實例來進一步闡述GBDT的詳細流程。

　　一直認為李航博士講的機器學習更加貼近算法的本質，我們先來看一下他是如何對GBDT進行定義的(在《統計學習方法中》，GBDT又被稱為是提升樹boosting tree)。

　　提升方法實際采用了加法模型(即基函數的線性組合)與前向分步算法。以決策樹為基函數的提升方法稱為提升樹，對分類問題決策樹是二叉分類樹，而對于回歸問題決策樹是二叉回歸樹。提升樹模型可以表示為決策樹的加法模型：

其中，表示決策樹；表示決策樹的參數；M為樹的個數。

　　針對不同問題的提升樹(GBDT)，其主要區別在于使用的損失函數不同，包括用平方誤差損失函數的回歸問題，用指數損失函數的分類問題，以及用一般損失函數的一般決策問題。

　　提升樹的流程：

? ?

　　下面我們通過一個實例來透徹地來看一下提升樹(GDBT)到底是怎樣一步一步解決問題的。

? ? ??

? ? ?

? ? ?

? ? ?

? ? ?

6參考內容

　　[1] 李航《統計學習方法》

　　[2]?GBDT(MART) 迭代決策樹入門教程 | 簡介

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的随机森林和gbdt结合_决策树与迭代决策树(GBDT)的全部內容，希望文章能夠幫你解決所遇到的問題。

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