2.9 集成学习与随机森林

1.集成学习的核心直觉：一群弱鸡凑成一个强队

说起来，前面几章我们陆陆续续讲了KNN、朴素贝叶斯、逻辑回归这些单个模型，每一种都有自己擅长的地方，也都有自己够不着的角落。这一章换个思路，把很多个模型凑在一起，让它们集体拿主意。这条路在机器学习里有个专门的名字，叫集成学习（ensemble learning）。

我先讲一条很朴素的经验。古希腊有个说法叫三个臭皮匠顶个诸葛亮，意思是一个普通人的判断可能不准，可如果让好几个普通人各自独立地答一道题，再把答案综合起来，结果常常比一个专家单独答还要靠谱。集成学习干的就是这件事，它训练一群弱学习器（weak learner，也就是单独拎出来表现平平的小模型），再让它们一起投票或者求平均，凑成一个强学习器（strong learner）。

这件事不是玄学，背后有数学撑腰。我们在3.9 节里讲过偏差和方差这对老冤家，一个模型泛化不好，多半是这两个毛病里的至少一个。集成学习特别聪明的地方在于，它能把降偏差和降方差这两件事分头去做。Boosting这一路（比如AdaBoost、GBDT、XGBoost、LightGBM、CatBoost）走的是降偏差的路线，后一个模型专门来纠前一个模型答错的题，一棒接一棒把误差往下压。Bagging这一路（比如这一章的主角随机森林）走的是降方差的路线，让很多个互相独立的模型各答各的，再平均一下，方差就稳了。Boosting我们留到下一章细讲，这一章专心把Bagging和随机森林说透。

2.先理一理偏差和方差，再回头看Bagging为什么能稳

要理解Bagging为什么有用，我们得先把偏差和方差的账算清楚。我们记一个模型在某个样本上的预测为 $\hat{y}$，$\hat{y}$ 是模型给出的预测值，记这个样本的真实答案为 $y$，$y$ 是数据里实际观测到的那个真值。模型每次用不同的训练集去训，会得到不同的 $\hat{y}$，把这些 $\hat{y}$ 在所有可能的训练集上求个平均，记作 $\bar{y}$，$\bar{y}$ 就是模型预测的平均位置。那么模型的期望误差可以拆成三块：

$$\mathbb{E}\big[(y-\hat{y})^2\big] = \underbrace{(y-\bar{y})^2}_{\text{偏差}^2} + \underbrace{\mathbb{E}\big[(\hat{y}-\bar{y})^2\big]}_{\text{方差}} + \sigma^{2}$$

这里 $\mathbb{E}$ 是期望符号，意思是对所有可能的训练集求平均，等号右边第一项叫偏差的平方，衡量平均预测 $\bar{y}$ 离真值 $y$ 有多远，第二项叫方差，衡量同一个模型在不同训练集上预测的波动幅度，第三项 $\sigma^{2}$ 是数据自带的噪声方差（也就是真值 $y$ 本身带的那点不可预测的抖动），$\sigma^{2}$ 这一项我们改不了，只能承认它在那里。

我打个比方，偏差就像是射击的平均落点离靶心的距离，方差是弹孔散得多开。一群各自独立训练出来的决策树，每一棵都过拟合得厉害，单拎一棵出来预测方差 $\operatorname{Var}$ 都很大。我们把单棵树的预测方差记作 $\tau^{2}$，$\tau^{2}$ 是单棵树预测值自身的方差（和数据噪声方差 $\sigma^{2}$ 是两回事），$\operatorname{Var}$ 表示方差这个运算本身。现在如果训练 $B$ 棵互相完全独立的树，$B$ 是树的总棵数，再把它们的预测取平均，新模型的方差会变成：

$$\operatorname{Var}(\bar{y}) = \frac{\tau^{2}}{B}$$

这里 $\bar{y}$ 现在表示 $B$ 棵树预测的平均值。$B$ 越大，方差越小，理论上趋近于零。可现实里这些树毕竟是用同一拨数据训出来的，彼此之间不会完全独立，相关程度记作 $\rho$，$\rho$ 是一个介于 $0$ 到 $1$ 之间的数，刻画树和树之间有多像。考虑相关性之后，平均之后的方差其实是：

$$\operatorname{Var}(\bar{y}) = \rho\tau^{2} + \frac{(1-\rho)\tau^{2}}{B}$$

第一项 $\rho\tau^{2}$ 是树之间相似带来的那部分没法靠平均消掉的方差，第二项随着 $B$ 增大可以压到很小。所以集成降方差能不能压得下去，关键看树和树之间的相关性 $\rho$ 高不高。$\rho$ 越低，集成效果越好。这一观察会直接决定下面随机森林的设计动机，请先记在心里。

3.Bagging：有放回采样造出一堆训练集

Bagging的全称是Bootstrap Aggregating，中文常译作自助聚合。它干的事可以拆成两步。第一步叫bootstrap（有放回采样），第二步叫aggregating（聚合）。

bootstrap说的是这样一件事。假设原始训练集里有 $N$ 个样本，$N$ 是样本总数。我们每次从中随机抽一个样本，记下来，再放回去，下一轮还是从完整的 $N$ 个里抽，这样重复 $N$ 次，就得到一份新的也是 $N$ 个样本的训练集。因为有放回，同一份样本可能在这份新训练集里出现多次，也可能一次都没被抽到。我们这样独立地抽出 $B$ 份训练集，每份都有 $N$ 个样本，彼此之间大致相同又有差别。

有个很经典的结论，一次bootstrap下来，大概有 $37\%$ 的原始样本一次都没被抽到，这部分样本叫OOB（Out-Of-Bag，袋外样本）。这个 $37\%$ 怎么来的呢，单个样本一次没被抽到的概率是 $(1-1/N)^{N}$，当 $N$ 比较大的时候，这个数趋近于 $1/e\approx0.368$，$e$ 是自然对数的底，约等于 $2.718$。所以大约 $36.8\%$，约等于 $37\%$。这部分袋外样本特别有用，可以拿来当现成的验证集评估模型，不必再额外切一份验证集出来，业内管这个叫OOB估计。

聚合这一步就很直白了。如果是分类任务，让 $B$ 个模型各自预测一个类别，最后多数投票，谁票多听谁的。如果是回归任务，把 $B$ 个模型的预测值取平均。说穿了就是少数服从多数或者大家一起求均值。

4.顺带把决策树复习一下

随机森林的基本构件是决策树（decision tree），所以我们顺带把决策树回顾一下。决策树是一棵从根到叶子的二叉或多叉树，每个内部节点挑一个特征做一次判断（比如年龄是否大于60），把样本分流到子节点，一直到叶子节点给出预测。

决策树怎么挑特征呢，常见的有三条路。ID3用信息增益（information gain）来挑，信息增益的定义联系到我们在1.4 节讲过的熵 $H$。C4.5用信息增益率，是对信息增益做了一点修正，避免偏向取值多的特征。CART用基尼指数（Gini index），基尼指数的定义是这样的，对一个有 $K$ 个类别的节点，类别 $k$ 在这个节点里的占比记作 $p_k$，$p_k$ 是节点里第 $k$ 类样本的比例：

$$\text{Gini} = 1 - \sum_{k=1}^{K} p_k^{2}$$

这里 $\sum$ 是求和符号，从第 $1$ 类到第 $K$ 类，把每个 $p_k$ 平方之后加起来。如果这个节点里所有样本都属于同一类，那么对应的 $p_k$ 就是 $1$，其余全是 $0$，Gini等于 $1-1=0$，最纯。如果 $K$ 类均匀分布，Gini接近 $1-1/K$，最乱。决策树每一步都挑那个能让分完之后子节点最纯（也就是不纯度下降最多）的特征和切分点。

单棵决策树有个要命的毛病，它特别容易把训练集死记硬背下来，长成一棵深到离谱的树，训练集准确率接近百分之百，测试集惨不忍睹，这就是过拟合。这恰恰就是Bagging要来治的毛病。

5.随机森林：Bagging再加一道特征随机

到这里随机森林的来历就水到渠成了。Bagging确实能让树和树长得不一样，毕竟每份训练集的样本都不完全相同。可这里有个隐患，如果训练集里有那么一两个特别强的特征（比如某个对预测特别有用的指标），那么每一棵树在根节点附近都会优先挑它来切分，结果所有树长得都差不多，相关性 $\rho$ 就高上去了，前面那个降方差公式里第一项 $\rho\tau^{2}$ 就压不下去，集成的好处就大打折扣。

随机森林（Random Forest）在这个节点上加了一招。每个节点分裂的时候，不让它看全部 $p$ 个特征，$p$ 是特征总数，只随机挑 $m$ 个特征出来，$m$ 通常远小于 $p$，让它在这 $m$ 个里头挑最好的切分。对于分类任务，常用 $m=\sqrt{p}$，也就是取特征总数的平方根。对于回归任务，常用 $m=p/3$。这样一来，即便那个超强特征确实存在，很多时候它压根没被选中，树就被迫去用别的次优特征，长出来的树就花样百出，相关性 $\rho$ 大大下降。

这一招看着简单，效果却出奇地好。它和Bagging组合起来就是完整的随机森林。把这两件事串一下，整个训练流程是这样走的，先用bootstrap造出 $B$ 份训练集，每份上训一棵决策树，每棵树在每个节点分裂时只随机看 $m$ 个特征，长到头都不剪枝，最后让 $B$ 棵树集体投票或者求平均。

随机森林还顺带送我们一个特别实用的副产品，叫特征重要性（feature importance）。它的算法直觉是这样的，某个特征如果在很多棵树里被频繁用来分裂，而且每次分裂都能让不纯度（基尼指数或者信息熵）下降一大截，那这个特征显然对预测很有用。具体做法是把每个节点的不纯度下降量记下来，记节点在分裂前的不纯度为 $I_{\text{parent}}$，分裂后左子节点的不纯度为 $I_{\text{left}}$、右子节点为 $I_{\text{right}}$，左右子节点里的样本数分别记作 $N_{\text{left}}$ 和 $N_{\text{right}}$，父节点里的样本数记作 $N_{\text{parent}}$，那么这次分裂带来的不纯度下降就是：

$$\Delta I = I_{\text{parent}} - \frac{N_{\text{left}}}{N_{\text{parent}}}I_{\text{left}} - \frac{N_{\text{right}}}{N_{\text{parent}}}I_{\text{right}}$$

这里 $\Delta I$ 就是这一次分裂让不纯度下降了多少，下降越多说明这次分裂越值。把每个特征在所有树里贡献的 $\Delta I$ 全部累加起来再求平均，就得到这个特征的重要性得分。这个得分在做特征筛选、向业务方解释模型的时候，几乎人见人爱。

6.随机森林为什么这么讨喜

说起来随机森林在工程界受欢迎不是没来由的。第一，它抗过拟合的能力相当扎实。单棵树容易过拟合，可一上百棵上千棵互相不一样的树凑在一起，各自过拟合的方向都不一样，平均下来就把那些乱七八糟的过拟合给抵消掉了，这是方差公式 $\rho\tau^{2}+(1-\rho)\tau^{2}/B$ 在起作用。

第二，它几乎不用怎么调参。sklearn里的 RandomForestClassifier 默认参数在很多任务上就跑得不错，树的数量 $B$ 调大一点（比如500或者1000）通常就更稳一点，特征抽样数 $m$ 用默认的 $\sqrt{p}$ 一般够用。这点对新手特别友好，对赶工期的工程师更友好。

第三，它能扛高维数据。因为每个节点只看 $m$ 个特征，特征数量 $p$ 哪怕上千上万，每棵树也只挑一小撮来分裂，训练开销可控。这一点比起KNN在高维下被距离诅咒折磨得死去活来（2.5 节讲过），要舒服得多。

第四，它原生就给特征重要性，等于顺带帮你做了一遍特征筛选。新人小张第一次进公司，被丢一份几百列的表格数据让他做信用评分，他甚至都不必先做太多特征工程，跑一个随机森林看看重要性排序，就能把那些没用的列筛掉一大半，再交给后面的精细模型。

当然它也有自己的短板。树多了之后模型体积偏大，预测时要把所有树都跑一遍，速度比不上单一一颗逻辑回归或者一棵小树。它的可解释性也比单棵树要差，毕竟几百棵树摞在一起，你想指着某一条if-else路径解释给业务方听就难了。这些缺点在工程里通常都能接受，不行的话再换Boosting路线。

7.两个小例子，看看实战长什么样

第一个例子来自医疗。小张的导师接了医院一个项目，要预测某个病人是不是会发生术后感染，数据是几百个病人的指标，包括年龄、血压、白细胞计数、过往病史这些。数据量小，特征不算少，还有不少缺失值。小张先试了逻辑回归，准确率一直上不去，调成随机森林之后，OOB准确率从逻辑回归的 $78\%$ 提到了 $86\%$，再一看特征重要性，排在最前面的居然是术前的某项炎症指标，这个发现后来还写进了他们组的小论文里。这件事说明，数据量小、特征关系复杂的表格任务，随机森林常常是性价比最高的起点。

第二个例子来自Kaggle那类表格数据竞赛。如果哪位同学看过Kaggle的历年方案，会发现只要赛题给的是结构化表格数据（比如电商的用户购买预测、物流的到货时间预测），大家几乎人手一个随机森林当baseline（基线模型）。所谓baseline，就是上来先跑一版能用的最朴素的模型，看看分数大概在什么水平，后面所有的花活都拿它做参照。我记得有一年某电商推荐赛，小明用500棵树的随机森林两个小时就跑出baseline，排到中间名次，后面再上XGBoost和LightGBM慢慢往上抠，最后拿了铜牌。他说随机森林最大的好处就是稳，给你一个心里有数的下限，免得后面那些精细调参的尝试跑了半天还不知道是模型的问题还是数据的问题。

讲到这，集成学习两条路里的Bagging这条我们就说清楚了，下一章我们接着讲Boosting那条，看看XGBoost和LightGBM又是怎么把误差一棒一棒压下去的。

练习

Q1. 随机森林相对朴素 Bagging 多加了哪一道随机？为什么要加？

多加了特征随机：每个节点分裂时不看全部 $p$ 个特征，只随机挑 $m$ 个（分类常用 $m=\sqrt{p}$，回归常用 $m=p/3$）。原因是 Bagging 虽然让样本不同，但若有一两个超强特征，每棵树的根节点都会优先选它，所有树长得差不多、相关性 $\rho$ 高，降方差公式里 $\rho\tau^2$ 那一项就压不下去。加了特征随机，强迫树用次优特征，相关性大降，集成效果才好。

Q2. Bagging 里常说的"大约 37% 袋外样本（OOB）"是怎么算出来的？它有什么用？

单个样本一次 bootstrap 没被抽到的概率是 $(1-1/N)^N$，$N$ 较大时趋近 $1/e\approx 0.368$，约 37%。这部分样本这棵树没见过，天然能拿来当验证集评估模型，不必再额外切一份验证集出来，这叫 OOB 估计。

Q3. 随机森林降的是偏差还是方差？请结合偏差-方差分解说明，并和 Boosting 对比。

随机森林走的是降方差那一路。多棵互相独立的树预测取平均后，方差从 $\tau^2$ 降到 $\rho\tau^2+(1-\rho)\tau^2/B$，$B$ 越大、$\rho$ 越小方差越低；它不动偏差，靠平均抵消各棵树各自的过拟合方向。Boosting 才是降偏差的，后一棵专纠前一棵的错，一棒接一棒把误差往下压。

Q4.（面试题） 请写出随机森林特征重要性的计算思路，并说明它和"该特征被选为根节点"是不是一回事。

特征重要性把每次分裂带来的不纯度下降 $\Delta I = I_{\text{parent}}-\frac{N_{\text{left}}}{N_{\text{parent}}}I_{\text{left}}-\frac{N_{\text{right}}}{N_{\text{parent}}}I_{\text{right}}$ 按特征在所有树上累加再求平均，下降越多重要性越高。它不只是"是否被选为根节点"，而是综合了"被用来分裂的频率"和"每次分裂降了多少不纯度"——一个特征即便不在根节点，但在很多节点都被频繁选用且每次降幅大，重要性照样高。