1.两种集成学习范式

根据基本学习器的生成方式，粗略地说，有两种集成方法的范式，即以 AdaBoost 为代表的顺序生成基本学习器的序列可重构方法和以 Bagging为代表的并行集成方法。

顺序学习方法的基本动机是利用基础学习者之间的依赖性，因为总体学习效果可以通过残差递减的方式得到提高。

并行集成方法的基本动机是利用基学习器之间的独立性，因为通过结合独立基学习器可以显著地减少错误。

以 { − 1 , + 1 } \{-1,+1\}{−1,+1} 二分类问题为例，假设真实函数为 f ff ,每个基分类器有独立的泛化误差 ϵ \epsilonϵ ,则对于每个基分类器 h i h_ihi​ 有P ( h i ( x ) ≠ f ( x ) ) = ϵ P\left ( h_i(x)\ne f(x) \right ) =\epsilonP(hi​(x)​=f(x))=ϵ结合 T TT 个这样的基分类器之后，根据H ( x ) = s i g n ( ∑ i = 1 T h i ( x ) ) H(x)=sign\left ( \sum_{i=1}^{T}h_i(x) \right )H(x)=sign(i=1∑T​hi​(x))集成后的 H HH 只有在至少一半的基分类器预测错误时才会犯错。因此，根据 Hoeffding不等式，集成后模型的泛化误差为P ( H ( x ) ≠ f ( x ) ) = ∑ k = 0 ⌊ T / 2 ⌋ ( T K ) ( 1 − ϵ ) k ϵ T − k ≤ e x p ( − 1 2 T ( 2 ϵ − 1 ) 2 ) P\left ( H(x)\ne f(x) \right ) =\sum_{k=0}^{\left \lfloor T/2 \right \rfloor }

(TK)(TK)

(1-\epsilon )^k\epsilon^{T-k} \le exp\left (-\frac{1}{2}T(2\epsilon-1)^2 \right )P(H(x)​=f(x))=k=0∑⌊T/2⌋​(TK​)(1−ϵ)kϵT−k≤exp(−21​T(2ϵ−1)2)

这表明随着集成规模 T TT 的增大，模型的泛化误差以指数级速度下降，并最终随着 T TT 趋向于无穷而趋向于0。由于基分类器由相同的训练集学习产生，因此很难得到真正独立的基分类器，但可以通过在学习过程中引入随机性来减少它们之间的相关性，并通过集成得到好的泛化性能。

并行集成方法的另一个好处是它们天然可并行，通过使用多核、多机的方式很容易加快训练速度。

2.Bagging算法

Bagging名称来源于Bootstrap AGGregatING 的缩写。顾名思义，“自助”和“聚合”是Bagging的两个关键。

由于聚合独立的基分类器可以显著降低误差，所以我们希望得到的基分类器越独立越好。给定训练集，一种可能的实现是采样得到若干相互没有重合样本的子集，每个子集各自训练基分类器。然而，由于训练数据是有限的，这样得到的子集样本少，不具代表性，使得基分类器的性能受限。

Bagging采用自助采样生成不同的基分类器。它引入自助采样得到训练子集用于训练基分类器。给定一个样本数为 m mm 的训练集合，它通过有放回采样得到有 m个训练样本的采样集。原始样本有的被选中多次，有的未被选中。重复过程 T 次，得到 T TT 个样本数目为 m的样本集。对每个采样出来的训练集，使用基学习算法可以得到一个基学习器。

Bagging采用最常用的方法来聚合基分类器，如在分类任务上投票，在回归问题上平均。自助采样赋予了Bagging一个额外优势，给定 m个训练样本，第 i个样本被选中 0 , 1 , 2 , …次的概率近似为 λ = 1 的泊松分布，所以第 i ii 个样本至少出现一次的概率为 1 − ( 1 / e ) ≈ 0.632，即对Bagging的任一基分类器，训练时原始数据集中约有36.8%的样本未被使用。此时，基分类器的好坏可以通过这些包外样本估算，继而对Bagging算法的泛化误差进行估算。

包外样本还有其他用途。例如当使用决策树作为基分类器时，每棵树任意节点的后验概率可以通过包外样本进行估算。如果一个树节点不包含包外样本，标记它为“未计数节点”。预测样本时，样本的后验概率可以通过对它所落入的非未计数节点的后验概率求平均进行估算。

3.随机森林

随机森林是集成方法最前沿的代表之一。随机森林是Bagging的升级，它和Bagging的主要区别在于引入了随机特征选择。即在每棵决策树选择分割点时，随机森林会先随机选择一个特征子集，然后在这个子集上进行传统的分割点选择。

随机森林中使用的随机决策树算法如下：

输入：数据集 D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x m , y m ) } ; 特征子集大小 K；

步骤：

N ← 给定数据集 D构建节点；if 所有样本属于一个类别then   return   N;F← 可以继续分类的特征集合；if F 为空 t h e n   r e t u r n   N ；从 F中随机选择 K个特征；N . f ← 特征 F 中具有最好分割点的特征；N . p ←N.f 中最好的分割点；D l ← D D_l\gets DDl​←D 中 N . f N.fN.f 值小于 N . p N.pN.p 的样本子集；D r ← D D_r\gets DDr​←D 中 N . f N.fN.f 值不小于 N . p N.pN.p 的样本子集；N l ← N_l \getsNl​← 以参数 ( D l , K ) (D_l,K)(Dl​,K) 继续调用本程序；N r ← N_r \getsNr​← 以参数 ( D r , K ) (D_r,K)(Dr​,K) 继续调用本程序；r e t u r n  N.

输出：一棵随机决策树

参数 K KK 用来控制随机性。当 K KK 等于所有特征总数时，构建的决策树等价于传统确定性的决策树；当 K = 1 K=1K=1 时，会随机选择一个特征。随机树只在特征选择阶段引入随机性，在选择分割点时不会引入。

4.Bagging程序示例

我们创建一个含有1000个样本20维特征的随机分类数据集：

我们将使用重复的分层k-fold交叉验证来评估该模型，一共重复3次，每次有10个fold。我们将评估该模型在所有重复交叉验证中性能的平均值和标准差。

此Bagging方法，以决策树为基分类器，基分类器个数默认为10个，使用有放回抽样，最终模型的效果是Accuracy: 0.859， 标准差0.034。对比随机森林算法：

随机森林默认的决策树个数为10，默认的特征数为所有特征数的开方。由于随机森林的基分类器决策树并不像传统Bagging算法使用全部特征，而是随机选取部分特征，所以基分类器之间的独立性更好，因此也带来了性能的进一步提升。

在本实例中，随机森林的结果是Accuracy: 0.891， 标准差0.040，准确率优于传统的Bagging算法。

本文理论部分来自《集成学习：基础与算法》/周志华著；李楠译。

后面实验部分借鉴了Datawhale的开源学习内容，链接是：

感谢Datawhale对开源学习的贡献！