ISL 真是好书！

资料

An Introduction to Statistical Learning，下文简称 ISL

概述

决策树的方法对于 interpretation 很有用，但是它们在预测准确性上效果不是特别好。

决策树可以同时用于回归变量与分类变量的问题。我们先考虑回归问题，

Regression Trees

Predicting Baseball Players’Salaries Using Regression Trees

我们先看一个简单的例子，我们通过回归树来预测足球运动员的收入，这里的特征是 Year (踢球的年限) 和 Hits (上一年度射中球门的数目) 。 我们先移除收入缺失的行，然后对 Salary 变量进行 log 转换（底为 e），使得它的分布更类似于正态分布。

下图表示了一个回归树的结果，它从树的根部出发。第一个分支条件使 Year < 4.5 ，满足这个条件分到了左枝，这里的 5.11 是所有满足 Year < 4.5 的运动员的薪资均值。以此类推。

这里最终是把所有的运动员分成了3个子群体，如下图所示：

我们如果用决策树的术语，这里的三个子区域 R₁ , R₂ , R₃ 称为 terminal nodes 或 terminal leaves 。 自变量空间被划分的那个节点称为 internal nodes 。在图 8.1 中，总共有2个 internal nodes ，Years < 4.5 和 Hits < 117.5 。我们把决策树上连接 internal nodes 的片段称为 branches 。

我们一般会这么解释图 8.1 的回归树：Years 是最重要的区分 Salary 性状的因子，年限短的运动员挣的钱少，年限长的运动员挣的钱多；如果一个远动员年限短，那么他上一年进球数对他的薪资几乎没有影响。但是如果一个运动员年限长（>4.5年），那么他上一年进球数会对他的薪资造成影响，上一年进球数越多薪资越高。

这种回归树的图是对 Hits ,Years, Salary 三者之间关系的简化，但是它对于其他回归模型有优势，因为它容易解释，而且有可视化效果。

Prediction via Stratification of the Feature Space

我们现在讨论一下构建一个回归树的过程。简单地讲，总共有两步：

1. 我们首先切分 predictor space — 将所有可能的值 X₁ , X₂ ，…… , X_p 分成 J 个互不重叠的区域， R₁, R₂ , ……，R_J 。
2. 对于落在同一区域的观测值，我们会做相同的预测，即这个区域内所有观测值的均值。

我们先看第一步，我们要如何去划分区域呢？一般我们会将各个区域划分成高维矩形，或者称为 boxes ，这样解释结果更简单。我们划分的目标是，找到一组 boxes R₁, R₂ , ……，R_J ，使得 RSS 最小，RSS 计算见下式

下式为 R_j 中所有观测值的均值。

但是，我们不可能穷尽所有的划分方式，找到这个最佳的划分方法。因此我们采取一种称为 recursive binary splitting 的方法。这是一种 top-down 并且是 greedy 的方法，top-down 指从决策树的一开始的节点一直向下切分，每次生成两条新枝；greedy 指在每一步的切分中，所谓的最好的切分方式的决策都仅针对当前这一步，它不会往前看，面向未来，找会使得将来几步最好的切分。

recursive binary splitting 方法的第一步，是选取一个特征 X_j 和相应的一个断点 s ，然后将个预测因子空间切分为两部分，从而使得 RSS 减少得最多。两个子空间如下：

这就要求需要考虑所有得预测因子 X₁ , X₂ ，…… , X_p ，以及每个预测因子上所有可能的断点，然后挑 RSS 最低的组合。RSS 计算方式如下：

之后我们会重复这一步，，但是这次就不是对整个预测因子空间进行切分，而是对上面的两个子空间的一个进行切分，然后我们就有了3个区域。之后我们会再找一个子空间进行切分，这个过程会一直持续，以至于满足了一个停止条件，例如直到所有区域包含不超过 5 个观测值。

一旦我们创建好了所有子区域，我们就可以通过计算子区域内所有观测值的均值，作为这个子区域的预测值。下图为一个 5个子区域划分的例子。

Tree Pruning

上面的划分过程可能会造成 overfitting ，因为划分得到的决策树过于复杂了。一个简单一些的决策树的 variance 更低，解释效果更好，但是 bias 会略有增加。一个可能的解决办法是每次切分过程 RSS 降低量必须超过某个阈值。但是这个策略的问题是短视，因为一个看上去没有意义的切分可能会带来后面的一个很好的切分，即在它后面的一个切分可能RSS降低很多。

因此，一个更好的策略是先生成一个非常大的决策树 T₀ ，然后进行删减得到一个 subtree 。我们如何进行删减分支呢？从目标上，我们的目的是选择一个 test error rate 最低的 subtree 。如果给定一个 subtree， 我们可以通过交叉验证来验证 test error 。但是，对于每一个可能的 subtree 如果都进行交叉验证，计算量就太大了。因此，我们需要一种方式事先挑出少数的一些 subtree 备选。

我们可以通过 Cost complexity pruning 或者称为 weakest link pruning 方法来实现这一点。我们通过指定参数 α 来挑出一部分 trees 。

对于每个给定的 α 值，都存在一个 subtree T ⊂T₀ ，使得下式尽可能小。

这里的 |T| 表示 决策树 T 的 terminal leaf 的数量 , R_m 是相应于第 m 个 terminal leaf 的子空间。这里就是增加了一个惩罚项，越复杂的 subtree 惩罚越严重，通过调控 α 来控制调控比例。我们可以先通过交叉验证得到一个合适的 α 值，然后根据这个 α 值得到相应的最佳的 subtree 。 这个流程如下图：

首先对所有训练集的个体先得到 T₀ 和 best subtree 与 α 的函数。

然后进行交叉验证结果选择最好的 α 值，最后根据 α 值返回第二步找到相应的 best subtree 。

效果如下图，我们可以看到交叉验证结果很好地估计了 Test data error ，交叉验证最佳的 terminal leaf 的数目为3， 使用 test data 的结果的最佳数目为9，但是在terminal leaf 为3的地方有一个明显的下降。

Classification Trees

classification trees 和上面的 regression trees 很相似，仅仅是用于预测分类变量，将每个子空间的预测值改为出现概率最大的那个水平。

创建一个分类树的过程和创建回归树的过程类似。我们先用 recursive binary splitting 方法来创建一个分类树，但是这里不能再用 RSS 作为指标了，一般用 classification error rate ，即观测值和预测值（子空间中最大可能的水平）不一致的比例，公式如下：

下式为 训练集第m个子空间中属于k 水平的比例。

这里，E 就是这个子空间内所有观测值中不是最大可能观测值的比例。但是实际证明这个指标在划分决策树时不够敏感，因为实际我们一般会用另外两个指标。

第一个就是 Gini index, 定义为如下式，可以视为 K 个水平的总方差的衡量公式。只看查看这个式子我们不难发现，如果 p^{^} _mk 越接近于0或1，那么这个式子就越小，因此这个式子也可以视为 node purity 的衡量指标 - 值越小说明这个子空间的预测值越纯。

另外一个指标就是 entropy ， 计算方法如下：

同样地， 当 p^{^} _mk 越接近于0或1，那么这个式子就越小。实际证明这两个式子效果差不多。

因此创建分类树时，我们一般会用 Gini index 或 entropy 作为划分新枝的衡量标准。当我们在 pruning 分枝时，我们可能会不用这两个指标，而是用一开始的 classfication error rate ，因为最终我们的目标还是预测准确性。

在创建新枝的过程中，属于分类变量的特征也可以用于划分新枝，只用把其中的一些水平划给一个分支，把剩下的所有水平划给另外一个分支即可。下图即为一个分类树结果，比如这里的 Thal:a 就表示左边为 Thal 的第一个水平的观测值，右边为其他水平的观测值。

Trees Versus Linear Models

如果反应变量与特征之间存在明显的线性关系，那么线性回归会很合适。但是，如果反应变量与特征之间存在非线性的复杂关系，那么决策树会比那些经典方法更合适。下图就是一个很好的例子，这是一个p=2的分类问题，上方的行表示真实的决策线是线性的，不同的颜色表示不同的水平，这里明显可以看出线性模型效果更好；下方的行中真实决策线是非线性的，这里线性模型的方法无法准确预测，而决策树效果很好。

Advantages and Disadvantages of Trees

决策树的优点如下：

• 结果容易解释
• 更符合人的做决定的方式
• 可视化，不言自明
• 可以直接处理分类变量，而不用像线性模型那样转变为哑变量。

缺点如下：

• 预测准确性没有经典方法高
• 有时不够稳健，换句话说，数据稍有改变，可能最终的决策树就有一个大的改变。

但是，通过使用 bagging, random forests, and boosting ，我们可以提高决策树的预测准确性。

Bagging, Random Forests, Boosting

这三种方法都是使用决策树作为 blocks，来创建更加强大的预测模型。

Bagging

自助法是一种强大的思路，可以计算很难计算或无法计算的因子估计值的标准误。这里我们同样可以用自助法的思想，来提高决策树的效果。

上面我们讨论过，决策树具有 high variance 的缺点，这表明如果我们随机将训练集拆分成两部分，然后对每一部分拟合决策树，我们可能会得到两个完全不同的结果。Bootstrap aggregation，或称为 bagging 方法是一种通用的降低统计方法方差的流程，它对决策树非常有用。

假设我们有一个 n 个独立的观测值的数据集 Z₁,……, Z_n ，观测值的方差为 σ² ，那么观测值均值的方差为 σ² / n 。也就是所，对多个数据集求均值可以降低方差。因此一个降低方差，提高预测准确性的方法就是用多个训练集单独进行模型拟合，最终对所有模型的预测值求均值。比如我们得到了 B 个单独的拟合模型，最终模型的预测值如下：

但是，这在实际中并不可行，因为我们不可能得到很多个训练集。因此，我们可以使用自助法作为替代方法，从一个训练集中有返回地重复抽样，最终生成B个不同的自助法的训练集。代入上式，得到最终的统计模型。这种方法称为 bagging。

Bagging 方法可以显著提高很多回归方法的预测效果，它同样对于决策树也很有用。我们可以用这 B 个自助法训练集来创建 B 个决策树，这些决策树是最深的，没有进行删减。因此这些决策树偏差很小，方差很高。我们通过对这 B 个决策树进行求均值，可以降低方差。

对于反应变量是质量性状的情况，我们可以对这B个决策树的预测结果取 majority vote （占比最高的水平）。

下图中的横坐标为自助法抽样次数，纵坐标为 test error ，这里的黑线就是自助法的结果，黑色虚线是原始结果，我们可以看到自助法没有随着抽样次数的增加出现 overfitting 的问题。实际上，这里 B = 100 就已经够用了。

自助法究竟是如何用到决策树上？

自助法的思路用到线性回归上，这个流程很容易理解，就是把 B 次估计的系数求均值，就得到了最终使用的模型。推导如下：

但是决策树不是每一次分枝情况都不一样吗？这个最终的模型到底是如何构建的呢？没有说清楚。

Out-of-Bag Error Estimation

Bagging 方法有一个直接的估计 test error 的方式，不需要使用交叉验证或者验证集方法。 每个自助集的决策树平均只用了 2/3 的观测值。剩下的没有用到的 1/3 的观测值称为 out-of-bag (OOB) observations。我们可以用当这个观测值为OOB的决策树来预测这个观测值的结果，因此针对某个观测值，我们可以得到差不多 B/3 个预测值。为了获得一个单独的预测值，我们可以对这接近B/3 个预测值求均值，这样每一个观测值都可以得到一个 OOB 预测值，然后我们就可以计算 OOB MSE (反应变量为连续变量) 或者 claffication error (反应变量为分类变量)。实际证明，OOB error 是一个有效地估计 test error 的统计量。如果 K 足够大，那么OOB error 其实就接近于 LOOCV error 。

Variable Importance Measures

bagging 方法可以增加预测准确性，但是缺点在于最终的统计模型难以解释。然而决策树的优势就在于可视化和易于解释。但是 bagging 的结果最终无法显示为一个决策树的可视化结果，也无法显示哪些特征很重要，哪些特征无关紧要。因此，bagging 方法提高了预测准确性，其代价就是降低了模型解释性。

但是我们可以通过 RSS 或 Gini index 来或者所有特征的重要性。例如针对一个 bagging regression trees，我们可以获取所有B个决策树中因为基于某个特征的切分造成的 RSS 的下降值，并求均值。如果这个值很大，说明这个特征很重要。下图为特征重要性的可视化，我们把最重要的特征视为100%，然后其他特征与最重要的特征进行比较。

Random Forests

随机森林对于 bagging 方法做了一些调整，实现了 decorrelates the trees （降低多次抽样的决策树之间的相关性）。就像 bagging 方法，随机森林方法同样会用自助法的思想，创建出多个训练集，然后拟合多个决策树。仅仅是在拟合决策树的过程中，随机森林方法不再使用所有 p 个特征，而是随机抽样挑选 m 个特征用于拟合决策树。一般来说，m 一般设定为约等于 √p 。

举个例子，加入在数据集中有一个效果非常强的特征，其他特征只有中等效果。因此，在 bagging 方法创建的众多决策树中，大部分或所有的决策树都会用这个最重要的特征作为第一次切分的特征。因此，所有的决策树看上去都很像。不幸地是，对高度相关的连续变量求均值无法起到大幅度降低方差的作用。因此，这到这 bagging 方法降低方差的作用可能不是很大。

随机森林方法通过每次都只用一小部分特征来构建决策树克服了这个问题，例如这个例子中，我们大概有 (p-m)/p 的比例的决策树中没有这个最重要的特征，因此其他的特征可以有机会体现作用。我们可以认为这个过程降低了决策树之间的相关，因此对这些决策树求均值的方差更低，结果更可靠。

因此，bagging 和 随机森林的最大区别在于如何选择 m 的大下。如果随机森林选择 m = p，那么这时就是 bagging 方法。上图8.8中显示，随机森林方法相较于bagging方法，test error 和 OOB error 均更低，说明随机森林方法更佳。

当我们有数目很多的并且彼此存在相关的特征时，随机森林方法提升效果更好。这里举个例子，假如我们有 349个个体的 4718 个基因的表达量。在这个数据集中，反应变量是一个15个水平的分类变量：要么是正常，要么就是 1-14 种不同类型的癌症。我们随机将数据分为训练集和验证集，然后挑出训练集中方差最大的 500 个基因，我们的目的是用随机森林的方法使用这500个基因预测个体的癌症类型，其中我们采用了三个不同的 m 值。下图为结果显示，其中一次决策树的 test error rate 是 45.7% 。我们可以看到 m = √p 的效果比 bagging （m=p）效果略好。类似于 bagging，随着 B 的增加，随机森林不会出现 overfit 的情况，因此实际情况中，挑选的B值 只要使得 test error 稳定下来即可。

Boosting

Boosting 方法类似于 Bagging 方法，是一种可以应用在多种统计学习模型中的一般方法。这里仅讨论 Boosting 方法在决策树上的应用。

Boosting 方法也是创建多个决策树，最终综合所有决策树的结果。但是这里不再使用自助法生成训练集，而是相继创建训练集：每一个决策树都会用到上一个决策树的数据。

传统的决策树容易 fitting the data hard ，从而造成 overfitting 。但是 Boosting 方法 learns slowly 。除了第一次创建决策树，之后创建决策树的过程都是使用上一步的残差。算法过程如下：

d 决定每一次决策树的 teminal nodes 的数目；λ 参数用于降低学习速度。一般来说，learn slowly 的统计学习模型效果更好。

对于反应变量是分类变量的流程，ISL 没讲。

Boosting 方法有3个参数：

• The number of trees B. 这里不像 bagging 和 random forests 方法，当 B 很大时，boosting 方法可能会出现 overfitting 现象（虽然过拟合增加的效果很缓慢），所以一般会通过交叉验证选择一个合适的 B 值。
• The shrinkage parameter λ. 这是一个很小的正数，控制每一步学习的速度。一般会采用 0.01 或 0.001 。 λ 值越小，B 要求越大。
• The number d of splits in each tree. 这控制每一步的决策树的复杂度。一般选择 d=1，因此这样每个决策树只有一次切分。最终的模型是可加的，因为每一步的决策树都只包含了一个特征。

下图为 15个水平的癌症基因表达量数据集使用 boosting 的效果。我们可以 d=1 的效果比 d=2 和随机森林的效果都好。一般来说，d=1 效果就可以了，唯一问题在于可能需要增加B的数目，但是在对模型的解释性上很好，因为最终的模型是一个加性模型。

R 代码

略