加權隨機森林算法研究

楊 飚,尚秀偉

(北方工業大學 城市道路交通智能控制技術北京市重點實驗室，北京 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)