集成算法-Bagging算法-随机森林

一、什么是集成学习

集成学习是一种技术框架，它本身不是一个单独的机器学习算法，而是通过构建并结合多个机器学习器来完成学习任务，一般结构是：先产生一组“个体学习器”，再用某种策略将它们结合起来，目前，有三种常见的集成学习框架（策略）：bagging，boosting和stacking

也就是说，集成学习有两个主要的问题需要解决，第一是如何得到若干个个体学习器，第二是如何选择一种结合策略，将这些个体学习器集合成一个强学习器
集成学习是指将若干弱分类器组合之后产生一个强分类器。弱分类器（weak learner）指那些分类准确率只稍好于随机猜测的分类器（error rate < 50%）。如今集成学习有两个流派，一种是bagging流派，它的特点是各个弱学习器之间没有依赖关系，可以并行拟合，随机森林算法就属于bagging派系；另一个是boosting派系，它的特点是各个弱学习器之间有依赖关系，Adaboost算法就属于boosting派系。在实现集成学习算法时，很重要的一个核心就是如何实现数据的多样性，从而实现弱分类器的多样性
集成学习有如下的特点：
（1）将多个分类方法聚集在一起，以提高分类的准确率（这些算法可以是不同的算法，也可以是相同的算法。）；
（2）集成学习法由训练数据构建一组基分类器，然后通过对每个基分类器的预测进行投票来进行分类；
（3）严格来说，集成学习并不算是一种分类器，而是一种分类器结合的方法；
（4）通常一个集成分类器的分类性能会好于单个分类器；
（5）如果把单个分类器比作一个决策者的话，集成学习的方法就相当于多个决策者共同进行一项决策。

Bagging和Boosting的使用区别如下：
1）样本选择：
Bagging：训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的。
Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整。
2）样例权重
Bagging：使用均匀取样，每个样例的权重相等
Boosting：根据错误率不断调整样例的权值，错误率越大则权重越大。
3）预测函数
Bagging：所有预测函数的权重相等。
Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重。
4）并行计算
Bagging：各个预测函数可以并行生成
Boosting：各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果。
5）计算效果
Bagging主要减小了variance，而Boosting主要减小了bias，而这种差异直接推动结合Bagging和Boosting的MultiBoosting的诞生

二、Bagging算法

Bagging（装袋算法）的集成学习方法非常简单，假设我们有一个数据集D，使用Bootstrap sample（有放回的随机采样，这里说明一下，有放回抽样是抽一个就放回一个，然后再抽，而不是这个人抽10个，再放回，下一个继续抽，它是每一个样本被抽中概率符合均匀分布）的方法取了k个数据子集（子集样本数都相等）：D1，D2，…，Dk，作为新的训练集，我们使用这k个子集分别训练一个分类器（使用分类、回归等算法），最后会得到k个分类模型。我们将测试数据输入到这k个分类器，会得到k个分类结果，比如分类结果是0和1，那么这k个结果中谁占比最多，那么预测结果就是谁。

大致过程如下：

1. 对于给定的训练样本S,每轮从训练样本S中采用有放回抽样(Booststraping)的方式抽取M个训练样本,共进行n轮，得到了n个样本集合，需要注意的是这里的n个训练集之间是相互独立的。
2. 在获取了样本集合之后，每次使用一个样本集合得到一个预测模型，对于n个样本集合来说，我们总共可以得到n个预测模型。
3. 如果我们需要解决的是分类问题，那么我们可以对前面得到的n个模型采用投票的方式得到分类的结果，对于回归问题来说，我们可以采用计算模型均值的方法来作为最终预测的结果。

那么我们什么时候该使用bagging集成方法：
学习算法不稳定：就是说如果训练集稍微有所改变就会导致分类器性能比较大大变化那么我们可以采用bagging这种集成方法
AdaBoost只适用于二分类任务不同，Bagging可以用于多分类，回归的任务
举个例子可以看出bagging的好处：
X 表示一维属性，Y 表示类标号（1或-1）测试条件：当x<=k时，y=？；当x>k时，y=？；k为最佳分裂点
下表为属性x对应的唯一正确的y类别：

每一轮随机抽样后，都生成一个分类器。然后再将五轮分类融合


即是说当我们模型拿捏不住样本属于哪个，或者是分裂时的阈值，我们多做几次，得到多个结果，然后投票决定
优缺点：
（1） Bagging通过降低基分类器的方差，改善了泛化误差；
（2）其性能依赖于基分类器的稳定性；如果基分类器不稳定，bagging有助于降低训练数据的随机波动导致的误差；如果稳定，则集成分类器的误差主要由基分类器的偏倚引起；
（3）由于每个样本被选中的概率相同，因此bagging并不侧重于训练数据集中的任何特定实例
1.优点，可以减小方差和减小过拟合
2.缺点，重复有放回采样的道德样本集改变了数据原有的分布，因此在一定程度上引入了偏差，对最终的结果预测会造成一定程度的影响

为什么说Bagging算法会减少方差？
首先我们来看看偏差和方差的概念
偏差：描述的是预测值（估计值）的期望与真实值之间的差距。偏差越大，越偏离真实数据
方差：描述的是预测值的变化范围，离散程度，也就是离其期望值的距离。方差越大

• bias描述的是根据样本拟合出的模型的输出预测结果的期望与样本真实结果的差距，简单讲，就是在样本上拟合的好不好。要想在bias上表现好，low bias，就得复杂化模型，增加模型的参数，但这样容易过拟合 (overfitting)，过拟合对应上图是high variance，点很分散。low bias对应就是点都打在靶心附近，所以瞄的是准的，但手不一定稳。
• varience描述的是样本上训练出来的模型在测试集上的表现，要想在variance上表现好，low varience，就要简化模型，减少模型的参数，但这样容易欠拟合(unfitting)，欠拟合对应上图是high bias，点偏离中心。low variance对应就是点都打的很集中，但不一定是靶心附近，手很稳，但是瞄的不准。

bagging是对许多强（甚至过强）的分类器求平均。在这里，每个单独的分类器的bias都是低的，平均之后bias依然低；而每个单独的分类器都强到可能产生overfitting的程度，也就是variance高，求平均的操作起到的作用就是降低这个variance。
boosting是把许多弱的分类器组合成一个强的分类器。弱的分类器bias高，而强的分类器bias低，所以说boosting起到了降低bias的作用。variance不是boosting的主要考虑因素。Boosting 则是迭代算法，每一次迭代都根据上一次迭代的预测结果对样本进行加权，所以随着迭代不断进行，误差会越来越小，所以模型的 bias 会不断降低。这种算法无法并行，例子比如Adaptive Boosting

Bagging和Rand Forest
1）Rand Forest是选与输入样本的数目相同多的次数（可能一个样本会被选取多次，同时也会造成一些样本不会被选取到），而Bagging一般选取比输入样本的数目少的样本
2）bagging是用全部特征来得到分类器，而Rand Forest是需要从全部特征中选取其中的一部分来训练得到分类器； 一般Rand forest效果比Bagging效果好！

三、随机森林

随机森林是由很多决策树构成的，不同决策树之间没有关联。当我们进行分类任务时，新的输入样本进入，就让森林中的每一棵决策树分别进行判断和分类，每个决策树会得到一个自己的分类结果，决策树的分类结果中哪一个分类最多，那么随机森林就会把这个结果当做最终的结果。

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

随机森林的优缺点
优点

1. 它可以出来很高维度（特征很多）的数据，并且不用降维，无需做特征选择
2. 它可以判断特征的重要程度
3. 可以判断出不同特征之间的相互影响
4. 不容易过拟合
5. 训练速度比较快，容易做成并行方法
6. 实现起来比较简单
7. 对于不平衡的数据集来说，它可以平衡误差。
8. 如果有很大一部分的特征遗失，仍可以维持准确度。

缺点

1. 随机森林已经被证明在某些噪音较大的分类或回归问题上会过拟合。
2. 对于有不同取值的属性的数据，取值划分较多的属性会对随机森林产生更大的影响，所以随机森林在这种数据上产出的属性权值是不可信的