机器学习——打开集成方法的大门，手把手带你实现AdaBoost模型

本文始发于个人公众号：TechFlow，原创不易，求个关注

今天是机器学习专题的第25篇文章，我们一起来聊聊AdaBoost。

我们目前为止已经学过了好几个模型，光决策树的生成算法就有三种。但是我们每次进行分类的时候，每次都是采用一个模型进行训练和预测。我们日常在做一个决策的时候，往往会咨询好几个人，综合采纳他们的意见。那么有没有可能把这个思路照搬到机器学习领域当中，创建多个模型来综合得出结果呢？

这当然是可以的，这样的思路就叫做集成方法（ensemble method）。

集成方法

集成方法本身并不是某种具体的方法或者是算法，只是一种训练机器学习模型的思路。它的含义只有一点，就是训练多个模型，然后将它们的结果汇聚在一起。

根据这个思路，业内又衍生出了三种特定的方法，分别是Bagging、Boosting和Stacking。

Bagging

Bagging是bootstrap aggregating的缩写，我们从字面上很难理解它的含义。我们记住这个名字即可，在Bagging方法当中，我们会通过有放回随机采样的方式创建K个数据集。对于每一个数据集来说，可能有一些单个的样本重复出现，也可能有一些样本从没有出现过，但整体而言，每个样本出现的概率是相同的。

之后，我们用抽样出来的K个数据集训练K个模型，这里的模型没有做限制，我们可以使用任何机器学习方模型。K个模型自然会得到K个结果，那么我们采取民主投票的方式对这K个模型进行聚合。

举个例子说，假设K=25，在一个二分类问题当中。有10个模型预测结果是0，15个模型预测结果是1。那么最终整个模型的预测结果就是1，相当于K个模型民主投票，每个模型投票权一样。大名鼎鼎的随机森林就是采取的这种方式。

Boosting

Boosting的思路和Bagging非常相似，它们对于样本的采样逻辑是一致的。不同的是，在Boosting当中，这K个模型并不是同时训练的，而是串行训练的。每一个模型在训练的时候都会基于之前模型的结果，更加关注于被之前模型判断错误的样本。同样，样本也会有一个权值，错误判断率越大的样本拥有越大的权值。

并且每一个模型根据它能力的不同，会被赋予不同的权重，最后会对所有模型进行加权求和，而不是公平投票。由于这个机制，使得模型在训练的时候的效率也有差异。因为Bagging所有模型之间是完全独立的，我们是可以采取分布式训练的。而Boosting中每一个模型会依赖之前模型的效果，所以只能串行训练。

Stacking

Stacking是Kaggle比赛当中经常使用的方法，它的思路也非常简单。我们选择K种不同的模型，然后通过交叉验证的方式，在训练集上进行训练和预测。保证每个模型都对所有的训练样本产出一个预测结果。那么对于每一条训练样本，我们都能得到K个结果。

之后，我们再创建一个第二层的模型，它的训练特征就是这K个结果。也就是说Stacking方法当中会用到多层模型的结构，最后一层模型的训练特征是上层模型预测的结果。由模型自己去训练究竟哪一个模型的结果更值得采纳，以及如何组合模型之间的特长。

我们今天介绍的AdaBoost顾名思义，是一个经典的Boosting算法。

模型思路

AdaBoost的核心思路是通过使用Boosting的方法，通过一些弱分类器构建出强分类器来。

强分类器我们都很好理解，就是性能很强的模型，那么弱分类器应该怎么理解呢？模型的强弱其实是相对于随机结果来定义的，比随机结果越好的模型，它的性能越强。从这点出发，弱分类器也就是只比随机结果略强的分类器。我们的目的是通过设计样本和模型的权重，使得可以做出最佳决策，将这些弱分类器的结果综合出强分类器的效果来。

首先我们会给训练样本赋予一个权重，一开始的时候，每一条样本的权重均相等。根据训练样本训练出一个弱分类器并计算这个分类器的错误率。然后在同一个数据集上再次训练弱分类器，在第二次的训练当中，我们将会调整每个样本的权重。其中正确的样本权重会降低，错误的样本权重会升高。

同样每一个分类器也会分配到一个权重值，权重越高说明它的话语权越大。这些是根据模型的错误率来计算的。错误率定义为：

这里的D表示数据集表示分类错误的集合，它也就等于错误分类的样本数除以总样本数。

有了错误率之后，我们可以根据下面这个公式得到。

得到了之后，我们利用它对样本的权重进行更新，其中分类正确的权重更改为：

分类错误的样本权重更改为：

这样，我们所有的权重都更新完了，这也就完成了一轮迭代。AdaBoost会反复进行迭代和调整权重，直到训练错误率为0或者是弱分类器的数量达到阈值。

代码实现

首先，我们来获取数据，这里我们选择了sklearn数据集中的乳腺癌预测数据。和之前的例子一样，我们可以直接import进来使用，非常方便：

import numpy as np
import pandas as pd
from sklearn.datasets import load_breast_cancer

breast = load_breast_cancer()
X, y = breast.data, breast.target
# reshape，将一维向量转成二维
y = y.reshape((-1, 1))

接着，我们将数据拆分成训练数据和测试数据，这个也是常规做法了，没有难度：

from sklearn.model_selection import train_test_split

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=23)

在AdaBoost模型当中，我们选择的弱分类器是决策树的树桩。所谓的树桩就是树深为1的决策树。树深为1显然不论我们怎么选择阈值，都不会得到特别好的结果，但是由于我们依然会选择阈值和特征，所以结果也不会太差，至少要比随机选择要好。所以这就保证了，我们可以得到一个比随机选择效果略好一些的弱分类器，并且它的实现非常简单。

在我们实现模型之前，我们先来实现几个辅助函数。

def loss_error(y_pred, y, weight):
    return weight.T.dot((y_pred != y_train))

def stump_classify(X, idx, threshold, comparator):
    if comparator == 'lt':
        return X[:, idx] <= threshold
    else:
        return X[:, idx] > threshold
    
def get_thresholds(X, i):
    min_val, max_val = X[:, i].min(), X[:, i].max()
    return np.linspace(min_val, max_val, 10)

这三个函数应该都不难理解，第一个函数当中我们计算了模型的误差。由于我们每一个样本拥有一个自身的权重，所以我们对误差进行加权求和。第二个函数是树桩分类器的预测函数，逻辑非常简单，根据阈值比较大小。这里有两种情况，有可能小于阈值的样本是正例，也有可能大于阈值的样本是正例，所以我们还需要第三个参数记录这个信息。第三个函数是生成阈值的函数，由于我们并不需要树桩的性能特别好，所以我们也没有必要去遍历阈值的所有取值，简单地把特征的范围划分成10段即可。

接下来是单个树桩的生成函数，它等价于决策树当中选择特征进行数据拆分的函数，逻辑大同小异，只需要稍作修改即可。

def build_stump(X, y, weight):
    m, n = X.shape
    ret_stump, ret_pred = None, []
    best_error = float('inf')

    # 枚举特征
    for i in range(n):
        # 枚举阈值
        for j in get_thresholds(X, i):
            # 枚举正例两种情况
            for c in ['lt', 'gt']:
                # 预测并且求误差
                pred = stump_classify(X, i, j, c).reshape((-1, 1))
                err = loss_error(pred, y, weight)
                # 记录下最好的树桩
                if err < best_error:
                    best_error, ret_pred = err, pred.copy()
                    ret_stump = {'idx': i, 'threshold': j, 'comparator': c} 
    return ret_stump, best_error, ret_pred

接下来要做的就是重复生成树桩的操作，计算和，并且更新每一条样本的权重。整个过程也没有太多的难点，基本上就是照着实现公式：

def adaboost_train(X, y, num_stump):
    stumps = []
    m = X.shape[0]
    # 样本权重初始化，一开始全部相等
    weight = np.ones((y_train.shape[0], 1)) / y_train.shape[0]
    # 生成num_stump个树桩
    for i in range(num_stump):
        best_stump, err, pred = build_stump(X, y, weight)
        # 计算alpha
        alpha = 0.5 * np.log((1.0 - err) / max(err, 1e-10))
        best_stump['alpha'] = alpha
        stumps.append(best_stump)

        # 更新每一条样本的权重
        for j in range(m):
            weight[j] = weight[j] * (np.exp(-alpha) if pred[j] == y[j] else np.exp(alpha))
        weight = weight / weight.sum()
        # 如果当前的准确率已经非常高，则退出
        if err < 1e-8:
            break
    return stumps

树桩生成结束之后，最后就是预测的部分了。整个预测过程依然非常简单，就是一个加权求和的过程。这里要注意一下，我们在训练的时候为了突出错误预测的样本，让模型拥有更好的能力，维护了样本的权重。然而在预测的时候，我们是不知道预测样本的权重的，所以我们只需要对模型的结果进行加权即可。

def adaboost_classify(X, stumps):
    m = X.shape[0]
    pred = np.ones((m, 1))
    alphs = 0.0
    for i, stump in enumerate(stumps):
        y_pred = stump_classify(X, stump['idx'], stump['threshold'], stump['comparator'])
        # 根据alpha加权求和
        pred = y_pred * stump['alpha']
        alphs += stump['alpha']
    pred /= alphs
    # 根据0.5划分0和1类别
    return np.sign(pred).reshape((-1, 1))