決策樹CART、ID3、C4.5原理梳理

《老餅講解機器學習》

http://ml.bbbdata.com/teach#108

目錄

一. 學習決策樹原理的順序

二.CART分類樹

(一)分類樹模型結構

(二).分類樹建構過程

(二).剪枝(防止過拟合）

三. CART回歸樹模型

四. ID3算法

五.C4.5算法

(一) ID3的缺陷

(二) C4.5打上更新檔

六.決策樹演進與對比

能來看算法原理的，估計都對決策樹有一些初步了解了。

決策樹算法原理其實非常簡單， 但由于網上雜文過多，往往把概念弄得非常混亂，造成原理了解困難。

本文對原理進行簡單介紹與梳理 。

一. 學習決策樹原理的順序

決策樹算法有CART,ID3,C4.5 幾種,如果把多種算法原理概念混在一起，必然很難了解。

思想起源來自于ID3，是以一般會先介紹ID3，但我建議不要從ID3入手，學習路線線最好如下安排：

了解CART分類樹---->了解CART回歸樹--->了解ID3算法---->了解C4.5算法。

為什麼先了解CART分類樹

(1) matlab,python的sklearn都隻實作CART算法，沒有ID3,C4.5算法。

(2)CART和ID3(c4.5)是兩條支線。現在人們所說的決策樹，現在基本都是暗指CART，而非ID3,C4.5，是以沒有必要糾結着ID3,C4.5不放。

重要的事說三遍， 先了解CART,先了解CART，先了解CART，再了解ID3,C4.5。

CART更加成熟，更加合理，更加實用，更加容易了解，越不成熟，越不合理的東西越難了解。

(3)CART(classification and regression tree)望文思義就是分類與回歸樹，使用得更多的是分類樹，而回歸樹是在分類樹的基礎上的改動成适用于回歸問題。

二.CART分類樹

(一)分類樹模型結構

CART分類樹的結構就是一棵二叉樹，每個節點有一個變量與一個判斷值，該變量<=值，則判為左節點，否則為右節點。

樹的訓練則是指建構這樣一棵樹，使它能夠較好的預測新樣本。

(二).分類樹建構過程

建構過程是逐節點建構的方式,直到所有樣本都配置設定到葉子節點，即完成樹的建構。

建構樹的核心問題是：

（1）節點是作為葉子，還是繼續分裂（即葉子準則）。

（2）如果分裂，該選擇哪個變量作為判斷值，變量的門檻值是多少。

（3）葉子節點的所屬類别是哪個。

是以，建構樹是一個while循環過程，例如一開始根節點是150個樣本，則開始while循環，

如圖所示，根據分裂準則，确定了變量與門檻值，則可把根節點分為左右兩個子節點，假設現在50個配置設定到左節點，100個配置設定到右節點。

再根據葉子準則，判斷到左節點是葉子，不再分裂。右節點不是葉子，則繼續把這100個樣本分裂...直到所有樣本都落在葉子節點。

現在，隻要确定以上三個核心問題即可。

1.葉子準則

(1) 節點樣本<min_samples_split則作為葉子

(2) 超過了樹分枝最大深度max_depth，則作為葉子

(3) 其它類似的條件。

2.确定節點變量與門檻值

分裂選擇哪個變量，和門檻值是多少？

這個問題極其簡單，先定一個分裂收益評估函數，把所有變量和門檻值的可能組合都代進去算一遍，哪個收益大，就用哪組[變量，門檻值]，

怎麼比較哪種分裂效果更好？主要評估子節點的清晰度。如果左節點上全是A類，那左節點就很清晰了。如果左節點上A，B兩類各占50%，那就還不是很明朗。

也即是，從節點中任意抽取兩個樣本，這兩個樣本不屬同一類的機率

（這機率的怎麼來的後面會放連結）越小說明節點分得越清晰,這個機率稱為基尼系數(GINI)。

分裂後有左右兩個節點，取兩個節點的權重機率即可

G越小，就代表分得越清晰。（如果是定義收益函數，收益函數需要越大越好，則取上式相反數）

通過比較每種分裂的GINI系數，最後取GINI系數（即在左/右節點随機抽兩個樣本，兩個樣本不屬同一類的機率）最小的分裂對應的[特征-門檻值] 即可。

3.葉子節點類别判定

葉子節點上的樣本，哪類樣本最多，葉子就屬于哪一類。

在建構完樹後，預測時隻要判斷新樣本落在哪個葉子，就預測為哪一類。

至此，CART回歸樹的建樹原理就結束了。

(二).剪枝(防止過拟合）

剪枝分為預剪枝和後剪枝，

1.預剪枝

預剪枝就是在建構樹過程設定一個條件，防止節點分度分裂，好家夥，其實就是葉子準則，設嚴此，就是預剪枝了。

2.後剪枝

後剪枝就是在樹建構完後再剪掉一些葉子節點。通常使用的是CCP（Cost Complexity Pruning）後剪枝法。

損失函數定義為樹的代價+複雜度：

其中



 ：葉子節點個數 



 ：所有樣本個數

 ：第 i 個葉子節點上的樣本數 



 ： 第i個葉子節點的損失函數（常用的有：錯誤占比，GINI系數，和熵。）

α  ：待定系數，用于懲罰節點個數，引導模型用更少的節點。

然後根據損失函數進行剪枝，使 L最小。

後剪枝是使用者的後期操作，是以程式一般隻提供一條 \alphaα的所有可能取值，與對應的葉子權重損失函數

的值，供使用者自行選擇α 。

具體計算方法參考《決策樹後剪枝原理：CCP剪枝法》。

三. CART回歸樹模型

決策樹用于回歸

回歸與分類的不同，在于回歸的輸出變量y為連續數值變量。

整體算法類似于分類樹，關鍵有以下兩點修改：

（1）葉子節點輸出的不是類别，而是節點上所有y的均值。

（2）構樹過程中節點分割評估不用基尼指數，改用 平方差

至此，CART回歸樹也就講完了。資訊熵呢？資訊增益比呢？怎麼沒有講？那是ID3,C4.5的概念。是以說不要混在一起~！ 

四. ID3算法

ID3與CART分類樹的差異：

1.樹結構不同：ID3決策樹模型也是一棵樹。輸入變量必須全是枚舉型。每個節點選擇一個變量，按該變量所有可能取值分叉。

2.輸入變量不同：CART是連續變量，用門檻值切割，而ID3輸入變量必須全是枚舉型。按變量所有可能取值分叉。

3.分叉依據不同：ID3是全分叉，是以沒有門檻值一說，僅需比較不同變量的分叉品質即可。

分叉依據的是資訊增益(Gain)：

   ： 分叉子節點個數

    ： 所有子節點的總樣本數（也即父節點的樣本數）

   ： 第 i 個子節點上樣本個數

 ：第 i 個子節點上第k類樣本的個數

  ：父節點上第 k 類樣本的個數

其中

稱為熵。

4.沒有剪枝：對，ID3是較原始的一個算法，沒有剪枝。

五.C4.5算法

C4.5就是對ID3的補充，就是對ID3打更新檔

(一) ID3的缺陷

(1)變量偏好多枚舉值：

ID3更偏好優先分叉枚舉值多的變量。因為ID3用資訊增益評估分叉品質，該評估函數會更偏好枚舉值多的變量。

(如果變量A有2個枚舉，B有10個枚舉，肯定就偏好B了，因為B一下子把節點分叉成10個子節點，而A隻分成2個子節點。分成10個子節點的确定性肯定比2個會更強些。)

(2) ID3容易過拟合。

(3) ID3不支援連續變量。

(4) 不支援資料有缺失值。

(二) C4.5打上更新檔

(1) 變量偏好糾正：使用資訊增益比

資訊增益比：

分子就是ID3中的資訊增益， 分母則是全體樣本中變量v的熵

分母符号說明：



  :  全體樣本（劃重點，是全體樣本）變量v的枚舉個數



  :  全體樣本個數。



 ：全體樣本變量v第k個枚舉值的樣本個數。

(2) 過拟合處理:添加剪枝

剪枝方法就是CART中所說的CCP,與CART不同的是，損失函數中節點的損失用熵函數，而不是GINI。

(3) 連續變量處理：與CART類似。

(4)變量有缺失值的處理：很複雜和别扭。

六.決策樹演進與對比

1.樹結構：ID3不是二叉樹,C4.5在輸入是連續變量時是二叉樹，CART一定是二叉樹。非二叉樹都可以用二叉樹替代，統一用二叉樹更加簡單優雅。

2.分裂依據：ID3分裂時用熵，C4.5用熵增益，CART用GINI。GINI很容易了解，就是抽出兩個樣本不屬同一類的機率。GINI沒有log，計算也友善。（熵也可遷移到CART中用，但CART更偏向用GINI）。

3.特征資料類型：ID3的輸入變量是枚舉類型，C4.5是枚舉與數值相容，CART是數值類型。完全抛棄了枚舉，是因為枚舉型問題可以轉化為數值類型問題。

4.缺失值支援：ID3不支援缺失值，C4.5支援缺失值，CART不支援缺失值。最後抛棄了缺失值的相容，是缺失值處理極其複雜與不夠優雅。統一在入模前把缺失問題處理，更加清晰，可控。

5.剪枝：ID3沒有剪枝，C4.5有剪枝，CART有剪枝。

備注：一般軟體包(python,matlab)隻支援CART,不支援ID3,C4.5

相關文章

《深入淺出:決策樹入門簡介》

《一個簡單的決策樹分類例子》

《sklearn決策樹結果可視化》

《sklearn決策樹參數詳解》