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

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

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

1 引言

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

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

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

2 隨機(jī)森林原理

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

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

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

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

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

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

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

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

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

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

為了提高隨機(jī)森林算法的分類性能，需要同時考慮單棵決策樹的分類正確率和樹的多樣性，然而兩者之間也存在著一定關(guān)系。到目前為止仍沒有關(guān)于兩者關(guān)系對隨機(jī)森林性能影響的研究[16]。本文針對隨機(jī)森林算法中決策樹數(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ī)森林在構(gòu)建過程中的隨機(jī)性，分類誤差可能會在一定范圍內(nèi)波動，因此為減小不確定性對參數(shù)選擇產(chǎn)生的影響，本文在求分類誤差時選用多個隨機(jī)森林模型分類誤差的平均值。具體步驟如下：

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

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

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

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

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

4 仿真驗(yàn)證

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

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

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

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

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

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

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

為驗(yàn)證本文提出的方法對其他數(shù)據(jù)集也適用，本文對表1中剩余數(shù)據(jù)集重復(fù)上述步驟，進(jìn)行網(wǎng)格搜索，得到隨機(jī)森林相應(yīng)的決策樹數(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時隨機(jī)森林的泛化誤差，第5列為利用本文提出的方法進(jìn)行參數(shù)選擇后隨機(jī)森林的泛化誤差。由表2可以看出，基于改進(jìn)的網(wǎng)格搜索算法對隨機(jī)森林算法的參數(shù)進(jìn)行優(yōu)化，可以使隨機(jī)森林的分類效果得到一定程度的提高。

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

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

對于dna數(shù)據(jù)集和msplice數(shù)據(jù)集，由于樣本多，維數(shù)高，使用網(wǎng)格搜索算法對隨機(jī)森林參數(shù)進(jìn)行參數(shù)優(yōu)化時，超出了計算機(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ù)的增加，節(jié)省的時間越多。

5 結(jié)束語

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

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

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

[9]莊進(jìn)發(fā)，羅鍵，彭彥卿，等.基于改進(jìn)隨機(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].福建廈門：廈門大學(xué)，2014.

[14]謝劍斌.視覺機(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.