机器学习：集成算法 - 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-8
import numpy as np


def 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 retArray


def 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, bestClasEst


def 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, aggClassEst


def 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)
????
????