來源：http://www.cnblogs.com/pinard/p/6053344.html

作者：劉建平Pinard

對于C4.5算法，我們也提到了它的不足，比如模型是用較為復雜的熵來度量，使用了相對較為復雜的多叉樹，只能處理分類不能處理回歸等。對于這些問題， CART算法大部分做了改進。CART算法也就是我們下面的重點了。由于CART算法可以做回歸，也可以做分類，我們分別加以介紹，先從CART分類樹算法開始，重點比較和C4.5算法的不同點。接著介紹CART回歸樹算法，重點介紹和CART分類樹的不同點。然后我們討論CART樹的建樹算法和剪枝算法，最后總結決策樹算法的優缺點。

1.CART（Classification And Regression Tree）分類回歸樹算法的最優特征選擇方法

　　　　我們知道，在ID3算法中我們使用了信息增益來選擇特征，信息增益大的優先選擇。在C4.5算法中，采用了信息增益比來選擇特征，以減少信息增益容易選擇特征值多的特征的問題。但是無論是ID3還是C4.5,都是基于信息論的熵模型的，這里面會涉及大量的對數運算。能不能簡化模型同時也不至于完全丟失熵模型的優點呢？有！CART分類樹算法使用基尼系數來代替信息增益比，基尼系數代表了模型的不純度，基尼系數越小，則不純度越低，特征越好。這和信息增益(比)是相反的。

　　　　具體的，在分類問題中，假設有K個類別，第k個類別的概率為pkpk, 則基尼系數的表達式為：

Gini(p)=∑k=1Kpk(1−pk)=1−∑k=1Kp2kGini(p)=∑k=1Kpk(1−pk)=1−∑k=1Kpk2

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

Gini(p)=2p(1−p)Gini(p)=2p(1−p)

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

Gini(D)=1−∑k=1K(|Ck||D|)2Gini(D)=1−∑k=1K(|Ck||D|)2

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

Gini(D,A)=|D1||D|Gini(D1)+|D2||D|Gini(D2)Gini(D,A)=|D1||D|Gini(D1)+|D2||D|Gini(D2)

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

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

2.CART分類樹算法對于連續特征和離散特征處理的改進

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

　　　　具體的思路如下，比如m個樣本的連續特征A有m個，從小到大排列為a1,a2,...,ama1,a2,...,am,則CART算法取相鄰兩樣本值的中位數，一共取得m-1個劃分點，其中第i個劃分點Ti表示Ti表示為：Ti=ai+ai+12Ti=ai+ai+12。對于這m-1個點，分別計算以該點作為二元分類點時的基尼系數。選擇基尼系數最小的點作為該連續特征的二元離散分類點。比如取到的基尼系數最小的點為atat,則小于atat的值為類別1，大于atat的值為類別2，這樣我們就做到了連續特征的離散化。要注意的是，與離散屬性不同的是，如果當前節點為連續屬性，則該屬性后面還可以參與子節點的產生選擇過程。

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

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

3. CART分類樹建立算法的具體流程

　　　　上面介紹了CART算法的一些和C4.5不同之處，下面我們看看CART分類樹建立算法的具體流程，之所以加上了建立，是因為CART樹算法還有獨立的剪枝算法這一塊，這塊我們在第5節講。

　　　　算法輸入是訓練集D，基尼系數的閾值，樣本個數閾值。

　　　　輸出是決策樹T。

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

　　　　1) 對于當前節點的數據集為D，如果樣本個數小于閾值或者沒有特征，則返回決策子樹，當前節點停止遞歸。

　　　　2) 計算樣本集D的基尼系數，如果基尼系數小于閾值，則返回決策樹子樹，當前節點停止遞歸。

　　　　3) 計算當前節點現有的各個特征的各個特征值對數據集D的基尼系數，對于離散值和連續值的處理方法和基尼系數的計算見第二節。缺失值的處理方法和上篇的C4.5算法里描述的相同。

　　　　4) 在計算出來的各個特征的各個特征值對數據集D的基尼系數中，選擇基尼系數最小的特征A和對應的特征值a。根據這個最優特征和最優特征值，把數據集劃分成兩部分D1和D2，同時建立當前節點的左右節點，做節點的數據集D為D1，右節點的數據集D為D2.

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

　　　

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

4. CART回歸樹建立算法

　　　　CART回歸樹和CART分類樹的建立算法大部分是類似的，所以這里我們只討論CART回歸樹和CART分類樹的建立算法不同的地方。

　　　　首先，我們要明白，什么是回歸樹，什么是分類樹。兩者的區別在于樣本輸出，如果樣本輸出是離散值，那么這是一顆分類樹。如果果樣本輸出是連續值，那么那么這是一顆回歸樹。

　　　　除了概念的不同，CART回歸樹和CART分類樹的建立和預測的區別主要有下面兩點：

　　　　1)連續值的處理方法不同

　　　　2)決策樹建立后做預測的方式不同。

　　　　對于連續值的處理，我們知道CART分類樹采用的是用基尼系數的大小來度量特征的各個劃分點的優劣情況。這比較適合分類模型，但是對于回歸模型，我們使用了常見的均方差的度量方式，CART回歸樹的度量目標是，對于任意劃分特征A，對應的任意劃分點s兩邊劃分成的數據集D1和D2，求出使D1和D2各自集合的均方差最小，同時D1和D2的均方差之和最小所對應的特征和特征值劃分點。表達式為：

min??????A,s[min??????c1∑xi∈D1(A,s)(yi−c1)2+min??????c2∑xi∈D2(A,s)(yi−c2)2]min?A,s[min?c1∑xi∈D1(A,s)(yi−c1)2+min?c2∑xi∈D2(A,s)(yi−c2)2]

　　　　其中，c1c1為D1數據集的樣本輸出均值，c2c2為D2數據集的樣本輸出均值。

　　　　對于決策樹建立后做預測的方式，上面講到了CART分類樹采用葉子節點里概率最大的類別作為當前節點的預測類別。而回歸樹輸出不是類別，它采用的是用最終葉子的均值或者中位數來預測輸出結果。

　　　　除了上面提到了以外，CART回歸樹和CART分類樹的建立算法和預測沒有什么區別。

5. CART樹算法的剪枝

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

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

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

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

Cα(Tt)=C(Tt)+α|Tt|Cα(Tt)=C(Tt)+α|Tt|

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

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

　　　　看過剪枝的損失函數度量后，我們再來看看剪枝的思路，對于位于節點t的任意一顆子樹TtTt，如果沒有剪枝，它的損失是

Cα(Tt)=C(Tt)+α|Tt|Cα(Tt)=C(Tt)+α|Tt|

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

Cα(T)=C(T)+αCα(T)=C(T)+α

　

　　　　當α=0α=0或者αα很小時，Cα(Tt)<Cα(T)Cα(Tt)<Cα(T), 當αα增大到一定的程度時

Cα(T)=C(T)+αCα(T)=C(T)+α

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

α=C(T)−C(Tt)|Tt|−1α=C(T)−C(Tt)|Tt|−1

　　　　TtTt和TT有相同的損失函數，但是TT節點更少，因此可以對子樹TtTt進行剪枝，也就是將它的子節點全部剪掉，變為一個葉子節點TT。

　　　　最后我們看看CART樹的交叉驗證策略。上面我們講到，可以計算出每個子樹是否剪枝的閾值αα，如果我們把所有的節點是否剪枝的值αα都計算出來，然后分別針對不同的αα所對應的剪枝后的最優子樹做交叉驗證。這樣就可以選擇一個最好的αα，有了這個αα，我們就可以用對應的最優子樹作為最終結果。

　　　　好了，有了上面的思路，我們現在來看看CART樹的剪枝算法。

　　　　輸入是CART樹建立算法得到的原始決策樹TT。

　　　　輸出是最優決策子樹TαTα。

　　　　算法過程如下：

　　　　1）初始化αmin=∞αmin=∞， 最優子樹集合ω={T}ω={T}。

　　　　2）從葉子節點開始自下而上計算各內部節點t的訓練誤差損失函數Cα(Tt)Cα(Tt)（回歸樹為均方差，分類樹為基尼系數）, 葉子節點數|Tt||Tt|，以及正則化閾值α=min{C(T)−C(Tt)|Tt|−1,αmin}α=min{C(T)−C(Tt)|Tt|−1,αmin}, 更新αmin=ααmin=α

　　　　3) 得到所有節點的αα值的集合M。

　　　　4）從M中選擇最大的值αkαk，自上而下的訪問子樹t的內部節點，如果C(T)−C(Tt)|Tt|−1≤αkC(T)−C(Tt)|Tt|−1≤αk時，進行剪枝。并決定葉節點t的值。如果是分類樹，則是概率最高的類別，如果是回歸樹，則是所有樣本輸出的均值。這樣得到αkαk對應的最優子樹TkTk

　　　　5）最優子樹集合ω=ω∪Tkω=ω∪Tk，M=M−{αk}M=M−{αk}。

　　　　6) 如果M不為空，則回到步驟4。否則就已經得到了所有的可選最優子樹集合ωω.

　　　　7) 采用交叉驗證在ωω選擇最優子樹TαTα

6. CART算法小結

　　　　上面我們對CART算法做了一個詳細的介紹，CART算法相比C4.5算法的分類方法，采用了簡化的二叉樹模型，同時特征選擇采用了近似的基尼系數來簡化計算。當然CART樹最大的好處是還可以做回歸模型，這個C4.5沒有。下表給出了ID3，C4.5和CART的一個比較總結。希望可以幫助大家理解。

算法	支持模型	樹結構	特征選擇	連續值處理	缺失值處理	剪枝
ID3	分類	多叉樹	信息增益	不支持	不支持	不支持
C4.5	分類	多叉樹	信息增益比	支持	支持	支持
CART	分類，回歸	二叉樹	基尼系數，均方差	支持	支持	支持

　　　　看起來CART算法高大上，那么CART算法還有沒有什么缺點呢？有！主要的缺點我認為如下：

　　　　1）應該大家有注意到，無論是ID3, C4.5還是CART,在做特征選擇的時候都是選擇最優的一個特征來做分類決策，但是大多數，分類決策不應該是由某一個特征決定的，而是應該由一組特征決定的。這樣絕息到的決策樹更加準確。這個決策樹叫做多變量決策樹(multi-variate decision tree)。在選擇最優特征的時候，多變量決策樹不是選擇某一個最優特征，而是選擇最優的一個特征線性組合來做決策。這個算法的代表是OC1，這里不多介紹。

　　　　2）如果樣本發生一點點的改動，就會導致樹結構的劇烈改變。這個可以通過集成學習里面的隨機森林之類的方法解決。　　　

7. 決策樹算法小結

　　　　終于到了最后的總結階段了，這里我們不再糾結于ID3, C4.5和 CART，我們來看看決策樹算法作為一個大類別的分類回歸算法的優缺點。這部分總結于scikit-learn的英文文檔。

　　　　首先我們看看決策樹算法的優點：

　　　　1）簡單直觀，生成的決策樹很直觀。

　　　　2）基本不需要預處理，不需要提前歸一化，處理缺失值。

　　　　3）使用決策樹預測的代價是O(log2m)O(log2m)。 m為樣本數。

　　　　4）既可以處理離散值也可以處理連續值。很多算法只是專注于離散值或者連續值。

　　　　5）可以處理多維度輸出的分類問題。

　　　　6）相比于神經網絡之類的黑盒分類模型，決策樹在邏輯上可以得到很好的解釋

　　　　7）可以交叉驗證的剪枝來選擇模型，從而提高泛化能力。

　　　　8） 對于異常點的容錯能力好，健壯性高。

　　　　我們再看看決策樹算法的缺點:

　　　　1）決策樹算法非常容易過擬合，導致泛化能力不強。可以通過設置節點最少樣本數量和限制決策樹深度來改進。

　　　　2）決策樹會因為樣本發生一點點的改動，就會導致樹結構的劇烈改變。這個可以通過集成學習之類的方法解決。

　　　　3）尋找最優的決策樹是一個NP難的問題，我們一般是通過啟發式方法，容易陷入局部最優。可以通過集成學習之類的方法來改善。

　　　　4）有些比較復雜的關系，決策樹很難學習，比如異或。這個就沒有辦法了，一般這種關系可以換神經網絡分類方法來解決。

　　　　5）如果某些特征的樣本比例過大，生成決策樹容易偏向于這些特征。這個可以通過調節樣本權重來改善。

總結

以上是生活随笔為你收集整理的CART算法(转)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。