基于改進網格搜索算法的隨機森林參數優化

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

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

1 引言

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

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

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

2 隨機森林原理

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

隨機森林的構建過程如圖1所示[14]。

圖1 隨機森林的構建過程

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

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

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

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

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

3 基于改進網格搜索的隨機森林參數優化

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

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

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

（2）對網格節點上的每一組參數構建隨機森林，并利用袋外數據估計分類誤差。

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

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

圖2 基于改進的網格搜索算法的隨機森林參數尋優流程圖

4 仿真驗證

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

表1 UCI數據集

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

圖3 隨機森林參數粗搜索結果圖

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

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

圖4 隨機森林參數大步長搜索結果圖

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

表2 基于UCI數據集的隨機森林參數尋優結果

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

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

表3 隨機森林參數優化算法的訓練時間對比 s

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

5 結束語

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

：

[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].數理統計與管理，2010，29（5）：805-811.

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

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

[9]莊進發，羅鍵，彭彥卿，等.基于改進隨機森林的故障診斷方法研究[J].計算機集成制造系統，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.