机器学习之AdaBoost

发表于 | 分类于 | 浏览 次
| 字数统计: 1,776 字 | 阅读时长 ≈ 8 分钟

分类、集成、属于Boosting

什么是Boosting？

Boosting是一种广泛应用的集成学习框架，该框架一般的训练过程是依次训练基础模型，并在训练过程中对训练集不断地进行调整，也即当前训练所用的训练集由前一次训练的训练集根据某些策略调整得到，最后将所有基础模型组合起来即为最终得到的模型。

监督学习最优方法之一

AdaBoost算法是模型为加法模型、损失函数为指数函数、学习算法为向前同步算法时的二类分类学习方法。

优点：泛化错误率低，易编码，可以应用到大部分分类器上，少参数调整。

缺点：对离群点敏感。

适用数据类型：数值型和标称型数据 / 二分类问题、多分类问题、回归问题

概念

  • 强可学习

    在概率近似正确学习的框架中，一个概念（类），如果存在一个多项式的学习算法能够学习它，并且正确率很高。

  • 弱可学习

    在概率近似正确学习的框架中，一个概念，如果存在一个多项式的学习算法能够学习它，学习的正确率仅比随机猜测略好。

  • 提升方法

    从弱学习算法除法，反复学习，得到一系列弱分类器（又称基本分类器），然后组合这些弱分类器，构成一个强分类器

基本思路

问题

  1. 每一轮如何改变训练数据的权值或者概率分布

    提高前一轮中被错误分类的样本的权值，降低被正确分类的样本的权值。

    目的：没有得到正确分类的数据的权值的加大受到后一轮弱分类器的关注。

  2. 如何将弱分类器组合成一个强分类器

    加权多数表决方法。

    加大正确率高的弱分类器，减小正确率低的分类器。

基本思路

​ 先从初始训练集合中训练出一个基学习器，再根据基学习器的表现对训练样本的权重进行调整，使得先前基学习器做错的样本在后续得到更多的关注，然后基于调整后的样本权重来训练下一个基学习器，直到基学习器的数目达到事先指定的数目M，最终将这M个学习器进行加权组合。

步骤

输入：

​ T=\left\{ (x_{1},y_{1}), (x_{2},y_{2}),... (x_{N},y_{N})\right\} 其中 x\in R^{n} , y\in \left\{ -1,+1 \right\} 和一个弱学习算法

  • 初始化训练数据权值

D_{1}=\left\{ w_{11},w_{12},...w_{1N} \right\},w_{1i}=\frac{1}{N}

​ 第m个基分类器的样本权重为：D_{m}=\left\{ w_{m1},w_{m2},...w_{mN} \right\}，\sum_{i=1}^{N}{w_{mi}=1}

  • 在此权值上训练弱分类器（策略为最小化分类误差率）

  • 计算分类误差率（误分类样本的权值之和）

    ​ f(x)=\sum_{i=1}^{M}{\alpha_{i}G_{i}(x)}

    其中 \alpha_{i} 为第i个基学习器的系数， G_{i}(x) 为第i个基学习器。

  • 计算分类器系数（要用到上一步的分类误差率）

    ​

  • 更新训练权值->

  • 构建基本分类器的线性组合，一直循环，直到基本分类器的线性组合没有误分类点。

Python代码实现

单决策树生成函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
from numpy import *
# 加载数据
def loadsimpData():
    dataMat=matrix([[1,2.1],
                    [2,1.1],
                    [1.3,1],
                    [1,1],
                    [2,1]])
    classLabels=[1,1,-1,-1,1]
    return dataMat,classLabels

# 单层决策树生成函数
# dimen是哪一个特征；threshVal是特征阈值；threshIneq是大于还是小于
def stumpClassify(dataMatrix,dimen,threshVal,threshIneq):
    # 初始化一个全1列表
    retArray=ones((shape(dataMatrix)[0],1))
    if(threshIneq=='lt'):
        # 以阈值划分后，小于等于阈值的，类别定为-1
        retArray[dataMatrix[:,dimen]<=threshVal]=-1.0
    else:
        retArray[dataMatrix[:,dimen]>threshVal]=-1.0
    return retArray

# D是权重向量
def buildStump(dataArr,classLabels,D):
    dataMatrix=mat(dataArr);labelMat=mat(classLabels).T
    m,n=shape(dataMatrix)
    numSteps=10.0;bestStump={};bestClassEst=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
                errArr=mat(ones((m,1)))
                # 将errArr中分类正确的置为0
                errArr[predictedVals==labelMat]=0
                # 计算加权错误率
                weightedError=D.T*errArr
                # print("split:dim %d,thresh %.2f,thresh inequal:"
                       # "%s,the weighted error is %.3f"%(i,threshVal,
                          inequal,weightedError))
                # 如果错误率比之前的小
                if(weightedError<minError):
                    minError=weightedError
                    # bestClassEst中是错误最小的分类类别
                    bestClassEst=predictedVals.copy()
                    bestStump['dim']=i
                    bestStump['thresh']=threshVal
                    bestStump['ineq']=inequal
    return bestStump,minError,bestClassEst

基于单决策树的Adaboosting训练过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# 基于单层决策树的Adaboost训练过程
# numIt表示最多迭代的次数
def adaBoostTrainDS(dataArr,classLabels,numIt=40):
    weakClassArr=[]
    m=shape(dataArr)[0]
    # 初始化权重矩阵D,1/m
    D=mat(ones((m,1))/m)
    # 初始化，aggClassEst里面存放的是类别估计的累计值
    aggClassEst=mat(zeros((m,1)))
    for i in range(numIt):
        bestStump,error,classEst=buildStump(dataArr,classLabels,D)
        print("D:",D.T)
        # 计算分类器的系数；max（）的作用是防止error=0
        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")
        # 如果分类错误率为0，则结束
        if(errorRate==0):break
    # 返回建立的分类器列表
    return weakClassArr

daboost分类函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# adaBoost分类函数
# datToClass是待分类数据；classifierArr是建立好的分类器列表
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)
    # 返回类别；sign(x)函数：x>0返回1；x<0返回-1；x=0返回0
    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

拓展

提升树

是以分类树或回归树为基本分类器的提升方法。

提升树被认为是统计学习中性能最好的方法之一。

-------------感谢阅读-------------
0%