随机森林中的数学理论(2)
Breiman1证明了泛化误差的上界是可以得到的，它主要由两方面因素决定：单棵决策树的分类强度，决策树之间的相关性。
泛化误差上界
定义单棵决策树的余量函数：
分类强度(余量函数在整个 data space 的期望)：
假定 $s>0$（即随机森林对各个样本的分类结果是可信的），根据切比雪夫不等式：
准备工作
要求出这个上界，我们需要先分析下 $var(mr)$。为了解决这个问题，我们引入几个新的量，
也就是说，
另外有恒等式，
好，现在我们来推 $var(mr)$，
正式开推
定义决策树之间的平均相关系数 $\overline{\rho}$，
则，
故，
总结
随机森林错误率与两个因素有关2：
- 森林中任意两棵树的相关性(correlation)：相关性越大，错误率越大；
- 森林中每棵树的分类强度(strength)：每棵树的分类能力越强，整个森林的错误率越低。
减小特征选择个数m，树的相关性和分类强度也会相应的降低；增大m，两者会随之增大。所以关键的问题是如何选择最优的 m（或者是范围），通过计算袋外错误率 oob error，我们可以很快锁定 m.
资料传送门：