导入：为什么要学习决策树与集成学习

在前面的课程中，我们已经学习了回归方法和分类方法，知道很多统计学习问题都可以理解为：根据输入变量 $x$ 去预测输出变量 $y$。如果因变量是连续变量，我们通常考虑回归；如果因变量是离散变量，我们通常考虑分类。第8讲进一步讨论一类非常重要的方法：决策树与集成学习。

与线性回归、Logistic 回归等模型相比，基于树的方法具有几个非常突出的特点：第一，它几乎不要求我们事先对总体分布作严格假设；第二，它的建模过程接近人类“按条件一步步判断”的思维方式；第三，它既可以处理分类问题，也可以处理回归问题；第四，它天然具有较好的可视化和解释性。与此同时，单棵树也存在方差大、不稳定、容易过拟合等问题，因此进一步发展出了 Bagging、随机森林、Boosting、GBDT、XGBoost 等组合学习方法。

分类

分类问题的基本形式

• 当因变量取离散值时，我们称之为分类。模仿回归的表达式，我们可以将分类问题写成

• 其中，$f$是关于$x$的函数，往往被称为分类器（classifier），比如 Logistic 模型、决策树、随机森林和支持向量机等都是经典的分类器。

分类问题

• 基于树的方法是数据科学、机器学习里最常用的方法之一，本质上它是一种非参数方法，因为我们不需要事先对总体的分布作任何假设。
• 决策树的算法很多，首先以经典的 CART 算法开始，它既可以做分类，也可以做回归。为了防止过拟合，常常是先生成一棵大树，然后对生成的树进行剪枝。
• 最后，介绍几种基于决策树的组合学习方法（ensemble learning）。因为基于树的方法简单且易于解释，但存在方差大、不稳定的问题。而通过组合算法常常能降低方差，大大提高预测效果，虽然与此同时会损失一些解释性。

问题的提出

例子1：乳腺癌良恶性分类

• MASS 库包含的乳腺癌（biopsy）数据集。该数据集来自威斯康星麦迪逊大学医院，共有 699 个观测和 11 个变量。
• 除了不纳入分析的病人 ID 外，包含了病人乳腺肿瘤切片的诊断信息（Class），以及 9 个与是否为恶性肿瘤相关的检验指标，如肿块厚度、细胞大小均匀性等。每个病人在这些细胞特征上都有一个 1 到 10 的得分，其中 1 更接近良性，10 更接近病变。
• 如果希望根据这 9 个检验指标的得分来预测病人是否为恶性肿瘤，就可以把它看作一个典型的分类问题。

数据1

例子2：儿童座椅销量预测

• ISLR 库中包含的座椅（Carseats）数据集，是一个包含 400 个不同商店儿童座椅销售情况的模拟数据集，共有 11 个变量。
• 我们感兴趣的是儿童座椅的销售量（Sales，单位：千），可能与其相关的变量包括地区收入水平（Income）、广告预算（Advertising）、人口规模（Population）、价格（Price）等。
• 若想了解各因素对儿童座椅销售量是否有影响，并进一步进行销量预测，就可以建立回归树模型。

数据2

这两个例子说明：树模型既可以做分类，也可以做回归，关键差别在于因变量的类型与节点纯度度量方式不同。

决策树

决策树与 CART 思想

• 决策树方法最早产生于20世纪60年代，其中 CART（Classification and Regression Tree）算法是决策树最经典和最主要的算法。
• CART 算法是 Breiman 等在 1984 年提出的一种非参数方法，它既可以解决分类问题，又可以解决回归问题，分别称为分类树（Classification Tree）和回归树（Regression Tree）。

决策树的基本思想

• CART 算法的基本思想是一种二分递归分割方法。在计算过程中充分利用二叉树，在一定的分割规则下将当前样本集分割为两个子样本集，使得生成的决策树的每个非叶节点都有两个分裂，这个过程又在子样本集上重复进行，直至无法再分裂为止。

从几何角度看，决策树实际上是在不断划分自变量空间；从预测角度看，决策树是在不断寻找“在哪个变量上、以哪个阈值切一刀，能让分组后的样本更纯”。

基本概念

1. 节点

决策树包含三种节点：

• 根节点（root node）：建模之初全部样本组成的节点，没有入边，只有出边；
• 中间节点（internal node）：根节点和叶节点之外的节点，既有入边，又有出边；
• 叶节点（leaf node）：不再继续分裂的节点，也称终端节点（terminal node），没有出边，只有入边。

叶节点的个数决定了树的规模和复杂程度。

决策树的分割过程

• 根节点在一定的分割规则下被分割成两个子节点，这个过程在子节点上重复进行，直至无法再分裂为叶节点为止。

决策树的建立

• 在 Carseats 数据集中，如果只考虑 Income 和 Advertising 两个自变量来预测 Sales，则可以生成一棵含有三个叶节点的回归树。

• 这棵树由一系列从树顶端开始的分裂规则构成。例如根节点是 Advertising < 8，则对于所有 Advertising < 8 的样本，其 Sales 都将被预测为 7.149；中间节点可能是 Income < 73.5，则所有 Advertising ≥ 8 且 Income < 73.5 的样本，其 Sales 被预测为 7.533；其余样本则被预测为 9.881。
• 如果把这个过程放到二维平面中去理解，就会发现决策树其实是在对特征空间进行区域划分，而每一个叶节点对应一个划分区域。

决策树的区域划分思想

将上述过程推广到多维情形，决策树可以概括为两个步骤：

1. 将自变量空间 $X_1, X_2, \cdots, X_p$ 的所有可能取值划分成 $J$ 个互不重叠的区域 $R_1, R_2, \cdots, R_J$；
2. 对落入区域 $R_j$ 的每个观测，都将其预测为该区域中训练样本响应值的简单统计量。

• 对于回归树，这个统计量通常是区域内响应值的平均值；
• 对于分类树，这个统计量通常是区域内占比最高的类别。

因此，树模型的本质可以理解为：先分区，再在区内给出一个统一预测。

如何构建区域

• 理论上，区域可以有各种复杂形状，但为了简化建模过程并增强可解释性，实际中通常只把空间划分为高维矩形。
• 区域划分一般采用一种自上而下（top-down）、贪婪（greedy）的方法，即递归二叉分裂（recursive binary splitting）。所谓“自上而下”，是指从树顶端开始依次分裂；所谓“贪婪”，是指每一步都只选择当前看起来最优的分裂，而不是从全局角度寻找未来可能最优的整体结构。
• 在每一个节点上，我们都要寻找继续分割数据集的最优自变量和最优分裂点。这一过程不断持续，直到满足某个停止准则，例如叶节点包含的观测值个数低于某个最小值时停止分裂。

分裂准则与节点不纯度

如何确定最优分裂？核心思想是比较分裂前后节点不纯度的变化。不同类型的树使用不同的不纯度指标：

• 对于分类树，常用指标包括 Gini 指数、交叉熵（或偏差）以及分类错误率；
• 对于回归树，常用指标是残差平方和 RSS 的下降量。

原则上，好的分裂应该使得分裂后的子节点更“纯”，也就是类别更集中，或者数值波动更小。

剪枝

为什么要剪枝

• 决策树虽然能在训练集上取得很好的预测效果，但却很容易过拟合，在测试集上表现不佳。因此，在实际应用中往往需要控制树的复杂度。

两类剪枝方法

• 事先剪枝（pre-prune）：在建树过程中就限制继续分裂，比如要求某个节点的不纯度下降必须超过阈值，否则停止分裂。其问题是可能过早停止，从而错失后续更优分裂。
• 事后剪枝（post-prune）：先让树尽可能长大，再在大树基础上进行修剪。实践中更常用的就是事后剪枝。

复杂性剪枝

实际中，最常用的是代价复杂性剪枝（cost complexity pruning）。它先让树充分生长，得到 $T_0$，然后在 $T_0$ 的基础上修剪。设 $|T|$ 表示子树 $T$ 的叶节点数，$n_m$ 表示叶节点 $R_m$ 的样本量，则代价复杂性剪枝的目标函数为：

其中：

• $Q_m(T)$ 表示叶节点 $m$ 的不纯度；
• $\alpha$ 是复杂度惩罚参数；
• $|T|$ 越大，树越复杂。

我们的目标是找到使 $C_\alpha(T)$ 最小的子树 $T_\alpha$。在实践中，通常利用交叉验证来选择最优的 $\alpha$。

分类树

分类树的基本思想

• 当因变量为定性变量时，可建立分类树模型。分类树的建模过程就是自动选择分裂变量以及分裂条件，使得分裂后的节点纯度尽可能高。
• 假设数据 $(x_i, y_i)$ 包含 $p$ 个输入变量和一个分类型因变量 $y \in {1,2,\cdots,K}$，样本量为 $n$。我们希望把数据分成 $M$ 个区域，第 $m$ 个区域 $R_m$ 的样本量为 $n_m$。

分类树算法

分类树算法

三指标关系

这些图展示了分类树中几种常用不纯度指标之间的关系。通常来说：

• Gini 指数越小，说明节点越纯；
• 交叉熵越小，说明不确定性越低；
• 分类错误率越低，说明分类越准确。

在实际建树过程中，Gini 指数是 CART 分类树中最常用的分裂准则之一。

分类图

这类图形有助于理解：分类树得到的决策边界往往是分段、分层、轴平行的，而不是像 Logistic 回归那样通常给出一条整体的线性边界。

回归树

回归树的基本思想

• 回归树和分类树的基本思想相同，只是在分裂准则和叶节点预测值的定义上不同。
• 当因变量为连续型变量时，可建立回归树模型。对于分类树，叶节点通常预测为节点内比例最高的类别；对于回归树，则是将落在叶节点中的观测点的平均值作为该叶节点的预测值。

回归树算法

回归树结果

回归树通常以最小化区域内残差平方和为目标，因此它更适合捕捉变量之间的非线性关系和分段规律。

树模型的优缺点

优点

• 易理解，解释性强；
• 不需要任何先验分布假设；
• 与传统回归和分类方法相比，更接近人的决策模式；
• 可以用图形直观展示，非专业人士也容易理解；
• 可以直接处理定性的自变量，而不需要像线性模型那样事先转换为虚拟变量。

缺点

• 单棵决策树方差大，不稳定；
• 数据发生很小扰动时，可能得到完全不同的分裂结果；
• 容易过拟合；
• 预测性能往往不如强组合模型。

正因为如此，基于树的组合学习方法得到了广泛发展。课件中明确指出，常用的组合算法主要有装袋法（Bagging）、随机森林（Random Forest）和提升法（Boosting）等。

Bagging

基本思想

• Bagging 是 bootstrap aggregating 的缩写，它利用 Bootstrap 抽样方法对训练集反复有放回抽样，得到一系列新的训练集；在每个训练集上分别建立一个预测器；最后再把这些预测器的结果进行综合。
• 它的理论直觉很简单：如果一组预测器各自存在波动，那么对它们求平均或投票，往往能够降低方差。

设训练样本集为 $T=(x_i,y_i)$。如果我们能从总体中抽取多个训练集，对每个训练集分别建立模型，再对多个预测值进行平均或投票，就能得到更稳定的最终模型。但现实中通常只有一个训练集，因此需要借助 Bootstrap 抽样来“模拟”多个训练集。

Bagging 的核心步骤

1. 对原训练集进行有放回抽样，生成 $B$ 个 Bootstrap 样本；
2. 对每一个 Bootstrap 样本分别训练一棵树；
3. 对分类问题，采用多数投票得到最终结果；
4. 对回归问题，采用平均预测值得到最终结果。

Bagging 算法

说明

• 树的棵数 $B$ 一般不是一个决定性参数。$B$ 很大时通常不会导致过拟合，但会增加计算量。
• 在实践中，取足够大的 $B$ 值，比如 200 左右，通常就可以使误差趋于稳定。
• Bagging 是一种组合学习思想，不只适用于决策树，也可以扩展到其他基学习器，但树模型是它最经典的应用场景。

变量重要性的度量

• 与单棵树相比，Bagging 往往能显著提升预测精度，但解释性会下降。
• 对于回归树，可以考察打乱某个变量前后 RSS 减少量的变化；若打乱后模型性能显著下降，则说明该变量重要。
• 对于分类树，可以考察某变量参与分裂时导致 Gini 指数下降的总量，并在所有树上取平均。平均下降越大，变量越重要。

重要性

随机森林

随机森林（RF）

• 随机森林是 Breiman 于 2001 年提出的一种统计学习方法。
• 它与 Bagging 类似，首先生成大量树，再对各棵树的结果进行投票或平均得到最终预测结果。
• 两者的关键区别在于：Bagging 只是对样本做 Bootstrap 抽样；而随机森林不仅对样本进行抽样，还在每次分裂时只从自变量的一个随机子集中选择最优分裂变量，从而实现对树之间相关性的削弱。

也就是说，随机森林是通过“去相关（decorrelate）”来改进 Bagging 的一种算法。

随机森林算法

说明

• Bagging 和随机森林最大的不同就在于自变量子集规模 $m$ 的选择。
• 如果在每次分裂时都取 $m=p$，那么随机森林就退化为 Bagging。
• 和 Bagging 一样，随机森林也可以利用袋外（out-of-bag, OOB）样本来估计预测误差，也可以得到变量重要性排序。
• 随机森林同样不会因为 $B$ 的增大而过拟合，因此在实践中通常也取足够大的 $B$，比如 $B>200$ 时误差往往已较稳定。

提升法

提升法的基本思想

• 提升法（Boosting）也是一种把多个弱学习器组合成强学习器的方法。
• 与 Bagging 不同，Bagging 的各棵树是相互独立、并行训练的；而 Boosting 中的各棵树是顺序生成的，后一棵树要利用前面树所留下的信息，重点修正前面模型没有学好的部分。

这意味着：

• Bagging 更强调“并行平均，降低方差”；
• Boosting 更强调“串行纠错，降低偏差”。

常见 Boosting 方法

课件中重点提到三类典型算法：

• AdaBoost
• GBDT（Gradient Boosting Decision Tree）
• XGBoost

AdaBoost

• AdaBoost 的核心思想是：对前一轮分类错误的样本赋予更高权重，使后续学习器更加关注“难分样本”。
• 因此，AdaBoost 的本质是一种“错误驱动”的顺序学习策略。

GBDT

• 与 AdaBoost 不同，GBDT 在每一步并不是直接修改样本权重，而是通过训练一个新学习器去拟合当前损失函数在负梯度方向上的残差，从而逐步降低总体损失。
• GBDT（Gradient Boosting Decision Tree）的关键思想可以理解为：每一轮都用一棵新树去纠正前面所有树的残差。
• 相较于经典 AdaBoost 主要适用于指数损失下的二分类任务，GBDT 通过选择不同的可微损失函数，可以处理回归、分类、排序等更广泛的学习任务。

GBDT 算法

XGBoost

• XGBoost 是 Extreme Gradient Boosting 的简称，是陈天奇于 2016 年提出并推广的一种高效集成学习算法。
• 它本质上是在 GBDT 的基础上做了系统改进，更强调运算效率、正则化控制和工程可实现性。

XGBoost 的主要特点

1. 传统 GBDT 主要利用一阶导数信息，而 XGBoost 对损失函数做二阶泰勒展开，同时利用一阶与二阶导数信息；
2. 在目标函数中加入正则项，权衡损失下降与模型复杂度，从而降低过拟合；
3. 支持并行计算，能更高效地利用 CPU 多线程；
4. 能处理回归、分类、排序等多种任务；
5. 在实际数据挖掘比赛和工业界应用中表现非常强大。

• 正因为预测性能突出，XGBoost 成为很多机器学习竞赛中的常用方法，但与此同时，它的参数较多、调参也更复杂。

XGBoost 图示

##

决策树与集成学习的比较总结

单棵树 vs 组合树

从整体上看，可以把本讲的方法分成两类：

1. 单棵树方法

• 分类树
• 回归树

特点是：解释性强、结构清晰、便于可视化，但容易过拟合、方差较大。

2. 集成树方法

• Bagging
• 随机森林
• AdaBoost
• GBDT
• XGBoost

特点是：预测性能更强、更稳定，但模型解释性下降，训练和调参更复杂。

这几类方法的逻辑关系

• Bagging：并行生成多棵树，降低方差；
• 随机森林：在 Bagging 基础上进一步让树之间“去相关”；
• Boosting：顺序生成多棵树，逐步修正误差；
• GBDT：Boosting 在损失函数梯度方向上的实现；
• XGBoost：对 GBDT 的高效改进版本。

因此，本讲的核心逻辑可以概括为：

单棵树强调解释，组合树强调预测。

R 实现与实践提示

• tree：基础树模型；
• rpart：CART 建模与剪枝；
• randomForest：随机森林；
• gbm：GBDT；
• xgboost：XGBoost。

在实践中，通常需要关注以下几个问题：

1. 树的深度是否过大；
2. 叶节点最小样本数如何设置；
3. 是否需要交叉验证选择复杂度参数；
4. 随机森林中树的棵数 $B$ 与变量子集规模 $m$ 如何选择；
5. Boosting / XGBoost 中学习率、树深、正则项等参数如何调节。

本讲小结

本讲围绕“决策树与集成学习”展开，主线非常清晰：先介绍树模型的基本思想，再讨论分类树和回归树，然后进一步说明为什么单棵树虽然直观，但不够稳定，于是引出 Bagging、随机森林和 Boosting 等组合方法。

如果用一句话概括本讲，可以表述为：

决策树通过不断划分特征空间完成预测，而集成学习通过组合大量树模型，在牺牲部分解释性的同时显著提升了模型的稳定性与预测能力。