人工智能之機器學習主要有三大類：1）分類；2）回歸；3）聚類。今天我們重點探討一下CART算法。

我們知道十大機器學習中決策樹算法占有兩席位置，即C4．5算法和CART算法，可見CART算法的重要性。下面重點介紹CART算法。

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

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

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

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

CART算法組成如下：

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

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

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

1）回歸樹生成

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

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

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

回歸樹生成算法如下：

輸入：訓練數(shù)據(jù)集 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é)點設置為一個線性函數(shù)，這便是所謂的分段線性模型樹。實驗表明：模型樹效果比回歸樹的效果要好一些。模型樹只需在回歸樹的基礎上稍加修改即可，對于分到葉節(jié)點的數(shù)據(jù)，采用線性回歸的最小均方損失來計算該節(jié)點的損失。

2）分類樹生成

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

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

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

k k

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

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

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