Bagging与随机森林算法

一、bagging的原理

        从上图可以看出，bagging的个体弱学习器的训练集是通过随机采样得到的。通过T次的随机采样，我们就可以得到T个采样集，对于这T个采样集，我们可以分别独立的训练出T个弱学习器，再对这T个弱学习器通过集合策略来得到最终的强学习器。

        何谓随机采样？即对于m个样本的原始训练集，我们每次先随机采集一个样本放入采样集，接着把该样本放回，也就是说下次采样时该样本仍有可能被采集到，这样采集m次，最终可以得到m个样本的采样集，由于是随机采样，这样每次的采样集是和原始训练集不同的，和其他采样集也是不同的，这样得到多个不同的弱学习器。

        bagging对于弱学习器没有限制，这和Adaboost一样。但是最常用的一般也是决策树和神经网络。

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

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

二、Bagging算法流程

三、随机森林算法原理（Random Forest）

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

        使用决策树的基础上，RF对决策树的建立做了改进，对于普通的决策树，我们会在节点上所有的 n 个样本特征中选择一个最优的特征来做决策树的左右子树划分，但是RF通过随机选择节点上的一部分样本特征，这个数字小于 n，假设为 m，然后在这些随机选择的 m 个样本特征中，选择一个最优的特征来做决策树的左右子树划分。这样进一步增强了模型的泛化能力。

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

        补充：在机器学习中，偏差（bias）反映了模型无法描述数据规律，而方差（variance）反映了模型对训练集过度敏感，而丢失了数据规律，高偏差和高方差都会造成新数据到来时，模型给出错误的预测。

四、Random Forest算法流程

五、随机森林的推广

        由于RF在实际应用中的良好特性，基于RF，有很多变种算法，应用也很广泛，不光可以用于分类回归，还可以用于特征转换，异常点检测等。下面对于这些RF家族的算法中有代表性的做一个总结。

1、extra trees

2、Totally Random Trees Embedding

3、Isolation Forest

（1）简介

        Isolation Forest是一种异常点检测的方法。异常数据的两个标准：异常数据跟样本中大多数数据不太一样；异常数据在整体数据样本中占比比较小。

        为了刻画异常数据的“不一样”，最直接的做法是利用各种统计的、距离的、密度的量化指标去描述数据样本跟其他样本的疏离程度。而 Isolation Forest 的想法要巧妙一些，它尝试直接去刻画数据的“疏离”(isolation)程度，而不借助其他量化指标。Isolation Forest 因为简单、高效，在学术界和工业界都有着不错的名声。

（2）算法思想

（3）训练Isolation Forest，并用其检测异常点

        训练决策树时，从训练集中抽取样本的个数要远远小于训练集个数，因为我们的目的是异常点检测，只需要部分样本，我们一般就可以将异常点区别出来了。

（4）Isolation Forest的特点

        其它常用异常挖掘的算法，比如常用的统计方法，基于分类的方法，和基于聚类的方法。这些传统算法通常是对正常的数据构建一个模型，然后把不符合这个模型的数据，认为是异常数据。而且，这些模型通常用正常数据作优化，而不是用异常数据作优化。而 Isolation Forest 可以显示地找出异常数据，而不用对正常的数据构建模型。

        由于异常数据的两个特征：异常数据只占很少量；异常数据特征值和正常数据差别很大。异常数据的这两个特征，确定了算法的理论基础。因此，构建二叉树型结构的时候，异常数据离根更近，而正常数据离根更远，更深。算法为了效率考虑，也限定了树的深度：ceil(log2(n))，（n表示单棵决策树的训练样本的样本数）这个值近似于树的平均深度，因为只需要关心那些低于平均高度的数据点，而不需要树进行完全生成。

        算法只需要两个参数：树的多少与采样的多少。实验发现，在100颗树的时候，路径的长度就已经覆盖得比较好了，因此选100颗也就够了。采样，是为了更好的将正常数据和异常数据分离开来。有别于其它模型，采样数据越多，反面会降低Isolation Forest识别异常数据的能力。通常使用256个样本，这也是scikit-learn实现时默认使用的采样数。由于算法只需要采样数据256条样本，并且对树的深度也有限制，因此，算法对内存要求很低，且处理速度很快，其时间复杂度也是线性的。

六、随机森林的优缺点

   优点：

           （1）训练可以高度并行化，对于大数据时代的大样本训练速度有优势。

　　　（2）由于可以随机选择决策树节点划分特征，这样在样本特征维度很高的时候，仍然能高效的训练模型。

　　　（3）在训练后，可以给出各个特征对于输出的重要性

　　　（4）由于采用了随机采样，训练出的模型的方差小，泛化能力强。

　　　（5）相对于Boosting系列的Adaboost和GBDT， RF实现比较简单。

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

    缺点：

　　　　（1）在某些噪音比较大的样本集上，RF模型容易陷入过拟合。

　　　　（2）取值划分比较多的特征容易对RF的决策产生更大的影响，从而影响拟合的模型的效果。