不同的分類算法各有優(yōu)缺點(diǎn)，可以將不同的分類器組合起來
這種組合被稱為集成方法（ensemble method）或者元算法（meta-algorithm）


使用集成方法有多種形式
?○?可以是不同算法的集成
?○?可以是同一算法在不同設(shè)置下的集成
?○?可以是數(shù)據(jù)集不同部分分配給不同分類器之后的集成

bagging （Bootstrap aggregating，引導(dǎo)聚集算法，又稱裝袋算法）

• 隨機(jī)采樣：在一個(gè)有 m 個(gè)樣本的數(shù)據(jù)集中，每次采集一個(gè)樣本，然后將該樣本放回，共采集 m 個(gè)樣本形成新的數(shù)據(jù)集，這樣原始數(shù)據(jù)集中有些樣本會被重復(fù)采集，有些樣本則不會被采集，形成的新的數(shù)據(jù)集和原數(shù)據(jù)集大小相等，理論上 m 足夠大的情況下平均會有約 36% 的樣本不會被采集
• 重復(fù) S 次得到 S 個(gè)新數(shù)據(jù)集
• 將某個(gè)學(xué)習(xí)算法分別作用于每個(gè)數(shù)據(jù)集就得到了 S 個(gè)分類器
• 對新數(shù)據(jù)進(jìn)行分類時(shí)，應(yīng)用這 S 個(gè)分類器進(jìn)行分類，選擇分類器投票結(jié)果中最多的類別作為最后的分類結(jié)果

隨機(jī)森林（random forest, RF）

和普通的 bagging 差不多，在其基礎(chǔ)上做了一點(diǎn)改進(jìn)
?○?使用 S 個(gè) CART 決策樹作為弱學(xué)習(xí)器
?○?假設(shè)樣本特征數(shù)為 a，則每次生成 CART 樹都是隨機(jī)選擇 a 中的 k 個(gè)特征

boosting（提升算法）

• 與 bagging 類似，不同的是 bagging 的各個(gè)分類器是獨(dú)立訓(xùn)練出來的，而 boosting 的每個(gè)分類器是根據(jù)已訓(xùn)練出的分類器的性能來進(jìn)行訓(xùn)練
• boosting 是通過集中關(guān)注被已有分類器錯(cuò)分的那些數(shù)據(jù)來獲得新的分類器
• boosting 分類的結(jié)果是基于所有分類器的加權(quán)求和，而 bagging 中的分類器權(quán)重是相等的
• boosting 公式
  ??
  ??\(\large f(x)= \sum_{i=1}^{n}(a_{i}f_{i}(x))\)
  ??
• boosting 是串行過程，不好并行化，這是它的一個(gè)缺點(diǎn)
• boosting 有多種算法比如 adaboost、GBDT、xgboost

adaboost（adaptive boosting - 自適應(yīng) boosting）

adaboost 可以應(yīng)用于任意分類器，只要將該分類器改造成能夠處理加權(quán)數(shù)據(jù)即可

其運(yùn)行過程如下

• 對每個(gè)樣本賦予一個(gè)權(quán)重，這些權(quán)重構(gòu)成向量 D，一開始 D 初始化成相等值： \(\Large \frac{1}{樣本數(shù)}\)
• 先在訓(xùn)練數(shù)據(jù)上訓(xùn)練出一個(gè)弱分類器 \(\large f(x)\) 并按照樣本權(quán)值 D 計(jì)算該分類器的錯(cuò)誤率
  
  ??\(\large e = \sum D_{i}\)????其中 \(\large i\) 為分類錯(cuò)誤的數(shù)據(jù)
  
  
• 每個(gè)分類器也有一個(gè)權(quán)重值，該值基于每個(gè)弱分類器的錯(cuò)誤率進(jìn)行計(jì)算的，公式為
  
  ??\(\large \alpha = \frac{1}{2} ln(\frac{1-e}{e})\)
  
  
• 這里要有 \(\large e<0.5\) 以保證 \(\large \alpha>0\)，分類器也不應(yīng)該出現(xiàn)錯(cuò)誤大于一半的情況，否則應(yīng)忽略
• 然后在同一數(shù)據(jù)集上再次訓(xùn)練弱分類器，這次會調(diào)整每個(gè)樣本的權(quán)重，上一次分對的樣本的權(quán)重將會降低，分錯(cuò)的樣本的權(quán)重將會提高，同時(shí)基于上個(gè)分類器權(quán)值 \(\small \alpha\) 計(jì)算
  
  ??正確分類則
  ????\(\Large D_{i-new} = \frac{D_{i-old}\ e^{(-\alpha)}}{\sum_{j=1}^{n}D_{j-old}\ e^{(-\alpha)}}\)
  ?
  ??錯(cuò)誤分類則
  ????\(\Large D_{i-new} =\frac{D_{i-old}\ e^{(\alpha)}}{\sum_{j=1}^{n}D_{j-old}\ e^{(\alpha)}}\)
  ??
  ??將分類結(jié)果標(biāo)記為 1 和 -1，這樣統(tǒng)一寫為
  ?
  ????\(\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})))}}\)
  
  
• 累加分類結(jié)果為
  
  ??\(\Large y = sign(\sum_{i=1}^{n}(\alpha_{i}f_{i}(x)))\)
  
  
• 不斷迭代直到總錯(cuò)誤率為 0 或者弱分類器的數(shù)目達(dá)到用戶的指定值為止
  
  ??\(\Large 總錯(cuò)誤率 = \frac{累加分類結(jié)果錯(cuò)誤數(shù)}{總樣本數(shù)}\)

adaboost 代碼

# coding=utf-8
import numpy as np


def stumpClassify(dataMatrix, dimen, threshVal, threshIneq):
    """
    單層決策樹 (decision stump，也稱決策樹樁)
        它僅基于單個(gè)特征來做決策，由于只有一次分裂過程，實(shí)際上就是一個(gè)樹樁
        單層決策樹的分類能力比較弱，是一種弱分類器，通過 adaboost 使用多個(gè)單層決策樹可以構(gòu)建強(qiáng)分類器

    dataMatrix - 要分類的數(shù)據(jù)集 (n, m) 矩陣
    dimen -      用于分類的特征
    threshVal -  判斷分類的閥值
    threshIneq - 操作符 ('lt', 'gt') 決定是特征值大于閥值返回分類 -1，還是小于閥值返回分類 -1
    """

    # 初始化分類矩陣，默認(rèn)為分類 1
    retArray = np.ones((np.shape(dataMatrix)[0], 1))

    if threshIneq == 'lt':
        # 當(dāng) dataMatrix[x, dimen] <= threshVal 時(shí)，將 retArray[x] 改為 -1
        retArray[dataMatrix[:, dimen] <= threshVal] = -1.0
    else:
        retArray[dataMatrix[:, dimen] > threshVal] = -1.0

    return retArray


def buildStump(dataArr, classLabels, D):
    """
    按照樣本權(quán)值，尋找最佳的單層決策樹，即尋找最佳的分類特征和分類閥值，以及操作符

    dataArr -     樣本數(shù)據(jù)
    classLabels - 標(biāo)簽數(shù)據(jù)
    D -           樣本權(quán)值
    """

    # 初始化矩陣并獲取矩陣大小
    dataMatrix = np.mat(dataArr)
    labelMat = np.mat(classLabels).T
    n, m = np.shape(dataMatrix)

    # 閥值數(shù)
    # 將特征值從最大值到最小值之間，取 10 個(gè)間隔分出 11 個(gè)閥值，在這些閥值中選取最佳值
    numSteps = 10.0

    # 用于存儲最佳決策樹的配置，包括（特征，閥值，操作符）
    bestStump = {}

    # 用于保存最佳決策樹的分類結(jié)果
    bestClasEst = np.mat(np.zeros((n, 1)))

    # 用于保存最佳決策樹的錯(cuò)誤率
    minError = np.inf

    # 遍歷每一個(gè)特征
    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)

                # 以 (特征，閥值，操作符) 作為決策樹，對所有數(shù)據(jù)分類
                predictedVals = stumpClassify(dataMatrix, i, threshVal, inequal)

                # 評估分類結(jié)果，正確分類為 1，錯(cuò)誤分類為 0
                errArr = np.mat(np.ones((n, 1)))
                errArr[predictedVals == labelMat] = 0

                # 計(jì)算錯(cuò)誤率, D 的初始值是 1/(樣本總數(shù))
                weightedError = D.T*errArr
                if weightedError < minError:
                    # 找到更好的決策樹，保存結(jié)果
                    minError = weightedError
                    bestClasEst = predictedVals.copy()
                    bestStump['dim'] = i
                    bestStump['thresh'] = threshVal
                    bestStump['ineq'] = inequal

    # 返回最佳決策樹配置(特征，閥值，操作符), 最佳決策樹的錯(cuò)誤率, 最佳決策樹的分類結(jié)果
    return bestStump, minError, bestClasEst


def adaBoostTrainDS(dataArr, classLabels, numIt = 40):
    """
    基于單層決策樹的 adaboost 訓(xùn)練

    dataArr -     樣本數(shù)據(jù)
    classLabels - 樣本標(biāo)簽
    numIt -       最大迭代次數(shù)
    """

    # 用于保存決策樹列表
    # 每次迭代會產(chǎn)生一個(gè)決策樹, 直到達(dá)到最大迭代次數(shù), 或是最終錯(cuò)誤率為 0
    weakClassArr = []

    # 樣本數(shù)
    n = np.shape(dataArr)[0]

    # 初始化樣本權(quán)值 D，每個(gè)數(shù)據(jù)的權(quán)重為 1/(樣本數(shù))
    D = np.mat(np.ones((n, 1))/n)

    # 保存累加分類結(jié)果
    aggClassEst = np.mat(np.zeros((n, 1)))

    for i in range(numIt):
        # 按樣本和權(quán)值尋找最佳決策樹
        # 返回決策樹配置(特征，閥值，操作符), 錯(cuò)誤率, 分類結(jié)果
        bestStump, error, classEst = buildStump(dataArr, classLabels, D)

        # 計(jì)算決策樹權(quán)值 alpha = 0.5 * ln((1-err)/err)
        # 1e-16 是防止 err 為 0 的情況, ln(1/1e-16) 的結(jié)果為 36.8
        # 這里沒處理 err > 0.5 導(dǎo)致 alpha < 0 的情況, 照理說也不應(yīng)該出現(xiàn)這種情況
        alpha = float(0.5 * np.log((1.0 - error)/max(error, 1e-16)))

        # 將決策樹權(quán)值加入到?jīng)Q策樹配置
        bestStump['alpha'] = alpha

        # 將決策樹配置加入決策樹列表
        weakClassArr.append(bestStump)

        # 計(jì)算新的樣本權(quán)值
        # 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()

        # 該決策樹的分類結(jié)果, 按權(quán)值算入累加分類結(jié)果
        aggClassEst  = alpha*classEst

        # 計(jì)算累加分類結(jié)果的錯(cuò)誤率, 如果錯(cuò)誤率為 0 則退出迭代
        aggErrors = np.multiply(np.sign(aggClassEst) != np.mat(classLabels).T, np.ones((n, 1)))
        errorRate = aggErrors.sum()/n
        if errorRate == 0.0:
            break

    # 返回決策樹配置列表, 累加分類結(jié)果
    return weakClassArr, aggClassEst


def adaClassify(datToClass, classifierArr):
    """
    使用決策樹列表進(jìn)行分類

    weakClassArr -  要分類的數(shù)據(jù)
    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'])

        # 按權(quán)值累加分類結(jié)果
        aggClassEst  = classifierArr[i]['alpha']*classEst

    # sign 函數(shù)：大于 0 返回 1，小于 0 返回 -1，等于 0 返回 0
    return np.sign(aggClassEst)
????
????