決策樹算法總結（下：CART決策樹）

文章目錄

• 一、CART樹原理
• 二、CART分類樹
• • 2.1 特征選擇
  • 2.2 建立流程
  • 2.3 連續特征和離散特征的處理
• 三、CART回歸樹
• 四、CART樹算法的剪枝
• • 4.1 剪枝的損失函數度量
  • 4.2 剪枝的思路
  • 4.3 CART樹的交叉驗證
  • 4.4 CART樹的剪枝算法
• 五、決策樹總結

上一篇文章中，講解了ID3決策樹及C4.5決策樹，但是特們仍有許多不足：比如模型是用較為複雜的熵來度量，使用了相對較為複雜的多叉樹，隻能處理分類不能處理回歸等。對于這些問題， CART算法大部分做了改進。由于CART算法可以做回歸，也可以做分類，我們分别加以介紹，先從CART分類樹算法開始，重點比較和C4.5算法的不同點。接着介紹CART回歸樹算法，重點介紹和CART分類樹的不同點。然後我們讨論CART樹的建樹算法和剪枝算法，最後總結決策樹算法的優缺點。

一、CART樹原理

CART 全稱為 Classification And Regression Trees，即分類回歸樹。顧名思義，該算法既可以用于分類還可以用于回歸。

克服了 ID3 算法隻能處理離散型資料的缺點，CART 可以使用二進制切分來處理連續型變量。二進制切分法，即每次把資料集切分成兩份，具體地處理方法是：如果特征值大于給定值就走左子樹，否則就走右子樹。對 CART 稍作修改就可以處理回歸問題。先前我們使用香農熵來度量集合的無組織程度，如果選用其它方法來代替香農熵，就可以使用樹建構算法來完成回歸。

與ID3決策樹及C4.5決策樹一樣，CART是決策樹的一種，主要由特征選擇，樹的生成和剪枝三部分組成。它主要用來處理分類和回歸問題，下面對分别對其進行介紹。

本部分将建構兩種樹，第一種是分類樹；第二種是回歸樹。

二、CART分類樹

2.1 特征選擇

CART分類樹使用基尼指數最小化準則來選擇最佳屬性。

ID3算法使用了資訊增益來選擇特征，資訊增益大的優先選擇。C4.5算法采用了資訊增益比來選擇特征，以減少資訊增益容易選擇特征值多的特征的問題。但是無論是ID3還是C4.5，都是基于資訊論的熵模型的，這裡面會涉及大量的對數運算。是以，我們希望有一種方法簡化模型同時又不至于完全丢失熵模型的優點，這就是基尼系數。CART分類樹算法使用基尼系數來代替資訊增益比，基尼系數代表了模型的不純度，基尼系數越小，則不純度越低，特征越好。這和資訊增益(比)是相反的。

在分類問題中，假設有K個類别，第k個類别的機率為 p k p_k pk​, 則基尼系數的表達式為：

G i n i ( p ) = ∑ k = ∑ k = 1 K p k ( 1 − p k ) = 1 − ∑ k = 1 K p k 2 Gini(p)=∑k=\sum_{k=1}^{K}p_k(1−p_k)=1-\sum_{k=1}^{K}p^2_k Gini(p)=∑k=k=1∑K​pk​(1−pk​)=1−k=1∑K​pk2​

如果是二類分類問題，計算就更加簡單了，如果屬于第一個樣本輸出的機率是p，則基尼系數的表達式為：

G i n i ( p ) = 2 p ( 1 − p ) Gini(p)=2p(1−p) Gini(p)=2p(1−p)

對于個給定的樣本D,假設有K個類别, 第k個類别的數量為 C k C_k Ck​,則樣本D的基尼系數表達式為：

G i n i ( D ) = 1 − ∑ k = 1 K ( ∣ C k ∣ ∣ D ∣ ) 2 Gini(D)=1-\sum_{k=1}^{K}(\frac{|C_k|}{|D|})^2 Gini(D)=1−k=1∑K​(∣D∣∣Ck​∣​)2

特别的，對于樣本D,如果根據特征A的某個值a,把D分成D1和D2兩部分，則在特征A的條件下，D的基尼系數表達式為：

G i n i ( D , A ) = ∣ D 1 ∣ ∣ D ∣ G i n i ( D 1 ) + ∣ D 2 ∣ ∣ D ∣ G i n i ( D 2 ) 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​)

其中：

• Gini(D)：表示集合D的不确定性。
• Gini(A,D)：表示經過A=a分割後的集合D的不确定性。

對比基尼系數表達式和熵模型的表達式，二次運算要比對數簡單很多，尤其是二類分類的計算，更加簡單。但是簡單歸簡單，和熵模型的度量方式比，基尼系數對應的誤差有多大呢？對于二類分類，基尼系數和熵之半的曲線如下：

　從上圖可以看出，基尼系數和熵之半的曲線非常接近，僅僅在45度角附近誤差稍大。是以，基尼系數可以做為熵模型的一個近似替代。而CART分類樹算法就是使用的基尼系數來選擇決策樹的特征。同時，為了進一步簡化，CART分類樹算法每次僅僅對某個特征的值進行二分，而不是多分，這樣CART分類樹算法建立起來的是二叉樹，而不是多叉樹。這樣一可以進一步簡化基尼系數的計算，二可以建立一個更加優雅的二叉樹模型。

2.2 建立流程

算法從根節點開始，用訓練集遞歸的建立CART樹。

• 1）對于目前節點的資料集為D，如果樣本個數小于門檻值或者沒有特征，則傳回決策子樹，目前節點停止遞歸。
• 2）計算樣本集D的基尼系數，如果基尼系數小于門檻值，則傳回決策樹子樹，目前節點停止遞歸。
• 3）計算目前節點現有的各個特征的各個特征值對資料集D的基尼系數。
• 4）在計算出來的各個特征的各個特征值對資料集D的基尼系數中，選擇基尼系數最小的特征A和對應的特征值a。根據這個最優特征和最優特征值，把資料集劃分成兩部分D1和D2，同時建立目前節點的左右節點，做節點的資料集D為D1，右節點的資料集D為D2.
• 5）對左右的子節點遞歸的調用1-4步，生成決策樹。

對于生成的決策樹做預測的時候，假如測試集裡的樣本A落到了某個葉子節點，而節點裡有多個訓練樣本。則對于A的類别預測采用的是這個葉子節點裡機率最大的類别。

2.3 連續特征和離散特征的處理

1）、連續特征的處理

對于CART分類樹連續值的處理問題，其思想和C4.5是相同的，都是将連續的特征離散化。唯一的差別在于在選擇劃分點時的度量方式不同，C4.5使用的是資訊增益比，則CART分類樹使用的是基尼系數。

具體的思路如下，比如m個樣本的連續特征A有m個，從小到大排列為 a 1 , a 2 , . . . , a m a_1,a_2,...,a_m a1​,a2​,...,am​,則CART算法取相鄰兩樣本值的平均數，一共取得m-1個劃分點，其中第i個劃分點 T i T_i Ti​表示為： T i = a i + a ( i + 1 ) 2 Ti=\frac{a_i+a_{(i+1)}}{2} Ti=2ai​+a(i+1)​​。對于這m-1個點，分别計算以該點作為二進制分類點時的基尼系數。選擇基尼系數最小的點作為該連續特征的二進制離散分類點。比如取到的基尼系數最小的點為 a t a_t at​,則小于 a t a_t at​的值為類别1，大于 a t a_t at​的值為類别2，這樣我們就做到了連續特征的離散化。要注意的是，與ID3或者C4.5處理離散屬性不同的是，如果目前節點為連續屬性，則該屬性後面還可以參與子節點的産生選擇過程。

2)、離散特征處理

對于CART分類樹離散值的處理問題，采用的思路是不停的二分離散特征。

在ID3或者C4.5，如果某個特征A被選取建立決策樹節點，如果它有A1,A2,A3三種類别，我們會在決策樹上一下建立一個三叉的節點。這樣導緻決策樹是多叉樹。但是CART分類樹使用的方法不同，他采用的是不停的二分，還是這個例子，CART分類樹會考慮把A分成{A1}和{A2,A3}, {A2}和{A1,A3}, {A3}和{A1,A2}三種情況，找到基尼系數最小的組合，比如{A2}和{A1,A3},然後建立二叉樹節點，一個節點是A2對應的樣本，另一個節點是{A1,A3}對應的節點。同時，由于這次沒有把特征A的取值完全分開，後面我們還有機會在子節點繼續選擇到特征A來劃分A1和A3。這和ID3或者C4.5不同，在ID3或者C4.5的一棵子樹中，離散特征隻會參與一次節點的建立。

三、CART回歸樹

CART回歸樹使用平方誤差最小準則。

訓練回歸樹其實和訓練分類樹沒有本質不同，也是自上而下，不斷分裂節點的過程。不同之處在于對節點分裂的分裂準則和分裂值的選擇方法上。我下面将一步步推導回歸樹的建構算法。

設有訓練資料集 D = { ( X 1 , y 1 ) , ( X 2 , y 2 ) , … , ( X n , y n ) } D=\{(X_1,y_1),(X_2,y_2),…,(X_n,y_n)\} D={(X1​,y1​),(X2​,y2​),…,(Xn​,yn​)}。我們知道決策樹最終将資料元組劃分到了多個葉子節點中，比如分類樹的每個葉子就有一個類标号，作為元組的預測類。回歸樹的思路類似，我将資料空間劃分成了mm個區域 { R 1 , R 2 , … , R m } \{R_1,R_2,…,R_m\} {R1​,R2​,…,Rm​}，實際上就是将訓練元組的分區。然後賦給每個區域有一個固定的代表值 C i C_i Ci​（類似于分類樹中的類标号），這樣，回歸樹的模型可以表示成r如下公式的形式：

f ( X ) = ∑ i = 1 m C i I ( X ∈ R i ) f(X)=\sum_{i=1}^{m}C_iI(X \in R_i) f(X)=i=1∑m​Ci​I(X∈Ri​)

其中 I ( X ∈ R i ) = 1 I(X∈R_i)=1 I(X∈Ri​)=1，如果 X ∈ R i X∈R_i X∈Ri​；否則， I ( X ∈ R i ) = 0 I(X∈R_i)=0 I(X∈Ri​)=0。這麼看來，上式的含義是：先判斷X屬于哪個區域，然後傳回這個區域的代表值。

這樣，我們可以寫出對于某個區域Ri回歸模型的損失函數：

J ( C ) = ∑ X j ∈ R i ( f ( X j ) − g i ) 2 J(C)=\sum_{X_j \in R_i}(f(X_j)-g_i)^2 J(C)=Xj​∈Ri​∑​(f(Xj​)−gi​)2

其中， g i g_i gi​為這個區域的代表值（這裡用 g i g_i gi​而不用 C i C_i Ci​的原因是我要表達 g i g_i gi​是分裂中間的某個區域的代表值，而 C i C_i Ci​為最終完成分裂之後的葉子節點的代表值）， g i g_i gi​的計算方法一般是這個區域中的元組的y值的均值（取均值時，損失函數達到最優）。

g i = 1 N i ∑ X j ∈ R i y i g_i=\frac{1}{N_i}\sum_{X_j \in R_i}y_i gi​=Ni​1​Xj​∈Ri​∑​yi​

其中， N i N_i Ni​為這個區域内資料元組的總數。初始時，所有的資料元組都在一個區域内，我們按照 J ( C ) J(C) J(C)計算損失函數，如果計算得到的誤內插補點太大，不能滿足要求，則尋找最佳的分裂準則（屬性）和分裂值将資料集一分為二。這裡的關鍵在于怎樣的分裂準則和分裂值對于回歸樹來說是最佳的。其實很明顯，“最佳”指我按照這樣的屬性和屬性值将資料集一分為二後，使得分裂得到的兩個子區域的誤差和最小。

綜上所述，回歸樹的計算步驟如下：

• 1）初始時，将所有訓練元組放置于根節點中，計算損失函數得到誤內插補點，倘若誤差大于事先定好的參數，那麼執行下面的2~4步；

• 2）選擇用于分裂區域的屬性A和對應的屬性值s，将目前節點的資料元組劃分到以下兩個區域 R 1 R_1 R1​, R 2 R_2 R2​中。：

  R 1 = { X ∣ x i ≤ s } ； R 1 = { X ∣ x i > s } R_1=\{X|x_i\leq s\}；R_1=\{X|x_i>s\} R1​={X∣xi​≤s}；R1​={X∣xi​>s}

其中 x i x_i xi​為元組 X X X中屬性 A A A的值。而選擇分裂屬性 A A A以及屬性值 s s s的依據是使得分裂後的子區域誤內插補點的和最小。即：

m i n ∑ X j ∈ R 1 ( f ( X j ) − y 1 ) 2 + ∑ X j ∈ R 2 ( f ( X j ) − y 2 ) 2 min\sum_{X_j \in R_1}(f(X_j)-y_1)^2+\sum_{X_j \in R_2}(f(X_j)-y_2)^2 minXj​∈R1​∑​(f(Xj​)−y1​)2+Xj​∈R2​∑​(f(Xj​)−y2​)2

這一步具體執行的時候，我們周遊所有的屬性以及每個屬性的所有可能的劃分值，分别計算他們劃分資料元組之後的兩個子區域的代表值 y 1 , y 2 y_1,y_2 y1​,y2​，這樣就可以計算 R 1 , R 2 R_1,R_2 R1​,R2​的誤差和上式，最終選擇誤差和最小的屬性 A A A和屬性值 s s s，作為分裂依據。

四、CART樹算法的剪枝

CART回歸樹和CART分類樹的剪枝政策除了在度量損失的時候一個使用均方差，一個使用基尼系數，算法基本完全一樣，這裡我們一起來講。

由于決策時算法很容易對訓練集過拟合，而導緻泛化能力差，為了解決這個問題，我們需要對CART樹進行剪枝，即類似于線性回歸的正則化，來增加決策樹的泛化能力。但是，有很多的剪枝方法，我們應該這麼選擇呢？CART采用的辦法是後剪枝法，即先生成決策樹，然後産生所有可能的剪枝後的CART樹，然後使用交叉驗證來檢驗各種剪枝的效果，選擇泛化能力最好的剪枝政策。

也就是說，CART樹的剪枝算法可以概括為兩步，第一步是從原始決策樹生成各種剪枝效果的決策樹，第二步是用交叉驗證來檢驗剪枝後的預測能力，選擇泛化預測能力最好的剪枝後的數作為最終的CART樹。

4.1 剪枝的損失函數度量

首先我們看看剪枝的損失函數度量，在剪枝的過程中，對于任意的一刻子樹T,其損失函數為：

C α ( T t ) = C ( T t ) + α ∣ T t ∣ C_{\alpha}(T_t)=C(T_t)+\alpha|T_t| Cα​(Tt​)=C(Tt​)+α∣Tt​∣

其中， α α α為正則化參數，這和線性回歸的正則化一樣。 C ( T t ) C(T_t) C(Tt​)為訓練資料的預測誤差，分類樹是用基尼系數度量，回歸樹是均方差度量。 ∣ T t ∣ |T_t| ∣Tt​∣是子樹T的葉子節點的數量。

當 α = 0 α=0 α=0時，即沒有正則化，原始的生成的CART樹即為最優子樹。當 α = ∞ α=∞ α=∞時，即正則化強度達到最大，此時由原始的生成的CART樹的根節點組成的單節點樹為最優子樹。當然，這是兩種極端情況。一般來說， α α α越大，則剪枝剪的越厲害，生成的最優子樹相比原生決策樹就越偏小。對于固定的 α α α，一定存在使損失函數 C α ( T ) C_α(T) Cα​(T)最小的唯一子樹。

4.2 剪枝的思路

對于位于節點t的任意一顆子樹Tt，如果沒有剪枝，它的損失是：

C α ( T t ) = C ( T t ) + α ∣ T t ∣ C_{\alpha}(T_t)=C(T_t)+\alpha|T_t| Cα​(Tt​)=C(Tt​)+α∣Tt​∣

如果将其剪掉，僅僅保留根節點，則損失是：

C α ( T ) = C ( T ) + α C_{\alpha}(T)=C(T)+\alpha Cα​(T)=C(T)+α

當 α = 0 α=0 α=0或者 α α α很小時， C α ( T t ) &lt; C α ( T ) C_α(T_t)&lt;C_α(T) Cα​(Tt​)<Cα​(T) , 當 α α α增大到一定的程度時:

C α ( T t ) = C α ( T ) C_{\alpha}(T_t)=C_{\alpha}(T) Cα​(Tt​)=Cα​(T)

當α繼續增大時不等式反向，也就是說，如果滿足下式：

α = C ( T ) − C ( T t ) ∣ T t ∣ − 1 \alpha=\frac{C(T)-C(T_t)}{|T_t|-1} α=∣Tt​∣−1C(T)−C(Tt​)​

T t T_t Tt​ 和 T T T有相同的損失函數，但是 T T T節點更少，是以可以對子樹 T t T_t Tt​進行剪枝，也就是将它的子節點全部剪掉，變為一個葉子節點T。

4.3 CART樹的交叉驗證

由上面可知：可以計算出每個子樹是否剪枝的門檻值α，如果我們把所有的節點是否剪枝的值α都計算出來，然後分别針對不同的α所對應的剪枝後的最優子樹做交叉驗證。這樣就可以選擇一個最好的α，有了這個α，我們就可以用對應的最優子樹作為最終結果。

4.4 CART樹的剪枝算法

• 輸入：CART樹建立算法得到的原始決策樹T。
• 輸出：最優決策子樹Tα。

算法如下：

• 1）初始化 α m i n = ∞ α_{min}=∞ αmin​=∞， 最優子樹集合 ω = { T } ω=\{T\} ω={T}；
• 2）從葉子節點開始自下而上計算各内部節點t的訓練誤差損失函數 C α ( T t ) C_α(T_t) Cα​(Tt​)（回歸樹為均方差，分類樹為基尼系數）,葉子節點數 ∣ T t ∣ |T_t| ∣Tt​∣，以及正則化門檻值 α = m i n { C ( T ) − C ( T t ) ∣ T t ∣ − 1 , α m i n } α=min\{\frac{C(T)−C(T_t)}{|T_t|−1},α_{min}\} α=min{∣Tt​∣−1C(T)−C(Tt​)​,αmin​},更新 α m i n = α α_{min}=α αmin​=α；
• 3）得到所有節點的 α α α值的集合 M M M；
• 4）從M中選擇最大的值 α k α_k αk​，自上而下的通路子樹 t t t的内部節點，如果 C ( T ) − C ( T t ) ∣ T t ∣ − 1 \frac{C(T)−C(T_t)}{|T_t|−1} ∣Tt​∣−1C(T)−C(Tt​)​時，進行剪枝。并決定葉節點 t t t的值。如果是分類樹，則是機率最高的類别，如果是回歸樹，則是所有樣本輸出的均值。這樣得到αk對應的最優子樹Tk；
• 5）最優子樹集合 ω = ω ∪ T k ω=ω∪T_k ω=ω∪Tk​， M = M − α k M=M−{α_k} M=M−αk​；
• 6）如果M不為空，則回到步驟4。否則就已經得到了所有的可選最優子樹集合ω；
• 7）采用交叉驗證在ω選擇最優子樹 T α T_α Tα​。

五、決策樹總結

決策樹優點：

• 1）簡單直覺，生成的決策樹很直覺。
• 2）基本不需要預處理，不需要提前歸一化，處理缺失值。
• 3）使用決策樹預測的代價是O(log2m)。 m為樣本數。
• 4）既可以處理離散值也可以處理連續值。很多算法隻是專注于離散值或者連續值。
• 5）可以處理多元度輸出的分類問題。
• 6）相比于神經網絡之類的黑盒分類模型，決策樹在邏輯上可以得到很好的解釋
• 7）可以交叉驗證的剪枝來選擇模型，進而提高泛化能力。
• 8） 對于異常點的容錯能力好，健壯性高。

決策樹缺點：

• 1）決策樹算法非常容易過拟合，導緻泛化能力不強。可以通過設定節點最少樣本數量和限制決策樹深度來改進。
• 2）決策樹會因為樣本發生一點點的改動，就會導緻樹結構的劇烈改變。這個可以通過內建學習之類的方法解決。
• 3）尋找最優的決策樹是一個NP難的問題，我們一般是通過啟發式方法，容易陷入局部最優。可以通過內建學習之類的方法來改善。
• 4）有些比較複雜的關系，決策樹很難學習，比如異或。這個就沒有辦法了，一般這種關系可以換神經網絡分類方法來解決。
• 5）如果某些特征的樣本比例過大，生成決策樹容易偏向于這些特征。這個可以通過調節樣本權重來改善。

文章有很多直接複制了決策樹算法原理(下)中的總結，因為該文章寫的太全了。