人工智能之機器學習主要有三大類：1）分類；2）回歸；3）聚類。今天我們重點探讨一下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算法組成：
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）的取值越小越好。
更多好文請關注資料星河公衆号（bdg-store）