CART(Classification And Regression Tree)算法采用一種二分遞歸分割的技術(shù)，將當前 的樣本集分為兩個子樣本集，使得生成的
決策樹的每個非葉子節(jié)點都有兩個分支。因此，CART算法生成的決策樹是結(jié)構(gòu)簡潔的二叉樹。
以下是算法描述：其中T代表當前樣本集，當前候選屬性集用T_attributelist表示。
?。?）創(chuàng)建根節(jié)點N
?。?）為N分配類別
?。?）if T都屬于同一類別or T中只剩下 一個樣本則返回N為葉節(jié)點，為其分配屬性
（4）for each T_attributelist中屬性執(zhí)行該屬性上的一個劃分，計算此劃分的GINI系數(shù)
（5）N的測試屬性test_attribute=T_attributelist中最小GINI系數(shù)的屬性
?。?）劃分T得到T1 T2子集
（7）對于T1重復(fù)（1）-（6）
?。?）對于T2重復(fù)（1）-（6）
CART算法考慮到每個節(jié)點都有成為葉子節(jié)點的可能，對每個節(jié)點都分配類別。分配類別的方法可以用當前節(jié)點中出現(xiàn)最多的類別，也可以參考當前節(jié)點的分類錯誤或者其他更復(fù)雜的方法。
CART算法仍然使用后剪枝。在樹的生成過程中，多展開一層就會有多一些的信息被發(fā)現(xiàn)，CART算法運行到不能再長出分支位置，從而得到一棵最大的決策樹。然后對這棵大樹進行剪枝。
