Bagging, Boosting & Random Forests

Posted by Breezedeus on February 10, 2011

这几种技术通常对高度非线性的模型(如树)比较管用,对线性模型可能无效。

Bagging(bootstrap aggregation的缩写)的本质想法是平均很多有噪音但无偏的模型,以便达到降低模型方差的作用。所以bagging技术比较适合用于树模型。利用Bagging技术最终获得的模型,其偏差与单个模型(identically distributed,简记为i.d.)的偏差相同。

不同于Bagging的是,Boosting自动调整各个模型以便删除其中的偏差,所以其中的各个模型不是i.d. 。

B 个具有$\sigma^2$方差的i.i.d.随机变量平均后其方差变为$\frac{1}{B} \sigma^2$,而如果它们两两之间具有相关性$\rho$,则平均后的方差变为

\[\rho \sigma^2 + \frac{1-\rho}{B} \sigma^2 .\]

使用Bagging技术可以降低上式中第二项的结果,但是第一项的值却不会降低。Random Forests(RF)的想法是通过降低不同树之间的相关性的同时使得每颗树的方差不增加太多,从而达到降低Bagging方差的效果。RF通过在每次分割时随机选取不同的候选输入变量来达到降低不同树之间的相关性的目的。

RF的一个好处是它几乎不会因为使用了太多的树而导致最终的模型overfitting,这大概也是为什么它可以比较有效地用于组合多个算法的预测结果(如在Netflix Prize Challenge中)。而且使用RF之前对输入数据不需要做预处理,也即可以不rescale,transform,或modify数据。

RF的模型偏差比单颗树的偏差要大,之所以它们的模型精确度更高,主要得益于它们的模型方差降低。

更详细的内容可参考文献1 2Wiki上列出了RF的学习算法以及优劣势。

References

  1. Trevor Hastie, Robert Tibshiraniand and Jerome Friedman, Chapter 15: Random Forests, The Elements of Statistical Learning, the 2nd edition, 2008. 

  2. AlbertA. Montillo, Random Forests, 2009.