高级统计方法 第一轮学习 Chapter 8 基于树的方法#

回归树#

• 决策树通常是从上到下绘制的，树叶位于树的底部。

• 沿树将预测变量空间分开的点称为内部结点（internal nodes）。个树叶上的数字 表示落在这个树叶处观测值的平均响应值。

建立回归树的过程#

将预测空间（即 $X_1, X_2, \ldots, X_p$）划分为 $J$ 个互不重叠的区域 $R_1, R_2, \ldots, R_J$，并对落入区域 $R_j$ 的每个观测值做同样的预测，预测值为该区域内训练集观测值的算术平均。

理论上，这些区域的形状是任意的。但出于模型简化和增强可解释性的考虑，我们选择将预测变量空间划分为高维矩形，或称盒子（boxes）。

划分区域的目标是找到能最小化训练误差平方和（RSS）的划分方式 $R_1, R_2, \ldots, R_J$。RSS 定义为：

上式中的 $\hat{y}_{R_j}$ 是区域 $R_j$ 内所有训练观测值的平均响应值。

直观理解就是：我们希望通过划分预测变量空间，使得每个区域内的响应值尽可能接近该区域的平均值，从而最小化整体的预测误差。

由于同时考虑所有可能的划分方式计算量过大，因此实际中我们一般采用一种自上而下（top-down）、贪婪（greedy）方法：递归二叉分裂（recursive binary splitting）。

“自上而下”指的是它从树顶端开始依次分裂预测变量空间，每个分裂点都产生两个新的分支。

“贪婪”指的是在每一步分裂时，它只考虑当前分裂点的最佳选择，而不考虑未来可能的分裂方式。

具体步骤如下：

1. 我们首先选择预测变量 $X_j$ 和分割点 $s$，将预测变量空间分为两个区域 $R_1(j, s) = \{X | X_j < s\}$ 和 $R_2(j, s) = \{X | X_j \geq s\}$，使得 RSS 尽可能最小化。

2. 考虑所有可能的预测变量 $j$ 和分割点 $s$，找到使 RSS 最小预测变量和分割点，可设为 $X_j$ 和分割点 $s$。

3. 重复上述步骤，寻找继续分割数据集的最优预测变量和最优分割点，使随之产生的区域中的 $RSS$ 达到最小。此时被分割的不再是整个预测变量空间，而是之前确定的两个区域之一。如此一来就能得到 $3$ 个区域。

4. 不断重复该过程，直到满足某个停止准则为止，例如每个区域内的观测值数量小于某个阈值，或者达到预设的树的最大深度。

树的剪枝#

上述方法会在训练集中取得良好的预测效果，却很有可能造成数据的过拟合，导致在测试集上效果不佳。

一棵分裂点更少、规模更小（区域的个数更少）的树会有更小的方差和更好的可解释性（以增加微小偏差为代价）。

针对上述问题，一种可能的解决办法是：仅当分裂使残差平方和 RSS 的减小量超过某阀值时，才分裂树结点。这种策略能生成较小的树，但可能产生过于短视的问题，一些起初看来不值得的分裂却可能之后产生非常好的分裂，也就是说在下一步中，RSS 大幅减小。

我们还可以考虑另一种方法：剪枝。

代价复杂性剪枝（cost complexity pruning），也称最弱联系剪枝（weakest link pruning），不考虑所有可能的子树，而考虑以非负调整参数 $\alpha$ 标记的一系列子树。

具体的，每一个 $\alpha \geq 0$，都对应着一棵子树 $T \subseteq T_0$，其中 $T_0$ 是原始大树。子树 $T$ 通过最小化下列目标函数得到：

上式中，$|T|$ 是子树 $T$ 中的叶节点个数，$R_m$ 是第 $m$ 个叶节点对应的区域，$\hat{y}_{R_m}$ 是该区域内所有训练观测值的平均响应值。调整系数𝛼在子树的复杂性和与训练数据的契合度之间控制权衡。

调整系数 $\alpha$ 在子树的复杂性和与训练数据的契合度之间控制权衡。

通俗地理解，较大的 $\alpha$ 值会惩罚更复杂的树结构，从而倾向于选择较小的子树；而较小的 $\alpha$ 值则允许更复杂的树结构，以更好地拟合训练数据。

一般我们通过交叉验证来选择最佳的 $\alpha$ 值，从而得到最优的子树。

回归树建立+剪枝算法#

1. 利用递归二叉分裂在训练集中生成一颗大树，只有当终端结点包含的观测值个数低于某个最小值时才停止。

2. 对大树进行代价复杂性剪枝，得到一系列最优子树，子树是 $\alpha$ 的函数，每个 $\alpha$ 对应一系列子树。

3. 利用 K 折交叉验证选择最佳的 $\alpha$ 值：将训练集分为 $K$ 折，对所有的 $k = 1, 2, \ldots, K$，有：

   1. 对训练集上所有不属于第 $k$ 折的数据重复步骤 1 和 2，得到与 $\alpha$ 一一对应的子树。

   2. 计算每个子树在第 $k$ 折数据上的均方误差 MSE。

   上述操作结束后，每个 $\alpha$ 会有相应的 $K$ 个均方预测误差，对这 $K$ 个值求平均，作为此次 $\alpha$ 取值对应的预测误差；选出使平均误差最小的 $\alpha$。

4. 找出选定的 $\alpha$ 值在步骤 2 中对应的子树，作为最终模型。

分类树#

对分类树来说，给定观测值被预测为它所属区域内的训练集中最常出现的类。

分类树的构造#

与回归树类似，分类树也使用递归二叉分裂方法来划分预测变量空间。

但在分类树中，RSS 无法作为划分的标准，因为响应变量是分类变量而非连续变量。

一个自然的代替方法是使用分类错误率（misclassification error rate）作为划分标准。分类错误率定义为：

上式中，$\hat{p}_{mk}$ 是在区域 $R_m$ 中属于第 $k$ 类的观测值所占的比例。

但是事实证明，该指标在构建树的时候不够敏感，对于小比例的类无法有效区分。

通俗理解，就是当一个区域内大部分观测值属于同一类时，分类错误率可能无法反映出该区域内其他类的存在，从而导致划分不够细致。

因此，更常用的指标是基尼指数（Gini index）和互熵（cross-entropy）。

基尼指数#

基尼指数定义为：

其中，$K$ 是类别的总数，$\hat{p}_{mk}$ 是在区域 $R_m$ 中属于第 $k$ 类的观测值所占的比例。

基尼系数衡量的是 $K$ 个类别的总方差。

如果所有的 $\hat{p}_{mk}$ 都接近 $0$ 或 $1$，则基尼指数较小，表示该区域内的观测值大多属于同一类，分类效果较好。因此基尼系数被视为衡量分类纯度的指标。

基尼系数考虑了所有的类别比例，因此在划分时更敏感于类别分布的变化。

互熵#

互熵定义为：

事实上，基尼系数和互熵在数值上非常相似，通常会得出相似的划分结果。

优点#

• 决策树解释性强，在解释性方面甚至比线性回归更方便。

• 树可以用图形表示，非专业人士也可以轻松解释（尤其是当树规模较小时）。

• 有人认为与传统的回归和分类方法相比，决策树更接近人的决策模式。

• 树可以直接处理定性的预测变量而不需创建哑变量。

缺点#

• 遗憾的是，树的预测准确性一般无法达到其他回归和分类方法的水平。

• 基本的决策树有高方差，也即：把训练集随机分成两半，对这两个子集分别建立回归树，可能得到截然不同的两棵树。

通过用装袋法、随机森林和提升法等方法组合大量决策树，可以显著提升树的预测效果。

装袋法#

前节提出的决策树有高方差，比如：把训练集随机分成两半，对这两个子集分别建立回归树，可能得到截然不同的两棵树。

本节将介绍一种减小统计学习方法方差的通用做法，叫做自助法聚集（bootstrap aggregation），或称装袋法（bagging），它在决策树情境下效果很好，颇为常用。

给定 $n$ 个独立观测值 $Z_1, Z_2, \ldots, Z_n$，每个观测值的方差都是 $\sigma^2$，他们的均值 $\overline{Z}$ 的方差为 $\sigma^2 / n$。

即，对一组观测值求平均可以减小方差。

我们通常不能访问多个训练集，但是自助法可以作为替代，就能生成 $B$ 个不同的自助抽样训练集。

用第 $b$ 个自助抽样训练集拟合模型，并求得变量 $x$ 的预测值 为 $\hat{f}_b(x)$，最后对所有预测值求平均得：

此即为装袋法。

通俗理解，装袋法就是通过对原始训练集进行多次自助抽样（bootstrap sampling），生成多个不同的训练集，然后对每个训练集分别训练模型，最后将所有模型的预测结果进行平均，从而得到更稳定、更准确的预测结果。

装袋法（分类树）#

上述公式适用于回归树，对于分类树：对一个给定的测试值，记录 $B$ 棵树各自给出的预测类别，然后采取多数投票（majority vote）：将 $B$ 个预测中出现频率最高的类作为总体预测。

装袋法的测试错误率是树的个数 $B$ 的函数，$B$ 并不是一个对装袋法起决定性作用的参数，$B$ 值很大时也不会产生过拟合。实践中，取足够大的 $B$ 值，可以使得误差稳定下来（如 $B = 100$）。

装袋法（测试误差-OOB）#

有一种无需使用交叉验证就能直接估计装袋模型测试误差的方法。

显然由自助数据集的特性，平均每棵树能利用约三分之二的观测值。剩余三分之一没有使用的观测值被称为此树的袋外（out-of-bag，OOB）观测值。

可以用所有将第 $i$ 个观测值作为 OOB 的树，来预测第 $i$ 个观测值的响应值。这样，便会生成约 $B / 3$ 个对第 $i$ 个观测值的预测。

（换个角度理解：每个点有 $\frac23$ 概率被包含到某棵树中；总共 $B$ 棵树，该点会被包含到 $\frac23 B$ 棵树中，没有被 $\frac13 B$ 包含；所以可以产生 $\frac13 B$ 个 OOB 预测）

当 $B$ 足够大时，OOB 误差实质上与留一法交叉验证误差是等价的。

变量重要性度量#

在装袋回归树建模过程中，可以记录（每棵树上）任一给定预测变量引 发的分裂而减小的 RSS 的总量（回归树），对每个减小总量在所有 $B$ 棵树上取平均。结果值越大则说明预测变量越重要。

同样的道理，在装袋法分类树建模过程中，可以对某一给定的预测变量 在一棵树上因分裂而使基尼系数的减小量加总，再取所有 $B$ 棵树的平均。

随机森林#

随机森林依然需要借助自助抽样训练集建立一系列决策树，与装袋法类似。

不过，随机森林在建立这些决策树时，每考虑树上的一个分裂点，都要从全部的 $p$ 个预测变量中随机选出 $m$ 个预测变量作为候选变量，这个分裂点所用的预测变量只能从这 $m$ 个变量中选择。

在每个分裂点处都重新进行抽样，选出 $m$ 个预测变量，通常 $m \approx \sqrt{p}$，也就是说，每个分裂点所考虑的预测变量的个数约等于预测变量总数的平方根（例如 Heart 数据集共有 $13$ 个预测变量，则取 $m = 4$）。

可以看到，如果 $m = p$，那么退化为装袋法。

通俗理解，所谓的在每个分裂点处都重新进行抽样，选出 $m$ 个预测变量，即每次分裂的时候挑选看哪些预测变量从中选优作为切的一刀的时候，强行规定抓阄来决定候选预测变量集合，从而增加模型的多样性，进一步降低方差。

提升法#

提升法采用相似于装袋法的方式，但是并不是对训练集进行自助抽样，而是按顺序生成一系列决策树。

每棵树的构建都需要用到之前生成的树中的信息（$x$ 不变，$y$ 为残差）。

提升法（对回归树的应用）#

1. 对训练集中的所有的 $i$，令 $\hat{f}(x) = 0$, 并令残差 $r_i = y_i$。

2. 对 $b = 1, 2, \ldots, B$，重复以下步骤：

   1. 对训练数据 $(x_i, r_i)$（变量 $X$ 和当前的残差），建立一颗有 $d$ 个分裂点（切 $d$ 刀，$d + 1$ 个叶子）的回归树 $\hat{f}^b$。

   2. 使用参数 $\lambda$ 压缩所得到的回归树，并将压缩后的新树加入模型以更新 $\hat{f}$：

   $$\hat{f}(x) \leftarrow \hat{f}(x) + \lambda \hat{f}^b(x)$$
   3. 更新残差：
   $$r_i \leftarrow r_i - \lambda \hat{f}^b(x_i)$$

3. 输出经过提升的模型：

上式中，$\lambda$ 是一个介于 $0$ 和 $1$ 之间的小常数。较小的 $\lambda$ 值会使得每棵树对最终模型的贡献较小，从而需要更多的树来达到良好的拟合效果，但通常能提升模型的预测性能。

这一过程背后的理论依据是什么?

• 提升方法与生成一棵大规模的决策树不同，生成大树意味着对数据的严格契合（fitting a data hard）和可能的过拟合，而提升法则是一种舒缓（learning slowly）的训练模型的方法。

• 用现有模型的残差（作为目标变量）生成决策树。也就是说，将现有残差（而不是结果 $Y$）作为响应值。然后把这棵新生成的树进行压缩（压缩参数 $\lambda$），再和前面的树不断累加。通过对残差生成小型的树，在 $\hat{f}$ 效果不佳的地方缓慢地对它进行改进。

• 算法中的参数 $d$ 控制着树的规模（终端节点的个数），通过对 $d$ 的调整，所有这些树都可以变得更小，只有少数终端结点。

• 压缩参数 $\lambda$ 让学习过程进一步变慢，允许更多不同结构的树改变残差。

提升分类树的生成与生成提升回归树的过程相似，但更复杂一些，这 里不作详述。

提升法（三个调整参数）#

1. 树的总数 $B$。与装袋法和随机森林不同，如果 $B$ 值过大，提升法可能出现过拟合，不过即使出现过拟合，其发展也很缓慢。可以用交叉验证来选择 $B$。

2. 取极小正值的压缩参数 $\lambda$。它控制着提升法的学习速度。$\lambda$ 通常取 $0.01$ 或 $0.001$，合适的取值视具体问题而定。若 $\lambda$ 值很小，则需要很大的 $B$ 才能获得良好的预测效果。

3. 每棵树的分裂点数 $d$，它控制着整个提升模型的复杂性。用 $d = 1$ 构建模型通常能得到上佳效果，此时每棵树都是一个树桩（stump），仅由一个分裂点构成。这种情况下的提升法整体与加法模型相符，因为每个树包含一个变量。（每个树桩均抓住了尚未解释的那部分信息）

更多情况下，$d$ 表示交互深度（interaction depth），它控制着提升模型的交互顺序，因为 $d$ 个分裂点最多包含 $d$ 个变量。