集成学习之bagging回顾

在之前的集成学习中我们提到有两个流派，一个是boosting派系，它的特点是各个弱学习器之间有依赖关系；另一种是bagging流派，它的特点是各个弱学习器之间没有依赖关系，可以并行拟合。决策树模型中尽管有剪枝等等方法，一棵树的生成肯定还是不如多棵树，因此就有了随机森林，解决决策树泛化能力弱的缺点。随机森林是基于bagging框架下的决策树模型，集成学习中可以和梯度提升树GBDT分庭抗礼的算法，尤其是它可以很方便的并行训练，在如今大数据大样本的的时代很有诱惑力。随机森林是一种灵活的、便于使用的机器学习算法，即使没有超参数调整，大多数情况下也会带来好的结果。它可以用来进行分类和回归任务。

在同一批数据中，用同样的算法只能产生一棵树，这时Bagging策略可以帮助我们产生不同的数据集。Bagging策略来源于bootstrap aggregation：从样本集（假设样本集N个数据点）中重采样选出n个样本（有放回的采样，样本数据点个数仍然不变为N），在所有样本上，对这n个样本建立分类器（ID3\C4.5\CART\SVM\LOGISTIC），重复以上两步m次，获得m个分类器，最后根据这m个分类器的投票结果，决定数据属于哪一类。

随机采样：

随机采样(bootsrap)就是从我们的训练集里面采集固定个数的样本，但是每采集一个样本后，都将样本放回。也就是说，之前采集到的样本在放回后有可能继续被采集到。对于我们的Bagging算法，一般会随机采集和训练集样本数m一样个数的样本。这样得到的采样集和训练集样本的个数相同，但是样本内容不同。如果我们对有m个样本训练集做T次的随机采样，，则由于随机性，T个采样集各不相同。注意这和GBDT的子采样是不同的。GBDT的子采样是无放回采样，而Bagging的子采样是放回采样。

对于一个样本，它在某一次含m个样本的训练集的随机采样中，每次被采集到的概率是1m$\frac{1}{m}$。不被采集到的概率为1−1m$1-\frac{1}{m}$。如果m次采样都没有被采集中的概率是(1−1m)m$(1-\frac{1}{m}{)}^m$。当m→∞$m\to \mathrm{\infty }$时，(1−1m)m→1e≃0.368$(1-\frac{1}{m}{)}^m\to \frac{1}{e}\simeq 0.368$。也就是说，在bagging的每轮随机采样中，训练集中大约有36.8%的数据没有被采样集采集中。对于这部分大约36.8%的没有被采样到的数据，我们常常称之为袋外数据(Out Of Bag, 简称OOB)。这些数据没有参与训练集模型的拟合，因此可以用来检测模型的泛化能力。

随机森林是bagging的一个特化进阶版，所谓的特化是因为随机森林的弱学习器都是决策树。所谓的进阶是随机森林在bagging的样本随机采样基础上，又加上了特征的随机选择，其基本思想没有脱离bagging的范畴。

bagging的集合策略：

bagging的集合策略也比较简单，对于分类问题，通常使用简单投票法，得到最多票数的类别或者类别之一为最终的模型输出。对于回归问题，通常使用简单平均法，对T个弱学习器得到的回归结果进行算术平均得到最终的模型输出。

bagging算法步骤：

相对于Boosting系列的Adaboost和GBDT，bagging算法要简单的多。

输入为样本集D={(x,y1),(x2,y2),...(xm,ym)}$D=\{(x_{,}{y}_1),(x_2,y_2),...(x_m,y_m)\}$，弱学习器算法, 弱分类器迭代次数T。

输出为最终的强分类器f(x)$f(x)$

1）对于t=1,2...,T:

   (a) 对训练集进行第t次随机采样，共采集m次，得到包含m个样本的采样集Dt$D_t$

   (b) 用采样集Dt$D_t$训练第t个弱学习器Gt(x)$G_t(x)$

2) 如果是分类算法预测，则T个弱学习器投出最多票数的类别或者类别之一为最终类别。如果是回归算法，T个弱学习器得到的回归结果进行算术平均得到的值为最终的模型输出。

集成学习之随机森林算法

随机森林是基于bagging框架下的决策树模型（在bagging的基础上更进一步），随机森林包含了很多树，每棵树给出分类结果，每棵树的生成规则如下：

（1）样本的随机：如果训练集大小为N，对于每棵树而言，从训练样本集中用Bootstrap随机且有放回地抽取n个训练样本，作为该树的训练集，重复K次，生成K组子训练样本集；

（2）特征的随机：如果每个特征的样本维度为M，指定一个常数m<<M，随机地从M个特征中选取m个特征；

（3） 利用m个特征对每个子数据集构建最优学习模型，即建立了K棵CART决策树，每棵树尽最大程度的生长，并且没有剪枝过程；

（4） 对于新的输入数据，根据这K个CART形成的随机森林模型，通过投票表决结果，决定数据属于哪一类（投票机制有一票否决制、少数服从多数、加权多数）

随机森林的算法流程如下图：

随机森林(Random Forest)是Bagging算法的进化版，思想仍然是bagging,但是进行了独有的改进。首先，Random Forest使用了CART决策树作为弱学习器，这让我们想到了梯度提示树GBDT。第二，在使用决策树的基础上，Random Forest对决策树的建立做了改进，对于普通的决策树，我们会在节点上所有的n个样本特征中选择一个最优的特征来做决策树的左右子树划分，但是RF通过随机选择节点上的一部分样本特征，这个数字小于n，假设为nsub$n_{sub}$，然后在这些随机选择的nsub$n_{sub}$个样本特征中，选择一个最优的特征来做决策树的左右子树划分。这样进一步增强了模型的泛化能力。　　　　

如果nsub=n$n_{sub}=n$，则此时RF的CART决策树和普通的CART决策树没有区别。nsub$n_{sub}$越小，则模型约健壮，当然此时对于训练集的拟合程度会变差。也就是说nsub$n_{sub}$越小，模型的方差会减小，但是偏倚会增大。在实际案例中，一般会通过交叉验证调参获取一个合适的nsub$n_{sub}$的值。

随机森林算法步骤：

输入为样本集D={(x