集成学习
 
一、集成学习算法简介
 
1.什么是集成学习
 
 
2.复习：机器学习的两个核心任务
 
 
3.集成学习中boosting和Bagging
 
 
4.小结
 
 
二、Bagging和随机森林
 
1.Bagging集成原理
 

 
 
 
 
 
 
2.随机森林构造过程
 

 
 
三、包外估计 (Out-of-Bag Estimate)
 
 
1.包外估计的定义
 

 
 
2.包外估计的用途
 
 
3.随机森林api介绍
 

 
 
 
4.随机森林预测案例
 

 
 
5.bagging集成优点
 
 
6.小结
 
 
四、otto案例介绍 – Otto Group Product Classification Challenge
 
1.背景介绍
 

 
 
2.数据集介绍
 
 
3.评分标准
 
 
4.实现过程
 
流程分析
 
 
代码实现
 
具体见【[RF]OTTO Group Product Classification Challenge.ipynb】
 
五、Boosting
 
1.什么是boosting
 
 
2.实现过程：
 

 
 
 
 
 
 
3.bagging集成与boosting集成的区别：
 
 
4.AdaBoost介绍
 
构造过程细节
 

 
 
关键点剖析
 
 
案例：
 

 
 
 
 
 
api介绍
 
 
5.小结
 
 
六、GBDT介绍
 
 
1.Decision Tree：CART回归树
 
 
回归树生成算法（复习）
 
 
2.Gradient Boosting： 拟合负梯度
 

 
 
 
 
3.GBDT算法原理
 

 
 
4.实例介绍
 
数据介绍
 
 
模型训练
 
设置参数：
 
 
开始训练
 

 
 
 
 
 
 
 
 
 
 
5.小结
 

一 集成学习简介
 
集成学习（ensemble learning）通过构建并结合多个学习器来完成学习任务。
 
如何产生“好而不同”的个体学习器，是集成学习研究的核心。
 
集成学习的思路是通过合并多个模型来提升机器学习性能，这种方法相较于当个单个模型通常能够获得更好的预测结果。这也是集成学习在众多高水平的比赛如奈飞比赛，KDD和Kaggle，被首先推荐使用的原因。
 
一般来说集成学习可以分为三大类：
 
用于减少方差的bagging
用于减少偏差的boosting
用于提升预测结果的stacking
集成学习方法也可以归为如下两大类：
 
串行集成方法，这种方法串行地生成基础模型（如AdaBoost）。串行集成的基本动机是利用基础模型之间的依赖。通过给错分样本一个较大的权重来提升性能。
并行集成方法，这种方法并行地生成基础模型（如Random Forest）。并行集成的基本动机是利用基础模型的独立性，因为通过平均能够较大地降低误差。
大部分集成模型都通过一个基础学习算法来生成一个同质的基础学习器，即同类型的学习器，也叫同质集成。
 
有同质集成就有异质集成，为了集成后的结果表现最好，异质基础学习器需要尽可能准确并且差异性够大。
 
 
二 Bagging
 
 
Bagging是引导聚合的意思。减少一个估计方差的一种方式就是对多个估计进行平均。例如，我们可以用训练集的不同子集（随机选择并替代训练集）训练M个不同的树然后计算最后的结果：
 
Bagging使用装袋采样来获取数据子集训练基础学习器。通常分类任务使用投票的方式集成，而回归任务通过平均的方式集成。
 
1）从原始样本集中抽取训练集。每轮从原始样本集中使用Bootstraping（有放回）的方法抽取n个训练样本（在训练集中，有些样本可能被多次抽取到，而有些样本可能一次都没有被抽中）。共进行k轮抽取，得到k个训练集。（我们这里假设k个训练集之间是相互独立的，事实上不是完全独立）
 
2）每次使用一个训练集得到一个模型，k个训练集共得到k个模型。但是是同种模型。（注：，k个训练集虽然有重合不完全独立，训练出来的模型因为是同种模型也是不完全独立。这里并没有具体的分类算法或回归方法，我们可以根据具体问题采用不同的分类或回归方法，如决策树、感知器等）
 
3）对分类问题：将上步得到的k个模型采用投票的方式得到分类结果；对回归问题，计算上述模型的均值作为最后的结果。（所有模型的重要性相同）
 
对于Bagging需要注意的是，每次训练集可以取全部的特征进行训练，也可以随机选取部分特征训练，例如随机森林就是每次随机选取部分特征
 
 
 
常用的集成算法模型是随机森林和随机树
 
在随机森林中，每个树模型都是装袋采样训练的。另外，特征也是随机选择的，最后对于训练好的树也是随机选择的。
 
这种处理的结果是随机森林的偏差增加的很少，而由于弱相关树模型的平均，方差也得以降低，最终得到一个方差小，偏差也小的模型。
 
 
在一个极端的随机树算法中，随机应用的更为彻底：训练集分割的阈值也是随机的，即每次划分得到的训练集是不一样的。这样通常能够进一步减少方差，但是会带来偏差的轻微增加。
 
 
 
下面通过应用Iris数据集的分类问题来距离说明bagging。
 
我们可以使用两种基础模型：决策树和KNN。图中展示了基础模型与集成模型学习得到的决策边界。
 
Accuracy: 0.63 (+/- 0.02) [Decision Tree]      Accuracy: 0.64 (+/- 0.01) [Bagging Tree]
 
Accuracy: 0.70 (+/- 0.02) [K-NN]                 Accuracy: 0.59 (+/- 0.07) [Bagging K-NN]
 
 
 
 
决策树学到的是轴平行边界，然而k=1最近邻对数据拟合的最好。bagging通过训练10个基础模型能过随机选择80%的数据作为训练集，同样随机选择80%的特征进行训练。
 
 
决策树bagging集成相比K-NN bagging集成获得了更高的准确率。K-NN对于训练样本的扰动并不敏感，这也是为什么K-NN成为稳定学习器的原因。
 
整合稳定学习器对于提升泛化性能没有帮助。
 
图像结果同样展示了通过增加集成模型的个数带来的测试准确率变化。基于交叉验证的结果，我们可以看到整合基础模型个数大于10个之后性能就基本不再提升了，只是带来了计算复杂度的增加。
 
最后一张图绘制的是集成学习模型的学习曲线，注意训练集数据的平均误差为0.3，在对训练集做80%采样的时候训练集和验证集误差最小。
 
 
三 Boosting
 
 
Boosting指的是通过算法集合将弱学习器转换为强学习器。boosting的主要原则是训练一系列的弱学习器，所谓弱学习器是指仅比随机猜测好一点点的模型，例如较小的决策树，训练的方式是利用加权的数据。在训练的早期对于错分数据给予较大的权重。
 
对于训练好的弱分类器，如果是分类任务按照权重进行投票，而对于回归任务进行加权，然后再进行预测。boosting和bagging的区别在于是对加权后的数据利用弱分类器依次进行训练。
 
 
 
 
  
boosting是一族可将弱学习器提升为强学习器的算法，这族算法的工作机制类似：
 
  
先从初始训练集训练出一个基学习器；
再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注；
基于调整后的样本分布来训练下一个基学习器；
重复进行上述步骤，直至基学习器数目达到事先指定的值T，最终将这T个基学习器进行加权结合。
 
 
 
下面描述的算法是最常用的一种boosting算法，叫做AdaBoost，表示自适应boosting。
 
 
AdaBoost算法每一轮都要判断当前基学习器是否满足条件，一旦条件不满足，则当前学习器被抛弃，且学习过程停止。
 
AdaBoost算法中的个体学习器存在着强依赖关系，应用的是串行生成的序列化方法。每一个基生成器的目标，都是为了最小化损失函数。所以，可以说AdaBoost算法注重减小偏差。
 
由于属于boosting算法族，采用的是加性模型，对每个基学习器的输出结果加权处理，只会得到一个输出预测结果。所以标准的AdaBoost只适用于二分类任务。
 
 
我们可以看到第一个分类器y1(x)是用相等的权重系数进行训练的。在随后的boosting中，错分的数据权重系数将会增加，正确分类的数据权重系数将会减小。
 
epsilon表示单个分类器的加权错误率。alpha是分类器的权重，正确的分类器alpha较大。
 
 
 
AdaBoost算法的表现如上图所示。每个基础模型包含一个深度为1的决策树，这种决策树依靠线性划分进行分类，决策平面跟其中一个轴平行。上图还展示了集成规模的增加带来的测试准确率变化以及训练和测试集的学习曲线。
 
 
梯度树提升（Gradient Tree Boosting）是一个boosting算法在损失函数上的泛化。能够用于分类和回归问题。Gradient Boosting采用串行方式构建模型。
 
 
每新增一个决策树hm(x)都尽可能的选择是的当前模型Fm-1(x)损失最小的那个：
 
 
注意：分类和回归使用的损失函数有所差别。
 
 
Bagging，Boosting二者之间的区别
 (1) 样本选择：
 
Bagging：训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的。
 Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化，而权值是根据上一轮的分类结果进行调整。
 
(2) 样例权重：
 
Bagging：使用均匀取样，每个样例的权重相等。
 Boosting：根据错误率不断调整样例的权重，错误率越大则权重越大。
 
(3) 预测函数：
 
Bagging：所有预测函数的权重相等。
 Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重。
 
(4) 并行计算：
 
Bagging：各个预测函数可以并行生成
 Boosting：各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果。
 
 
四 Stacking（堆叠）
 
Stacking是通过一个元分类器或者元回归器来整合多个分类模型或回归模型的集成学习技术。基础模型利用整个训练集做训练，元模型将基础模型的特征作为特征进行训练。
 
基础模型通常包含不同的学习算法，因此stacking通常是异质集成。算法伪代码如下：
 
 
 
各基础模型的预测结果如下：
 
Accuracy: 0.91 (+/- 0.01) [KNN]
 
Accuracy: 0.91 (+/- 0.06) [Random Forest]
 
Accuracy: 0.92 (+/- 0.03) [Naive Bayes]
 
Accuracy: 0.95 (+/- 0.03) [Stacking Classifier]
 
Stacking集成效果如上图所示。分别在K-NN，Random Forest,Naive Bayes做训练和预测，然后将其输出结果作为特征，利用逻辑回归作为元模型进一步训练。如图所示，stacking集成的结果由于每个基础模型，并且没有过拟合。
 
Stacking被Kaggle竞赛获奖者广泛使用。例如，Otto Group Product分类挑战赛的第一名通过对30个模型做stacking赢得了冠军。他将30个模型的输出作为特征，继续在三个模型中训练，这三个模型XGBoost，Neural Network和Adaboost，最后再加权平均。详见文章(https://www.kaggle.com/c/otto-group-product-classification-challenge/discussion/14335)。
 
结构如下：
 
 
 
Stacking的两种思想
 
第一种思想：
 
假设有12000条数据样本，将样本集分为训练集(training data)10000条和测试集(testing data)2000条。
 第一层： 采用4个模型（假设其分别是RF、ET、GBDT、XGB），分别对训练集进行训练，然后将预测的结果作为下一层的输入。
 
Step1：将训练集分为5折
 1. 分别用第2、3、4、5折训练一个RF，用训练好的RF直接预测第1折训练数据；
 2. 分别用第1、3、4、5折训练一个新的RF，用训练好的RF直接预测第2折训练数据；
 3. 分别用第1、2、4、5折训练一个新的RF，用训练好的RF直接预测第3折训练数据；
 4. 分别用第1、2、3、5折训练一个新的RF，用训练好的RF直接预测第4折训练数据；
 5. 分别用第1、2、3、4折训练一个新的RF，用训练好的RF直接预测第5折训练数据；
 训练后，可以得到10000 个1维的RF对training data的预测结果，对于testing data，用上面训练得到的5个RF，预测出2000 个5维的预测结果，然后对其取平均生成2000个1维的RF预测结果。
 
Step2：另外ET、GBDT、XGB  3个模型同理。
 最终第一层中，training data会输出10000个4维的预测结果，将这个结果作为第二层训练集的输入。testing data 会输出2000个4维的结果，将这个结果作为第二层预测集的输入。
 第二层： 将上一层的结果带入新的模型中，进行训练再预测，第二层的模型一般为了防止过拟合会采用简单的模型(如 LR).
 
 
 
 
 
第二种思想： 
 
第二层的输入数据，除了第一层的训练结果外，还包括了原始特征。
 
 
 
 
五 Blending
 
Blending与Stacking大致相同，只是Blending的主要区别在于训练集不是通过K-Fold的CV策略来获得预测值从而生成第二阶段模型的特征，而是建立一个Holdout集，例如10%的训练数据，第二阶段的stacker模型就基于第一阶段模型对这10%训练数据的预测值进行拟合。说白了，就是把Stacking流程中的K-Fold CV 改成 HoldOut CV。
 
 
Stacking和Blending对比
 
1.Blending方式和Stacking方式很类似,相比Stacking更简单点,两者区别是:
 
*blending是直接准备好一部分10%留出集只在留出集 上继续预测,用不相交的数据训练不同的Base Model ,将它们的输出取(加权)平均。实现简单,但对训练数据利用少了。
 
2.blending的优点是:比stacking简单,不会造成数据穿越(所谓数据创越,就比如训练部分数据时候用了全局的统计特征,导致模型效果过分的好) , generaliers和Istackers使用不同的数据,可以随时添加其他模型到blender中。
 
3.缺点在于: blending只使用了一部分数据集作为留出集进行验证 ,而stacking使用多折交叉验证,比使用单-留出集更加稳健
 
4.两个方法都挺好,看偏好了, 可以一部分做Blending.-部分做Stacking。
 
 
 
 
结合策略
 
 
 
 
  
集成学习的第二类模型，为了提高集成的泛化能力，每个基学习器之间不存在很强的依赖性，所以最终预测结果时，需要一定的策略对T个结果进行结合。下面介绍结合策略。
 
  
平均法
 
  
对数值型输出，最常见的结合策略是使用平均法。
 
  
简单平均法
加权平均法
 但是对于规模比较大的集成来说，权重参数比较多，较容易导致过拟合。加权平均法未必一定优于简单平均法。
  
一般而言，在个体学习器性能相差较大时，宜使用加权平均法，而在个体学习器性能相近时，宜使用简单平均法。
 
  
这一点在第二个项目中深有体会，该模型有三个损失函数，每个损失函数的性能差别比较大，所以用了加权，在第一个数据集中调好参数以后，在第二个数据集中，效果就不是很好，需要重新进行调参。
 
  
投票法
 
  
绝对多数投票法
 若某标记得票过半数，则预测为该标记；否则拒绝预测。
相对多数投票法
 预测为得票最多的标记。若同时有多个标记获得最高票，则从中随机选取一个。
加权投票法
  
学习法
 
  
当训练数据很多时，一种更为强大的结合策略是使用“学习法”，即通过另一个学习器来进行结合。
 
 
 
 
代码
 
本文的代码参见： ipython notebook.
 
 
总结
 
除了本文所提到的集成学习研究之外，集成学习还被广泛应用于利用多种分类器做训练的深度学习模型中。深度学习模型中的分类器可能在架构、超参数以及训练技巧上存在差异，都可以进行集成。
 
集成学习已经被证明在Kaggle数据科学竞赛中能够获得较好的成绩。
 
 
推荐阅读
 
Zhi-Hua Zhou, “Ensemble Methods: Foundations and Algorithms”, CRC Press, 2012
L. Kuncheva, “Combining Pattern Classifiers: Methods and Algorithms”, Wiley, 2004
Kaggle Ensembling Guide
Scikit Learn Ensemble Guide
S. Rachka, MLxtend library
Kaggle Winning Ensemble
 
参考：
 
https://blog.statsbot.co/ensemble-learning-d1dcd548e936
 
https://www.jianshu.com/p/0a23d578ac81
 
 
 
 
 

集成学习(ensemble learning)可以说是现在非常火爆的机器学习方法了。它本身不是一个单独的机器学习算法，而是通过构建并结合多个机器学习器来完成学习任务。也就是我们常说的“博采众长”。集成学习可以用于分类问题集成，回归问题集成，特征选取集成，异常点检测集成等等，可以说所有的机器学习领域都可以看到集成学习的身影。本文就对集成学习的原理做一个总结。
 
1. 集成学习概述
 
　　　　从下图，我们可以对集成学习的思想做一个概括。对于训练集数据，我们通过训练若干个个体学习器，通过一定的结合策略，就可以最终形成一个强学习器，以达到博采众长的目的。
 
 
　　　　也就是说，集成学习有两个主要的问题需要解决，第一是如何得到若干个个体学习器，第二是如何选择一种结合策略，将这些个体学习器集合成一个强学习器。
 
2. 集成学习之个体学习器
 
　　　　上一节我们讲到，集成学习的第一个问题就是如何得到若干个个体学习器。这里我们有两种选择。
 
　　　　第一种就是所有的个体学习器都是一个种类的，或者说是同质的。比如都是决策树个体学习器，或者都是神经网络个体学习器。第二种是所有的个体学习器不全是一个种类的，或者说是异质的。比如我们有一个分类问题，对训练集采用支持向量机个体学习器，逻辑回归个体学习器和朴素贝叶斯个体学习器来学习，再通过某种结合策略来确定最终的分类强学习器。
 
　　　　目前来说，同质个体学习器的应用是最广泛的，一般我们常说的集成学习的方法都是指的同质个体学习器。而同质个体学习器使用最多的模型是CART决策树和神经网络。同质个体学习器按照个体学习器之间是否存在依赖关系可以分为两类，第一个是个体学习器之间存在强依赖关系，一系列个体学习器基本都需要串行生成，代表算法是boosting系列算法，第二个是个体学习器之间不存在强依赖关系，一系列个体学习器可以并行生成，代表算法是bagging和随机森林（Random Forest）系列算法。下面就分别对这两类算法做一个概括总结。
 
3. 集成学习之boosting
 
　　　　boosting的算法原理我们可以用一张图做一个概括如下：
 
 
　　　　从图中可以看出，Boosting算法的工作机制是首先从训练集用初始权重训练出一个弱学习器1，根据弱学习的学习误差率表现来更新训练样本的权重，使得之前弱学习器1学习误差率高的训练样本点的权重变高，使得这些误差率高的点在后面的弱学习器2中得到更多的重视。然后基于调整权重后的训练集来训练弱学习器2.，如此重复进行，直到弱学习器数达到事先指定的数目T，最终将这T个弱学习器通过集合策略进行整合，得到最终的强学习器。
 
　　　　Boosting系列算法里最著名算法主要有AdaBoost算法和提升树(boosting tree)系列算法。提升树系列算法里面应用最广泛的是梯度提升树(Gradient Boosting Tree)。AdaBoost和提升树算法的原理在后面的文章中会专门来讲。
 
4. 集成学习之bagging
 
　　　　Bagging的算法原理和 boosting不同，它的弱学习器之间没有依赖关系，可以并行生成，我们可以用一张图做一个概括如下：
 
 
　　　　从上图可以看出，bagging的个体弱学习器的训练集是通过随机采样得到的。通过T次的随机采样，我们就可以得到T个采样集，对于这T个采样集，我们可以分别独立的训练出T个弱学习器，再对这T个弱学习器通过集合策略来得到最终的强学习器。
 
　　　　对于这里的随机采样有必要做进一步的介绍，这里一般采用的是自助采样法（Bootstap sampling）,即对于m个样本的原始训练集，我们每次先随机采集一个样本放入采样集，接着把该样本放回，也就是说下次采样时该样本仍有可能被采集到，这样采集m次，最终可以得到m个样本的采样集，由于是随机采样，这样每次的采样集是和原始训练集不同的，和其他采样集也是不同的，这样得到多个不同的弱学习器。
 
　　　　随机森林是bagging的一个特化进阶版，所谓的特化是因为随机森林的弱学习器都是决策树。所谓的进阶是随机森林在bagging的样本随机采样基础上，又加上了特征的随机选择，其基本思想没有脱离bagging的范畴。bagging和随机森林算法的原理在后面的文章中会专门来讲。
 
5. 集成学习之结合策略
 
　　　　在上面几节里面我们主要关注于学习器，提到了学习器的结合策略但没有细讲，本节就对集成学习之结合策略做一个总结。我们假定我得到的T个弱学习器是
 
5.1 平均法
 
　　　　对于数值类的回归预测问题，通常使用的结合策略是平均法，也就是说，对于若干和弱学习器的输出进行平均得到最终的预测输出。
 
　　　　最简单的平均是算术平均，也就是说最终预测是
 
　　　　如果每个个体学习器有一个权重
 
，则最终预测是
 
　　　　其中
 
是个体学习器的权重，通常有
 
5.2 投票法
 
　　　　对于分类问题的预测，我们通常使用的是投票法。假设我们的预测类别是
 
,对于任意一个预测样本x，我们的T个弱学习器的预测结果分别是
 
。
 
　　　　最简单的投票法是相对多数投票法，也就是我们常说的少数服从多数，也就是T个弱学习器的对样本x的预测结果中，数量最多的类别
 
为最终的分类类别。如果不止一个类别获得最高票，则随机选择一个做最终类别。
 
　　　　稍微复杂的投票法是绝对多数投票法，也就是我们常说的要票过半数。在相对多数投票法的基础上，不光要求获得最高票，还要求票过半数。否则会拒绝预测。
 
　　　　更加复杂的是加权投票法，和加权平均法一样，每个弱学习器的分类票数要乘以一个权重，最终将各个类别的加权票数求和，最大的值对应的类别为最终类别。
 
5.3 学习法
 
　　　　上两节的方法都是对弱学习器的结果做平均或者投票，相对比较简单，但是可能学习误差较大，于是就有了学习法这种方法，对于学习法，代表方法是stacking，当使用stacking的结合策略时， 我们不是对弱学习器的结果做简单的逻辑处理，而是再加上一层学习器，也就是说，我们将训练集弱学习器的学习结果作为输入，将训练集的输出作为输出，重新训练一个学习器来得到最终结果。
 
　　　　在这种情况下，我们将弱学习器称为初级学习器，将用于结合的学习器称为次级学习器。对于测试集，我们首先用初级学习器预测一次，得到次级学习器的输入样本，再用次级学习器预测一次，得到最终的预测结果。
 
 
 
　　　　以上就是集成学习原理的一个总结，后面会分别对Adaboost, 提升树，bagging和随机森林的算法原理做一个总结，敬请期待。

 
文章目录
 
集成学习
AdaBoost
代码
  
Bagging与随机森林
Bagging
随机森林(Random Forest)
  
结合策略
增加多样性的策略
多样性度量

 
集成学习
 
​ 之前已经讲过了好几个学习算法，或者说分类器、模型。都能达到一定的分类效果，俗话说的好：三个臭皮匠赛过诸葛亮。集成学习就是想将不同的学习算法集成在一起来工作，以期达到$1+1\ge 2$的效果。
 
​ 集成学习一般的结构为：
 
 
​ 个体学习期就是之前说过的各种各样的学习器：决策树、线性模型、支持向量机、贝叶斯分类器等。
 
如果所有的个体学习器都相同，这样的集成学习就是“同质”集成学习，个体学习器被称为“基学习器”或者“基学习算法”
如果所有的个体学习器不同，这样的集成学习就是“异质”集成学习，个体学习器就不被称为“基学习器”了。
 
​ 从上面的图中可以看出，集成学习的重点部分就是在于各个个体徐诶器的结合策略。和足球队一样，大家要取长补短才能达到$1+1\ge 2$的效果。
 
​ 比如下图中有三个个体学习器：$h1,h2,h3$，如果结合策略采用最基本的“少数服从多数”的策略的话，根据不同的情况，同样的集成策略会有完全不同的效果。
 
 
​ 另外还有一个问题就是，到底用多少个学习器会比较合适呢？《机器学习》上给出了一个数学推导。
 
假设每个基学习器(同质集成学习)的错误率是$ϵ$，也就是$P(h_i(x)\ne f(x))=ϵ$
我们使用T个基学习器进行整合，通过简单的投票规则进行整合，以超过半数的结果为准。 那么集成的错误率就是:
 
$$\begin{gathered} P(H(x)\ne f(x))=\sum _{k=0}^{T/2}(\begin{array}{c}T\\ k\end{array})(1-ϵ{)}^k{ϵ}^{T-k} \\ \le exp(-\frac{1}{2}T(1-2ϵ{)}^2) \end{gathered}$$
 
​ 从这个式子看出，如果T越大，错误率就会越低。
 
但是，这里的一个前提是所有的学习器都是相互独立的。而我们面对同一个问题而训练出来的学习器都是基于相同的数据，或者是通过某种划分策略选出来的训练样本，所以不可能是相互独立的。因此，直接增加基学习器的数量是无法直接达到提高准确率的。
 
​ 学习器的集成方法一般分成两种：
 
串行的、强依赖的方式：AdaBoost
并行的、低依赖的方式：Bagging与随机森林
 
AdaBoost
 
​ 书中的AdaBoost算法是基于同质集成学习来进行讨论的。
 
​ AdaBoost是基于以下的思路进行集成：
 
依次训练若干个(T个)基学习算法。
为训练集中的每个样本分配相应的权重，这些权重在每一次训练可以视作为一种分布$D$。
在前一个学习器训练完之后，更新样本的权重，使得在第一次学习器中分类失败的样本权重升高，分类正确的样本的权重降低。
每个学习器也存在一个权重$\alpha$，权重$\alpha$会根据每次训练的错误率$ϵ$来进行计算。最终得到集成输出$H(x)=sign({\sum }_{t=1}^T{\alpha }_t{h}_t(x))$。
 
​ 书中给出了训练过程的伪代码：
 
 
​ 这里解释下其中几行伪代码的来历：
 
 
第一行初始化权重，每个样本的权重均为1/m。
 
 
第四行是计算训练后学习器的错误率。
 
 
第五行是因为，如果训练错误率小于0.5，对于二分类问题比随机猜测还低，就不值得考虑了。语境中的弱学习器也是要高于0.5的正确率的。
 
 
第六行是根据错误率来计算当前学习器的权重的。从这个公式来看，错误率越低，相应的权重就会越大。为啥等于这个公式，我没怎么看懂就接受了这个结论，有兴趣的朋友可以去琢磨一下。
 
 
第7行是为下一次迭代计算样本权重。按照AdaBoost的思路，下一次的迭代在最好情况下应该可以修复掉前一轮的所有错误样本分类。这里解释一下东西：当$h_t(x)=f(x)$时，$h_t(x)\ast f(x)=1$，因为作为一个二分类问题，$h(x)$和$f(x)$符号相同的话，肯定是等于1。所以，当$h_t(x)\ne f(x)$时，$h_t(x)f(x)=-1$。所以根据第7行的公式，先不看$Z_t$的话:
 
$$\begin{gathered} D_{t+1}(x)=D_t(x)\ast e^{-{\alpha }_t},if{h}_t(x)=f(x) \\ {D}_{t+1}(x)=D_t(x)\ast e^{{\alpha }_t},if{h}_t(x)\ne f(x) \end{gathered}$$
 接下来是$Z_t$的问题，书中的解释是一个规范化因子，我不是很理解这个东西，结合《机器学习实战》里面的代码实现，我理解这个东西应该是一个归一化的东西，$D_{t+1}$这个权重向量计算出来之后还是一个分布，也就是${\sum }_{i=1}^m{D}_i=1$。所以我这里参考《机器学习实战》一书中的：$Z_t=\sum D_{i=n}^{m}ti$
 
同样，如果有兴趣得知这个推导过程的可以自行研究，我是没太看明白。
 
 
把所有的学习器训练完之后，输出还是采用$T$个学习器对新样本都输出，针对每个学习器的输出来乘以权重${\alpha }_i$，求和后进行$sign$函数输出。
 
 
标准的AdaBoost只适合二分类问题，如要处理其他问题则需要做一些改造。
 
 
代码
 
def stumpClassify(dataMatrix,dimen,threshVal,threshIneq):#just classify the data
    retArray = ones((shape(dataMatrix)[0],1))
    if threshIneq == 'lt':
        retArray[dataMatrix[:,dimen] <= threshVal] = -1.0
    else:
        retArray[dataMatrix[:,dimen] > threshVal] = -1.0
    return retArray
    

def buildStump(dataArr,classLabels,D):
    dataMatrix = mat(dataArr); labelMat = mat(classLabels).T
    m,n = shape(dataMatrix)
    numSteps = 10.0; bestStump = {}; bestClasEst = mat(zeros((m,1)))
    minError = inf #init error sum, to +infinity
    for i in range(n):#loop over all dimensions
        rangeMin = dataMatrix[:,i].min(); rangeMax = dataMatrix[:,i].max();
        stepSize = (rangeMax-rangeMin)/numSteps
        for j in range(-1,int(numSteps)+1):#loop over all range in current dimension
            for inequal in ['lt', 'gt']: #go over less than and greater than
                threshVal = (rangeMin + float(j) * stepSize)
                predictedVals = stumpClassify(dataMatrix,i,threshVal,inequal)#call stump classify with i, j, lessThan
                errArr = mat(ones((m,1)))
                errArr[predictedVals == labelMat] = 0
                weightedError = D.T*errArr  #calc total error multiplied by D
                #print "split: dim %d, thresh %.2f, thresh ineqal: %s, the weighted error is %.3f" % (i, threshVal, inequal, weightedError)
                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):
    weakClassArr = []
    m = shape(dataArr)[0]
    D = mat(ones((m,1))/m)   #init D to all equal
    aggClassEst = mat(zeros((m,1)))
    for i in range(numIt):
        bestStump,error,classEst = buildStump(dataArr,classLabels,D)#build Stump
        #print "D:",D.T
        alpha = float(0.5*log((1.0-error)/max(error,1e-16)))#calc alpha, throw in max(error,eps) to account for error=0
        bestStump['alpha'] = alpha  
        weakClassArr.append(bestStump)                  #store Stump Params in Array
        #print "classEst: ",classEst.T
        expon = multiply(-1*alpha*mat(classLabels).T,classEst) #exponent for D calc, getting messy
        D = multiply(D,exp(expon))                              #Calc New D for next iteration
        D = D/D.sum()
        #calc training error of all classifiers, if this is 0 quit for loop early (use break)
        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
        if errorRate == 0.0: break
    return weakClassArr,aggClassEst

def adaClassify(datToClass,classifierArr):
    dataMatrix = mat(datToClass)#do stuff similar to last aggClassEst in adaBoostTrainDS
    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'])#call stump classify
        aggClassEst += classifierArr[i]['alpha']*classEst
        print aggClassEst
    return sign(aggClassEst)
 
Bagging与随机森林
 
Bagging
 
​ 上面提到的AdaBoost是串行的进行训练，每个学习器都是使用全部的训练集样本数据。这样使得所有的学习器都没法“独立”。因此，Bagging是与AdaBoost不同的思路，是将所有的样本拆分成T份，用每份数据去训练T个学习器，从而降低学习器之间的关联关系。
 
​ 将样本进行拆分的策略也不是简单的进行M/T的划分，而是采用前面介绍过的
 
​ 进行划分来生成T份训练样本集。对T个学习器的决策输出也是采用基本的投票法(分类)或者简单平均法(回归)进行输出：
 
 
随机森林(Random Forest)
 
​ 如果使用Bagging集成方法，而基学习器为决策树的话(
 
)，再增加一点改造就是随机森林了。所以说随机森林是Bagging集成方法上的一个特殊变体。这点点改造就是指在决策树的基学习器训练过程中，每次创建节点选择最优属性进行划分时，引入一个随机变量$k$。如果令$k=d$，就是普通的决策树，而训练多个决策树后进行集成就是普通的Bagging方法。
 
​ 如果令$k=1$，就是在随机选择一个。每个基学习器通过随机选择增加泛化能力。一般的策略是令$k={\log }_{2}d$。
 
结合策略
 
​ 在对多个个体学习器进行结合输出的时候，这里就涉及到一个决策输出的策略问题，一般来说有如下几种：
 
 
平均法，一般用于回归问题。
 
  
简单平均法：$H(x)=\frac{1}{T}{\sum }_{i=1}^T{h}_i(x)$。
加权平均法：$H(x)=\frac{1}{T}{\sum }_{i=1}^T{w}_i{h}_i(x)$
 
 
投票法，一般用于分类问题。
 
  
绝对多数投票法：若某类别超过半数，则预测为该类别。
相对多数投票法：预测类别为票数最多的那个类别。
加权投票法：为每个学习器给一个权值，然后再进行票数计数。
 
 
学习法，所有的个体学习器称为初级学习器，结合策略时也使用一个学习器，称之为次级学习器。使用初级学习器的输出样本来训练这个次级学习器，最终来做输出。
 
 
增加多样性的策略
 
​ 开篇时讲到的，解决学习器之间的耦合性，让每个学习器尽量的“独立”，是提高集成学习的一个重要手段。
 
数据样本扰动：使用一些例如自助采样的不同的采样方法，对输入的样本数据进行一些挑选，来解决学习器之间的耦合性。
输入属性扰动：如果样本中的一些属性是冗余的，每个不同的学习器使用不同的属性集合进行训练。
输出表示扰动：手动修改一些标记。
算法参数扰动：也就是改一下算法模型的一些参数，增加一些随机变量进去。
 
多样性度量
 
​ 那么怎么评价两个算法是否有耦合性呢？
 
​ 首先列出两个算法之间的预测结果列联表：
 
 
​ $h_i,h_j$表示两个学习器，其中$a+b+c+d=m$。
 
不合度量：$dis{t}_{ij}=\frac{b+c}{m}$，也就是两个学习器不同的样本数有多少，值越大，多样性越大。
相关系数：${\rho }_{ij}=\frac{ad-bc}{\sqrt{(a+b)(a+c)(c+d)(b+d)}}$，如果值为0，则表示$h_i,h_j$无关。
Q-统计量：$Q_{ij}=\frac{ad-bc}{ad+bc}$。
$\kappa$统计量：$\kappa =\frac{p1-p2}{1-p2}$。其中$p1$为两个分类器取得一致的概率：$p1=\frac{a+d}{m}$，$p2$为两个分类器偶然达成一致的概率，若两个分类器完全一致则$\kappa =1$，若只是偶然一致则$\kappa =0$。