機器學習回顧篇（8）：CART決策樹演算法

• 2019 年 11 月 1 日
• 筆記

註：本系列所有部落格將持續更新並發布在github和gitee上，您可以通過github、gitee下載本系列所有文章筆記文件。

1 引言

上一篇部落格中介紹了ID3和C4.5兩種決策樹演算法，這兩種決策樹都只能用於分類問題，而本文要說的CART（classification and regression tree）決策樹不僅能用於分類問題，也能用於回歸問題。

與ID3演算法和C4.5演算法相比，CART 還有個特性就是其所有非葉子結點都只有兩個子樹，也就是說在根據特徵屬性分裂數據集時，無論該特徵屬性有多少個可能取值，都只有兩種選擇——‘是’和‘否’，以上文中判斷是否是程式設計師數據集為例，如果根據近視程度進行分裂，可以將數據集分為{‘輕微’}和{‘中等’，‘嚴重’}兩個數據集（當然也可以是其兩種組合）然後在進一步迭代中進一步細化分數據集。

下面，我們分別說說CART演算法如何解決分類問題和回歸問題。

2 分類問題

對於分類問題，CART演算法採用基尼指數作為最優分裂特徵屬性選擇標準。

先來說說基尼指數，與熵一樣，基尼指數越小則數據集不確定性越小，代表著數據集純度越高。給定數據集$X$包含$L$個分類，那麼數據集$X$的基尼指數為：

 $$Gini(X) = sumlimits_l^L {frac{{|{X_l}|}}{{|X|}}(1 – frac{{|{X_l}|}}{{|X|}})}  = 1 – {sumlimits_{l = 1}^L {left( {frac{{|{X_l}|}}{{|X|}}} right)} ^2}$$

假設$A$是數據集$X$中包含若干個可能取值的一個特徵屬性，$a$是$A$的其中一個可能取值，將數據集$X$按照$a$進行劃分，就可以分為兩個數據集，分別是${X_1} = left{ {x in X|{x_A} = a} right}$和${X_2} = left{ {x in X|{x_A} ne a} right}$，那麼在特徵$A$下，集合$X$的基尼指數為：

$$Gini(X,A) = left| {frac{{{X_1}}}{X}} right|Gini({X_1}) + left| {frac{{{X_2}}}{X}} right|Gini({X_2})$$

接下來，我們通過實例演示如果應用基尼指數選擇最優分裂特徵屬性。還是使用上篇部落格中介紹ID3演算法時使用過的數據集，如下所示。先來計算三個特徵屬性各個可能取值的基尼指數。

對屬性$A$的“穿格子襯衫”這個值計算基尼指數：

$$Gini(X,{A_1}) = frac{5}{{10}} times left{ {2 times frac{4}{5} times frac{1}{5}} right} + frac{5}{{10}} times left{ {2 times frac{3}{5} times frac{2}{5}} right} = 0.4$$

對屬性$A$的“不穿格子襯衫”這個值計算基尼指數，由於只有兩個屬性，無論按照哪個屬性來計算結果都一樣，所以：

$$Gini(X,{A_2}){text{ = }}Gini(X,{A_1}) = 0.4$$

對屬性$B$的“嚴重”這個值計算基尼指數：

$$Gini(X,{B_1}) = frac{3}{{10}} times left{ {2 times frac{2}{3} times frac{1}{3}} right} + frac{7}{{10}} times left{ {2 times frac{5}{7} times frac{2}{7}} right} = 0.42$$

對屬性$B$的“中等”這個值計算基尼指數：

$$Gini(X,{B_2}) = frac{4}{{10}} times left{ {2 times frac{4}{4} times frac{0}{4}} right} + frac{6}{{10}} times left{ {2 times frac{3}{6} times frac{3}{6}} right} = 0.3$$

對屬性$B$的“輕微”這個值計算基尼指數：

$$Gini(X,{B_3}) = frac{3}{{10}} times left{ {2 times frac{1}{3} times frac{2}{3}} right} + frac{7}{{10}} times left{ {2 times frac{6}{7} times frac{1}{7}} right} = 0.46$$

對屬性$C$的“嚴重”這個值計算基尼指數：

$$Gini(X,{C_1}) = frac{3}{{10}} times left{ {2 times frac{0}{3} times frac{3}{3}} right} + frac{7}{{10}} times left{ {2 times frac{4}{7} times frac{3}{7}} right} = 0.34$$

對屬性$C$的“中等”這個值計算基尼指數：

$$Gini(X,{C_2}) = frac{3}{{10}} times left{ {2 times frac{1}{3} times frac{2}{3}} right} + frac{7}{{10}} times left{ {2 times frac{5}{7} times frac{2}{7}} right} = 0.42$$

對屬性$C$的“輕微”這個值計算基尼指數：

$$Gini(X,{C_3}) = frac{3}{{10}} times left{ {2 times frac{1}{3} times frac{2}{3}} right} + frac{7}{{10}} times left{ {2 times frac{6}{7} times frac{1}{7}} right} = 0.46$$

可見，屬性$B$的“中等“取值時具有最小的基尼指數，所以這個值作為當前數據集的最優分裂特徵屬性值。分裂後，可以獲得兩個數據集，對獲得的數據集繼續計算基尼指數，選擇最優分裂特徵屬性值，如此迭代形成一顆完整的決策樹。

對於連續型特徵屬性，可以參照C4.5演算法對連續型特徵屬性的處理方法，只不過在CART演算法中是計算基尼指數。

3 回歸問題

此時，我們研究的已經是回歸問題了（關於回歸與分類，在討論線性回歸演算法的時候已經分析過，如果還不清楚，傳送門走起，所以，請轉變思路，對於任意一個$x in X$，經過決策樹後的輸出$f(x)$的可能取值已經不再像之前的分類決策樹那樣，$f(x)$的取值只可能是在$X$中出現過的那幾種取值，回歸樹最後的輸出$f(x)$可能是之前沒有出現過的，甚至連可能值的個數都不固定。所以，對於回歸樹，首先解決的問題就是如何確定$f(x)$的可能值。

對於數據集$X$，假設我們在其特徵屬性$A$上早上一個值$a$將數據集劃分成兩類：

$${X_1} = { x|{x_A} leqslant a} $$

$${X_2} = { x|{x_A} > a} $$

在這兩個類上的輸出值$f(x)$分別為${c_1}$和${c_2}$，那麼根據特徵屬性$A$的值$a$對$X$進行劃分，所產生的總誤差是：

$$Los{s_{A,a}} = sumlimits_{x in {X_1}} {(y – {c_1}} {)^2} + sumlimits_{x in {X_2}} {(y – {c_2}} {)^2}$$

式中，$y$是$x$對應的真實值。我們的目標就是使得$Los{s_{A,a}}$最小化時的${c_1}$和${c_2}$，目標函數為：

$${min sumlimits_{x in {X_1}} {{{(y – {c_1})}^2}}  + min sumlimits_{x in {X_2}} {{{(y – {c_2})}^2}} }$$

那麼，當${c_1}$和${c_2}$取什麼值的的時候$Los{s_{A,a}}$最小呢？根據最小二乘的性質可知，當${c_1}$和${c_2}$分為為${X_1}$和${X_2}$中所有$y$的平均值的時候${c_1}$和${c_2}$去的最小值，即：

$${c_i} = ave(y|x in {X_i})$$

所以，如果根據$a$劃分之後得到的是葉子結點，那麼最終輸出的值就是所屬樣本子集所有$y$的平均值。

$$f(x)={c_i} = ave(y|x in {X_i})$$

對數如何確定輸出值的問題，就已經解決了。接下來還剩兩個個問題需要解決，那就是選擇哪個屬性作為最優分割特徵屬性以及選擇哪個值作為最佳的分割點。

對於這個問題，可以通過遍曆數據集各特徵屬性的可能取值的方式來解決：對數據集$X$中各特徵屬性$A$，計算其所有取值$a$下的$Los{s_{A,a}}$，然後對比所有$Los{s_{A,a}}$，取值最小的$Los{s_{A,a}}$所對應的特徵屬性$A$為當前最優分裂特徵屬性，$a$為最佳分裂點。

至此，如何確定各分支的輸出值、如何選擇最優分割特徵屬性和分割點的問題都已解決，最後總結一下CART演算法在回歸問題中的決策樹構建流程：

（1）對當前數據集$X$，計算所有特徵屬性$A$下所有取值$a$作為分割點時的最小$Los{s_{A,a}}$；

（2）對比所有$Los{s_{A,a}}$，選擇最小的$Los{s_{A,a}}$所對應的特徵屬性$A$為當前最優分裂特徵屬性，$a$為最佳分裂點將數據集劃分都左右兩個子樹中；

（3）對左右兩個子樹的數據集重複（1）、（2）步驟繼續劃分，直到節點中數據集滿足指定條件則決策樹構建完成。

4 樹剪枝

無論是面對分類問題，還是回歸問題，最終生成的樹都有可能過於複雜，容易發生過擬合的情況，所以決策樹構建完成後，有必要進一步完成數剪枝。

本文代價複雜度剪枝 Cost-Complexity Pruning(CCP) 方法，過程如下：

輸入：CART演算法生成的決策樹$T_0$  
輸出：剪枝後的最優決策樹${T_alpha }$  
（1）令$k=0$， $T=T_0$，$alpha  =  + infty $；   
（2）自上而下地對各內部節點計算$C({T_t})$，$|{T_t}|$以及

$$g(t) = {{C(t) – C({T_t})} over {|{T_t}| – 1}}$$

$$alpha  = min (alpha ,g(t))$$ 

其中，$T_t$表示以$t$為根節點的子樹，${C(t)}$是對$t$進行剪枝後對訓練數據集的預測誤差，${C({T_t})}$是對訓練數據集的預測誤差，${|{T_t}|}$是$T_t$的葉子結點個數；

（3）自上而下地訪問內部節點$t$，如果有$g(t)=alpha$，則對$t$進行剪枝，並對葉子結點$t$以多數表決法決定輸出，得到樹$T$；

（4）令$k=k+1$，${alpha _k} = alpha $，${T_k} = T$；

（5）如果$T$不是由根節點單獨構成的樹，則回到步驟（3）； 

（6）採用交叉驗證法在子樹序列${T_0},{T_1}, cdots ,{T_k} = T$選取最優的子樹${T_alpha }$。

要理解CART決策樹的整個剪枝過程，關鍵是明白$g(t)$的含義，對於一顆理想的決策樹，我們當然希望預測誤差越小越好，樹的規模也越小越好，但是兩者卻不能兩全，因為往往預測誤差隨著樹規模的增大而減小，所以單獨考慮預測誤差變化或者樹規模變化都不合適，最好是選擇一個衡量標準能夠同時考慮到預測誤差變化量和樹規模變化，例如兩者的比值。

仔細$g(t)$的計算髮現，分子是剪枝前後預測誤差相減，也就是預測誤差變化量，分子是剪枝前後葉子結點數的變化量，所以我們可以認為兩者的比值就是樹$t$每個葉子節點所帶來的的預測誤差的變化量，或者說樹$t$所帶來的的預測誤差變化率——這就是$g(t)$的含義。
為什麼每次對$g(t)$最小的節點進行剪枝呢？因為$g(t)$越小代表對$t$對整個決策樹的作用越小，對其進行剪枝對決策樹的準確率影響也是最想的，當然應該優先被剪枝。

如果還不明白，那麼通過下面的例子來理解吧（例子來源於：https://www.jianshu.com/p/b90a9ce05b28）。 

有下面這個坐標中中的數據集，以及根據數據集構建好的決策樹，如下圖所示：

此時，${alpha _1} = 0$，樹中共有3個節點，對每個節點分別計算其$g(t)$：

$t_1$、$t_2$節點的$g(t)$最小，我們選擇剪枝少的節點，也就是$t_3$進行剪枝,並且令${alpha _2} = {1 over 8}$。剪枝後決策樹如下：

剩下兩個節點，繼續計算每一個節點的$g(t)$:

顯然，$t_2$的$g(t)$更小，所以對$t_2$進行剪枝，並令${alpha _3} = {1 over 8}$：

這時候僅剩下一個$t_1$，計算後有$g({t_3}) = {1 over 4}$，所以${alpha _4} = {1 over 4}$

完成上述所有計算後，我們得到序列${alpha _0} = 0,{alpha _2} = {1 over 8},{alpha _3} = {1 over 8},{alpha _4} = {1 over 4}$，以及對應的子樹。接下來剩餘的工作就是利用獨立的驗證數據集計算每個子樹的平方誤差或者基尼指數，選擇誤差最小的那個子樹作為最優的剪枝後的樹。

5 總結

在本文末尾對3種決策樹演算法做一個簡單對比總結：