第十章 集成学习

1 集成学习概要

在集成学习中，个体学习器的准确率和彼此之间的差异性都至关重要

弱学习器

在特定学习任务上性能略高于随机猜测的学习器

分类

• **Bagging：**个体学习器间存在强依赖关系的并行化方法（放回取样）

  是一族并行化集成学习算法，其一般通过训练多个独立的基学习器，将它们的预测结果进行平均或投票，以得到最优结果

  对样本的抽取是有放回的

  为避免样本未被选中带来的信息损失，在Bagging集成中，可将未被选中的样本作为测试集，而不用预先对数据集划分训练集和测试集

• **Boosting：**个体学习器间不存在强依赖关系的序列化方法

  是一族序列化集成学习算法，通过训练一系列基学习器，将它们加权结合成一个泛化性能强的强学习器

  对于前序基学习器预测错误的样本，通过重新赋权为这些错误分类的样本赋予更高的权重，这能使下一个基学习器更关注这些样本

  使用Boosting集成时，为防止过拟合以及欠拟合，通常会选择弱学习器来进行学习

• Stacking

  构建多个不同类型的基学习器，并使用它们得到预测结果，然后基于这些预测结果，构建一个次级学习器，进而得到最终的预测结果

• Blending

• Pasting：通常用于大型数据集，因为可以减少基学习器之间的相关性（无放回取样）

结合策略

• 平均法：适用于连续型数值
  • 简单平均法
  • 加权平均法
• 投票法：适用于离散型数值
  • 硬投票法：少数服从多数
  • 软投票法：基于各基学习器分类置信度（预测的各类别概率），加权求和得到最终的预测结果
• 学习法：通过学习器对弱学习器的输出进行整合的集成算法

---

2 随机森林

from sklearn.ensemble import RandomForestClassifier

一种通过随机数据采样和随机特征选择的方式构建多个决策是，并利用投票法或平均法将预测结果结合的集成算法

算法评价

能够处理高维数据和大规模数据集，具有出色的鲁棒性

对数据存在少量缺失值的情况，随机森林在建立决策树时，能够基于其他特征进行分裂，从而无需对缺失值进行填充或删除

随机森林的可解释性较差，且由于需要保留大量决策树的信息，对内存的需求较高

---

3 自适应增强算法AdaBoost

from sklearn.ensemble import AdaBoostClassifier

自适应增强算法，通过迭代训练弱分类器，并加权调整错误样本的重要性，从而构建出一个强分类器

每个弱分类器的训练都依赖于前一轮中模型的性能，使得模型能够集中精力纠正先前错误

通过增加被错误分类样本的占比，使其在下一轮训练中更容易被采集到，进而使模型更关注这些分类错误的样本

算法步骤

1. 数据预处理。使用均值填充缺失值，并对数据进行适当的缩放和标准化
2. 给定一个训练样本集，并初始化样本的权值分布$w_i=\frac{1}{n},i=1,2,\cdots ,n$
3. 训练当前基学习器$G_m(x)$
4. 计算当前学习器在训练集的分类误差率$e_m={\sum }_{G_m(x_i)\ne y_i}{w}_{m,i}$（分类错误样本的权重之和）
5. 计算当前基学习器的权值${\alpha }_m=\frac{1}{2}\log \frac{1-e_m}{e_m}$
6. 将${\alpha }_m{G}_m(x)$增加到加法模型$f(x)$中
7. 更新样本权重$w_{m,i}=\{\begin{array}{cc}\frac{w_{m-1,i}}{Z_{m-1}}{e}^{-{\alpha }_{m-1}},& G_{m-1}(x_i)=y_i\\ \frac{w_{m-1,i}}{Z_{m-1}}{e}^{{\alpha }_{m-1}},& G_{m-1}(x_i)\ne y_i\end{array}$，其中规范化因子$Z_{m-1}$用于确保新的样本权重之和等于1

重复步骤3~7直到达到预设定的迭代次数或精度

算法评价

对噪声数据相对敏感，因为它在每一轮训练中都会聚焦于先前分类错误的样本。如果数据中存在噪声，可能导致模型过度关注噪声数据，从而影响整体性能

当数据集非常复杂或包含大量重叠类别时，可能导致AdaBoosting过拟合训练数据

为了避免过拟合，建议选择简单而稳定的基础分类器

---

4 梯度提升树GBDT

from skearn.ensemble import GradientBoostingClassifier

在迭代构建决策树的同时校正先前树的误差，具备捕捉数据集中复杂非线性关系的能力

算法原理

一种以CART回归树为基学习器的集成学习算法，其以梯度下降思想为基础，通过损失函数的负梯度方向来调整模型参数

CART回归树：

将输入空间划分为多个子区域，每个子区域的输出为该区域内所有训练样本的平均值

在划分过程中，通常使用RSS来度量每个节点的纯度，RSS 越小，则纯度越高。对于每一个划分，选择能够最大程度减少节点内部样本RSS的划分特征和划分点

GBDT每轮以当前预测为基准，通过拟合误差函数对预测值的残差进行调整

使用均方差函数作为损失函数
$$L(y,f(x))=\frac{1}{2}\sum _{i=1}^n{\left(y_i-f^{(m)}(x_i)\right)}^2$$

算法步骤

1. 初始化决策树模型$f(x)$

2. 计算每个样本的残差$r_{im}=\frac{\partial L\left(y_i,f^{(m)}(x_i)\right)}{\partial f^{(m)}(x_i)}$

3. 基于所计算的残差构架一颗新决策树

4. 将新学习器的输出$\eta h_m(x)$与模型的原始预测$f^{(m-1)}(x)$相加，获得更新后的模型

   $\eta$：学习率

   $h_m(x)$：
   $$h_m(x)=\arg \min \left\{\sum _{i=1}^N{r}_{im}^2\right\}$$
   更新后的模型：
   $$f^{(m)}(x)=f^{(m-1)}(x)+\eta h_m(x)$$

5. 重复步骤2~4，直到满足模型停止条件（树的深度限制、叶子节点最小样本数等）。最终的GDBT模型为训练过程中所有若学习器的输出和

算法评价

GBDT能处理复杂的非线性关系，并对异常值和噪声相对鲁棒，而且其在回归和分类任务中表现出色，具有良好的泛化能力和抗过拟合能力

GBDT在处理高维稀疏数据时可能效率较差，尤其在文本特征上表现相对较弱

---

5 极端梯度上升算法XGBoost

from xgboost import XGBClassifier

算法特色

在GDBT的基础上，独特之处在于支持并行计算、引入正则化项和列采样等特性

• 并行化处理：采用了Block存储结构，对特征进行分块并排序，每个块内保存了排序后的特征值以及对应样本的引用
• 正则化技术：包括L1和L2正则化
• 列采样：在每次迭代中对特征进行采样，防止模型过度依赖某些特定的特征

算法实现

与GDBT相比，目标函数由损失函数，变为
obj∗=−12∑j=1TGj2Hj+λ+γThm(x)=arg⁡min⁡{obj∗} obj^*=-\cfrac{1}{2}\sum_{j=1}^T{\cfrac{G_j^2}{H_j+\lambda}+\gamma T}\\ h_m(x)=\arg \min\{ obj^*\} obj∗=−21​j=1∑T​Hj​+λGj2​​+γThm​(x)=argmin{obj∗}
其中，
$$\begin{gathered} G_j=\sum _{i\in I_j}{g}_i=\sum _{i\in I_j}\frac{\partial L\left(y_i,F_{t-1}(x_i)\right)}{\partial F_{t-1}(x_i)} \\ {H}_j=\sum _{i\in I_j}{h}_i=\sum _{i\in I_j}\frac{{\partial }^{2}L\left(y_i,F_{t-1}(x_i)\right)}{{\partial }^2{F}_{t-1}(x_i)} \end{gathered}$$

算法评价

在处理大规模数据集时表现出色

在小样本数据集上容易过拟合

处理大规模数据时需要较大内存

---

6 轻量级梯度提升机LightGBM

from lightgbm import LGBMClassifier

提供快速、高效、低内存、高准确度、支持并行和大规模数据处理的工具

算法特色

LightGBM的提出旨在弥补传统梯度提升树算法在大规模和高维度数据集上效率不足的问题

传统梯度提升树算法，如GBDT和XGBoost算法在处理大规模和高维数据集时，加载整个训练数据至内存可能受限于内存容量的大小，而不加载至内存则会导致反复读写训练数据，造成巨大的时间开销

LightGBM引入了创新性的技术，包括互斥特征捆绑算法EFB、直方图算法HA、梯度单边采样算法GOSS，大幅降低生成单叶时的时间复杂度

• 互斥特征捆绑算法EFB：减少了特征的数量
• 直方图算法HA：减少了候选分裂点的数量
• 梯度单边采样算法GOSS：减少了样本的数量

LightGBM使用了带有深度限制的按叶生长Leaf-wise策略

模型通过计算每个叶节点的分箱增益，选择具有最大增益的叶节点进行分裂

分箱是将连续变量转换为分类变量的过程，目的是通过这种变换提高模型的稳定性和预测能力

互斥特征捆绑算法EFB

通过对高维稀疏的互斥特征进行捆绑操作，即将多个互斥特征捆绑为一个，以达到减少特征数量的目的

1. 判断哪些特征可以捆绑在一个Bundle中

   构建Bundle的步骤：

   1. 将特征作为节点，冲突次数$k$作为边的权值构建互斥关系图$G$，当两个特征不是互斥特征时，使用连边连接节点
   2. 对特征按度进行降序排序，度$K$为某一特征与其他特征的冲突次数和
   3. 按顺序对排好序的特征进行遍历，根据阈值判断当前特征$i$是否能加入已有的Bundle，若小于阈值$z$，则可以加入，若大于阈值$z$，则新建一个Bundle
   4. 最终得到特征捆绑结果$F$

2. 保留绑定前的特征，以保证在新的合并特征中识别到原本特征（可通过对原始特征的值添加偏移来实现）

直方图算法HA

1. 对每个特征维度$j$的取值进行排序

2. 将排序后的每个特征维度$j$中的样本根据给定的范围划分为$B$个箱，每个箱包含给定范围内的数据点

3. 计算每个箱内样本的梯度之和$G$和梯度平方之和$H$，用于后续分箱增益计算

   对于每个分箱$i$：
   $$\begin{gathered} G=\sum _{j\in bi{n}_i}{g}_j=\sum _{j\in bi{n}_i}\frac{\partial L\left(y_j,F(x_j)\right)}{\partial F(x_j)} \\ H=\sum _{j\in bi{n}_i}{g}_j=\sum _{j\in bi{n}_i}\frac{{\partial }^{2}L\left(y_j,F(x_j)\right)}{{\partial }^{2}F(x_j)} \end{gathered}$$

4. 对于每个特征维度$j$，把每个箱作为分裂点，计算分箱增益$\Delta loss$以选择最佳分裂点

   对于每个分箱$i$：
   $$GradSu{m}_i=\sum _{j\in bi{n}_i}{g}_j+\frac{1}{2}\sum _{j\in bi{n}_i}{h}_j$$
   则分箱增益$\Delta loss$：
   $$\Delta loss=\frac{GradSu{m}_L^2}{n_L}+\frac{GradSu{m}_R^2}{n_R}-\frac{GradSu{m}_P^2}{n_P}$$
   其中，$GradSu{m}_L$为分割点左侧分箱至当前分割点的梯度总和，$GradSu{m}_R$为分割点右侧分箱的梯度总和，$GradSu{m}_P$为父节点的梯度总和，$n_L$、$n_R$、$n_P$分别为对应的样本数量

5. 根据最佳分裂点将树进行扩展，并更新叶节点的预测值

梯度单边采样算法GOSS

较大的梯度意味着模型在样本上的预测错误较大，而小梯度表示样本已经取得了较好的训练效果，其对模型学习的影响较小

GOSS在进行数据采样时，保留梯度较大的数据，在梯度较小的数据中随机采样并加权处理

1. 计算每个样本的梯度值，并排序得到排序后的训练集$\bar{D}$
2. 选择前$a\times |\bar{D}|$个样本作为大梯度数据集，记作${\bar{D}}_{big}$
3. 对剩余的$|\bar{D}|-a\times |\bar{D}|$样本进行$b$随机采样，选取$b\times (|\bar{D}|-a\times |\bar{D}|)$个样本作为小梯度数据集，记作${\bar{D}}_{small}$
4. 合并${\bar{D}}_{big}$和${\bar{D}}_{small}$，赋予权重$w_i=\frac{1-a}{b}$给小梯度数据集中的每个样本
5. 将采样样本数据输入新的弱学习器训练
6. 重复直至达到给定的迭代次数