统计学习方法-AdaBoost笔记

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转载请注明出处