基于改進(jìn)網(wǎng)格搜索算法的隨機(jī)森林參數(shù)優(yōu)化

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

空軍工程大學(xué) 航空航天工程學(xué)院，西安 710038

1 引言

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

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

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

2 隨機(jī)森林原理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

上述搜索過(guò)程可用圖2所示的流程圖進(jìn)行表示。

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

4 仿真驗(yàn)證

本文選取了UCI數(shù)據(jù)庫(kù)中的11個(gè)數(shù)據(jù)集，表1對(duì)數(shù)據(jù)集的樣本數(shù)、特征維數(shù)、類(lèi)別數(shù)做出了簡(jiǎn)要描述。

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

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

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

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

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

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

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

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

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

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

表3 隨機(jī)森林參數(shù)優(yōu)化算法的訓(xùn)練時(shí)間對(duì)比 s

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

5 結(jié)束語(yǔ)

本文提出了一種基于改進(jìn)的網(wǎng)格搜索的隨機(jī)森林參數(shù)優(yōu)化算法，該方法能夠在一定程度上提高隨機(jī)森林算法的分類(lèi)性能，同時(shí)也比基于網(wǎng)格搜索算法的優(yōu)化算法節(jié)約了大量時(shí)間。但是，在粗搜索的最優(yōu)點(diǎn)附近繼續(xù)進(jìn)行網(wǎng)格搜索可能會(huì)陷入局部最優(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]馬景義，吳喜之，謝邦昌.擬自適應(yīng)分類(lèi)隨機(jī)森林算法[J].數(shù)理統(tǒng)計(jì)與管理，2010，29（5）：805-811.

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

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

[9]莊進(jìn)發(fā)，羅鍵，彭彥卿，等.基于改進(jìn)隨機(jī)森林的故障診斷方法研究[J].計(jì)算機(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]李貞貴.隨機(jī)森林改進(jìn)的若干研究[D].福建廈門(mén)：廈門(mén)大學(xué)，2014.

[14]謝劍斌.視覺(jué)機(jī)器學(xué)習(xí)[M].北京：清華大學(xué)出版社，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.