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

　　關(guān)鍵詞：隨機(jī)森林; 權(quán)重訓(xùn)練；模式識別；決策樹

　　0引言

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

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

　　1.1隨機(jī)森林介紹

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

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

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

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

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

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

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

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

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

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

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

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

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

3結(jié)論

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

參考文獻(xiàn)

　　［1］ BREIMAN L. Random forests［J］. Machine Learning, 2001, 45(1):532.

　?。?］ 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.

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

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

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

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

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

　?。?0］ 涂宏斌, 周新建.基于支持向量機(jī)的軸承表面缺陷檢測［J］. 現(xiàn)代制造工程, 2006（9）：9092.