前面兩篇文章給大家介紹了ID3和C4.5決策樹分類算法，今天給大家介紹CART決策樹分類算法。
CART算法簡介（Classification And Regression Tree）
CART同樣由特徵選擇、樹的生成及剪枝組成，即可以用於分類也可以用於迴歸
CART假設決策樹是二叉樹，內部結點特徵的取值為“是”和“否。這樣的決策樹等價於遞歸地二分每個特徵
二叉樹不易產生數據碎片，精確度往往也會高於多叉樹，所以在CART算法中，採用了二元劃分
CART與前面介紹的ID3算法和C4.5算法不同的是，使用的屬性度量標準是Gini指標
Gini指數
Gini指數主要是度量數據劃分或訓練數據集D的不純度為主，Gini值越小，表明樣本的“純淨度”越高
Gini指數的定義和計算
對缺失值和連續屬性的處理
對缺失值的處理詳見《常用數據挖掘算法從入門到精通 第八章 C4.5決策樹分類算法》中有介紹
對於離散值屬性，在算法中遞歸的選擇該屬性產生最小Gini指標的子集作為它的分裂子集
對於連續值屬性，必須考慮所有可能的劃分點。其策略類似於C4.5算法中介紹的方法，利用Gini指數最小原則，選擇劃分點
CART決策樹的算法步驟
創建根節點R
如果當前DataSet中的數據的類別相同，則標記R的類別標記為該類
如果決策樹高度大於alpha，則不再分解，標記R的類別classify(DataSet)
遞歸情況：
標記R的類別classify(DataSet)
從featureList中選擇屬性F（選擇Gini(DataSet, F)最小的屬性劃分，連續屬性參考C4.5的離散化過程(以Gini最小作為劃分標準)）
根據F，將DataSet做二元劃分DS_L 和 DS_R：
如果DS_L或DS_R為空，則不再分解
如果DS_L和DS_R都不為空，節點：
C_L= CART_classification(DS_L, featureList, alpha);
C_R= CART_classification(DS_R featureList, alpha)
將節點C_L和C_R添加為R的左右子節點
CART算法實例分析
CART算法和ID3算法以及C4.5算法的過程基本都是相同的，主要的區別就是在屬性選擇標準上CART算法採用Gini指數作為選擇標準，其他過程基本一樣，《第七章 ID3決策樹分類算法》和《 第八章 C4.5決策樹分類算法》都給出了不同的案例和決策樹具體計算構建過程，感興趣的讀者可以參照本章前面給出的Gini指數的計算方法，將前面給出的案例算一算用以構建CART決策樹。