1. 前言
分类与回归树（Classification and Regression Trees, CART）是由四人帮Leo Breiman, Jerome Friedman, Richard Olshen与Charles Stone于1984年提出，既可用于分类也可用于回归。本文将主要介绍用于分类的CART。CART被称为数据挖掘领域内里程碑式的算法。
不同于C4.5，CART本质是对特征空间进行二元划分（即CART生成的决策树是一棵二叉树），并能够对标量属性（nominal attribute）与连续属性（continuous attribute）进行分裂。
CART对特征属性进行二元分裂。特别地，当特征属性为标量或连续时，可选择如下方式分裂：
An instance goes left if CONDITION, and goes right otherwise
即样本记录满足CONDITION则分裂给左子树，否则则分裂给右子树。
标量属性
进行分裂的CONDITION可置为不等于属性的某值；比如，标量属性Car Type取值空间为{Sports, Family, Luxury}，二元分裂与多路分裂如下：
连续属性
CONDITION可置为不大于εε；比如，连续属性Annual Income，εε取属性相邻值的平均值，其二元分裂结果如下：
CART算法流程与C4.5算法相类似：
CART剪枝与C4.5的剪枝策略相似，均以极小化整体损失函数实现。同理，定义决策树TT的损失函数为：
Lα(T)=C(T)+α|T| (3)
其中，C(T)表示决策树的训练误差，αα为调节参数，|T|为模型的复杂度。
CART算法采用递归的方法进行剪枝，具体办法：
