机器学习算法总结之Bagging与随机森林

写在前面

集成学习（ensemble learning）是现在非常热门的机器学习方法，在各种大赛中都可以看到它的身影。它本身不是一个单独的机器学习算法，而是通过构建并结合多个机器学习器来完成学习任务，所以常常比单一学习器具有更为显著的泛化性能。根据个体学习器的生成方式，目前的集成学习主要可以分为两类：①个体学习器之间存在强依赖关系、必须串行生成的序列化方法，代表是Boosting；②个体学习器之间不存在强依赖关系、可同时生成并行化方法，代表是Bagging和随机森林（Random Forest）。

1. Bagging的原理

Bagging的原理如上图，采用的是一种“自助采样法（bootstrp sampling）”：对于m个样本的原始训练集，我们每次先随机采集一个样本放入采样集，接着把该样本放回，也就是说下次采样时该样本仍有可能被采集到，这样采集m次，最终可以得到m个样本的采样集，由于是随机采样，这样每次的采样集是和原始训练集不同的，和其他采样集也是不同的，这样得到多个不同的弱学习器。

注意这里的采样是有放回的采样，对于一个含有m个训练样本的训练集，通过数学推导可知，约有63.2％的样本会出现在采样集中。另外值得一提的是，剩下的36.8％的杨嫩可以用作验证集来对泛化性能进行“包外估计”（out-of-bag estimation）

通过上述步骤得到不同的基学习器之后，再将他们进行结合。对于分类问题，通常使用简单投票法，得到最多票数的类别或者类别之一为最终的模型输出。对于回归问题，通常使用简单平均法，对T个弱学习器得到的回归结果进行算术平均得到最终的模型输出。

由于Bagging算法每次都进行采样来训练模型，因此泛化能力很强，对于降低模型的方差很有作用。当然对于训练集的拟合程度就会差一些，也就是模型的偏差会大一些。

2.Bagging算法

输入为样本集D={(x,y1),(x2,y2),...(xm,ym)}，弱学习器算法, 弱分类器迭代次数T。
输出为最终的强分类器f(x)
1）对于t=1,2...,T:
　　　a)对训练集进行第t次随机采样，共采集m次，得到包含m个样本的采样集Dt
　　　b)用采样集Dt训练第t个弱学习器Gt(x)
2) 如果是分类算法预测，则T个弱学习器投出最多票数的类别或者类别之一为最终类别。如果是回归算法，T个弱学习器得到的回归结果进行算术平均得到的值为最终的模型输出。

3.随机森林

随机森林（RF）是Bagging的一个改进版本：RF在以决策树为基学习器构建一个Bagging集成的基础上，进一步在决策树的训练过程中引入了随机属性选择。。具体而言，传统决策树在选择划分属性时是在当前结点的属性集合中选择一个最优属性（根据信息增益、增益率等准则），而在RF中，对基决策树的每个结点，先从该结点的属性集合中随机选择一个包含K个属性的子集，然后再从这个子集中选择一个最优属性用于划分。这里的参数k控制了随机性的引入程度，推荐k=log（d）。

随着个体学习器数目的增加，随机森林通常会收敛到更低的泛化误差。

4.小结

RF的主要优点有：
　　　　1） 训练可以高度并行化，对于大数据时代的大样本训练速度有优势。
　　　　2） 由于可以随机选择决策树节点划分特征，这样在样本特征维度很高的时候，仍然能高效的训练模型。
　　　　3） 在训练后，可以给出各个特征对于输出的重要性
　　   　4） 由于采用了随机采样，训练出的模型的方差小，泛化能力强。
　　　　5） 相对于Boosting系列的Adaboost和GBDT， RF实现比较简单。

　　　　6） 对部分特征缺失不敏感。

RF的主要缺点有：

　　　   1）在某些噪音比较大的样本集上，RF模型容易陷入过拟合。
          　2) 取值划分比较多的特征容易对RF的决策产生更大的影响，从而影响拟合的模型的效果。

关于随机森林，刘建平大牛博客中还提到了许多RF推广变形形式：Bagging与随机森林算法原理小结

以上~