如果只想大致理解下随机森林的原理请看第一部分，第二部分是对原论文的研读（灰色引用标记的为证明或自己的理解），这部分可能需要花的时间比较长，不需要的可以忽略。
此外，文末列出来的参考视频，如果读论文还是不太懂个人觉得很有必要看看，会加深理解，因为读完论文再看了一遍也让我对之前脑海中的袋外估计、特征重要性等内容有了推掉重来的印象。

第一部分：理解

随机森林（Random forest，简称RF）是由Leo Breiman在2001年在《Machine Learning》（IF:2.809，2018）正式发表提出。正如上一篇博客中写的，随机森林属于集成学习中Bagging的典型算法。总的来说，随机森林就是在随机子空间中随机组合的自由生长的CART决策树+Bagging得到的。

这里在CART决策树前加入了三个描述词，一个是在随机子空间中，也就是指数据随机采样，即随机地在样本空间中选取样本子空间；一个是随机组合，也就是特征随机采样，将一些特征随机组合在一起，可以只是选出来的这些特征进行学习，也可以将某些特征进行组合成新的特征进行学习，总之都在这个随机的子空间中；还有一个自由生长，这个比较好理解，就是对每个决策树都不进行剪枝。

对于随机森林的理解可以分为“随机”和“森林”：“随机”是指数据随机采样以及特征随机采样，主要体现在Bagging，它的全称是Bootstrap aggregation，称为自助法，它是一种有放回的抽样方法。Bagging的每个弱学习器的训练集都是通过随机且有放回采样得到的，简单来说就是每次从原始样本中随机且有放回的采样n个训练样本，进行T轮采样，得到T个训练集，然后用这T个训练集，分别独立训练T个弱学习器，这T个弱学习器结合成一个强学习器，强学习器的结果作为整体的结果输出。而“森林”则是指利用多颗自由生长的CART决策树组成一个“森林”，作为上述的T个弱学习器。

随机森林的生成规则如下：

1. 从原始训练集中随机有放回采样n个训练样本，重复T次；
2. 用这T个数据集，分别作为训练集训练T个CART树模型；
3. 如果特征维度为M，指定一个常数m（网上说一般小于等于$\sqrt{M}$，论文中尝试了$int(lo{g}_{2}M+1)$），随机地从M个特征中选取m个特征子集，每次树进行分裂时，从这m个特征中选择最优的；
4. 将生成的T棵决策树组成随机森林，保证每棵树都尽最大程度的生长，并且没有剪枝过程；
5. 对于分类问题，由T个CART树投票表决产生分类结果。对于回归问题，由T棵树预测结果的均值作为最终的预测结果。

由于数据采样的随机性，每棵树的训练集都是不同的，而且里面包含重复的训练样本，对于一个含有异常值的数据来说，这种采样方式可以令大多数的树模型得到不包含或者只包含少量异常点的数据，再经过多个学习器最终的“投票”或者“平均”，可以使得随机森林对异常值不敏感，有很强的抗干扰能力。而特征随机采样可以说是随机森林自带的特征选择的功能，正如前面所说，实际数据中会有很多多余甚至无关特征，这些特征会严重影响模型效果，随机森林中让每棵决策树只选择少量的特征进行学习，最后再合成他们的学习成果，因此随机森林能处理高维数据，并且不用做特征选择。

Out of Bag

此外，Bagging中还涉及到一个比较重要的概念：OOB（Out of Bag），意思是，通过统计，有放回的抽样，有一部分样本会多次出现，而另一部分样本不出现。Bagging每轮随机采样中，假如说训练集很大，而且抽的次数很多，也就是$n$很大，那训练集中大约有
$$(1-\frac{1}{n}{)}^n=\frac{1}{(\frac{n}{n-1}{)}^n}=\frac{1}{(1+\frac{1}{n-1}{)}^n}\to \frac{1}{e}\approx 36.8\%$$
的数据没有被采样集采集。对于这部分大约$\frac{1}{3}$没有被采样的数据，称为袋外数据。这些数据没有参与模型的训练，可以用来测试模型的泛化能力，所以随机森林可以不需要单独留出交叉验证的验证集。下图是机器学习技法中的ppt，描述了随机森林的袋外误差是怎样计算的，具体为：

1. 对于数据集中每一个样本$(x_i,y_i)$，将所有未使用该样本$(x_i,y_i)$进行训练得到的决策树组成的子随机森林模型$G_i^{-}$；
2. 对$G_i^{-}$进行误差计算，即得到样本$(x_i,y_i)$进行交叉验证的结果，看看这个子模型在样本$(x_i,y_i)$的表现；（此步骤与使用留一法类似）
3. 重复步骤2，依次计算在剩余每个样本；
4. 对所有样本进行交叉验证的结果进行求和取平均，作为随机森林模型最终的交叉验证的结果。
   

特征重要性：

如果某个特征对于这个模型很重要，那将这个特征用一些噪音替换之后的表现将会下降，而替换前后的差值就可以用来选择重要的特征，因为特征越重要对模型的表现影响越大，因此差值也越大。
但是若替换成一些噪音，例如高斯或者均匀分布的噪音，会影响训练集原本的分布，因此采用permutation，这里的大概意思就是将数据重新洗牌。

而原始的洗牌需要在训练数据上做的，并且每次洗牌后需要重新训练一个模型，再进行验证得出模型的performance，而随机森林的表现由上述所说就是袋外误差$E_{OOB}(G)$来评估，但是随机森林不需要在训练的时候做洗牌，而是在验证的时候洗牌，就是直接使用OOB的那部分数据上来替换掉需要测试重要性的特征的袋外误差，然后这样计算出每一个特征的重要性。总的说来随机森林的特征重要性是由permutation+OOB得到。

这样的优点是不需要在原始数据上做洗牌，因而也不需要重新训练模型，在训练完一个随机森林的模型后，即可使用该模型来计算特征重要性。

注： 目前在Python的机器学习工具scikit-learn中随机森林的特征重要性不是上述这样做，而是通过（树中的决策节点的）特征使用的相对顺序（即深度）来进行评估。 决策树顶部使用的特征对更大一部分输入样本的最终预测决策做出贡献；因此，可以使用接受每个特征对最终预测的贡献的样本比例来评估该 特征的相对重要性 。
通过对多个随机树中的 预期贡献率 （expected activity rates） 取平均，可以减少这种估计的方差 ，并将其用于特征选择。
详见scikit-learn (sklearn) 官方文档

随机森林的优点：

1. 由于每棵树之间是没有相关性的，因此可以并行生成，使得整个算法运行十分高效；
2. 自由生长的决策树很容易过拟合，但是由于Bagging使得随机森林对异常值不敏感，有很强的抗干扰能力；
3. CART决策树有很好的性质，例如可以处理缺失值、处理连续或者多分类的变量等；
4. 可以用来做特征选择。

第二部分：论文研读

主要内容框架（不含介绍）：

• 随机森林的收敛：用强大数定律证明了收敛性，得出不会因为树的增加而过拟合；
• 强度和相关系数（泛化误差的上界）：给出了泛化误差的上界，这个上界取决于单个分类器的强度和相关系数；
• 随机森林的优点
• 袋外估计：给出了袋外估计的理论支撑综述；
• 随机输入选择：即特征子空间的随机选择，给出了方法和实证，并与Adaboost和Bagging对比，在很小的特征数量时精度也很高；
• 输入的线性组合：特征的线性组合在大数据集以及合成数据集上表现更好；
• 分类变量：给出处理分类变量的方法以进行特征组合；
• 强度与相关系数的实证结果：采用袋外估计，使理论值具体化，实证说明分类器之间的相关关系越低，分类器的强度越大，随机森林的泛化误差越小；
• 推测：Adaboost是一个随机森林：给出了猜想，但是没有证明（至于它和Adaboost是什么关系还值得后续探讨研究）；
• 输出噪声的影响：Adaboost对标签数据有噪音很敏感，随机森林影响很小；
• 具有许多弱输入的数据：对于弱输入，森林似乎有能力使用非常弱的分类器，只要它们的相关性很低；
• 探索随机森林机制（特征的重要性）：通过计算特征重要性了解随机森林的黑盒机制
• 随机森林回归：给出泛化误差的上界，残差之间的相关系数以及决策树平均泛化误差越低，泛化误差越小；
• 回归的实证结果：实证说明相关系数随着使用的特征数量的增加而增长得非常慢，且随机森林中随机性的组合很灵活；
• 评价和结论

Breiman L. Random Forests[J]. Machine Learning, 2001, 45(1):5-32.
这篇文章主要是受到Amit和Geman在1997发表的Shape quantization and recognition with randomized trees一文的启发。他们从大量几何定义的特征中随机选择一些浅层树来定义每个节点上的分割，从而生成手写字符识别的浅层树。尽管随机森林的实现是不同的，也不是基于特定问题的，但他们的工作为随机森林的想法提供了开端。

对于第$k$个决策树，就有一个随机向量${\Theta }_k$，它与之前的随机向量${\Theta }_1,\dots ,{\Theta }_{k-1}$独立但是同分布；这样一个由训练集和${\Theta }_k$长成的树就对应了一个分类器$h(x,{\Theta }_k)$，其中$x$是输入向量。由此给出随机森林的定义，即：

定义1.1 随机森林是一个树状结构分类器组成的分类器集合 { h ( x , Θ k ) , k = 1 , …   } \{h(x,\Theta_k),k=1,\dots\} {h(x,Θk​),k=1,…}，其中 { Θ k } \{\Theta_k\} {Θk​}是独立同分布的随机向量，并且每棵树在输入$x$下得到一个类别由此投票选出最有可能的类别。

随机森林的收敛

给定一组分类器$h_1(x),h_2(x),\dots ,h_K(x)$，它的的训练集是从随机向量$Y,X$的分布中随机抽取的，定义margin函数为$$mg(X,Y)=a{v}_{k}I(h_k(X)=Y)-\underset{j̸=Y}{\max }a{v}_{k}I(h_k(X)=j)$$其中$I(\cdot )$为示性函数。则这个margin函数描述了在$Y,X$上分类正确的平均投票数超过分类为其他任何类别的平均投票数的程度，它类似于回归问题中的残差$y-f(x)$，但不同的是，这个margin越大，分类就越可信。
给定泛化误差为$$P{E}^{\ast }=P_{X,Y}(mg(X,Y)<0)$$

这里对于泛化误差我的理解有以下两种：
1、因为泛化误差的定义为：学到的模型$\tilde{f}$对未知数据预测的误差，即$R_{exp}(\tilde{f})=E_p[L(Y,\tilde{f}(X))]$，其中$L(\cdot )$为损失函数。这里的margin函数相当于损失函数，因为margin越大，分类就越可信，因此假定分布为伯努利分布，即$mg<0$时取1，$mg>0$时取0，则$E_p[L(Y,\tilde{f}(X))]=1\times P_{X,Y}(mg(X,Y)<0)+0\times P_{X,Y}(mg(X,Y)>0)=P{E}^{\ast }$
2、分类任务中错误率的定义为：$E(f,D)=\frac{1}{m}{\sum }_{i=1}^{m}I(f(x_i)̸=y_i)\to P(I(f(x_i)̸=y_i)$，类似的，对于margin来说我们评价分类错误超过分类正确的情况，这样定义一个性能度量$P{E}^{\ast }=P_{X,Y}(mg(X,Y)<0)$来评价泛化误差也是很自然的。

在随机森林中$h_k(X)=h(x,{\Theta }_k)$，因此，由强大数定律就有：

定理1.2 随着树的数量增加，对于序列${\Theta }_1,{\Theta }_2,\dots$，泛化误差$P{E}^{\ast }$几乎处处收敛到$$P_{X,Y}(P_{\Theta }(h(X,\Theta )=Y)-\underset{j̸=Y}{\max }{P}_{\Theta }(h(X,\Theta )=j)<0)$$

证明：只需证明在序列空间上${\Theta }_1,{\Theta }_2,\dots$上存在一个零测集$C$，使得对所有$x\notin C$，有$$\frac{1}{N}\sum _{n=1}^{N}I(h({\Theta }_n,x)=j)\to P_{\Theta }(h({\Theta }_n,x)=j)$$对固定的训练集和固定的$\Theta$，使得$h(\Theta ,x)=j$成立的所有$x$是一个hyper-rectangle的并，对所有$h(\Theta ,x)$，只存在唯一的有限$K$个这样的hyper-rectangle的并，表示为$S_1,\dots ,S_K$。若 { x : h ( Θ , x ) = j } = S k \{x:h(\Theta,x)=j\}=S_k {x:h(Θ,x)=j}=Sk​，定义$\phi (\Theta )=k$。令$N_k$表示为前$N$次实验中$\phi (\Theta )=k$成立的次数。则有$$\frac{1}{N}\sum _{n=1}^{N}I(h({\Theta }_n,x)=j)=\frac{1}{N}\sum _k{N}_{k}I(x\in S_k)$$由大数定律，有$$N_k=\frac{1}{N}\sum _{n=1}^{N}I(\phi ({\Theta }_n)=k)\stackrel{a.s.}{}{P}_{\Theta }(\phi ({\Theta }_n)=k)$$对于某些不收敛的$k$，取所有集合的并，得到零测集$C$，使得在$C$外面，有$$\frac{1}{N}\sum _{n=1}^{N}I(h({\Theta }_n,x)=j)\to \sum _k{P}_{\Theta }(\phi ({\Theta }_n)=k)I(x\in S_k)=P_{\Theta }(h({\Theta }_n,x)=j)$$

这个定理解释了为什么随机森林不会因为树的增加而过拟合，反而产生了一个泛化误差的有界值。

强度和相关系数（泛化误差的上界）

对于随机森林，可以用两个参数来表示泛化误差的上界，这两个参数是衡量单个分类器的精确度以及它们之间的相关性的指标。

定义2.1 随机森林的margin函数为$$mr(X,Y)=P_{\Theta }(h(X,\Theta )=Y)-\underset{j̸=Y}{\max }{P}_{\Theta }(h(X,\Theta )=j)$$分类器集合 { h ( x , Θ ) } \{h(x,\Theta)\} {h(x,Θ)}的强度为$s=E_{X,Y}mr(X,Y)$

假设$s>0$，由切比雪夫不等式有$$P{E}^{\ast }⩽var(mr)/s^2\text{\hspace{1em}(4)}$$

因为$P{E}^{\ast }=P_{X,Y}(mr(X,Y)<0)⩽P_{X,Y}(mr<0)+P_{X,Y}(mr>2s)=P_{X,Y}(|mr-s|>s)⩽var(mr)/s^2$

令$\hat{j}(X,Y)=\arg {\max }_{j̸=Y}{P}_{\Theta }(h(X,\Theta )=j)$，则$$\begin{array}{rl}mr(X,Y)& =P_{\Theta }(h(X,\Theta )=Y)-P_{\Theta }(h(X,\Theta )=\hat{j}(X,Y))\\ & =E_{\Theta }[I(h(X,\Theta )=Y)-I(h(X,\Theta )=\hat{j}(X,Y))]\end{array}$$

定义2.2 raw margin函数定义为$$rmg(\Theta ,X,Y)=I(h(X,\Theta )=Y)-I(h(X,\Theta )=\hat{j}(X,Y))$$

则$mr(X,Y)$是$rmg(\Theta ,X,Y)$关于$\Theta$取期望。
对任意的函数$f$，当$\Theta ,{\Theta }^{\prime }$相互独立且同分布时等式$[E_{\Theta }f(\Theta ){]}^2=E_{\Theta ,{\Theta }^{\prime }}f(\Theta )f({\Theta }^{\prime })$恒成立。所以有$$mr(X,Y{)}^2=E_{\Theta ,{\Theta }^{\prime }}rmg(\Theta ,X,Y)rmg({\Theta }^{\prime },X,Y)$$

因此，$$\begin{array}{rl}var(mr)& =E_{\Theta ,{\Theta }^{\prime }}(co{v}_{X,Y}rmg(\Theta ,X,Y)rmg({\Theta }^{\prime },X,Y))\\ & =E_{\Theta ,{\Theta }^{\prime }}(\rho (\Theta ,{\Theta }^{\prime })sd(\Theta )sd({\Theta }^{\prime }))\end{array}$$其中$\rho (\Theta ,{\Theta }^{\prime })$是固定$\Theta ,{\Theta }^{\prime }$时$rmg(\Theta ,X,Y)$与$rmg({\Theta }^{\prime },X,Y)$之间的相关系数，$sd(\Theta )$是固定$\Theta$时$rmg(\Theta ,X,Y)$的标准差。则$$\begin{array}{rl}var(mr)& =\bar{\rho }(E_{\Theta }sd(\Theta ){)}^2\\ & ⩽\bar{\rho }{E}_{\Theta }var(\Theta )(var(sd)=Es{d}^2-(Esd{)}^2⩾0)\end{array}\text{\hspace{1em}(7)}$$其中$\bar{\rho }$是相关系数的均值，即$\bar{\rho }=E_{\Theta ,{\Theta }^{\prime }}(\rho (\Theta ,{\Theta }^{\prime })sd(\Theta )sd({\Theta }^{\prime }))/E_{\Theta ,{\Theta }^{\prime }}(sd(\Theta )sd({\Theta }^{\prime }))$。而$$\begin{array}{rl}{E}_{\Theta }var(\Theta )& ⩽E_{\Theta }(E_{X,Y}rmg(\Theta ,X,Y){)}^2-s^2\\ & ⩽1-s^2\end{array}\text{\hspace{1em}(8)}$$

$$\begin{array}{rl}{E}_{\Theta }var(\Theta )& ⩽va{r}_{\Theta }(E(\Theta ))?\\ & =va{r}_{\Theta }(E_{X,Y}rmg(\Theta ,X,Y))\\ & =E_{\Theta }(E_{X,Y}rmg(\Theta ,X,Y){)}^2-(E_{\Theta }{E}_{X,Y}rmg(\Theta ,X,Y){)}^2\\ & =E_{\Theta }(E_{X,Y}rmg(\Theta ,X,Y){)}^2-(E_{X,Y}{E}_{\Theta }rmg(\Theta ,X,Y){)}^2\\ & =E_{\Theta }(E_{X,Y}rmg(\Theta ,X,Y){)}^2-(E_{X,Y}mr(X,Y){)}^2\\ & =E_{\Theta }(E_{X,Y}rmg(\Theta ,X,Y){)}^2-s^2\\ & ⩽1-s^2\end{array}$$

由式$(4),(7),(8)$得到下面定理：

定理2.3 泛化误差的上界为$$P{E}^{\ast }⩽\bar{\rho }(1-s^2)/s^2$$

虽然这个界可能很松，但它对随机森林的提示功能与VC类型上界对其他类型分类器的提示功能相同。结果表明，随机森林泛化误差涉及的两个因素是森林中单个分类器的强度，以及它们之间关于raw margin函数的相关系数。c/s2比值是相关系数除以强度的平方。对于理解随机森林的作用，这个比值将是一个有效的指导——越小越好。

这里的$s$就是前面说所得类似于分类器精度的一个性能度量，$\rho$是关于raw margin函数的相关系数，因此上述推导说明泛化误差的上界只与分类器精度以及分类器之间的某种相关系数有关。

定义2.4 随机森林的c/s2比值定义为$c/s2=\bar{\rho }/s^2$

在二分类情形下，margin函数为$$mr(X,Y)=2P_{\Theta }(h(X,\Theta )=Y)-1$$强度为正的要求(见(4))与我们熟悉的弱学习条件$E_{X.Y}{P}_{\Theta }(h(X,\Theta )=Y)>0.5$相似。（即弱学习器的准确度要比随便猜好一些）。raw margin函数为$2I(h(X,\Theta )=Y)-1$，$\bar{\rho }$是$I(h(X,\Theta )=Y)$与$I(h(X,{\Theta }^{\prime })=Y)$之间的相关系数。特别地，若$Y$的值取$+1$和$-1$，则$$\bar{\rho }=E_{\Theta ,{\Theta }^{\prime }}[\rho (h(\cdot ,\Theta ),h(\cdot ,{\Theta }^{\prime }))]$$因此$\bar{\rho }$是在平均分布$\Theta ,{\Theta }^{\prime }$下森林中两颗不同的决策树之间的相关系数。
对于多分类任务，之前定义的强度既取决于森林，又取决于单独的每棵树，因为是森林决定了$\hat{j}(X,Y)$。另外，因为$$\begin{array}{rl}P{E}^{\ast }& =P_{X,Y}(P_{\Theta }(h(X,\Theta )=Y)-\underset{j̸=Y}{\max }{P}_{\Theta }(h(X,\Theta )=j)<0)\\ & ⩽\sum _j{P}_{X,Y}(P_{\Theta }(h(X,\Theta )=Y)-P_{\Theta }(h(X,\Theta )=j)<0)\end{array}$$令$$s_j=E_{X,Y}(P_{\Theta }(h(X,\Theta )=Y)-P_{\Theta }(h(X,\Theta )=j))$$表示分类器$h(x,{\Theta }_k)$相对于第$j$类的强度。注意强度的定义不依赖于森林。由切比雪夫不等式，假设所有的$s_j>0$，则有$$P{E}^{\ast }⩽\sum _{j}var(P_{\Theta }(h(X,\Theta )=Y)-P_{\Theta }(h(X,\Theta )=j))s_j^2$$类似于$(7)$式得推导，这个方差也可以写成平均相关系数。本文并没有估计上式的经验值。

随机森林的优点

为了提高精度,随机性必须最小化相关系数$\bar{\rho }$的同时保持强度。这里研究的森林包括使用随机选择的输入或每个节点上的输入组合来生长每棵树。由此产生的森林具有与Adaboost相比更好的准确性。这类程序有以下可取的特点:

1. 它的准确度和Adaboost一样好，有时甚至更好。
2. 对异常值和噪声具有较强的鲁棒性。
3. 它比bagging或boosting快。
4. 它给出了有用的内部估计误差，强度，相关系数和变量重要性。
5. 它简单而且容易并行化。

袋外估计

在随机森林实验中，bagging与随机特征选择相结合。每一个新的训练集都从原始的训练集中有放回的抽取出来，然后在新的训练集上使用随机特征选择生成一棵树，长出来的树不修剪。

使用bagging有两个原因。首先，当使用随机特征时，使用bagging似乎可以提高准确性。第二，bagging可用于对组合树的泛化误差(PE)进行持续估计，以及对强度和相关系数的估计。

假设有一种从任意训练集构造分类器的方法，给定一个特定的训练集$T$，形成boostrap训练集$T_k$，构造分类器$h(x,T_k)$，让它们投票组成一个包装好的预测器。对于训练集中的每个$y,x$，只对那些不包含$y,x$的分类器$T_k$进行汇总，称之为袋外分类器。这样对泛化误差的袋外估计为训练集上袋外分类器的错误率。

也就是之前机器学习技法视频中给出的那个计算公式，对泛化误差的袋外估计为$E_{OOB}(G)$，$G_n^{-}(x_n)$就是这里所说的袋外分类器，它的错误率就是所有袋外分类器的平均值，因此$E_{OOB}(G)=\frac{1}{N}{\sum }_{n=1}^{N}err(y_n,G_n^{-}(x_n))$。

Tibshirani(1996)、Wolpert和Macready(1996)提出使用袋外估计作为估计泛化误差的一个组成部分。Wolpert和Macready研究了回归类型问题，并提出了一些估计袋装预测器生成误差的方法。Tibshirani使用袋外方差估计来估计任意分类器的泛化误差。Breiman (1996 b)的袋装分类器的学习误差估计给出了经验证据，表明袋外估计与使用相同大小的测试集作为训练集一样准确，因此使用袋外误差估计不需要留出测试集。

在每个boostrap训练集中，约有三分之一的样本被遗漏。因此，袋外估计是基于组合的分类器数量仅为当前主组合的三分之一左右。由于错误率随着组合数量的增加而降低，袋外估计往往会高估当前的错误率。为了得到无偏的袋外估计，有必要运行超过测试集错误收敛的点。但与交叉验证不同的是，交叉验证存在偏差但其程度未知，而袋外估计是无偏的。

强度和相关系数也可以用袋外法估计。这给出了有助于理解分类精度以及如何提高分类精度的内部估计。

随机输入选择

最简单的具有随机特征的随机森林是通过随机选择在每个节点上用来做划分的一小组输入变量而形成的。使用CART方法生成树，且最大化树的形状，不要剪枝，用Forest-RI表示这个过程，组的大小$F$是固定的。这里试了两个$F$的值。第一个只使用一个随机选择的变量，即$F=1$。第二个$F$是第一个小于$lo{g}_{2}M+1$的整数，其中$M$是输入的个数。

作者的实验使用了来自UCI存储库的13个较小的数据集、3个较大的数据集，这些数据集被分成训练和测试集以及4个合成数据集。表1给出了一个简要的总结（这里不列出来）。

在这13个较小的数据集中，每一个都使用以下步骤：随机留出10%的数据。在剩下的数据上，随机森林运行两次，第一次$F=1$，第二次$F=int(lo{g}_{2}M+1)$，生长并组合100棵树。然后将预留的10%放入每个森林中，得到两者的测试集误差。所选择的测试集误差对应于两次运行中out-of-bag估计值的较低值。重复100次，计算测试集的平均误差。基于50棵树的Adaboost也遵循相同的过程运行。

随机森林中使用100棵树和Adaboost使用50棵树的原因有两个。袋外估计仅基于森林中树木数量的三分之一左右。为了得到可靠的估计，作者选择了100棵树。第二个考虑因素是，根据Adaboost中所需的所有输入，随机森林的生成速度要比Adaboost生成速度快很多倍。随机森林中100棵树的生长速度要比Adaboost的50棵树的生长速度快得多。

表2中第二列是通过最小的袋外误差从两组规模中选取的结果。第三列是只使用一个随机特性来生成树的测试集误差。第四列包含了为最佳设置(单个或选择)计算的森林中单个树的泛化误差的袋外估计（单颗树的平均误差）。这个估计值是通过在每棵生长的树中使用遗漏的实例作为测试集，并对森林中所有树的结果求平均值来计算的。

与Adaboost相比，使用随机输入选择的错误率更好。如果搜索超过更多的$F$值而不是预先设置的两个值，这种比较可能会更有利。但该方法对$F$值不太敏感，$F=1$时的错误率与$F$值较高时的错误率的平均绝对差小于1%。这种差异在三个大数据集中表现得最为明显。

之所以包括单变量测试集的结果，是因为在一些数据集中，使用一个随机输入变量比使用多个更好。在其他组中，结果仅略好于使用单一变量。令人惊讶的是，在每个节点上使用一个随机选择的输入变量进行分割可以产生良好的精度。（表2中明显可以看出）

随机输入选择可以比Adaboost或Bagging快得多。一个简单的分析表明，使用所有变量的RI计算时间与未剪枝的树构建计算时间之比为$F\ast lo{g}_2(N)/M$，其中$F$是Forest-RI中使用的变量的数量，$N$是样本的数量，$M$是输入变量的数量。对于邮政编码数据，使用$F=1$，这个比率是0.025，这意味着Forest-RI要快40倍。实证检验证实了这一差异。在250Mhz的Macintosh上，对邮政编码数据执行Forest-RI ($F=1$需要4.0分钟才能生成100棵树，而Adaboost几乎需要3个小时。对于具有多个变量的数据集，计算时间差可能是显著的。

输入的线性组合

如果只有少量的输入，比如$M$，将$F$取$M$中相当大的一部分可能会导致强度的增加，但相关系数也更高。另一种方法是通过对一些输入变量进行随机线性组合来定义更多的特征。也就是说，通过指定要组合的变量数$L$来生成一个特性。在给定的节点上，随机选取$L$个变量，并将其与$[-1,1]$上的均匀随机数相加。生成$F$个线性组合，然后在这些组合上搜索最佳分割。这个过程称为Forest-RC。

我们使用$L=3$和$F=2,8$，$F$的选择由袋外估计决定。我们选择$L=3$，是因为对于$O(M^3)$不同的输入变量组合，$F$的值越大，在增加强度的同时，相关系数不会有太大的上升。如果输入变量在一个数据集是不能比较的，他们需要做标准化处理。测试集的结果在表3给出，第三列包含$F=2$的结果。第四列包含表2所计算的单个树的结果。

除了三个较大的数据集外，$F=8$的使用非常没必要；$F=2$接近最小值。对于较大的数据集，$F=8$给出了更好的结果。Forest-RC在合成数据集上表现非常好。总的来说，和Forest-RI相比，它比Adaboost更好。

在表2和表3中有一些项，其中所选的项小于一个输入值或Forest-RC小于两个特征的值。发生这种情况的原因是，当与$F$的两个值对应的错误率接近时，out-of-bag估计将几乎随机地选择$F$的值。

进行了一项小型调查，以确定是否可以改进这三个较大数据集的性能。根据第6节卫星数据的运行情况，我们推测强度在较大的数据集中不断上升，而相关系数更快地达到渐近线。因此，我们对较大的数据集分别使用100、100和200棵树进行了$F=100$的运行。在卫星数据上，误差降至8.5%，在字母数据上，误差降至3.0%，但压缩码测试集误差没有减小。根据一种有根据的预感，我尝试了$F=25$的Forest-RI。邮政编码测试集错误降低到5.8%。这是迄今为止树集成在这三个数据集上实现的最低测试集错误。

分类变量

一些或所有的输入变量可能是分类变量，因为我们想定义变量的加法组合，所以我们需要定义如何处理分类变量，以便它们可以与数值变量组合。作者的方法是，每次在一个节点上选择一个分类变量进行分割时，选择该变量类别的一个随机子集，并定义一个替代变量，当该变量的分类值在子集中且在子集外为零时，该替代变量为1。

由于具有$I$值的分类变量可以编码为$I-1$虚拟的0 - 1变量，所以我们使变量$I-1$的概率是数值变量的1倍。当许多变量是分类变量时，使用$F$的低值会导致低相关系数，但也会导致低强度。$F$必须增加到大约2 - 3倍$int(lo{g}_{2}M+1)$，以获得足够的强度来提供良好的测试集精度。

例如，在有60个四值分类的DNA数据集上，训练集中有2000个样本，测试集中有1186个样本，使用$F=20$的Forest-RI，测试集的错误率为3.6% (Adaboost为4.2%)。大豆数据有685个样本、35个变量、19个类和15个分类变量。使用$F=12$的Forest-RI得到的测试集误差为5.3% (Adaboost为5.8%)。将Forest-RC与3个组合和F = 8结合使用，误差为5.5%。

这种方法的一个优点是，它克服了如何处理具有许多值的分类的困难。在二分类问题中，这可以通过使用Breiman等人(1985)提出的机制来避免，该机制将对最佳分类分割的搜索简化为$O(I)$计算。对于更多的类，搜索最佳分类分割是一个$O(2^{I-1})$计算。在随机森林实现中，对任何类别变量的计算只涉及类别的随机子集的选择。

强度与相关系数的实证结果

为了对各种数据集中强度和相关系数的影响进行实证研究，使用了强度和相关系数的out-of-bag估计。

首先对声纳数据(60个输入，208个示例)使用1到50个输入运行Forest-RI。在每次迭代中，将10%的数据分割成一个测试集，然后将每个节点上随机选择的输入数$F$从1变化到50。对于每一个$F$值，生长100棵树形成一个随机森林，记录下测试集误差、强度、相关系数等的终值。进行了80次迭代，每次随机删除10%的数据作为测试集使用，所有结果的平均值都超过80次。在这个实验中总共生成了40万棵树。

图1的顶部图表绘制了强度和相关系数的值与$F$的关系。当$F=4$时，强度保持不变，增加更多的输入没有帮助。但相关系数持续增加。第二个图绘制了测试集误差和对$F$的泛化误差的袋外估计。袋外估计更为稳定。两者都表现出相同的行为——从$F=1$到$F$在4-8之间有一个小的下降，然后是一个普遍的、逐渐的上升。误差的增加与强度的稳定区域的开始相吻合。

图2显示了在breast数据集中类似的运行情况，其中使用了由三个输入的随机组合组成的特征。这些特征的数量从1个到25个不等。同样，相关系数显示出缓慢的上升，而强度实际上保持不变，因此最小误差是在F = 1处。令人惊讶的是，这两个数字的强度相对稳定。由于相关系数缓慢而稳定地增加，当只使用少量输入或特性时，误差最小。

由于较大的数据集似乎与较小的数据集具有不同的表现，所以作者对卫星数据集进行了类似的实验。特征的数量(每个特征由两个输入的随机加和组成)从1到25不等，每个特征集组合100个分类器。结果如图3所示。结果与较小数据集的结果不同。相关系数和强度均有小幅但稳定的增长。错误率略有下降。我们推测，随着更大、更复杂的数据集的出现，这种强度在稳定下来之前持续增长的时间更长。

作者的结果表明，较好的(较低的泛化误差)随机森林分类器之间的相关关系越低，分类器的强度越大。建树过程中使用的随机性主要为了低相关系数$\bar{\rho }$，同时保持合理的强度。这一结论已在以前的工作中有所暗示。Dietterich(1998)测量了一个集成的色散，并指出更精确的集成具有更大的色散。Freund(个人通讯)认为Adaboost如此成功的一个原因是，它在每一步都试图将下一个分类器与当前分类器解耦。Amit等(1999)分析表明，Adaboost算法的目的是保持分类器之间的协方差较小。

所以随机森林之所以表现好，就是在保证了单个分类器的性能的同时，分类器之间相关性比较低。

推测：Adaboost是一个随机森林

可以修改各种分类器，使其同时使用训练集和训练集上的一组权重。考虑如下的随机森林：定义了训练集上$K$个不同的非负的和为一的权值集合，用$w(1),w(2),\dots ,w(K)$表示。与这些权重对应的是概率$p(1),p(2),\dots ,p(K)$，其和为1。根据这些概率，从$1,\dots ,K$中抽取整数，结果即为$\Theta$。若$\Theta =k$，
则用训练集来生成一个带权重$w(k)$的分类器$h(x,\Theta )$。

在其原始版本中，Adaboost (Freund & Schapire, 1996)是一种确定性算法，它根据之前分类器中的错误分类，选择训练集上的权重，输入到下一个分类器。在作者的实验中，随机森林的生成如下：Adaboost在一个数据集上运行75次，生成$w(1),w(2),\dots ,w(50)$(前25个被丢弃)。第$k$组权值的概率与$Q(w_k)=log[(1-error(k))/error(k)]$成正比，其中$error(k)$为第$k$分类器的$w(k)$加权训练集误差。然后森林被运行250次。

这在一些数据集上重复了100次，每次只留下10%作为测试集，然后平均测试集错误。在每个数据集上，Adaboost的错误率都非常接近随机森林错误率。一个典型的结果是威斯康辛州乳腺癌数据，Adaboost平均产生2.91%的错误，随机森林产生2.94%的错误。

Adaboost算法，$w(k+1)=\varphi (w(k))$，其中$\varphi$是由基分类器决定的函数。用$h(x,w_k)$表示第$k$个分类器。第k个分类器的投票由$Q(w_k)$加权，因此第$j$类在$x$时的标准化投票为$$\sum _{k}I(h(x,w_k)=j)Q(w_k)/\sum _{k}Q(w_k)\text{\hspace{1em}(10)}$$对于任何定义在权重空间上的函数，定义算子$Tf(w)=f(\varphi (w))$。我们猜想，$T$是对于不变测度$\pi (dw)$是遍历的。则$(10)$式会以分布$Q\pi (dw)=Q(w)\pi (dw)/\int Q(v)\pi (dv)$收敛到$E_{Q\pi }[I(h(x,w)=j)]$。如果这个猜想是正确的，那么Adaboost等价于一个随机森林，它在训练集上的权重是从分布$Q\pi$中随机选择的。

它的正确性也可以解释为什么当更多的树集成时，Adaboost并没有过拟合——这是一个令人困惑的实验事实。有一些实验证据表明，如果运行数千次，Adaboost可能会过拟合(Grove & Schuurmans, 1998)，但这些运行是使用非常简单的基分类器完成的，可能不会延续到使用树作为基分类器。作者在许多数据集上运行Adaboost到1,000棵树的经验是，测试集错误收敛到一个渐近值。

这个猜想的正确性并没有解决Adaboost如何在它所做的权重空间上选择有利分布的问题。注意，权重的分布依赖于训练集。在通常的随机森林中，随机向量的分布不依赖于训练集。

输出噪声的影响

Dietterich(1998)的研究表明，当训练集中输出标签的一小部分被随机改变时，Adaboost的准确率下降，而bagging和随机分割选择对噪声的免疫力更强。由于输出中经常存在一些噪声，因此对噪声的鲁棒性是一个理想的特性。Dietterich(1998)进行了以下实验，改变了大约20%的类别标签(注入5%的噪声)。

对于实验中的每一个数据集，随机抽取10%作为一个测试集，对剩余的训练集进行两次运行，第一次运行在训练集上。第二次运行是在训练集的噪声版本上。噪声版本是通过随机地将5%的类别标签更改为从其他标签中均匀地选择的替代类标签而得到的。

使用Adaboost(确定性版本)、Forest- RI和Forest- RC重复50次。测试集的结果在50次重复中平均，并计算出由于噪声而增加的百分比。在两种随机森林中，我们都使用了在之前实验中给出测试集误差最小的特征数。由于运行的长度，只使用了9个最小的数据集。表4给出了由于噪声引起的错误率的增加。

5%的噪声使Adaboost明显变差，而随机森林大体上变化较小。奇怪的是，对Adaboost的影响依赖于数据集，glass和ecoli这两个多类数据集以及糖尿病数据集受噪声的影响最小。Adaboost算法迭代地增加最近被错误分类的样例的权重。具有不正确类标签的实例将持续被错误分类。然后，Adaboost将把更多的精力集中在这些嘈杂的样例上，并将其扭曲。随机森林过程不将权重集中在样例的任何子集上，并且噪声影响更小。

具有许多弱输入的数据

具有弱输入的数据集在医学诊断、文献检索等领域越来越普遍。其共同特征是没有单个输入或小组输入可以区分类别。这种类型的数据对于通常的分类器(神经网络和树)来说是困难的。

为了查看Forest-RI方法是否有可能工作，生成了10个类，1000个二元输入数据。文中代码生成了一组概率 { p ( j , m ) } \{p(j, m)\} {p(j,m)}，其中$j$是类标签，$m$是输入号。然后，类$j$的输入是一个由$M$个二元变量组成的字符串，第M个变量以概率$p(j,M)$为1。

对于训练集，$N=1000$。还使用相同的 { p ( j , k ) } \{p (j, k)\} {p(j,k)}构造了一个4000个样本的测试集。对代码的检查表明，每个类在某些位置具有更高的潜在概率。但是所有这些位置的总数大约是2000个，所以有很大的重叠。假设我们知道所有的 { p ( j , k ) } \{p (j, k)\} {p(j,k)}，那么在我们的运行中计算的特定 { p ( j , m ) } \{p (j, m)\} {p(j,m)}的贝叶斯错误率为1.0%。

由于输入之间是相互独立的，根据训练数据估计 { p ( j , k ) } \{p (j, k)\} {p(j,k)}的朴素贝叶斯分类器应该是最优的，而且错误率为6.2%。这并不是对朴素贝叶斯的认可，因为很容易在输入之间建立依赖关系，从而增加朴素贝叶斯的错误率。作者用这个例子是因为贝叶斯错误率和朴素贝叶斯错误率很容易计算。

作者从$F=1$的Forest-RI开始。它收敛得非常慢，经过2500次迭代，当它停止时，仍然没有收敛。测试集误差为10.7%。强度为0.069，c/s2比值为2.5，相关系数为0.012。尽管强度很低，但几乎为零的相关系数意味着，随着迭代的进行，我们在增加小的精度增量。

显然，我们想要的是在保持低相关系数的同时增加强度。再次使用$F=int(lo{g}_{2}M+1)=10$运行Forest-RI。结果令人鼓舞。经过2000次迭代，它收敛了。测试集误差为3.0%。强度为0.22，相关系数为0.045，c/s2为0.91。按照这个趋势，Forest-RI以$F=25$运行，迭代2000次后停止。测试集误差为2.8%。强度为0.28，相关性为0.065，c/s2为0.83。

有趣的是，Forest-RI可以产生比贝叶斯错误率高不了多少的错误率。单个分类器是弱分类器。$F=1$时，平均树错误率为80%，$F=10$时，是65%，对于$F=25$，是60%。森林似乎有能力使用非常弱的分类器，只要它们的相关性很低。作者尝试了使用Adaboost进行比较，但是无法让Adaboost在这个数据上运行，因为基本分类器太弱。

探索随机森林机制（特征的重要性）

就对其机制的简单解释而言，由树组成的森林是很费解的。在一些应用中，例如医学实验分析中，理解变量之间的相互作用是至关重要的，它提供了预测的准确性。首先使用内部的out-of-bag估计，并通过仅使用选定的变量重新运行来验证。

假设有$M$个输入变量。在构建每棵树之后，袋外样本中的第$m$个变量的值被随机排列，袋外数据运行到相应的树中。对每个袋外的$x_n$给出的分类将被保存，从$m=1,2,\dots ,M$重复，在运行结束时，将关于第$m$个混噪音变量的$x_n$的多数袋外类别投票与$x_n$的真实类标签进行比较，给出一个误分类率。

输出是与袋外率(所有变量不变)相比，误分类率增加的百分比。我们通过使用一个包含1000棵树且没有测试集的森林的单次运行来得到这些估计。

在糖尿病数据集中，仅使用$F=1$的单变量，由于变量的噪声，误差的上升如图4所示。

第二个变量是迄今为止最重要的，其次是变量8和变量6。在100次重复中只使用变量2运行随机森林，每次只留下10%来测量测试集的误差，得到的误差为29.7%，而使用所有变量时的误差为23.1%。但是当变量8被添加时，误差只下降到29.4%。当变量6与变量2相加时，误差降至26.4%。

变量6看起来很重要，但一旦输入变量2就没有帮助了，这是因变量如何影响随机森林预测误差的一个特性。假设有两个变量$x_1$和$x_2$是相同的，并且具有重要的预测信息。因为在随机森林中，每一个都是以相同的频率被选中的，所以分别对每一个进行噪声处理将导致相同的错误率增加。但是，一旦$x_1$作为预测变量，再使用$x_2$将不会带来任何错误率的下降。在糖尿病数据集中，第8个变量与第2个变量携带一些相同的信息。因此，当与第二个变量结合使用时，它不会增加预测精度。

相对于所使用的输入特性，错误率上升的相对幅度相当稳定。上面的实验是用$F=2$的三个输入的组合重复进行的。结果如图5所示。

另一个有趣的例子是投票数据。这有435个例子对应于435个国会议员和16个变量反映他们对16个问题的赞成-反对投票。分类变量是共和党人还是民主党人。为了了解哪些问题是最重要的，我们再次运行生成1000棵树的噪音变量程序。使用$F=5$的单个输入获得原始数据的最低错误率，因此在运行中使用了这些参数。图6中的结果。

变量4很突出，如果变量4有噪声，则错误为三倍。我们仅使用变量4重新运行这个数据集。测试集误差为4.3%，与使用所有变量时的误差基本相同。4票的表决结果把共和党人和民主党人区分开来，就像4票的表决结果以及其他15个议题的表决结果组合一样。

本节给出的方法只是一个开始。需要更多的研究来理解如何给出一个更完整的图景。

随机森林回归

随机森林回归是由依赖于一个随机向量?$\Theta$的生成树组成，使得这样树预测$h(x,\Theta )$为数值，而不是分类标签。输出值为数值，并且假设训练集独立从随机向量$Y,X$的分布中抽样。任意数值预测器$h(x)$的均方泛化误差为$$E_{X,Y}(Y-h(X){)}^2$$随机森林预测器由决策树 { h ( x , Θ ) } \{h(x,\Theta)\} {h(x,Θ)}对$k$取平均得到。

定理11.1 随着森林中树的数量趋于无穷$$E_{X,Y}(Y-a{v}_{k}h(X,\Theta ){)}^2\stackrel{a.s.}{}{E}_{X,Y}(Y-E_{\Theta }h(X,\Theta ){)}^2\text{\hspace{1em}(12)}$$

将$(12)$式右边项记为$P{E}^{\ast }(forest)$——随机森林的泛化误差。将决策树的平均泛化误差定义为：$$P{E}^{\ast }(tree)=E_{\Theta }{E}_{X,Y}(Y-h(X,\Theta ){)}^2$$

定理11.2 假设对所有的$\Theta$，$EY=E_{X}h(X,\Theta )$，则$$P{E}^{\ast }(forest)⩽\bar{\rho }P{E}^{\ast }(tree)$$其中$\bar{\rho }$是残差项$Y-h(X,\Theta )$和$Y-h(X,{\Theta }^{\prime })$之前的加权相关系数，$\Theta ,{\Theta }^{\prime }$相互独立。

证明：$$\begin{array}{rl}P{E}^{\ast }(forest)& =E_{X,Y}[E_{\Theta }(Y-h(X,\Theta )){]}^2\\ & =E_{\Theta }{E}_{{\Theta }^{\prime }}{E}_{X,Y}(Y-h(X,\Theta ))(Y-h(X,{\Theta }^{\prime }))\end{array}$$等式右边为协方差，可以写为：$E_{\Theta }{E}_{{\Theta }^{\prime }}(\rho (\Theta ,{\Theta }^{\prime })sd(\Theta )sd({\Theta }^{\prime }))$，其中$sd(\Theta )=\sqrt{E_{X,Y}(Y-h(X,\Theta ){)}^2}$，定义加权相关系数为：$\bar{\rho }=E_{\Theta ,{\Theta }^{\prime }}(\rho (\Theta ,{\Theta }^{\prime })sd(\Theta )sd({\Theta }^{\prime }))/(E_{\Theta }sd(\Theta ){)}^2$
则有：$$P{E}^{\ast }(forest)=\bar{\rho }(E_{\Theta }sd(\Theta ){)}^2⩽\bar{\rho }P{E}^{\ast }(tree)$$

定理(11.2)指出了精确回归森林的要求——残差之间的低相关系数以及低误差决策树。随机森林减少树木的平均误差受限于系数$\bar{\rho }$。所采用的随机化需要针对低相关性。

回归的实证结果

在回归森林中，我们在bagging上使用随机特征选择。因此,我们可以使用由out-of-bag估计提供的监控给出$P{E}^{\ast }(forest),P{E}^{\ast }(tree)$和$\bar{\rho }$的估计。这些估计数的推导与分类中的类似。整个过程中，使用由两个输入的随机线性加和组成的特征。稍后我们将讨论这些特性中有多少可以用于确定每个节点上的分割。使用的特征越多较$P{E}^{\ast }(tree)$越低，但$\bar{\rho }$会更高。在我们的实证研究中使用了以下数据集，见表5。

在这些数据集中，波士顿住房，Abalone和Servo可在UCI存储库获取。机械臂数据由迈克尔·乔丹提供。最后三个数据集是合成的。它们起源于Friedman (1991)， Breiman (1998b)也对它们进行了描述。这些数据集是用来比较适应性套袋和套袋的相同的数据集(见Breiman, 1999)，除了一个合成数据集(Peak20)被排除了，这个数据集被其他研究人员和作者自己都发现是异常的。

列出的前三个数据集大小适中，测试集误差的估计方法是去掉10%的随机实例，在剩下的90%上运行，并使用剩下的10%作为测试集。重复100次，测试集误差取平均值。鲍鱼数据集更大，有4,177个实例和8个输入变量。它最初有25%的实例作为测试集。我们运行这个数据集时，将随机选择的25%的实例作为测试集使用，重复10次并取平均值。

表6给出了bagging、自适应bagging和随机森林的测试集均方误差。这些都是使用25个特征运行的，每个特征都是两个随机选择的输入的随机线性组合，来分割每个节点，每个特征都是两个输入的随机组合。所有的方法都运行了所有数据集，结合100棵树。在所有数据集中，都强制执行了“如果节点大小小于5，则不拆分”规则。

回归和分类之间一个有趣的区别是，相关系数随着使用的特征数量的增加而增长得非常慢。主要的影响是$P{E}^{\ast }(tree)$的减少。因此，需要相对大量的特性来减少$P{E}^{\ast }(tree)$并获得最佳的测试集误差近似值。

表6中的结果是混合的。随机森林-随机特征总是比bagging好。在自适应bagging使误差急剧减少的数据集中，森林所产生的误差减少并不明显。在自适应bagging并没有比bagging更好的数据集中，森林产生了改进。

对于相同数量的输入组合，在较宽的范围内，误差不会随着特性的数量发生太大的变化。如果使用的数量过小，$P{E}^{\ast }(tree)$就会变得过大，误差就会增加。如果使用的数量太大，相关系数就会上升，误差也会增加。介于两者之间的范围通常很大。在这个范围内，随着特性数量的增加，相关系数会增加，但是$P{E}^{\ast }(tree)$会通过减少来进行补偿。

表7给出了测试集误差、袋外误差估计和对$P{E}^{\ast }(tree)$的袋外估计以及相关系数。

正如预期的那样，OB的误差估计一直很高。机器人手臂的数据比较低，但作者认为这是单独的训练集和测试集造成的伪影，其中测试集的错误率可能略高于训练集。

作为一个实验，作者没有使用bagging，并将其替换为随机输出(Breiman, 1998b)。在这个过程中，每个输出都加入了均值为零的高斯噪声。噪声的标准差等于输出的标准差。与bagging实验类似，树的构建使用了25个特征，每个特征由两个随机选择的输入随机线性组合而成，用于分割每个节点。结果如表8所示。

前两个数据集的错误率是迄今为止最低的。总的来说，添加输出噪声与随机特征选择比bagging效果更好。这说明了随机森林设置的灵活性——可以添加各种随机组合来查看哪种方法效果最好。

评价和结论

随机森林是一种有效的预测工具。由于大数定律，它们不会过拟合。加入正确的随机性使它们成为精确的分类器和回归器。此外，根据单个预测器的强度和它们之间的相关系数，该框架可以洞察随机森林的预测能力。采用袋外估计，使强度和相关系数的理论值具体化。

在一段时间内，传统的想法是森林不能与arcing类型的算法在精确性方面竞争。我们的研究结果消除了这种想法，但也引出了一些有趣的问题。boosting和arcing算法具有减少偏差和方差的能力(Schapire et al.，1998)。回归中的自适应bagging算法(Breiman, 1999)是为了减少偏差而设计的，在分类和回归中都能有效地运行。但是，就像arcing一样，它也会随着训练的进展而改变训练集。

森林提供了与boosting和自适应bagging相比较的结果，但并没有显著地改变训练集。它们的精度表明它们的作用是减少偏差。其机制并不明显。随机森林也可以看作是贝叶斯预测。虽然作者怀疑这是一个富有成效的探索路线，如果它可以解释偏差减少，作者可能更偏向于贝叶斯。

随机输入和随机特征在分类上有很好的效果，而在回归分析中效果较差。本研究中唯一使用的随机性类型是bagging和随机特征。很有可能加入其他类型的随机性会给出更好的结果。例如，一位评审建议使用特征的随机布尔组合。

一个几乎显而易见的问题是，是否可以通过用结合随机特征和boosting来提高精度。对于较大的数据集，似乎可以显著降低错误率。在一些运行中，我们得到的错误低至5.1%的邮编数据，2.2%的字母数据和7.9%的卫星数据。在较小的数据集上，改进较少。这方面还需要做更多的工作，但它确实表明，加入不同的随机性可以产生更好的结果。

最近的一篇论文(Breiman, 2000)表明在二分类问题的分布空间中，随机森林等价于一个作用于真实margin的核。讨论了随机性(低相关系数)增强了核的对称性，而强度增强了在突变曲线边界处的理想偏度。希望这能说明相关性和强度的双重作用。Kleinberg(2000)关于随机区分的理论框架也有助于理解。

下一篇可以看看Breiman, L. 2000. Some infinity theory for predictor ensembles. Technical Report 579, Statistics Dept. UCB.

参考资料

Breiman L. Random Forests[J]. Machine Learning, 2001, 45(1):5-32.
机器学习技法（林轩田）