ML算法(四)——Bagging和随机森林算法

用户7506105

发布于 2021-08-10 11:57:06

7830

发布于 2021-08-10 11:57:06

前面一篇文章主要解释了集成学习算法中Boosting一类的典型代表adaboost的数学原理，在集成学习中还有一种模型是Bagging，它和Boosting算法的主要区别在于每个基学习器是否有依赖拓扑关系，Boosting是不断修正前一个基学习器的训练误差来生成新的基学习器，而Bagging则不然，它的基学习器不存在明显的强依赖关系，每个基学习器可以并行的训练。随机森林算法是Bagging模型的一个扩展变体。

预备知识

有放回采样(自助法，bootstrap sample)

这个在中学概率问题上非常常见，通俗理解是，一个含有m个样本的集合D，每次随机的从里面抽取一个样本，复制样本并放入新的集合D’中，原样本放回原集合D，这种操作一直重复m次(重复次数和样本数量一致)，就会得到一个新的集合D',称D'是通过自助法从D中选出来的，很显然D'可能会有D的某一个样本的重复多个样本，一个样本在一次抽取中没有被抽中的概率为

P = 1 - \frac{1}{m}

则在m次抽取后(假设m无限大)有

\lim_{m\rightarrow \infty}(1 - \frac{1}{m})^m = \frac{1}{e} \approx 0.368

成立，这说明初始数据集D会有约36.8%的样本不会被选到新集合D'中

Bagging

解释随机森林之前先引入Bagging的基本思想

思想

其实较为容易理解，就是基于上述所述有放回采样生成和原始数据集一样大小的新数据集，然后这样的新数据集生成T个，这T个新数据集分别用来训练T个基学习器(可以是决策树，神经网络等)，然后通过一定的手段将这些基学习器进行结合，得到一个集成学习器，一般来说对于分类场景会使用投票法进行表决，回归场景的预测结果会通过所有基学习器预测值的平均值进行代替

特点

算法开销只取决于训练基学习器的复杂度，可以并行训练，所以比较高效
因为每次可能会有36.8%的样本不会拿来训练，所以天然地可以用作验证集做泛化性能的包外估计，这样如果基学习器是决策树可以辅助进行剪枝，如果是神经网络可以使用dropout进行降低过拟合
Bagging的预测结合过程多为平均或投票，所以在降低方差的性能上表现良好，所以对于那些对样本噪声敏感的基础算法(比如决策树)，用Bagging做集成会比较好
Bagging模型可以做多分类和回归，而一般Adaboost在分类问题上只能做二分类

随机森林

引言中说随机森林是Bagging的一种扩展变体，那究竟变在哪了呢?而且由随机森林的名称可知，一定是多颗树集成的算法，所以随机森林是基学习器为决策树的一类Bagging算法，Bagging算法的基学习器假设是决策树的话，那就需要在每个有放回生成的数据集D上进行决策树的构建，具体构建方式和ID3、C4.5算法过程一样(可参考文章决策树算法推导)，而随机森林构造的基决策树则会使用随机特征，具体做法是假设自变量有d个特征，则构建时随机地从里面选k个特征作为属性集找到此时的最优特征进行节点分裂(一般k的推荐值是

k = log_2 d

,二叉树的既视感)，如此一来构建的每个基决策树都是从随机的k个特征上构建的，进一步加强了泛化能力，随机森林的随机也体现在这，所以随机森林算法不仅满足Bagging算法的对样本集进行放回扰动的特性还满足在构建树的节点特征分裂时的特征集的随机，并且森林中每棵树都采取相同的分裂规则(比如都为信息增益或gini系数)进行树构建，构建终止条件是达到节点上的训练样本属于同一类或达到树的最大深度为止。