Breiman1证明了泛化误差的上界是可以得到的,它主要由两方面因素决定:单棵决策树的分类强度,决策树之间的相关性

此处输入图片的描述


泛化误差上界

定义单棵决策树的余量函数

分类强度(余量函数在整个 data space 的期望):

假定 $s>0$(即随机森林对各个样本的分类结果是可信的),根据切比雪夫不等式:


准备工作

要求出这个上界,我们需要先分析下 $var(mr)$。为了解决这个问题,我们引入几个新的量,

也就是说,

另外有恒等式,


好,现在我们来推 $var(mr)$,


正式开推

定义决策树之间的平均相关系数 $\overline{\rho}$,

则,

故,


总结

随机森林错误率与两个因素有关2

  • 森林中任意两棵树的相关性(correlation):相关性越大,错误率越大;
  • 森林中每棵树的分类强度(strength):每棵树的分类能力越强,整个森林的错误率越低。

减小特征选择个数m,树的相关性和分类强度也会相应的降低;增大m,两者会随之增大。所以关键的问题是如何选择最优的 m(或者是范围),通过计算袋外错误率 oob error,我们可以很快锁定 m.


资料传送门: