溫博文，董文瀚，解武杰，馬 駿

空軍工程大學 航空航天工程學院，西安 710038

1 引言

隨機森林算法是由Breiman于2001年提出的一種集成學習算法，并在文獻[1]用強大數(shù)定理證明了其收斂性。其后，國內(nèi)外學者相繼對其進行了后續(xù)研究。在國外，Kulkarni等通過將維度分為兩部分，一定程度上提高了正確率[2-3]。Oshiro等證明了隨機森林的決策樹數(shù)量存在一個臨界值使其性能達到最優(yōu)[4]。Bernard等研究了隨機森林強度與相關性的關系，內(nèi)在分析了隨機森林的原理[5]。在國內(nèi)，馬景義等綜合了Adaboost算法和隨機森林算法的優(yōu)勢，提出了擬自適應分類隨機森林算法[6]。劉迎春等基于隨機森林算法，設計了互聯(lián)網(wǎng)行業(yè)的大數(shù)據(jù)流式應用場景中的流式計算方法[7]。

隨機森林是一種有效的機器學習方法，可應用于分類問題、回歸問題以及特征選擇問題[8]。隨機森林是由決策樹作為基分類器的集成學習模型，結(jié)合了Bagging和隨機子空間理論。隨機森林算法引入了兩個隨機量：一是從訓練集中有放回地隨機抽取樣本數(shù)據(jù)組成自助訓練集；二是在構(gòu)建決策樹的過程中隨機選擇特征屬性作為候選分裂屬性。正是由于兩個隨機量的引入，隨機森林對噪聲數(shù)據(jù)不敏感，克服了過擬合的問題。由于隨機森林具有良好的性能，因此在諸多領域得到了廣泛的應用。但到目前為止，對隨機森林算法中決策樹數(shù)量k、候選分裂屬性數(shù)mtry等參數(shù)進行優(yōu)化選擇的研究還較少，通常都是通過經(jīng)驗選擇參數(shù)，在文獻[1]中，Breiman選取mtry為1和「lb M +1」進行了試驗，M為訓練樣本集特征維數(shù)。文獻[9-10]選擇mtry=進行試驗，Panov等[11]則對 mtry=「lb M +1」和mtry=分別進行了試驗。文獻[12]研究了隨機森林算法中決策樹數(shù)量對其性能的影響，并指出對于不同的具體對象而言，使其性能達到最優(yōu)時的k值是不同的。通過經(jīng)驗選擇隨機森林算法的參數(shù)，往往得不到性能最優(yōu)的隨機森林。

本文針對上述問題，采用改進的網(wǎng)格搜索算法，基于袋外數(shù)據(jù)估計，對隨機森林算法的決策樹數(shù)量和候選分裂屬性數(shù)兩個參數(shù)進行優(yōu)化，該方法能夠克服交叉驗證的缺點，選取到參數(shù)最優(yōu)值。UCI數(shù)據(jù)集的仿真實驗結(jié)果表明，利用本文提出的方法能夠使隨機森林分類性能達到最優(yōu)。

2 隨機森林原理

隨機森林算法是由多個決策樹{h(x,Θk),k=1,2,…}組成的集成算法，其中Θk為相互獨立且同分布的隨機變量，決定自助訓練集的隨機抽取和候選分裂屬性的隨機選擇，即決定決策樹的生成。對于分類問題，采用簡單多數(shù)投票法的結(jié)果作為隨機森林的輸出；對于回歸問題，根據(jù)單棵樹輸出結(jié)果的簡單平均作為隨機森林的輸出[13]。

隨機森林的構(gòu)建過程如圖1所示[14]。

圖1 隨機森林的構(gòu)建過程

（1）從大小為N的訓練數(shù)據(jù)集L中有放回地隨機抽取N個訓練數(shù)據(jù)樣本，得到一個自助訓練集L(B)k。

（2）以L(B)k為訓練數(shù)據(jù)，創(chuàng)建決策樹Tk(x)。對每個節(jié)點的分裂，從M個特征屬性中隨機選取mtry個作為候選分裂屬性，根據(jù)基尼指數(shù)從mtry個特征屬性中選擇一個進行分裂，重復上述過程，直至這棵樹能夠準確分類訓練數(shù)據(jù)，或所有特征屬性均已被使用過。在構(gòu)建決策樹的過程中，本文采用CART算法分裂節(jié)點，即選用基尼指數(shù)最小的分裂方式進行分裂。

選用基尼指數(shù)進行分裂時，如果一個訓練樣本集合T含有m個不同類別的樣本，那么該樣本集合的基尼指數(shù)為[8]：

式中，pi為第i類樣本的概率。如果一個樣本集T被劃分為了l個樣本子集T1,T2,…,Tl，子集所含樣本數(shù)分別為N1,N2,…,Nl，則這次分裂的基尼指數(shù)為[8]：

在上述構(gòu)建隨機森林的過程中，第一步利用統(tǒng)計學中的重采樣技術隨機抽取k個自助訓練集時，對于每次抽取大約有36.8%的訓練樣本未被抽中，這些未被抽中的訓練樣本稱為袋外數(shù)據(jù)。Breiman在文獻[1]中指出，利用袋外數(shù)據(jù)可以對決策樹的強度和決策樹之間的相關性進行估計。袋外數(shù)據(jù)估計的決策樹的泛化誤差與使用和訓練集相同大小的測試集的泛化誤差相同[15]，因此可以利用袋外數(shù)據(jù)對本文提出的方法進行泛化誤差估計。

3 基于改進網(wǎng)格搜索的隨機森林參數(shù)優(yōu)化

網(wǎng)格搜索是指將變量區(qū)域網(wǎng)格化，遍歷所有網(wǎng)格點，求解滿足約束函數(shù)的目標函數(shù)值，最終比較選擇出最優(yōu)點。遍歷網(wǎng)格上所有點需要大量訓練時間，為了提高訓練速度，本文提出了一種基于改進的網(wǎng)格搜索的隨機森林參數(shù)優(yōu)化算法。首先，在較大范圍內(nèi)用大步長劃分網(wǎng)格，進行粗搜索選擇出最優(yōu)點。然后在最優(yōu)點附近利用小步長劃分網(wǎng)格，使網(wǎng)格劃分更加密集，再次進行搜索選擇出最優(yōu)點。重復以上步驟，直至網(wǎng)格間距或目標函數(shù)變化量小于給定值。

為了提高隨機森林算法的分類性能，需要同時考慮單棵決策樹的分類正確率和樹的多樣性，然而兩者之間也存在著一定關系。到目前為止仍沒有關于兩者關系對隨機森林性能影響的研究[16]。本文針對隨機森林算法中決策樹數(shù)k和候選分裂屬性數(shù)mtry為離散值的特點，采用網(wǎng)格搜索算法進行參數(shù)優(yōu)化。本文提出的基于改進的網(wǎng)格搜索的隨機森林參數(shù)優(yōu)化的目標函數(shù)值選用袋外數(shù)據(jù)估計的分類誤差。由于隨機森林在構(gòu)建過程中的隨機性，分類誤差可能會在一定范圍內(nèi)波動，因此為減小不確定性對參數(shù)選擇產(chǎn)生的影響，本文在求分類誤差時選用多個隨機森林模型分類誤差的平均值。具體步驟如下：

（1）確定決策樹的數(shù)量k和候選分裂屬性數(shù)mtry的范圍，設定步長，在k和mtry坐標系上建立二維網(wǎng)格，網(wǎng)格節(jié)點就是相應的k和mtry的參數(shù)對。

（2）對網(wǎng)格節(jié)點上的每一組參數(shù)構(gòu)建隨機森林，并利用袋外數(shù)據(jù)估計分類誤差。

（3）選擇分類誤差最小的參數(shù)k,mtry,若分類誤差或者步長滿足要求，則輸出最優(yōu)參數(shù)和分類誤差；否則，縮小步長，重復上述步驟，繼續(xù)搜索。

上述搜索過程可用圖2所示的流程圖進行表示。

圖2 基于改進的網(wǎng)格搜索算法的隨機森林參數(shù)尋優(yōu)流程圖

4 仿真驗證

本文選取了UCI數(shù)據(jù)庫中的11個數(shù)據(jù)集，表1對數(shù)據(jù)集的樣本數(shù)、特征維數(shù)、類別數(shù)做出了簡要描述。

表1 UCI數(shù)據(jù)集

現(xiàn)以spambase數(shù)據(jù)集為例基于網(wǎng)格搜索對隨機森林算法的參數(shù)進行優(yōu)化。spambase是歸類為“垃圾郵件”和“非垃圾郵件”兩類的電子郵件數(shù)據(jù)集。在進行大步長粗搜索時，決策樹的數(shù)量k的取值范圍設定為50≤k≤500，步長設定為50，候選分裂屬性mtry取值范圍設定為1≤mtry≤57，步長設定為10。搜索結(jié)果如圖3所示。

圖3 隨機森林參數(shù)粗搜索結(jié)果圖

由圖3可以看出，基于網(wǎng)格搜索進行大步長粗搜索時，發(fā)現(xiàn)當決策樹數(shù)量k=400，候選分裂屬性數(shù)mtry=5時，隨機森林的泛化誤差最小，為0.055 963。同時可以看出，隨著隨機森林的候選分裂屬性數(shù)mtry增大，分類的效果并不是越來越好。這是因為隨機森林的泛化誤差與決策樹之間的相關性成正比。隨著候選分裂屬性的增多，決策樹之間的相關性越高，所以在mtry增加到某一數(shù)值后，分類效果反而出現(xiàn)了下降。隨著決策樹的數(shù)量逐漸增加，隨機森林的泛化誤差逐漸減小，當決策樹的數(shù)量增加到某一數(shù)值后，泛化誤差趨于穩(wěn)定。

圖4為利用網(wǎng)格搜索對隨機森林進行參數(shù)優(yōu)化選擇的結(jié)果。在粗搜索得到的最優(yōu)點k=400，mtry=5附近進行網(wǎng)格劃分。k的取值范圍為360≤k≤440，步長設定為10，mtry的取值范圍為1≤mtry≤9，步長設定為1。由圖4可以看出，當決策樹的數(shù)量k=440，候選分裂屬性數(shù)mtry=5時，隨機森林的泛化誤差最小，為0.053 518。

圖4 隨機森林參數(shù)大步長搜索結(jié)果圖

為驗證本文提出的方法對其他數(shù)據(jù)集也適用，本文對表1中剩余數(shù)據(jù)集重復上述步驟，進行網(wǎng)格搜索，得到隨機森林相應的決策樹數(shù)量k和候選分裂屬性數(shù)mtry的優(yōu)化參數(shù)以及優(yōu)化參數(shù)后的泛化誤差如表2。

表2 基于UCI數(shù)據(jù)集的隨機森林參數(shù)尋優(yōu)結(jié)果

表2中的第4列為mtry=lb「 M +1」，k=200時隨機森林的泛化誤差，第5列為利用本文提出的方法進行參數(shù)選擇后隨機森林的泛化誤差。由表2可以看出，基于改進的網(wǎng)格搜索算法對隨機森林算法的參數(shù)進行優(yōu)化，可以使隨機森林的分類效果得到一定程度的提高。

采用基于改進的網(wǎng)格搜索的隨機森林參數(shù)優(yōu)化算法和網(wǎng)格搜索的隨機森林參數(shù)優(yōu)化算法分別對表1中的11個數(shù)據(jù)集進行訓練，得到二者的訓練時間如表3。

表3 隨機森林參數(shù)優(yōu)化算法的訓練時間對比 s

對于dna數(shù)據(jù)集和msplice數(shù)據(jù)集，由于樣本多，維數(shù)高，使用網(wǎng)格搜索算法對隨機森林參數(shù)進行參數(shù)優(yōu)化時，超出了計算機的運行內(nèi)存，并未完成訓練，而本文提出的優(yōu)化算法完成了訓練。由表3可以看出，本文提出的基于改進的網(wǎng)格搜索的隨機森林參數(shù)優(yōu)化算法比基于網(wǎng)格搜索的優(yōu)化算法節(jié)省了大量時間，并且隨著維數(shù)的增加，節(jié)省的時間越多。

5 結(jié)束語

本文提出了一種基于改進的網(wǎng)格搜索的隨機森林參數(shù)優(yōu)化算法，該方法能夠在一定程度上提高隨機森林算法的分類性能，同時也比基于網(wǎng)格搜索算法的優(yōu)化算法節(jié)約了大量時間。但是，在粗搜索的最優(yōu)點附近繼續(xù)進行網(wǎng)格搜索可能會陷入局部最優(yōu)，從而不能尋找到最優(yōu)參數(shù)。

：

[1]Breiman L.Random forests[J].Machine Learning，2001，45（1）：5-32.

[2]Kulkarni V Y，Pradeep K S.Efficient learning of random forest classifier using disjoint partitioning approach[C]//Proceeding of the Word Congress on Engineering 2013.London：IAENG，2013：1-5.

[3]Kulkarni V Y，Pradeep K S.Random forest classifiers：a survey and future research directions[J].International Journal of Advanced Computing，2011，36（1）：1144-1153.

[4]Oshiro T M，Perez P S，Baranauskas J A.How many trees in a random forest[C]//Lecture Notes in Computer Science：International Workshop on Machine Learning and Data Mining in Pattern Recognition，2012，7376：154-168.

[5]Bernard S，Heutte L，Adam S.Towards a better understanding of random forests through the study of strength and correlation[C]//Lecture Notes in Computer Science：International Conference on Intelligent Computing.Berlin，Heidelberg：Springer-Verlag，2009，5755：536-545.

[6]馬景義，吳喜之，謝邦昌.擬自適應分類隨機森林算法[J].數(shù)理統(tǒng)計與管理，2010，29（5）：805-811.

[7]劉迎春，陳梅玲.流式大數(shù)據(jù)下隨機森林方法及其應用[J].西北工業(yè)大學學報，2015，33（6）：1055-1061.

[8]王全才.隨機森林特征選擇[D].大連：大連理工大學，2011.

[9]莊進發(fā)，羅鍵，彭彥卿，等.基于改進隨機森林的故障診斷方法研究[J].計算機集成制造系統(tǒng)，2009，15（4）：777-785.

[10]Genuer R，Poggi J M，Tuleau-Malot C.Variable selection using random forests[J].Pattern Recognition Letters，2010，31（14）：2225-2236.

[11]Panov P，Deroski D.Combining bagging and random subspaces to create better ensembles[C]//Lecture Notes in Computer Science：Proceedings of the 7th International Conference on Intelligent Data Analysis.Berlin，Heidelberg：Springer-Verlag，2007，4723：118-129.

[12]Bernard S，Heutte L，Adam S.Influence of hyperparameters on random forest accuracy[C]//Proceedings of the 8th International Workshop on Multiple Classifier System.Berlin，Heidelberg：Springer-Verlag，2009：171-180.

[13]李貞貴.隨機森林改進的若干研究[D].福建廈門：廈門大學，2014.

[14]謝劍斌.視覺機器學習[M].北京：清華大學出版社，2015：55-58.

[15]Breiman L.Stacked regressions[J].Machine Learning，1996，24（1）：49-64.

[16]Adnan M N，Islam M Z.Optimizing the number of trees in a decision forest to discover a subforest with high ensemble accuracy using a genetic algorithm[J].Knowledge-Based Systems，2016，110：86-97.