英语原文共 28 页，剩余内容已隐藏，支付完成后下载完整资料
机器学习，45，5-32，2001
copy; 2001 Kluwer学术出版社。出版于荷兰。
随机森林
LEO BREIMAN
加州大学伯克利分校统计系，CA 94720
编辑：Robert E. Schapire
摘要：随机森林是若干预测树的组合，其中每一棵树都取决于一个独立采样的随机向量的值，并且森林中的树都拥有相同的分布。随着森林中树木的增加，森林的泛化误差逐渐收敛到极限。一颗由分类树组成的森林的泛化误差取决于森林中每一棵树的强度和它们之间的关联。使用随机选择的特征来分割每个节点所产生的错误率优于Adaboost(Y.Freund amp; R.Schapire，机器学习：第十三届国际会议记录，***，148-156),而在抗干扰性方面也更健壮。内部估算监视器错误，强度，相关性，这些用于显示对分割所用特征数量的增加的回应。内部估计也用于衡量变量的重要性。这些思想也适用于回归。
关键字：分类，回归，集成
1. 随机森林
1.1. 引言
逐渐生成树的集合并且让它们决定出现次数最多的分类，这些都使得分类准确性有了显著的提高。为了生成这些集合，通常会生成随机向量来控制集合中每棵树的生长。一个早期的例子是Bagging法（Breiman，1996），其中每棵树都是根据训练集中的示例随机选择的（无需替换）。
另一个例子是随机拆分选择（Dietterich，1998）,其中在每个节点上的分割都从k个最佳分割中选择。Breiman（1999）通过将原始训练集的输出随机化来产生新的训练集。另一个方法是从加了随机权重的训练集中的示例中获得训练集。Ho（1998）已经写了多篇关于“随机子空间”方法的论文，随机选择用于生长每棵树的特征子集。
在一篇有关书面字符识别的重要论文中，Amit和Geman（1997）定义了大量的几何特征，并且为了每个节点上最好的分割进行对这些特征的随机选择的搜索。后一篇论文对我的思想产生了影响。
所有这些过程的共同点是，对于第k棵树，生成一个随机向量Ik，该向量和之前的I1，hellip;hellip;，Ik-1无关但是有着相同的分布，然后使用训练集和Ik生成一棵树，从而得到分类器h（x，Ik），其中x是输入向量。例如，在Bagging法中，随机向量I来源于N个飞镖随机扔向N个盒子中的计数，其中N是训练集中示例的数量。在随机分割选择中I包括多个从1到k之间的独立随机整数。I的性质和维度取决于它在树的形成中的作用。
在大量的树被建立之后，它们会选出出现次数最多的分类。我们称这些过程为随机森林。
定义1.1. 随机森林是由树状结构的分类器｛h（x，Ik），k=1，hellip;｝的集合组成的分类器，其中｛Ik｝是独立独立同分布的随机向量，并且每一棵树在输入x处对出现次数最多的类进行一个单位表决。
1.2. 论文大纲
第2章给出了随机森林的一些理论背景，强大数定律的运用表明它们始终会收敛，因此过度拟合不成问题。我们给出了Amit和Geman（1997）分析的简化和扩展版本，表明了一个随机森林的准确性取决于每一棵树个体的强度，并且还给出了它们之间依赖性的一个度量（见第二节定义）。
第3章介绍了使用每个节点上特征的随机选择来决定分割的森林。一个重要的问题是每个节点上选择多少个特征。作为指导，泛化误差的内部估计，分类器强度和依赖性计算。这些被称作袋外估计，将在第4章中进行回顾。第5和6章给出了两种不同形式的随机特征的经验结果。第一种从原始输入中进行随机选择；第二种使用输入的随机线性组合。结果优于Adaboost。
结果表明对选择分割每个节点的特征的数量不敏感。通常，选择一个或者两个特征可获得最佳效果。对于这方面的探索和将它们同强度和相关性方面联系起来，将在第7章给出一个实证研究。
Adaboost没有随机元素，通过对训练集的连续重赋权来生成树的集合，当前的权重取决于过去历史的整体形成。但是就像确定性随机数生成器一样可以对随机性进行很好的模仿，我相信Adaboost在后期阶段会模仿随机森林。该猜想的证据会在第8章给出。
最近的重要问题，也就是医学诊断和文件检索，通常具有输入变量很多的属性，通常都是成百上千，每一个属性只包含少量信息。单个树分类器的准确性比随机选择的类只好一点点。但是使用随机特征进行生成的组合树能够提高准确性。在第9章中我们分别对一个具有1000个输入变量的模拟数据集，训练集中的1000个示例和4000个示例测试集进行实验。达到了与贝叶斯相当的精度。
在许多应用中，了解随机森林“黑匣子”的机制是必要的。第10章将在这方面通过计算变量内部估计的重要性和用重用运行将它们绑定在一起来开个头。
第11章关注随机森林中的回归。均方泛化误差的一个界被派生出来，这显示在森林中的树个体的错误的下降取决于树个体的残差和均方误差的相关性。回归的经验结果在第12章中。结束语在第13章中给出。
2. 表征随机森林的准确性
2.1. 随机森林收敛
给定分类器h1（x），h2（x），hellip;，hk（x）的集合，并根据随机向量Y，X的分布随机生成的训练集，定义边缘函数为
其中I（·）是指标函数。边缘衡量的是在X，Y处，正确类别的平均表决数超过任何其他类别的平均表决数的程度。边缘越大，分类的信心就越大。泛化误差由下式给出
下标X，Y概率在X，Y空间上。
在随机森林中，hk（X）= h（X，Ik）。对于大量的树，其遵从强大数定律和树结构：
定义1.2. 随着树数量的增加，几乎可以肯定对所有序列I1，hellip;，收敛于
（1）
证明：见附录I。
这个结果解释了为什么随机森林不会因为树的增多而过度拟合，而是产生泛化误差的极限值。
2.2. 强度和相关性
对于随机森林，泛化误差的上界可以由两个参数得出，它们分别用于衡量各个分类器的准确性和它们之间的依赖。两者之间的相互作用为理解随机森林的运作方法提供了基础。我们的研究基于Amit和Geman的分析。
定义2.1. 一个随机森林的边缘函数为
（2）
并且分类器集｛h（X，I）｝的强度为
（3）
假设sge;0，Chebyshev不等式给出
（4）
以下是关于mr方差的一个更清晰的表达式：让
所以
定义2.2. 原始边缘函数为
因此，是相对于I的期望。对于任意函数f，等式
恒成立，其中独立同分布，这意味着
（5）
由（5）得
（6）
其中是和在保持不变的情况下的相关性，是保持不变的情况下对的标准偏差。故，
（7）
其中是相关系数的平均值；那就是，
写
（8）
结合（4），（7）和（8）可得：
定理 2.3. 泛化误差的上限由下式给出
尽管界限可能会松散，但它对于随机森林达到了像VC类型的边界对其他类型的分类器那样相同的提示功能。它表明在随机森林的泛化误差中包含的两种成分是森林中分类器的个体的强度，以及它们之间在原始边缘函数方面的相关性。c/s2是除以强度的平方。在理解随机森林的功能上，该比率将是一个有用的指导-它越小越好。
定义2.4. 随机森林的c/ssup2;的比定义为
在两个类的情况下有一些简化。边缘函数为
强度为积极的要求（见（4））与我们所熟悉的弱学习条件相似。原始边缘函数是，相关性在和。尤其是如果将Y的值设为 1和-1，则
因此是在分布上两个不同森林成员之间的平均相关性。
对于两个以上的类，（3）中定义的强度度量取决于森林和单独的树木，因为是森林决定了。另一种方法是可能的。写
定义
为相对于类j的分类器集｛｝的强度。注意这个定义的强度并不取决于森林。由Chebyshev不等式，假设所有的gt;0可得
（9）
使用与推导（7）相似的恒等式，（9）中的方差可以用平均相关表示。在我们的实证研究中，我没有使用（9）中的量的估计，但我认为它们对一个多类问题来说会有点意思。
3. 使用随机特征
文献中报道的一些随机森林的泛化误差一直低于其他森林。例如，随机分割选择（Dieterrich，1998）比Bagging好。布雷曼在输出端引入随机噪声（布雷曼，1998c）的效果也更好。但这三种森林都不如Adaboost（Freundamp;Schapire，1996）或其他通过训练集的自适应重赋权（arcing）工作的算法（见Breiman，1998b；Dieterrich，1998；Baueramp;Kohavi，1999）。
为了提高准确性，在保持强度的同时，注入的随机性须最小化相关性。这里研究的森林包括使用随机选择的输入或每个节点的输入组合来生成每棵树。由此产生的森林提供的准确性与Adaboost相比是有优势的。这类程序具有可取的特点：
i 它的精度和Adaboost一样好，有时更好。
ii 它对异常值和噪声相对稳健。
iii 它比Bagging或Boosting要快。
iv 它给出了误差、强度、相关性和可变重要性的有用内部估计。
v
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[238384]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
