本篇将繼續介紹決策的第三種算法：CART算法，它可以說是學習決策樹的核心了。進階內建學習很多複雜架構都是基于CART的。下面将詳細介紹CART算法的來龍去脈。
CART生成算法
CART剪枝算法
CART算法小結
決策樹算法優缺點總結
▍CART生成算法
為什麼叫CART算法呢？這還要從它的英文單詞說起。CART是 "Classification and Regression Trees" 的縮寫，意思是 "分類回歸樹"。從它的名字上就不難了解了，CART算法是既可以用于分類的，也可以用于回歸的。
很多朋友詫異于決策樹為什麼可以用于回歸，明明是if-then結構用于分類的。下面我們來分别介紹CART分類和回歸兩種情況。
分類樹生成算法
CART算法的分類樹是與ID3和C4.5有所不同。下面我們針對特征值的類型來分别介紹CART算法是如何進行分類的，以及和C4.5有什麼異同。
如果特征值是連續值：CART的處理思想與C4.5是相同的，即将連續特征值離散化。唯一不同的地方是度量的标準不一樣，CART采用基尼指數，而C4.5采用資訊增益比。下面舉個例子說明下：
特征a有連續值m個，從小到大排列。m個數值就有m-1個切分點，分别使用每個切分點把連續數值離散劃分成兩類，将節點資料集按照劃分點分為D1和D2子集，然後計算每個劃分點下對應的基尼指數，對比所有基尼指數，選擇值最小的一個作為最終的特征劃分。
基尼指數公式，以及基于特征A劃分後的基尼指數
以上就實作了将連續特征值離散化，但是CART與ID3，C4.5處理離散屬性不同的是：如果目前節點為連續屬性，則該屬性(剩餘的屬性值)後面還可以參與子節點的産生選擇過程。
如果特征值是離散值：CART的處理思想與C4.5稍微所有不同。如果離散特征值多于兩個，那麼C4.5會在節點上根據特征值劃分出多叉樹。但是CART則不同，無論離散特征值有幾個，在節點上都劃分成二叉樹。CART樹是如何進行分類的呢？
還是假設特征a有m個離散值。分類标準是：每一次将其中一個特征分為一類，其它非該特征分為另外一類。依照這個标準周遊所有的分類情況，計算每種分類下的基尼指數，最後選擇值最小的一個作為最終的特征劃分。
特征值連續和離散有各自的處理方法，不應該混淆使用。比如分類0,1,2隻代表标簽含義，如果進行加減的運算或者求平均則沒有任何意義。是以，CART分類樹會根據特征類型選擇不同的劃分方法，并且與C4.5不同是，它永遠隻有兩個分支。
李航 “統計學習方法” 中的分類樹算法流程僅僅是針對特征是離散型的情況，并沒有提及連續值的情況。本篇根據上面我們介紹兩個特征類型情況重新給出一個算法流程(主要就是區分兩種不同特征類型)：
輸入：訓練資料集D，停止計算的參數條件。
輸出：CART決策樹。
根據訓練資料集，從根結點開始，
遞歸地對每個結點進行以下操作，建構二叉決策樹：
1：如果樣本個數小于門檻值或者沒有特征，
則傳回決策子樹，目前節點停止遞歸。2：計算樣本集D的基尼系數，如果基尼系數小于門檻值，
則傳回決策樹子樹，目前節點停止遞歸。
3：識别各個特征類型，離散值還是連續值？
對每種類型使用相應的處理方法并計算每個切分下的基尼系數。
缺失值的處理方法和C4.5算法裡描述的相同。
4：在計算出來的各個特征的各個特征值對資料集D的基尼系數中，
選擇基尼系數最小的特征A和對應的特征值a。
根據這個最優特征和最優特征值，把資料集劃分成兩部分D1和D2，
同時建立目前節點的左右節點，做節點的資料集D為D1，右節點的資料集D為D2.
5：對左右的子節點遞歸的調用1-4步，生成決策樹。算法停止計算的條件是：如步驟1,2中所示，結點中的樣本個數小于預定門檻值，
或樣本集的Gini系數小于預定門檻值(樣本基本屬于同一類)，或者沒有更多特征。
回歸樹生成算法
與分類樹不同，回歸樹的預測變量是連續值，比如預測一個人的年齡，又或者預測季度的銷售額等等。另外，回歸樹在選擇特征的度量标準和決策樹建立後預測的方式上也存在不同。
預測方式
一個回歸樹對應着輸入特征空間的一個劃分，以及在劃分單元上的輸出值。先假設資料集已被劃分，R1,R2,...,Rm共m的子集，回歸樹要求每個劃分Rm中都對應一個固定的輸出值cm。
這個cm值其實就是每個子集中所有樣本的目标變量y的平均值，并以此cm作為該子集的預測值。所有分支節點都是如此，葉子節點也不例外。是以，可以知道回歸樹的預測方式是：将葉子節點中樣本的y均值作為回歸的預測值。而分類樹的預測方式則是：葉子節點中機率最大的類别作為目前節點的預測類别。
選擇特征的度量标準
CART回歸樹對于特征類型的處理與分類樹一樣，連續值與離散值分開對待，并隻能生成二叉樹。但是CART回歸樹對于選擇特征的度量标準則完全不同。
分類樹的特征選擇标準使用基尼指數，而回歸樹則使用RSS殘差平方和。了解線性回歸的朋友知道，損失函數是以最小化離差平方和的形式給出的。回歸樹使用的度量标準也是一樣的，通過最小化殘差平方和作為判斷标準，公式如下：
注意：計算的是屬性劃分下樣本的目标變量y的殘差平方和，而非屬性值。
yi：樣本目标變量的真實值。
R1&R2：被劃分的兩個子集，回歸樹是二叉樹，固隻有兩個子集。
c1&c2：R1&R2子集的樣本均值。
j：目前的樣本特征
s：劃分點
上面公式的含義是：計算所有的特征以及相應所有切分點下的殘差平方和，找到一組(特征j，切分點s)，以滿足：分别最小化左子樹和右子樹的殘差平方和，并在此基礎上再次最小化二者之和。
其實，回歸樹也有分類的思想。所謂 “物以類聚”，相同類之間的目标變量值才會更接近，方內插補點也就會更小。對于回歸樹的生成算法，除了以上兩點外，其它都分類樹是相同的。
▍CART剪枝算法
對于決策樹剪枝，上一篇已經介紹：決策樹學習筆記(二)：剪枝，ID3，C4.5。這部分重點介紹下CART是如何剪枝的？選擇的是哪種方式？
CART回歸樹和CART分類樹的剪枝政策除了在度量損失的時候一個使用均方差，一個使用基尼系數，算法基本完全一樣，是以将它們統一來說。CART采用的辦法是後剪枝法，即先生成決策樹，然後産生所有可能的剪枝後的CART樹，然後使用交叉驗證來檢驗各種剪枝的效果，選擇泛化能力最好的剪枝政策。
也就是說，CART樹的剪枝算法可以概括為兩步：
1)是從原始決策樹生成各種剪枝效果的決策樹序列。
2)是用交叉驗證來檢驗剪枝後的預測能力，選擇泛化預測能力最好的剪枝後的數作為最終的CART樹。
1)生成決策樹序列
CART采用CCP(代價複雜度)的後剪枝方法，定義了決策樹的損失函數和正則化項。公式如下：
T：決策樹中的任意一個節點
|T|：葉子節點數
alpha：正則化參數，懲罰系數
C(T)：無懲罰項情況下的預測誤差，比如基尼指數
C_alpha(T)：在正則參數alpha情況下節點T對應的預測誤差
CART剪枝與C4.5有所不同，C4.5剪枝算法是人為給定一個alpha，然後從葉結點逐漸向根節點回溯，然而CART多了一個周遊alpha的步驟，從0~+無窮。
我們先明确幾個概念，然後将這幾個概念結合起來就可以了解整個生成決策樹序列的算法流程了。
現假設我標明了決策樹的任意一個節點t，并将節點t作為根節點。那麼這個時候我想知道節點t下的分支是否需要剪枝，怎麼辦呢？
很容易想到，我們可以對比一下剪枝以後的預測誤差和剪枝以前的預測誤內插補點的大小，如果不剪枝的誤差比剪枝的大，那麼我們就執行剪枝。用公式來抽象描述一下：
以t為單節點樹的損失函數，|t|=1(剪枝後)
以t為根節點的Tt損失函數(剪枝前)
現在我們有了以t為根節點剪枝前後的損失函數，我們隻需要對比一下就知道了。由于alpha未确定，是以臨界的情況是：
我們把這時候的alpha臨界值稱為誤差增益率，用g(t)來表示，公示如下：
我們可以将g(t)簡單的了解為一種門檻值，如果alpha大于或者等于g(t)，那麼就剪枝。因為在相等的情況下，不剪枝和剪枝達到同樣的效果，也就相當于這些分支沒有什麼作用。如果alpha小于g(t)，則保留，不剪枝。
考慮另外一個問題，如何選擇用哪個節點進行剪枝呢？
我們上面已經找到了對某個節點下是否該剪枝的方法了，但我們開始假設的是任意一個節點t，是一個通用的方法。對于一個生成完整的決策樹而言，是至少擁有一個節點的。如果一個決策樹有n個節點，那麼我就會有相應的n個誤差增益率g(t)。
現在alpha是未知的，我們需要從零開始周遊，直到正無窮。顯然，如果節點下的g(t)越小，alpha就會越先達到該節點的門檻值，而此時的alpha大小還不足以達到其它節點的門檻值。這說明g(t)越小的節點應該越先被剪枝。
如果我們将所有g(t)排序，g1(t)，g2(t)，...，gn(t)，那麼我就會先對g1(t)對應的節點剪枝，得到一個最優子樹，和alpha區間。然後在此基礎上再對g2(t)對應的節點進行剪枝，得到第二個最優子樹，直到得到n個最優子樹的序列。
有的朋友不明白：既然是周遊alpha，從0~+無窮，那為什麼還會得到一個alpha的區間呢？這個很好了解，因為每個alpha區間是對應一個特征節點的，而決策樹的節點是有限的，是以我們真正的目的并不是周遊alpha，而是通過周遊alpha與各個g(t)比較而得到(n+1)個最優子樹序列。
交叉驗證
得到字數序列以後，我們可以使用獨立的驗證資料集，測試各子樹的平方誤差或基尼指數。平方誤差或基尼指數最小的決策樹被認為是最優的決策樹。并且，每顆子樹都對應着一個alpha，是以最優子樹确定了，alpha也就确定了。
上面已經将CART剪枝進行詳細的分析了，下面看一下CART剪枝的整個算法流程。
▍CART算法小結
上面我們對CART算法做了一個詳細的介紹，CART算法相比C4.5算法的分類方法，采用了簡化的二叉樹模型，同時特征選擇采用了近似的基尼系數來簡化計算。當然CART樹最大的好處是還可以做回歸模型，這個C4.5沒有。下表給出了ID3，C4.5和CART的一個比較總結。希望可以幫助大家了解。
看起來CART算法高大上，那麼CART算法還有沒有什麼缺點呢？有，主要的缺點如下：
1)無論是ID3, C4.5還是CART,在做特征選擇的時候都是選擇最優的一個特征來做分類決策，但是大多數，分類決策不應該是由某一個特征決定的，而是應該由一組特征決定的。這樣決策得到的決策樹更加準确。這個決策樹叫做多變量決策樹(multi-variate decision tree)。在選擇最優特征的時候，多變量決策樹不是選擇某一個最優特征，而是選擇最優的一個特征線性組合來做決策。這個算法的代表是OC1，這裡不多介紹。
2)如果樣本發生一點點的改動，就會導緻樹結構的劇烈改變。這個可以通過內建學習裡面的随機森林之類的方法解決。
▍決策樹算法優缺點總結
我們前面介紹了決策樹的特征選擇，生成，和剪枝，然後對ID3, C4.5和CART算法也分别進行了詳細的分析。下面我們來看看決策樹算法作為一個大類别的分類回歸算法的優缺點。
決策樹算法的優點
1)簡單直覺，生成的決策樹很直覺。
2)基本不需要預處理，不需要提前歸一化，處理缺失值。
3)使用決策樹預測的代價是O(log2m)O(log2m)。 m為樣本數。
4)既可以處理離散值也可以處理連續值。很多算法隻是專注于離散值或者連續值。
5)可以處理多元度輸出的分類問題。
6)相比于神經網絡之類的黑盒分類模型，決策樹在邏輯上可以得到很好的解釋
7)可以交叉驗證的剪枝來選擇模型，進而提高泛化能力。
8) 對于異常點的容錯能力好，健壯性高。
決策樹算法的缺點
1)決策樹算法非常容易過拟合，導緻泛化能力不強。可以通過設定節點最少樣本數量和限制決策樹深度來改進。
2)決策樹會因為樣本發生一點點的改動，就會導緻樹結構的劇烈改變。這個可以通過內建學習之類的方法解決。
3)尋找最優的決策樹是一個NP難的問題，我們一般是通過啟發式方法，容易陷入局部最優。可以通過內建學習之類的方法來改善。
4)有些比較複雜的關系，決策樹很難學習，比如異或。這個就沒有辦法了，一般這種關系可以換神經網絡分類方法來解決。
5)如果某些特征的樣本比例過大，生成決策樹容易偏向于這些特征。這個可以通過調節樣本權重來改善。