机器学习：集成算法 - bagging、boosting、adaboost

不同的分类算法各有优缺点，可以将不同的分类器组合起来
这种组合被称为集成方法（ensemble method）或者元算法（meta-algorithm）


使用集成方法有多种形式
 ○ 可以是不同算法的集成
 ○ 可以是同一算法在不同设置下的集成
 ○ 可以是数据集不同部分分配给不同分类器之后的集成

bagging （Bootstrap aggregating，引导聚集算法，又称装袋算法）

• 随机采样：在一个有 m 个样本的数据集中，每次采集一个样本，然后将该样本放回，共采集 m 个样本形成新的数据集，这样原始数据集中有些样本会被重复采集，有些样本则不会被采集，形成的新的数据集和原数据集大小相等，理论上 m 足够大的情况下平均会有约 36% 的样本不会被采集
• 重复 S 次得到 S 个新数据集
• 将某个学习算法分别作用于每个数据集就得到了 S 个分类器
• 对新数据进行分类时，应用这 S 个分类器进行分类，选择分类器投票结果中最多的类别作为最后的分类结果

随机森林（random forest, RF）

和普通的 bagging 差不多，在其基础上做了一点改进
 ○ 使用 S 个 CART 决策树作为弱学习器
 ○ 假设样本特征数为 a，则每次生成 CART 树都是随机选择 a 中的 k 个特征

boosting（提升算法）

• 与 bagging 类似，不同的是 bagging 的各个分类器是独立训练出来的，而 boosting 的每个分类器是根据已训练出的分类器的性能来进行训练
• boosting 是通过集中关注被已有分类器错分的那些数据来获得新的分类器
• boosting 分类的结果是基于所有分类器的加权求和，而 bagging 中的分类器权重是相等的
• boosting 公式
    
    \(\large f(x)= \sum_{i=1}^{n}(a_{i}f_{i}(x))\)
    
• boosting 是串行过程，不好并行化，这是它的一个缺点
• boosting 有多种算法比如 adaboost、GBDT、xgboost

adaboost（adaptive boosting - 自适应 boosting）

adaboost 可以应用于任意分类器，只要将该分类器改造成能够处理加权数据即可

其运行过程如下

• 对每个样本赋予一个权重，这些权重构成向量 D，一开始 D 初始化成相等值： \(\Large \frac{1}{样本数}\)
• 先在训练数据上训练出一个弱分类器 \(\large f(x)\) 并按照样本权值 D 计算该分类器的错误率
  
    \(\large e = \sum D_{i}\)    其中 \(\large i\) 为分类错误的数据
  
  
• 每个分类器也有一个权重值，该值基于每个弱分类器的错误率进行计算的，公式为
  
    \(\large \alpha = \frac{1}{2} ln(\frac{1-e}{e})\)
  
  
• 这里要有 \(\large e<0.5\) 以保证 \(\large \alpha>0\)，分类器也不应该出现错误大于一半的情况，否则应忽略
• 然后在同一数据集上再次训练弱分类器，这次会调整每个样本的权重，上一次分对的样本的权重将会降低，分错的样本的权重将会提高，同时基于上个分类器权值 \(\small \alpha\) 计算
  
    正确分类则
      \(\Large D_{i-new} = \frac{D_{i-old}\ e^{(-\alpha)}}{\sum_{j=1}^{n}D_{j-old}\ e^{(-\alpha)}}\)
   
    错误分类则
      \(\Large D_{i-new} =\frac{D_{i-old}\ e^{(\alpha)}}{\sum_{j=1}^{n}D_{j-old}\ e^{(\alpha)}}\)
    
    将分类结果标记为 1 和 -1，这样统一写为
   
      \(\Large D_{i-new} = \frac{D_{i-old}\ e^{(-\alpha y_{i}f(x_{i}))}}{\sum_{j=1}^{n}D_{j-old}\ e^{(-\alpha y_{j}f(x_{j})))}}\)
  
  
• 累加分类结果为
  
    \(\Large y = sign(\sum_{i=1}^{n}(\alpha_{i}f_{i}(x)))\)
  
  
• 不断迭代直到总错误率为 0 或者弱分类器的数目达到用户的指定值为止
  
    \(\Large 总错误率 = \frac{累加分类结果错误数}{总样本数}\)

adaboost 代码

# coding=utf-8import numpy as npdef stumpClassify(dataMatrix, dimen, threshVal, threshIneq):    """    单层决策树 (decision stump，也称决策树桩)        它仅基于单个特征来做决策，由于只有一次分裂过程，实际上就是一个树桩        单层决策树的分类能力比较弱，是一种弱分类器，通过 adaboost 使用多个单层决策树可以构建强分类器    dataMatrix - 要分类的数据集 (n, m) 矩阵    dimen -      用于分类的特征    threshVal -  判断分类的阀值    threshIneq - 操作符 ('lt', 'gt') 决定是特征值大于阀值返回分类 -1，还是小于阀值返回分类 -1    """    # 初始化分类矩阵，默认为分类 1    retArray = np.ones((np.shape(dataMatrix)[0], 1))    if threshIneq == 'lt':        # 当 dataMatrix[x, dimen] <= threshVal 时，将 retArray[x] 改为 -1        retArray[dataMatrix[:, dimen] <= threshVal] = -1.0    else:        retArray[dataMatrix[:, dimen] > threshVal] = -1.0    return retArraydef buildStump(dataArr, classLabels, D):    """    按照样本权值，寻找最佳的单层决策树，即寻找最佳的分类特征和分类阀值，以及操作符    dataArr -     样本数据    classLabels - 标签数据    D -           样本权值    """    # 初始化矩阵并获取矩阵大小    dataMatrix = np.mat(dataArr)    labelMat = np.mat(classLabels).T    n, m = np.shape(dataMatrix)    # 阀值数    # 将特征值从最大值到最小值之间，取 10 个间隔分出 11 个阀值，在这些阀值中选取最佳值    numSteps = 10.0    # 用于存储最佳决策树的配置，包括（特征，阀值，操作符）    bestStump = {}    # 用于保存最佳决策树的分类结果    bestClasEst = np.mat(np.zeros((n, 1)))    # 用于保存最佳决策树的错误率    minError = np.inf    # 遍历每一个特征    for i in range(m):        # 取该特征的最大最小值以及步长        rangeMin = dataMatrix[:, i].min()        rangeMax = dataMatrix[:, i].max()        stepSize = (rangeMax - rangeMin)/numSteps        # 遍历所有阀值        for j in range(0, int(numSteps)   1):            # 遍历操作符            for inequal in ['lt', 'gt']:                # 取阀值                threshVal = (rangeMin   float(j) * stepSize)                # 以 (特征，阀值，操作符) 作为决策树，对所有数据分类                predictedVals = stumpClassify(dataMatrix, i, threshVal, inequal)                # 评估分类结果，正确分类为 1，错误分类为 0                errArr = np.mat(np.ones((n, 1)))                errArr[predictedVals == labelMat] = 0                # 计算错误率, D 的初始值是 1/(样本总数)                weightedError = D.T*errArr                if weightedError < minError:                    # 找到更好的决策树，保存结果                    minError = weightedError                    bestClasEst = predictedVals.copy()                    bestStump['dim'] = i                    bestStump['thresh'] = threshVal                    bestStump['ineq'] = inequal    # 返回最佳决策树配置(特征，阀值，操作符), 最佳决策树的错误率, 最佳决策树的分类结果    return bestStump, minError, bestClasEstdef adaBoostTrainDS(dataArr, classLabels, numIt = 40):    """    基于单层决策树的 adaboost 训练    dataArr -     样本数据    classLabels - 样本标签    numIt -       最大迭代次数    """    # 用于保存决策树列表    # 每次迭代会产生一个决策树, 直到达到最大迭代次数, 或是最终错误率为 0    weakClassArr = []    # 样本数    n = np.shape(dataArr)[0]    # 初始化样本权值 D，每个数据的权重为 1/(样本数)    D = np.mat(np.ones((n, 1))/n)    # 保存累加分类结果    aggClassEst = np.mat(np.zeros((n, 1)))    for i in range(numIt):        # 按样本和权值寻找最佳决策树        # 返回决策树配置(特征，阀值，操作符), 错误率, 分类结果        bestStump, error, classEst = buildStump(dataArr, classLabels, D)        # 计算决策树权值 alpha = 0.5 * ln((1-err)/err)        # 1e-16 是防止 err 为 0 的情况, ln(1/1e-16) 的结果为 36.8        # 这里没处理 err > 0.5 导致 alpha < 0 的情况, 照理说也不应该出现这种情况        alpha = float(0.5 * np.log((1.0 - error)/max(error, 1e-16)))        # 将决策树权值加入到决策树配置        bestStump['alpha'] = alpha        # 将决策树配置加入决策树列表        weakClassArr.append(bestStump)        # 计算新的样本权值        # D(i_new) = (D(i_old) * exp(-alpha * yi * f(xi))) / SUM_j_1_n (D(j_old) * exp(-alpha * yj * f(xj)))        expon = np.multiply(-1 * alpha * np.mat(classLabels).T, classEst)        D = np.multiply(D, np.exp(expon))        D = D/D.sum()        # 该决策树的分类结果, 按权值算入累加分类结果        aggClassEst  = alpha*classEst        # 计算累加分类结果的错误率, 如果错误率为 0 则退出迭代        aggErrors = np.multiply(np.sign(aggClassEst) != np.mat(classLabels).T, np.ones((n, 1)))        errorRate = aggErrors.sum()/n        if errorRate == 0.0:            break    # 返回决策树配置列表, 累加分类结果    return weakClassArr, aggClassEstdef adaClassify(datToClass, classifierArr):    """    使用决策树列表进行分类    weakClassArr -  要分类的数据    classifierArr - 决策树配置列表    """    dataMatrix = np.mat(datToClass)    n = np.shape(dataMatrix)[0]    aggClassEst = np.mat(np.zeros((n, 1)))    # 遍历决策树    for i in range(len(classifierArr)):        # 分类        classEst = stumpClassify(dataMatrix,                                 classifierArr[i]['dim'],                                 classifierArr[i]['thresh'],                                 classifierArr[i]['ineq'])        # 按权值累加分类结果        aggClassEst  = classifierArr[i]['alpha']*classEst    # sign 函数：大于 0 返回 1，小于 0 返回 -1，等于 0 返回 0    return np.sign(aggClassEst)        

来源：https://www.icode9.com/content-1-645001.html