CART

CART演演算法

以下是演演算法描述：其中T代表當前樣本集，當前候選屬性集用T_attributelist表示。

（徠1）創建根節點N

（2）為N分配類別

（3）ifT都屬於同一類別orT中只剩下一個樣本則返回N為葉節點，否則為其分配屬性

（4）foreachT_attributelist中屬性執行該屬性上的一個劃分，計算此劃分的GINI係數

（5）N的測試屬性test_attribute=T_attributelist中最小GINI係數的屬性

（6）劃分T得到T1T2子集

（7）對於T1重複（1）-（6）

（8）對於T2重複（1）-（6）

CART演演算法考慮到每個節點都有成為葉子節點的可能，對每個節點都分配類別。分配類別的方法可以用當前節點中出現最多的類別，也可以參考當前節點的分類錯誤或者其他更複雜的方法。

CART演演算法仍然使用后剪枝。在樹的生成過程中，多展開一層就會有多一些的信息被發現，CART演演算法運行到不能再長出分支為止，從而得到一棵最大的決策樹。然後對這棵大樹進行剪枝。