CART(CART算法)

CART是一種計算方法。

CART算法

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

（1）創建根節點N

（2）為N分配類別

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

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

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

（6）劃分T得到T1 T2子集

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

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

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

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