楊 飚,尚秀偉

(北方工業(yè)大學(xué) 城市道路交通智能控制技術(shù)北京市重點實驗室，北京 100144)

加權(quán)隨機森林算法研究

楊 飚,尚秀偉

(北方工業(yè)大學(xué) 城市道路交通智能控制技術(shù)北京市重點實驗室，北京 100144)

隨機森林可以產(chǎn)生高準(zhǔn)確度的分類器，被廣泛用于解決模式識別問題。然而，隨機森林賦予每個決策樹相同的權(quán)重，這在一定程度上降低了整個分類器的性能。為了解決這個問題，本文提出一種加權(quán)隨機森林算法。該算法引入二次訓(xùn)練過程，提高分類正確率高的決策樹投票權(quán)重，降低分類錯誤率高的決策樹投票權(quán)重，從而提高整個分類器的分類能力。通過在不同數(shù)據(jù)集上的分類測試實驗，證明了本文算法相比于傳統(tǒng)的隨機森林算法具有更強的分類性能。

隨機森林; 權(quán)重訓(xùn)練；模式識別；決策樹

0 引言

隨機森林(Random Forests)最早由加利福尼亞大學(xué)的Leo Breiman[1]在2001年提出。它是一個由許多基礎(chǔ)分類器“決策樹”構(gòu)成的組合分類器，不同決策樹之間是獨立同分布的，當(dāng)輸入一個測試樣本時，由所有基礎(chǔ)分類器的投票結(jié)果來確定最終樣本的所屬類別。傳統(tǒng)的隨機森林通過創(chuàng)建一系列獨立同分布的決策樹來分類樣本，用投票結(jié)果來決策最終的分類結(jié)果。隨機森林引入了兩個隨機化過程，使得不同的決策樹分類器具有不同的分類能力，一些決策樹的分類性能好，另一些決策樹的分類性能差，但是，在確定一個樣本屬于哪個類別屬性時，這兩種決策樹具有相同投票權(quán)重，因而會削弱分類器的整體性能。本文提出的加權(quán)隨機森林算法通過引入二次訓(xùn)練，賦予決策樹不同的權(quán)重，提高分類器的整體性能。

1 加權(quán)隨機森林

1.1 隨機森林介紹

早期，Breiman[2]采用bagging方法從訓(xùn)練集中有放回地隨機選取數(shù)據(jù)來產(chǎn)生決策樹；之后Dietterich[3]采用了在每個節(jié)點的K個最優(yōu)分割中隨機選取一個作為分割來產(chǎn)生決策樹；另外的方法是從訓(xùn)練樣本集構(gòu)成的帶有加權(quán)隨機數(shù)據(jù)集中選擇訓(xùn)練數(shù)據(jù)。隨機森林是以K個決策樹為基本分類器，進行集成學(xué)習(xí)后得到一個組合分類器。該算法由三步實現(xiàn)：首先，采用bootstrap抽樣從原始數(shù)據(jù)集中抽取n個訓(xùn)練集，每個訓(xùn)練集的大小約為原始數(shù)據(jù)集的三分之二；其次，為每一個bootstrap訓(xùn)練集分別建立分類回歸樹，共產(chǎn)生n棵決策樹構(gòu)成一片“森林”，這些決策樹均不進行剪枝，在每棵樹生長過程中，并不是選擇全部M個屬性中的最優(yōu)屬性作為內(nèi)部節(jié)點進行分支，而是從隨機選擇的m≤M個屬性中選擇最優(yōu)屬性進行分支；最后，由于各個決策樹的訓(xùn)練是相互獨立的，因此隨機森林的訓(xùn)練可以通過并行處理來實現(xiàn)，這將大大提高生成模型的效率。將以同樣的方式訓(xùn)練得到的K個決策樹組合起來，就可以得到一個隨機森林。當(dāng)輸入待分類的樣本時，隨機森林輸出的分類結(jié)果由每個決策樹的輸出結(jié)果進行簡單投票決定。

隨機森林通過構(gòu)建一系列獨立同分布的決策樹分別對樣本進行判別，最后根據(jù)每個決策樹投票來確定樣本的最終類別。兩個隨機化過程決定了構(gòu)建的決策樹分類能力不同，但是在分類決策上，強分類器和弱分類器有相同的投票權(quán)重，這導(dǎo)致隨機森林分類器整體性能下降。

1.2 權(quán)重二次訓(xùn)練

由于構(gòu)建的決策樹分類能力不同，一些決策樹分類效果好，另一些分類效果差，應(yīng)根據(jù)分類能力來設(shè)定相應(yīng)決策樹的權(quán)重。為了提高權(quán)重的魯棒性，通過二次訓(xùn)練構(gòu)造改進的隨機森林分類器。將一次訓(xùn)練的結(jié)果重新導(dǎo)入分類器，進行二次訓(xùn)練，強化分類性能優(yōu)的決策樹權(quán)重，弱化分類性能差的決策樹權(quán)重，提升分類水平。其訓(xùn)練流程如圖1所示。

圖1 加權(quán)隨機森林訓(xùn)練流程圖

首先，導(dǎo)入訓(xùn)練集，設(shè)定決策樹數(shù)目，隨機選擇樣本子集和樣本特征子集，構(gòu)造決策樹，若構(gòu)造的決策樹數(shù)目等于設(shè)定的數(shù)目，則進行二次訓(xùn)練，否則重新設(shè)置決策樹數(shù)目。導(dǎo)入二次訓(xùn)練后，對構(gòu)造好的決策樹的每一個葉子節(jié)點的投票權(quán)重設(shè)定為0.5，這對隨機森林決定一個樣本類別是沒有影響的。然后對每棵決策樹輸入一個完備的訓(xùn)練樣本集，樣本到達某個葉子節(jié)點后，將該節(jié)點的權(quán)重調(diào)整為判斷正確的樣本數(shù)量與到達的樣本總數(shù)之比，達到修正分類器權(quán)重的效果。加權(quán)隨機森林葉子節(jié)點的投票權(quán)重如圖2所示。

若修正完的決策樹數(shù)目等于設(shè)定的決策樹數(shù)目，則組合生成隨機森林分類器，否則繼續(xù)進行權(quán)重修正過程。

圖2 加權(quán)隨機森林葉子節(jié)點的投票權(quán)重示意圖

以上過程中，隨機決策樹的最終決策在于葉子節(jié)點，這說明對隨機決策樹的權(quán)重修正也是由構(gòu)成決策樹的每個葉子節(jié)點決定。輸入的任何一個樣本最終都會到達其中的一個節(jié)點，而每個葉子節(jié)點有各自對應(yīng)的樣本類別屬性。隨機森林在每個葉子節(jié)點上對樣本的判斷是離散的，即到達該節(jié)點的樣本不是正樣本就是負樣本。但是在實際的測試中發(fā)現(xiàn)，某些葉節(jié)點誤判的概率很高，這就需要減低這些葉節(jié)點在投票時的權(quán)重。二次訓(xùn)練法就起到了修正分類器權(quán)重、增強分類性能的作用。綜上所述，加權(quán)隨機森林在判斷樣本集屬于哪一樣本類別時，是一個關(guān)于樣本特征X、隨機向量Θ和葉子節(jié)點權(quán)重ω的函數(shù)：

(1)

式中：ωk,j表示樣本落入第k棵樹第j個節(jié)點上時決策樹對類別的投票權(quán)重系數(shù)。通過二次訓(xùn)練，分類效果好的葉節(jié)點的投票權(quán)重超過了0.5，相反地，分類效果差的葉節(jié)點的投票權(quán)重小于0.5，而訓(xùn)練樣本未到達的葉子節(jié)點投票權(quán)重不變還為0.5。最終達到提升分類器整體分類性能的作用。

2 實驗結(jié)果與分析

首先，采用兩個數(shù)據(jù)集來進行測試。數(shù)據(jù)集1包含的是較為理想的數(shù)據(jù)，數(shù)據(jù)集2為含有噪聲的復(fù)雜樣本數(shù)據(jù)。表1列出了不同決策樹數(shù)量下隨機森林和加權(quán)隨機森林的識別率(分類正確率)。

表1 決策樹數(shù)目對識別率的影響

同時繪制不同決策樹數(shù)目下隨機森林和加權(quán)隨機森林的識別率(分類正確率)曲線，如圖3所示。

圖3 數(shù)據(jù)集1和數(shù)據(jù)集2的識別率

由實驗結(jié)果可知，決策樹的數(shù)目影響隨機森林分類器的分類性能，對于數(shù)據(jù)集1，隨著決策樹數(shù)量的增加，隨機森林分類器的識別率也增加，改進后的隨機森林識別率要比改進前上升得更快，提高了2%左右。對于數(shù)據(jù)集2，隨著決策樹數(shù)目的增加，改進后的隨機森林比改進前的識別率要上升更快，但是當(dāng)隨機森林所包含的決策樹的數(shù)量大于200棵時，識別率變化不明顯，此時可以作為一個穩(wěn)定的分類器應(yīng)用到分類實驗中。其次，在研究對比了HOG[4-5]特征和Haar[6]特征后,采用行人數(shù)據(jù)的HOG特征測試Adaboost算法[7-8]、SVM算法[9-10]、隨機森林算法和加權(quán)隨機森林算法性能。測試結(jié)果取識別率平均值得到如表2所示的實驗結(jié)果。

由表2可知，實驗中隨機森林算法的分類效果優(yōu)于SVM算法和Adaboost算法，其識別率比SVM算法高1.85%，比Adaboost高0.67%,加權(quán)隨機森林算法比傳統(tǒng)隨機森林識別率提高了1.16%，比經(jīng)典的SVM算法提高了3.01%。以上分析結(jié)果說明，加權(quán)隨機森林算法在識別率上比傳統(tǒng)的隨機森林算法有一定的提高，分類性能更強，能夠滿足實際使用需求。

表2 分類器檢測效果

3 結(jié)論

傳統(tǒng)的隨機森林由若干獨立同分布的決策樹構(gòu)成，采用投票的方法進行分類。但是每棵決策樹的分類能力不同，會導(dǎo)致隨機森林分類器的整體性能有所下降。本文提出的加權(quán)隨機森林算法通過引入二次訓(xùn)練對投票權(quán)重進行修正，達到提高分類器分類性能的效果。應(yīng)用不同的數(shù)據(jù)進行測試，結(jié)果表明改進的加權(quán)隨機森林算法識別率更好，分類性能更高，有一定的研究和實用價值。

[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].微型機與應(yīng)用,2015,34(5):43-46,50.

[6] 林景亮,唐杰.一種融合膚色和Haar特征的人臉檢測方法[J].微型機與應(yīng)用,2013,32(8):35-37.

[7] 黃如錦，李誼，李文輝，等.基于多特征的Adaboost行人檢測算法[J].吉林大學(xué)學(xué)報(理學(xué)版), 2010, 48(3):449-455.

[8] 李偉，何鵬舉，楊恒，等.基于雙閾值運動區(qū)域分割的Adaboost行人檢測算法[J].計算機應(yīng)用研究, 2012, 29(9): 3571-3574, 3596.

[9] 紀(jì)華.支持向量機的改進及其在巖土工程反分析中的應(yīng)用[D].銀川：寧夏大學(xué), 2005.

[10] 涂宏斌, 周新建.基于支持向量機的軸承表面缺陷檢測[J]. 現(xiàn)代制造工程, 2006(9)：90-92.

楊飚(1979-)， 男，博士，副教授，主要研究方向：機器學(xué)習(xí)、圖像處理、智能交通。

尚秀偉(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

楊飚,尚秀偉．加權(quán)隨機森林算法研究[J] .微型機與應(yīng)用，2015，35(3)：28- 30.

2015-10-06)