CART（分類與回歸樹），也就是說CART算法既可以用于分類，也可以用于回歸，它是在給定輸入随機變量X條件下輸出随機變量Y的條件機率分布的學習方法，其也和回歸樹一樣是二叉樹。
是CART算法，也是分為：特征選擇，樹的生成，樹的剪枝。其實感覺前兩步可以合并為一步，因為樹的生成過程中就是不斷的進行特征的選擇。
李航《統計學習方法》中說，決策樹生成階段，生成的決策樹要盡可能的大，也就是生成階段，模型要複雜。為什麼這麼說，我覺得因為後面還是剪枝的過程，在複雜的模型上剪枝優化得到最優模型，這是最合理也是最有可能得到最優模型的方式。
1.回歸樹的生成
回歸樹的生成方式可以參考我的另一篇文章《決策樹（二）：回歸樹和模型樹》中的回歸樹的生成方式，這裡不再贅述。
2.分類樹的生成
CART算法生成的是二叉樹，而分類樹适用的是标稱型資料，每個特征有好多個特征值，是以怎麼生成二叉樹是個問題。之前計算分類樹某個節點的劃分标準的時候是計算某個特征的資訊增益，而CART中計算每個特征值的基尼系數，找出基尼系數最小的，即選擇最優特征，作為劃分值，等于那個特征對應的特征值放到左子樹，其餘的放到右子樹。
假設有K個分類，樣本點資料第k類的機率為pk，則機率分布的基尼指數定義為：
是以對于給定的樣本集合D，其基尼指數為：
其中Ck是D中屬于第k類的樣本子集，K是類的個數。
下面一段話及公式是李航書的原來内容，我感覺不太好了解：
如果樣本集合D根據特征A是否取某一可能值a被分割成D1和D2兩部分，即
則在特征A的條件下，集合D的基尼指數定義為
。
怎麼了解上述公式？我們其它文章介紹過，條件資訊熵是針對整個特征求的熵，而基尼指數是需要計算某個特征的某個特征值的基尼指數，是以我們這裡就不要考慮特征值之間的關系了。假設我們根據特征A的某個特征值a，将整個資料集分為D1和D2兩個部分，D1是特征A是a的資料集合，而D2是特征A不是a的集合；|D1|/|D|就是特征A的值是a的資料集個數占總集合個數的比例，|D2|/|D|亦然；再看基尼指數的計算公式Gini(D1)=1-
，其中K是集合D1中分類結果的總個數，即有多少種分類結果，相當于Y的個數，|D1|是集合D1中元素的個數，|Ck|是第k個分類中元素的個數；對于D2集合的了解亦同理；
其實從上面我麼就可以看出和資訊增益算法的差別：資訊增益如果選擇了某個特征分類，是按照所有兄弟種類分的，而CART算法因為是二叉樹，是以會選擇某個特征的某個值去分，是以分的子集是特征值是a的分一個子集，特征值不是a的是一個子集。
這裡有個容易忽略的點，看李航書中的CART生成算法第（3）步，有這麼一句話：對兩個子節點遞歸調用（1），（2），直至滿足停止條件。是以說特征值等于a的分出來的子集還是需要進行再切分的；另外書上沒有說停止條件，但是前面我們說過生成樹盡可能要複雜，可以參考這個條件，怎麼複雜我覺得可以自己把握，例如基尼指數都小于某個門檻值什麼的。
3.CART剪枝
CART算法的第一階段我們得到的是一個比較複雜的決策樹，是以第二步我們就需要對生成的決策樹進行剪枝，進而得到泛化能力更強的決策樹。
CART剪枝算法會生成好多個子樹{T1，T2，T3，…，Tn}，然後用交叉驗證的方式選出損失最少的決策樹，作為最終的決策樹。
CART剪枝算法中用到的損失函數，和其它剪枝算法的損失函數的基本表達式是一樣的：Cα(T) = C(T)+α|T|，其中C(T)是基本的損失函數，參考決策樹生成過程中的誤差計算概念，我們可以了解為資料的混亂程度（如基尼指數，資訊熵），|T|是樹的葉子節點的個數，是模型的複雜度（葉子節點越多，模型越複雜），α>=0是參數，權衡訓練資料的拟合程度與模型的複雜程度。
當α固定時，則一定存在一棵樹，損失是最小的，用Tα表示；當α較大時，|T|較小的話整體損失就會達到一個較大的值，是以偏向選擇模型較簡單（葉子節點較少）的模型；當α較小時，|T|取到較大的值，是以偏向選擇模型相對複雜（葉子節點較多）的模型。
CART算法對于一個子樹來說需要定義兩個損失函數：
- 對于樹内部的任意節點t，以t為單節點數的損失函數是： ，這個損失函數是假設對子樹進行剪枝後，就隻保留一個這個子樹的根節點的損失函數。
決策樹（三）：CART算法 - 以t為根節點的子樹Tt的損失函數是： ，這個損失函數是假設不剪枝的損失函數。
決策樹（三）：CART算法
當α=0及α充分小時，有不等式
,當α增大時，在某一α有
。李航《統計學習方法》一書上是這麼寫的，為什麼說這麼說，沒太明白。以下是個人了解：
就拿以t為根節點的子樹來說，所有分到t節點的樣本，對于這個子樹來說就是這個子樹的所有樣本，也就是還沒有開始往下分類的樣本。對于這個子樹來說，較小的α偏向選擇較複雜的模型，也就是有一定的葉子節點（非根節點t），那麼就是對于根節點t來說就是有分支結構的，那麼就是更加細分了，整體損失就更小了，就會有
；當α變大的時候，因為根節點的|T|=1，而這顆子樹的|T| > 1，是以子樹的整體損失增加較快，α到達一定程度的時候，就會有
，此時由于剪枝前後損失相同，并且隻有根節點t，模型偏向簡單，所有隻保留根節點比保留以t為根節點的子樹更加可取，就進行剪枝。
是以根據以上等式，我們可以得到
我們要保證α從小到大增加，是以對CART第一階段生成的樹的每個節點計算上述值，然後選擇最小的α，然後将其對應的子樹剪枝，得到子樹T1，然後在T1基礎上再重複上述過程，直到剪枝到根節點。最後得到一系列子樹T1，T2，T3，…，Tn并且對應一些列參數α1，α2，α3，…，αn。得到這些子樹後，采用交叉驗證的方式在一系列子樹中選取最優子樹Tα。
通過以上過程，我們可以看到CART剪枝比一般剪枝算法還是複雜一些的；最起碼普通的剪枝算法，不需要生成那麼多的樹，隻需要在一棵樹上不斷計算剪枝前後的誤差，然後決定是否剪枝，思路也相對好了解，CART剪枝就不那麼好了解了。