18. 机器学习——集成学习 试读

机器学习面试题汇总与解析——集成学习

本章讲解知识点

• 1. 什么是集成学习
• 2. AdaBoost
• 3. 梯度提升树(Gradient Boosting Decision Tree, GBDT)
• 4. 随机森林(Random Forest，简称RF)
• 5. XGBoost
• 6. LightGBM

• 本专栏适合于Python已经入门的学生或人士，有一定的编程基础。

• 本专栏适合于算法工程师、机器学习、图像处理求职的学生或人士。

• 本专栏针对面试题答案进行了优化，尽量做到好记、言简意赅。这才是一份面试题总结的正确打开方式。这样才方便背诵

• 如专栏内容有错漏，欢迎在评论区指出或私聊我更改，一起学习，共同进步。

• 相信大家都有着高尚的灵魂，请尊重我的知识产权，未经允许严禁各类机构和个人转载、传阅本专栏的内容。

  
  

• 关于机器学习算法书籍，我强烈推荐一本《百面机器学习算法工程师带你面试》，这个就很类似面经，还有讲解，写得比较好。

• 关于深度学习算法书籍，我强烈推荐一本《解析神经网络——深度学习实践手册》，简称 CNN book，通俗易懂。

• B站机器学习视频：https://space.bilibili.com/10781175/channel/detail?cid=133301

1. 什么是集成学习

1.1 基本概念

集成学习（Ensemble Learning）是一种机器学习方法，通过将多个基本模型（弱分类器或弱回归器）组合在一起，以达到更好的预测性能。它的基本思想是通过结合多个模型的预测结果，从而降低单个模型的误差，并提高整体的泛化能力。

集成学习通常包括两个主要步骤：生成基本模型和集成基本模型。在生成基本模型的过程中，可以使用不同的算法和模型来训练一组基本模型，每个基本模型对数据集进行预测。在集成基本模型的过程中，可以采用不同的策略来结合基本模型的预测结果，从而得到最终的集成预测结果。集成中只包含同种类型的个体学习器，称为同质，当中的个体学习器亦称为“基学习器”，相应的算法称为“基学习算法”。集成中包含不同类型的个体学习器，称为“异质”，当中的个体学习器称为“组建学习器”。

集成学习有多种方法，其中最常见的方法包括投票法（Voting）、平均法（Averaging）、堆叠法（Stacking）和提升法（Boosting）等。这些方法根据不同的原理和策略，通过组合基本模型的预测结果来进行集成。

集成学习具有以下优点：

• 提高预测性能：集成多个模型可以降低单个模型的偏差和方差，从而提高整体的预测性能。
• 增强模型的鲁棒性：集成学习可以通过多个模型的共同决策，减少单个模型的错误，从而提高模型的鲁棒性。
• 提供多样性和泛化能力：不同的基本模型可以从不同的角度对数据进行学习，提供更多的多样性，从而提高模型的泛化能力。

根据个体学习器的生成方式，目前的集成学习方法大致可以分为两类：

• 个体学习器间存在强依赖关系、必须串行生成的序列化方法，代表为 Boosting；
• 个体学习器间不存在强依赖关系、可同时生成的并行化方法，代表为 Bagging 和随机森林。

注：所谓串行生成的序列化方法就是除了训练第一个之外，其他的学习器学习都需要依赖于前面生成的学习的结果。

1.2 Bootstrap（自助法）

Bootstrap 是一种用于数据采样的技术，用于生成多个训练集。它基于有放回地从原始训练数据集中抽取样本，构成一个新的训练集。通过对原始数据集的多次重采样，可以生成多个不同的训练集，每个训练集都是原始数据集的一部分。具体地：Bootstrap 是一种抽样方法，即随机抽取数据并将其放回。如一次抽取一个样本，然后放回样本集中，下次可能再抽取这个样本。接着将每轮未抽取的数据合并形成袋外数据集（Out of Bag, OOB），用于模型中的测试集。

Bootstrap 是现代统计学较为流行的一种统计方法，在小样本时效果很好，就是为了重采样，要是数据本身就够，还费那事干嘛。机器学习中的 Bagging，AdaBoost 等方法其实都蕴含了 Boostrap 的思想。

从数学角度来说，Bootstrap 是一种在统计中通过样本估计总体的方法。子样本之于样本，可以类比样本之于总体。我们以前高中就学过统计，有一个例子：

农场主要统计鱼塘里面的鱼的条数，怎么统计呢？假设鱼塘总共有鱼 1000 条，但是农场主是不知道里面有多少。肯定不能鱼塘水抽干了一条一条数。那么课本给我们的解决方案是什么呢？

步骤：

1. 承包鱼塘，不让别人捞鱼（规定总体分布不变）。
2. 农场主捞鱼，捞 100 条，都打上标签（构造样本）。
3. 把鱼放回鱼塘，休息一晚（使之混入整个鱼群，确保之后抽样随机）
4. 开始捞鱼，每次捞 100 条，数一下，自己昨天标记的鱼有多少条，占比多少（一次重采样取分布）。
5. 重复 3，4 步骤 n 次。建立分布。

原理是中心极限定理：中心极限定理是概率论中的一个重要定理，它说明在一定条件下，大量独立随机变量的和会趋近于高斯分布（正态分布）。这意味着当我们从总体中取出多个独立样本，并计算每个样本的均值时，这些样本均值的分布将趋于高斯分布。

假设一下，第一次重新捕鱼 100 条，发现里面有标记的鱼 12 条，记下 12%，放回去，再捕鱼 100 条，发现标记的为 9 条，记下 9%，重复重复好多次之后，农场主发现，每次捕鱼平均在 10 条左右有标记，所以，农场主可以大致推测出鱼塘有 1000 条左右。其实是一个很简单的类似于一个比例问题。这就是为什么可以用 Bootstrap 来建立袋外数据集，从数学上能做出解释，这可不是拍拍脑袋凭直觉办事。

这也就解释了，为什么在小样本的时候，bootstrap 效果较好，比如这样想，如果我想统计大海里有多少鱼，标记 100000 条也没用，因为实际数量太过庞大，取的样本相比于太过渺小，最实际的就是，下次再捕100000的时候，发现一条都没有标记，就等于标记的意义了。

1.3 Boosting（提升法）

Boosting 是一种集成学习方法，通过组合多个弱学习器（weak learner）来构建一个强学习器（strong learner）。它通过反复迭代训练一系列弱学习器，并根据前一轮学习器的结果调整样本的权重，使得下一轮学习器能够更关注被前一轮学习器错误分类的样本，从而逐步提高整体的分类性能。

Boosting 的基本原理是将弱学习器组合成一个强学习器的过程。在每一轮迭代中，Boosting 算法根据当前样本的权重分布训练一个弱学习器，并根据该学习器的分类准确度调整样本的权重。具体来说，被错误分类的样本会被赋予更高的权重，以便在下一轮迭代中更多地关注这些样本。这样，通过多次迭代，每个弱学习器都会对前一轮学习器的错误进行修正，最终组合成一个具有较高分类准确度的强学习器。

Boosting 算法中的一个重要概念是"加权多数表决"，即每个弱学习器的预测结果会根据其分类准确度进行加权，最终根据加权结果进行整体的分类决策。

常见的 Boosting 算法包括 AdaBoost（Adaptive Boosting）、Gradient Boosting 和 XGBoost（eXtreme Gradient Boosting）等。这些算法在每一轮迭代中采用不同的策略来训练弱学习器和调整样本权重，从而不断提高整体的分类性能。

Boosting 算法的优点包括能够有效处理复杂的分类问题，具有较高的准确度和鲁棒性，对于噪声和异常值具有一定的容忍度。

1.4 Bagging（袋装法）

Bagging（Bootstrap Aggregating）是一种集成学习方法，通过组合多个独立的弱学习器（weak learner）来构建一个强学习器（strong learner）。它通过对原始训练集进行有放回抽样（bootstrap sampling），生成多个训练子集，并分别使用这些子集来训练不同的弱学习器。最终，通过对弱学习器的预测结果进行投票或取平均等方式来进行整体的决策。

Bagging 的基本原理是通过并行训练多个弱学习器，使它们在不同的训练子集上学习，从而降低了模型的方差。每个弱学习器都是独立地学习，它们之间没有依赖关系，可以同时进行训练。在预测阶段，Bagging 算法会将每个弱学习器的预测结果进行集成，如投票、平均等，得到最终的预测结果。Bagging 通过 bootstrap sampling 采样方式，每个训练子集都有一定的重叠和差异，从而使得弱学习器能够学习到数据的不同特征和变化模式，增强了模型的多样性。

常见的 Bagging 算法包括随机森林（Random Forest），它是一种基于决策树的集成学习方法。随机森林使用 Bagging 的思想，在每个弱学习器的训练过程中，除了对训练样本进行有放回抽样，还会对特征进行随机选择，从而增加模型的多样性和泛化能力。

Bagging 算法的优点包括能够降低模型的方差，提高模型的鲁棒性和泛化能力，对噪声和过拟合具有一定的容忍度。此外，Bagging 算法的训练和预测过程可以并行化处理，适用于大规模数据集和高维特征。

Bagging 的优点：

• 训练一个 Bagging 集成与直接使用基分类器算法训练一个学习器的复杂度同阶，说明 Bagging 是一个高效的集成学习算法。
• 此外，与标准的 AdaBoost 算法只适用于二分类问题不同，Bagging 能不经过修改用于多分类、回归等任务。
• 由于每个基学习器只使用 63.2% 的数据，所以剩下 36.8% 的数据可以用来做验证集来对泛化性能进行“包外估计”。

从偏差-方差的角度来说，Boosting 主要关注减小偏差，而Bagging 主要关注降低方差，也就说明 Boosting 在弱学习器上表现更好，而降低方差可以减小过拟合的风险，所以 Bagging 通常在强分类和复杂模型上表现得很好。举个例子：Bagging 在不减枝决策树、神经网络等易受样本扰动的学习器上效果更为明显。

1.5 Stacking（集成法）

Stacking（堆叠）是一种集成学习方法，它通过将多个基学习器的预测结果作为输入，再使用一个元学习器来对这些预测结果进行整合和组合，从而得到最终的预测结果。

Stacking 的主要思想为：先从初始数据集训练出初级学习器，然后“生成”一个新的数据集用于训练次级学习器。生成的该新数据中，初级学习器的输出被当做样例输入特征，而初始样本的标记仍被当做样例标记（Ground Truth）。也就是说，假设初级学习器有 $MM$ 个，那么对于一个原始数据集中的样本 $(x,y)(x,\; y)$，通过这 $MM$ 个初级学习器有 $MM$ 个输出 $h_1(x),h_2(x),\mathrm{.}\mathrm{.}\mathrm{.},h_M(x)\{h\_1(x),h\_2(x),...,h\_M(x)\}$，把 $h_1(x),h_2(x),\mathrm{.}\mathrm{.}\mathrm{.},h_M(x);y\{h\_1(x),h\_2(x),...,h\_M(x);\; y\}$ 作为新数据的一个样本，所以一个初级学习器的输出作为新数据集中对应样本的一个特征，将原始训练集的真实标签作为目标值。

Stacking 的算法流程如下：

• 准备数据集：将原始数据集分成训练集和测试集。

• 构建第一层的基学习器：使用训练集对多个不同的基学习器进行训练，得到它们在训练集上的预测结果。 假设我们有 K 个基学习器，分别记为 $h_1,h_2,\mathrm{.}\mathrm{.}\mathrm{.},h_{K}h\_1,\; h\_2,\; ...,\; h\_K$，则对于训练集中的第 $ii$ 个样本 $x_{i}x\_i$，基学习器 $h_{k}h\_k$ 的预测结果为 $y_{ik}=h_k(x_i)y\_\{ik\}\; =\; h\_k(x\_i)$。

• 构建元学习器的训练集：将基学习器在训练集上的预测结果作为特征，将原始训练集的真实标签作为目标值，构建一个新的训练集。 对于训练集中的第 $ii$ 个样本 $x_{i}x\_i$，将基学习器的预测结果 $y_{i1},y_{i2},\mathrm{.}\mathrm{.}\mathrm{.},y_{iK}y\_\{i1\},\; y\_\{i2\},\; ...,\; y\_\{iK\}$ 作为特征向量，将其对应的真实标签 $y_{i}y\_i$ 作为目标值。得到元学习器的训练集为 $D^{\mathrm{\prime }}=(y_{i1},y_{i2},\mathrm{.}\mathrm{.}\mathrm{.},y_{iK}),y_{i}D\text{'}\; =\; \{(y\_\{i1\},\; y\_\{i2\},\; ...,\; y\_\{iK\}),\; y\_i\}$。

• 训练元学习器：使用新的训练集 $D^{\mathrm{\prime }}D\text{'}$ 来训练一个元学习器，例如逻辑回归、支持向量机等。 元学习器通过学习基学习器的预测结果和真实标签之间的关系，来进行模型的整合和组合。假设元学习器的预测函数为 $f(x)f(x)$，则元学习器的训练过程可以表示为 $f(x)=g(y_{i1},y_{i2},\mathrm{.}\mathrm{.}\mathrm{.},y_{iK})f(x)\; =\; g(y\_\{i1\},\; y\_\{i2\},\; ...,\; y\_\{iK\})$。

• 预测过程：对于测试集中的样本，先使用已训练好的基学习器对其进行预测，然后将预测结果作为输入，经过元学习器进行整合和组合，得到最终的预测结果。 对于测试集中的第 $jj$ 个样本 $x_{j}x\_j$，基学习器的预测结果为 $y_{1j},y_{2j},\mathrm{.}\mathrm{.}\mathrm{.},y_{Kj}y\_\{1j\},\; y\_\{2j\},\; ...,\; y\_\{Kj\}$，则通过元学习器进行预测得到最终结果 ${\widehat{y}}_j=f(x_j)=g(y_{1j},y_{2j},\mathrm{.}\mathrm{.}\mathrm{.},y_{Kj})\backslash hat\{y\}\_j\; =\; f(x\_j)\; =\; g(y\_\{1j\},\; y\_\{2j\},\; ...,\; y\_\{Kj\})$。

Stacking的优点包括：

• 结合多个基学习器的优点：Stacking 能够结合多个基学习器的预测结果，充分发挥它们各自的优势，从而提高整体模型的性能。

• 能够处理复杂的问题：由于 Stacking 使用多层的学习结构，能够处理复杂的问题，包括特征之间的高阶交互等。

• 可以适应不同类型的基学习器：Stacking 并不限定基学习器的类型，可以使用各种不同的学习算法作为基学习器，提供了更大的灵活性。

Stacking的缺点包括：

• 训练时间较长：由于 Stacking 涉及多层学习过程，训练时间相对较长。

• 对数据的依赖性较高：Stacking 的性能高度依赖于基学习器的性能和预测结果的质量，如果基学习器的性能较差或预测结果存在噪声，可能会影响整体模型的性能。

2. AdaBoost

2.1 基本概念

AdaBoost 是 Boosting 中的经典算法，其主要应用于二分类问题。

Adaboost 算法采用调整样本权重的方式来对样本分布进行调整，即提高前一轮个体学习器错误分类的样本的权重，而降低那些正确分类的样本的权重，这样就能使得错误分类的样本可以受到更多的关注，从而在下一轮中可以正确分类，使得分类问题被一系列的弱分类器“分而治之”。对于组合方式，AdaBoost 采用加权多数表决的方法，具体地，加大分类误差率小的弱分类器的权值，减小分类误差率大的弱分类器的权值，从而调整他们在表决中的作用。

AdaBoost 算法流程如下：

输入：训练集 $D=(x_1,y_1),(x_2,y_2),\mathrm{.}\mathrm{.}\mathrm{.},(x_n,y_n)D\; =\; \{\; (x\_1,\; y\_1),\; (x\_2,\; y\_2),\; ...,\; (x\_n,\; y\_n)\; \}$，其中 $x_{i}x\_i$ 为样本的特征向量，$y_{i}y\_i$ 为样本的类别标签，$i=1,2,\mathrm{.}\mathrm{.}\mathrm{.},Ni\; =\; 1,\; 2,\; ...,\; N$。

输出：强分类器 $H(x)H(x)$。

1.初始化样本权重：

$w_i^{(1)}=\frac{1}{N},i=1,2,\mathrm{.}\mathrm{.}\mathrm{.},Nw\_i^\{(1)\}=\backslash frac\{1\}\{N\},\; \backslash quad\; i\; =\; 1,\; 2,\; ...,\; N$

2.对于每一轮 $t=1,2,\mathrm{.}\mathrm{.}\mathrm{.},Tt=1,\; 2,\; ...,\; T$，执行以下步骤：

• 训练一个弱分类器： 使用当前样本权重训练一个弱分类器，得到分类器 $G_t(x)G\_t(x)$。

• 计算弱分类器的权重： 计算弱分类器 $G_t(x)G\_t(x)$ 的权重 ${\alpha }_t\backslash alpha\_t$，表示其在最终模型中的重要性，计算公式如下： ${\alpha }_t=\frac{1}{2}\ln (\frac{1-er{r}_t}{er{r}_t})\backslash alpha\_t=\backslash frac\{1\}\{2\}\; \backslash ln(\backslash frac\{1-err\_t\}\{err\_t\})$ 其中，${\text{err}}_t\backslash text\{err\}\_t$ 为弱分类器 $G_t(x)G\_t(x)$ 在训练集上的加权误差率，计算公式如下： $er{r}_t={\sum }_{i=1}^N{w}_i^{(t)}\cdot \mathbb{I}(y_i\mathrm{\ne }{G}_t(x_i))err\_t=\backslash sum\_\{i=1\}^N\; w\_i^\{(t)\}\; \backslash cdot\; \backslash mathbb\{I\}(y\_i\; \backslash neq\; G\_t(x\_i))$ 其中，$\mathbb{I}(\cdot )\backslash mathbb\{I\}(\backslash cdot)$ 为指示函数，当括号内条件为真时取值为 1，否则为 0。

• 更新样本权重： 更新样本的权重 $w_i^{(t+1)}w\_i^\{(t+1)\}$，使得被错误分类的样本权重增加，被正确分类的样本权重减小，计算公式如下： $w_i^{(t+1)}=\frac{w_i^{(t)}\cdot \exp (-{\alpha }_t\cdot y_i\cdot G_t(x_i))}{Z_t}w\_i^\{(t+1)\}=\backslash frac\{w\_i^\{(t)\}\; \backslash cdot\; \backslash exp(-\backslash alpha\_t\; \backslash cdot\; y\_i\; \backslash cdot\; G\_t(x\_i))\}\{Z\_t\}$ 其中，$Z_{t}Z\_t$ 为规范化因子，用于保证样本权重的总和为 1，计算公式如下： $Z_t={\sum }_{i=1}^N{w}_i^{(t)}\cdot \exp (-{\alpha }_t\cdot y_i\cdot G_t(x_i))Z\_t=\backslash sum\_\{i=1\}^N\; w\_i^\{(t)\}\; \backslash cdot\; \backslash exp(-\backslash alpha\_t\; \backslash cdot\; y\_i\; \backslash cdot\; G\_t(x\_i))$

3.构建强分类器：

将所有弱分类器按照权重 ${\alpha }_t\backslash alpha\_t$ 进行加权组合，得到最终的强分类器 $H(x)H(x)$，计算公式如下：

$H(x)=sign({\sum }_{t=1}^T{\alpha }_t\cdot G_t(x))H(x)=sign(\backslash sum\_\{t=1\}^T\; \backslash alpha\_t\; \backslash cdot\; G\_t(x))$

最终，得到的强分类器 $H(x)H(x)$ 可以用于对新样本进行预测。

2.2 AdaBoost 实例

让我们通过一个简单的示例来计算 AdaBoost 权重和预测。

给定如表所示训练数据，假设弱分类器由 或 $x>vx>v$ 产生，其阈值 $vv$ 使该分类器在训练数据集上分类误差率最低。试用 AdaBoost 算法学习一个强分类器。

Sample 1: $(x_1,y_1)=(0,1)(x\_1,\; y\_1)\; =\; (0,\; 1)$

Sample 2: $(x_2,y_2)=(1,1)(x\_2,\; y\_2)\; =\; (1,\; 1)$

Sample 3: $(x_3,y_3)=(2,1)(x\_3,\; y\_3)\; =\; (2,\; 1)$

Sample 4: $(x_4,y_4)=(3,-1)(x\_4,\; y\_4)\; =\; (3,\; -1)$

Sample 5: $(x_5,y_5)=(4,-1)(x\_5,\; y\_5)\; =\; (4,\; -1)$

Sample 6: $(x_6,y_6)=(5,-1)(x\_6,\; y\_6)\; =\; (5,\; -1)$

Sample 7: $(x_7,y_7)=(6,1)(x\_7,\; y\_7)\; =\; (6,\; 1)$

Sample 8: $(x_8,y_8)=(7,1)(x\_8,\; y\_8)\; =\; (7,\; 1)$

Sample 9: $(x_9,y_9)=(8,1)(x\_9,\; y\_9)\; =\; (8,\; 1)$

Sample 10: $(x_{10},y_{10})=(9,-1)(x\_\{10\},\; y\_\{10\})\; =\; (9,\; -1)$

第一步：初始化数据权值分布：

第二步：执行第一轮 AdaBoost：

a.训练弱分类器：

弱分类器 $G_1(x)G\_1(x)$ 是基于特征 $xx$ 的决策树，在权值分布为 $D_{1}D\_1$ 的训练数据上，阈值 $vv$ 为 2.5 时分类误差率最低。分类器对 $x\le 2.5x\; \le \; 2.5$ 的样本预测 1，对 $x>2.5x\; >\; 2.5$ 的样本预测 -1。故基本分类器为：

b.计算弱分类器 $G_1(x)G\_1(x)$ 在训练数据集上的误差率：$er{r}_1=P\cdot \mathbb{I}(y_i\mathrm{\ne }{G}_1(x_i))=0.3err\_1\; =\; P\; \backslash cdot\; \backslash mathbb\{I\}(y\_i\; \ne \; G\_1(x\_i))=0.3$

c.计算弱分类器 $G_1(x)G\_1(x)$ 的权重 ${\alpha }_1=\frac{1}{2}\log \frac{1-er{r}_1}{er{r}_1}=0.4236\alpha \_1=\backslash frac\{1\}\{2\}\; \backslash log\; \backslash frac\{1-err\_1\}\{err\_1\}=0.4236$：

d.更新样本权重：使用以下公式更新样本的权值分布：

$D_2=(w_{21},w_{22},\mathrm{.}\mathrm{.}\mathrm{.},w_{210})w_{2i}=\frac{w_{1i}}{Z_1}\exp (-{\alpha }_1{y}_i{G}_1(x_i)),i=1,2,\mathrm{.}\mathrm{.}\mathrm{.},10D_2=(0.0715,0.0715,0.0715,0.0715,0.0715,0.0715,0.1666,0.1666,0.1666,0.0715)f_1(x)=0.4236G_1(x)D\_2=(w\_\{21\},w\_\{22\},...,w\_\{210\})\; \backslash \backslash \; w\_\{2i\}=\backslash frac\{w\_\{1i\}\}\{Z\_1\}\; \backslash exp(-\backslash alpha\_1\; y\_i\; G\_1(x\_i)),\; \backslash quad\; i=1,2,...,10\; \backslash \backslash \; D\_2=(0.0715,0.0715,0.0715,0.0715,0.0715,0.0715,0.1666,0.1666,0.1666,0.0715)\; \backslash \backslash \; f\_1(x)=0.4236G\_1(x)$

这里，$Z_{1}Z\_1$ 是归一化因子，计算为所有更新权重的总和。分类器 $sign[f_1(x)]sign[f\_1(x)]$ 在训练数据集上有 3 个误分类点。

第三步：进行第二轮 AdaBoost：

a.训练弱分类器：

弱分类器 $G_2(x)G\_2(x)$ 是基于特征 $xx$ 的决策树，在权值分布为 $D_{2}D\_2$ 的训练数据上，阈值 $vv$ 为 8.5 时分类误差率最低。分类器对 $x\le 8.5x\; \le \; 8.5$ 的样本预测 1，对 $x>8.5x\; >\; 8.5$ 的样本预测 -1。故基本分类器为：

b.计算弱分类器 $G_2(x)G\_2(x)$ 在训练数据集上的误差率：$er{r}_2=P\cdot \mathbb{I}(y_i\mathrm{\ne }{G}_2(x_i))=0.2143err\_2\; =\; P\; \backslash cdot\; \backslash mathbb\{I\}(y\_i\; \ne \; G\_2(x\_i))=0.2143$

c.计算弱分类器 $G_2(x)G\_2(x)$ 的权重 ${\alpha }_2=\frac{1}{2}\log \frac{1-er{r}_2}{er{r}_2}=0.6496\alpha \_2=\backslash frac\{1\}\{2\}\; \backslash log\; \backslash frac\{1-err\_2\}\{err\_2\}=0.6496$：

d.更新样本权重：使用以下公式更新样本的权值分布：

$D_3=(0.0455,0.0455,0.0455,0.1667,0.1667,0.1667,0.1060,0.1060,0.1060,0.0455)f_2(x)=0.4236G_1(x)+0.6496G_2(x)D\_3=(0.0455,0.0455,0.0455,0.1667,0.1667,0.1667,0.1060,0.1060,0.1060,0.0455)\; \backslash \backslash \; f\_2(x)=0.4236G\_1(x)+0.6496G\_2(x)$

这里，$Z_{1}Z\_1$ 是归一化因子，计算为所有更新权重的总和。分类器 $sign[f_2(x)]sign[f\_2(x)]$ 在训练数据集上有 3 个误分类点。

第四步：进行第三轮 AdaBoost：

a.训练弱分类器：

弱分类器 $G_3(x)G\_3(x)$ 是基于特征 $xx$ 的决策树，在权值分布为 $D_{3}D\_3$ 的训练数据上，阈值 $vv$ 为 5.5 时分类误差率最低。分类器对 $x\le 5.5x\; \le \; 5.5$ 的样本预测 -1，对 $x>5.5x\; >\; 5.5$ 的样本预测 1。故基本分类器为：

b.计算弱分类器 $G_3(x)G\_3(x)$ 在训练数据集上的误差率：$er{r}_3=P\cdot \mathbb{I}(y_i\mathrm{\ne }{G}_3(x_i))=0.1820err\_3\; =\; P\; \backslash cdot\; \backslash mathbb\{I\}(y\_i\; \ne \; G\_3(x\_i))=0.1820$

c.计算弱分类器 $G_3(x)G\_3(x)$ 的权重 ${\alpha }_3=\frac{1}{2}\log \frac{1-er{r}_3}{er{r}_3}=0.7514\alpha \_3=\backslash frac\{1\}\{2\}\; \backslash log\; \backslash frac\{1-err\_3\}\{err\_3\}=0.7514$：

d.更新样本权重：使用以下公式更新样本的权值分布：

$D_4=(0.125,0.125,0.125,0.102,0.102,0.102,0.065,0.065,0.065,0.125)f_3(x)=0.4236G_1(x)+0.6496G_2(x)+0.7514G_3(x)D\_4=(0.125,0.125,0.125,0.102,0.102,0.102,0.065,0.065,0.065,0.125)\; \backslash \backslash \; f\_3(x)=0.4236G\_1(x)+0.6496G\_2(x)+0.7514G\_3(x)$

这里，$Z_{1}Z\_1$ 是归一化因子，计算为所有更新权重的总和。分类器 $sign[f_3(x)]sign[f\_3(x)]$ 在训练数据集上有 0 个误分类点。

于是最终分类器为：

$H(x)=sign[f_3(x)]=sign[0.4236G_1(x)+0.6496G_2(x)+0.7514G_3(x)]H(x)\; =\; sign[f\_3(x)]=sign[0.4236G\_1(x)+0.6496G\_2(x)+0.7514G\_3(x)]$

2.3 AdaBoost 优缺点

AdaBoost算法是模型为加法模型、损失函数为指数函数、学习算法为前向分步算法时的二分类算法。

优点：

• 高精度：AdaBoost 在处理复杂的分类问题时具有较高的准确性，它能够通过组合多个弱分类器来构建一个强分类器，提高整体的分类性能。
• 自适应调整：AdaBoost 在每一轮迭代中都会调整样本的权重，更加关注前一轮分类错误的样本，使得模型能够逐步适应困难样本，提高分类效果。
• 不易过拟合：AdaBoost 在迭代过程中通过加权组合多个分类器，可以有效减少过拟合的风险，提高模型的泛化能力。
• 简单易实现：AdaBoost 的基本原理简单，易于理解和实现。

缺点：

• 对异常值敏感：AdaBoost 对异常值敏感，异常值可能会对模型产生较大的影响，导致模型性能下降。
• 计算复杂度高：AdaBoost 的训练过程需要多次迭代，每一轮迭代都需要训练一个新的分类器，因此计算复杂度较高，训练时间较长。
• 数据不平衡问题：当训练数据中存在严重的类别不平衡问题时，AdaBoost 的效果可能会受到影响，可能会倾向于对占比较大的类别进行更好的分类，而忽略较小类别的分类效果。

3. 梯度提升树(Gradient Boosting Decision Tree, GBDT)

3.1 基本概念

GBDT（Gradient Boosting Decision Tree）是一种集成学习算法，它是由多个决策树组成的集成模型。它通过迭代训练一系列的决策树来逐步提升整体模型的性能。

GBDT 的工作原理如下：

• 初始化模型：首先，将整个训练集作为初始模型进行训练，通常使用一个简单的模型作为初始模型，例如单个决策树。
• 迭代训练：在每一轮迭代中，根据上一轮的模型预测结果与真实标签之间的差异（残差），训练一个新的决策树来拟合残差。
• 更新模型：将新的决策树添加到模型中，并更新整体模型的预测结果。
• 终止条件：重复迭代训练过程，直到达到预定的迭代次数或满足终止条件。

在训练过程中，GBDT 使用梯度下降的思想来逐步优化模型。每一轮迭代都通过调整残差的权重来更新模型，使得每一轮的模型都能够更好地拟合训练数据的残差部分。最终，将所有决策树的预测结果相加得到最终的集成模型。

3.2 公式推导

1.初始化：

• 初始化样本权重：$w_i=\frac{1}{N}w\_i\; =\; \backslash frac\{1\}\{N\}$，其中 $NN$ 是样本总数。
• 初始化模型 $F_0(x)=0F\_0(x)\; =\; 0$。

2.迭代训练：

对于每一轮 $m=1,2,\mathrm{.}\mathrm{.}\mathrm{.},Mm\; =\; 1,\; 2,\; ...,\; M$，进行以下步骤：

• 根据样本权重 $w_{i}w\_i$ 拟合一个决策树模型：$h_m(x)h\_m(x)$。
• 计算当前模型的预测结果：$F_m(x)=F_{m-1}(x)+\eta \cdot h_m(x)F\_m(x)\; =\; F\_\{m-1\}(x)\; +\; \backslash eta\; \backslash cdot\; h\_m(x)$，其中 $\eta \backslash eta$ 是学习率，控制每一棵树的贡献程度。
• 计算当前模型的残差：$r_{im}=y_i-F_m(x_i)r\_\{im\}\; =\; y\_i\; -\; F\_m(x\_i)$，其中 $y_{i}y\_i$ 是样本 $x_{i}x\_i$ 的真实标签。
• 更新样本权重：
  • 计算样本权重的指数损失函数梯度：$g_{im}=\frac{\mathrm{\partial }L(y_i,F_m(x_i))}{\mathrm{\partial }{F}_m(x_i)}g\_\{im\}\; =\; \backslash frac\{\backslash partial\; L(y\_i,\; F\_m(x\_i))\}\{\backslash partial\; F\_m(x\_i)\}$，其中 $LL$ 是损失函数。
  • 更新样本权重：$w_i=w_i\cdot \exp (-g_{im})w\_i\; =\; w\_i\; \backslash cdot\; \backslash exp(-g\_\{im\})$。
• 归一化样本权重：$w_i=\frac{w_i}{{\sum }_{i=1}^N{w}_i}w\_i\; =\; \backslash frac\{w\_i\}\{\backslash sum\_\{i=1\}^\{N\}\; w\_i\}$。

每一轮迭代重复以上步骤。

3.组合最终模型：

• 最终模型的预测结果：$F(x)=F_M(x)={\sum }_{m=1}^M\eta \cdot h_m(x)F(x)\; =\; F\_M(x)\; =\; \backslash sum\_\{m=1\}^\{M\}\; \backslash eta\; \backslash cdot\; h\_m(x)$。

其中，$MM$ 是迭代轮数，$h_m(x)h\_m(x)$ 是第 $mm$ 轮迭代中拟合的决策树模型，$F_m(x)F\_m(x)$ 是第 $mm$ 轮迭代的模型预测结果，$r_{im}r\_\{im\}$ 是第 $ii$ 个样本在第 $mm$ 轮迭代中的残差，$g_{im}g\_\{im\}$ 是样本权重的指数损失函数梯度，$LL$ 是损失函数，$F(x)F(x)$ 是最终组合的模型预测结果。

3.3 GBDT 优缺点

优点：

• 高预测准确率：GBDT 在处理各种任务时表现出色，包括分类和回归。它能够通过多轮迭代不断优化模型，提高预测准确率。

• 处理复杂特征交互：GBDT 可以自动捕捉特征之间的复杂交互关系，无需人为进行特征工程。

• 鲁棒性：GBDT 对于噪声和异常值相对较为鲁棒，它通过多棵决策树的组合减少了单棵树的过拟合风险。

• 可解释性：GBDT 能够提供特征的重要性排序，帮助理解模型对于预测的贡献程度。

缺点：

• 训练时间较长：GBDT 的训练过程是顺序迭代的，每轮迭代需要构建一个新的决策树。因此，相对于一些快速训练的模型，如线性模型或浅层神经网络，GBDT 的训练时间较长。

• 参数调节难度较高：GBDT 中有多个参数需要调节，如树的数量、树的深度、学习率等。不恰当的参数选择可能导致模型性能下降。

• 需要大量内存：由于 GBDT 是一种集成模型，它需要存储多棵决策树的结构和参数信息，因此占用较大的内存空间。

4. 随机森林(Random Forest，简称RF)

4.1 基本概念

随机森林（Random Forest）是一种集成学习方法，通过组合多个决策树来进行分类或回归任务。以下是随机森林的基本流程：

1.数据准备：

• 假设有包含 $NN$ 个样本的训练集，每个样本包含 $MM$ 个特征。
• 根据任务类型，确定目标变量（分类或回归）。

2.随机森林的构建：

• 设定森林中决策树的数量 $TT$。

• 对于每棵决策树 $t=1,2,\mathrm{.}\mathrm{.}\mathrm{.},Tt\; =\; 1,\; 2,\; ...,\; T$：

  • 从原始训练集中进行有放回抽样（Bootstrap），得到一个随机抽样的训练集，大小与原始训练集相同。
  • 根据抽样的训练集构建一棵决策树，可以使用特定的算法（如 ID3、C4.5、CART 等）。
  • 决策树的构建过程中，每个节点的特征选择时，随机从所有特征中选取一部分特征进行评估，一般是 $kk$ 个特征（$k\ll Mk\; \backslash ll\; M$）。

• 重复上述步骤，构建出 $TT$ 棵决策树。

3.随机森林的预测：

• 对于新的输入样本：
  • 将样本输入到每棵决策树中进行预测。
  • 对于分类任务，采用投票机制（多数表决）确定最终类别。
  • 对于回归任务，采用平均 $H(x)=\frac{1}{T}{\sum }_{i=1}^T{h}_i(x)H(x)=\backslash frac\{1\}\{T\}\; \backslash sum\_\{i=1\}^T\; h\_i(x)$ 或加权平均 $H(x)=\frac{1}{T}{\sum }_{i=1}^T{w}_i{h}_i(x)H(x)=\backslash frac\{1\}\{T\}\; \backslash sum\_\{i=1\}^T\; w\_i\; h\_i(x)$ 的方式确定最终预测值（$w_{i}w\_i$ 为权值，要求 $w_i\ge 0,{\sum }_{i=1}^T{w}_i=1w\_i\; \backslash geq\; 0,\; \backslash sum\_\{i=1\}^T\; w\_i=1$）。加权平均法的权重一般从训练数据中学习而得，对规模比较大额集成来说，要学习的权重比较多，较容易导致过拟合，因此加权平均法不一定优于简单平均法。

随机森林通过对训练集进行有放回抽样和随机特征选择，增加了模型的多样性和泛化能力。它能够有效地处理高维数据和大规模数据，并且对异常值和噪声有一定的鲁棒性。此外，随机森林还能够评估特征的重要性，提供有关特征对任务的贡献程度的信息。

4.2 Random Forest 优缺点

优点：

• 高度准确性：随机森林能够产生较高的预测准确性，因为它由多个决策树组成，通过集体投票或平均预测来确定最终结果，从而减少了单个决策树的过拟合风险。
• 抗噪能力强：随机森林对于数据中的噪声和异常值具有较好的鲁棒性，它可以通过多棵决策树的集成来减少单个决策树的错误。
• 处理高维数据：随机森林可以处理具有大量特征的高维数据，它能够自动选择重要特征，减少冗余特征的影响，并提供有关特征重要性的信息。
• 可解释性：随机森林可以提供特征重要性评估，它能够告诉我们哪些特征对于模型的预测起到了重要作用。

缺点：

• 训练时间长：随机森林由多个决策树组成，训练时间较长，尤其在处理大规模数据集时。
• 占用内存较大：由于随机森林包含多个决策树，需要占用较大的内存空间存储模型。
• 预测时间长：在进行预测时，需要遍历所有决策树并进行投票或平均，因此预测时间较长。

5. XGBoost

5.1 基本概念

XGBoost（eXtreme Gradient Boosting）是一种基于梯度提升（GBDT）算法的集成学习模型，它在梯度提升算法的基础上进行了优化和改进，具有较高的预测性能和计算效率。下面是 XGBoost 的基本原理和特点：

基本原理：

• XGBoost 通过组合多个弱学习器（通常是决策树）来构建一个强大的集成模型。
• 它通过迭代的方式，每次迭代都根据前一次迭代的结果对模型进行优化，以逐步减少训练误差。
• 每个弱学习器的生成是通过梯度提升算法，即每次迭代时，将损失函数的负梯度作为残差的估计值。

特点：

• 正则化控制：XGBoost 提供了正则化项来控制模型的复杂度，包括 L1 正则化和 L2 正则化，可以有效防止过拟合。
• 损失函数选择：XGBoost 支持多种损失函数的选择，包括平方损失、逻辑损失、指数损失等，可以根据问题的特点选择合适的损失函数。
• 自定义目标函数和评估指标：XGBoost 允许用户自定义目标函数和评估指标，以适应不同的任务和需求。
• 特征重要性评估：XGBoost 能够计算特征的重要性得分，通过衡量特征在模型中的分裂贡献度来评估特征的重要程度。
• 并行计算：XGBoost 支持并行计算，可以利用多线程或分布式计算来加速训练过程。
• 缺失值处理：XGBoost 能够自动处理缺失值，无需对缺失值进行填充或删除。

参考文章：https://www.cnblogs.com/mantch/p/11164221.html 终于有人说清楚了--XGBoost算法

5.2 XGBoost 相对于 GBDT 的改进点

• 正则化项： XGBoost引入了 L1正则化（Lasso）和L2正则化（Ridge）作为模型的正则化项，用于控制模型的复杂度，防止过拟合。

• 损失函数的二阶导数近似： XGBoost通过对损失函数的二阶导数进行近似（二阶泰勒展开），提高模型的训练速度和效率。这种近似方式能够更准确地估计每个叶子节点的分裂增益。

• 列抽样和行抽样： XGBoost 支持对特征和样本进行随机抽样（bootstrap sampling），以减少过拟合的风险。通过随机选择一部分特征和样本，XGBoost 增加了模型的多样性，提高泛化能力。

• 并行计算： XGBoost 实现了并行计算的能力，可以利用多线程和分布式计算来加速训练过程，提高模型训练的效率。

• 缺失值处理： XGBoost 能够自动处理缺失值，无需对缺失值进行填充或删除。XGBoost 使用一种特殊的方式来处理缺失值，在树的分裂过程中将缺失值分配给左子树或右子树。

• 特征重要性评估： XGBoost 能够计算特征的重要性得分，衡量特征在模型中的分裂贡献度。通过特征重要性评估，可以识别和选择最具预测能力的特征，进一步优化模型。

6. LightGBM

LightGBM是一种基于梯度提升决策树（Gradient Boosting Decision Tree，简称GBDT）的机器学习算法，它是 Microsoft 开发的一种高效的梯度提升框架。与传统的 GBDT 算法相比，LightGBM 在训练速度和内存利用方面有较大的优势。

下面是LightGBM的一些主要特点和改进点：

• 基于直方图的决策树算法： LightGBM 采用了一种基于直方图的决策树算法，将连续特征离散化为离散的直方图，减少了内存使用和计算复杂度。

• Leaf-wise 生长策略： 传统的 GBDT 算法是按层级生长树，而 LightGBM 采用了 Leaf-wise 的生长策略，即每次选择当前分裂能够带来最大增益的叶子节点进行生长。这样可以加快训练速度，但容易过拟合，因此 LightGBM 引入了一些正则化手段来控制过拟合。

• 直方图差加速： LightGBM 在构建直方图时使用了差值计算的技巧，减少了直方图的构建时间，提高了训练速度。

• 特征并行化： LightGBM 支持特征并行化，在训练过程中可以并行计算多个特征的直方图，加快了训练速度。

• 稀疏特征优化： LightGBM 对稀疏特征进行了优化，有效地处理了包含大量零值的稀疏特征，提高了训练速度和内存利用效率。

• 并行学习： LightGBM 可以利用多线程和分布式计算来加速训练过程，特别适用于处理大规模数据集。

参考文章：https://zhuanlan.zhihu.com/p/99069186 深入理解LightGBM

面试题

1. LightGBM 和 XGBoost、GBDT 的区别⭐⭐⭐⭐⭐

参考回答

XGBoost 与 LightGBM 的区别

• 分裂策略： XGBoost 采用的是贪心算法，按照最大增益的方式选择最佳的分裂点。而 LightGBM 采用的是基于直方图的分裂策略，将连续特征离散化为离散的直方图，并计算直方图之间的增益，从而选择最佳的分裂点。

• 生长策略： XGBoost 采用的是 Level-wise 的生长策略，即按层级逐层生长树。而 LightGBM 采用的是 Leaf-wise 的生长策略，每次选择当前分裂能够带来最大增益的叶子节点进行生长。Leaf-wise 的生长策略在训练速度上有优势，但容易过拟合，因此 LightGBM 引入了一些正则化手段来控制过拟合。

• 并行化： XGBoost 和 LightGBM 都支持特征并行化，在训练过程中可以并行计算多个特征的直方图，加快了训练速度。但在样本并行化方面，XGBoost 采用了一种类似于数据划分的方式，将数据分成多个子集并并行训练多个模型，而 LightGBM 采用了基于直方图的数据并行化策略，将数据分成多个子集并构建多个直方图进行并行计算。

• 内存利用： LightGBM 在内存利用方面更加高效，它使用了压缩技术和直方图优化，能够处理包含大量零值的稀疏特征，并减少了内存的占用。LightGBM 只保存特征离散化后的值，而这个值一般用 8 位整型存储就足够了，内存消耗可以降低为原来的 1/8

XGBoost 和 GBDT 的区别

• 正则化： XGBoost 引入了正则化项来控制模型的复杂度，包括 L1 正则化（L1 regularization）和 L2 正则化（L2 regularization）。这样可以防止过拟合并提高模型的泛化能力。而 GBDT 通常只使用了简单的剪枝策略来控制模型的复杂度。

• 损失函数： XGBoost 支持多种损失函数，包括平方损失函数（回归问题）、逻辑损失函数（二分类问题）和Softmax损失函数（多分类问题）。GBDT 主要用于回归问题，使用的是平方损失函数。

• 并行化： XGBoost 在训练过程中进行了并行化处理，可以并行计算多个特征的增益并选择最佳的分裂点。这样可以提高训练速度。而 GBDT 通常是串行训练的，无法进行并行计算。

• 特征处理： XGBoost 对于缺失值和稀疏特征有更好的处理能力。它可以自动处理缺失值，并使用稀疏特征优化算法来处理稀疏特征。GBDT 对于缺失值和稀疏特征的处理相对简单。

• 样本权重： XGBoost 支持样本权重的定义，可以根据样本的重要性为不同样本设置不同的权重。这样可以更好地处理不平衡数据集。GBDT 在样本权重方面相对简单，通常采用平等的样本权重。

• 分类器：传统GBDT以 CART 作为基分类器，XGBoost 还支持线性分类器，这个时候 XGBoost 相当于带 L1 和 L2 正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。

• 导数利用：传统GBDT在优化时只用到一阶导数信息，XGBoost 则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数，训练速度更快。

• 实现：GBDT 是机器学习算法，XGBoost 是该算法的工程实现。

2. XGBoost 和 GBDT 的区别⭐⭐⭐⭐⭐

答案同第一题。

3. XGBoost 的 block 结构⭐⭐⭐⭐⭐

XGBoost 中的 block 结构是指模型内部的一种数据组织形式，它有助于提高训练速度和内存利用效率。在树生成过程中，最耗时的一个步骤就是在每次寻找最佳分裂点时都需要对特征的值进行排序。而 XGBoost 在训练之前会根据特征对数据进行排序，然后保存到块结构中，并在每个块结构中都采用了稀疏矩阵存储格式（Compressed Sparse Columns Format，CSC）进行存储，后面的训练过程中会重复地使用块结构，可以大大减小计算量。下面是 XGBoost 中 block 结构：

• 特征块（Feature Blocks）： 特征块是指将特征按列划分为多个块，每个块包含一部分特征。这样可以将特征的计算分布到不同的线程或计算单元上，并实现并行计算。每个特征块可以独立地计算梯度和 Hessian 矩阵，并进行分裂点选择。

作者提出通过按特征进行分块并排序，在块里面保存排序后的特征值及对应样本的引用，以便于获取样本的一阶、二阶导数值。 具体方式如图：

通过顺序访问排序后的块遍历样本特征的特征值，方便进行切分点的查找。此外分块存储后多个特征之间互不干涉，可以使用多线程同时对不同的特征进行切分点查找，即特征的并行化处理。在对节点进行分裂时需要选择增益最大的特征作为分裂，这时各个特征的增益计算可以同时进行，这也是 XGBoost 能够实现分布式或者多线程计算的原因。

4. XGBoost 的优缺点⭐⭐⭐⭐⭐

参考回答

优点

1. 精度更高：GBDT 只用到一阶泰勒展开，而 XGBoost 对损失函数进行了二阶泰勒展开。XGBoost 引入二阶导一方面是为了增加精度，另一方面也是为了能够自定义损失函数，二阶泰勒展开可以近似大量损失函数；

2. 灵活性更强：GBDT 以 CART 作为基分类器，XGBoost 不仅支持 CART 还支持线性分类器，使用线性分类器的 XGBoost 相当于带 L1 和 L2 正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。此外，XGBoost 工具支持自定义损失函数，只需函数支持一阶和二阶求导；

3. 正则化：XGBoost 在目标函数中加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、叶子节点权重的 L2 范式。正则项降低了模型的方差，使学习出来的模型更加简单，有助于防止过拟合，这也是 XGBoost 优于传统 GBDT 的一个特性。

4. 列抽样：XGBoost 借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算。这也是 XGBoost 异于传统 GBDT 的一个特性；

5. 缺失值处理：对于特征的值有缺失的样本，XGBoost 采用的稀疏感知算法可以自动学习出它的分裂方向；

6. XGBoost 工具支持并行：XGBoost在训练之前，预先对数据进行了排序，然后保存为 block 结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。

缺点

1. 计算资源要求高： XGBoost 在大规模数据集上的训练需要较大的计算和内存资源，可能对计算环境有一定要求。

2. 参数调优复杂： XGBoost 有多个参数需要进行调优，包括树的深度、学习率、正则化参数等，需要进行交叉验证等技巧来选择最佳参数组合。

5. 集成学习 Bootstrap Bagging Boosting⭐⭐⭐⭐⭐

Bootstrap、Bagging 和 Boosting 是集成学习中常用的技术，用于提高机器学习模型的性能和泛化能力。它们都是通过组合多个基础模型来构建一个更强大的模型。

• Bootstrap（自助法）： Bootstrap 是一种用于数据采样的技术，用于生成多个训练集。它基于有放回地从原始训练数据集中抽取样本，构成一个新的训练集。通过对原始数据集的多次重采样，可以生成多个不同的训练集，每个训练集都是原始数据集的一部分。具体地：Bootstrap 是一种抽样方法，即随机抽取数据并将其放回。如一次抽取一个样本，然后放回样本集中，下次可能再抽取这个样本。接着将每轮未抽取的数据合并形成袋外数据集（Out of Bag, OOB），用于模型中的测试集。

• Bagging（袋装法）： Bagging 是一种集成学习方法，通过在 Bootstrap 生成的多个训练集上训练多个独立的基础模型，并将它们的预测结果进行平均或投票来进行最终预测。每个基础模型都是独立训练的，它们之间没有依赖关系。Bagging 可以减少模型的方差，提高模型的稳定性和泛化能力。典型算法为随机森林。

• Boosting（提升法）： Boosting 也是一种集成学习方法，与 Bagging 不同的是，Boosting 是通过逐步构建一个强大的模型。Boosting 从一个小的训练集开始，训练一个基础模型，并根据其表现调整样本的权重，使得被错误分类的样本在后续训练中得到更多的关注。通过迭代地训练多个基础模型，并根据其表现进行加权组合，Boosting 可以构建一个更准确的模型。典型算法为 AdaBoost、GBDT。

6. RF 和 GBDT 的区别⭐⭐⭐⭐⭐

• 算法原理： Random Forest 是一种基于决策树的集成学习算法，通过构建多个决策树并使用投票或平均等方式进行集成。GBDT 也是基于决策树的集成学习算法，但是是通过逐步迭代的方式训练多个决策树，每棵树都是在前一棵树的残差上进行训练。
• 集成方式： Random Forest 使用 Bagging 方法并行集成，即通过随机采样生成多个训练集，每个训练集构建一个决策树，最后进行集成。GBDT 使用 Boosting 方法串行生成，即通过逐步迭代的方式构建多个决策树，每棵树都在前一棵树的残差上进行训练，然后将所有树的预测结果进行累加得到最终结果。
• 特征选择： Random Forest 在每次构建决策树时，对于每个节点的特征选择是随机的，从候选特征集中随机选择一部分特征进行评估。而 GBDT 则是根据每个节点的最佳分割准则选择最优特征。
• 并行化能力： Random Forest 的构建过程可以并行化，每个决策树的构建是独立的，可以同时进行。而 GBDT 的每棵树的构建是依赖于前一棵树的残差，所以难以进行并行化处理。
• 预测能力： Random Forest 在处理高维稀疏数据时的预测能力相对较强，而 GBDT 在样本量较大且特征维度较低的情况下表现较好。
• 用途：Random Forest 可以用于回归或分类；GBDT 用于回归。
• 异常值：随机森林对异常值不敏感，而 GBDT 对异常值比较敏感

7. GBDT 是否适合于处理大规模的 ID 特征⭐⭐⭐⭐⭐

参考回答

GBDT 对于海量的 id 类特征，GBDT 由于树的深度和树的数量限制（防止过拟合），不能有效存储；另外海量特征也会存在性能瓶颈，当 GBDT 的 one hot 特征大于 100k 维时，需要做分布式训练才能保证不爆内存

• 内存消耗： GBDT 模型需要存储大量的决策树和相关的节点信息，如果特征空间非常庞大，可能会导致内存消耗较高。这可能会限制模型在内存受限环境下的使用。

• 训练时间： GBDT 模型的训练过程是迭代的，每棵树的训练都需要对所有样本和特征进行遍历，如果特征空间非常大，可能会导致训练时间较长。

• 过拟合风险： 当 ID 特征的基数非常高时，每个 ID 都可以被视为唯一的特征取值，这可能导致每个 ID 都成为 GBDT 模型的叶子节点，从而容易发生过拟合的情况。在这种情况下，需要进行一些特征工程或者模型调参的策略来控制模型的复杂度。

8. LightGBM 的直方图 排序后会比 XGBoost 的效果差吗，为什么⭐⭐⭐⭐⭐

参考回答

1. 基于树模型的 boosting 算法，很多算法比如 XGBoost 都是用预排序（pre-sorting）算法进行特征的选择和分裂

2. LightGBM 采用HistoGram算法，其思想是将连续的浮点特征离散成 k 个离散值，并构造宽度为 k 的 Histogram。然后遍历训练数据，计算每个离散值在直方图中的累计统计量。在进行特征选择时，只需要根据直方图的离散值，遍历寻找最优的分割点。

LightGBM 使用直方图算法来构建决策树，其中的特征分箱是基于直方图的离散化处理。而 XGBoost 则使用精确的分位点方式进行特征分箱。直方图排序会导致特征分箱过程中的信息损失。当特征分箱过程中的排序不准确时，可能会导致特征分布的不连续性。所以如果 LightGBM 的直方图排序后，最优的分割点就变了，效果可能会比 XGBoost 差。

9. XGBoost 正则化项和什么有关⭐⭐⭐⭐⭐

参考回答

XGBoost 的正则化项包括两个部分：L1 正则化项和 L2 正则化项。

• L1 正则化项（也称为 L1 正则化或 Lasso 正则化）：它与叶子节点权重的绝对值成正比。L1 正则化可以促使模型将不重要的特征的权重降为零，从而实现特征选择和模型简化的效果。

• L2 正则化项（也称为 L2 正则化或 Ridge 正则化）：它与叶子节点权重的平方成正比。L2 正则化可以防止模型过度依赖某些特征，降低模型对噪声的敏感性，并使模型更加平滑和稳定。

10. 随机森林哪两个随机⭐⭐⭐⭐⭐

参考回答

2个随机(bootstrap+特征m)

• 随机选择样本：在每个决策树的训练过程中，随机森林从原始数据集中进行有放回的抽样，形成不同的训练子集。这意味着每个决策树都是在不同的样本集上训练的，这样可以增加模型的多样性。

• 随机选择特征：在每个决策树的节点划分过程中，随机森林仅考虑一部分特征进行划分，而不是考虑所有特征。通常，每个节点上的特征候选集是随机选择的，可以通过设定一个固定的特征数或者按照一定的比例来选择。这样做的目的是减少特征之间的相关性，增加每棵决策树的独立性。

11. bootstrap 怎么做的⭐⭐⭐⭐⭐

Bootstrap 是一种用于数据采样的技术，用于生成多个训练集。它基于有放回地从原始训练数据集中抽取样本，构成一个新的训练集。通过对原始数据集的多次重采样，可以生成多个不同的训练集，每个训练集都是原始数据集的一部分。具体地：Bootstrap 是一种抽样方法，即随机抽取数据并将其放回。如一次抽取一个样本，然后放回样本集中，下次可能再抽取这个样本。接着将每轮未抽取的数据合并形成袋外数据集（Out of Bag, OOB），用于模型中的测试集。

12. 介绍 GBDT 的详细计算过程⭐⭐⭐⭐⭐

1.初始化：

• 初始化样本权重：$w_i=\frac{1}{N}w\_i\; =\; \backslash frac\{1\}\{N\}$，其中 $NN$ 是样本总数。
• 初始化模型 $F_0(x)=0F\_0(x)\; =\; 0$。

2.迭代训练：

对于每一轮 $m=1,2,\mathrm{.}\mathrm{.}\mathrm{.},Mm\; =\; 1,\; 2,\; ...,\; M$，进行以下步骤：

• 根据样本权重 $w_{i}w\_i$ 拟合一个决策树模型：$h_m(x)h\_m(x)$。
• 计算当前模型的预测结果：$F_m(x)=F_{m-1}(x)+\eta \cdot h_m(x)F\_m(x)\; =\; F\_\{m-1\}(x)\; +\; \backslash eta\; \backslash cdot\; h\_m(x)$，其中 $\eta \backslash eta$ 是学习率，控制每一棵树的贡献程度。
• 计算当前模型的残差：$r_{im}=y_i-F_m(x_i)r\_\{im\}\; =\; y\_i\; -\; F\_m(x\_i)$，其中 $y_{i}y\_i$ 是样本 $x_{i}x\_i$ 的真实标签。
• 更新样本权重：
  • 计算样本权重的指数损失函数梯度：$g_{im}=\frac{\mathrm{\partial }L(y_i,F_m(x_i))}{\mathrm{\partial }{F}_m(x_i)}g\_\{im\}\; =\; \backslash frac\{\backslash partial\; L(y\_i,\; F\_m(x\_i))\}\{\backslash partial\; F\_m(x\_i)\}$，其中 $LL$ 是损失函数。
  • 更新样本权重：$w_i=w_i\cdot \exp (-g_{im})w\_i\; =\; w\_i\; \backslash cdot\; \backslash exp(-g\_\{im\})$。
• 归一化样本权重：$w_i=\frac{w_i}{{\sum }_{i=1}^N{w}_i}w\_i\; =\; \backslash frac\{w\_i\}\{\backslash sum\_\{i=1\}^\{N\}\; w\_i\}$。

每一轮迭代重复以上步骤。

3.组合最终模型：

• 最终模型的预测结果：$F(x)=F_M(x)={\sum }_{m=1}^M\eta \cdot h_m(x)F(x)\; =\; F\_M(x)\; =\; \backslash sum\_\{m=1\}^\{M\}\; \backslash eta\; \backslash cdot\; h\_m(x)$。

其中，$MM$ 是迭代轮数，$h_m(x)h\_m(x)$ 是第 $mm$ 轮迭代中拟合的决策树模型，$F_m(x)F\_m(x)$ 是第 $mm$ 轮迭代的模型预测结果，$r_{im}r\_\{im\}$ 是第 $ii$ 个样本在第 $mm$ 轮迭代中的残差，$g_{im}g\_\{im\}$ 是样本权重的指数损失函数梯度，$LL$ 是损失函数，$F(x)F(x)$ 是最终组合的模型预测结果。

13. XGBoost 的正则项是什么⭐⭐⭐⭐⭐

XGBoost 的正则化项包括两个部分：L1 正则化项和 L2 正则化项。

• L1 正则化项（也称为 L1 正则化或 Lasso 正则化）：它与叶子节点权重的绝对值成正比。L1 正则化可以促使模型将不重要的特征的权重降为零，从而实现特征选择和模型简化的效果。

• L2 正则化项（也称为 L2 正则化或 Ridge 正则化）：它与叶子节点权重的平方成正比。L2 正则化可以防止模型过度依赖某些特征，降低模型对噪声的敏感性，并使模型更加平滑和稳定。

14. XGBoost 缺失值处理方法⭐⭐⭐⭐⭐

参考回答

论文中关于缺失值的处理将其看与稀疏矩阵的处理看作一样。在寻找 split point 的时候，不会对该特征为 missing 的样本进行遍历统计，只对该列特征值为 non-missing 的样本上对应的特征值进行遍历，通过这个技巧来减少了为稀疏离散特征寻找 split point 的时间开销。在逻辑实现上，为了保证完备性，会分别处理将 missing 该特征值的样本分配到左叶子结点和右叶子结点的两种情形，计算增益后选择增益大的方向进行分裂即可。可以为缺失值或者指定的值指定分支的默认方向，这能大大提升算法的效率。如果在训练中没有缺失值而在预测中出现缺失，那么会自动将缺失值的划分方向放到右子树。

15. 为什么 xgboost 要二阶展开？⭐⭐⭐⭐⭐

参考回答

1. xgboost 是以 mse 为基础推导出来的，在 mse 的情况下， xgboost 的目标函数展开就是一阶项+二阶项的形式，而其他类似 log loss 这样的目标函数不能表示成这种形式。为了后续推导的统一，所以将目标函数进行二阶泰勒展开，就可以直接自定义损失函数了，只要二阶可导即可，增强了模型的扩展性。

2. 二阶信息能够让梯度收敛的更快，类似牛顿法比 SGD 收敛更快。一阶信息描述梯度变化方向，二阶信息可以描述梯度变化方向是如何变化的。

16. 集成学习的方法有哪些⭐⭐⭐⭐⭐

• Bagging（袋装法）： Bagging 是一种集成学习方法，通过在 Bootstrap 生成的多个训练集上训练多个独立的基础模型，并将它们的预测结果进行平均或投票来进行最终预测。每个基础模型都是独立训练的，它们之间没有依赖关系。Bagging 可以减少模型的方差，提高模型的稳定性和泛化能力。典型算法为随机森林。

• Boosting（提升法）： Boosting 也是一种集成学习方法，与 Bagging 不同的是，Boosting 是通过逐步构建一个强大的模型。Boosting 从一个小的训练集开始，训练一个基础模型，并根据其表现调整样本的权重，使得被错误分类的样本在后续训练中得到更多的关注。通过迭代地训练多个基础模型，并根据其表现进行加权组合，Boosting 可以构建一个更准确的模型。典型算法为 AdaBoost、GBDT。

17. 泰勒公式求 e 的近似值⭐⭐⭐⭐⭐

参考回答

自然常数 e 可以用级数 $1+1\mathrm{/}1!+1\mathrm{/}2!+\cdots +1\mathrm{/}n!+\cdots 1+1/1!+1/2!+\cdots +1/n!+\cdots$ 来近似计算。

18. XGBoost 如果损失函数没有二阶导，该怎么办⭐⭐⭐⭐⭐

参考回答

gbdt的目标函数与xgboost区别就是带不带正则项(算法内容上)。gbdt对损失函数的优化是直接使用了损失函数的负梯度，沿着梯度下降的方向来减小损失，其是也就是一阶泰勒展开。而xgboost在这里使用了二阶泰勒展开，因为包含了损失函数的二阶信息，其优化的速度大大加快。但如果loss没有二阶导数，就使用一阶导数优化

19. GBDT 的 G 梯度的向量长度为多少⭐⭐⭐⭐⭐

在梯度提升决策树（Gradient Boosting Decision Tree，GBDT）中，G 梯度的向量长度与训练样本的数量相同。具体而言，如果有 N 个训练样本，则 G 梯度的向量长度为 N。

在每一轮迭代中，GBDT通过计算损失函数对当前模型的负梯度来更新模型，这个负梯度即为 G。对于回归问题，G 的长度为 N，表示每个样本的负梯度值；对于二分类问题，G 的长度同样为 N，每个样本对应的负梯度是一个实数值；对于多分类问题，G 的长度为 N x K，其中 K 是类别数，每个样本的负梯度是一个长度为 K 的向量，表示每个类别的负梯度。

20. 什么是集成学习？简要解释其原理和优势。⭐⭐⭐⭐⭐

集成学习（Ensemble Learning）是一种机器学习方法，通过组合多个基础模型的预测结果来提高整体的预测性能。集成学习的原理基于一个重要的观点：多个模型的综合效果往往比单个模型更好。通过将多个弱学习器（weak learner）组合成强学习器（strong learner），集成学习能够在复杂的问题上取得更好的泛化能力。

集成学习的优势主要体现在以下几个方面：

• 提高预测准确性：集成学习通过结合多个模型的预测结果，可以减少个别模型的错误和偏差，从而提高整体的预测准确性。

• 提高泛化能力：由于集成学习采用多个模型的组合，可以在不同的模型之间取得平衡，避免过拟合问题，提高模型的泛化能力。

• 增强鲁棒性：通过集成多个模型，集成学习可以降低对于特定数据的敏感性，增强模型的鲁棒性，对噪声和异常值具有一定的容错能力。

• 可解释性：集成学习可以通过组合多个基础模型的预测结果，提供更全面和综合的特征表达，从而增强模型的可解释性。

21. Bagging 和 Boosting 的区别是什么？⭐⭐⭐⭐⭐

• 集成方式：Bagging 采用并行的方式，即通过对训练数据进行有放回的抽样，每个基础模型都是独立训练的，最后通过投票或平均等方式进行集成。Boosting 采用串行的方式，每个基础模型都是基于上一个模型的表现进行调整和优化，通过迭代逐步提升模型性能。

• 样本权重：Bagging 中每个基础模型的训练样本权重相等，每个样本都有相同的机会被抽样到不同的子集中进行训练。而 Boosting 中，根据模型在上一轮迭代中的表现，会调整样本的权重，将更多的关注放在难以分类的样本上，使得后续模型更加关注于错误的样本。

• 模型关系：Bagging 中的基础模型是相互独立的，它们之间没有直接的联系。Boosting 中的基础模型是依次构建的，每个模型都试图修正前一个模型的错误，因此模型之间有一定的关联性。

• 预测结果：Bagging 采用投票或平均的方式对多个基础模型的预测结果进行集成。Boosting 中的基础模型通过加权求和的方式进行集成，权重与模型的性能相关。

22. 请解释一下随机森林（Random Forest）的原理。⭐⭐⭐⭐⭐

随机森林的原理如下：

• 数据集采样：从原始训练数据集中采用有放回抽样的方式，随机选择一部分样本作为训练集，这个过程称为自助采样（bootstrap sampling）。每个基础决策树使用不同的自助采样集进行训练。

• 特征随机选择：对于每个决策树的节点，在进行特征选择时，随机从所有特征中选择一个子集作为候选特征。这个过程确保了每个决策树的多样性，避免了过度拟合。

• 决策树训练：基于采样得到的训练集和随机选择的特征子集，构建决策树模型。决策树的生成过程使用递归的方式，根据某个特征的某个阈值将数据划分为更纯净的子节点。

• 集成投票：生成多个决策树后，对新的样本进行分类时，每个决策树都会给出一个分类结果。随机森林通过投票的方式，选择获得最多票数的类别作为最终的分类结果（对于回归问题，可以通过平均预测结果得到回归值）。

随机森林的优势在于：

• 随机性：通过自助采样和特征随机选择，随机森林可以减少模型的方差，避免过拟合，提高泛化能力。

• 高效性：随机森林能够并行训练多个决策树，加快模型训练速度。

• 可解释性：决策树具有很好的可解释性，可以帮助理解特征的重要性和模型的决策过程。

• 对特征缺失和异常值的鲁棒性：随机森林能够处理缺失值和异常值，不需要额外的数据预处理。

23. GBDT（Gradient Boosting Decision Trees）是如何工作的？请列出其算法步骤。⭐⭐⭐⭐⭐

GBDT（Gradient Boosting Decision Tree）是一种集成学习算法，它是由多个决策树组成的集成模型。它通过迭代训练一系列的决策树来逐步提升整体模型的性能。

GBDT 的工作原理如下：

1.初始化：

• 初始化样本权重：$w_i=\frac{1}{N}w\_i\; =\; \backslash frac\{1\}\{N\}$，其中 $NN$ 是样本总数。
• 初始化模型 $F_0(x)=0F\_0(x)\; =\; 0$。

2.迭代训练：

对于每一轮 $m=1,2,\mathrm{.}\mathrm{.}\mathrm{.},Mm\; =\; 1,\; 2,\; ...,\; M$，进行以下步骤：

• 根据样本权重 $w_{i}w\_i$ 拟合一个决策树模型：$h_m(x)h\_m(x)$。
• 计算当前模型的预测结果：$F_m(x)=F_{m-1}(x)+\eta \cdot h_m(x)F\_m(x)\; =\; F\_\{m-1\}(x)\; +\; \backslash eta\; \backslash cdot\; h\_m(x)$，其中 $\eta \backslash eta$ 是学习率，控制每一棵树的贡献程度。
• 计算当前模型的残差：$r_{im}=y_i-F_m(x_i)r\_\{im\}\; =\; y\_i\; -\; F\_m(x\_i)$，其中 $y_{i}y\_i$ 是样本 $x_{i}x\_i$ 的真实标签。
• 更新样本权重：
  • 计算样本权重的指数损失函数梯度：$g_{im}=\frac{\mathrm{\partial }L(y_i,F_m(x_i))}{\mathrm{\partial }{F}_m(x_i)}g\_\{im\}\; =\; \backslash frac\{\backslash partial\; L(y\_i,\; F\_m(x\_i))\}\{\backslash partial\; F\_m(x\_i)\}$，其中 $LL$ 是损失函数。
  • 更新样本权重：$w_i=w_i\cdot \exp (-g_{im})w\_i\; =\; w\_i\; \backslash cdot\; \backslash exp(-g\_\{im\})$。
• 归一化样本权重：$w_i=\frac{w_i}{{\sum }_{i=1}^N{w}_i}w\_i\; =\; \backslash frac\{w\_i\}\{\backslash sum\_\{i=1\}^\{N\}\; w\_i\}$。

每一轮迭代重复以上步骤。

3.组合最终模型：

• 最终模型的预测结果：$F(x)=F_M(x)={\sum }_{m=1}^M\eta \cdot h_m(x)F(x)\; =\; F\_M(x)\; =\; \backslash sum\_\{m=1\}^\{M\}\; \backslash eta\; \backslash cdot\; h\_m(x)$。

其中，$MM$ 是迭代轮数，$h_m(x)h\_m(x)$ 是第 $mm$ 轮迭代中拟合的决策树模型，$F_m(x)F\_m(x)$ 是第 $mm$ 轮迭代的模型预测结果，$r_{im}r\_\{im\}$ 是第 $ii$ 个样本在第 $mm$ 轮迭代中的残差，$g_{im}g\_\{im\}$ 是样本权重的指数损失函数梯度，$LL$ 是损失函数，$F(x)F(x)$ 是最终组合的模型预测结果。

24. Stacking 是什么？请解释其工作原理。⭐⭐⭐⭐⭐

Stacking（堆叠）是一种集成学习方法，它通过将多个基学习器的预测结果作为输入，再使用一个元学习器来对这些预测结果进行整合和组合，从而得到最终的预测结果。

Stacking 的主要思想为：先从初始数据集训练出初级学习器，然后“生成”一个新的数据集用于训练次级学习器。生成的该新数据中，初级学习器的输出被当做样例输入特征，而初始样本的标记仍被当做样例标记（Ground Truth）。也就是说，假设初级学习器有 $MM$ 个，那么对于一个原始数据集中的样本 $(x,y)(x,\; y)$，通过这 $MM$ 个初级学习器有 $MM$ 个输出 $h_1(x),h_2(x),\mathrm{.}\mathrm{.}\mathrm{.},h_M(x)\{h\_1(x),h\_2(x),...,h\_M(x)\}$，把 $h_1(x),h_2(x),\mathrm{.}\mathrm{.}\mathrm{.},h_M(x);y\{h\_1(x),h\_2(x),...,h\_M(x);\; y\}$ 作为新数据的一个样本，所以一个初级学习器的输出作为新数据集中对应样本的一个特征，将原始训练集的真实标签作为目标值。

25. 集成学习中如何处理模型之间的差异和冲突？⭐⭐⭐⭐⭐

在集成学习中，处理模型之间的差异和冲突是非常重要的，以提高集成模型的性能和稳定性。以下是一些常见的方法：

• 多样性引入：模型之间的差异性是通过引入多样性来实现的。可以使用不同的基学习算法、不同的参数设置、不同的特征集或数据子集等方式让模型产生差异。这样可以减少模型之间的相关性，增加集成模型的多样性。

• 交叉验证：使用交叉验证来评估模型的性能，以便发现模型之间的差异和冲突。通过交叉验证，可以对训练数据进行多次划分，训练多个模型，并通过比较它们的性能来选择最佳模型或权重。

• 加权投票：对于分类问题，可以使用加权投票的方式来处理模型之间的差异和冲突。每个模型的预测结果根据其性能和可信度进行加权，从而得到集成模型的最终预测结果。

• 算法组合：可以使用一些特定的算法组合方法，例如Stacking、Blending和Boosting等，来处理模型之间的差异和冲突。这些方法通过结合不同模型的预测结果，并使用元学习器或加权策略来生成最终的集成预测结果。

26. 集成学习在解决什么类型的问题上表现较好？⭐⭐⭐⭐⭐

• 分类问题：集成学习在解决分类问题上表现出色。通过结合多个分类器的预测结果，可以提高整体的分类准确性和鲁棒性。

• 不平衡数据集：当数据集中存在类别不平衡问题时，集成学习可以有效地处理。它可以通过集成模型的投票或加权策略来平衡不同类别的预测结果，从而改善对少数类别的分类效果。

• 噪声数据：集成学习对于噪声数据具有一定的鲁棒性。通过集成多个模型，可以减少个别模型对噪声数据的过拟合程度，提高整体的鲁棒性和泛化能力。

• 复杂问题：对于复杂的问题，集成学习可以通过组合多个简单模型来解决。每个简单模型可以专注于问题的不同方面，最终形成一个强大的集成模型。

27. 在集成学习中，如何处理数据不平衡问题？⭐⭐⭐⭐⭐

• 重采样（Resampling）：通过增加少数类样本或减少多数类样本来平衡数据集。常见的重采样方法包括欠采样（undersampling）和过采样（oversampling）。欠采样通过减少多数类样本来达到平衡，而过采样则通过复制或生成少数类样本来增加其数量。

• 类别权重（Class Weights）：给不同类别赋予不同的权重，使得模型更关注少数类别的学习。在训练过程中，可以调整损失函数中各类别的权重，使得模型更倾向于正确分类少数类别。

• 集成方法：使用集成学习方法，如Bagging或Boosting，来结合多个基分类器的预测结果。在集成过程中，可以采用投票或加权策略，使得少数类别的预测结果得到更多的重视，提高整体的分类准确性。

• 阈值调整：根据具体问题的需求，调整分类器的预测阈值。对于少数类别，可以降低预测阈值，使得模型更容易将其判定为正例，从而提高召回率。