本文共 5957 字，大约阅读时间需要 19 分钟。

1、Adaboost算法：

  输入训练数据集$T=\{ (x_1,y_1),(x_2,y_2),...,(x_n,y_n)\}$，其中$x_i\subset R^n,y_i\in\{-1,1\}$；弱学习算法。   输出：最终分类器$G(x)$ (1)、初始化训练数据的权值分布：

$$D_1=(w_{11},...,w_{1i},...,w_{1N})，w_{1i}=1/N,i=1,2,3...,N$$ (2)对于 m=1,2,3,...,M m = 1 , 2 , 3 , . . . , M $m=1,2,3,...,M$     (a)使用具有权值分布 Dm D m $D_m$的训练数据集学习，得到基本分类器 Gm(x) G m ( x ) $G_m(x)$     (b)计算 Gm(x) G m ( x ) $G_m(x)$在加权的训练数据集上的分类误差率 $$e_m=\sum_{i=1}^NP(G_m(x_i)\neq y_i)=\sum_{i=1}^Nw_{mi}I(G_m(x_i)\neq y_i)$$      wm,i w m , i $w_{m,i}$表示第m轮第i个实例的权值， ∑Ni=1wmi=1 ∑ i = 1 N w m i = 1 $\sum_{i=1}^Nw_{mi}=1$，这表明， Gm(x) G m ( x ) $G_m(x)$在加权的训练数据集上的分类误差率是被 Gm(x) G m ( x ) $G_m(x)$误分类样本的权值之和。     (c)计算分类器 Gm(x) G m ( x ) $G_m(x)$的系数 $$\alpha_m=\frac 1 2 \quad log\frac {1-e_m }{e_m} \quad$$     这里的对数为自然对数， αm α m $\alpha_m$随着 em e m $e_m$的减小二增大， em<0.5 e m < 0.5 $e_m<0.5$时， αm>0 α m > 0 $\alpha_m>0$， em>0.5 e m > 0.5 $e_m>0.5$时， αm<0 α m < 0 $\alpha_m<0$，所以分类误差率越小的基本分类器在最终分类器中的作用越大。     (d)更新训练集的权值分布： $$Z_m=\sum_{i=1}^Nw_{mi}exp(-\alpha_my_iG_m(x_i))$$ $$w_{m+1,i}=\frac {w_{mi}} {Z_m} \quad exp(-\alpha_my_iG_m(x_i))$$ $$D_{m+1}=(w_{m+1,1},...,w_{m+1,i},...w_{m+1,N})$$ 其中， Zm Z m $Z_m$是规范化因子，它使得 Dm+1 D m + 1 $D_{m+1}$成为一个概率分布 (3)、构建基本分类器的线性组合： $$f(x)=\sum_{m=1}^M\alpha_mG_m(x)$$

2、Adaboost算法实现

#coding=utf-8import numpy as np# 创建简单的数据集def createDataSet():     datMat = np.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# 按照指定方式分类并返回结果 #==========================================# 输入:#        dataMatrix:    输入数据#        dimen:        划分特征下标#        threshVal:    划分阈值#        threshIneq:    划分方向(是左1右0分类还是左0右1分类)# 输出:#        retArray:    分类结果，这是二分类模型，结果列表只有{-1,1}两种元素#==========================================def stumpClassify(dataMatrix,dimen,threshVal,threshIneq):        retArray = np.ones((np.shape(dataMatrix)[0],1))    if threshIneq == 'lt':        retArray[dataMatrix[:,dimen] <= threshVal] = -1.0    else:        retArray[dataMatrix[:,dimen] > threshVal] = -1.0            return retArray# 创建单层最佳决策树#==========================================# 输入:#        dataArr:    输入数据#        classLabels:    分类标签集#        D:    权重向量# 输出:#        bestStump:    决策树信息#        minError:    带权错误(用于生成分类器权重值 alpha)#        bestClasEst:    分类结果#==========================================def buildStump(dataArr,classLabels,D):        dataMatrix = np.mat(dataArr);     labelMat = np.mat(classLabels).T  # matrix.T是矩阵的转置    m,n = np.shape(dataMatrix)       numSteps = 10.0  # 特征值阈值步长        bestStump = {}   # 当前最佳决策树信息集        bestClasEst = np.mat(np.zeros((m,1)))  # 分类结果    # 最小带权错误初始化为无穷大    minError = np.inf        for i in range(n):      # 遍历所有的特征选取最佳划分特征        rangeMin = dataMatrix[:,i].min()        rangeMax = dataMatrix[:,i].max()        stepSize = (rangeMax-rangeMin)/numSteps          # 遍历所有的特征值选取最佳划分特征值 stepSize为探测步长                 for j in range(-1,int(numSteps)+1):             # 对于 左1右0 和 左0右1 两种分类方式                                      for inequal in ['lt', 'gt']:                           threshVal = (rangeMin + float(j) * stepSize)        # 当前划分阈值                                predictedVals = stumpClassify(dataMatrix,i,threshVal,inequal)  # 分类                                # 统计分类错误信息                errArr = np.mat(np.ones((m,1)))                  errArr[predictedVals == labelMat] = 0                weightedError = D.T*errArr                               # 更新最佳决策树的信息                if weightedError < minError:                    minError = weightedError                    bestClasEst = predictedVals.copy()                    bestStump['dim'] = i                    bestStump['thresh'] = threshVal                    bestStump['ineq'] = inequal                        return bestStump,minError,bestClasEst# 训练AdaBoost分类器#==========================================# 输入:#        dataArr:    输入数据#        classLabels: 分类标签集#        numIt:      最大迭代次数# 输出:#        bestStump:    决策树信息#        minError:     带权错误(用于生成分类器权重值 alpha)#        bestClasEst:  分类结果#==========================================def adaBoostTrainDS(dataArr,classLabels,numIt=40):       weakClassArr = []  # 最佳决策树集合        m = np.shape(dataArr)[0]  # 样本个数        D = np.mat(np.ones((m,1))/m)  #权重向量,mat()函数可以将目标数据的类型转换为矩阵（matrix）    aggClassEst = np.mat(np.zeros((m,1)))  #各个类别的估计累积值    for i in range(numIt):  # 迭代 numIt 次        # 构建最佳决策树        bestStump,error,classEst = buildStump(dataArr,classLabels,D)        # 计算该决策树的分类器权重值 alpha        alpha = float(0.5*np.log((1.0-error)/max(error,1e-16)))        bestStump['alpha'] = alpha          # 将该决策树加入到决策树数组中去        weakClassArr.append(bestStump)                # 更新权重向量        expon = np.multiply(-1*alpha*np.mat(classLabels).T,classEst)        D = np.multiply(D,np.exp(expon))                                      D = D/D.sum()                # 计算当前的总错误率。如果错误率为0则退出循环。        aggClassEst += alpha*classEst        aggErrors = np.multiply(np.sign(aggClassEst) != np.mat(classLabels).T,np.ones((m,1)))        errorRate = aggErrors.sum()/m        print "错误率: ",errorRate        if errorRate == 0.0:            break            return weakClassArr# Adaboost分类函数def adaClassify(datToClass,classifierArr):    dataMatrix=np.mat(datToClass)    m=np.shape(dataMatrix)[0]    aggClassEst=np.mat(np.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         return np.sign(aggClassEst)if __name__ == '__main__':    daaArr,labelArr=createDataSet()    # 获取训练集    classifierArr = adaBoostTrainDS(daaArr, labelArr, 30)    # print classifierArr    # 分类并打印结果    print adaClassify([0,0], classifierArr)