说到决策树（Decision tree），我们很自然会想到用其做分类，每个叶子代表有限类别中的一个。但是对于决策树解决回归问题，一直是一知半解，很多时候都是一带而过。
对于一个回归问题，我们第一时间想到的可能就是线性回归（linear regression），当线性回归不好的时候，可能想着用 SVR（Support Vector Regression）试试。但回归树（regression tree）也很重要，现在 shallow learning 被 SVM 和树模型统治，随机森林、GBDT、xgboost、lightGBM 大行其道，所以知道什么是回归树很有必要。
常用的决策树有 ID3、C4.5、CART 等，其中 CART 就可以用来做回归问题，CART 全称就是 Classification And Regression Tree（分类和回归树）。至于 ID3 和 C4.5，能不能用来做回归问题，等了解完 CART 回归树再讨论。
接下来我们介绍将 CART 用于回归问题。
回归树
回归树（regression tree），顾名思义，就是用树模型做回归问题，每一片叶子都输出一个预测值。预测值一般是该片叶子所含训练集元素输出的均值，即 (c_{m} = ave(y_i | m x_i in leaf_m))。
CART 在分类问题和回归问题中的相同和差异：
- 相同：
- 在分类问题和回归问题中，CART 都是一棵二叉树，除叶子节点外的所有节点都有且仅有两个子节点；
- 所有落在同一片叶子中的输入都有同样的输出。
- 差异：
- 在分类问题中，CART 使用基尼指数（Gini index）作为选择特征（feature）和划分（split）的依据；在回归问题中，CART 使用 mse（mean square error）或者 mae（mean absolute error）作为选择 feature 和 split 的 criteria。
- 在分类问题中，CART 的每一片叶子都代表的是一个 class；在回归问题中，CART 的每一片叶子表示的是一个预测值，取值是连续的。
下面以 criteria = 'mse' 为例，介绍 CART 回归树。
理论解释
给定一个数据集 (D = {(m x_1, y_1), (m x_2, y_2), ..., (m x_i, y_i), ...,(m x_n, y_n)})，其中 (m x_i) 是一个 m 维的向量，即 (x_i) 含有 m 个 features。
回归问题的目标就是构造一个函数 (f(m x)) 能够拟合数据集 (D) 中的元素，使得 mse 最小，即：
用 CART 进行回归，目标自然也是一样的，最小化 mse。
假设一棵构建好的 CART 回归树有 (M) 片叶子，这意味着 CART 将输入空间 (m x) 划分成了 (M) 个单元 (R_1, R_2, ..., R_M)，同时意味着 CART 至多会有 (M) 个不同的预测值。CART 最小化 mse 公式如下：
其中，(c_m) 表示第 (m) 片叶子的预测值。
想要最小化 CART 总体的 mse，只需要最小化每一片叶子的 mse 即可，而最小化一片叶子的 mse，只需要将预测值设定为叶子中含有的训练集元素的均值，即：
所以，在每一次的划分中，选择切分变量（splitting variable）和切分点（splitting point）时（也就是选择 feature 和将该 feature space 一分为二的 split），使得模型在训练集上的 mse 最小，也就是每片叶子的 mse 之和最小。
这里采用启发式的方法，遍历所有的切分变量和切分点，然后选出 叶子节点 mse 之和最小 的那种情况作为划分。选择第 (j) 个 feature (m x^{(j)}) 和它取的值 (s)，作为切分变量和切分点，则切分变量和切分点将父节点的输入空间一分为二：
CART 选择切分变量 (j) 和 切分点 (s) 的公式如下：
采取遍历的方式，我们可以将 (j) 和 (s) 找出来：先固定 feature (j) 再选出在该 feature 下的最佳划分 (s)；对每一个 feature 都这样做，那么有 (m) 个feature，我们就能得到 (m) 个 feature 对应的最佳划分，从这 (m) 个值中取最小值即可得到令全局最优的 ((j, s))。式（5）中，第一项 (min_{c_1} sum_{x_i in R_1{j, s}} (y_i - c_1)^2) 得到的 (c_1) 值按照式（3）就是 (ave(y_i | m x_i in R_1{j, s}))，同理，第二项中 (c_2 = ave(y_i | m x_i in R_2{j, s})) 。
算法流程
ID3 和 C4.5 能不能用来回归？
CART 是一棵二叉树，那么只要回归树不是一棵二叉树，那么就不是 CART 树了。
在分类问题中，ID3、C4.5 和 CART 的区别就在与划分子节点的策略不同，信息增益、增益比、基尼指数；而在回归问题中，criteria 是 mse 或者 mae，这种情况下，分类时的 ID3、C4.5、CART 之间的区别就没了，那么就是每个父节点划分成多少个子节点的问题了，如果还是二叉树，那么就认为是 CART 回归树，否则就不是了。
如果你在同一个时刻对某一个 feature (m x^{(j)}) 选择两个切分点 (s_1) 和 (s_2) 来划分父节点，那么就将产生三个区间 (R_1{j, s_1}, R_2{j, s_1, s_2}, R_3{j, s_2})，这种做法无疑增大了遍历的难度，如果选择更多个切分点，那么遍历的难度会指数上升。如果我们想要细分多个区域，让 CART 回归树更深即可，这样遍历的难度会小很多。
所以，固然可以构建非 CART 回归树，但是不如 CART 回归树来的更简单。
回归树示例
Decision Tree Regression -- scikit-learn