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