数学推导+纯Python实现机器学习算法16：Adaboost

点击上方“小白学视觉”，选择加"星标"或“置顶”

重磅干货，第一时间送达

上一讲我们讲到集成学习的核心算法GBDT，但早在GBDT之前，boosting理念的核心算法是一种被称作为Adaboost的算法。Adaboost全称为Adaptive boosting，可以翻译为自适应提升算法。Adaboost是一种通过改变训练样本权重来学习多个弱分类器并进行线性组合的过程。本讲我们一起来学习一下Adaboost算法原理并尝试给出其基本实现方式。

Adaboost算法原理

boosting方法的核心理念在于博采众长，正所谓"三个臭皮匠，顶个诸葛亮"，这也使得boosting方法要好于大多数单模型算法。一般来说，boosting方法都要解答两个关键问题：一是在训练过程中如何改变训练样本的权重或者是概率分布，二是如何将多个弱分类器组合成一个强分类器。针对这两个问题，Adaboost是做法非常朴素，第一个就是提高前一轮被弱分类器分类错误的样本的权重、而降低分类正确的样本权重；第二则是对多个弱分类器进行线性组合，提高分类效果好的弱分类器权重，减小分类误差率大的弱分类器权重。

给定一个二分类训练数据集

每个样本由输入实例和对应标签组成，实例，标签。我们来看Adaboost的具体算法流程，具体给出算法的每一步，这样在后面做算法实现的时候可以一一对应起来。

(1) 初始化训练样本的权值分布，假设开始训练时每个样本都有相同大小的权值，即样本权值是均匀分布的，，

(2) 对于

使用初始化均匀权值分布的数据集进行训练，可得到弱分类器
计算弱分类器在训练数据上的分类误差率
计算弱分类器的权重
更新训练样本的权值分布其中为规范化因子：

(3) 构建多个弱分类器的线性组合

最终Adaboost的分类器可表示为：

从上述步骤可以看到，Adaboost的算法思想非常简单和朴素，实际用起来也会非常高效。Adaboost是弱分类器通常使用决策树桩(decision stump)，非常简单且灵活。上述Adaboost算法流程可能看起来不够显式，甚至连损失函数和优化算法都找不到，针对于此，所以Adaboost又有了另外一种解释。即Adaboost算法是以加法模型为模型，以指数函数为损失函数，训练算法为前向分布算法的一种二分类算法。这里不做过多展开，具体可参考统计学习方法一书。

Adaboost实现

下面我们根据上述算法流程来编写代码进行实现。

先定义一个决策树桩，本质上就是一个带有阈值划分的决策树结点。

class DecisionStump():    def __init__(self):        # 基于划分阈值决定样本分类为1还是-1        self.polarity = 1        # 特征索引        self.feature_index = None        # 特征划分阈值        self.threshold = None        # 指示分类准确率的值        self.alpha = None

然后直接定义一个Adaboost算法类，将上述算法流程在类中实现。

class Adaboost():    # 弱分类器个数    def __init__(self, n_estimators=5):        self.n_estimators = n_estimators    # Adaboost拟合算法    def fit(self, X, y):        n_samples, n_features = X.shape
        # (1) 初始化权重分布为均匀分布 1/N        w = np.full(n_samples, (1/n_samples))                self.estimators = []        # (2) for m in (1,2,...,M)        for _ in range(self.n_estimators):            # (2.a) 训练一个弱分类器：决策树桩            clf = DecisionStump()            # 设定一个最小化误差            min_error = float('inf')            # 遍历数据集特征，根据最小分类误差率选择最优划分特征            for feature_i in range(n_features):                feature_values = np.expand_dims(X[:, feature_i], axis=1)                unique_values = np.unique(feature_values)                # 尝试将每一个特征值作为分类阈值                for threshold in unique_values:                    p = 1                    # 初始化所有预测值为1                    prediction = np.ones(np.shape(y))                    # 小于分类阈值的预测值为-1                    prediction[X[:, feature_i] < threshold] = -1                    # 2.b 计算误差率                    error = sum(w[y != prediction])                                        # 如果分类误差大于0.5，则进行正负预测翻转                    # E.g error = 0.8 => (1 - error) = 0.2                    if error > 0.5:                        error = 1 - error                        p = -1
                    # 一旦获得最小误差则保存相关参数配置                    if error < min_error:                        clf.polarity = p                        clf.threshold = threshold                        clf.feature_index = feature_i                        min_error = error                                    # 2.c 计算基分类器的权重            clf.alpha = 0.5 * math.log((1.0 - min_error) / (min_error + 1e-10))            # 初始化所有预测值为1            predictions = np.ones(np.shape(y))            # 获取所有小于阈值的负类索引            negative_idx = (clf.polarity * X[:, clf.feature_index] < clf.polarity * clf.threshold)            # 将负类设为 '-1'            predictions[negative_idx] = -1            # 2.d 更新样本权重            w *= np.exp(-clf.alpha * y * predictions)            w /= np.sum(w)
            # 保存该弱分类器            self.estimators.append(clf)        # 定义预测函数


    
    def predict(self, X):        n_samples = np.shape(X)[0]        y_pred = np.zeros((n_samples, 1))        # 计算每个弱分类器的预测值        for clf in self.estimators:            # 初始化所有预测值为1            predictions = np.ones(np.shape(y_pred))            # 获取所有小于阈值的负类索引            negative_idx = (clf.polarity * X[:, clf.feature_index] < clf.polarity * clf.threshold)            # 将负类设为 '-1'            predictions[negative_idx] = -1            # 2.e 对每个弱分类器的预测结果进行加权            y_pred += clf.alpha * predictions
        # 返回最终预测结果        y_pred = np.sign(y_pred).flatten()        return y_pred

这样，一个完整Adaboost算法就搞定了。我们使用sklearn默认数据集来看一下算法效果。

from sklearn import datasetsfrom sklearn.metrics import accuracy_scorefrom sklearn.model_selection import train_test_split
data = datasets.load_digits()X = data.datay = data.target
digit1 = 1digit2 = 8idx = np.append(np.where(y==digit1)[0], np.where(y==digit2)[0])y = data.target[idx]# Change labels to {-1, 1}y[y == digit1] = -1y[y == digit2] = 1X = data.data[idx]
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.7)
# 使用5个弱分类器clf = Adaboost(n_clf=5)clf.fit(X_train, y_train)y_pred = clf.predict(X_test)
accuracy = accuracy_score(y_test, y_pred)print ("Accuracy:", accuracy)

验证集分类精度接近达到0.94，可见我们编写的Adaboost算法还比较成功。

Accuracy: 0.9397590361445783

sklearn也提供了Adaboost对应的api：

from sklearn.ensemble import AdaBoostClassifierclf_ = AdaBoostClassifier(n_estimators=5, random_state=0)# trainclf_.fit(X_train, y_train)# validy_pred_ = clf_.predict(X_test)accuracy = accuracy_score(y_test, y_pred_)print ("Accuracy:", accuracy)

Accuracy: 0.8733734939759037

可以看到sklearn对于Adaboost的封装使用起来非常便捷，实际工作中我们直接调包即可。

好消息！

小白学视觉知识星球

开始面向外开放啦👇👇👇

下载1：OpenCV-Contrib扩展模块中文版教程

在「小白学视觉」公众号后台回复：扩展模块中文教程，即可下载全网第一份OpenCV扩展模块教程中文版，涵盖扩展模块安装、SFM算法、立体视觉、目标跟踪、生物视觉、超分辨率处理等二十多章内容。

下载2：Python视觉实战项目52讲

在「小白学视觉」公众号后台回复：Python视觉实战项目，即可下载包括图像分割、口罩检测、车道线检测、车辆计数、添加眼线、车牌识别、字符识别、情绪检测、文本内容提取、面部识别等31个视觉实战项目，助力快速学校计算机视觉。

下载3：OpenCV实战项目20讲

在「小白学视觉」公众号后台回复：OpenCV实战项目20讲 ，即可下载含有20个基于OpenCV实现20个实战项目，实现OpenCV学习进阶。

交流群

欢迎加入公众号读者群一起和同行交流，目前有SLAM、三维视觉、传感器、自动驾驶、计算摄影、检测、分割、识别、医学影像、GAN、算法竞赛等微信群（以后会逐渐细分），请扫描下面微信号加群，备注：”昵称+学校/公司+研究方向“，例如：”张三 + 上海交大 + 视觉SLAM“。请按照格式备注，否则不予通过。添加成功后会根据研究方向邀请进入相关微信群。请勿在群内发送广告，否则会请出群，谢谢理解~