什么是AdaBoost 算法？

AdaBoost（Adaptive Boosting）算法，全称为 自适应提升 ，是 一种在机器学习中用作集成方法的提升技术 。它之所以被称为自适应提升，因为每个实例的权重会重新分配，错误分类的实例分配较高的权重。

它属于boosting算法家族，其核心思想是通过迭代训练多个弱分类器（weak classifiers），每个弱分类器针对之前迭代中被错误分类的样本进行重点训练，最终将这些弱分类器组合成一个强分类器。

AdaBoost 算法的优点和缺点

优点

• 高精度： AdaBoost能够将多个弱分类器组合成一个强分类器，从而提高整体分类性能。
• 抗过拟合： 由于算法重点关注错误分类的样本，因此具有一定的抗过拟合能力。
• 适用性广泛： 可以应用于各种类型的问题，并且对于大型数据集或具有复杂模式的数据集也适用。
• 多功能： 可以与不同类型的基础分类器一起使用，从而实现建模的灵活性。

缺点

• 对噪声数据敏感： AdaBoost对噪声数据非常敏感，因为它会将更多的注意力放在错误分类的样本上。
• 计算开销大： 在训练过程中，AdaBoost需要大量的计算资源，尤其是在处理大规模数据集时。
• 超参数调优： 迭代次数和弱分类器的选择都是需要调优的超参数，这需要一定的经验和计算成本。
• 对不平衡数据集表现不佳： 当某一类样本数量远远超过其他类别时，AdaBoost可能会出现性能下降的情况。

AdaBoost 算法的工作原理

1. 初始化样本权重： 算法开始时，为每个样本赋予相同的权重，这些权重表示样本的重要性。初始情况下，所有样本对分类器的影响被认为是相同的。

2. 迭代训练弱分类器： AdaBoost通过多次迭代训练弱分类器，每个迭代都会生成一个弱分类器，比如单层决策树（decision stump），该分类器略优于随机猜测。

3. 加权训练： 在每次迭代中，弱分类器都会根据当前样本权重进行训练，以最小化错误分类。这意味着算法更加关注之前分类错误的样本。

4. 更新样本权重： 在每次迭代后，算法会更新样本的权重，将错误分类的样本的权重增加，而正确分类的样本的权重减少。

5. 集成弱分类器： 经过多次迭代后，AdaBoost将所有弱分类器组合成一个强分类器，通过加权多数投票的方式获得最终分类结果。

6. 重复迭代： 重复上述步骤，直到达到预设的迭代次数或者达到停止条件。

大致过程如图所示：

图片来自于：AdaBoost Algorithm: Understand, Implement and Learn

这个算法的作用是构建一个模型，并给所有数据点赋予相等的权重。然后为错误分类的数据点赋予更高的权重。现在，所有具有较高权重的数据点在下一个模型中将被赋予更多的重要性。它会不断训练模型，直到获得较低的错误为止。

Titanic 数据集例子

假设我们在 Titanic 数据集上构建了一个决策树算法，并得到了 80% 的准确率。之后，应用了不同的算法，并检查准确率，结果为 KNN 算法的 75% 和线性回归的 70%。

在同一数据集上构建不同模型时，我们会观察到准确率的变化。然而，通过利用 AdaBoost 的力量，我们可以结合这些算法来增强最终的预测。通过平均不同模型的结果，AdaBoost 使我们能够有效地提高准确率并增强预测能力。

让我们现在一步步的理解这个处理的过程，来了解这个算法的工作原理。

步骤 1 ：分配权重

Row No.	Gender	Age	Income	Illness	Sample Weights
1	Male	41	40,000	Yes	1/5
2	Male	54	30,000	No	1/5
3	Female	42	25,000	No	1/5
4	Female	40	60,000	Yes	1/5
5	Male	46	50,000	Yes	1/5

我们数据集的实际表示如表所示。由于目标列是二元的（是否生病），所以这是一个分类问题。首先，这些数据点将被分配一些权重。最初，所有的权重将是相等的。
计算样本权重的公式是：
$$w(x_i,y_i)=\frac{1}{N},i=1,2,....n$$
其中 N 是数据点的总数，这里因为我们有 5 个数据点，所以分配的样本权重将是 1/5。

步骤 2：分类样本

我们首先看看“性别”如何分类样本，然后再看看变量（年龄，收入）如何分类样本。

我们将为每个特征创建一个 决策树桩（decision stump） ，然后计算每个树的基尼指数（Gini Index）。基尼指数（Gini Index）最低的树将是我们的第一个树桩。

在我们的数据集中，假设性别具有最低的基尼指数，因此它将是我们的第一个树桩。

在步骤2中，为了更好地理解 AdaBoost 算法，我们需要了解一些基本概念：决策树桩和基尼指数。下面详细解释这些概念。

决策树桩（Decision Stump）是什么？

决策树桩是决策树的一种简单形式，它 只考虑一个特征 来进行决策。它是一个只有一层深度的决策树，意味着它只基于一个特征将数据划分成两类。

示例：

假设我们有一个数据集，包含两个特征“年龄”和“收入”，以及一个二元分类标签“是否购买”。一个决策树桩可能会基于“年龄”特征，将数据划分成“年龄<30”和“年龄≥30”两类。然后它会根据这两个类别分别预测是否购买。

由于决策树桩非常简单，只能基于一个特征进行划分，所以它被称为“弱学习器”。但在 AdaBoost 中，通过组合多个弱学习器，我们可以获得一个强大的分类器。

基尼指数（Gini Index）是什么？

基尼指数是用于评估决策树分割质量的一种指标。它衡量了数据集中类别的不纯度。基尼指数的计算公式为：

$$Gini(D)=1-\sum _{k=1}^n{p}_k^2$$

其中，$p_k$ 是第 $k$ 类在数据集 $D$ 中的比例。

基尼指数的取值范围在 0 到 0.5 之间：

• 当基尼指数为 0 时，数据集是纯净的，只有一个类别。
• 当基尼指数接近 0.5 时，数据集的类别分布是最不均匀的。

“基尼指数最低的树将是我们的第一个树桩。”如何理解这句话？

在构建 AdaBoost 模型的过程中，我们需要选择一个最能区分数据的特征作为第一个决策树桩。这句话的意思是我们将选择基尼指数最低的决策树桩作为第一个弱学习器。基尼指数最低意味着这个决策树桩能够 最好地划分数据 ，从而减少数据集的不纯度。

理解这个过程：

1. 计算每个特征的基尼指数：对于每个特征（例如“年龄”、“收入”等），计算它们基于不同划分点（例如“年龄<30”和“年龄≥30”）的基尼指数。
2. 选择基尼指数最低的特征：比较所有特征的基尼指数，选择基尼指数最低的特征作为第一个决策树桩。
3. 构建第一个决策树桩：基于选定的特征构建第一个决策树桩，这个树桩将用于第一次划分数据。

通过这种方法，我们保证第一个弱学习器能够尽可能有效地对数据进行分类，从而为后续的模型训练提供良好的基础。

步骤 3：计算影响

现在我们将计算这个分类器在分类数据点中的“影响量（Amount of Say）”或“重要性（Importance）”或“影响力（Influence）”，使用以下公式：

$$Influence=\frac{1}{2}log\frac{1-TotalError}{TotalError}$$
总错误（TotalError）只是错误分类数据点的所有样本 权重的总和 。

在我们的数据集中，假设有一个错误输出，所以我们的总错误（TotalError）将是 1/5（只有对应错误样本点的权重），而 alpha（树桩的表现）将是：

$$Performanceofthestump=\frac{1}{2}{\log }_e\left(\frac{1-\text{ Total Error }}{\text{ Total Error }}\right)$$

$$\begin{array}{rl}\alpha & =\frac{1}{2}{\log }_e\left(\frac{1-\frac{1}{5}}{\frac{1}{5}}\right)\\ \alpha & =\frac{1}{2}{\log }_e\left(\frac{0.8}{0.2}\right)\\ \alpha & =\frac{1}{2}{\log }_e(4)=\frac{1}{2}\ast (1.38)\\ \alpha & =0.69\end{array}$$

注意： 总错误（TotalError）将始终在 0 和 1 之间。

0 表示完美的树桩（没有一个错误），1 表示糟糕的树桩（全错）。

从上图可以看出，当没有错误分类时，我们的总错误为 0，因此“影响量（alpha）”将是一个大数值。

当分类器预测一半正确一半错误时，总错误为 0.5，分类器的重要性（影响量）将为 0。

如果所有样本都被错误分类，那么错误将非常高（接近 1），因此我们的 alpha 值将为负数。

步骤 4：计算总错误和表现

为什么要计算 AdaBoost 树桩的总错误（TE）和表现？更新权重是关键 。如果对后续模型保持相同的权重，输出将与初始模型相同。

错误的预测将被赋予更高的权重，而正确的预测权重将减少。当我们在更新权重后构建下一个模型时，具有更高权重的点将被赋予更多的优先权。

在找到分类器的重要性和总错误后，我们需要最终更新权重，为此我们使用以下公式：

$$Newsampleweight=oldweight\ast e^{\pm Amountofsay(\alpha )}$$

当样本被正确分类时，影响量（alpha）将为负。

当样本被错误分类时，影响量（alpha）将为正。

这里有四个正确分类的样本和一个错误分类的样本。错误分类数据点的样本权重为 1/5，性别树桩的表现为 0.69（前面通过公式计算得到）。

正确分类样本的新权重是：

$$Newsampleweight=\frac{1}{5}\ast exp(-0.69)$$
$$Newsampleweight=0.2\ast 0.502=0.1004$$

对于错误分类的样本，更新后的权重为：
$$Newsampleweight=\frac{1}{5}\ast exp(0.69)$$
$$Newsampleweight=0.2\ast 1.994=0.3988$$

注意（Note）
当我填入值时，请看 alpha 的符号，当数据点正确分类时，alpha 为负，这将样本权重从 0.2 减少到 0.1004。当有错误分类时，它为正，这将样本权重从 0.2 增加到 0.3988。

Row No.	Gender	Age	Income	Illness	Sample Weights	New Sample Weights
1	Male	41	40,000	Yes	1/5	0.1004
2	Male	54	30,000	No	1/5	0.1004
3	Female	42	25,000	No	1/5	0.1004
4	Female	40	60,000	Yes	1/5	0.3988
5	Male	46	50,000	Yes	1/5	0.1004

我们知道样本权重的总和必须等于 1，但这里如果我们将所有新样本权重相加，我们将得到 0.8004。为了使这个总和等于 1，我们将通过将所有权重除以更新权重的总和 0.8004 来 归一化 这些权重。所以，归一化后的样本权重是这样的，现在总和等于 1。

为了确保在重新采样时，权重作为概率来使用。
权重越大，数据点被选中的概率就越高。

Row No.	Gender	Age	Income	Illness	Sample Weights	New Sample Weights
1	Male	41	40,000	Yes	1/5	0.1004 / 0.8004 = 0.1254
2	Male	54	30,000	No	1/5	0.1004 / 0.8004 = 0.1254
3	Female	42	25,000	No	1/5	0.1004 / 0.8004 = 0.1254
4	Female	40	60,000	Yes	1/5	0.3988 / 0.8004 = 0.4982
5	Male	46	50,000	Yes	1/5	0.1004 / 0.8004 = 0.1254

步骤 5：减少错误

现在，我们需要创建一个新数据集来查看错误是否减少。为此，我们将删除“样本权重”（“sample weights”）和“新样本权重”（“new sample weights”）列，然后根据“新样本权重”（“new sample weights”）将我们的数据点分成几个桶（buckets）。

Row No.	Gender	Age	Income	Illness	Sample Weights	New Sample Weights	Buckets
1	Male	41	40,000	Yes	1/5	0.1004 / 0.8004 = 0.1254	0 to 0.1254
2	Male	54	30,000	No	1/5	0.1004 / 0.8004 = 0.1254	0.1254 to 0.2508
3	Female	42	25,000	No	1/5	0.1004 / 0.8004 = 0.1254	0.2508 to 0.3762
4	Female	40	60,000	Yes	1/5	0.3988 / 0.8004 = 0.4982	0.3762 to 0.8744
5	Male	46	50,000	Yes	1/5	0.1004 / 0.8004 = 0.1254	0.8744 to 0.9998

buckets是什么？用来干啥的？

buckets 用于重新采样数据点。为了重新采样数据，我们会生成随机数（范围在0到1之间），这些随机数落在哪个bucket中，就选择哪个bucket对应的数据点。

例如，如果随机数是 0.38，那么它落在 0.3762（0.1254 * 3 ） 到 0.8744（0.3762 + 0.4982-归一化得到的新权重） 之间，因此我们选择第4个样本。

bucket计算过程是怎样的？

• 第一个数据点的新权重为0.1254，累积区间为0到0.1254（0+0.1254）。
• 第二个数据点的新权重为0.1254，累积区间为0.1254到0.2508（0.1254+0.1254）。
• 第三个数据点的新权重为0.1254，累积区间为0.2508到0.3762（0.2508+0.1254）。
• 第四个数据点的新权重为0.4982，累积区间为0.3762到0.8744（0.3762+0.4982）。
• 第五个数据点的新权重为0.1254，累积区间为0.8744到0.9998。

累积权重区间（buckets）是通过将每个数据点的权重依次累加而得出的。每个数据点的累积权重区间从前一个数据点的累积区间上限开始，加上当前数据点的权重。

步骤 6：新数据集

到这一步，我们基本上完成了。现在，算法会从 0 到 1 选择随机数。由于错误分类的记录具有较高的样本权重，选择这些记录的概率非常高。

假设算法选择的 5 个随机数是 [0.58842873 0.88056847 0.61431001 0.02307079 0.69973373]。

• 0.58842873 处于 （0.3762 到 0.8744）——第四个样本
• 0.88056847 处于（0.8744 到 0.9998）——第五个样本
• 0.61431001 处于 （0.3762 到 0.8744）——第四个样本
• 0.02307079 处于（0 到 0.1254）——第一个样本
• 0.69973373 处于 （0.3762 到 0.8744）——第四个样本

现在我们将看到这些随机数落在桶中的位置，并据此创建我们的新数据集，如下所示。

Row No.	Gender	Age	Income	Illness	Sample Weights	New Sample Weights	Buckets
4	Female	40	60,000	Yes	1/5	0.4982	0.3762 to 0.8744
5	Male	46	50,000	Yes	1/5	0.1254	0.8744 to 0.9998
4	Female	40	60,000	Yes	1/5	0.4982	0.3762 to 0.8744
1	Male	41	40,000	Yes	1/5	0.1254	0 to 0.1254
4	Female	40	60,000	Yes	1/5	0.4982	0.3762 to 0.8744

这就是我们的新数据集，我们看到错误分类的数据点被选中了三次，因为它具有较高的权重。

步骤 7：重复前面的步骤

现在，这成为我们的新数据集，我们需要重复上述所有步骤，即：

• 为所有数据点分配相等的权重。
• 找到分类新样本集合最好的树桩，通过找到它们的基尼指数并选择基尼指数最低的一个。
• 计算“影响量”和“总错误”以更新先前的样本权重。
• 归一化新样本权重。
• 迭代这些步骤，直到达到较低的训练误差。

假设就我们的数据集而言，我们已经以顺序方式构建了 3 棵决策树（DT1、DT2、DT3）。如果我们现在发送我们的测试数据，它将通过所有决策树，最后我们将看到哪个类占多数，并根据此对我们的测试数据集进行预测。

参考文章：

• Understanding the AdaBoost Algorithm | by Data Science Wizards | Medium
• AdaBoost Algorithm: Understand, Implement and Learn