决策树不仅可以进行分类，也可以进行回归。与线性回归不同，回归树是将“空间”进行划分，每个空间对应一个统一的预测值。

回归树的建立

当面对一个回归问题时，如特征向量为: , 对应数据的多个维度，回归问题就是求出来这个特征向量的预测结果。

回归树所做的事情是：将空间X划分为多个不重叠的领域，其中，每一个划分出来的空间对应一个预测结果，即标签值y，标签值是根据该区域内的总样本数平均化得出的，即：

与线性回归类似，需要一个损失函数对回归的效果进行评估，采用平方残差和RSS进行评估：

内层就是将该区域内所有样本的预测值和真实值之差值的平方进行求和；

外层就是遍历所有划分出来的区域。

但是如果真的按照上述计算公式来进行空间划分的话，计算量将会非常惊人。为了对空间划分进行简化，通常使用递归二分法来对空间进行划分。

递归二分法

什么是递归二分法？顾名思义，树的每次分裂都以二叉树的形式分裂。当我们初步根据特征及其最佳划分点分裂出了2个空间后，不断从当前位置，继续将该空间的样本再次划分成2份。

不同划分空间，生成回归树

划分方案

• 自顶向下：从所有样本开始，不断从当前位置，把样本切分到2个分支里；
• 贪婪：每一次的划分，只考虑当下划分的最优，不会回头考虑先前的划分。

假如回归树的特征向量是2个维度，若第一次分裂时，通过计算得知，当选取属性X1 最佳切分点为 t1 时，得到的损失函数RSS最小，那么本次分裂则可划分出两片区域R1和R2。

划分出R1和R2两个区域后，继续进行树的第二次分裂，若本次分裂根据特征 X2 找到最佳切分点 t2，则可将上图中原R1中的区域再次进行二分。类似的，原样本空间则可根据每一次属性及切分点的选择，以二分裂的形式每次更新两片空间，直到符合某个停止准则，如我们在前文《大数据：如何用决策树解决分类问题》中提到过的预剪枝中的停止准则。

前文《大数据：如何用决策树解决分类问题》介绍了几种可以用于分类问题的决策树，比如ID3和C4.5等。本文要介绍的CART（Classification and Regression Tree）树，既可以用于分类，也可以用于回归。

CART分类树

首先我们先说一下CART分类树，ID3和C4.5都是多叉树，而CART是二叉树，内部节点的取值为“是”或“否”。除此之外，CART分类树和C4.5的最大区别在于选择分裂点时的计算逻辑，C4.5选择分裂点基于信息增益率，而CART分类树基于基尼指数的增益率。

基尼指数反映了从数据集中随机抽取两个样本，其类别标记不一致的概率。基尼指数越小，则数据集纯度越高。

基尼系数

其中Ck代表在数据集D中属于标签值为K的数据样本个数。

总体来说，CART分类树是以基尼系数作为选择的标准，但CART每次分类都以2叉树的形式进行分类，需要进行多次的基尼系数差值的运算才能找到最好的分类结果。

对比C4.5，CART的提升主要包括以下方面：

• C4.5 只能分类，CART 既可以分类也可以回归；
• CART 使用 Gini 系数作为度量，减少了大量的对数运算，运算速度较快；C4.5使用信息增益率作为度量，信息增益率的计算需要使用大量对数运算，计算复杂度较高。

CART回归树

CART回归树与分类树的建立很相似，不同的地方在于连续值的处理方法及最终预测的方式不同。CART回归树使用平方误差最小化准则构建二叉回归树。一棵回归树对应输入空间X的一个划分以及在划分的单元上的输出值。

对于训练集，和CART分类树唯一不同的在于CART回归树面向的是回归问题，即样本的输出为连续型变量。

单一决策树的学习能力是有限的，所以后来人们开始通过集成学习的方法，将多个弱学习器联合在一起，提升为强学习器。

著名的梯度提升机（GBM：Gradient Boosting Machine）中最常见的算法叫做GBDT（Gradient Boosting Decision Tree）。GBDT中的弱学习器就是CART回归树，GBDT就是CART回归树的加性模型，因此也被称为GBRT（Gradient Boosting Regression Tree）。在之后的文章中，我们再来介绍集成学习的方法。