KeepNotes blog

Stay hungry, Stay Foolish.

0%

统计学习方法-AdaBoost笔记

Posted on Edited on In
Symbols count in article: 4.2k Reading time ≈ 4 mins.

AdaBoost算法和SVM算法曾被当做两大最好的监督学习分类算法，现在可能要再加上神经网络了（以上均为听说。。。）

AdaBoost是adaptive boosting的缩写（自适应增强学习），是基于Boosting思想的机器学习算法，是集成学习中的一种，其基本原理就是将多个弱分类器（弱分类器一般选用单层决策树，也叫决策树桩）进行线性组合，使其成为一个强分类器，从而提高分类性能 说到Boost方法，则需要先理解下集成方法（参照文章：集成学习原理小结）：

  • 集成方法本身不是单个机器学习算法，而是通过构造并结合多个学习机来学习；可以用于分类问题集成，回归问题集成，特征选取集成，异常点检测集成等等
  • 集成方法的个体学习机有两种选择：1. 个体学习机是同质的，即都为同一种学习机，比如都是决策树或者都是神经网络；2. 个体学习机是异质的，即是由不同学习机组成的，比如由SVM/LR/NB等学习机共同来学习
  • 目前来说同质学习机使用最为广泛，其主要可以分为两大类：Bagging和Boosting（其实还有stacking，这里不做介绍了）
    • Bagging方法，主要通过对训练数据集进行随机采样，以重新组合成不同的数据集，利用弱学习算法对不同的新数据集进行学习，得到一系列的预测结果；对这些预测结果做平均或者投票做出最终的预测，因此这多个学习机是并行的，如随机森林算法
    • Boosting方法，主要通过对样本设置权值（错误学习的样本给予较大的权值），最终得到一系列的预测结果，并用加权多数表决方法，使预测效果较好的个体学习机获得较大的权值，因此这多个学习机是串行的，比如AdaBoost和GBDT(Gradient Boost Decision Tree，梯度提升决策树)算法

此外再补充一句（机器学习-周志华）：Boosting主要关注降低偏差，因此Boosting能基于泛化性能相当弱的学习器构建出很强的集成；Bagging主要关注降低方差，因此它在不剪枝的决策树、神经网络等学习器上效用更为明显

简单易学的机器学习算法——AdaBoost

从AdaBoost算法中可看出，其主要两个权值：

  • 第一个是样本权值，每个样本都一个初始化权值，然后不断迭代，提高前一轮被错误分类样本的权值，并且在Z归一化后，使得每次总权值不变，因此正确分类的样本权值会不断减少，而错误分类样本权值则会不断增加（相当于中加权误差）
  • 第二个是弱分类器（一般指那些误差率略低于50% 的算法，比如单层决策树？）权值，由于每个弱分类器一般侧重于前一轮错误分类的样本（因为错误分类样本权值高），但其不能保证将之前都正确分类的样本也再次分对，因此需要通过分类错误率来计算每个弱分类器的权值；由于AdaBoost算法最终是多个弱分类器线性组合的结果，再加上加权多数表决的方法，因此权值越大的弱分类器，其对于最终分类效果其的作用就越大

此外对于弱分类器而言，不仅仅局限于单层决策树，其他分类器都是可以的，但是简单的弱分类器效果更好

从上也能大致看出AdaBoost算法的基本思路（分而治之），如果以二分类问题算法为例（弱分类器选择决策树桩），算法流程如下（参照《统计学习方法》）：

  • 初始化样本权值
  • 循环选择每个特征值的切点（阈值），找出加权误差率最小的切点
  • 根据公式8.2计算弱分类器的权值alpha
  • 根据公式8.4更新每个样本的权值D
  • 迭代多次（或者直至误差样本为0），根据公式8.7构建线性组合分类器
  • 以该分类器对测试集做预测

从上述可看出，AdaBoost的公式理解比较简单，因此用Python实现也不复杂，如下所示：

class Adaboost:
    def calc_e(self, X, y, i, threshold, orientation, D):
        # 计算错误率和G(x)分类结果
        e = np.ones((X.shape[0],1))
        Gx = np.zeros((X.shape[0],1))
        if orientation == "left":
            Gx[X[:,i] <= threshold] = 1
            Gx[X[:,i] > threshold] = -1
        else:
            Gx[X[:,i] > threshold] = 1
            Gx[X[:,i] <= threshold] = -1
        e[Gx == y] = 0
        # 加权误差weight_e
        weight_e = D * e
        return weight_e, Gx

    def build_stump(self, X, y, D):
        # 设置步长，对于非二值化的数据而言
        numSteps = 4
        # 用于存储决策树桩的一些数据，比如切点、分类方向、加权误差等
        best_stump = {}
        weight_e_min = 1

        for i in range(X.shape[1]):
            X_min = X[:,i].min()
            X_max = X[:,i].max()
            step_size = (X_max-X_min) / numSteps
            for j in range(-1, int(numSteps) + 1):
                for ori in ["left", "right"]:
                    thr = X_min + j * step_size
                    weight_e, Gx = self.calc_e(X, y, i, thr, ori, D)
                    if weight_e < weight_e_min:
                        weight_e_min = weight_e
                        best_stump["e"] = weight_e_min
                        best_stump["threshold"] = thr
                        best_stump["orientation"] = ori
                        best_stump["Gx"] = Gx
                        best_stump["feature"] = i
        return best_stump

    def adaboost_classfier(self, X, y, max_iter = 200):
        m, n = np.shape(X)
        # 初始化样本权值
        D = np.mat([1 / m] * m)
        # 存储每个弱分类器
        weak_classfier = []
        fx = np.mat(np.zeros((m,1)))

        for i in range(max_iter):
            stump = self.build_stump(X, y, D)
            Gx = stump["Gx"]

            # 公式8.2，计算alpha
            alpha = 1/2 * np.log((1 - stump["e"]) / stump["e"])

            # 公式8.4，更新样本权值
            D = np.multiply(D, np.exp(-1 * alpha * np.multiply(y, stump["Gx"]).T))
            D = D / np.sum(D)

            stump["alpha"] = alpha
            weak_classfier.append(stump)

            # 构建线性组合分类器
            fx += np.multiply(alpha, Gx)
            # 计算测试误差，为0则结束迭代
            error = np.sum(np.sign(fx) != y)
            if error == 0: break
        return weak_classfier


def predict(self, X_test, classfier):
    for stump in classfier:
        threshold = stump["threshold"]
        orientation = stump["orientation"]
        feature = stump["feature"]

        if orientation == "left":
            if X_test[:,feature] <= threshold:
                return 1
            else:
                return -1
        else:
            if X_test[:,feature] > threshold:
                return 1
            else:
                return -1

取《统计学习方法习题8.1》为例，用AdaBoost算法学习一个强分类器（从结果中可看出，迭代6次就可以结束了）：

train_X = np.mat([[0.,1.,3.],
                  [0.,3.,1.],
                  [1.,2.,2.],
                  [1.,1.,3.],
                  [1.,2.,3.],
                  [0.,1.,2.],
                  [1.,1.,2.],
                  [1.,1.,1.],
                  [1.,3.,1.],
                  [0.,2.,1.]])
train_y = np.mat([-1.0, -1.0, -1.0, -1.0, -1.0, -1.0, 1.0, 1.0, -1.0, -1.0]).T
adaboost = Adaboost()
tree = adaboost.adaboost_classfier(X=train_X, y=train_y, max_iter = 50)
len(tree)
>>6

此外还有些内容，如Adaboost算法可以利用加性模型的损失函数最小化来推导出来，，有确切的误差界，模型是加法模型，损失函数是指数损失，算法是前向分布算法

为了防止Adaboost过拟合，通常会正则化，在Adaboost中就相当于对每个迭代器加上一个正则化项（步长或者叫学习率Learning rat），为了避免过多的迭代器所造成的过拟合（其实在Adaboost使用中，也可以通过设定弱分类器迭代次数来避免过拟合，这两种方法需要综合权衡考虑），学习率一般设置范围在0-1之间（1就相当于不正则化。。。那么较小的学习率就会使得更多的弱分类器迭代次数）

对于多分类的情况，Adaboost也是可以处理的，只需要将多分类转化为多个二分类问题即可

Adaboost算法优点：分类时精确度很好；可以将不同的分类算法作为弱分类器；相比bagging，其考虑了每个分类器的权重；结果可读可解释；无需调参；不易发生过拟合

缺点：对异常样本非常敏感，因为异常样本会在迭代中获得相对较高的权值；数据不平衡会导致精度下降；因为要循环选择最佳切点，有时会非常耗时

Adaboost入门教程——最通俗易懂的原理介绍（图文实例）
AdaBoost 自适应增强学习算法原理
简单易学的机器学习算法——AdaBoost
机器学习实战之AdaBoost元算法
比较全面的Adaboost算法总结（二）

本文出自于http://www.bioinfo-scrounger.com转载请注明出处

Related Posts