说到决策树(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 | \bm 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 = \{(\bm x_1, y_1), (\bm x_2, y_2), ..., (\bm x_i, y_i), ...,(\bm x_n, y_n)\}\),其中 \(\bm x_i\) 是一个 m 维的向量,即 \(x_i\) 含有 m 个 features。

回归问题的目标就是构造一个函数 \(f(\bm x)\) 能够拟合数据集 \(D\) 中的元素,使得 mse 最小,即:
\[\min \frac{1}{n} \sum_{i = 1}^{n} (f(\bm x_i) - y_i)^2\tag{1}\]

用 CART 进行回归,目标自然也是一样的,最小化 mse。

假设一棵构建好的 CART 回归树有 \(M\) 片叶子,这意味着 CART 将输入空间 \(\bm x\) 划分成了 \(M\) 个单元 \(R_1, R_2, ..., R_M\),同时意味着 CART 至多会有 \(M\) 个不同的预测值。CART 最小化 mse 公式如下:
\[\min \frac{1}{n} \sum_{m = 1}^{M}\sum_{\bm x_i \in R_m} (c_m - y_i)^2\tag{2}\]
其中,\(c_m\) 表示第 \(m\) 片叶子的预测值。
想要最小化 CART 总体的 mse,只需要最小化每一片叶子的 mse 即可,而最小化一片叶子的 mse,只需要将预测值设定为叶子中含有的训练集元素的均值,即:
\[c_{m} = ave(y_i | \bm x_i \in leaf_m)\tag{3}\]

所以,在每一次的划分中,选择切分变量(splitting variable)和切分点(splitting point)时(也就是选择 feature 和将该 feature space 一分为二的 split),使得模型在训练集上的 mse 最小,也就是每片叶子的 mse 之和最小。

这里采用启发式的方法,遍历所有的切分变量和切分点,然后选出 叶子节点 mse 之和最小 的那种情况作为划分。选择第 \(j\) 个 feature \(\bm x^{(j)}\) 和它取的值 \(s\),作为切分变量和切分点,则切分变量和切分点将父节点的输入空间一分为二:
\[\begin{split}R_1\{j, s\} = \{\bm x| \bm x^{(j)} \le s\} \\R_2\{j, s\} = \{\bm x| \bm x^{(j)} > s\}\end{split}\tag{4}\]

CART 选择切分变量 \(j\) 和 切分点 \(s\) 的公式如下:
\[\min_{j, s} \left[\min_{c_1} \sum_{\bm x_i \in R_1\{j, s\}} (y_i - c_1)^2 + \min_{c_2} \sum_{\bm x_i \in R_2\{j, s\}} (y_i - c_2)^2 \right]\tag{5}\]

采取遍历的方式,我们可以将 \(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 | \bm x_i \in R_1\{j, s\})\),同理,第二项中 \(c_2 = ave(y_i | \bm x_i \in R_2\{j, s\})\)

算法流程

回归树(Regression Tree)-LMLPHP

ID3 和 C4.5 能不能用来回归?

CART 是一棵二叉树,那么只要回归树不是一棵二叉树,那么就不是 CART 树了。

在分类问题中,ID3、C4.5 和 CART 的区别就在与划分子节点的策略不同,信息增益、增益比、基尼指数;而在回归问题中,criteria 是 mse 或者 mae,这种情况下,分类时的 ID3、C4.5、CART 之间的区别就没了,那么就是每个父节点划分成多少个子节点的问题了,如果还是二叉树,那么就认为是 CART 回归树,否则就不是了。

如果你在同一个时刻对某一个 feature \(\bm 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

References

《统计学习方法》-- 李航
Decision Tree Regression -- scikit-learn

04-18 11:28