集成学习

概念

集成学习 (ensemble learning) 通过构建并结合多个学习器来完成学习任务。下图展示了集成学习的一般结构：先产生一组“个体学习器” (individual learner)，再用某种策略将它们结合。若集成中只包含同种类型的个体学习器，这样的集成是“同质的” (homogeneous)，同质集成中的个体学习器称为“基学习器” (base learner)，相应的学习算法称为“基学习算法” (base learning algorithm)。集成也可以包含不同类型的个体学习器，即“异质的” (heterogenous)。

**集成学习通过将多个学习器进行结合，通常可以获得比单一学习器显著优越的泛化性能。**这对“弱学习器” (weak learner) 尤为明显。实际中，要获得好的集成，个体学习器通常应该“好二不同”，即个体学习器要有一定的“准确性”，并且要有“多样性”，即学习器间具有差异。

Bagging

给定包含 m个样本的数据集，先随机取出一个样本放入采样集，再把该样本放回初始数据集，使得下次采样时该样本仍有可能被选中，经过 m 次随机采样，得到含 m 个样本的采样集，初始训练集中有的样本在采样集多次出现，有的则从未出现。这样可采样出 T 个含 m 个训练样本的采样集，然后基于每个采样集训练出一个基学习器，再将这些基学习器结合。这就是 Bagging 的基本流程。

随机森林

随机森林 (Random Forset，RF) 是 Bagging 的一个扩展。RF 在以决策树为基学习器构建 Bagging 集成的基础上，在决策树的训练过程中引入随机属性选择。传统决策树在选择划分属性时是在当前节点的属性集合 (假定有 d 个属性) 中选择一个最优属性；而在 RF 中，对基决策树的每个结点，先从该结点的属性集合中随机选择一个包含 k 个属性的子集，然后再从这个子集中选择一个最优属性用于划分。参数 k 控制了随机性的引入程度。

假如有N个样本，则有放回的随机选择N个样本(每次随机选择一个样本，然后返回继续选择)。这选择好了的N个样本用来训练一个决策树，作为决策树根节点处的样本。
当每个样本有M个属性时，在决策树的每个节点需要分裂时，随机从这M个属性中选取出m个属性，满足条件m << M。然后从这m个属性中采用某种策略（比如说信息增益）来选择1个属性作为该节点的分裂属性。
决策树形成过程中每个节点都要按照步骤2来分裂（很容易理解，如果下一次该节点选出来的那一个属性是刚刚其父节点分裂时用过的属性，则该节点已经达到了叶子节点，无须继续分裂了）。一直到不能够再分裂为止。注意整个决策树形成过程中没有进行剪枝。
按照步骤1~3建立大量的决策树，这样就构成了随机森林了

Boosting

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

著名代表为Adaboosting：

初始化训练数据的权值分布

如果有N个样本，则每一个训练样本最开始时都被赋予相同的权值：1/N
训练弱分类器

如果某个样本点已经被准确地分类，那么在构造下一个训练集中，它的权值就被降低

相反，如果某个样本点没有被准确地分类，那么它的权值就得到提高

权值更新过的样本集被用于训练下一个分类器，整个训练过程如此迭代地进行下去
将各个训练得到的弱分类器组合成强分类器

加大分类误差率小的弱分类器的权重，而降低分类误差率大的弱分类器的权重

AdaBoost算法流程如下：

Adaboost流程示意图