導讀：人工智能機器學習有關算法內容，今天我們重點探討一下CART算法。

繼上兩篇決策樹算法之ID3算法和ID3的改進算法－C4．5算法后，本文繼續討論另一種二分決策樹算法－CART算法。我們知道十大機器學習中決策樹算法占有兩席位置，即C4．5算法和CART算法，可見CART算法的重要性。下面重點介紹CART算法。

不同于ID3與C4．5，CART為一種二分決策樹，是滿二叉樹。CART算法由Breiman等人在 1984 年提出，它采用與傳統統計學完全不同的方式構建預測準則，它是以二叉樹的形式給出，易于理解、使用和解釋。由CART 模型構建的預測樹在很多情況下比常用的統計方法構建的代數學預測準則更加準確，且數據越復雜、變量越多，算法的優越性就越顯著。

CART算法既可用于分類也可用于回歸。CART算法被稱為數據挖掘領域內里程碑式的算法。

CART算法概念：

CART（Classification andRegression Tree）分類回歸樹是一種決策樹構建算法。CART是在給定輸入隨機變量X條件下輸出隨機變量Y的條件概率分布的學習方法。CART假設決策樹是二叉樹，內部結點特征的取值為“是”和“否”，左分支是取值為“是”的分支，右分支是取值為“否”的分支。這樣的決策樹等價于遞歸地二分每個特征，將輸入空間即特征空間劃分為有限個單元，并在這些單元上確定預測的概率分布，也就是在輸入給定的條件下輸出的條件概率分布。

CART算法既可以處理離散型問題，也可以處理連續型問題。這種算法在處理連續型問題時，主要通過使用二元切分來處理連續型變量，即特征值大于某個給定的值就走左子樹，或者就走右子樹。

CART算法組成：

1）決策樹生成：基于訓練數據集生成決策樹，生成的決策樹要盡量大；自上而下從根開始建立節點，在每個節點處要選擇一個最好（不同算法使用不同指標來定義＂最好＂）的屬性來分裂，使得子節點中的訓練數據集盡量的純。

2）決策樹剪枝：用驗證數據集對已生成的樹進行剪枝并選擇最優子樹，這時損失函數最小作為剪枝的標準。這里用代價復雜度剪枝CCP（Cost－Complexity Pruning）。

決策樹的生成就是通過遞歸地構建二叉決策樹的過程，對回歸樹用平方誤差最小化準則，對分類樹用基尼指數最小化準則，進行特征選擇，生成二叉樹。

CART決策樹生成：

1）回歸樹生成

回歸樹采用均方誤差作為損失函數，樹生成時會遞歸的按最優特征與最優特征下的最優取值對空間進行劃分，直到滿足停止條件為止，停止條件可以人為設定，比如當切分后的損失減小值小于給定的閾值 ε，則停止切分，生成葉節點。對于生成的回歸樹，每個葉節點的類別為落到該葉節點數據的標簽的均值。

回歸樹為一棵二叉樹，每次都是按特征下的某個取值進行劃分，每一個內部節點都是做一個對應特征的判斷，直至走到葉節點得到其類別，構建這棵樹的難點在于如何選取最優的切分特征與切分特征對應的切分變量。

回歸樹與模型樹既可以處理連續特征也可以處理離散特征。

回歸樹生成算法如下：

輸入：訓練數據集 D＝｛（x1，y1），（x2，y2），…，（xN，yN）｝

輸出：回歸樹 T

1）求解選擇切分特征 j 與切分特征取值 s ，j 將訓練集 D 劃分為兩部分，R1 與R2 ，依照（j，s）切分后如下：

R1（j，s）＝｛xi｜xji≤s｝ ? R2（j，s）＝｛xi｜xji＞s｝

c1＝1N1∑xi∈R1yi ? ?c2＝1N2∑xi∈R2yi

2）遍歷所有可能的解（j，s），找到最優的 （j＊，s＊） ，最優的解使得對應損失最小，按照最優特征（j＊，s＊）來切分即可。

Min ｛ ∑ （yi–c1）＾2 ＋∑ （yi–c2）＾2 ｝

j，s ? ?xi∈R1 ? ? ? ? ?xi∈R2

3）遞歸調用 1）和2），直到滿足停止條件。

4）返回決策樹 T。

回歸樹主要采用了分治策略，對于無法用唯一的全局線性回歸來優化的目標進行分而治之，進而取得比較準確的結果，但分段取均值并不是一個明智的選擇，可以考慮將葉節點設置為一個線性函數，這便是所謂的分段線性模型樹。實驗表明：模型樹效果比回歸樹的效果要好一些。模型樹只需在回歸樹的基礎上稍加修改即可，對于分到葉節點的數據，采用線性回歸的最小均方損失來計算該節點的損失。

2）分類樹生成

分類樹是CART中用來分類的，不同于 ID3 與 C4．5，CART分類樹采用基尼指數來選擇最優的切分特征，而且每次都是二分。

基尼指數是一個類似與熵的概念，對于一個有 K 種狀態對應的概率為 p1，p2，…，pK的隨機變量 X ，其基尼指數Gini定義如下：

Gini（X）＝∑pk（1？pk）＝1？∑kp2k

k ? ? ? ? ? ? ? ? ? ? ? k

在已知特征 A條件下集合 D 的基尼指數：

Gini（D，A）＝（｜D1｜／｜D｜）＊Gini（D1）＋（｜D2｜／｜D｜）＊Gini（D2）

Gini（D，A）取值越大，樣本的不確定性也越大，這一點與熵類似，所以選擇特征 A 的標準是 Gini（D，A） 的取值越小越好。

分類樹生成算法如下：

輸入：訓練數據集 D＝｛（x1，y1），（x2，y2），…，（xN，yN）｝，停止條件

輸出：分類樹 T

1）利用特征 A 的取值 a 將數據分為兩部分，計算 A＝a時的基尼系數：

Gini（D，A）＝（｜D1｜／｜D｜）＊Gini（D1）＋（｜D2｜／｜D｜）＊Gini（D2）

2）對整個數據集中所有的可能特征 A 以及其可能取值 a 選取基尼系數最小的特征 A＊ 與特征下的取值 a＊，來將數據集切分，將數據 D1、D2 分到兩個子節點中去。

3）對子節點遞歸調用 1）和2） ，直至滿足停止條件

4）返回 CART 樹 T

該算法停止條件可以是節點中的樣本數不能小于給定閾值，或者樣本集的基尼系數小于給定閾值，或者沒有更多的特征。

3）剪枝

CART需要對生成的樹進行剪枝，避免模型過度擬合訓練數據，剪枝時使用的損失函數如下：

Ca（T）＝C（T）＋a｜T｜

C（T）為樹 T 對訓練數據的誤差，可以用基尼系數或者均方損失來表示，a≥0 代表一個權衡訓練數據損失 C（T）與總節點數 ｜T｜的參數，Ca（T） 代表了樹 T 的整體損失，對于固定的 a，一定存在一個確定的使得 Ca（T）最小的子樹，當 a偏大時， ｜T｜ 偏小，樹 T 的規模偏小，反之，樹 T 的規模偏大，Breiman 等人采用遞歸的方法對 CART 進行剪枝，將 a從小增大 ?0＝a0＜a1＜…＜an，如此產生的區間 a∈［ai，ai＋1）， i＝1，2，…，n用對應此區間的 a 產生一系列的子樹序列 ｛T0，T1，…，Tn｝這里 Ti＋1總是由 Ti 剪枝后產生。

剪枝算法如下：

輸入：CART 生成樹 T0

輸出：剪枝后的最優樹 T＊

1）設 k＝0 ， T＝T0 ，a＝＋∞

3） 自下而上的對內部節點 t 計算：

g（t）＝［Ct？C（Tt）］／（｜Tt｜？1）

a＝min（a，g（t））

4） 自上而下的訪問內部節點 t ，對最小的 g（t）＝a進行剪枝，并對葉節點 t 以多數表決形式決定其類別，得到樹 T

5） k＝k＋1， ak＝a，Tk＝T

6） 如果 T 為非單節點樹，回到4）

7） 對于產生的子樹序列 ｛T0，T1，…，Tn｝分別計算損失，得到最優子樹 T＊并返回．

剪枝后的樹便是所需要的CART決策樹。

CART優點：

1） 可以生成可以理解的規則；

2） 計算量相對來說不是很大；

3） 可以處理連續和種類字段；

4）決策樹可以清晰的顯示哪些字段比較重要。

CART缺點：

1） 對連續性的字段比較難預測；

2） 對有時間順序的數據，需要很多預處理的工作；

3）當類別太多時，錯誤可能就會增加的比較快；

4）一般的算法分類的時候，只是根據一個字段來分類。

CART應用場景：

CART算法既可以處理離散型問題，也可以處理連續型問題。CART算法是一種非常有趣且十分有效的非參數分類和回歸方法。它通過構建二叉樹達到預測目的。它已在統計、數據挖掘和機器學習領域中普遍使用，是一種應用廣泛的決策樹算法。

結語：

CART模型最早由Breiman 等人提出，它采用與傳統統計學完全不同的方式構建預測準則，它是以二叉樹形式給出，易于理解、使用和解釋。由CART 模型構建的預測樹在很多情況下比常用的統計方法構建的代數學預測準則更加準確，且數據越復雜、變量越多，CART算法優越性就越顯著。模型的關鍵是預測準則的構建。CART算法在統計、數據挖掘和機器學習等領域得到廣泛應用。