机器学习 学习笔记（17） 集成学习

个体与集成

集成学习通过构建并结合多个学习器来完成学习任务，有时候也被称为多分类器系统（multi-classifier system）、基于委员会的学习（committee-based learning）等。

集成学习的一般结构为：先产生一组个体学习器，再用某种策略将它们结合起来。个体学习器通常由一个现有的学习算法从训练数据产生，例如C4.5、BP神经网络算法等，此时集成中只包含同类型的个体学习器，这样的集成是同质的，同质集成中的个体学习器亦称为基学习器，相应的学习算法被称为基学习算法。集成也可包含不同类型的个体学习器，例如同时包含决策树和神经网络，这样的集成是异质的。异质集成中的个体学习器由不同的学习算法生成，这时就不再有基学习算法，相应的个体学习器一般不称为基学习器，常称为组件学习器，或者直接称为个体学习器。

集成学习通过将多个学习器进行结合，常可获得比单一学习器显著优越的泛化性能，这对弱学习器尤为明显，因此集成学习的很多理论研究都是针对弱学习器进行的，而基学习器很多时候也被称为弱学习器。但需要注意的是，虽然从理论上来说，使用弱学习器集成足以获得好的性能，但在实践中出于种种考虑，例如希望使用较少的个体学习器，或者是重用关于常见学习器的一些经验等，人们往往会使用比较强的学习器。

要获得好的集成，个体学习器应该好而不同，即个体学习器要有一定的准确性，即学习器不能太坏，并且要有多样性，即学习器间具有差异。

个体学习器的准确性和多样性本身就存在冲突，一般的，准确性很高之后，要增加多样性就需要牺牲准确性。事实上，如何产生并集合好而不同的个体学习器，恰是集成学习研究的核心。

根据个体学习器的生成方式，目前的集成学习方法大致可分为两大类，即个体学习器间存在强依赖关系、必须串行生成的序列化方法，以及个体学习器之间不存在强依赖关系、可同时生成的并行化方法；前者的代表是boosting，后者的代表是bagging和随机森林（Random Forest）。

Boosting（提升方法）

Boosting是一族可将弱学习器提升为强学习器的算法，这族算法的工作机制类似：先从初始训练集训练出一个基学习器，在根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注，然后基于调整后的样本分布来训练下一基学习器；如此重复进行，直至基学习器数目达到了事先指定的值T，最终将这T个基学习器进行加权结合。 

对提升方法来说，有两个问题需要回答，一是在每一轮如何改变训练数据的权值或概率分布，二是如何将弱分类器组合成一个强分类器，关于第一个问题，AdaBoost的做法是，提高哪些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类的样本的权值。那些没有得到正确分类的数据，由于其权值的加大而受到后一轮的弱分类器的更大关注，于是分类问题被一系列弱分类器分而治之。至于第二个问题，即弱分类器的组合，AdaBoost采取加权多数表决的方法，具体的，加大分类误差率小的弱分类器的权值，使其在表决中起到较大的作用，减小分类误差率大的弱分类器的权值，使其在表决中起较小的作用。

Boosting组算法最著名的代表是AdaBoosting，其中

y_i \in \{-1,+1\}

，f是真实函数。

AdaBoosting算法描述如下：

输入：训练集

D=\{(x_1,y_1),(x_2,y_2),...,(x_m,y_m)\}

，基学习算法

\varsigma

，训练轮数T

过程：

D_1(x)=1/m

           for t=1,2,...,T do

h_t=\varsigma (D,D_t)

\epsilon _t=P_{x\sim D_t}(h_t(x)\neq f(x))

               if 

\epsilon _t>0.5

 then break

\alpha _t=\frac{1}{2}ln(\frac{1-\epsilon _t}{\epsilon _t})

D_{t+1}(x)=\frac{D_t(x)}{Z_t} \times\left\{\begin{matrix} exp(-\alpha _t) & ,if h_t(x)=f(x) \\ exp(\alpha _t)& ,if h_t(x)\neq f(x) \end{matrix}\right.

           end for

输出：

H(x)=sign(\sum_{t=1}^T\alpha _th_t(x))

AdaBoost算法有多种推导方式，比较易于理解的是加性模型，即基学习器的线性组合

H(x)=\sum_{t=1}^T\alpha _th_t(x)

，来最小化指数损失函数（exponential loss function），

l_{exp}(H|D)=E_{x\sim D}[e^{-f(x)H(x)}]

若H(x)能令指数损失函数最小化，则考虑上式对H(x)的偏导：

\frac{\partial l_{exp}(H|D)}{\partial H(x)}=-e^{-H(x)}P(f(x)=1|x)+e^{H(x)}P(f(x)=-1|x)

,

令上式为0，得

H(x)=\frac{1}{2}ln \frac{P(f(x)=1|x)}{P(f(x)=-1|x)}

因此，

sign(H(x))=sign(\frac{1}{2} ln \frac{P(f(x)=1|x)}{P(f(x)=-1|x)})=\left\{\begin{matrix} 1, & P(f(x)=1|x)>P(f(x)=-1|x)\\ -1,& P(f(x)=1|x)<P(f(x)=-1|x) \end{matrix}\right.

=\arg \max \limits_{y \in \{-1,+1\}} P(f(x)=y|x)

这意味着sign(H(x))达到了贝叶斯最优错误率。换言之，若指数函数最小化，则分类错误率也将达到最小化，这说明指数损失函数是分类任务原本0/1损失函数的一致的替代损失函数。

在AdaBoost算法中，第一个基分类器h1是通过直接将基学习算法用于初始数据分布而得到，此后迭代地生成

h_t

和

\alpha _t

，当基分类器

h_t

基于分布

D_t

产生后，该基分类器的权重

\alpha _t

应使得

\alpha _th_t

最小化指数损失函数

l_{exp}(\alpha _th_t|D_t)=E_{x\sim D_t}[e^{-f(x)\alpha _th_t(x)}]

=E_{x\sim D_t}[e^{-\alpha _t} \mathbb{I} (f(x)=h_t(x))+e^{\alpha _t}\mathbb{I}(f(x)\neq h_t(x))]

=e^{-\alpha _t}P_{x\sim D_t}(f(x)=h_t(x))+e^{\alpha _t}P_{x\sim D_t}(f(x)\neq h_t(x))

=e^{-\alpha _t}(1-\epsilon _t)+e^{\alpha _t}\epsilon _t

其中

\epsilon _t=P_{x\sim D_t}(h(x)\neq f(x))

。考虑指数损失函数的导数：

\frac{\partial l_{exp}(\alpha _th_t|D_t)}{\partial \alpha _t}=e^{-\alpha _t}(1-\epsilon _t)+e^{\alpha _t}\epsilon _t

令上式为0可以得到

\alpha _t=\frac{1}{2} ln \frac{1-\epsilon _t}{\epsilon _t}

AdaBoost算法在获得

H_{t-1}

之后样本分布将进行调整，使下一轮的基学习器

h_t

能纠正

H_{t-1}

的一些错误，理想的

h_t

能纠正

H_{t-1}

的全部错误，即最小化：

l_{exp}(H_{t-1}+h_t|D)=E_{x\sim D}[e^{-f(x)(H_{t-1}(x)+h_t(x))}]=E_{x\sim D}[e^{-f(x)H_{t-1}(x)}e^{-f(x)h_t(x)}]

注意到

f^2(x)=h^2_t(x)=1

，使用

e^{-f(x)h_t(x)}

的泰勒展式近似为：

l_{exp}(H_{t-1}+h_t|D)\simeq E_{x\sim D}[e^{-f(x)H_{t-1}(x)}(1-f(x)h_t(x)+\frac{f^2(x)h^2_t(x)}{2})]

=E_{x\sim D}[e^{-f(x)H_{t-1}(x)}(1-f(x)h_t(x)+\frac{1}{2})]

于是，理想的基学习器：

h_t(x)=\arg \min \limits_{h} l_exp(H_{t-1}+h|D)

=\arg \min \limits_{h} E_{x\sim D}[e^{-f(x)H_{t-1}(x)}(1-f(x)h(x)+\frac{1}{2})]

=\arg \max \limits_{h} E_{x\sim D}[e^{-f(x)H_{t-1}(x)}f(x)h(x)]=\arg \max \limits_{h} E_{x\sim D}[\frac{e^{-f(x)H_{t-1}(x)}}{E_{x\sim D[e^{-f(x)H_{t-1}(x)}]}}f(x)h(x)]

E_{x\sim D[e^{-f(x)H_{t-1}(x)}]}

是一个常数，令

D_t

表示一个分布，

D_t(x)=\frac{D(x)e^{-f(x)H_{t-1}(x)}} {E_{x\sim D}[e^{-f(x)H_{t-1}(x)}]}

根据数学期望的定义，等价于：

h_t(x)=\arg \max \limits_{h} E_{x\sim D}[\frac{e^{-f(x)H_{t-1}(x)}}{E_{x\sim D[e^{-f(x)H_{t-1}(x)}]}}f(x)h(x)]=\arg \max \limits_{h} E_{x\sim D_t}[f(x)h(x)]

由

f(x),h(x)\in \{-1,+1\}

，有

f(x)h(x)=1-2\mathbb{I}(f(x)\neq h(x))

，则理想的基学习器

h_t(x)=\arg \min \limits_{h} E_{x\sim D_t}[\mathbb{I}(f(x)\neq h(x))]

理想的

h_t

将在分布

D_t

下最小化分类误差，因此，弱分类器将基于分布

D_t

来训练，且针对

D_t

的分类误差应小于0.5，这在一定程度上类似残差逼近的思想，考虑到

D_t

和

D_{t+1}

的关系，有：

D_{t+1}(x)=\frac{D(x)e^{-f(x)H_t(x)}}{E_{x\sim D}[e^{-f(x)H_t(x)}]}=\frac{D(x)e^{-f(x)H_{t-1}(x)}e^{-f(x)\alpha _th_t(x)}}{E_{x\sim D}[e^{-f(x)H_t(x)}]}

=D_t(x)\cdot e^{-f(x)\alpha _th_t(x)}\frac{E_{x\sim D[e^{-f(x)H_{t-1}(x)}]}}{E_{x\sim D[e^{-f(x)H_{t}(x)}]}}

Boosting算法要求基学习器能对特定的数据分布进行学习，这可通过重赋权法（re-weighting）实施，即在训练过程的每一轮中，根据样本分布为每个训练样本重新赋予一个权重。对无法接受带权样本的基学习算法，则可通过重采样法（re-sampling）来处理，即在每一轮学习中，根据样本分布对训练集重新进行采样，再用重采样而得的样本集对基学习器进行训练。一般而言，这两种做法没有明显的优劣差别。需要注意的是，Boosting算法在训练的每一轮都要检查当前生成的基学习器是否满足基本条件，一旦条件不满足，则当前基学习器就被抛弃，且学习过程停止。此种情况下，初始设置的学习轮数T也许远远未达到，可能导致最终集成中只包含很少的基学习器而性能不佳，若采用重采样法，则可获得重启动的机会以避免训练过程过早停止，即在抛弃不满足条件的当前基学习器之后，可根据当前分布重新对训练样本进行采样，在基于新的采样结果重新训练处基学习器，从而使得学习过程可以持续到预设的T轮完成。

从偏差方差恩杰的角度看，Boosting主要关注降低偏差，因此Boosting能基于泛化性能相当弱的弱学习器构建出很强的集成。

AdaBoost最基本的性质是它能在学习过程中不断减少训练误差，即在训练数据集上的分类误差率。

AdaBoost算法最终分类器的训练误差界为：

\frac{1}{N} \mathbb{I}(G(x_i)\neq y_i)\leqslant \frac{1}{N}\sum_{i} exp(-y_if(x_i))=\prod _{m}Z_m

，

G(x)=sign(f(x))=sign(\sum_{m=1}^M\alpha _mG_m(x))

，

f(x)=\sum_{m=1}^M\alpha _mG_m(x)

，

Z_m=\sum_{i=1}^Nw_{mi}exp(-\alpha _my_iG_m(x_i))

若存在

\gamma >0

，对所有的m有

\gamma _m\geqslant \gamma

，则

\frac{1}{N}\sum_{i=1}^N\mathbb{I}(G(x_i)\neq y_i)\leqslant exp(-2M\gamma ^2)

，这表明在此条件下的AdaBoost的训练误差是以指数速率下降的。

AdaBoost算法的一个解释是模型为加法模型、损失函数为指数函数、学习算法为前向分步算法时的二分类学习方法。

前向分步算法

考虑加法模型

f(x)=\sum_{m=1}^M\beta _mb(x;\gamma _m)

，其中

b(x;\gamma _m)

为基函数，

\gamma _m

为基函数的参数，

\beta _m

为基函数的系数。

给定训练数据及损失函数

L(y,f(x))

的条件下，学习加法模型

f(x)

称为经验风险极小化即损失函数极小化问题

\min \limits_{\beta _m,\gamma _m} \sum_{i=1}^NL(y_i,\sum_{m=1}^M\beta _mb(x_i;\gamma _m))

通常这是一个复杂的优化问题，前向分步算法（forward stagewise algorithm）求解这一优化问题的想法是，因为学习的是加法模型，如果能从前向后，每一步只学习一个基函数及其系数，逐步逼近优化目标函数式，那么就可以简化优化的复杂度，具体地，每步只需要优化如下损失函数：

\min \limits_{\beta ,\gamma }\sum_{i=1}^N L(y_i,\beta b(x_i;\gamma ))

，给定训练数据集

T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}

，

x_i\in \chi \subseteq R^n

,

y_i\in Y\subseteq \{-1,+1\}

，损失函数

L(y,f(x))

和基函数的集合

\{b(x;\gamma )\}

，学习加法模型f(x)的前向分步算法如下：

输入：训练数据集

T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}

，损失函数

L(y,f(x))

，基函数

\{b(x;\gamma )\}

输出：加法模型f(x)

（1）初始化

f_0(x)=0

（2）对m=1,2,...,M

         (a)极小化损失函数

(\beta _m,\gamma _m)=\arg \min \limits_{\beta ,\gamma }\sum_{i=1}^N(y_i,f_{m-1}(x_i)+\beta b(x_i;\gamma ))

，得到参数

\beta _m,\gamma _m

         (b)更新

f_m(x)=f_{m-1}(x)+\beta _mb(x;\gamma _m)

（3）得到加法模型

f(x)=f_{M}(x)=\sum_{m=1}^M\beta _mb(x;\gamma _m)

这样，前向分步算法将同时求解从m=1到M所有参数

\beta _m,\gamma _m

的优化问题简化为逐次求解各个

\beta _m,\gamma _m

的优化问题。

# 代码主要来自于机器学习实战
from numpy import *

def loadSimpData():
    datMat=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

# 单层决策树生成树

# 通过阈值比较对数据进行分类的。
# 所有在阈值一边的数据会分类到类别-1，而在另外一边的数据分到类别+1
# 该函数可以通过数组过滤来实现
# 首先将返回数组的全部元素设置为1
# 然后将所有不满足不等式要求的元素设置为-1
# 可以基于数据集中的任一元素进行比较，同时也可以将不等号在大于小于之间切换
def stumpClassify(dataMatrix,dimen,threshVal,threshIneq):
    retArray=ones((shape(dataMatrix)[0],1))
    if threshIneq=='lt':
        retArray[dataMatrix[:,dimen]<=threshVal]=-1.0
    else:
        retArray[dataMatrix[:,dimen]>threshVal]=-1.0

    return retArray

# 第二个函数buildStump将会遍历stumpClassify函数所有的可能输入值
# 并找到数据集上最佳的单层决策树
# 最佳是基于数据的权重向量D来定义的
# 在确保输入数据符合矩阵格式之后，整个函数就开始执行了
# 函数将构建一个称为bestStump的空字典，这个字典用于存储给定权重向量D时所得到的最佳单层决策树的相关信息
# 变量numSteps用于在特征的所有可能值上进行遍历
# 而遍历minError则在一开始就初始化成正无穷大，之后用于寻找可能的最小错误率
# 三层嵌套的for循环是程序最主要的部分。
# 第一层for循环在数据集的所有特征上遍历
# 考虑数值型的特征，我们就可以通过计算最小值和最大值来了解应该需要多大的步长
# 第二层for循环再在这些值上遍历。甚至将阈值设置为整个取值范围之外也是可以的。
# 因此在取值范围之外应该还有两个额外步骤
# 最后一个for循环则是在大于和小于之间切换不等式
# 在嵌套的三层for循环之内，我们在数据集及三个循环变量上调用stumpClassify函数
# 基于这些循环变量，该函数会返回分类预测结果
# 接下来构建一个列向量errArr，如果predcitVals中的值不等于labelMat中的真正类别标签值
# 那么errArr的相应位置为1
# 将错误向量errArr和权重向量D的相应元素相乘并求和，就得到了数值weightedError
# 这就是AdaBoost和分类器交互的地方
# 这里，我们是基于权重向量D而不是其他错误计算指标来评价分类器的
# 如果需要使用其他分类器的话，就需要考虑D上最佳分类器所定义的计算过程
# 最后，将当前的错误率与已有的最小错误率进行对比
# 如果当前的值较小，那么就在词典bestStump中保存该单层决策树
# 字典、错误率和类别估计值都会返回AdaBoost算法
def buildStump(dataArr,classLabels,D):
    dataMatrix=mat(dataArr)
    labelMat=mat(classLabels).T
    m,n=shape(dataMatrix)
    numSteps=10.0
    bestStump={}
    bestClassEst=mat(zeros((m,1)))
    minError=inf
    for i in range(n):
        rangeMin=dataMatrix[:,i].min()
        rangeMax=dataMatrix[:,i].max()
        stepSize=(rangeMax-rangeMin)/numSteps
        for j in range(-1,int(numSteps)+1):
            for inequal in ['lt','gt']:
                threshVal=(rangeMin+float(j)*stepSize)
                predictVals=stumpClassify(dataMatrix,i,threshVal,inequal)
                errArr=mat(ones((m,1)))
                errArr[predictVals==labelMat]=0
                weightedError=D.T*errArr # 计算加权错误率
                print('split: dim %d,htresh %.2f, thresh inequal: %s, the weighted error is %.3f' % (i,threshVal,inequal,weightedError))
                if weightedError<minError:
                    minError=weightedError
                    bestClassEst=predictVals.copy()
                    bestStump['dim']=i
                    bestStump['thresh']=threshVal
                    bestStump['ineq']=inequal
    return bestStump,minError,bestClassEst

D=mat(ones((5,1))/5)
datMat,classLabels=loadSimpData()
#buildStump(datMat,classLabels,D)

# 基于单层决策树的AdaBoost训练过程
# 这个算法会输出一个单层决策树的数组，因此首先需要建立一个新的python表来对其进行存储
# 然后，得到数据集中的数据点的数目m，并建立一个列向量D
# 向量D非常重要，包含了每个数据点的权重
# 一开始，这些权重都赋予了相等的值
# 在后续的迭代中，adaboost算法会在增加错分数据权重的同事，降低正确分类数据的权重
# D是一个概率分布向量，因此其所有元素之和为1.0
# 一开始的所有元素都会被初始化为1/m
# 同时，程序还会建立另一个列向量aggClassEst，
# 记录每个数据点的类别估计累计值
# AdaBoost算法的核心在于for循环，该循环运行numIt次或者直到训练错误率为0为止
# 循环中的第一件事就是利用前面介绍的buildStump函数建立一个单层决策树
# 该函数的输入为权重向量D，返回的则是利用D而得到的具有最小错误率的单层决策树
# 同时返回的还有最小的错误率以及估计的类别向量
# 接下来，需要计算alpha的值，该值会告诉分类器本次单层决策树输出结果的权重
# 其中的max(error,1e-16)用于确保在没有错误时不会发生除0溢出
# 而后，alpha值加入到bestStump字典中，该字典又添加到列表中
# 该字典包括了分类所需要的所有信息
# 接下来，计算下一次迭代中的新权重向量D，在训练错误率为0时，就要提前结束for循环
# 此程序是通过aggClassEst变量保持一个运行时的类别估计值来实现的
# 该值只是一个浮点数，为了得到二值分类结果还需呀调用sign()函数
# 如果总错误率为0，则有break语句终止for循环
def adaBoostTrainDS(dataArr,classLabels,numIt=40):
    weakClassArr=[]
    m=shape(dataArr)[0]
    D=mat(ones((m,1))/m)
    aggClassEst=mat(zeros((m,1)))
    for i in range(numIt):
        bestStump,error,classEst=buildStump(dataArr,classLabels,D)
        print("D: ",D.T)
        alpha=float(0.5*log((1.0-error)/max(error,1e-16)))
        bestStump['alpha']=alpha
        weakClassArr.append(bestStump)
        print('classEst: ',classEst.T)
        # 为下一次迭代计算D
        expon=multiply(-1*alpha*mat(classLabels).T,classEst)
        D=multiply(D,exp(expon))
        D=D/D.sum()
        aggClassEst+=alpha*classEst
        print('aggClassEst: ',aggClassEst.T)
        # 错误率累加计算
        aggErrors=multiply(sign(aggClassEst)!=mat(classLabels).T,ones((m,1)))
        errorRate=aggErrors.sum()/m
        print('total error: ',errorRate,'\n')
        if errorRate==0.0:
            break
    return weakClassArr,aggClassEst

classifierArray=adaBoostTrainDS(datMat,classLabels,9)
#print(classifierArray)

# AdaBoost分类函数
# 利用训练出的多个弱分类器进行分类
# 该函数的输入是由一个或者多个待分类样例datToClass以及多个弱分类器组成的数组classifierArr
# 函数首先将datToClass转换成了一个numpy矩阵，并且得到其中的待分类样例个数m
# 然后构建一个0向量aggClassEst
# 这个列向量与adaBoostTrainDS中的含义一样
# 接下来，遍历classifierArr中的所有弱分类器
# 并给予stumpClassify对每个分类器得到一个类别的估计值
# 在前面构建单层决策树是，已经见过了stumpClassify函数
# 在那里，在所有可能的树桩值上进行迭代得到具有最小加权错误率的单层决策树
# 这里只是简单地应用了单层决策树
# 输出的类别估计值乘上该单层决策树的alpha权重然后累加到aggClassEst上，就完成了这一过程
def adaClassify(datToClass,classifierArr):
    dataMatrix=mat(datToClass)
    m=shape(dataMatrix)[0]
    aggClassEst=mat(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
        print(aggClassEst)
    return  sign(aggClassEst)
# datArr,labelArr=loadSimpData()
# classifierArr=adaBoostTrainDS(datArr,labelArr,30)
# adaClassify([0,0],classifierArr)

Bagging与随机森林

Bagging是并行式集成学习方法最著名的代表。给定包含m个样本的数据集，先随机取出一个样本放入采样集中，再把该样本放回初始数据集，使得下次采样时，该样本仍有可能被选中，这样经过m次随机采样操作，我们得到含m个样本的采样集，初始训练集中有的样本在采样集中多次出现，有的则从未出现，初始训练集中约有63.2%的样本出现在采样集中。

可采样出T个含m个训练样本的采样集，然后基于每个采样集训练出一个基学习器，再将这些基学习器进行结合。这就是Bagging的基本流程。在对预测输出进行结合时，Bagging通常对分类任务使用简单投票法，对回归任务使用简单平均法。若分类预测时出现两个类收到同样票数的情形，则最简单的做法是随机选择一个，也可进一步考察学习器的投票置信度来确定最终胜者。

Bagging算法描述如下：

输入：训练集

D=\{(x_1,y_1),(x_2,y_2),...,(x_m,y_m)\}

，基学习算法

\zeta

，训练轮数T

过程：for t=1,2,...,T do

h_t=\zeta (D,D_{bs})

           end for

输出：

H(x)=\arg \max \limits_{y\in Y} \sum_{t=1}^T\mathbb{I}(h_t(x)=y)

假定基学习器计算复杂度为O(m)，则Bagging的复杂度大致为T(O(m)+O(s))，考虑到采样与投票/平均过程的复杂度为O(s)很小，而T通常是一个不太大的常数，因此，训练一个Bagging集成与直接使用基学习算法训练一个学习器复杂度同阶，这说明Bagging是一个很高效的集成学习算法。另外与标准AdaBoost只适用于二分类任务不同，Bagging能不经修改地用于多分类、回归等任务。

值得一提的是，自助采样过程还给Bagging带来了另一个由于每个基学习器只使用了初始训练集中约63.2%的样本，剩下的36.8%的样本可以用作训练集来对泛化性能进行包外估计。为此需要记录每个基学习器所使用的训练样本，不妨令

D_t

表示

h_t

实际使用的训练样本集，令

H^{oob}(x)=\arg \max \limits_{y \in Y} \sum_{t=1}^T \mathbb{I}(h_t(x)=y)\cdot \mathbb{I}(x \notin D_t)

，则Bagging泛化误差的包外估计为

\epsilon ^{oob}=\frac{1}{|D|} \sum_{(x,y)\in D}\mathbb{I}(H^{oob}(x)\neq y)

实际上包外样本还有许多用途。比如基学习器是决策树时，可以使用包外样本来辅助剪枝，或用于估计决策树中各结点的后验概率以辅助对零训练样本结点的处理，当基学习器是神经网络时，可使用包外样本来辅助早期停止以减小过拟合风险。

从偏差-方差分解的角度看，Bagging主要关注降低方差。

随机森林

随机森林（Random Forest，RF）是Bagging的一个扩展变体。RF在引入决策树为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入了随机属性选择。具体来说，传统决策树在选择划分属性时是在当前结点的属性集中选择一个最优属性，而在RF中，对基决策树的每个结点，先从该结点的属性集合中随机选择一个包含k个属性的子集，然后再从这个子集中选择一个最优属性用于划分。参数k控制了随机性引入的程度：若令k=d，则基决策树的构建与传统决策树相同，若k=1，则是随机选择一个属性用于划分，一般情况下，推荐值

k=log_2 d

。

随机森林简单、容易实现、计算开销小，但在很多现实任务中展现出强大的性能，被誉为代表集成学习技术水平的方法。可以看出，随机森林对Bagging只做了小改动，但是与Bagging中基学习器的多样性，仅通过样本扰动（通过对初始训练集采样）而来不同，随机森林中基学习器的多样性不仅来自样本扰动，还来自属性扰动，这就使得最终集成的泛化性能可通过个体学习器之间的差异度的增加而进一步提升。

随机森林的收敛性与Bagging相似，随机森林的其实性能往往相对比较差，特别是在集成中只包含一个基学习器时。随着个体学习器数目的增加，随机森林通常会收敛到更低的泛化误差。值得一提的是，随机森林的训练效率常优于Bagging，因为在个体决策树的构建过程中，Bagging使用的是确定型决策树，在选择划分属性时要对结点的所有属性进行考察，而随机森林使用的随机型决策树只需考察一个属性子集。

结合策略

学习器结合可能会从三个方面带来好处，首先，从统计的方面来看，由于学习任务的假设空间往往很大，可能有多个假设在训练集上达到同样性能，此时若使用但学习器可能因误选而导致泛化性能不佳，结合多个学习器则会减小这一风险。第二，从计算的方面来看，学习算法往往会陷入局部极小，有的局部极小点所对应的泛化性能可能很糟，而通过多次运行之后结合，可降低陷入糟糕局部极小点的风险。第三，从表示的方面看，某些学习任务的真实假设可能不在当前学习算法所考虑的假设空间中，此时，若使用单学习器肯定无效，而通过结合多个学习器，由于相应的假设空间有所扩大，有可能学得更好的近似。

假定集成包含T个基学习器

\{h_1,h_2,...,h_T\}

，其中

h_i

在示例x上的输出为

h_i(x)

。以下是几种对

h_i

进行结合的常见策略。

1. 对数值型输出

h_i(x) \in R

，最常见的结合策略是使用平均法。简单平均法，加权平均法。事实上，加权平均法可认为是集成学习研究的基本出发点，对给定的基学习器，不同的集成学习方法可视为通过不同的方式来确定加权平均法中的基学习器权重。加权平均法的权重一般是从训练数据中学习而得到，现实任务中的训练样本通常不充分或存在噪声，这将使得学出的权重不完全可靠。对于规模较大的集成来说，要学习的权重比较大，容易导致过拟合。一般而言，在个体学习器性能相差较大时宜使用加权平均法，而在个体学习器性能相近时，宜使用简单平均法。

1. 投票法，对分类任务来说，学习器

h_i

将从类别标记中预测出一个标记，最常见的结合策略是使用投票法。绝对多数投票法（若某标记得票超过半数，则预测为该标记，否则拒绝预测）、相对多数投票法（预测为得票最多的标记）、加权投票法。

1. 学习法。当训练数据很多时，一种更为强大的结合策略是使用学习法，即通过另一个学习器来进行结合。Stacking是学习法的典型代表。个体学习器被称为初级学习器，用于集合的学习器称为刺激学习器或元学习器。

现实任务中，不同类型个体学习器可能产生不同类型的

h^j_i(x)

值，常见的有类标记（硬投票）和类概率（软投票），不同类型的值不能混用。对一些能在预测出类别标记的同事产生分类置信度的学习器，其分类置信度可以转化为类概率使用，若此类值未进行规范化，则必须使用一些技术如Platt缩放、等分回归等进行校准后才能作为类概率使用。虽然分类器估计出的类概率值一般都不太准确，但基于类概率进行结合的却往往比直接基于类标记进行结合性能更好。需要注意的是，若基学习器的类型不同，则其类概率值不能直接进行比较，此种情况下，往往将类概率转化为类标记输出然后再进行投票。

Stacking先从初始数据集训练处初级学习器，然后生成一个新的数据集用于训练次级学习器，在这个心数据集中，初级学习器的输出被当做样例输入特征，而初始样本的标记仍被当做样例标记。

Stacking的算法描述如下所示，假定初级学习器使用不同的学习算法产生，即初级集成是异质的：

输入：训练集

D=\{(x_1,y_1),(x_2,y_2),...,(x_m,y_m)\}

，初级学习算法

\zeta _1,\zeta _2,...,\zeta _T

，次级学习算法

\zeta

过程：

for t=1,2,...,T do

h_t=\zeta _t(D)

end for

D'=\varnothing

for i=1,2,...,m do

    for t=1,2,...,T do

z_{it}=h_t(x_i)

    end for

D'=D'\cup ((z_{i1},z_{i2},...,z_{iT}),y_i)

end for

h'=\zeta (D')

输出：

H(x)=h'(h_1(x),h_2(x),...,h_T(x))

在训练阶段，次级训练集是利用初级学习器产生的，若直接使用初级学习器的训练集来产生次级训练集，过拟合风险较大，因此一般通过交叉验证法或留一法这样的方式，用训练初级学习器未使用的样本来产生次级学习器的训练样本。

次级学习器的输入属性表示和次级学习算法对Stacking集成的泛化性能有很大影响。有研究表明，将初级学习器的输出类概率作为次级学习器的输入属性，用多响应线性回归（Multi-response Linear Regression，MLR）作为次级学习算法效果较好，在MLR中使用不同的属性集更佳。

贝叶斯模型平均（Bayes Model Averaging，BMA）基于后验概率来为不同模型赋予权重，可视为加权平均法的一种特殊实现。理论上来说，若数据生成模型恰在当前考虑的模型中，且数据噪声很少，则BMA不差于Stacking，然而在现实应用中无法确保数据生成模型一定在当前考虑的模型中，甚至可能难以用当前考虑的模型来近似。因此Stacking往往优于BMA，因为其鲁棒性更好，而且BMA对模型近似误差非常敏感。

多样性

个体学习器准确性越高、多样性越大，则集成越好。

多样性度量是用于度量集成中个体分类器的多样性，即估算个体学习器的多样化程度。典型的做法是考虑个体分类器的两两相似性/不相似性。

给定数据集

D=\{(x_1,y_1),(x_2,y_2),...,(x_m,y_m)\}

，对二分类任务，

y_i\in \{-1,+1\}

，分类器

h_i

与

h_j

的预测结果列联表为

a+b+c+d=m。

• 不合度量(disagreement measure)  

dis_{ij}=\frac{b+c}{m}

 ，

dis_{ij}\in [0,1]

，值越大则多样性越大

• 相关系数（correlation coefficient）

\rho _{ij}=\frac{ad-bc}{\sqrt{(a+b)(a+c)(c+d)(b+d)}}

   ，

\rho _{ij}\in [-1,1]

，若

h_i,h_j

无关，则值为0，若正相关，则值为正，否则为负。

• Q-统计量（Q-statistic） 

Q_{ij}=\frac{ad-bc}{ad+bc}

，

Q_{ij}

与相关系数

\rho _{ij}

符号相同，且

|Q_{ij}|\geqslant |\rho _{ij}|

\kappa -

统计量（

\kappa -statistic

）

\kappa =\frac{p_1-p_2}{1-p_2}

，

p_1

是两个分类器取得一致的概率，

p_2

是两个分类器偶然达成一致的概率，它们可由数据集D估算。

p_1=\frac{a+d}{m}

，

p_2=\frac{(a+b)(a+c)+(c+d)(b+d)}{m^2}

。若分类器

h_i,h_j

在D上完全一致，则

\kappa =1

，若它们仅是偶然达成一致，则

\kappa =0

，

\kappa

通常为非负值，仅在 

h_i,h_j

达成一致的概率甚至低于偶然性的情况下取负值

以上都是成对行度量，可以很容易地通过2维图绘制处出来，如著名的

\kappa -

误差图 ，就是将每一对分类器作为图上的一个点，横坐标是这对分类器的

\kappa

值，纵坐标是它们的平均误差。数据点云位置越高，个体分类器准确性越低，点云的位置越靠右，则个体学习器的多样性越小。

增强多样性，一般思路是在学习过程中引入随机性，常见做法主要是对数据样本、输入属性、输出表示、算法参数进行扰动。

• 数据样本扰动，给定初始数据集，可从中产生出不同的数据子集，再利用不同的数据子集训练出不同的个体学习器。数据样本扰动通常是基于采样法，例如在Bagging中使用自助采样，在AdaBoost中使用序列采样。此类做法简单高效，使用最广。对很多常见的基学习器，例如决策树、神经网络等，训练样本稍加变化就会导致学习器有显著变动，数据样本的扰动法对这样的不稳定基学习器很有效。然而一些基学习器对数据样本扰动不敏感，例如线性学习器、支持向量机、朴素贝叶斯、k近邻学习器等，这样的基学习器称为稳定基学习器，对此类基学习器进行集成往往需使用输入属性扰动等其他机制。
• 输入属性扰动，训练样本通常由一组属性描述，不同的子空间（即属性子集）提供了观察数据的不同视角，显然，从不同子空间训练出的个体学习器必然有所不同。著名的随机子空间（random subspace）算法就依赖于输入属性扰动，该算法从初始属性集中抽取出若干属性子集，再基于每个属性子集训练一个基学习器。对包含大量冗余属性的数据，在子空间中训练个体学习器不仅能产生多样性大的个体，还会因属性数的减少而大幅节省时间开销，同时，由于冗余属性多，减少一些属性后训练出的个体学习器也不至于太差。若数据只包含少量属性，或者冗余属性很少，则不宜使用输入属性扰动法。
• 输出表示扰动，此类做法的基本思路是对输出表示进行操纵以增强多样性，可对训练样本的类标记稍作变动，如“翻转法”随机改变一些训练样本的标记，也可对输出表示进行转化，如“输出调制法”将分类输出转化为回归输出后构建个体学习器，还可以将原任务拆解为多个可同时求解的子任务，如ECOC法利用纠错输出码将多分类任务拆解称一系列二分类任务来训练基学习器。
• 算法参数扰动。基学习算法一般都有参数需进行设置，例如神经网络的隐层神经元数、初始连接权值等，通过随机设置不同的参数，往往可产生差别较大的个体学习器。“负相关法”显式地通过正则化项来强制个体神经网络使用不同的参数，对参数较少的算法，可通过将其学习过程中的某些环节用其他类似方式代替，从而达到扰动目的。

随机子空间算法描述：

输入：训练集

D=\{(x_1,y_1),(x_2,y_2),...,(x_m,y_m)\}

，基学习算法

\zeta

，基学习器数T，子空间属性数

d'

过程：

for t=1,2,...,T do

F_t=RS(D,d')

D_t=Map_{F_t}(D)

h_t=\zeta (D)

end for

输出：

H(x)=\arg \max \limits_{y \in Y} \sum_{t=1}^T\mathbb{I}(h_t(Map_{F_t}(x))=y)

参考

1. 《机器学习》
2. 《统计学习方法》
3. 《机器学习实战》