一、集成学习介绍

其中的个体学习器就是之前学习的算法：

• 1.决策树算法
• 2.BP神经网络
• 

1、”…集成”表示集成器中只有同种类型的个体学习器。例如，”决策树集成”中全是决策树，”神经网络决策树”中全是神经网络，这时的集成是同质的(homogenous)。同质集成中的个体学习器为”基学习器”，相应的学习算法称为”基学习算法”。(base algorithm)
不同类型的学习器是异质的(heterogenous)，这时的个体学习器称为”组件学习器”(component lerner)。
2、弱学习器(weak learner)相对比与单一的学习器而言有优越的泛化能力。
3、集成学习是通过投票方式进行解决的，例子如下

假设集成通过简单投票法结合个基分类器，若有超过半数的基分类器正确，则集成分类就正确：

其中的函数，将整数变为1，负数变为-1，0仍然为0
4、单个分类器的错误率

假设分类的错误率相互独立，集成学习的错误率为：

推导过程：由基分类器相互独立，假设随机变量为个基分类器分类正确的次数，那么，设为每一个分类器分类正确的次数，则，那么有

证明过程：

根据Hoeffding不等式得知

令得

由式子1可以得到，当集成学习中的个体分类器数目增大时，集成的错误率呈指数级下降，最终趋于0.
但是，基学习器的误差不可能相互独立，因为个体学习器是为了解决同一个问题而训练的，它们之间不可能相互独立。个体学习器的”准确性”和”多样性”时相互冲突的。
根据个体学习器的生成方式，目前集成学习的方法大致分为两大类：

• 1.个体学习器间存在强依赖关系、必须串行生成的并行化方法，代表是Boosting

• 2.个体学习器之间不存在强依赖关系，可同时生成的并行化方法，代表是Bagging和随机森林(Random Forest)

  二、Boosting算法

  、 Boosting算法用于弱学习器(weak learner)提升为强学习器。
  最终的集成学习器是个基学习器的加权结合

  Boosting算法中的AdaBoost算法

  2.1模型

  
  这个式子是集成学习的加性模型，加性模型不采用梯度下降的思想，而是
  
  每次更新求解一个理论上的最优和

  2.2最小化指数损失函数(exponential loss function)

  
  根据后面推导出的结论，每次更新的。
  对这个损失函数的解读

• 1.指数损失函数的含义：为真实的函数，对于分类任务来说，。是预测的数据，当与符号一致的时候，。我们成这个为预测的信心，当信心越大时，损失函数越小。

• 2.符号的含义：为概率分布，可简单理解为在数据集中进行一次随机抽样，每个样本被取到的概率；为经典的期望，则综合起来表示在概率分布上的期望，可简单理解为对数据集以概率进行加权后的期望。即：

上述式子说明损失函数是每个损失函数按照概率分布进行加权后得到的。

2.3 目标是使损失函数最小化

这时要考虑对的导数，由上式(3)求解

求导

之后令导数为0，求得的解

因为我们是通过投票法来决定的，带入最开始投票法的公式:

2.4 AbaBoost算法的训练过程

2.4.1 根据指数损失函数找到第一个基分类器

2.4.2 根据指数函数最小化求得权重的更新

对式子(5)求导：

2.4.3 下一个基学习器纠正前面的学习器的错误

对这个损失函数进行处理，使用泰勒展开式

2.4.4 所以达到最小化的学习器

、 此时引进的是一个常数，令表示一个分布

所以式子（6）称为

现在我们用另一个特殊的判断的表达式

其中的表示判断是否成立。

• 如果成立，,；
• 否则，
• 

最终得到理想的基学习器

由此可见，理想将在分布下最小化分类误差。因此弱分类器将基于分布来进行训练，且针对的分类误差将小于0.5，类似残差逼近思想。
且由式子(7)所假设的分布，我们可以得到分类器的分布迭代为

2.4.5 迭代公式

由上面的推到我们得出了迭代过程中的两个更新公式：1.样本分布调整 2.基学习器的调整

Boosting算法要求基学习器对特定的数据分布进行学习，者可通过”重赋权法”(re-weighting)实施，即在训练的过程中，根据样本分布为每个训练样本重新赋予一个权重，对无法接受带权样本的基学习器算法，通过”重采样法”(re-sampling)来处理，即在每一轮学习中，根据样本分布对训练集重新进行采样，再用重采样而得的样本对基学习器训练。

2.4.6 代码

从偏差-方差分解的角度看，Boosting主要关注降低偏差，因此Boosting能基于泛化相当弱的学习器建出很强的集成。对西瓜数据集以决策树桩为基学习器运行AdaBoost算法。
例子链接

function [error_final,D,dataset_final,coefficient] = adoboost(dataset_initial,T)
    dataset_initial = [0,1,2,3,4,5,6,7,8,9;1,1,1,-1,-1,-1,1,1,1,-1];
    dataset = dataset_initial;
    dataset_update = [0,1,2,3,4,5,6,7,8,9];
    %以决策树桩，找到误差率最小的阈值
    %step1 给权值赋予初值
    D(1:size(dataset_initial,2)) = 1/(size(dataset_initial,2));
    %找到第一个基分类器，通过暴力循环，找到误差率最小的阈值
    dataset_final=0;
    for t = 1:T%基分类器个数为T
        number = 1;%每个阈值对应的误差率矩阵的增加标志
         %根据每个阈值找到误差率最小
        for threshold = 0:0.01:9%对每个阈值赋值
            error = 0;
            error1 = 0;
            %需要比较判断然后赋值,需要进行符号的判断
            for i = 1:size(dataset_initial,2)
                if dataset_initial(1,i) <threshold
                    dataset_update(2,i) = 1;
                else
                    if dataset_initial(1,i)>threshold
                        dataset_update(2,i) = -1;
                    end
                end
            end
             for i = 1:size(dataset_initial,2)
                if dataset_initial(1,i) <threshold
                    dataset_update1(2,i) = -1;
                else
                    if dataset_initial(1,i)>threshold
                        dataset_update1(2,i) = 1;
                    end
                end
             end
            for i = 1:size(dataset_initial,2)%计算出误差率
                    if dataset_initial(2,i) ~= dataset_update(2,i)
                        error = D(i)+error;
                    else
                        error = error + 0;
                    end
                    if dataset_initial(2,i) ~= dataset_update1(2,i)
                        error1 = D(i)+error1;
                    else
                        error1 = error1 + 0;
                    end
            end
            error_matrix1(number) = error;
            error_matrix2(number) = error1;
            number = number+1;
        end
    %     if t==1
    %         plot(0:0.01:9,error_matrix);
    %     end
        %判别找到更新的分类数据集和原数据集，找到分类误差率
        %找到最小的误差率和误差率所在位置，从而找到阈值，并且得到根据阈值做出的判断
        [error_minmum1,position1] = min(error_matrix1);
        [error_minmum2,position2] = min(error_matrix2);
        if error_minmum1<error_minmum2
            error_minmum = error_minmum1;
            position = position1;
            flag = 1;
            threshold_flag = 1;
        else
            error_minmum = error_minmum2;
            position = position2;
            flag = 2;
            threshold_flag = -1;
        end
        for i =1:size(dataset_initial,2)
            if dataset(1,i)< (position/100)
                    if flag == 1
                        dataset(2,i) =1;
                    else 
                        dataset(2,i) = -1;
                    end
            else 
                if flag == 1
                    dataset(2,i) = -1;
                else
                    dataset(2,i) =1;
                end
            end
        end
        %通过误差率计算出系数
        coefficient = 0.5*log((1-error_minmum)/error_minmum);
        %更新权值
        Z=0;
        for i = 1:size(dataset_initial,2)
            Z = Z+D(i) *exp(-coefficient*dataset_initial(2,i)*dataset(2,i));%先计算出Z
        end
        for i = 1:size(dataset_initial,2)
            D(i) = D(i)*exp(-coefficient*dataset_initial(2,i)*dataset(2,i));
        end
        D = D/Z;%得到更新的权值
        %使用matlab表示分段函数
        x = dataset(2,:);
        dataset_final=coefficient*x+dataset_final;
    end
    %使用这个计算最终的数据集
    %大于0的为1，小于0的为-1
    for i=1:length(dataset_final)
        if dataset_final(i) >0
            dataset_final(i) =1;
        else 
            if dataset_final(i) ==0
                dataset_final(i)=0;
            else
                dataset_final(i) =-1;
            end
        end
    end
    %比较数据的异同
    number1=0;
    for i=1:length(dataset_final)
        if dataset_final(i) ~= dataset_initial(2,i)
            number1 =number1+1;
        end
    end
    error_final = number1/length(dataset_final)
end

三、Bagging与随机森林

想要使得集成学习有很强的泛化性能，集成学习器之间应该尽可能要相互独立。在现实生活中”独立”是做不到的，因为都是为了解决同一件事情而提出的。为了想办法使得学习器之间相互独立，在给定一个训练数据集的情况下，一种做法是：

由于训练数据不同，我们获得的基学习器具有比较大的差异。然而，为获得好的集成，我们希望个体学习器不能太差。如果采样出的每个子集都完全不同，则每个基学习器只用到了一小部分训练数据，甚至不能有效学习，这显然无法确保出好的基学习器，所以，我们考虑使用相互有交集的采样子集。

评估方法-自助法：

我们希望评估的使用训练出的模型，但在留出法和交叉验证法中，由于保留了一部分样本用于测试，因此实际评估中的模型所使用的训练集比小，必然会引入一些因训练样本规模不同而导致的估计偏差。
留一法受训练规模变化的影响较小，但计算复杂度又太高了。所以要找一种方法：既可以减少训练样本规模不同造成的影响，同时能比较高效地进行实验估计。
显然，在中有一部分样本会在中多次出现，而另一部分样本不出现。可以做一个简单的估计，样本在次采样中始终不被采到的概率是，取极限得到

即通过自助采样，初始数据集中约有的样本未出现在采样数据集中中。于是，我们可以将用作训练集，用作测试集。这样，实际评估的模型与期望评估的模型都是用个训练样本，而我们仍有数据总量约的、没在训练集中出现的样本用于测试，这样的测试结果，亦称为”包外估计”(out-of-bag-estimate)。
自助法在数据集较小、难以有效划分训练/测试集时分有用。此外，自助法能从初始数据集中产生多个不同的训练集，这对集成学习等方法有很大的好处。但是，自助法的数据集改变了初始数据集的分布，这会引入估计偏差。因此，当数据集较大时，留出法和交叉验证法更好。

3.1 Bagging

Bagging算法是使用的是上述的评估方法-自助法，由上面的结论初始数据集中约有的样本未出现在采样数据集中中，可以得到初始训练集中约有的样本出现在采样集中。
所以我们可以采样出个包含个训练样本的采样集，然后训练出一个基学习器，再将基学习器结合。

对预测输出时，

• Bagging通常对分类任务使用简单投票法，如果出现票数相同的情况，最简单的做法是随机选择一个，或者进一步考察学习器投票的置信度来确定最终的胜利者

• Bagging对回归任务使用简单平均法

  3.1.1复杂度

  如果基学习器的计算复杂度未，则Bagging算法的复杂度大致为，考虑到采样与投票/平均过程的复杂度很小，而通常是一个不太大的常数，因此，训练一个Bagging集成与直接使用基学习算法训练一个学习器的复杂度同届，这说明Bagging是一个很高效的集成学习算法，Bagging算法还可以用于多分类、回归任务。

  3.1.2 公式推导

  由上面的公式得到结论：每个基学习器只使用了初始训练集中的样本，剩下约的样本可用作验证集对泛化性能进行”包外估计”(out-of-bag estimate)。
  因此，我们可以：令表示实际使用的训练样本集，令对样本的包外预测，即仅考虑那些未使用训练的基学习在上的预测，有
  
  公式(1)解析：表示对个基学习器，判断结果是否与真是结果一致，的结果一般是，如果基学习器结果与一致，则，如果样本不在训练集内，则，综合起来看，对包外的数据，用投票法选择包外估计的结果，即1或-1.
  则Bagging泛化误差的包外估计为：
  
  公式(2)解析：是对包外的估计，该式表示，得到泛化误差的包外估计。
  包外样本还有其他的一些用途：

• 1.当基学习器是决策树时，可使用包外样本来辅助剪枝，或用于估计决策树中各结点的后验概率以辅助对零训练样本结点的处理

• 2.当基学习器是神经网络时，可使用包外样本来辅助早期停止以减小过拟合风险。

  3.1.3 Bagging 算法的数据

  Bagging算法主要关注降低方差，因此它在不剪枝决策树、神经网络等易受样本扰动的学习器上效用更为明显。我们以基于信息增益划分的决策树为基学习器，在表4.5的西瓜数据集3.0上运行Bagging算法，不同规模的集成及其基学习器所对应的分类边界如图所示：
  

  3.2随机森林

  
  传统的决策树在做选择划分的属性时时在当前结点的属性结合(假设有个属性)中选择一个最优属性（例如：西瓜的声音、密度、尾巴的长短中选择一个属性来划分）；
  在RF（random forest）中，对基决策树的每个结点，先从该结点的属性集合中随机选择包含个属性的子集，然后再从这个子集中选择一个最优属性用于划分。这里的参数控制了随机性的引入程度：若令，则基决策树的构建与传统决策树相同；若令，则是随机选择一个属性用于划分；一般情况下，推荐值
  
  随机森林对Bagging只做了一个小改动，但是与Bagging中基学习器的”多样性”仅通过样本扰动（通过对初始训练集采样）而来不同，随机森林中基学习器的多样性不仅来自样本扰动，还来自属性扰动（因为随机选择个属性），这使得最终集成的泛化性能可通过个体学习器之间差异度的增加而进一步提升。
  
  随机森林的收敛性与Bagging算法比较

• 1.随机森林的收敛性与Bagging相似。

• 2.随机森林的起始性能相对较差，特别是在集成中只包含一个基学习器时，这是因为引入属性扰动，使得随机森林中个体学习器的性能往往有所降低。

• 3.随着个体学习器数目的增加，随机森林通常会收敛到更低的泛化误差，随机森林的训练效率通常优于Baaging。Bagging使用的是”确定型”随机数，在选择属性划分时对个属性进行了考察，而随机森林的”随机型”决策树只需要考察一个属性子集。

  四、结合策略

  使用学习器结合相对于单个学习器的优点在于：

• 1.学习任务假设空间很大，如果有多个假设在训练集上达到了同等的性能，此时使用单学习器可能会因误选导致泛化性能不佳，多个学习器可减小这一风险

• 2.单个学习器往往会陷入局部极小，通过多次运行，降低陷入局部极小的风险
• 3.学习任务的真实假设可能不在当前学习算法考虑的假设空间中，通过结合多个学习器，相应的假设空间有所扩大。

4.1 平均法

对数值型输出，最常见的策略是使用平均法(averaging)

• 简单平均法(simple averaging)

• 加权平均法(weighted averaging)

加权平均法的权重一般是从训练数据中学习而得，现实任务中的训练样本通常不充分或者存在噪声，这将使得学出的权重不完全可靠，尤其是对规模比较大的集成来说，要学习的权重比较多，较容易导致过拟合。加权平均法未必优于简单平均法。一般而言，在个体学习器性能相差较大时适合使用加权平均法，在个体学习器性能相近时适合使用简单平均法。

4.2 投票法

对分类任务，学习器从类别标记集合，将在样本上的预测输出表示为一个维向量，其中是在类别标记上的输出。

4.2.1绝对多数投票法(majority voting)

即若某标记得票过半数，则预测为该标记；否则拒绝预测。

4.2.2 加权投票法(weighted voting)

与加权平均法类似，是的权重，通常。
如果学习任务要求必须提供预测结果，则绝对多数投票法将退化为相对多数投票法。在现实任务中，不同类型个体学习器可能产生不同类型的值，常见的有：

• 类标记：，若将样本预测为类别则取值为1，否则取值为0，使用类标记的投票也称”硬投票”(hard voting)。
• 类概率：，相当于对后验概率的一个估计。使用类概率的投票也称”软投票”(soft voting.

4.3 学习法

4.3.1 Stacking算法

学习法中的代表Stacking算法的描述如下图所示，我们假设初级学习器使用不同学习算法产生，即初级集成是异质的。

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

有研究表明，将初级学习器的输出类概率作为次级学习器的输入属性，用多响应线性回归(Multi-response Linear Regression，简称MLR)作为次级学习算法效果较好，在MLR中使用不同的属性集更佳。

4.3.2 BMA算法

贝叶斯模型平均(Bayes Model Averaging，简称BMA)基于后验概率来为不同模型赋予权重，可视为加权平均法的一种特殊实现。
在对Stacking和BMA算法进行比较的基础上，得到：若数据生成模型恰在当前考虑的模型中，且数据噪声很少，则BMA不差于Stacking；然而，在现实生活中无法确保数据生成模型一定在当前考虑的模型中，甚至可能难以用当前考虑的模型来进行近似，因此,Stacking通常优于BMA，因为其鲁棒性比BMA更好，而且BMA对模型近似误差非常敏感。

8.5 多样性

8.5.1 误差-分歧分解

想要构建泛化能力强的集成学习，个体学习器应当好而不同。我们现在开始理论分析。
假定我们用个体学习器通过加权 平均法结合产生的集成来完成回归学习任务。对示例，定义学习器的”分歧”(ambiguity)为

则集成的”分歧”是

这里的”分歧”项表征了个体学习器在样本上的不一致性，即在一定程度上反映了个个体学习器的多样性。个体学习器和集成的平方误差分别为

令表示个体学习器误差的加权均值，有

上式对所有样本均成立，令表示样本的概率密度，则在全样本上有

类似的，个体学习器在全样本上的泛化误差和分歧项分别为

集成的泛化误差为：

将式子(6-8)代入式子(5)，再令表示个体学习器泛化误差的加权均值，表示个体学习器的加权分歧值，有

式子(9)明确指出：个体学习器准确性越高、多样性越大，则集成越好。上面这个称为”误差-分歧分解”(error-ambiguity decomposition)。
但是，我们不能直接吧作为优化目标求解以此来得到最优的集成，

• 在现实任务中很难直接对进行优化，不仅由于它们是定义在整个样本空间上
• 由于不是一个可直接操作的多样性度量，它尽在集成构造好之后才能进行估计。
• 上面的推导过程只适用于回归学习，难以直接推广到分类学习任务上。

  8.5.2 多样性度量

  多样性度量是用于度量集成中个体分类器的多样性，典型做法是考虑个体分类器的两两相似/不相似性。
  给定数据集，对二分类任务，，分类器和的预测结果列联表(contingency table)为：

其中，表示与均预测为正类的样本数目；含义以此类推；。基于这个列联表，下面给出一些常见的多样性度量

• 不合度量(disagreement measure)

的值域为，值越大则多样性越大。

• 相关系数(correlation coefficient)

的值域为。若与无关，则值为；若与正相关则值为正，否则为负。

• -统计量(Q-statistic)

与相关系数的符号相同，且。

• -统计量（k-statistic）

其中，是两个分类器取得一致的概率，是两个分类器偶然达成一致的概率，它们可由数据集估算：

若分类器与在上完全一致，则；若它们仅是偶然达成一致，则通常为非负值，仅在与达成一致的概率甚至低于偶然性的情况下取负值。
以上介绍的是”成对型”(pairwise)多样性度量，它们可以通过2维图绘制出来。例如著名的”k-误差图”，就是将每一对分类器作为图上的一个点，横坐标是这对分类器的值，纵坐标是它们的平均误差，下图是一个例子。显然，数据点云的位置越高，个体分类器准确性越低；点云的位置越靠右，则个体学习器的多样性越小。

8.5.3 多样性增强

在集成学习中需有效地生成多样性大的个体学习器。与简单地直接用初始数据训练出个体学习器相比，如何增强多样性？一般思路是在学习过程中引入随机性，常见做法是对数据样本、输入属性、输出表示、算法参数进行扰动。

（1）数据样本扰动

• 数据扰动方法通常是基于采样法，在Bagging中使用过自助采样，在AdaBoost使用序列采样。这种方法对常见的基学习器，例如”决策树”、”神经网络”等这样的”不稳定基学习器“很有效

• 对于”线性学习器”、”支持向量机”、”朴素贝叶斯”、”k近邻学习器”这样的”稳定基学习器“(stable base learner)，效果不大，这时需要使用输入属性扰动等其他的方法。

  （2）输入属性扰动

  
  对包含大量冗余属性的数据，在子空间中训练个体学习器不仅可以产生多样性大的个体，还会因属性数量的减少节省时间。同时，冗余属性多，减少一些属性后训练出的个体学习器不会太差。
  若数据只包含少量属性，或者冗余属性很少，则不宜使用属性扰动法。下图，表示算法步骤
  

  （3）输出表示扰动

  此类做法的基本思路是对输出表示进行操纵以增强多样性，可对训练样本的类标记稍作标记

• 如”翻转法”(Flipping Output)随机改变一些训练样本的标记

• 也可对输出表示进行转化，如”输出调制法”(Ouput Smearing)，将分类输出转化为回归输出后构建个体学习器

• 还可以将原任务拆解为多个可同时求解的子任务，如ECOC法利用纠错输出码将多分类任务 拆解为一系列二分类任务来训练基学习器。

  (4)算法参数扰动

  基学习算法一般都有参数需要设置，例如神经网络的隐藏神经元数、初始连接权值等，通过随机设置不同的参数，往往可产生差别较大的个体学习器。

• “负相关法”显示地通过正则化项来强制个体神经网络使用不同的参数

• 对参数较少的算法，可通过其学习过程中某些环节用其他类似方式代替，从而达到扰动的目的。例如，可将决策树使用的属性选择机制替换成其他的属性选择机制