CART

CART(Classification And Regression Tree)算法采用一种二分递归分割的技术，将当前 的样本集分为两个子样本集，使得生成的决策树的每个非叶子节点都有两个分支。因此，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算法运行到不能再长出分支位置，从而得到一棵最大的决策树。然后对这棵大树进行剪枝。