人工智能機器學習有關算法內容，請參見公眾號“科技優(yōu)化生活”之前相關文章。人工智能之機器學習主要有三大類：1）分類；2）回歸；3）聚類。今天我們重點探討一下CART算法。 

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

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

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

CART算法概念：

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

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

CART算法組成：

CART算法組成如下：

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

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

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

CART決策樹生成：

1）回歸樹生成

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

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

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

回歸樹生成算法如下：

輸入：訓練數據集 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），找到最優(yōu)的 （j＊，s＊） ，最優(yōu)的解使得對應損失最小，按照最優(yōu)特征（j＊，s＊）來切分即可。

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

j，s    xi∈R1          xi∈R2

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

4）返回決策樹 T。

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

2）分類樹生成

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

基尼指數是一個類似與熵的概念，對于一個有 K 種狀態(tài)對應的概率為 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 分到兩個子節(jié)點中去。

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

4）返回 CART 樹 T

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

3）剪枝

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

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

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

剪枝算法如下：

輸入：CART 生成樹 T0

輸出：剪枝后的最優(yōu)樹 T＊

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

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

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

a＝min（a，g（t））

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

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

6） 如果 T 為非單節(jié)點樹，回到4）

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

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

CART優(yōu)點：

1） 可以生成可以理解的規(guī)則；

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

3） 可以處理連續(xù)和種類字段；

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

CART缺點：

1） 對連續(xù)性的字段比較難預測；

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

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

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

CART應用場景：

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

結語：

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

－－－－－－以往文章推薦－－－－－－

機器學習

深度學習

人工神經網絡

決策樹

隨機森林

強化學習

遷移學習

遺傳算法

樸素貝葉斯

支持向量機

蒙特卡羅方法

馬爾科夫模型

Hopfield神經網絡

回歸模型

K鄰近算法

卷積神經網絡

受限玻爾茲曼機

循環(huán)神經網絡

長短時記憶神經網絡

Adaboost算法

ID3算法

C4．5算法