决策树算法之 AdaBoost

AdaBoost 是一种更高级的「森林」类型的决策树，和随机森林比起来，它有以下三个特点

1. AdaBoost 的每棵树都只有一个根节点和两个叶子节点，实际上叫树桩（stump）可能会更合适
2. AdaBoost 的每个树桩的权重是不同的，而随机森林中的每棵树的权重是相同的
3. 前一个树桩的错误数据会影响后一个树桩的生成，意味着后面的树桩是前面树桩的补足。这种思想也被称为 Boosting，除 AdaBoost 外，GBDT 和 XGBoost 也是这样的思想（很明显它们中都有 Boost）。

AdaBoost 的生成步骤

假设我们有以下训练数据，我们想通过「胸口疼痛」、「血管堵塞」和「体重」这三个特征来训练一个心脏病预测模型：

首先，我们需要为每个样本附上一个相同的权重，因为只有 8 条数据，所以每个样本的权重均为 1/8，如下

接下来，我们利用基尼不纯度在这 3 个特征中找一个最合适的作为树根，经过计算，当「体重 >176」 时，基尼不纯度最小，则第一个树桩的节点为「体重 >176」，如下图所示：

产生出一个树桩后，我们把该树桩判断错误的样本拿出来，将它们的权重相加，便得出该树桩的总误差，上述树桩只有一个错误样本：

则该树桩的总误差（Total Error）即这条错误样本的权重——0.125。通过总误差，我们便可以计算出该树桩的 Weight：

$$ Weight_{stump} = \frac{1}{2}\log(\frac{1-TotalError}{TotalError}) $$

该公式的曲线如下图所示，可以看到，误差的取值范围在 0 到 1 之间，随着误差越大，树桩的 Weight 越小，上例中，我们的误差为 0.125，所对应的 Weight 为 0.973，也就是图中蓝色点所处的位置：

一棵树桩产生出来后，接着就要产生第二棵，前面说了，后一棵树的生成依赖于前一棵树的误差，具体的，我们会根据这个误差来调整每个样本的权重，这样，后面的树就可以根据样本的新权重来训练了，更进一步，前一棵树中错误的样本，我们希望在下一棵树的训练中，提高这些样本的权重，同时降低正确样本的权重，这样下一棵树便会更倾向于把错误样本处理好，起到了对前面树的补足作用。

整体误差和树的 Weight 成负相关关系，Weight 越高代表置信度越高，这时错误的样本相对于 Weight 低的树来说，样本权重要调的更高，而正确的样本的权重要调的更低，错误样本权重和正确样本权重的调整分别如下面左图和右图所示：

对于本例来说，第一个树桩的 Weight 为 0.973，则错误样本的权重根据左图公式，将调整为 $0.125 \times 2.646 = 0.33$，同理，正确样本的权重根据右图公式，将调整为 $0.125 \times 0.378=0.05$，归一化后，最终所有样本的权重调整如下：

接下来，我们需要根据新的特征权重来训练树桩，其中的一种办法是根据权重来抽样，即在每抽一条数据之前，产生一个 0-1 的随机数，根据随机数来决定抽哪条数据。以上面的数据举例，当随机数落在 [0, 0.07) 范围内时，则抽出第 1 条样本，落在 [0.07, 0.14) 范围内时，则抽出第 2 条样本，以此类推。

抽样完成后，我们重新对这些样本赋予等值的权重，如下：

因为在选样本时，第 4 条样本的权重最高，它被抽到的概率就最大，从上表也可以看出，第 4 条样本重复了 4 次，这样做的好处是，使用这批数据训练后，新的树桩会更倾向于把第 4 条样本分类正确。推而广之，在 AdaBoost 中，后面的树桩会更擅长于处理前面树桩的错误情况。

接下来的步骤和最开始的一样，重复上面的过程就可以了。

AdaBoost 的预测

在构建完 AdaBoost 后，我们该如何做预测呢？预测过程和随机森林类似，都是用每棵树的结果来投票，差别在于这里采用的是加权投票。例如我们有条数据，每棵树对该数据的预测结果如下：

聚合后，把相同预测结果的 Weight 相加，如下

取 Weight 较大者，所以该条数据的预测结果为 1.

总结

本文我们一起学习了 AdaBoost 的构建过程，AdaBoost 和随机森林比起来，有 3 个特点：

1. 每棵树只有一个根节点和两个叶子节点
2. 后一棵树由前一棵树的误差决定
3. 每棵树都有不同的权重，预测时会根据权重来聚合预测结果

此外，文中对样本加权的手段很有借鉴意义，我们可以把这种方法运用到预测 CTR 等模型的场景中。

参考：AdaBoost, Clearly Explained