概念
CART采用一种二分递归分割的技术，构建决策树时通常采用自上而下的方法，在每一步选择一个最好的属性来分裂。将当前的样本集分成两个子样本集，使得生成的决策树的每个非叶子节点都有两个分支。CART算法生成决策树是结构简洁的二叉树。
CART算法的原理与ID3相似，在CART中提出了杂度削减的概念，按杂度削减最大分裂节点生长决策树，与ID3不同的是，CART最终生成二叉树，然后利用重采样技术进行误差估计和树剪枝，然后选择最优作为最终构建的决策树。其中对于度量结点的不纯度通常有以下指标：Gini、熵、误分类误差。而在CART中使用Gini指标。（注意：C4.5算法与CART类似，也是先建树后剪枝，但具体实现上不同）
GINI（基尼）指数
生长划分终止条件
-
所有的叶结点的样本数为1或者样本属于同一类；
-
决策树高度达到用户设置的阈值；
-
节点中样本个数少于用户指定个数；
-
异质性指标下降的最大幅度小于用户指定的幅度。
树剪枝技术
当分类回归树划分得太细时，会对噪声数据产生过拟合作用，剪枝的主要目的就是防止树的过拟合。剪枝又分为前剪枝和后剪枝：前剪枝是指在构造树的过程中就知道哪些节点可以剪掉，于是干脆不对这些节点进行分裂；后剪枝是指构造出完整的决策树之后再来考查哪些子树可以剪掉。在分类回归树中可以使用的后剪枝方法有多种，比如：代价复杂性剪枝、最小误差剪枝、悲观误差剪枝。
代价复杂性剪枝CCP（Cost-Complexity Pruning）
标准是分类书的简单误分类（基于验证数据的）加上一个对树的大小的惩罚因素。具体如下：
ID3、C4.5和CART的区别
ID3和C4.5都是基于决策树和信息论基础，C4.5是ID3的延伸与改良，而C4.5和CART的区别如下：
