cart算法_算法思想與硬核推導：決策樹（ID3/C4.5/CART）

概括

決策樹的訓練過程是在樣本集中，選擇目前對樣本集最重要的特征并對其進行分割得到子節點的疊代過程，最終生成的樹模型将相似樣本聚集在一起成為葉子節點，以葉子節點的目标

作為該葉子節點的标簽，預測過程就是根據決策樹對樣本的劃分規則确定測試樣本所屬的葉子節點，而後以葉子節點标簽為預測值。

定義

決策樹是一個if-else規則集合，一個執行個體（樣本）進入已訓練好的決策樹後每次基于一個特征進行劃分最終落入一個葉子節點中，該執行個體的預測結果以該葉子節點結果值為預測值。是以可以将決策樹看做特征子空間到預測值的映射關系模型。

特征空間劃分與預測結果（label）映射關系

分類問題

決策樹一開始是為了解決分類問題，對于決策樹的建構有如下兩個問題：

1. 如何選擇最合适的特征
2. 選擇特征後如何進行劃分

ID3

ID3所需基礎：資訊增益

1.資訊量：資訊量定義了機率為p的事件發生時所産生的資訊量大小，表達式如下：

通俗解釋：一個發生機率很低的事件發生時産生很大的資訊量，反之發生機率很高的時間發生時産生較低的資訊量，log(p)函數圖像如下：

事間機率越高（越接近1），産生的資訊量越小

2.熵：評價某個随機變量的混亂程度，表達式為資訊量的期望（log=ln）：

通俗解釋：如果随機變量的機率分布比較‘極端’如 X=太陽是否升起，p(X=升)=0.99，p(X=不升)=0.01，H(X) = -0.01log(0.01) - 0.99log(0.99) = 0.056。即該随機變量有很小的混亂程度。若X為擲硬币事件，設正反機率均0.5，H(X) = -0.5log(0.5) - 0.5log(0.5) = log(2) = 0.692，随機變量取值若等機率則得到最大熵（随機變量最為混亂）。

3.條件熵：

通俗解釋：假設分類問題為依據汽車特征将汽車分類為：Y={轎車、SUV、皮卡、挖掘機}，樣本特征之一燃油類型為：X={汽油、柴油、EV}，條件熵的計算相當于計算每個具體燃油類别下的汽車類别Y的熵 H(Y) 記為

，然後求該熵對燃油類型的數學期望。

4.資訊增益：

通俗解釋：樣本集D的目标變量Y的熵 - 目标變量Y在特征X下的條件熵，相當于我用特征X對Y進行切分後，系統的熵的減小幅度（系統混亂程度減小幅度）。

5.資訊增益比：

通俗解釋：資訊增益傾向選擇種類多的特征，想象一個訓練集有一列index表示樣本編号，可将其看做特征，每個index對應一個樣本，是以每個index下H(Y)即

，是以index條件熵

，資訊增益達到最大，但index特征對于樣本集毫無用處，是以需要對類别數多的特征進行懲罰，除以該特征的熵（類别數越多，分布越均勻則熵越大越接近log(n)懲罰力度越大）。

第一個問題：如何選擇最合适的特征

ID3基于資訊增益，每次從可選特征集合中選擇資訊增益最大的特征然後可選特征集合删除該特征。

第二個問題：如何劃分

ID3直接在標明特征下依據特征種類劃分為多叉樹。

算法的過程為：

1).初始化資訊增益的門檻值ϵ

2).判斷樣本是否為同一類輸出

，如果是則傳回單節點樹T。标記類别為

3).備選特征是否為空，如果是則傳回單節點樹

，标記類别為樣本執行個體數最多的類别

4).計算集

中各個特征（一共n個）對目标變量

的資訊增益，選擇其值最大的特征

5).若A的資訊增益小于門檻值ϵ，則傳回單節點樹

，标記類别為樣本執行個體數最多的類别

6).否則，按特征

的不同取值

将

分成不同子集

。每個子節點對應特征值為

，傳回增加的節點數T。

7).對于所有的子節點，令

,備選特征集-

，遞歸調用2-6步，得到子樹

傳回。

ID3分類決策樹使用限制與不足：

1. 樣本特征均為離散特征
2. 特征需要無缺失值
3. 無正則化項，易過拟合

C4.5

C4.5基本流程和ID3相同，但C4.5是基于資訊增益比且可處理連續特征與特征值缺失問題。

1.連續特征處理（切分為兩類）：假設樣本集大小為m，連續特征為A，按特征A從小到大排序樣本，以相鄰樣本均值為切分點，前半部A為

後半部分為

，計算

最大時的切分點，以該值為A的資訊增益比，另外已選的連續特征仍可參與後需的特征選擇。

2.缺失值處理：

1).特征資訊增益計算問題：假設特征A有40%的缺失率，那麼利用無特征A缺失的60%的樣本集計算

，特征A的資訊增益比可記為

。

2).樣本劃分問題： 假設

最大且A有兩種離散值或連續特征對應的兩類切分

，對60%無特征A缺失的樣本正常劃分為兩個子集

，40%特征A缺失的樣本劃分到全部兩個子集中但同一樣本在兩個子集的權重分别為

和

，參與機率計算時将樣本視為0.x個即可。

3.剪枝：後面統一讨論。

C4.5分類決策樹使用限制與不足（同時也是ID3的缺陷）：

1. 生成的是多叉樹，在這些資料量小的切分空間上，統計資訊較不準确，樹模型複雜易過拟合，泛化性能較差，且多叉樹不利于程式優化。
2. 隻能用于分類。
3. 都使用熵模型，對待分化集合每種特征的每種取值計算log值，代價高。
4. C4.5的連續值需要排序，每次排序需要O(nlogn)，n為待排序集合大小。

CART

CART與ID3、C4.5有較大差别

1. CART標明特征後僅分裂為兩個子節點 而非ID3/C4.5每個特征值分裂一個節點。
2. CART可回歸。
3. 分裂依據為計算更高效的基尼不純度。

CART分類所需基礎：基尼不純度

1.基尼系數

假設樣本集

有K個類别，第k個類别的機率為

, 基尼系數的表達式為：

是以

均等時

取最小值，即樣本集類别機率分布越均勻，基尼系數越高，資料整體越‘不純’越混亂，基尼系數和熵的作用類似，但計算從log變為平方。

在K=2時，1/2H(D)和Gini(D)曲線類似

2.特征A的條件下，把樣本集

分成

兩部分，特征A條件下基尼系數表達式為：

通俗解釋：根據條件熵的定義，可以将其了解為條件基尼系數，隻不過這裡隻有兩部分。

第一個問題：如何選擇最合适的特征，第二個問題：如何劃分（二切分需搜尋最優切分點）

1. CART将兩個問題合并，1).對于離散特征，不同于ID3/C4.5，CART是二切分，依據特征值枚舉所有二切分情況，選擇條件基尼系數最小的二切分方式為切分依據。2).對于連續特征，除評判依據變為條件基尼系數外同C4.5，條件基尼系數最小時得到最佳切分點。
2. 選擇條件基尼系數最小的特征進行二切分。

被選擇過的離散特征同樣可參與後續的特征選拔

，因為CART是二切分，ID3/C4.5是完備切分，除非節點樣本集該離散特征取值唯一，否則就還有切分價值，缺失值處理同C4.5。

1).目前節點的資料集為

，如果樣本個數小于門檻值或者沒有特征，則傳回決策子樹。

2).計算樣本集

的基尼系數，如果基尼系數小于門檻值，則傳回決策樹子樹，停止遞歸。

3).計算目前節點現有的各個特征對資料集

依據條件基尼系數計算最優切分點。

4).依據最優特征和特征最優切分方式把資料集

劃分成左右節點

。

5).對左右的子節點遞歸的調用1-4步，生成決策樹。

回歸問題

CART除了分類也可以回歸，建立CART回歸樹時不再利用基尼指數作為特征選擇依據是使用平方誤差。

CART回歸所需基礎：最小平方誤差

通俗解釋：在某特征下選擇最佳二切分政策，使得切分後的兩個子集的平方誤差（相對于子集各自均值）和最小。然後選出效果最好的特征A。

将CART回歸和CART分類看做一種模型，兩者差別在于CART回歸的劃分依據為平方誤差，然後回歸以葉子節點樣本均值為預測結果，分類以樣本數最多的label為預測結果，其餘相同。

離散特征問題

CART涉及到離散特征最優切分政策查找，單純枚舉所有二切分方式查找其時間複雜度為指數為特征值數量k的指數級複雜度，而且現有sklearn和XGboost均不支援識别離散特征，是以需要對離散特征數值化。

1. 離散特征若有序列關系，直接編碼即可。
2. 如果是做樹回歸或二分類（可看做label有數值大小關系），可以按照每個類别值對應的label均值（leave-me-out，否則将本身的label算進去相當于資料洩露了）進行排序，相當于利用label均值對離散特征進行數值化處理，然後按照排序的結果依次枚舉最優分割點。
3. 多分類時，離散特征取值較少時可one-hot，較多且分布均勻時由于one-vs-rest導緻切分意義不大。
4. 多分類時，離散特征取值較多時可做embedding、自編碼、改為one-vs-rest二分類問題。

後剪枝

目标函數

對于不同的樹模型，其損失函數的形式是相同的，假設樹為

,葉子節點數為

,葉子節點

含有

個樣本，樹的訓練誤差為

,正則項即為

對于ID3/C4.5可以葉子節點資料集熵的權重和為訓練誤差

通俗解釋：熵的權重和越小說明樹對訓練集拟合效果越好，樹模型使得整體資料分布非常有規矩。正則項希望樹的節點少一些，增強樹的泛化性能。

對于CART分類，訓練誤差是葉子節點資料集基尼不純度系數權重和

對于CART回歸，訓練誤差是所有樣本平方誤差總和

剪枝

當α=0時，即沒有正則化，原始的生成的CART樹即為最優子樹。當α=∞時，即正則化強度最大，此時單節點樹為最優子樹。對于固定的α，一定存在使損失函數

最小的唯一子樹。

對于決策

中任意一顆子樹

（不是葉子節點），如果沒有剪枝，它的損失是：

如果将其剪掉，退化為根節點

，則損失是：

當α較小時正則強度小，是以不剪枝的整體結構損失值

小，若α增大，

相對于

迅速變大直到

，此時有：

針對子樹

此時

足夠大到剪枝和不剪枝兩者損失值相等，同時對于整體樹

而言也是如此（訓練損失增加

，正則損失減少

）

，子樹

損失值的變化就是整體樹

的變化，但剪枝後整體樹

的節點樹減少，樹更加單，泛化能力更強。

算法流程

對決策樹除葉子節點外所有節點代表的子樹

計算該

門檻值

:

1. 對所有計算的

   

   排序，

   

   從0起每次取值為最小

   

   值。
2. 對上步

   

   對應的節點剪枝得到剪枝樹

   

   ，剪之後

   

   不變。
3. 不斷重複至

   

   退化為單節點（此時對應一個很大的α）得到剪枝樹集合{

   

   }，對應的α為{

   

   }。
4. 上步剪枝樹集合對應的結構化誤差相等，采用交叉驗證選擇最優子樹

   

   。

reference

《統計學習方法》-李航

決策樹算法原理(上) - 劉建平Pinard - 部落格園

決策樹算法原理(下) - 劉建平Pinard - 部落格園

一文搞懂交叉熵在機器學習中的使用，透徹了解交叉熵背後的直覺_史丹利複合田的部落格-CSDN部落格

關于sklearn中的決策樹是否應該用one-hot編碼？

cart樹怎麼進行剪枝