Bagging

基本概念

又称袋装（bagging）或者自助聚集(boot strap aggregating)
是一种根据均匀概率分布从数据集中重复采样（有放回）的技术。每个自助采样的样本集都和原数据集一样大。
在又放回的抽样中，如果抽样的个数和原数据集的大小一致，则自助样本Di$D_i$中会有63%$63\mathrm{\%}$的原训练数据，因为每一个样本抽到Di$D_i$的概率为1−(1−1N)N$1-(1-\frac{1}{N}{)}^N$,如果N$N$足够大，则这个概率收敛于1−1/e≈0.632$1-1/e\approx 0.632$

算法

关于时间复杂度

Bagging$Bagging$的时间复杂度大致是T(O(m)+O(s))$T(O(m)+O(s))$，考虑到采样与投票的平均时间复杂度O(s)$O(s)$非常小,而且T$T$通常是一个不太大的常数，所以Bagging$Bagging$集成和直接使用基学习算法训练的一个学习器的复杂度同阶。这说明Bagging$Bagging$是一个很高效的集成学习算法。

随机森林和Bagging

随机森林（Random Forest简称RF），是Bagging的一个扩展变体。RF在以决策树为基学习器构建在Bagging$Bagging$集成的基础之上的。进一步在决策树的训练过程中引入了随机属性选择。
具体来说，传统的决策树在选择划分属性的时候是在当前结点属性集合（假定有d$d$个属性）中选择一个最优属性。而在RF$RF$中，对基决策树的每个结点，先从该结点的属性中随机选择一个包含k$k$个属性的子集，然后再从这个子集中选择一个最优属性用于划分。这里的参数k$k$控制了随机性的引入程度：若令k=d$k=d$则基决策树的构建和传统决策树相同。若令k=1$k=1$则相当于随机选择一种属性用于划分。一般情况下推荐k=log2d$k={\log }_{2}d$