第五篇 统计学习方法是如何实现分类与聚类的（六）

清华大学计算机系 马少平

第六节：随机森林算法

艾博士：下面我们对决策树算法做一个扩展讨论。设想我们有一个足够大的数据集，将该数据集分成n份，用每份构建一个决策树，这样我们对同一个问题就有了n个决策树。多个决策树组合在一起就构成了“决策森林”。

图5.20 决策森林示意图

小明：这个想法挺有意思的，那么如何使用这个决策森林呢？

艾博士：这里的n个决策树虽然是为了解决同一个问题而建立的，但是由于用到的数据集不同，所以每个决策树也会各有特点。对于同一个输入的待分类样本，不同的决策树可能会给出不同的分类结果，但是一般情况下，只要每个决策树具有一定的分类精度，则多数决策树给出的结果应该是正确的分类结果。基于这样的假设，在决策森林中可以采用简单投票的方法，得票最多的类别作为决策森林的输出。比如说对于男女性别分类问题，假定共有11个决策树，将一个待分类样本分别输入到这11个决策树中，如果说有6个以上的决策树输出为男性，则决策森林输出为男性，否则就输出为女性。

小明：明白了，决策森林的决策方式就是将每个决策树的输出作为对类别的投票，得票最多的类别就认作是决策森林的输出。如果是多个类别时怎么处理呢？

艾博士：多个类别时也是相同的原则，按照简单多数原则处理就可以，不要求得票数一定过半数。比如说还是11个决策树，共有a、b、c、d四个类别，假定说a获得4票，b获得3票、c获得2票、d获得2票，则投票结果为a。

小明：了解了，就是简单多数原则。

艾博士：但是我们多次说过，在实际应用中数据都是非常宝贵的，数据量总是显得不足，建立一个拥有10个决策树的决策森林就需要10倍多的数据，因此在决策森林构建问题上，数据不足问题更加严重。

小明：数据量确实是个非常严重的问题，没有足够的数据量就不能构建决策森林吗？

艾博士：为了解决数据不足的问题，提出了随机森林算法。

小明：随机森林算法中的“随机”是什么含义呢？又是如何解决数据不足问题的呢？

艾博士：设有数据集D，特征集合A，为了构建一个具有n个决策树的随机森林，在两个地方用到了“随机”。

一是从拥有N个样本的数据集D中有放回地随机抽取N个样本，用随机抽取到的数据集训练决策树，这样通过有放回地抽取数据的方法，就可以构建n个决策树。

小明问到：这里说的“有放回地随机抽取”是什么意思呢？

艾博士解释说：“有放回地随机抽取”指的是随机抽取到一个样本后，并不把该样本从数据集中删除，下次抽取时还可能会再次被抽取到。这样随机得到的不同数据集之间肯定是有大量重复样本的，即便是同一个数据集里边也会有重复样本。这样获取数据集的方法称作自举法。

小明：这样做有什么好处呢？

艾博士：决策森林里边的每一颗决策树我们都希望是不同的，这样投票才有意义。如何做到不同呢？只能是训练数据集不同。采用这种“有放回地随机抽取”方式得到的数据集具有与原始数据集D一样的大小，但是由于可能随机地出现重复样本，这样得到的n个数据集也就不同了，从而可以实现用与原始数据集D一样多的数据建立n个不同的决策树。

随机森林算法用到的第二个“随机”是指对特征做随机抽取。为了得到尽可能不同的n个决策树，除了对数据集做随机抽取以外，每次进行特征选择时对特征也做一次随机抽取，只有被抽取到的特征才有可能被选中。这样的话，即便数据集差别不大，但由于特征集有变化，也会得到不同的决策树。

采用这种方法构建的决策森林称作随机森林。

小明：那么随机森林中包括的决策树数应该如何确定呢？

艾博士：原则上来说，决策树越多随机森林的性能会越好，也就是错误率会越小。但是决策树越多，计算量也就越大，效率也就越低，所以应该在错误率和效率之间做一个平衡。同时由于采用有放回的随机抽取方法，采集的数据集数太多时，加大了出现雷同数据集的可能性，这也是我们不希望出现的结果。

小明：我猜测，当决策树数量达到一定程度后，随着决策树数量的增多，错误率应该接近饱和，不会再有显著的下降。所以是否可以以此作为一个原则决定决策树的数量呢？

艾博士：这是一个解决思路。这就涉及如何得到错误率的问题，因为测试错误率也需要数据。在随机森林中，由于每个决策树是通过随机采样获得的数据建立的，所以每个决策树都存在“集外”数据，也就是建立该决策树没有用到的数据。这样，可以利用集外数据作为测试用数据。

小明：利用集外数据进行测试确实是一个很好的想法，但是每个决策树的集外数据是不同的，如何测试也是一个问题吧？

艾博士：是这样的。由于每个决策树的训练数据集是不同的，所以集外数据也会不同。可以证明，对于每个决策树来说原数据集D中大约有三分之一的数据采集不到，属于集外数据，准确地说是大约 1/e=37% 的数据为集外数据。另一方面，对于数据集D中的每个样本来说，大约是三分之一决策树的集外数据。这样对于任意一个样本，都可以有大约三分之一的决策树组成一个小随机森林，用这个小随机森林对这个样本进行分类。最终可以得到一个分类错误率，该错误率我们称为集外错误率。该集外错误率可以作为随机森林错误率的一个估计。

小明：我了解了，对于任意一个样本，都有约三分之一决策树的训练数据集中不包含该样本，也就是集外数据，这样就可以用这三分之一的决策树组成一个小随机森林对这个样本做分类。而最终得到的错误率就是集外错误率，可以作为随机森林错误率的一个估计。这真是一个好的方法，充分利用了现有数据，在不增加数据量的情况下，就可以估算随机森林的错误率。

艾博士：大量实践证明，随机森林是一个性能很好的分类器，具有很好的泛化能力。充分体现了“三个臭皮匠顶个诸葛亮”的思想，利用多个“皮匠”（决策树），通过投票提高分类器的性能。

小明：随机森林中的决策树建造方法与普通的单个决策树的建造方法有什么不同吗？

艾博士：除了随机抽取数据、随机抽取特征外，决策树的建造方法是完全一样的，而且一般不需要剪枝处理，直接使用建造好的决策树即可。

小明：这样的话不会出现过拟合现象吗？

艾博士：对于每个决策树来说肯定会有过拟合现象的发生，但是由于随机森林具有多个决策树，通过投票方法决定最终的分类结果，过拟合现象并不明显，因为不同的决策树过拟合发生的位置（决策树的某个节点）是不一样的，通过投票可以一定程度上消除过拟合现象的发生。

小明读书笔记

决策树是一种特殊的树状结构，叶节点表示类别，非叶节点表示特征，按照特征的取值，逐步细化，实现分类。

为了构建一个比较好的决策树，重要的是如何选择特征的使用次序。ID3算法按照信息增益选择特征，优先使用信息增益大的特征。

一个特征的信息增益是数据集的熵与该特征的条件熵之差，反应了使用该特征之后，熵的降低程度。信息增益越大说明该特征对于该数据集的区分能力越强。

为了解决ID3算法中存在的倾向于优先使用取值多的特征的问题，提出了改进的决策树构建方法C4.5。C4.5按照信息增益率选择特征，并增加了对连续特征属性的处理。

采用剪枝方法可以解决过拟合问题。当数据量充足时，可以采用验证集的方法获得一个最佳的剪枝效果。也可以采用定义损失函数的方法，在训练集上获得一个比较好的剪枝结果。

随机森林是通过有放回采样的方法，随机地抽取多个数据集，利用每个数据集分别建立决策树，通过投票的方式最终决定分类结果。当特征数量比较多时，也可以对特征做采样，用采样得到的特征集构建决策树。

未完待续