王 杰， 程學新， 彭金柱

(鄭州大學 電氣工程學院 河南 鄭州 450001)

0 引言

隨機森林(RF)算法是一種分類模型，其本質(zhì)是將Bagging算法和random subspace算法結(jié)合起來[1-3]，通過構(gòu)造多棵決策樹分類器對測試樣本進行分類，然后對這些決策樹采取投票選取機制確定最終的分類結(jié)果.由于隨機森林模型對噪聲和異常值的容忍度較高，且隨機森林直接通過數(shù)據(jù)進行分類，不需要分類樣本的先驗知識，因此可省略數(shù)據(jù)預處理的工作.隨機森林算法自提出之后，被廣泛地運用于數(shù)據(jù)挖掘與分類問題中[4-6].

針對隨機森林算法中存在的一些問題，學者們提出了不同的方案，對隨機森林算法進行改進.文獻[7]從選取特征、訓練樣本等多個方面對隨機森林進行改進，提升了訓練準確率.文獻[8]提出了基于生存樹的隨機森林模型(RSF)，證明了隨機生存森林對于高維樣本的分類能力大于普通隨機森林.文獻[9]將分位數(shù)回歸理論引入隨機森林中，提出了分位數(shù)回歸森林(QRF).在處理生長較差的決策樹方面，文獻[10]將隨機森林算法中每棵決策樹按分類性能進行排序，并淘汰掉分類性能差的決策樹.但此方法的弊端在于容易淘汰掉僅對某一類別分類較好的決策樹，從而影響該類別最終的分類效果.文獻[11]提出了加權(quán)投票的概念，但其權(quán)值的計算方式不夠優(yōu)秀，很容易出現(xiàn)特別大的權(quán)值，從而使隨機森林的投票都集中于較少的幾棵樹.隨后，文獻[12]將以上兩種方法相結(jié)合，采用out-of-bag準確率作為決策樹投票權(quán)重并保留70%的決策樹.此方法的弊端在于每棵決策樹out-of-bag樣本不同從而導致投票不能保證其公平性.此外，至今為止較少有文獻提及隨機森林中各參數(shù)對模型的影響，決策樹棵數(shù)或剪枝閾值的選取也沒有理論上的支持，通常只能靠經(jīng)驗選取.

為解決以上問題，本文提出了一種基于粒子群算法優(yōu)化的加權(quán)隨機森林算法(PSOWRF)，采用粒子群算法對隨機森林模型進行優(yōu)化，通過迭代優(yōu)化的方式選取決策樹棵數(shù)、剪枝閾值等參數(shù).同時，為解決投票權(quán)重問題，本文從訓練樣本中提取出一部分樣本，作為預測試樣本，用來計算每棵決策樹的權(quán)值，從而保證其投票的公平性.而本文對權(quán)值的計算方式加以簡化，僅采用預測試樣本的分類正確率作為每棵決策樹的權(quán)值.其原因在于過于復雜的權(quán)值計算方式會極大地增加訓練時間，而采用較為簡單的正確率加權(quán)方法，經(jīng)過粒子群算法優(yōu)化之后，同樣可保證其分類精確度.

1 決策樹算法

1.1 ID3算法

隨機森林算法是由多棵決策樹分類器構(gòu)成，故在研究隨機森林算法之前，需要對決策樹有一定的了解.目前有很多種決策樹生成算法，但最有影響力的是Quinlan的ID3算法.該算法在決策樹中引入信息論的概念，并定義了信息增益.ID3算法的原理如下所示：假設樣本S可按照目標屬性分成c個不同的類別，則其分類的熵的定義為

(1)

其中：pi為目標屬性的第i個值所對應的樣本在總樣本S中所占的比例.

以上定義的分類熵可作為樣本S的純度判別標準，即Entropy(S)=0表示樣本S屬于同一種類別.根據(jù)此定義，可進一步引伸出樣本S中決策屬性A的信息增益Gain(S,A)的定義為

(2)

其中：V(A)是決策屬性A的值域，|Sv|是屬性A的值為v的樣本數(shù)量，|S|是總樣本數(shù)量.

ID3算法就是每次都選取擁有最大信息增益的屬性作為其分類屬性進行分類，而分類屬性臨界值的選取也要最大化信息增益，直到所有結(jié)點的分類熵值為0.若樣本的所有屬性均參與分類后分類熵仍大于0，則返回該樣本中目標屬性的眾數(shù)所對應的分類作為該樣本最終的分類結(jié)果.

1.2 C4.5算法

ID3算法雖可正確地進行分類，但仍存在許多問題.ID3算法只能對離散的數(shù)據(jù)進行分類，無法處理連續(xù)數(shù)據(jù).且ID3算法沒有剪枝的步驟，甚至可能導致每個葉結(jié)點只包含一個樣本，產(chǎn)生過擬合現(xiàn)象.C4.5算法是對ID3算法的一個改進，它采用信息增益率而非信息增益來選擇決策屬性.信息增益率的定義為：

(3)

此外，C4.5算法還加入了前剪枝的步驟.即在分類過程中，當某集合的樣本數(shù)小于一個給定的閾值ε時，就直接將此集合看作一個葉結(jié)點，然后返回目標屬性的眾數(shù)作為分類結(jié)果.閾值ε直接決定了決策樹是否會出現(xiàn)過擬合現(xiàn)象或者出現(xiàn)分類不準確，但ε只能憑經(jīng)驗選取，并無理論上的支持.

2 隨機森林模型及其優(yōu)化

2.1 隨機森林模型

隨機森林模型的實質(zhì)是一個有多棵互不相關決策樹的分類器.每棵決策樹均采用Bootstrap方法進行采樣，然后再從所有的M個決策屬性中隨機挑選出m個屬性進行分類.在整個訓練過程中，一般m的取值不變.訓練完成后，當測試樣本輸入時，每棵決策樹均對測試樣本進行分類，并采取投票的方法決定該測試樣本的最終分類結(jié)果.假設對于一個測試樣本x，第l棵決策樹的輸出為ftree,l(x)=i，i=1,2,…,c，即為其對應的類別，l=1,2,…,L，L為隨機森林中的決策樹棵數(shù),則隨機森林模型(RF)的輸出為

(4)

其中：I(·)表示滿足括號中表達式的樣本個數(shù).

2.2 隨機森林模型加權(quán)

在傳統(tǒng)的隨機森林模型中，每棵決策樹在投票時權(quán)重都相等，但又不能保證每棵決策樹的分類精度一致.因此，總會有一些訓練精度不高的決策樹投出錯誤的票數(shù)，從而影響了整個隨機森林的分類能力.為了降低訓練精度不高的決策樹對整個模型的影響，本文提出了一種加權(quán)隨機森林模型.其核心是將訓練樣本分為兩部分：一部分作為傳統(tǒng)隨機森林模型的訓練樣本，對所有的隨機數(shù)進行訓練；另一部分為預測試樣本，在訓練完成之后，對每棵決策樹分別進行測試，并計算其分類正確率，

(5)

其中：Xcorrect,l為第l棵樹分類正確的樣本數(shù)，X為預測試樣本數(shù).

將此正確率作為對應決策樹的權(quán)重，每棵決策樹在進行投票時，都要乘以此權(quán)值.則加權(quán)隨機森林模型(WRF)的輸出為：

(6)

2.3 隨機森林模型PSO加權(quán)優(yōu)化

以上算法中，剪枝閾值ε、決策樹棵數(shù)L、預測試樣本數(shù)X、隨機屬性個數(shù)m等參數(shù)對整個模型的輸出具有一定的影響.但所有參數(shù)均需要通過經(jīng)驗選取，并沒有理論上的支持.粒子群算法通過對鳥類捕食行為進行模擬，能夠快速地選取最優(yōu)解.本文通過將粒子群算法引入模型，對加權(quán)隨機森林算法中的參數(shù)進行迭代優(yōu)化，最終達到了較好的分類效果.

粒子群優(yōu)化加權(quán)隨機森林算法的步驟如下：

Step1 確定算法的參數(shù)，隨機設定出剪枝閾值ε、決策樹棵數(shù)L、預測試樣本數(shù)X、隨機屬性個數(shù)m的初值；

Step2 采用Bootstrap算法采樣，隨機生產(chǎn)L個訓練集，并在每個訓練集中選出X個預測試樣本；

Step3 利用每個訓練集剩下的樣本分別生成決策樹，共L棵，在生成過程中，每次選擇屬性前，均從全部屬性中選出m個屬性作為當前結(jié)點的決策屬性；

Step4 當結(jié)點內(nèi)包含的樣本數(shù)少于閾值ε時，將該結(jié)點作為葉結(jié)點，并返回其目標屬性的眾數(shù)作為該決策樹的分類結(jié)果；

Step5 當所有決策樹生成后，對每棵決策樹進行預測試，并利用式(5)計算其權(quán)值；

Step6 利用式(6)計算出模型的分類結(jié)果；

Step7 將分類結(jié)果作為適應度值，采用粒子群算法對Step1中提到的參數(shù)進行迭代優(yōu)化，確定最終模型的參數(shù).

3 實驗驗證及分析

本文中用到的實驗數(shù)據(jù)均來自于加利福尼亞大學的UCI數(shù)據(jù)庫，并選取了其中Abalone、Banks、Car Evaluation、Letter、Wine Quality和Yeast共6個數(shù)據(jù)集.為了驗證模型參數(shù)對加權(quán)隨機森林算法分類能力的影響，本文選取Wine Quality數(shù)據(jù)集作為驗證數(shù)據(jù)集，分別對剪枝閾值ε和決策樹棵數(shù)L進行驗證.實驗1對剪枝閾值ε在0到30之間進行取值，并記錄所得分類準確率.實驗1的結(jié)果如圖1所示.實驗2對決策樹棵數(shù)L分別取值為10到100之間的10的整數(shù)倍，其結(jié)果如圖2所示.

圖1 剪枝閾值對分類性能的影響Fig.1 Effect of pruning threshold on test accuracy

圖2 決策樹棵數(shù)對性能的影響Fig.2 Effect of tree’s number on test accuracy

通過圖1可看出，隨著剪枝閾值ε的不斷增加，分類性能呈現(xiàn)一個下降的趨勢.因此對于數(shù)據(jù)集Wine Quality來說，剪枝閾值ε為0可取得最高的分類準確率.從圖2可發(fā)現(xiàn)，決策樹棵數(shù)在50以后，分類的準確率在0.59左右開始波動.故對于數(shù)據(jù)集Wine Quality，最佳的決策樹棵數(shù)為50.因此可說明，Step1中提及的參數(shù)對模型的分類性能具有一定的影響.為保證選取到最優(yōu)值，本文采用粒子群算法對模型進行優(yōu)化，提出粒子群優(yōu)化加權(quán)隨機森林算法(PSOWRF)，并在6組數(shù)據(jù)集上進行測試.將其訓練結(jié)果與文獻[12]中提到的普通加權(quán)隨機森林(WRF)、分位數(shù)回歸森林(QRF)、隨機生存森林(RSF)、傳統(tǒng)隨機森林(RF)、C4.5決策樹分類器(DT)、支持向量機(SVM)和BP神經(jīng)網(wǎng)絡等傳統(tǒng)分類器進行對比，結(jié)果如表1所示.表1中記錄了所有算法對6個數(shù)據(jù)集的平均分類正確率. 每個數(shù)據(jù)集名之后括號中的兩個數(shù)字分類代表了該數(shù)據(jù)集的屬性個數(shù)和類別個數(shù).

表1 不同算法分類性能比較

注：粗體代表了每個數(shù)據(jù)集的最優(yōu)正確率，下劃線代表了與最優(yōu)正確率無統(tǒng)計學差異.

根據(jù)表1可以得到，PSOWRF在Abalone、Car Evaluation、Letter 3個數(shù)據(jù)集上均取得了最優(yōu)分類正確率，同時在Banks和Wine Quality兩個數(shù)據(jù)集上的分類正確率與最優(yōu)正確率無統(tǒng)計學差異.對于Abalone數(shù)據(jù)集，PSOWRF取得了最優(yōu)結(jié)果，WRF、RSF、QRF和SVM的表現(xiàn)情況相差不大，均比RF、DT和BP算法更加優(yōu)秀.對于高維的數(shù)據(jù)集Banks和Wine Quality，RSF充分展示了其對高維數(shù)據(jù)的分類能力，取得最優(yōu)解，而PSOWRF也表現(xiàn)良好，與RSF無明顯差異.對于數(shù)據(jù)集Car Evaluation，PSOWRF和QRF、SVM同時取得較好的分類結(jié)果，優(yōu)于其他算法.對于多類別的Letter數(shù)據(jù)集，PSOWRF遠遠領先于其他算法，取得最優(yōu)結(jié)果.最后，對于Yeast數(shù)據(jù)集，SVM算法超過了所有的隨機森林算法及改進.綜上所述，本文所提出的PSOWRF算法在除Yeast之外的5個數(shù)據(jù)集上均能夠取得不錯的表現(xiàn)，而且在Abalone和Letter數(shù)據(jù)集上要明顯優(yōu)于其他算法.

4 結(jié)論

本文對隨機森林模型的投票機制做出了一定的改進，從訓練樣本中提取出一部分預測試樣本，并將每棵決策樹對預測試樣本的分類正確率作為其投票權(quán)值.為保證模型參數(shù)能夠取得最優(yōu)值，本文還利用粒子群算法對模型進行優(yōu)化，提出了基于粒子群優(yōu)化的加權(quán)隨機森林算法.該算法在6組實驗數(shù)據(jù)集上均取得了良好的結(jié)果.在今后的工作中，我們將會對隨機森林模型的采樣機制進行研究.通過對比不同采樣算法對分類性能的影響，決定出最優(yōu)的采樣算法，而不局限于僅用Bootstrap算法進行采樣.

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

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

[3] HO T. The random subspace method for constructing decision forests[J]. IEEE transactions on pattern analysis and machine intelligence, 1998, 20(8):832-844.

[4] 李欣海. 隨機森林模型在分類與回歸分析中的應用[J]. 應用昆蟲學報, 2013, 50(4):1190-1197.

[5] 林成德, 彭國蘭. 隨機森林在企業(yè)信用評估指標體系確定中的應用[J]. 廈門大學學報(自然科學版), 2007, 46(2):199-203.

[6] 楊帆, 林琛, 周綺鳳，等. 基于隨機森林的潛在k近鄰算法及其在基因表達數(shù)據(jù)分類中的應用[J]. 系統(tǒng)工程理論與實踐, 2012, 32(4):815-825.

[7] ROBNIK-IKONJA M. Improving random forests[C]∥15th European Conference on Machine Learning. Italy, 2004.

[8] ISHWARAN H, KOGALUR U B, BLACKSTONE E H, et al. Random survival forests[J]. Journal of thoracic oncology official publication of the international association for the study of lung cancer, 2008, 6(12):1974-1975.

[9] NICOLAI M. Quantile regression forests[J]. Journal of machine learning research, 2006, 7(2):983-999.

[10] CROUX C, JOOSSENS K, LEMMENS A. Trimmed bagging[J]. Computational statistics & data analysis, 2007, 52(1):362-368.

[11] AMARATUNGA D, CABRERA J, LEE Y S. Enriched random forests[J]. Bioinformatics, 2008, 24(18):2010-2014.

[12] XU B, GUO X, YE Y, et al. An improved random forest classifier for text categorization[J]. Journal of computers, 2012, 7(12):2913-2920.