8.1 个体与集成

集成学习是通过构建并结合多个学习器来完成任务。

集成学习的一般结构：一组"个体学习器"通过某种策略将它们结合起来。

集成学习的种类：
1）同质集成
个体学习器通过某种算法训练而成，此时集成中只包含同种类型的个体学习器，这就是同质集成。如，每个个体学习器通过C4.5决策树算法训练而成，最终组成"决策树集成"；再如"神经网络集成"中都是神经网络。
同质集成中的个体学习器称为"基学习器"，相应算法称为"基学习算法"。
2）异质集成
集成中包含不同算法训练而成的个体学习器，如集成中同时包含决策树和神经网络，这样的集成就是异质集成。异质集成中的个体学习器称为"组件学习器"。

集成学习示意图

要获得好的集成，个体学习器应当"好而不同"。
"好"即个体学习器要有一定的"准确性"，不能太差；
"不同"即要有"多样性"，学习器之间要有差异。

集成中的学习器应好而不同

图a中，每个分类器h的精度是66.6%，但是集成中的精度提升到100%；图b中，每个分类器的结果都是一样的，因此集成中没有变化；图c中，每个分类器的精度只有33.3%，集成中的精度降低为0。从上面可以看出，图a的三个分类器满足了"好而不同"，"好"即有66.6%的精度，"不同"即每个分类器的结果不同；而图b虽然"好"，但是分类器结果相同；图c虽然结果不同，但是精度太低。

从集成错误率中可以看出，个体学习器的数目T越大，集成错误率越低，直至为0。

然而，现实中，基学习器不是相互独立的，所以个体学习器的"准确性"和"多样性"本身就存在冲突。一般的，准确性很高之后，要增加多样性就需牺牲准确性。

如何产生并结合"好而不同"的个体学习器，是集成学习研究的核心。

• 对于产生好而不同的学习器的方式
  根据个体学习器的生成方式，目前的集成学习方法大致可分为两大类：
  第一类：个体学习器问存在强依赖关系、必须串行生成的序列化方法。代表是Boosting
  第二类：个体学习器间不存在强依赖关系、可同时生成的并行化方法。代表是Bagging和"随机森林" (Random Forest)。

• 结合学习器的方式。
  1）平均法
  2）投票法
  3）学习法

上面的产生和结合方式将在下面讲到。

8.2 Boosting

弱学习器常指泛化性略优于随机猜测的学习器。
例如在二分类问题上精度略高于50%的分类器目。

Boosting是可以将弱学习器提升为强学习器的算法。
Boosting主要关住降低偏差，因此Boosting能基于泛化性能相当弱的学习器构建出很强的集成。

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

Boosting工作机制示意图

2）通过什么方式来组合弱分类器？
通过加法模型将弱分类器进行线性组合。

Boosting族中最著名的是AdaBoost算法。
刚开始训练时对每一个训练例赋相等的权重，然后用该算法对训练集训练t轮，每次训练后，对训练失败的训练例赋以较大的权重，也就是让学习算法在每次学习以后更注意学错的样本，从而得到多个预测函数。通过拟合残差的方式逐步减小残差，将每一步生成的模型叠加得到最终模型。

AdaBoost算法流程

以下是AdaBoost的推导

基于基学习器的线性组合，来最小化指数损失函数。

基学习器的线性组合

指数损失函数

第一个基学习器h₁是通过基学习算法用于初始数据发布获得。
之后迭代产生α_t和h_t，当学习器h_t基于发布D_t产生后，h_t的权重α_t，要使得α_th_t最小化指数损失函数。对于每个α_th_t有，

每个基学习器的指数损失函数

推导之后，可以再次巩固AdaBoost算法的流程。
算法流程:https://blog.csdn.net/qq_37960402/article/details/88426900

AdaBoost算法的实现代码

import pdb
import numpy as np
import operator
import math
def dataset():
    data=[0,1,2,3,4,5,6,7,8,9]
    labels=[1,1,1,-1,-1,-1,1,1,1,-1]
    return data,labels


def mytree(data,label,D1):    #生成最优决策树
    point=(np.array(data[:-1])+np.array(data[1:]))/2   #取data中相邻两者之间的平均值
    dic={}
    sign={}
    for i in point:      #遍历平均值
        predict1=np.array(data<i)       #判断左边为1
        predict1=(predict1+0)+(predict1-1)    #将结果转换为[1,-1]
        result1=sum(abs(predict1-label)/2*D1)  #误差

        predict2 = np.array(data > i)    #判断右边为1
        predict2 = (predict2 + 0) + (predict2 - 1)
        result2 = sum(abs(predict2 - label) / 2 * D1)
        if  result1<=result2:   #保存符号和左右边哪个结果更好
            dic[i]=result1
            sign[i]='<'
        else:
            dic[i]=result2
            sign[i]='>'
    bestpoint = sorted(dic.items(),key=operator.itemgetter(1))
    return bestpoint[0],sign[bestpoint[0][0]]



def Zm1(label,Gm,a,D1):   #返回当前样本的权重
    sum=0
    for i in range(len(label)):
        sum+=D1[i]*math.e**(-a*label[i]*Gm[i])
    newD1=[]
    for i in range(len(label)):
        w=D1[i]/sum*math.e**(-a*label[i]*Gm[i])
        newD1.append(w)
    return newD1


def adaboot1():
    data,label=dataset()           #获取数据集和标签文件
    D1=[1/len(data)]*len(data)     #求每一个样本的初始权重，0.1
    bestpoint=[]                   #保存目前最佳的分割点
    besta=[]                       #保存每一棵基决策树对应的权重
    signall=[]                       #保存每一个最佳分割点对应的符号（大于或小于）
    result=[]                         #保存每个基决策树对样本分类的结果
    for i in range(20):
        ht,sign=mytree(data,label,D1)   #当前最好的树
        signall.append(sign)            #保存记号
        bestpoint.append(ht[0])         #保存当前最佳分割点
        if sign==str('>'):
            Gm= np.array(data > ht[0])
            Gm = (Gm+0) + (Gm-1)
        else:
            Gm= np.array(data < ht[0])
            Gm = (Gm+ 0) + (Gm- 1)       #样本带入树中得到当前样本结果

        a=0.5*(math.log((1-ht[1])/ht[1]))    #通过误差计算得到基决策树权值
        besta.append(a)
        result.append(Gm)
        D1=Zm1(label,Gm,a,D1)                #计算得到每个样本点的权值

        sum1=[0]*len(data)              #以下循环计算当前结果是否达到最优
        for i in range(len(result)):
            sum1+=result[i]*besta[i]     #result=w1f(x1)+w2f(x2)+..
        sum1 = np.array(sum1>=0)
        sum1 = (sum1 + 0) + (sum1- 1)

        if sum(sum1==label)==len(data):    #如果结果相等，则输出以下语句
            print("一种生成{}棵基函数".format(len(result)))
            for i in range(len(result)):
                dic = {}
                print ("第{}棵决策树是".format(i+1))
                if signall[i]==str('>'):
                    dic['num'+'>' + str(bestpoint[i])]=1
                    dic['num'+'<' + str(bestpoint[i])] = -1
                if signall[i] == str('<'):
                    dic['num'+'<' + str(bestpoint[i])] = 1
                    dic['num'+'>' + str(bestpoint[i])] = -1
                print(dic)
                print ("权值是{}".format(besta[i]))
                print()
            break

adaboot1()

代码来源:https://blog.csdn.net/qq_37960402/article/details/88539253

8.3 Bagging与随机森林

为了提高泛化能力，要尽可能使基学习器相对独立，对训练样本进行采样以产生若干个不同的子集，对每一个子集训练一个基学习器；又为了进行有效的学习获得较好的集成，子集不能完全不同，因此使用子集之间相互有交叠的采样方法。

1. Bagging

bagging 是一种个体学习器之间不存在强依赖关系、可同时生成的并行式集成学习方法。

bagging基于自助采样法(bootstrap sampling)，即给定包含m个样本的数据集，先随机从样本中取出一个样本放入采样集中，再把该样本返回初始数据集，使得下次采样时该样本仍可以被选中。这样，经过m次随机采样，就可以得到包含m个样本的采样集，初始数据集中有的样本多次出现，有的未出现。训练集中约有63.2%的样本出现在采样集中。

上面的操作进行T次得到T个每个含m个样本的采样集，基于每个采样集训练一个基学习器，一共训练出T个，再将基学习器进行组合。这就是Bagging的基本流程。在对输出进行预测时，Bagging通常对分类进行简单投票法，对回归使用简单平均法。在分类中，若出现票数相同的情况，则随机取一个。

Bagging的基本流程

Bagging的优点：

• Bagging 是一个很高效的集成学习算务。
• 与标准 AdaBoost 只适用于二分类任务不间，Bagging能不经修改地用于多分类、回归等任务。
• 每个基学习器使用63.2%的数据，所以剩下36.8%的数据可以用来做验证集来对泛化性能进行“包外估计”(out-of-bag estimate)。
  进行包外估计，需要记录每个基学习器所使用的样本。
  令D_t表示h_t实际使用的训练样本集，令H_oob(x)表示对样本x的包外预测，即仅考虑剩余未使用的x训练的基学习器在x上的预测
  包外样本(剩余的样本)有其他用途
  当基学习器是决策树时，可以使用包外样本来辅助剪枝；
  当基学习器是神经网络，可用包外样本来辅助早停以减少过拟合。

从偏差-方差的角度来说，boosting主要关注减小偏差，而Bagging主要关注降低方差，也就说明boosting在弱学习器上表现更好，而降低方差可以减小过拟合的风险，所以Bagging通常在强分类和复杂模型上表现得很好。举个例子：bagging在不减枝决策树、神经网络等易受样本扰动的学习器上效果更为明显。

2. 随机森林

随机森林是Bagging算法的进化版，对bagging进行了改进。
随机森林RF以决策树为基学习器构建Bagging集成的基础上，进一步在决策数训练过程中引入了随机属性选择。

具体来说，传统决策树在选择划分属性时是在当前结点的属性集合(假定有d个属性)中选择一个最优属性;
而在RF中，对基决策树的每个结点，先从该结点的属性集合中随机选择一个包含k个属性的子集，然后再从子集中选择一个最优属性用于划分。

k描述了随机性的引入程度。若k=d，则决策树的构建与传统决策树相同；若k=1，则随机选择一个属性用于划分；一般情况，k=long₂d。

RF的优点
随机森林中基学习器的多样性不仅来自样本扰动，还来自属性扰动，这就使得最终集成的泛化性能可通过个体学习器之间差异度的增加而进一步提升。

RF与Bagging的比较

8.4 结合策略

通过上面对个体学习器产生的方式了解之后，我们来看一下个体学习器的结合。
结合有以下三个好处：
1）结合多个学习器可以提升泛化性能。
2）多个学习器结合可以降低陷入槽糕局部极小点的风险。
3）结合多个学习器，可以扩大假设空间，学得更好的近似。

结合策略如下
假定集成包含T个基学习器{h₁,h₂,……,h_T}，其中h_i在样例x上的输出为h_i(x)。

1. 平均法

对数值型输出h_i(x)∈R，常用的是平均法。

• 简单平均法

• 加权平均法
  

  
  加权平均法不一定优于简单平均法。一般在个体学习器性能相差较大时宜使用加权平均法，而在个体学习器性能相近时宜使用简单平均法。

2. 投票法

对分类来说，学习器h_i将从类别集合C={c₁,c₂,……,c_N}中预测出一个类别标记，最常用的是投票法。为便于讨论，我们将h_i在样本x上的预测输出表示为一个N维向量(h_i¹(x),h_i²(x),……,h_i^N(x))，其中h_i^j(x)是h_i在类别标记c_j上的输出。

• 绝对多数投票法

• 相对多数投票法

• 加权投票法

3. 学习法

当数据很多时，可以通过另一个学习器来结合，即学习法。其中典型代表为Stacking，在stacking中我们把个体学习器称为初级学习器，用于结合的学习器称为次学习器或者元学习器。

Stacking的主要思想为：先从初始数据集训练出初级学习器，然后“生成”一个新的数据集用于训练次级学习器。生成的新数据中，初级学习器的输出被当做样例输入特征，而初始样本的标记仍被当做样例标记。

在训练阶段，次级学习器的训练数据集是利用初级学习器来产生的，若直接用初级学习器的训练集来产生训练数据集，则很有可能会出现过拟合；所以一般在使用Stacking时，采用交叉验证或留一法的方式，用训练初级学习器未使用的样本来产生次级学习器的训练样本。
如以k折交叉验证法为例。初始训练集D被随机分为k个大小相同的子集D₁,D₂,……,D_k。令D_j和D^_j=D/D_j(D_j的补集)分别表示第j折的测试集和训练集。
给定T个初级学习算法，初级学习器h_t^j 在训练集D^_j 上使用第t个学习算法而得。对测试集D_j中每个样本x_i，令z_it=h_t^j(x_i)，即x_i在初始学习器h_t上的输出记为z_it，则由x_i产生的次级训练集的样例部分为z_i=(z_i1,z_i2,……,z_iT)，而标记部分为y_i。那么在整个过程结束之后，从T个初级学习器产生的次级训练集就是D'={(z_i,y_i)}^m_i=1，最后将次级训练集用于训练次级学习器。

8.5 多样性

1. 误差-分歧分解

上面的推导只适用于回归学习，难以推广到分类学习。

2. 多样性度量

多样性度量(diversity measure)是用于度量集成中个体分类器的多样性，即估算个体学习器的多样化程度。

• 不合度量

  
  

• 相关系数

  
  

• Q-统计量

  
  

• k-统计量

  
  

3. 多样性增强

增强多样性的方法有：

• 数据样本扰动
  给定初始数据集，可从中产生出不同的数据子集，再利用不同的数据子集训练出不同的个体学习器。如boosting 和bagging，这种方法对“不稳定学习器”（例如，决策树，神经网络）很有效。对于稳定基学习器，如 线性学习器，支持向量机，朴素贝叶斯往往使用输入属性扰动。
• 输入属性扰动
  训练样本通常由一组属性描述，不同的“子空间”提供了观察数据的不同视角。从不同子空间训练出的个体学习器必然有所不同。子空间一般指从初始的高维属性空间投影产生的低维属性空间。若数据只包含少量属性，或者冗余属性很少，则不宜使用输入属性扰动法.
• 输出表示扰动
  基本思路是对输出表示进行操纵以增强多样性。可对训练样本
  的类标记稍作变动，如翻转法（Flipping Output），随机改变一些训练样本的标记；也可对输出表示进行转化，如“输出调制法”（Output Smearing)。
• 算法参数扰动
  通过随机设置不同的参数可以产生不同的基学习器。对参数较少的算法，可通过将其学习过程中某些环节用其他类似方式代替?从而达到扰动的目的，例如可将决策树使用的属性选择机制替换成其他的属性选择机制。