基于改進隨機搜索算法的隨機森林調(diào)參優(yōu)化

◆劉紫亮 居翔 張永芳 黃逸翠

基于改進隨機搜索算法的隨機森林調(diào)參優(yōu)化

◆劉紫亮 居翔 張永芳 黃逸翠

（南昌工程學院 江西 330096）

隨機搜索法是對無約束力問題尋找最優(yōu)解的一種算法。隨機森林是一種集成算法，為了提高隨機森林分類的準確率，需要對參數(shù)進行調(diào)參。隨機森林可以通過網(wǎng)格搜索算法或?qū)W習曲線算法選取到合適的參數(shù)，但是訓練時間過長，消耗資源過大。本文通過對隨機搜索算法改進，利用改進的隨機搜索算法優(yōu)化隨機森林調(diào)參。經(jīng)過實驗驗證，改進的算法選取到的參數(shù)保證了隨機森林分類準確率的同時，相較于通過學習曲線算法縮短了約百分之六十的調(diào)參時間。

隨機搜索法；隨機森林；參數(shù)優(yōu)化；學習曲線

1 引言

集成學習（Emsemble Learning）是當前被廣泛使用的一種機器學習算法，再機器學習領域都可以找到其身影。集成算法是在數(shù)據(jù)集上建立多個訓練模型，構建多個相互獨立或者相關的基評估器（Base Estimator）。集成算法會把所有基評估器的分類或回歸結果進行整合運算，以提高分類或回歸結果的準確性[1]。隨機森林（Random Forest）就是集成學習算法的一種，隨機森林算法[2]是由Leo Breiman在2001年提出，結合了袋裝法（Bagging）和隨機子空間理論，使得決策樹過擬合的問題在隨機森林上得到解決。文獻[3]表明了隨機森林算法在處理高緯度數(shù)據(jù)或是數(shù)據(jù)特征缺失的情況下依舊能維持較高的分類準確率。

隨機森林的基評估器的數(shù)量代表決策樹（DecisionTree）的數(shù)量。決策樹可以是分類樹或者回歸樹，對應的分別為隨機森林分類器和隨機森林回歸器[4]。Paul At等提出一種改進的隨機森林分類器，提出的方法能迭代地刪除一些對隨機森林不重要的特征，減少了特征參數(shù)的數(shù)量[5]。Yang等驗證了一種基于邊緣優(yōu)化的剪枝算法，減小了調(diào)參的復雜性并提高了隨機森林的性能[6]。想要提高隨機森林的分類準確率，除了特征的選取，還需要對參數(shù)進行優(yōu)化。劉凱提出了自適應特征選擇參數(shù)優(yōu)化算法SARFFS，該算法綜合了粒子群算法和隨機森林算法，提高了參數(shù)選擇過程的效率[7]。溫博文等通過改進網(wǎng)格搜索法，對隨機森林的候選分類特征和決策樹的數(shù)量參數(shù)進行優(yōu)化，降低了泛化誤差[8]。具體調(diào)參方面的研究還甚少，究其原因就是每個數(shù)據(jù)集所需要的參數(shù)有所不同。僅憑借經(jīng)驗進行調(diào)參，往往得不到最優(yōu)的分類結果。若是以犧牲計算機的性能為代價，暴力地通過學習曲線法或者網(wǎng)格搜索法進行調(diào)參，雖然能夠遍歷所有參數(shù)，分析每個參數(shù)對隨機森林的影響，但代價就是訓練時間過長，消耗資源過大。

2 決策樹與隨機森林算法原理

2.1 決策樹算法

一片森林是由多棵樹構成，隨機森林的樹稱之為決策樹，一棵棵不同的決策樹就形成了隨機森林。式（1）中S為決策樹的數(shù)量。

決策樹算法的模型原理簡單，在解決分類和回歸問題上有很好的表現(xiàn)。決策樹算法的原理是在一組有不同特征和分類標簽的數(shù)據(jù)中，對特征進行分類判斷訓練，訓練結束后形成一棵類似樹的分類模型。構建決策樹模型最重要的是找到最佳的分支節(jié)點和最佳分支方法，衡量“最佳”的指標叫做不純度。分類樹的不純度選用信息熵或者基尼系數(shù)進行運算，分類決策樹每次選擇分支節(jié)點時，決策樹會對剩余所有特征進行不純度的計算，決策樹會選擇不純度最低的特征進行分支，分支越多，決策樹模型越復雜，樹整體不純度也越低。這種模型構建方法會導致決策樹易擬合，訓練集表現(xiàn)良好，測試集卻不盡人意。

2.2 隨機森林算法

隨機森林算法引入了兩個隨機量應對決策樹易過擬合的問題，分別是有放回的隨機抽取樣本數(shù)據(jù)和從特征中隨機選擇候選分類屬性。隨機森林的構建過程如圖1所示。

圖1 隨機森林構建過程

RF在構建每一棵決策樹的過程中，訓練集是通過在大小為N的數(shù)據(jù)集中有放回的抽取N個訓練樣本，一個樣本被抽取的概率為：

用泛化誤差衡量隨機森林的準確率。當泛化誤差達到最低點時，分類的準確率最高。泛化誤差受模型復雜度的影響，參數(shù)影響模型的復雜度，模型復雜度越高，泛化誤差隨之升高。相反，模型復雜度比最佳復雜度還低時，泛化程度也隨之升高。泛化誤差受到方差（var）與偏差（bias）和噪聲的影響：

偏差反映的是預測值和真實值的差異，隨機森林的偏差是所有決策樹偏差的均值，模型越精確，偏差越低。方差反映的是每次輸出結果與模型預測值的平均水平的誤差，模型的穩(wěn)定性與方差值成反比。方差與偏差不可能同時最低，調(diào)參的目的就是讓方差和偏差相對最低，得到最低的泛化誤差。

3 基于改進隨機搜索算法優(yōu)化隨機森林調(diào)參

隨機搜索法是一維搜索法，先確定一個大致的范圍，然后隨機對這個范圍內(nèi)的點進行比較，設定一個迭代次數(shù)的上限，如果在迭代次數(shù)的范圍內(nèi)找到最優(yōu)值，則終止迭代，否則加大迭代次數(shù)，重新開始。隨機搜索法的算法如下：

程序結束后可以通過觀察最優(yōu)解的穩(wěn)定性判斷迭代次數(shù)是否足夠，穩(wěn)定性不足，可以加大迭代上限。隨機搜索法得到的最優(yōu)解是全局最優(yōu)解而非局部最優(yōu)解，對低維的數(shù)據(jù)集搜索快速且效率高。

隨機森林模型分類準確率取決于泛化誤差的大小，而為了達到泛化誤差的方差與偏差的平衡，讓模型的效果達到最優(yōu)，我們需要進行超參數(shù)的優(yōu)化，也就是進行調(diào)參，隨機森林可調(diào)節(jié)參數(shù)和參數(shù)重要性如表1所示。

表1 隨機森林參數(shù)

參數(shù)對模型的影響影響等級 n_estimators基分類器數(shù)量不影響單棵決策樹的復雜度，數(shù)量越大模型越穩(wěn)定Level-1 max_depth最大深度越小，模型越簡單Leval-2 min_samples_leaf越小模型越復雜Leval-3 min_samples_split越小模型越復雜Leval-3 max_features數(shù)量為總特征數(shù)的平方，降低時模型復雜度降低Leval-4 criterion選用gini系數(shù)Leval-5

為了降低調(diào)參的時間，提高訓練的效率，本文提出了在學習曲線的基礎上，利用改進的隨機搜索法進行隨機森林的調(diào)參。具體步驟如下（見圖2）：

（1）確定選取參數(shù)的上限與學習曲線的粗步長，在范圍內(nèi)進行步長L搜索，利用交叉驗證的方法，得到每個點的分類準確率的均值，選取最優(yōu)的分類準確率的粗最優(yōu)點。

（2）在選取粗最優(yōu)點后利用隨機搜索法在粗最優(yōu)點附近進行隨機搜索，隨機搜索的范圍為。

（3）確定好迭代次數(shù)，對每一次迭代取到的隨機點進行交叉驗證，記錄選取的參數(shù)和對應的分類準確率。程序結束后輸出最優(yōu)的參數(shù)和最優(yōu)的分類準確率。判斷分類準確率的穩(wěn)定性，穩(wěn)定性不足增大迭代次數(shù)，重新進行搜索。

圖2 基于改進隨機搜索算法優(yōu)化隨機森林調(diào)參流程圖

通過學習曲線或者網(wǎng)格搜索的“暴力”搜索法，雖然能夠探索到參數(shù)的邊緣，但是代價就是訓練模型的時間非常長，極大地浪費資源，通過改進的隨機搜索改進的隨機森林調(diào)參法能夠避免對每個參數(shù)進行校驗，節(jié)省資源的同時縮短調(diào)參時間。

4 實驗

4.1 數(shù)據(jù)集和實驗環(huán)境

本文數(shù)據(jù)集采用的是sklearn數(shù)據(jù)庫中的6個數(shù)據(jù)集，開發(fā)環(huán)境為Jupyter Lab，使用的庫和模塊為Pandas、Matplotlib、Graphvi、SciP與Python。表2為數(shù)據(jù)集的描述。

表2 sklearn數(shù)據(jù)集

數(shù)據(jù)集樣本數(shù)特征維數(shù)類別數(shù) Wine124133 breast_cancer569302 Iris15043 Pima768822 Glass178133 Letter31752403

4.2 實驗過程

本文以breast_cancer數(shù)據(jù)集為例基于改進隨機搜索算法優(yōu)化隨機森林調(diào)參。breast_cancer是一個二分類數(shù)據(jù)集，兩個類別分別是“良性”和“惡性”，具有30個特征維度。選用隨機森林的基分類器（n_estimators）參數(shù)進行調(diào)參優(yōu)化，設定基分類器上限為300，粗步長為30，交叉驗證cv=10。

圖3 粗步長搜索圖

由圖3可知，當基分類器的數(shù)量71時，隨機森林的分類準確率最高，為0.963126?？梢钥闯鲭S機森林的準確率并不是隨著基分類器的增大而一直增大，這是由于基分類器的數(shù)量越大，模型的復雜度會增加，方差增大使得總泛化誤差也隨之變大。由于開始選取的粗步長為30，接下來需要在（41，101）范圍內(nèi)，利用隨機搜索法進行隨機搜索，設定迭代次數(shù)上限為20，進行隨機搜索。

圖4 改進隨機搜索法與學習曲線對比圖

圖4中折線與點狀圖分別為學習曲線與改進的隨機搜索法搜索參數(shù)的分類準確率。由點狀圖可知，當基分類器參數(shù)取到75時，隨機森林分類器的準確率最高，為0.9648809。由于參數(shù)的分類準確率趨于穩(wěn)定，可以認定該點為最優(yōu)點。由圖4可知，基于改進的隨機搜索法搜索到的參數(shù)最高的分類準確率與學習曲線取到的參數(shù)最高分類準確率相同，但兩者在訓練的時間上卻相差很大，分別為20s與98s。為了驗證本文提出的方法具有普遍性，對表2其余數(shù)據(jù)集也進行上述步驟，得到實驗結果如表3所示。

表3 不同數(shù)據(jù)集實驗結果比較

數(shù)據(jù)集學習曲線隨機森林準確率學習曲線算法時間（s）隨機搜索法隨機森林準確率隨機搜索法優(yōu)化后時間（s） wine0.955360.95411 iris0.943480.94313 pima0.9381120.93632 glass0.946530.94618 Letter0.8985780.904120

通過表3可以看出，基于改進隨機搜索法的隨機森林調(diào)參相對于通過學習曲線調(diào)參，選取的參數(shù)保證了隨機森林準確率的同時，縮短了約百分之六十的調(diào)參時間，數(shù)據(jù)集越大，節(jié)省時間的效果也越明顯。在letter數(shù)據(jù)集上，由于樣本數(shù)量的龐大，計算機未能通過學習曲線遍歷所有的參數(shù)，分類準確率低于本文提出的方法。

5 結束語

本文提出的基于改進隨機搜索法的隨機森林調(diào)參優(yōu)化，保證了搜索到的參數(shù)能提高隨機森林分類的準確率，相較于學習曲線算法極大縮短了搜索合適參數(shù)的時間。但是本文參數(shù)選擇有一定的隨機性，在進行步長搜索時，最優(yōu)的參數(shù)可能沒有被搜索到，陷入了局部最優(yōu)。

[1]于玲，吳鐵軍. 集成學習：Boosting算法綜述[J]. 模式識別與人工智能，2004（01）：52-59.

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

[3]方匡南，吳見彬，朱建平，等. 隨機森林方法研究綜述[J]. 統(tǒng)計與信息論壇，2011，26（003）：32-38.

[4]Bonissone P，Cadenas J M，Garrido M C，et al. A fuzzy random forest[J]. International Journal of Approximate Reasoning， 2010.

[5]Paul A，Mukherjee D P，Das P，et al. Improved Random Forest for Classification[J]. IEEE Transactions on Image Processing，2018：4012-4024.

[6]Yang，WH，Luo，et al. Margin optimization based pruning for random forest[J]. NEUROCOMPUTING，2012（94）：54-63.

[7]劉凱. 隨機森林自適應特征選擇和參數(shù)優(yōu)化算法研究[D].長春工業(yè)大學，2018.

[8]溫博文，董文瀚，解武杰，等. 基于改進網(wǎng)格搜索算法的隨機森林參數(shù)優(yōu)化[J]. 計算機工程與應用，2018.

[9]羅預欣，張兵，薛運強.基于變量分析和粒子群優(yōu)化加權隨機森林的交通事件檢測方法[J].科學技術與工程，2021，21（14）.

[10]余韋，余鳳麗，吉晶，等.一種基于改進邏輯回歸算法實現(xiàn)模型在線調(diào)參方法[J].通信技術，2020，53（08）：1965-1969.

[11]陳晉音，熊暉，鄭海斌.基于粒子群算法的支持向量機的參數(shù)優(yōu)化[J].計算機科學，2018，45（06）：197-203.

[12]Cai J，Xu K，Zhu Y，et al. Prediction and analysis of net ecosystem carbon exchange based on gradient boosting regression and random forest[J]. Applied Energy，2020，262：114566.