随机森林中的out of bag error
2015-06-16 14:23阅读：
[译者按]：这篇文献主要翻译自参考文献[1]，在oob部分，使用文献[2]稍作说明。
训练数据集为
T ，具有M个特征
T = {(X1,y1), (X2,y2), ... (Xn, yn)}
Xi {xi1, xi2, ... xiM}，是输入向量 yi 是标签.
随机森林总结:
随机森林算法是一个分类器算法，主要基于两种方法
- Bagging
- Random subspace method.
假设在森林中我们设定s棵树，首先我们生成
S 个和原始数据集大小一致的数据集，采用放回的随机抽样方法
(也即，每生成一个数据集抽样n次).最终产生
数据集T1, T2,
... TS}.
每个数据集称作一个 bootstrap 数据集. 由于放回抽样，每个数据集
Ti
中有重复数据，Ti
相比原始数据集，可能会缺少若干记录.这称为
Bootstrapping.
(en.wikipedia.org/wiki/Bootstrapping_(statistics))
Bagging
是进行 bootstraps & 然后将每个从
bootstrap中学到的模型进行集成的过程
现在, RF
生成
S 棵树，m (=sqrt(M) or
=floor(lnM+1)) 随机从M个特征中抽取子特征，来创建树.
这叫做随机子空间方法（random subspace method）.
所以对每个Ti bootstrap 数据集，我们创建了一棵树
Ki.
如果你相对某些输入数据进行分类 D = {x1, x2, ..., xM}
，你让这些数据在每棵树上都跑一遍，从而生成
S
个预测结果
(一棵树有一个预测结果) ，表示为 Y = {y1, y2, ...,
ys}. 最终预测结果通过大多数投票策略决定.
Out-of-bag error:
在生成s个分类器后 (S棵树), 对于原始训练集T中每个记录
(Xi,yi)
,选择所有不包括(Xi,yi) 的bootstrap数据集Tk.注意，这个子集，是一个boostrap
数据集所组成的集合，它们都不包含原始数据集中的某个特定记录. 这个集合被称作 out-of-bag 样例.
共有n 个这样的子集 (原始数据集 T中每行记录对应一个).
OOB 分类器 使用的是Tk 上投票的累积，所以它们不包含 (xi,yi).
从另外一个角度来解释oob方法如下：
每一棵树都通过使用不同的 bootstrap 样本.相比原始数据集，每个
bootstrap数据集中大概有1/3的记录没有包括进来，也就没有在构建第k棵树时候使用.
对于构建第k棵树时候没有用到的每条记录，让它们过一遍第k棵树，进而获得一个分类.通过这种方法, 对任何一条记录来说，大概有1/3
的树没有用这条记录来构建，因而对这些树可以进行测试集上的数据分类。最终, 假设 类别j
是当记录n是oob时候，获得投票最多的类别，j被错误分类除以总记录数n，就是 oob error estimate.
这在很多测试中被证明是无偏的[2].
Out-of-bag 估计的泛化错误率是 out-of-bag classifier
在训练集上的错误率。
那么它为什么重要? Breiman [1996b]在对 bagged 分类器的错误率估计研究中,
给出实证证据显示，out-of-bag 估计
和使用与训练集大小一致的测试集所得到的错误率一样精确. 所以, 使用out-of-bag error
估计可以不在另外建立一个测试集.
[1]http://stackoverflow.com/questions/18541923/what-is-out-of-bag-error-in-random-forests
[2]http://www.stat.berkeley.edu/~breiman/RandomForests/cc_home.htm
