精华内容
下载资源
问答
  • 04-02 AdaBoost算法

    2020-03-03 09:18:47
    文章目录AdaBoost算法AdaBoost算法学习目标AdaBoost算法详解Boosting算法回顾AdaBoost算法AdaBoost算法目标函数优化AdaBoost算法流程输入输出强分类器流程强回归器流程AdaBoost算法优缺点优点缺点小结 AdaBoost算法 ...

    AdaBoost算法

    在这里插入图片描述

      集成学习中弱学习器之间有强依赖关系的,称之为Boosting系列算法,而AdaBoost则是Boosting系列算法中最著名的算法之一。

      AdaBoost算法强大之处在于既可以解决分类问题,又可以解决回归问题。

    AdaBoost算法学习目标

    1. AdaBoost算法目标函数优化
    2. 强分类器和强回归器流程
    3. AdaBoost算法优缺点

    AdaBoost算法详解

    Boosting算法回顾

    在这里插入图片描述

      Boosting算法的流程是:首先训练处一个弱学习器,根据弱学习器的误差率更新训练样本的权重,然后基于调整权重后的训练集训练第二个弱学习器,直到弱学习器达到事先指定的数目T,停止算法。

      对于Boosting算法的流程,可以看到如果我们解决以下4个问题,既可以得到完整的Boosting算法

    1. 弱学习器的误差率
    2. 训练样本的权重 w w w更新方法
    3. 更新样本权重的方法
    4. 结合策略

    AdaBoost算法

      上面讲到了Boosting算法需要解决的4个问题,因为AdaBoost算法隶属于Boosting算法,那么AdaBoost算法也需要解决这4个问题,其实也可以说成只要是Boosting系列的算法,都需要解决这4个问题。

    AdaBoost算法目标函数优化

      AdaBoost算法可以理解成模型是加法模型、目标函数是指数函数、学习算法是前向分步算法时的学习方法。其中加法模型可以理解成强学习器是由之前所有的弱学习器加权平均得到的;前向分步算法则可以理解成弱学习器训练数据的权重通过前一个弱学习器更新。

      AdaBoost算法的模型是加法模型,即强学习器的模型为
    f ( x ) = ∑ k = 1 K α k G k ( x ) f(x) = \sum_{k=1}^K \alpha_kG_k(x) f(x)=k=1KαkGk(x)
    其中 K K K K K K个弱学习器。

      AdaBoost算法的事前向分步算法,即经过 k − 1 k-1 k1次迭代后,第 k − 1 k-1 k1轮后强学习器为
    KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ f_{k-1}(x) & =…
    经过 k k k次迭代后,第 k k k轮后强学习器为
    f k ( x ) = ∑ i = 1 k α i G i ( x ) = f k − 1 ( x ) + α k G k ( x ) f_k(x) = \sum_{i=1}^k \alpha_i G_i(x) = f_{k-1}(x) + \alpha_kG_k(x) fk(x)=i=1kαiGi(x)=fk1(x)+αkGk(x)
      得到第 k k k轮强学习器后,我们知道AdaBoost的目标函数是指数函数,因此我们的目标是使前向分步算法得到的 α k \alpha_k αk G k ( x ) G_k(x) Gk(x)使 f k ( x ) f_k(x) fk(x)在训练数据集上的指数损失最小,即AdaBoost的目标函数为
    KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ (\alpha_k,G_k(…
      由于 e [ − y i ( f k − 1 ( x i ) ) ] e^{[{-y_i(f_{k-1}(x_i))}]} e[yi(fk1(xi))]的值不依赖 α , G \alpha,G α,G,因此他与最小化无关,它仅仅依赖于随着每一轮迭代而变化的 f k − 1 ( x ) f_{k-1}(x) fk1(x),因此可以把 e [ − y i ( f k − 1 ( x i ) ) ] e^{[{-y_i(f_{k-1}(x_i))}]} e[yi(fk1(xi))]看做 w ‾ k i \overline{w}_{ki} wki,即目标函数变为
    ( α k , G k ( x ) ) = arg ⁡   m i n ⏟ α , G ∑ i = 1 m w ‾ k i e [ − y i ( α G ( x i ) ) ] (\alpha_k,G_k(x)) = \underbrace{\arg\,min}_{\alpha,G}\sum_{i=1}^m \overline{w}_{ki} e^{[{-y_i(\alpha{G(x_i)}})]} (αk,Gk(x))=α,G argmini=1mwkie[yi(αG(xi))]
      现在的目标就是最优化AdaBoost的目标函数得到能使目标函数最小化的 α k ∗ \alpha_k^* αk G k ∗ ( x ) G_k^*(x) Gk(x)

      首先,对于任意的 α > 0 \alpha>0 α>0 G k ∗ ( x ) G_k^*(x) Gk(x)表示第 k k k轮能够使得加训练数据分类误差率最小的基本分类器,分类误差率为
    e k = ∑ i = 1 m w ‾ k i I ( y i ≠ G k ( x i ) ) ∑ i = 1 m w ‾ k i = ∑ i = 1 m w ‾ k i I ( y i ≠ G k ( x i ) ) = ∑ y i ≠ G k ( x i ) w ‾ k i e_k = {\frac{\sum_{i=1}^m\overline{w}_{ki}I(y_i\neq{G_k(x_i)})}{\sum_{i=1}^m\overline{w}_{ki}}} = \sum_{i=1}^m\overline{w}_{ki}I(y_i\neq{G_k(x_i)}) = \sum_{{y_i}\neq{G_k(x_i)}}\overline{w}_{ki} ek=i=1mwkii=1mwkiI(yi=Gk(xi))=i=1mwkiI(yi=Gk(xi))=yi=Gk(xi)wki
    G k ∗ ( x ) G_k^*(x) Gk(x)
    G k ∗ ( x ) = a r g   min ⁡ ⏟ G ∑ i = 1 m w ‾ k i I ( y i ≠ G ( x i ) ) G_k^*(x) = \underbrace{arg\,\min}_{G}\sum_{i=1}^m \overline{w}_{ki} I(y_i\neq{G(x_i))} Gk(x)=G argmini=1mwkiI(yi=G(xi))
       G k ∗ ( x ) G_k^*(x) Gk(x)即为学习器的 G k ( x ) G_k(x) Gk(x),把 G k ( x ) G_k(x) Gk(x)代入目标函数对 α \alpha α求导并使导数为0,可以把上述的目标函数优化成
    KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ (\alpha_k,G_k(…
    既得最小的 α \alpha α
    α k ∗ = 1 2 log ⁡ 1 − e k e k \alpha_k^* = {\frac{1}{2}}\log{\frac{1-e_k}{e_k}} αk=21logek1ek
      最后看样本的权重更新,利用 f k ( x ) = f k − 1 ( x ) + α k G k ( x ) f_k(x)=f_{k-1}(x)+\alpha_kG_k(x) fk(x)=fk1(x)+αkGk(x) w ‾ k i = e [ − y i f k − 1 ( x i ) ] \overline{w}_{ki}=e^{[-y_if_{k-1}(x_i)]} wki=e[yifk1(xi)]可得
    KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ \overline{w}_{…
       w ‾ k + 1 , i \overline{w}_{k+1,i} wk+1,i即接下来要讲到的AdaBoost算法的训练数据权重的更新公式。

    AdaBoost算法流程

    在这里插入图片描述
      AdaBoost算法既可以解决分类问题,又可以解决回归问题。对于分类问题,此处我们讲述的AdaBoost算法流程主要是针对二分类问题,二分类问题和多分类问题的区别主要在于弱分类器的系数上,本文会介绍AdaBoost SAMME算法如何计算弱分类器的系数;对于回归问题,由于AdaBoost用来解决回归问题的变种有很多,本文只对AdaBoost R2算法做一个介绍。

    输入

       m m m个样本 n n n个特征的训练数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯   , ( x m , y m ) } T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_m,y_m)\} T={(x1,y1),(x2,y2),,(xm,ym)}

      针对二分类问题, y i ∈ Y = { 1 , − 1 } y_i\in{Y=\{1,-1\}} yiY={1,1}

    输出

      最终强学习器 G ( x ) G(x) G(x)

    强分类器流程

    1. 初始化训练数据的权重
      D 1 = ( w 11 , ⋯   , w 1 i , ⋯   , w 1 m ) , w 1 i = 1 m , i = 1 , 2 , ⋯   , m D_1 = (w_{11},\cdots,w_{1i},\cdots,w_{1m}),\quad{w_{1i}={\frac{1}{m}},\quad{i=1,2,\cdots,m}} D1=(w11,,w1i,,w1m),w1i=m1,i=1,2,,m
    2. 生成弱分类器
      G k ( x ) , k = 1 , 2 , ⋯   , K G_k(x),\quad{k=1,2,\cdots,K} Gk(x),k=1,2,,K
    3. 计算弱分类器 G k ( x ) G_k(x) Gk(x)在训练集上的分类误差率为
      KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ e_k & = \sum_{…
    4. 计算 G k ( x ) G_k(x) Gk(x)的权重系数
      KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ & \alpha_k={\f…
        二分类问题的权重系数中,可以看出如果分类误差率 e k e_k ek越大,则对应的弱分类器的权重系数 α k \alpha_k αk越小,即误差率小的弱分类器权重系数越大。

      多分类问题使用的是AdaBoost SAMME算法,其中 R R R为类别数,如果 R = 2 R=2 R=2,则该多元分类的权重系数将变成二元分类的权重系数。
    5. 更新训练数据的权重
    KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ & D_{k+1} = (w…
      其中 Z k Z_k Zk是规范因子
    Z k = ∑ i = 1 m w k i e − α k y i G k ( x i ) Z_k=\sum_{i=1}^mw_{ki}e^{-\alpha_ky_iG_k(x_i)} Zk=i=1mwkieαkyiGk(xi)
      从 w k + 1 , i w_{k+1,i} wk+1,i的计算公式中可以看出,如果第 i i i个样本分类错误,则 y i G k ( x i ) < 0 y_iG_k(x_i)<0 yiGk(xi)<0,导致样本的权重在第 k + 1 k+1 k+1个弱分类器中变大,反之,则样本权重在第 k + 1 k+1 k+1个弱分类器中变小。
    6. 结合策略
    KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ & f(x)=\sum_{k…

    强回归器流程

    1. 初始化训练数据的权重
      D 1 = ( w 11 , ⋯   , w 1 i , ⋯   , w 1 m ) , w 1 i = 1 m , i = 1 , 2 , ⋯   , m D_1 = (w_{11},\cdots,w_{1i},\cdots,w_{1m}),\quad{w_{1i}={\frac{1}{m}},\quad{i=1,2,\cdots,m}} D1=(w11,,w1i,,w1m),w1i=m1,i=1,2,,m
    2. 生成弱分类器
      G k ( x ) , k = 1 , 2 , ⋯   , K G_k(x),\quad{k=1,2,\cdots,K} Gk(x),k=1,2,,K
    3. 计算弱回归器 G k ( x ) G_k(x) Gk(x)在训练集上的最大误差
      E k = max ⁡ ∣ y i − G k ( x i ) ∣ , i = 1 , 2 , ⋯   , m E_k = \max|y_i-G_k(x_i)|,\quad{i=1,2,\cdots,m} Ek=maxyiGk(xi),i=1,2,,m
    4. 计算每个样本之间的相对误差
      e k i = ∣ y i − G k ( x i ) ∣ E k e_{ki}={\frac{|y_i-G_k(x_i)|}{E_k}} eki=EkyiGk(xi)
        此处也可以使用均方误差,即 e k i = ( y i − G k ( x i ) ) 2 E k 2 e_{ki}={\frac{(y_i-G_k(x_i))^2}{E_k^2}} eki=Ek2(yiGk(xi))2
    5. 计算第 k k k弱回归器的误差率和权重系数
      KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ & e_k = \sum_{…
    6. 更新训练数据的权重
      w k + 1 , i = w k i Z k α k 1 − e k i w_{k+1,i} = {\frac{w_{ki}}{Z_k}\alpha_k^{1-e_{ki}}} wk+1,i=Zkwkiαk1eki
        其中 Z k Z_k Zk是规范因子
      Z k = ∑ i = 1 m w k i α k 1 − e k i Z_k = \sum_{i=1}^m w_{ki}\alpha_k^{1-e_{ki}} Zk=i=1mwkiαk1eki
    7. 结合策略
      G ( x ) = G k ∗ ( x ) G(x) = G_{k^*}(x) G(x)=Gk(x)
        其中 G k ∗ ( x ) G_{k^*}(x) Gk(x)是所有 ln ⁡ 1 α k , k = 1 , 2 , ⋯   , K \ln{\frac{1}{\alpha_k}},\quad{k=1,2,\cdots,K} lnαk1,k=1,2,,K的中位数对应序号 k ∗ k^* k对应的弱回归器

    AdaBoost算法优缺点

    优点

    1. 不容易过拟合
    2. 分类精准度高
    3. 由于弱分类器既可以是分类器又可以是回归器,使用灵活

    缺点

    1. 由于是对训练数据加权,有可能会赋予训练数据中的异常值较高的权重,影响模型的准确度

    小结

      AdaBoost算法并没有使用较深的数学知识,而是推导过程涉及较为复杂的逻辑。如果看完一遍还不是很理解,需要自己多多揣摩。

      AdaBoost算法目前是一个比较流行的Boosting算法,他的弱学习器既可以是回归器,又可以是分类器,这也是AdaBoost较为强大的一点。虽然理论上任何学习器都可以作为AdaBoost的弱学习器,但是AdaBoost算法用的较多的弱学习器一般还是决策树和神经网络。

      相信有了第一个集成算法AdaBoost的基础,对于接下来的第二个用的较为广泛的Boosting系列算法你也能很快熟悉他,即梯度提升树(gradient boosting decision tree,GBDT)

    在这里插入图片描述

    展开全文
  • AdaBoost算法

    2016-12-27 09:51:15
    AdaBoost算法AdaBoost算法 算法概述 AdaBoost算法流程 示例代码 算法特点算法概述将不同分类器组合起来,这种组合结果被称为集成方法或者元算法。使用集成方法会有多种形式:可以是不同算法的集成,也可以是同一算法...

    AdaBoost算法

    算法概述

    将不同分类器组合起来,这种组合结果被称为集成方法或者元算法。使用集成方法会有多种形式:可以是不同算法的集成,也可以是同一算法在不同设置下的集成,也可以是数据集不同部分分配给不同分类器之后的集成。boosting 是通过关注被已有分类器错分那些数据获得新的分类器,其中最流行的boosting算法为AdaBoost算法。

    AdaBoost算法流程

    算法描述

    1. 给定训练样本 (x1,y1),...(xi,yi)...(xm,ym) 其中 xi 表示第 i 个样本, 表示为负样本, 表示为正样本。m为训练样本总数
    2. 初始化训练样本的权重( 1m )
    3. 第一次循环,首先训练一个弱分类器,计算该分类器的错误率;更改阈值使得错误率最低,更行样本权重
    4. 经过T次循环,得到T个弱分类器,根据每个分类器正确分类的贡献作为权重进行加权组合,最后得到强分类器。

    算法示意图

    AdaBoost算法示意图

    算法流程
    训练了T个弱分类器 ht,t{1,...,T} 。这些分类器很简单。大多数情况是只包含一次分裂的决策树。最后做决定的时候将赋值权重 αt 给每个分类器。输入特征向量为 xi ,类别标签为 yi,i{1,..m} ,且 yi{1,1} 。首先初始化样本全职 Dt(i) 来告诉分类器将一个数据点分类错误的代价是多少。

    1. D1(i)=1/m,i=1,...,m
    2. 针对 t=1,...,T :
      a. 寻找是的权重为 Dt(i) 的总错误最小的分类器 ht
      b.求 ht=argminhjHεj εj=mi=1Dt(i) (其中 yihj(xi) ),如果最小错误满足 ε<0.5 则继续;否则退出
      c. 设置 ht 的权重 αt=log[(1εt)/εt] ,这儿 εt 为步骤2b中的最小错误
      d. 更新数据点权重: Dt+1(i)=[Dt(i)e(αtyiht(xi))]/Zt ,这 Zt 将所有数据点权重归一化
    3. 算法结束后,最后的强分类器几首输入向量 x ,使用所有弱分类器的加权和进行分类
      H(x)=sign(t=1Tαtht(x))

    示例代码

    '''
    Created on Dec 26th
    Adaboost is short for Adaptive Boosting
    @author: zfluo
    '''
    from numpy import *
    def loadSimpData():
        datMat = matrix([[1., 2.1],
                        [2., 1.1],
                        [1.3, 1.],
                        [1., 1.],
                        [2., 1.]])
        classLabels = [1.0, 1.0, -1.0, -1.0, -1.0]
        return datMat, classLabels
    
    # 构建单层决策树, lt: less than, gt: greater than
    def stumpClassify(dataMatrix, dimen, threshVal, threshIneq):
        retArray = ones((shape(dataMatrix)[0], 1))
        if threshIneq == 'lt':
            retArray[dataMatrix[:, dimen] <= threshVal] = -1.0
        else:
            retArray[dataMatrix[:, dimen] > threshVal] = -1.0
        return retArray
    
    # 寻找最优分支
    def buildStump(dataArr, classLabels, D):
        dataMatrix = mat(dataArr)
        labelMat = mat(classLabels).T
        m, n = shape(dataMatrix)
        numSteps = 10.0; bestStump = {}; bestClasEst = mat(zeros((m, 1)))
        minError = inf
        for i in range(n):
            rangeMin = dataMatrix[:, i].min()
            rangeMax = dataMatrix[:, i].max()
            stepSize = (rangeMax - rangeMin)/numSteps
            for j in range(-1, int(numSteps) + 1):
                for inequal in ['lt', 'gt']:
                    threshVal = (rangeMin + float(j)*stepSize)
                    predictedVals = stumpClassify(dataMatrix, i, threshVal, inequal)
                    errArr = mat(ones((m, 1)))
                    errArr[predictedVals == labelMat] = 0
                    weightedError = D.T*errArr
                    # print('split: dim %d, thresh %.2f, thresh ineqal: %s, the weighted error is %.3f' %
                    #       (i, threshVal, inequal, weightedError))
                    if weightedError < minError:
                        minError = weightedError
                        bestClasEst = predictedVals.copy()
                        bestStump['dim'] = i
                        bestStump['thresh'] = threshVal
                        bestStump['ineq'] = inequal
        return bestStump, minError, bestClasEst
    
    # AdaBoost训练
    def adaBoostTrainDS(dataArr, classLabels, numIt = 40):
        weakClassArr = []
        m = shape(dataArr)[0]
        D = mat(ones((m, 1))/m)
        aggClassEst = mat(zeros((m,1)))
        for i in range(numIt):
            bestStump, error, classEst = buildStump(dataArr, classLabels, D)
            print('D:', D.T)
            alpha = float(0.5*log((1.0 - error)/max(error, 1e-16)))
            bestStump['alpha'] = alpha
            weakClassArr.append(bestStump)
            print('classEst: ', classEst.T)
            expon = multiply(-1*alpha*mat(classLabels).T, classEst)
            D = multiply(D, exp(expon))
            D = D/D.sum()
            aggClassEst += alpha*classEst
            print('aggClassEst: ', aggClassEst.T)
            aggErrors = multiply(sign(aggClassEst)!= mat(classLabels).T, ones((m, 1)))
            errorRate = aggErrors.sum()/m
            print('total error: ', errorRate, '\n')
            if errorRate == 0.0:
                break
        return weakClassArr, aggClassEst
    
    # AdaBoost分类
    def adaClassify(datToClass, classifierArr):
        dataMatrix = mat(datToClass)
        m = shape(dataMatrix)[0]
        aggClassEst = mat(zeros((m, 1)))
        for i in range(len(classifierArr)):
            classEst = stumpClassify(dataMatrix, classifierArr[i]['dim'], \
                                     classifierArr[i]['thresh'],  \
                                     classifierArr[i]['ineq'])
            aggClassEst += classifierArr[i]['alpha']*classEst
            print(aggClassEst)
        return sign(aggClassEst)
    
    def loadDataSet(fileName):
        numFeat = len(open(fileName).readline().split('\t'))
        dataMat = []; labelMat = []
        fr = open(fileName)
        for line in fr.readlines():
            lineArr = []
            curLine = line.strip().split('\t')
            for i in range(numFeat - 1):
                lineArr.append(float(curLine[i]))
            dataMat.append(lineArr)
            labelMat.append(float(curLine[-1]))
        return dataMat, labelMat
    
    # 绘制ROC曲线及AUC计算函数
    def plotROC(preStrengths, classLabels):
        import matplotlib.pyplot as plt
        cur = (1.0, 1.0)
        ySum = 0.0
        numPosClas = sum(array(classLabels) == 1.0)
        yStep = 1/float(numPosClas)
        xStep = 1/float(len(classLabels) - numPosClas)
        sortedIndicies = preStrengths.argsort()
        fig = plt.figure()
        fig.clf()
        ax = plt.subplot(111)
        for index in sortedIndicies.tolist()[0]:
            if classLabels[index] == 1.0:
                delX = 0; delY = yStep
            else:
                delX = xStep; delY = 0
                ySum += cur[1]
            ax.plot([cur[0], cur[0] - delX], [cur[1], cur[1] - delY], c = 'b')
            cur = (cur[0] - delX, cur[1] - delY)
        ax.plot([0, 1], [0, 1], 'b--')
        plt.xlabel('False Positive Rate')
        plt.ylabel('True Positive Rate')
        ax.axis([0, 1, 0, 1])
        plt.show()
        print('the Area Under the Curve is:', ySum*xStep)

    这里写图片描述

    AdaBoost识别结果ROC曲线

    算法特点

    优点: 泛化错误率低,易编码,适用于大部分分类器,误参数调整
    缺点: 对离群点敏感
    使用数据类型:数值型和标称型

    展开全文
  • AdaBoost 算法

    2020-02-06 19:30:38
    AdaBoost 算法 是一种经典的集成学习算法,它将多个弱分类器集成起来,以达到较高的分类准确率,广泛应用于数据分类、人脸检测等应用中。尤其在人脸检测方面,AdaBoost 是非常经典、成功的一个算法。弱分类器被线性...

            AdaBoost 算法 是一种经典的集成学习算法,它将多个弱分类器集成起来,以达到较高的分类准确率,广泛应用于数据分类、人脸检测等应用中。尤其在人脸检测方面,AdaBoost 是非常经典、成功的一个算法。弱分类器被线性组合成为一个强分类器。

    一、面临两个问题:

    1. 在每一轮,如何改变训练数据的概率分布或者权值分布。
    2. 如何将弱分类器组合成强分类器。

    二、AdaBoost 的思路:

    1. 提高那些被前一轮弱分类器错误分类样本的权值,降低那些被正确分类的样本的权值。
    2. 采用加权多数表决。具体的,加大分类错误率低的分类器的权值,使其在表决中起较大作用,减少分类误差率大的弱分类器的权值,使其在表决中起较小作用。

    三、训练目标:

    最小化指数损失函数。

    四、三部分组成:

    1. 初始化训练数据的权值分布。如果有N个样本,则每一个训练样本最开始时都被赋予相同的权值:1/N。
    2. 训练弱分类器。具体训练过程中,如果某个样本点已经被准确地分类,那么在构造下一个训练集中,它的权值就被降低;相反,如果某个样本点没有被准确地分类,那么它的权值就得到提高。然后,权值更新过的样本集被用于训练下一个分类器,整个训练过程如此迭代地进行下去。
    3. 将各个训练得到的弱分类器组合成强分类器。各个弱分类器的训练过程结束后,加大分类误差率小的弱分类器的权重,使其在最终的分类函数中起着较大的决定作用,而降低分类误差率大的弱分类器的权重,使其在最终的分类函数中起着较小的决定作用。换言之,误差率低的弱分类器在最终分类器中占的权重较大,否则较小。

    五、具体步骤:

    输人参数:e是预测误差,m 是需要构建的单决策器的个数,如:

    if(x < 3 )
        y ﹦1
    else
        y =-1

    就是一个简单的单决策器,基于x 预测y。α是每个单决策器的不同权重。n 是数据集中点的个数。

    W = [ 1/n,1/n,…,1/n ]   # W是一个数组,表示每个数据点的权重,初始相同

    C = {};  # C 是一个集合,存放每次循环得到的最佳单决策器

    For i = 1 : m

    1) 在当前的权重W 下,尝试各种不同的单决策器,直到找到预测误差最小的那个单决策器Hi(针对所有数据),使得误分的数据点的权重之和最小。对Hi预测错误的数据点,计算这些点的权重之和εi;

    2) C ﹦C 与 Hi 的并集;

    3) 计算分类器的权重αi, αi = 1/2 *log((1-εi + /εi) ;

    4) 更新W 数组,

        w_right = exp( - αi) ,w_wrong = exp( αi) ; # exp 是自然对数

        预测正确的数据点,原始权重乘以w_right;

        预测错误的数据点,原始权重乘以w_rong;

    5) W = W/sum(W) ;    # 规范化W,规范化之后,使各元素之和为1

    6) 对C 中保留的所有分类器,集成决策器为:H_all = α1 * H1 + …αi* Hi

    7)使用H_all对所有数据点再次预测,如果 H_a11 预测的误差e为0 或小于某个阈值,终止 for 循环;否则继续 for 循环。

    六、AdaBoost的优缺点

    1、AdaBoost算法优点

    1. 在Adaboost的框架下,可以使用各种回归分类模型来构建弱学习器,非常灵活。
    2. AdaBoost具有很高的精度,训练误差以指数速率下降。
    3. 相对于bagging算法和Random Forest算法,AdaBoost充分考虑的每个分类器的权重。

    2、Adaboost算法缺点

    1. AdaBoost迭代次数也就是弱分类器数目不太好设定,可以使用交叉验证来进行确定。
    2. 数据不平衡导致分类精度下降。
    3. 训练比较耗时,每次重新选择当前分类器最好切分点。
    4. 对异常样本敏感,异常样本在迭代中可能会获得较高的权重,影响最终的强学习器的预测准确性。

    3、AdaBoost应用领域

    1. 模式识别、计算机视觉领域,用于二分类和多分类场景
    2.  

    参考:

    展开全文
  • 一.简略介绍 GBDT(Gradient Boosting Decision Tree)又叫 MART...GBDT主要由三个概念组成:RegressionDecistionTree(即DT),GradientBoosting(即GB),Shrinkage(算法的一个重要演进分枝,目前大部分源码都按...

    一.简略介绍

    GBDT(Gradient Boosting Decision Tree)又叫 MART(Multiple Additive Regression Tree),是一种迭代的决策树算法。GBDT主要由三个概念组成:Regression Decistion Tree(即DT)Gradient Boosting(即GB)Shrinkage (算法的一个重要演进分枝,目前大部分源码都按该版本实现)。搞定这三个概念后就能明白GBDT是如何工作的,要继续理解它如何用于搜索排序则需要额外理解RankNet概念,之后便功德圆满。sklearn中GBDT文档 scikit-learn地址

    1 .DT:回归树 Regression Decision Tree

    GBDT 中的树全部都是回归树,核心就是累加所有树的结果作为最终结果。只有回归树的结果累加起来才是有意义的,分类的结果累加是没有意义的。

    GBDT 调整之后可以用于分类问题,但是内部还是回归树。

    这部分和决策树中的是一样的,无非就是特征选择。回归树用的是最小化均方误差,分类树是用的是最小化基尼指数(CART)

    提起决策树(DT, Decision Tree) 绝大部分人首先想到的就是C4.5分类决策树。但如果一开始就把GBDT中的树想成分类树,那就是一条歪路走到黑,一路各种坑,最终摔得都要咯血了还是一头雾水说的就是LZ自己啊有木有。咳嗯,所以说千万不要以为GBDT是很多棵分类树。决策树分为两大类,回归树和分类树。前者用于预测实数值,如明天的温度、用户的年龄、网页的相关程度;后者用于分类标签值,如晴天/阴天/雾/雨、用户性别、网页是否是垃圾页面。这里要强调的是,前者的结果加减是有意义的,如10岁+5岁-3岁=12岁,后者则无意义,如男+男+女=到底是男是女? GBDT的核心在于累加所有树的结果作为最终结果,就像前面对年龄的累加(-3是加负3),而分类树的结果显然是没办法累加的,所以GBDT中的树都是回归树,不是分类树,这点对理解GBDT相当重要(尽管GBDT调整后也可用于分类但不代表GBDT的树是分类树)。那么回归树是如何工作的呢?

    2.GB:梯度迭代 Gradient Boosting

    从GradientDescend到GradientBoosting


    首先 Boosting 是一种集成方法。通过对弱分类器的组合得到强分类器,他是串行的,几个弱分类器之间是依次训练的。GBDT 的核心就在于,每一颗树学习的是之前所有树结论和的残差。

    Gradient 体现在:无论前面一颗树的 cost function 是什么,是均方差还是均差,只要它以误差作为衡量标准,那么残差向量都是它的全局最优方向,类似于求梯度,这就是 Gradient

     

    3. Shrinkage

    Shrinkage(缩减)是 GBDT 算法的一个重要演进分支,目前大部分的源码都是基于这个版本的。

    核心思想在于:Shrinkage 认为每次走一小步来逼近结果的效果,要比每次迈一大步很快逼近结果的方式更容易防止过拟合。

    也就是说,它不信任每次学习到的残差,它认为每棵树只学习到了真理的一小部分,累加的时候只累加一小部分,通过多学习几棵树来弥补不足。每一步的残差计算其实变相的增大了分错样本的权重,而已经分对的样本则都趋向于 0。这样后面就更加专注于那些分错的样本。

    没用Shrinkage时:(yi表示第i棵树上y的预测值, y(1~i)表示前i棵树y的综合预测值)

    y(i+1) = 残差(y1~yi), 其中: 残差(y1~yi) =  y真实值 - y(1 ~ i)

    y(1 ~ i) = SUM(y1, ..., yi)

    Shrinkage不改变第一个方程,只把第二个方程改为: 

    y(1 ~ i) = y(1 ~ i-1) + step * yi

    具体的做法就是:仍然以残差作为学习目标,但是对于残差学习出来的结果,只累加一小部分(step* 残差)逐步逼近目标,step 一般都比较小 0.01-0.001, 导致各个树的残差是渐变而不是陡变的。

    本质上,Shrinkage 为每一颗树设置了一个 weight,累加时要乘以这个 weight,但和 Gradient 没有关系。

    这个 weight 就是 step。跟 AdaBoost 一样,Shrinkage 能减少过拟合也是经验证明的,目前还没有理论证明。

    具体的公式:

    4.其他

    算法的整体流程:

    在这里插入图片描述

    终止条件

    • 树的节点数
    • 树的深度
    • 没有适合分割的节点

    特征值排序

    在对每个节点进行分割的时候,首先需要遍历所有的特征,然后对每个样本的特征的值进行枚举计算。(CART)
    在对单个特征量进行枚举取值之前,我们可以先将该特征量的所有取值进行排序,然后再进行排序。
    优点
    避免计算重复的value值
    方便更佳分割值的确定
    减少信息的重复计算

    多线程/MPI并行化的实现

    通过MPI实现对GBDT的并行化,最主要的步骤是在建树的过程中,由于每个特征值计算最佳分割值是相互独立的,故可以对特征进行平分,再同时进行计算。

    二.GBDT 适用场景

    GBDT 可以适用于回归问题(线性和非线性);

    GBDT 也可用于二分类问题(设定阈值,大于为正,否则为负)和多分类问题。

    三.GBDT的优缺点

    GBDT主要的优点有:

        1) 可以灵活处理各种类型的数据,包括连续值和离散值。

        2) 在相对少的调参时间情况下,预测的准备率也可以比较高。这个是相对SVM来说的。

        3)使用一些健壮的损失函数,对异常值的鲁棒性非常强。比如 Huber损失函数和Quantile损失函数。

                   4) 很好的利用了弱分类器进行级联。

                   5) 充分考虑的每个分类器的权重。

    GBDT的主要缺点有:

        1)由于弱学习器之间存在依赖关系,难以并行训练数据。不过可以通过自采样的SGBT来达到部分并行。
     

    其他.面试常问GBDT相关

    1. 怎么设置单棵树的停止生长条件?

    设置参数:

    • 节点分裂时的最小样本数;min_samples;
    • 最大深度:max_depth;
    • 最多叶子节点数:max_leaf_nodes;
    • loss满足约束条件。

    2. 如何评估特征的权重大小?

    (1)计算每个特征在训练集下的特征增益,与所有特征的信息增益之和的比例为权重值。
    (2)借鉴投票机制。用相同的参数对 w 每个特征训练一个模型,计算各模型下每个特征正确分类的个数,每个特征正确分类个数与所有正确分类个数之和的比例为权重值。

    3. --当增加样本数量时,训练时长是线性增加的吗?

    不是,因为生成单棵决策树时,需要选择最佳分裂点,以拟合残差,寻找最优的拟合值,而这个运算与样本个数N不是线性相关的。

    4. --当增加树的颗数时,训练时长是线性增加的吗?

    不是,因为每棵树生成的时间复杂度不同。
    叶子节点数和每棵树的生成时间复杂度也不成正比。

    5. 每个节点上保存什么信息?

    树的中间节点保存某个特征的分割值,叶节点保存预测时某个类别的概率

    6.如何防止过拟合?

    (1)增加样本,移除噪声
    (2)减少特征,保留重要的特征;
    (3)对样本进行采样,建树的时候,选择一个子集(GBDT特有的方法,是无放回抽样);每一个子树都采用这个样本子集进行拟合。

    7. gbdt 在训练和预测的时候都用到了步长,这两个步长一样么?

    (1)这两个步长一样么?答:训练跟预测时,两个步长是一样的,也就是预测时的步长为训练时的步长,从训练的过程可以得知(更新当前迭代模型的时候)。
    (2)都有什么用,如果不一样,为什么?答:它的作用就是使得每次更新模型的时候,使得loss能够平稳地沿着负梯度的方向下降,不至于发生震荡
    (3)那么怎么设步长的大小?
    答:有两种方法,一种就是按策略来决定步长,另一种就是在训练模型的同时,学习步长
    A. 策略:
    a 每个树步长恒定且相等,一般设较小的值;
    b 开始的时候给步长设一个较小值,随着迭代次数动态改变或者衰减
    B. 学习:
    因为在训练第k棵树的时候,前k-1棵树时已知的,而且求梯度的时候是利用前k-1棵树来获得。所以这个时候,就可以把步长当作一个变量来学习。
    (4)(太小?太大?)在预测时,对排序结果有什么影响?
    答:如果步长过大,在训练的时候容易发生震荡,使得模型学不好,或者完全没有学好,从而导致模型精度不好
    而步长过小,导致训练时间过长,即迭代次数较大,从而生成较多的树,使得模型变得复杂,容易造成过拟合以及增加计算量
    不过步长较小的话,使训练比较稳定,总能找到一个稳定的局部最优解
    个人觉得过大过小的话,模型的预测值都会偏离真实情况(可能比较严重),从而导致模型精度不好。
    (5)跟shrinking里面的步长一样么?答:这里的步长跟shrinking里面的步长是一致的。

    8. gbdt中哪些部分可以并行?

    A. 计算每个样本的负梯度
    B. 分裂挑选最佳特征及其分割点时,对特征计算相应的误差及均值时
    C. 更新每个样本的负梯度
    D. 最后预测过程中,每个样本将之前的所有树的结果累加的时候

     

    GBDT 的调参

    参数说明(sklearn)
    n_estimators:控制弱学习器的数量
    max_depth:设置树深度,深度越大可能过拟合
    max_leaf_nodes:最大叶子节点数
    learning_rate:更新过程中用到的收缩步长,(0, 1]
    max_features:划分时考虑的最大特征数,如果特征数非常多,我们可以灵活使用其他取值来控制划分时考虑的最大特征数,以控制决策树的生成时间。
    min_samples_split:内部节点再划分所需最小样本数,这个值限制了子树继续划分的条件,如果某节点的样本数少于min_samples_split,则不会继续再尝试选择最优特征来进行划分。
    min_samples_leaf:叶子节点最少样本数,这个值限制了叶子节点最少的样本数,如果某叶子节点数目小于样本数,则会和兄弟节点一起被剪枝。
    min_weight_fraction_leaf:叶子节点最小的样本权重和,这个值限制了叶子节点所有样本权重和的最小值,如果小于这个值,则会和兄弟节点一起被剪枝。
    min_impurity_split:节点划分最小不纯度,使用 min_impurity_decrease 替代。
    min_impurity_decrease:如果节点的纯度下降大于了这个阈值,则进行分裂。
    subsample:采样比例,取值为(0, 1],注意这里的子采样和随机森林不一样,随机森林使用的是放回抽样,而这里是不放回抽样。如果取值为1,则全部样本都使用,等于没有使用子采样。如果取值小于1,则只有一部分样本会去做 GBDT 的决策树拟合。选择小于1的比例可以减少方差,即防止过拟合,但是会增加样本拟合的偏差,因此取值不能太低,一般在 [0.5, 0.8] 之间。

     

    CART回归树如何进行回归?

    第一步是遍历特征和切分点,找到分裂后左右节点MSE最小(即分裂后混程度最低)的特征和切分点;
    第二步以该特征和切分点进行分裂,计算输出值;
    重复上述步骤,直至达到停止条件(混乱程度小于一定数值、树深达到要求)
    生成决策树。

    关于损失函数的选取

    在回归问题中,LossFunction一般会选取MSE;而在二分类问题中,损失函数一般是LogLoss,在多分类问题上,损失函数则会是指数损失。

    关于分类与回归的区别

    1.分类和回归时,损失函数是不同的
    2.回归时,第一棵树直接通过标签真实值来训练;而在分类时,需要将真实值进行sigmoid映射。
     

    RF与GBDT之间的区别与联系?

    1)相同点:

    都是由多棵树组成

    最终的结果都由多棵树共同决定。

    2)不同点:

    a 组成随机森林的树可以分类树也可以是回归树,而GBDT只由回归树组成

    b 组成随机森林的树可以并行生成(Bagging);GBDT 只能串行生成(Boosting);这两种模型都用到了Bootstrap的思想。

    c 随机森林的结果是多数表决表决的,而GBDT则是多棵树加权累加之和

    d 随机森林对异常值不敏感,而GBDT对异常值比较敏感

    e 随机森林是减少模型的方差,而GBDT是减少模型的偏差

    f 随机森林不需要进行特征归一化。而GBDT则需要进行特征归一化

    g随机森林对训练集一视同仁权值一样,GBDT是基于权值的弱分类器的集成 

    xgboost/gbdt在调参时为什么树的深度很少就能达到很高的精度?

    现象:xgboost/gbdt仅仅用梯度上升法就能用6个节点的深度达到很高的预测精度,DecisionTree/RandomForest的时候需要把树的深度调到15或更高。(xgb倾向于先解决50%的问题,在解决25%的问题,再解决10%的问题,慢慢逼近解)

    答:Boosting主要关注降低偏差,因此Boosting能基于泛化性能相当弱的学习器构建出很强的集成;Bagging主要关注降低方差,因此它在不剪枝的决策树、神经网络等学习器上效用更为明显。

    其实就机器学习算法来说,其泛化误差可以分解为两部分,偏差(bias)和方差(variance)。这个可由下图的式子导出(这里用到了概率论公式D(X)=E(X2)-[E(X)]2)。偏差指的是算法的期望预测与真实预测之间的偏差程度,反应了模型本身的拟合能力;方差度量了同等大小的训练集的变动导致学习性能的变化,刻画了数据扰动所导致的影响。这个有点儿绕,不过你一定知道过拟合。

    如下图所示,当模型越复杂时,拟合的程度就越高,模型的训练偏差就越小。但此时如果换一组数据可能模型的变化就会很大,即模型的方差很大。所以模型过于复杂的时候会导致过拟合。

    当模型越简单时,即使我们再换一组数据,最后得出的学习器和之前的学习器的差别就不那么大,模型的方差很小。还是因为模型简单,所以偏差会很大。

    Adaboosting和gbdt的区别

    GBDT不是Adaboost Decistion Tree。就像提到决策树大家会想起C4.5,提到boost多数人也会想到Adaboost。Adaboost是另一种boost方法,它按分类对错,分配不同的weight,计算cost function时使用这些weight,从而让“错分的样本权重越来越大,使它们更被重视”。Bootstrap也有类似思想,它在每一步迭代时不改变模型本身,也不计算残差,而是从N个instance训练集中按一定概率重新抽取N个instance出来(单个instance可以被重复sample),对着这N个新的instance再训练一轮。由于数据集变了迭代模型训练结果也不一样,而一个instance被前面分错的越厉害,它的概率就被设的越高,这样就能同样达到逐步关注被分错的instance,逐步完善的效果。Adaboost的方法被实践证明是一种很好的防止过拟合的方法,但至于为什么则至今没从理论上被证明。GBDT也可以在使用残差的同时引入Bootstrap re-sampling,GBDT多数实现版本中也增加的这个选项,但是否一定使用则有不同看法。re-sampling一个缺点是它的随机性,即同样的数据集合训练两遍结果是不一样的,也就是模型不可稳定复现,这对评估是很大挑战,比如很难说一个模型变好是因为你选用了更好的feature,还是由于这次sample的随机因素。

    Adaboosting算法流程:

     

    参考链接:

    1.主讲gbdt原理:https://blog.csdn.net/qq_19446965/article/details/82079624?depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1&utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1

    2.参数空间和函数空间区别:https://www.jianshu.com/p/6075922a8bc3

    3.gbdt的一些介绍:https://blog.csdn.net/qq_19446965/article/details/82079624

    4.雪伦的介绍:https://blog.csdn.net/a819825294/article/details/51188740

    5.https://blog.csdn.net/Daverain/article/details/96702696

    展开全文
  • Adaboost算法

    2020-08-21 15:44:05
    Adaboost的学习内容整理自菊安酱小姐姐的直播视频,原视频链接:【菊安酱的机器学习】第6期 Adaboost算法,小姐姐还有完整的一系列机器学习视频课程,感兴趣的可以去看看。 Adaboost也属于集成学习,随机森林那里...
  • Adaboost 算法总结

    2017-06-22 18:11:17
    Adaboost 算法实例解析 1 Adaboost的原理 1.1 Adaboost基本介绍  AdaBoost,是英文"Adaptive Boosting"(自适应增强)的缩写,由Yoav Freund和Robert Schapire在1995年提出。Adaboost是一种迭代算法,其...
  • adaboost算法

    2017-04-25 20:46:00
     在介绍adaboost之前有必要先介绍一下,bagging和boosting算法。  bagging,即可以称之为自举汇聚算法也可以称之为基于数据随机重抽样算法。它的原理就是从原始数据集中,随机抽样出S个和原数据集大小相等的新...
  • Adaboost算法原理分析

    2018-08-13 13:18:14
    Adaboost算法原理分析和实例+代码(简明易懂)  转自 http://blog.csdn.net/guyuealian/article/details/70995333  本人最初了解AdaBoost算法着实是花了几天时间,才明白他的基本原理。也许是自己能力有限吧,很...
  • Adaboost算法+python源码

    2021-09-26 20:17:30
    AdaBoost算法(Adaptive Boosting)是一种有效而实用的Boosting算法,它以一种高度自适应的方法顺序地训练弱学习器。AdaBoost根据前一次的分类效果调整数据的权重,上一个弱学习器中错误分类样本的权重会在下一个弱...
  • Adaboost 算法实例解析

    千次阅读 2016-05-26 21:04:06
    目录(?)[+]  Adaboost 算法实例解析 ... Adaboost的原理 ... Adaboost基本介绍 ... AdaBoost,是英文"Adaptive Boosting"(自适应增强)的缩写,由Yoav Freund和Robert ...Adaboost是一种迭代算法,其核心思想是针对同
  • 机器学习(9): Adaboost算法 小结及实验

    千次阅读 2019-07-24 21:12:51
    文章目录1 Adaboost算法简介2 集成学习2.1 集成学习概念2.2 bagging2.3 boosting2.4 bagging与boosting的区别2.5 组合策略(1) 平均法(2) 投票法(3) 学习法3 Adaboost 算法4 实验实验1 基于单层决策树构建弱分类器...
  • AdaBoost算法原理及实例 Adaboost相关函数 弱分类器的误差率 ek=P(Gk(xi)≠yi)=∑i=1mwkiI(Gk(xi)≠yi) e_{k}=P\left(G_{k}\left(x_{i}\right) \neq y_{i}\right)=\sum_{i=1}^{m} w_{k i} I\left(G_{k}\left(x_{i}...
  • 目录boost算法问题描述Adaboost 算法基本思路传送门 boost算法问题描述 1 如何计算学习误差率e 2 如何得到弱学习器权重系数α 3 如何更新样本权重D 4 使用何种结合策略 ...集成学习之Adaboost算法原理小结 ...
  • 在机器学习算法中,有一种算法叫做集成算法AdaBoost 算法是集成算法的一种,由Freund 等人于1995 年提出。
  • 0 前言 本人计算机研二,专业带队数学建模,长期更新建模教学,有需要的同学欢迎讨论~ 本篇文章,本系列学长讲解一部分数学...前面已经介绍过许多算法,每种算法都有优缺点。那么是否可以将这些算法组合起来,共同做
  • Adaboost算法介绍

    2019-06-13 11:31:38
    1. 集成学习(ensemble learing)背景介绍 集成学习(ensemble learing)通过构建并结合多个学习器(learner)来完成学习任务,通常...另一类是以boosting、Adaboost算法为代表的,个体学习器是串行序列化生成的...
  • AdaBoost算法详细介绍

    万次阅读 2018-04-06 14:11:15
    一、Boosting算法Boosting集成分类器包含多个非常简单的成员分类器,这些成员分类器的性能仅好于随机猜想,常被称为弱学习机。典型的弱学习机的例子就是单层决策树。Boosting算法主要针对难以区分的样本,弱学习机...
  • Adaboost 算法介绍 1. Adaboost简介 1.1 集成学习(ensemble learning)背景介绍 集成学习(ensemble learning)通过构建并结合多个学习器(learner)来完成学习任务,通常可获得比单一学习器更良好的泛化性能(特别...
  • 常见分类算法优缺点

    千次阅读 2018-10-21 21:36:54
    本文主要回顾下几个常用算法的适应场景及其优缺点! 机器学习算法太多了,分类、回归、聚类、推荐、图像识别领域等等,要想找到一个合适算法真的不容易,所以在实际应用中,我们一般都是采用启发式学习方式来实验。...
  • AdaBoost算法理解

    2020-01-06 16:05:49
    AdaBoost的前身和今世 强可学习和弱可学习 在概率近似正确(PAC)学习框架中, 一个类如果存在: 一个多项式复杂度的学习算法,正确率略大于随机猜测(例如二分类问题中大于1/2),称弱可学习的 一个多项式复杂度的学习...
  •  接自https://blog.csdn.net/Y_hero/article/details/88381259 ,由上一篇总结我们已经初步了解了集成学习以及Boosting的基本原理,不过有几个Boosting具体的问题没有详细...只要是boosting大家族的算法,都要解决这...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,479
精华内容 2,591
关键字:

adaboost算法优缺点