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）进行分裂。

2. CART生成

前一篇提到过决策树生成涉及到两个问题：如何选择最优特征属性进行分裂，以及停止分裂的条件是什么。

特征选择

CART对特征属性进行二元分裂。特别地，当特征属性为标量或连续时，可选择如下方式分裂：

An instance goes left if CONDITION, and goes right otherwise

即样本记录满足CONDITION则分裂给左子树，否则则分裂给右子树。

标量属性

进行分裂的CONDITION可置为不等于属性的某值；比如，标量属性Car Type取值空间为{Sports, Family, Luxury}，二元分裂与多路分裂如下：

连续属性

CONDITION可置为不大于 

；比如，连续属性Annual Income， 

取属性相邻值的平均值，其二元分裂结果如下：

接下来，需要解决的问题：应该选择哪种特征属性及定义CONDITION，才能分类效果比较好。CART采用Gini指数来度量分裂时的不纯度，之所以采用Gini指数，是因为较于熵而言其计算速度更快一些。对决策树的节点 

，Gini指数计算公式如下：

Gini指数即为 

与类别   的概率平方之和的差值，反映了样本集合的不确定性程度。Gini指数越大，样本集合的不确定性程度越高。分类学习过程的本质是样本不确定性程度的减少（即熵减过程），故应选择最小Gini指数的特征分裂。父节点对应的样本集合为 ，CART选择特征 分裂为两个子节点，对应集合为   与   

；分裂后的Gini指数定义如下：

其中， 

表示样本集合的记录数量。如上图中的表格所示，当Annual Income的分裂值取87时，则Gini指数计算如下：

CART算法

CART算法流程与C4.5算法相类似：

1. 若满足停止分裂条件（样本个数小于预定阈值，或Gini指数小于预定阈值（样本基本属于同一类，或没有特征可供分裂），则停止分裂；
2. 否则，选择最小Gini指数进行分裂；
3. 递归执行1-2步骤，直至停止分裂。

3. CART剪枝

CART剪枝与C4.5的剪枝策略相似，均以极小化整体损失函数实现。同理，定义决策树 

的损失函数为：

其中， 

表示决策树的训练误差， 为调节参数， 

为模型的复杂度。

CART算法采用递归的方法进行剪枝，具体办法：

• 将 

递增         ，计算得到对应于区间     的最优子树为