1. CART算法的認識

   Classification And Regression Tree，即分類回歸樹算法，簡稱CART算法，它是決策樹的一種實現，通常決策樹主要有三種實現，分別是ID3算法，CART算法和C4.5算法。

   CART算法是一種二分遞歸分割技術，把當前樣本劃分為兩個子樣本，使得生成的每個非葉子結點都有兩個分支，因此CART算法生成的決策樹是結構簡潔的二叉樹。由于CART算法構成的是一個二叉樹，它在每一步的決策時只能是“是”或者“否”，即使一個feature有多個取值，也是把數據分為兩部分。在CART算法中主要分為兩個步驟

   （1）將樣本遞歸劃分進行建樹過程

   （2）用驗證數據進行剪枝

2. CART算法的原理

   上面說到了CART算法分為兩個過程，其中第一個過程進行遞歸建立二叉樹，那么它是如何進行劃分的 ？

   設代表單個樣本的個屬性，表示所屬類別。CART算法通過遞歸的方式將維的空間劃分為不重疊的矩形。

   劃分步驟大致如下：

   （1）選一個自變量，再選取的一個值，把維空間劃分為兩部分，一部分的所有點都滿足，另一部分的所有點都滿足，對非連續變量來說屬性值的取值只有兩個，即等于該值或不等于該值。

   （2）遞歸處理，將上面得到的兩部分按步驟（1）重新選取一個屬性繼續劃分，直到把整個維空間都劃分完。

   在劃分時候有一個問題，它是按照什么標準來劃分的 ？ 對于一個變量屬性來說，它的劃分點是一對連續變量屬性值的中點。假設個樣本的集合一個屬性有個連續的值，那么則會有個分裂點，每個分裂點為相鄰兩個連續值的均值。每個屬性的劃分按照能減少的雜質的量來進行排序，而雜質的減少量定義為劃分前的雜質減去劃分后的每個節點的雜質量劃分所占比率之和。而雜質度量方法常用Gini指標，假設一個樣本共有類，那么一個節點的Gini不純度可定義為

   其中表示屬于類的概率，當Gini(A)=0時，所有樣本屬于同類，所有類在節點中以等概率出現時，Gini(A)最大化，此時。

   有了上述理論基礎，實際的遞歸劃分過程是這樣的：如果當前節點的所有樣本都不屬于同一類或者只剩下一個樣本，那么此節點為非葉子節點，所以會嘗試樣本的每個屬性以及每個屬性對應的分裂點，嘗試找到雜質變量最大的一個劃分，該屬性劃分的子樹即為最優分支。

   下面舉個簡單的例子，如下圖

   在上述圖中，屬性有3個，分別是有房情況，婚姻狀況和年收入，其中有房情況和婚姻狀況是離散的取值，而年收入是連續的取值。拖欠貸款者屬于分類的結果。

   假設現在來看有房情況這個屬性，那么按照它劃分后的Gini指數計算如下

   而對于婚姻狀況屬性來說，它的取值有3種，按照每種屬性值分裂后Gini指標計算如下

   最后還有一個取值連續的屬性，年收入，它的取值是連續的，那么連續的取值采用分裂點進行分裂。如下

   根據這樣的分裂規則CART算法就能完成建樹過程。

   建樹完成后就進行第二步了，即根據驗證數據進行剪枝。在CART樹的建樹過程中，可能存在Overfitting，許多分支中反映的是數據中的異常，這樣的決策樹對分類的準確性不高，那么需要檢測并減去這些不可靠的分支。決策樹常用的剪枝有事前剪枝和事后剪枝，CART算法采用事后剪枝，具體方法為代價復雜性剪枝法。