机器学习:集成算法 - 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)
????
????

相关推荐