杨 飚,尚秀伟

(北方工业大学 城市道路交通智能控制技术北京市重点实验室，北京 100144)

加权随机森林算法研究

杨 飚,尚秀伟

(北方工业大学 城市道路交通智能控制技术北京市重点实验室，北京 100144)

随机森林可以产生高准确度的分类器，被广泛用于解决模式识别问题。然而，随机森林赋予每个决策树相同的权重，这在一定程度上降低了整个分类器的性能。为了解决这个问题，本文提出一种加权随机森林算法。该算法引入二次训练过程，提高分类正确率高的决策树投票权重，降低分类错误率高的决策树投票权重，从而提高整个分类器的分类能力。通过在不同数据集上的分类测试实验，证明了本文算法相比于传统的随机森林算法具有更强的分类性能。

随机森林; 权重训练；模式识别；决策树

0 引言

随机森林(Random Forests)最早由加利福尼亚大学的Leo Breiman[1]在2001年提出。它是一个由许多基础分类器“决策树”构成的组合分类器，不同决策树之间是独立同分布的，当输入一个测试样本时，由所有基础分类器的投票结果来确定最终样本的所属类别。传统的随机森林通过创建一系列独立同分布的决策树来分类样本，用投票结果来决策最终的分类结果。随机森林引入了两个随机化过程，使得不同的决策树分类器具有不同的分类能力，一些决策树的分类性能好，另一些决策树的分类性能差，但是，在确定一个样本属于哪个类别属性时，这两种决策树具有相同投票权重，因而会削弱分类器的整体性能。本文提出的加权随机森林算法通过引入二次训练，赋予决策树不同的权重，提高分类器的整体性能。

1 加权随机森林

1.1 随机森林介绍

早期，Breiman[2]采用bagging方法从训练集中有放回地随机选取数据来产生决策树；之后Dietterich[3]采用了在每个节点的K个最优分割中随机选取一个作为分割来产生决策树；另外的方法是从训练样本集构成的带有加权随机数据集中选择训练数据。随机森林是以K个决策树为基本分类器，进行集成学习后得到一个组合分类器。该算法由三步实现：首先，采用bootstrap抽样从原始数据集中抽取n个训练集，每个训练集的大小约为原始数据集的三分之二；其次，为每一个bootstrap训练集分别建立分类回归树，共产生n棵决策树构成一片“森林”，这些决策树均不进行剪枝，在每棵树生长过程中，并不是选择全部M个属性中的最优属性作为内部节点进行分支，而是从随机选择的m≤M个属性中选择最优属性进行分支；最后，由于各个决策树的训练是相互独立的，因此随机森林的训练可以通过并行处理来实现，这将大大提高生成模型的效率。将以同样的方式训练得到的K个决策树组合起来，就可以得到一个随机森林。当输入待分类的样本时，随机森林输出的分类结果由每个决策树的输出结果进行简单投票决定。

随机森林通过构建一系列独立同分布的决策树分别对样本进行判别，最后根据每个决策树投票来确定样本的最终类别。两个随机化过程决定了构建的决策树分类能力不同，但是在分类决策上，强分类器和弱分类器有相同的投票权重，这导致随机森林分类器整体性能下降。

1.2 权重二次训练

由于构建的决策树分类能力不同，一些决策树分类效果好，另一些分类效果差，应根据分类能力来设定相应决策树的权重。为了提高权重的鲁棒性，通过二次训练构造改进的随机森林分类器。将一次训练的结果重新导入分类器，进行二次训练，强化分类性能优的决策树权重，弱化分类性能差的决策树权重，提升分类水平。其训练流程如图1所示。

图1 加权随机森林训练流程图

首先，导入训练集，设定决策树数目，随机选择样本子集和样本特征子集，构造决策树，若构造的决策树数目等于设定的数目，则进行二次训练，否则重新设置决策树数目。导入二次训练后，对构造好的决策树的每一个叶子节点的投票权重设定为0.5，这对随机森林决定一个样本类别是没有影响的。然后对每棵决策树输入一个完备的训练样本集，样本到达某个叶子节点后，将该节点的权重调整为判断正确的样本数量与到达的样本总数之比，达到修正分类器权重的效果。加权随机森林叶子节点的投票权重如图2所示。

若修正完的决策树数目等于设定的决策树数目，则组合生成随机森林分类器，否则继续进行权重修正过程。

图2 加权随机森林叶子节点的投票权重示意图

以上过程中，随机决策树的最终决策在于叶子节点，这说明对随机决策树的权重修正也是由构成决策树的每个叶子节点决定。输入的任何一个样本最终都会到达其中的一个节点，而每个叶子节点有各自对应的样本类别属性。随机森林在每个叶子节点上对样本的判断是离散的，即到达该节点的样本不是正样本就是负样本。但是在实际的测试中发现，某些叶节点误判的概率很高，这就需要减低这些叶节点在投票时的权重。二次训练法就起到了修正分类器权重、增强分类性能的作用。综上所述，加权随机森林在判断样本集属于哪一样本类别时，是一个关于样本特征X、随机向量Θ和叶子节点权重ω的函数：

(1)

式中：ωk,j表示样本落入第k棵树第j个节点上时决策树对类别的投票权重系数。通过二次训练，分类效果好的叶节点的投票权重超过了0.5，相反地，分类效果差的叶节点的投票权重小于0.5，而训练样本未到达的叶子节点投票权重不变还为0.5。最终达到提升分类器整体分类性能的作用。

2 实验结果与分析

首先，采用两个数据集来进行测试。数据集1包含的是较为理想的数据，数据集2为含有噪声的复杂样本数据。表1列出了不同决策树数量下随机森林和加权随机森林的识别率(分类正确率)。

表1 决策树数目对识别率的影响

同时绘制不同决策树数目下随机森林和加权随机森林的识别率(分类正确率)曲线，如图3所示。

图3 数据集1和数据集2的识别率

由实验结果可知，决策树的数目影响随机森林分类器的分类性能，对于数据集1，随着决策树数量的增加，随机森林分类器的识别率也增加，改进后的随机森林识别率要比改进前上升得更快，提高了2%左右。对于数据集2，随着决策树数目的增加，改进后的随机森林比改进前的识别率要上升更快，但是当随机森林所包含的决策树的数量大于200棵时，识别率变化不明显，此时可以作为一个稳定的分类器应用到分类实验中。其次，在研究对比了HOG[4-5]特征和Haar[6]特征后,采用行人数据的HOG特征测试Adaboost算法[7-8]、SVM算法[9-10]、随机森林算法和加权随机森林算法性能。测试结果取识别率平均值得到如表2所示的实验结果。

由表2可知，实验中随机森林算法的分类效果优于SVM算法和Adaboost算法，其识别率比SVM算法高1.85%，比Adaboost高0.67%,加权随机森林算法比传统随机森林识别率提高了1.16%，比经典的SVM算法提高了3.01%。以上分析结果说明，加权随机森林算法在识别率上比传统的随机森林算法有一定的提高，分类性能更强，能够满足实际使用需求。

表2 分类器检测效果

3 结论

传统的随机森林由若干独立同分布的决策树构成，采用投票的方法进行分类。但是每棵决策树的分类能力不同，会导致随机森林分类器的整体性能有所下降。本文提出的加权随机森林算法通过引入二次训练对投票权重进行修正，达到提高分类器分类性能的效果。应用不同的数据进行测试，结果表明改进的加权随机森林算法识别率更好，分类性能更高，有一定的研究和实用价值。

[1] BREIMAN L. Random forests[J]. Machine Learning, 2001, 45(1):5-32.

[2] BREIMAN L. Bagging predictors[J]. Machine Learing, 1996,24(2):123-140.

[3] DIETTERICH T G. An expermental comparison of three methods for constructing ensembles of decision. trees:bagging,boosting and randomization[J].Machine Learning, 2002, 40(2):139-157.

[4] DALAL N, TRIGS B. Histograms of oriented gradients for human detection[C]. IEEE Computer Society Conference on Computer Vision and Pattern Recognition, New York: IEEE, New York: IEEE, 2005: 886-893.

[5] 肖华军,赵曙光,张乐，等.基于HOG-LBP特征融合的头肩检测研究[J].微型机与应用,2015,34(5):43-46,50.

[6] 林景亮,唐杰.一种融合肤色和Haar特征的人脸检测方法[J].微型机与应用,2013,32(8):35-37.

[7] 黄如锦，李谊，李文辉，等.基于多特征的Adaboost行人检测算法[J].吉林大学学报(理学版), 2010, 48(3):449-455.

[8] 李伟，何鹏举，杨恒，等.基于双阈值运动区域分割的Adaboost行人检测算法[J].计算机应用研究, 2012, 29(9): 3571-3574, 3596.

[9] 纪华.支持向量机的改进及其在岩土工程反分析中的应用[D].银川：宁夏大学, 2005.

[10] 涂宏斌, 周新建.基于支持向量机的轴承表面缺陷检测[J]. 现代制造工程, 2006(9)：90-92.

杨飚(1979-)， 男，博士，副教授，主要研究方向：机器学习、图像处理、智能交通。

尚秀伟(1989-)，女，硕士研究生，主要研究方向：图像处理、模式识别。

Weighted random forest algorithm

Yang Biao, Shang Xiuwei

(Beijing Key Lab of Urban Intelligent Traffic Control Technology, North China University of Technology, Beijing 100144, China)

Random forest can produce high accuracy classifier, which is widely used in pattern recognition. However, the random forest gives the same weight to each decision tree, which reduces the performance of the whole classifier to a certain extent. In order to solve this problem, this paper proposes a weighted random forest algorithm. The algorithm introduces the two training process to improve the classification accuracy of the decision tree voting weights, and reduce the decision tree voting weights of classification error rate of, so as to improve the classification ability of the whole classifier. Tests on different data sets show that the proposed algorithm is better than the traditional random forest algorithm.

random forest；weight training；pattern recognition；decision tree

TP391.41

A

1674- 7720(2016)03- 0028- 03

杨飚,尚秀伟．加权随机森林算法研究[J] .微型机与应用，2015，35(3)：28- 30.

2015-10-06)