決策樹的生成與剪枝CART

跟我一起機器學習系列文章將首發於公衆號：月來客棧，歡迎文末掃碼關注！

在之前的一篇文章中，筆者分別介紹了用ID3和C4.5這兩種算法來生成決策樹。其中ID3算法每次用信息增益最大的特徵來劃分數據集，C4.5算法每次用信息增益比最大的特徵來劃分數據集。接下來，我們再來看另外一種採用基尼指數爲標準的劃分方法，CART算法。

1 CART算法

分類與迴歸算法（Classification and Regression Tree,CAR），即可以用於分類也可以用於迴歸，它是應用最爲廣泛的決策樹學習方法之一。CART假設決策樹是二叉樹，內部節點特徵的取值均爲「是」和「否」，左分支是取值爲「是」的分支，右分支是取值爲「否」的分支。這樣的決策樹等價與遞歸地二分每個特徵，將輸入空間即特徵空間劃分爲有限個單元。

CART算法由以下兩步組成：

（1）決策樹生成：基於訓練數據集生成決策樹，生成的決策樹要儘量最大；

（2）決策樹剪枝：用驗證集對已生成的樹進行剪枝並選擇最優子樹，這時用損失函數最小作爲剪枝標準。

2 分類樹

在介紹分類樹的生成算法前，我們先介紹一下劃分標準基尼指數（gini index)。

2.1 基尼指數

在分類問題中，假設數據包含有 $K$K個類別，樣本點屬於第 $k$k類的概率爲 $\large p_{\small k}$pk​，則概率分佈的基尼指數定義爲：
$Gini(p)=\sum_{k=1}^K\large p_{\small k}(1-\large p_{\small k})=1-\sum_{k=1}^K\large p_{\small k}^2\tag{1}$Gini(p)=k=1∑K​pk​(1−pk​)=1−k=1∑K​pk2​(1)
因此，對於給定的樣本集合 $D$D，其基尼指數爲：
$Gini(D)=1-\sum_{k=1}^K\left(\frac{|C_k|}{|D|}\right)^2\tag{2}$Gini(D)=1−k=1∑K​(∣D∣∣Ck​∣​)2(2)
其中， $C_k$Ck​是 $D$D中屬於第 $k$k類的樣本子集， $K$K是類別的個數。

如果樣本集合 $D$D根據特徵 $A$A是否取某一可能值 $a$a被分割成 $D_1,D_2$D1​,D2​兩個部分，即
$D_1=\{(x,y)\in D|A(x)=a\},D_2=D-D_1$D1​={(x,y)∈D∣A(x)=a},D2​=D−D1​
則在特徵 $A$A的條件下，集合 $D$D的基尼指數定義爲（類似於條件熵的感覺）：
$Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)\tag{3}$Gini(D,A)=∣D∣∣D1​∣​Gini(D1​)+∣D∣∣D2​∣​Gini(D2​)(3)
基尼指數 $Gini(D)$Gini(D)表示集合 $D$D的不確定性，即表示經 $A=a$A=a分割後集合 $D$D的不確定性。基尼指數越大，樣本集合的不確定性也就越大，這點與信息熵相似。下圖是基尼指數、熵之半 $\frac{1}{2}H(p)$21​H(p)和分類誤差率之間的關係。橫座標表示概率，縱座標表示損失。可以看出基尼指數和熵之半的曲線很接近，都可以近似的表示分類誤差率。

2.2 生成算法

輸入：訓練數據集 $D$D，停止計算條件；

輸出：CART決策樹

根據訓練集，從根節點開始，遞歸地對每個節點進行如下操作，構建二叉決策樹：

（1）設節點的訓練集爲 $D$D，利用公式 $(2)$(2)計算現有特徵對該數據集的基尼指數。此時，對於每一個特徵 $A$A，對其可能的每一個值 $a$a，根據樣本點對 $A=a$A=a的測試爲「是」或「否」將 $D$D分割成 $D_1,D_2$D1​,D2​兩個部分，利用公式 $(3)$(3)計算 $A=a$A=a時的基尼指數；

（2）在所有可能的特徵 $A$A以及它們所有可能的切分點 $a$a中，選擇基尼指數最小的特徵作爲劃分標準將原有數據集劃分爲兩個部分，並分配到兩個子節點中去；

（3）對兩個子節點遞歸的調用(1),(2)，直到滿足停止條件；

（4）生成CART決策樹

其中，算法停止計算的條件是：節點中的樣本點個數小於預定閾值，或樣本集的基尼指數小於預定閾值（也就是說此時樣本基本屬於同一類），或者沒有更多特徵。

2.3 生成示例

同樣我們還是拿之前的數據集來走一遍生成流程：

$\begin{array}{c|cc} \hline ID&\text{年齡}&\text{有工作}&\text{有自己的房子}&\text{貸款情況}&\text{類別}\\ \hline 1&\text{青年}&\text{否}&\text{否}&\text{一般}&\text{否}\\ 2&\text{青年}&\text{否}&\text{否}&\text{好}&\text{否}\\ 3&\text{青年}&\text{是}&\text{否}&\text{好}&\text{是}\\ 4&\text{青年}&\text{是}&\text{是}&\text{一般}&\text{是}\\ 5&\text{青年}&\text{否}&\text{否}&\text{一般}&\text{否}\\ \hline 6&\text{中年}&\text{否}&\text{否}&\text{一般}&\text{否}\\ 7&\text{中年}&\text{否}&\text{否}&\text{好}&\text{否}\\ 8&\text{中年}&\text{是}&\text{是}&\text{好}&\text{是}\\ 9&\text{中年}&\text{否}&\text{是}&\text{非常好}&\text{是}\\ 10&\text{中年}&\text{否}&\text{是}&\text{非常好}&\text{是}\\ \hline 11&\text{老年}&\text{否}&\text{是}&\text{非常好}&\text{是}\\ 12&\text{老年}&\text{否}&\text{是}&\text{好}&\text{是}\\ 13&\text{老年}&\text{是}&\text{否}&\text{好}&\text{是}\\ 14&\text{老年}&\text{是}&\text{否}&\text{非常好}&\text{是}\\ 15&\text{老年}&\text{否}&\text{否}&\text{一般}&\text{否}\\ \hline \end{array}$ID123456789101112131415​年齡青年青年青年青年青年中年中年中年中年中年老年老年老年老年老年​有工作否否是是否否否是否否否否是是否​有自己的房子否否否是否否否是是是是是否否否​貸款情況一般好好一般一般一般好好非常好非常好非常好好好非常好一般​類別否否是是否否否是是是是是是是否​​

用 $D$D表示整個數據集， $A_1,A_2,A_3,A_4$A1​,A2​,A3​,A4​，分別依次表示四個特徵，用 $A_i=1,2,3...$Ai​=1,2,3...，表示每個特徵的可能取值；如 $A_2=1,A_2=2$A2​=1,A2​=2，表示有工作和無工作。

由公式 $(2)$(2)可知：
$\begin{aligned} Gini(D)=1-\sum_{k=1}^K\left(\frac{|C_k|}{|D|}\right)^2=1-\left[(\frac{6}{15})^2+(\frac{9}{15})^2\right]=2\times\frac{6}{15}\times\frac{9}{15}=0.48 \end{aligned}$Gini(D)=1−k=1∑K​(∣D∣∣Ck​∣​)2=1−[(156​)2+(159​)2]=2×156​×159​=0.48​

由公式 $(3)$(3)可知：
$Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$Gini(D,A)=∣D∣∣D1​∣​Gini(D1​)+∣D∣∣D2​∣​Gini(D2​)
求特徵 $A_1$A1​的基尼指數（注意，每次都是將其劃分爲兩部分，即 $A_i=a$Ai​=a和 $A_i\neq a$Ai​​=a）：
$\begin{aligned} Gini(D,A_1=1)&=\frac{5}{15}Gini(D_1)+\frac{10}{15}Gini(D_2)\\[1ex] &=\frac{5}{15}\left[2\cdot\frac{2}{5}\cdot(1-\frac{2}{5})\right]+\frac{10}{15}\left[2\cdot\frac{7}{10}\cdot(1-\frac{7}{10})\right]=0.44\\[1ex] Gini(D,A_1=2)&=\frac{5}{15}\left[2\cdot\frac{2}{5}\cdot\frac{3}{5}\right]+\frac{10}{15}\left[2\cdot\frac{4}{10}\cdot\frac{6}{10}\right]=0.48\\[1ex] Gini(D,A_1=3)&=\frac{5}{15}\left[2\cdot\frac{1}{5}\cdot\frac{4}{5}\right]+\frac{10}{15}\left[2\cdot\frac{5}{10}\cdot\frac{5}{10}\right]=0.44 \end{aligned}$Gini(D,A1​=1)Gini(D,A1​=2)Gini(D,A1​=3)​=155​Gini(D1​)+1510​Gini(D2​)=155​[2⋅52​⋅(1−52​)]+1510​[2⋅107​⋅(1−107​)]=0.44=155​[2⋅52​⋅53​]+1510​[2⋅104​⋅106​]=0.48=155​[2⋅51​⋅54​]+1510​[2⋅105​⋅105​]=0.44​

求特徵 $A_2,A_3$A2​,A3​的基尼指數:
$\begin{aligned} Gini(D,A_2=1)&=\frac{5}{15}\left[2\cdot\frac{5}{5}\cdot0\right]+\frac{10}{15}\left[2\cdot\frac{4}{10}\cdot\frac{6}{10}\right]=0.32\\[1ex] Gini(D,A_3=1)&=\frac{9}{15}\left[2\cdot\frac{6}{9}\cdot\frac{3}{9}\right]+\frac{6}{15}\left[2\cdot\frac{6}{6}\cdot0\right]=0.27\\[1ex] \end{aligned}$Gini(D,A2​=1)Gini(D,A3​=1)​=155​[2⋅55​⋅0]+1510​[2⋅104​⋅106​]=0.32=159​[2⋅96​⋅93​]+156​[2⋅66​⋅0]=0.27​

求特徵 $A_4$A4​的基尼指數:
$\begin{aligned} Gini(D,A_4=1)&=\frac{5}{15}\left[2\cdot\frac{1}{5}\cdot\frac{4}{5}\right]+\frac{10}{15}\left[2\cdot\frac{2}{10}\cdot\frac{8}{10}\right]=0.32\\[1ex] Gini(D,A_4=2)&=\frac{6}{15}\left[2\cdot\frac{2}{6}\cdot\frac{4}{6}\right]+\frac{9}{15}\left[2\cdot\frac{4}{9}\cdot\frac{5}{9}\right]=0.47\\[1ex] Gini(D,A_4=3)&=\frac{4}{15}\left[2\cdot\frac{4}{4}\cdot0\right]+\frac{11}{15}\left[2\cdot\frac{5}{11}\cdot\frac{6}{11}\right]=0.36 \end{aligned}$Gini(D,A4​=1)Gini(D,A4​=2)Gini(D,A4​=3)​=155​[2⋅51​⋅54​]+1510​[2⋅102​⋅108​]=0.32=156​[2⋅62​⋅64​]+159​[2⋅94​⋅95​]=0.47=154​[2⋅44​⋅0]+1511​[2⋅115​⋅116​]=0.36​

由以上計算結果我們可以知道， $Gini(D,A_3=1)=0.27$Gini(D,A3​=1)=0.27爲所有基尼指數中最小者，所有 $A_3=1$A3​=1爲最優劃分點。於是根節點生成兩個子節點，如下：

且我們發現對於「有房子左邊「是」這個子節點來說，已經滿足算法停止條件（均屬於同一類）；所有隻需對另外一個子節點繼續遞歸計算每個特徵取值情況下的基尼指數即可。並且，最終我們將得到與ID3算法所生成的決策樹完全一致。

2.3 剪枝算法

我們知道總體上來說，模型（決策樹）越複雜，越容易導致過擬合，此時對應的代價函數值也相對較小。 所以就要進行剪枝處理。CART剪枝算法由兩部組成：（1）首先是從之前生成的決策樹 $T_0$T0​底端開始不斷剪枝，直到 $T_0$T0​的根節點，形成一個子序列 $\{T_0,T_1,...,T_n\}${T0​,T1​,...,Tn​}；（2）然後通過交叉驗證對這一子序列進行測試，從中選擇最優的子樹。

下面的爲選讀內容，可自由選擇是否繼續閱讀（如果是第一次學習可不讀）

可以看出，第二步沒有什麼難點，關鍵就在於如何來剪枝生成這麼一個子序列.

（1）剪枝，形成一個子序列

在剪枝過程中，計算子樹的損失函數：
$C_{\alpha}(T)=C(T)+\alpha|T|\tag{4}$Cα​(T)=C(T)+α∣T∣(4)

其中， $T$T爲任意子樹， $C(T)$C(T)爲對訓練集的預測誤差， $|T|$∣T∣爲子樹的葉節點個數， $\alpha\geq0$α≥0爲參數。需要指出的是不同與之前ID3和C4.5中剪枝算法的 $\alpha$α，前者是人爲給定的，而此處則是通過計算得到，具體見後面。

具體地，從整體樹 $T_0$T0​開始剪枝。對 $T_0$T0​的任意內部節點 $t$t，以 $t$t爲根節點子樹 $T_t$Tt​（可以看作是剪枝前）的損失函數是:
$C_{\alpha}(T_t)=C(T_t)+\alpha|T_t|\tag{5}$Cα​(Tt​)=C(Tt​)+α∣Tt​∣(5)

以 $t$t爲單節點樹（可以看作是剪枝後）的損失函數是:
$C_{\alpha}(t)=C(t)+\alpha\cdot1\tag{6}$Cα​(t)=C(t)+α⋅1(6)

①當 $\alpha=0$α=0或者極小的時候，有不等式
$C_{\alpha}(T_t)< C_{\alpha}(t)\tag{7}$Cα​(Tt​)<Cα​(t)(7)

不等式成立的原因是因爲，當 $\alpha=0$α=0或者極小的時候，起決定作用的就是預測誤差 $C(t),C(T_t)$C(t),C(Tt​)，而模型越複雜其訓練誤差總是越小的，因此不等式成立。

②當 $\alpha$α增大時，在某一 $\alpha$α有
$C_{\alpha}(T_t)=C_{\alpha}(t)\tag{8}$Cα​(Tt​)=Cα​(t)(8)

等式成立的原因是因爲，當 $\alpha$α慢慢增大時，就不能忽略模型複雜度所帶來的影響（也就是式子 $(4)$(4)第二項。但由於相同取值的 $\alpha$α對於式子 $(5)(6)$(5)(6)所對應模型的懲罰力度不同（剪枝前的懲罰力度更大），因此儘管式子 $(5)(6)$(5)(6)所對應的模型複雜度均在減小（誤差變大），但是 $(5)$(5)較小得更快（誤差變大得更快），所以總有個時候等式會成立。

③當 $\alpha$α再增大時，不等式 $(8)$(8)反向。因此，當 $C_{\alpha}(T_t)=C_{\alpha}(t)$Cα​(Tt​)=Cα​(t)時，有 $\alpha=\frac{C(t)-C(T_t)}{|T_t|-1}$α=∣Tt​∣−1C(t)−C(Tt​)​，此時的子樹 $T_t$Tt​和單節點 樹 $t$t有相同的損失函數值，但 $t$t的節點少模型更簡單，因此 $t$t比 $T_t$Tt​更可取，即對 $T_t$Tt​進行剪枝。（注：此時的 $\alpha$α是通過 $C_{\alpha}(T_t)=C_{\alpha}(t)$Cα​(Tt​)=Cα​(t)計算得到)

爲此，對決策樹 $T_0$T0​中每一個內部節點 $t$t來說，都可以計算
$g(t)=\frac{C(t)-C(T_t)}{|T_t|-1}\tag{9}$g(t)=∣Tt​∣−1C(t)−C(Tt​)​(9)

它表示剪枝後整體損失函數減少的程度。因爲每個 $g(t)$g(t)背後都對應着一個決策樹模型，而不同的 $g(t)$g(t)則表示損失函數變化的不同程度。接着，在樹 $T_0$T0​中減去 $g(t)$g(t)最小的子樹 $T_t$Tt​，將得到的子樹作爲 $T_1$T1​。如此剪枝下去，直到得到根節點。

注意，此時得到的一系列 $g(t)$g(t)即 $\alpha$α，都能使得在每種情況下剪枝前和剪枝後的損失值相等，因此按照上面第③種情況中的規則要進行剪枝，但爲什麼是減去其中 $g(t)$g(t)最小的呢？如下圖：

對於樹 $T$T來說，其內部可能的節點 $t$t有 $t_0,t_1,t_2,t_3$t0​,t1​,t2​,t3​； $t_i$ti​表示其中任意一個。因此我們便可以計算得到 $g(t_0),g(t_1),g(t_2),g(t_3)$g(t0​),g(t1​),g(t2​),g(t3​)，也即對應的 $\alpha_0,\alpha_1,\alpha_2,\alpha_3$α0​,α1​,α2​,α3​。從上面的第③種情況我們可以知道， $g(t)$g(t)是根據公式 $(9)$(9)所計算得到，因此這四種情況下 $t_i$ti​比 $T_{t_i}$Tti​​更可取，都滿足剪枝。但是由於以 $t_i$ti​爲根節點的子樹對應的複雜度各不相同，也就意味着 $\alpha_i\neq\alpha_j,(i,j=0,1,2,3;i\neq j)$αi​​=αj​,(i,j=0,1,2,3;i​=j),即 $\alpha_i,\alpha_j$αi​,αj​存在着大小關係。又因爲我們知道：當 $\alpha$α大的時候，最優子樹 $T_{\alpha}$Tα​偏小；當 $\alpha$α小的時候，最優子樹 $T_{\alpha}$Tα​偏大；且子樹偏大意味着擬合程度更好。因此，在都滿足剪枝的條件下，選擇擬合程度更高的子樹當然是最好的選擇。所有選擇減去其中 $g(t)$g(t)最小的子樹。

在得到子樹 $T_1$T1​後，再通過上述步驟對 $T_1$T1​進行剪枝得到 $T_2$T2​。如此剪枝下去直到得到根節點，此時我們便得到了子樹序列 $T_0,T_1,T_2,....T_n$T0​,T1​,T2​,....Tn​。

（2）交叉驗證選擇最優子樹 $T_{\alpha}$Tα​

通過第（1）步我們便可以得到一系列的子樹序列 $T_0,T_1,...,T_n$T0​,T1​,...,Tn​，然後便可以通過交叉驗證來選取最優決的策樹 $T_{\alpha}$Tα​。

最後，通過sklearn來完成對於CART分類樹的使用也很容易，只需要將類DecisionTreeClassifier()中的劃分標準設置爲criterion="gini"即可，其它地方依舊不變，可參見上一篇文章。

3 總結

在這篇文章中， 筆者首先介紹了什麼是CART算法，進一步介紹了CART分類樹中的劃分標準基尼指數；接着詳細介紹了CART分類樹的生成過程，通過示例展示整個流程；最後介紹了CART分類樹剪枝過程的基本原理。本次內容就到此結束，感謝閱讀！

若有任何疑問與見解，請發郵件至[email protected]並附上文章鏈接，青山不改，綠水長流，月來客棧見！

引用

[1]《統計機器學習（第二版）》李航，公衆號回覆「統計學習方法」即可獲得電子版與講義

[3]《Python與機器學習實戰》何宇健