基于自適應(yīng)遺傳算法的隨機(jī)森林模型參數(shù)優(yōu)化方法

蔡 明，孫 杰，楊維發(fā)，鮑 清，李培德

（1 湖北省氣象信息與技術(shù)保障中心，武漢 430074；2 中國氣象局武漢暴雨研究所暴雨監(jiān)測預(yù)警湖北重點(diǎn)實(shí)驗(yàn)室，武漢 430074）

0 引言

隨機(jī)森林回歸（Random Forest Regression）算法作為一種靈活且易于使用的機(jī)器學(xué)習(xí)算法［1-2］，其理論和方法已被作為一種替代一般線性模型（線性回歸、方差分析等）和廣義線性模型（邏輯斯蒂回歸、泊松回歸等）的方法，廣泛應(yīng)用于工程應(yīng)用和科學(xué)領(lǐng)域中復(fù)雜問題的解決上。國內(nèi)外學(xué)者對(duì)隨機(jī)森林在回歸和分類問題中的應(yīng)用進(jìn)行了全面研究。在國外，Kulkarni 等人［3-4］為了提高分類正確率，將決策樹維度分為2 部分。Oshiro 等人［5］證明了在隨機(jī)森林性能達(dá)到最優(yōu)時(shí)決策樹數(shù)目存在臨界值。Bernard 等人［6］研究了隨機(jī)森林強(qiáng)度與相關(guān)性的關(guān)系。在國內(nèi)，袁遠(yuǎn)等人［7］利用隨機(jī)森林算法對(duì)非線性數(shù)據(jù)特征的學(xué)習(xí)能力，優(yōu)化ARIMA 模型預(yù)測殘差，最終達(dá)到提高回歸預(yù)測精度的目的。馬景義等人［8］綜合了Adaboost 算法和隨機(jī)森林算法的優(yōu)勢，提出了擬自適應(yīng)分類隨機(jī)森林算法。馮開平等人［9］將加權(quán)K 最近鄰法（KNN）與隨機(jī)森林算法結(jié)合應(yīng)用于表情識(shí)別，簡化了計(jì)算復(fù)雜度的同時(shí)取得了不錯(cuò)的識(shí)別率。

自適應(yīng)遺傳算法是將生物進(jìn)化論的自然選擇和遺傳機(jī)理應(yīng)用于粒子濾波算法以克服其粒子多樣性退化不足的一種隨機(jī)化搜索方法［10-11］。其主要特點(diǎn)是按照優(yōu)勢種群遺傳的原則將粒子適應(yīng)度變化情況作為遺傳操作中交叉和變異概率變化的依據(jù)，通過對(duì)粒子的選擇、交叉和變異操作模擬生物界優(yōu)勝劣汰、適者生存的過程，由于其直接對(duì)結(jié)構(gòu)化的對(duì)象進(jìn)行操作，故具有很好的全局尋優(yōu)能力。但是由于遺傳操作中的交叉和變異概率是預(yù)先設(shè)定的，參數(shù)選取不當(dāng)容易使算法陷入局部最優(yōu)［12-15］。

基于以上研究論述，本文提出一種基于自適應(yīng)遺傳算法的隨機(jī)森林回歸模型參數(shù)優(yōu)化方法，使用Boston house price 數(shù)據(jù)集對(duì)經(jīng)過該方法優(yōu)化后隨機(jī)森林模型的回歸預(yù)測效果進(jìn)行驗(yàn)證。

1 相關(guān)算法介紹

1.1 隨機(jī)森林回歸算法

隨機(jī)森林回歸（Random Forest Regression，RFR）算法是一種基于決策樹（Decision Tree）的引入隨機(jī)特征選擇的Bagging 類集成算法，目前被廣泛應(yīng)用于各類回歸問題。本文使用Boston house price 數(shù)據(jù)集對(duì)隨機(jī)森林回歸模型進(jìn)行訓(xùn)練和預(yù)測。隨機(jī)森林回歸模型的建立過程如下：

（1）從原始訓(xùn)練集中使用bootstrap 方法隨機(jī)有放回采樣取出m個(gè)樣本，共進(jìn)行n_tree次采樣。生成n_tree個(gè)訓(xùn)練集。

（2）對(duì)n_tree個(gè)訓(xùn)練集，分別獨(dú)立訓(xùn)練n_tree個(gè)決策樹模型。

（3）對(duì)于單個(gè)決策樹模型，假設(shè)訓(xùn)練樣本特征個(gè)數(shù)為n，選擇最好的特征進(jìn)行切分。

（4）每棵樹都按照步驟（3）來切分下去，直到該節(jié)點(diǎn)的所有訓(xùn)練樣例都屬于同一類。在決策樹的切分過程中不需要剪枝。

（5）將生成的多棵決策樹組成隨機(jī)森林，模型最終預(yù)測結(jié)果為隨機(jī)森林中多棵決策樹預(yù)測結(jié)果的均值。

決策樹的生長過程就是使用滿足劃分準(zhǔn)則的特征不斷將數(shù)據(jù)集劃分為純度更高、不確定性更小的子集的過程。

在步驟（3）中，當(dāng)訓(xùn)練決策樹模型時(shí)需要考慮怎樣選擇切分特征、切分點(diǎn)以及怎樣衡量切分特征、切分點(diǎn)的好壞。針對(duì)切分特征和切分點(diǎn)的選擇，本文采用窮舉法，即遍歷每個(gè)特征和每個(gè)特征的所有取值，再從中找出最好的切分變量和切分點(diǎn)；針對(duì)于切分特征和切分點(diǎn)的好壞，一般以切分后節(jié)點(diǎn)的不純度來衡量，即各個(gè)子節(jié)點(diǎn)不純度的加權(quán)和G（xi，vij），其計(jì)算公式如下：

其中，xi為節(jié)點(diǎn)的某一個(gè)切分特征；vij為切分特征的一個(gè)切分值；nleft、nright、Ns分別為切分后左子節(jié)點(diǎn)訓(xùn)練樣本個(gè)數(shù)、右子節(jié)點(diǎn)訓(xùn)練樣本個(gè)數(shù)以及當(dāng)前節(jié)點(diǎn)所有訓(xùn)練樣本個(gè)數(shù)；Xleft、Xright分為左、右子節(jié)點(diǎn)的訓(xùn)練樣本集合；H（X）為節(jié)點(diǎn)的不純度函數(shù)（impurity function），回歸模型一般采用均方誤差（Mean Square Error，MSE）或平均絕對(duì)誤差（Mean Absolute Error，MAE）作為不純度函數(shù)，本文則選用了MSE作為模型的不純度函數(shù)，其數(shù)學(xué)定義公式見式（2）：

其中，Xs為當(dāng)前節(jié)點(diǎn)訓(xùn)練樣本集合；ns為當(dāng)前節(jié)點(diǎn)訓(xùn)練樣本數(shù)目；為當(dāng)前節(jié)點(diǎn)樣本目標(biāo)特征的均值。

將式（2）帶入式（1）后，對(duì)于任意切分點(diǎn)可以得到：

1.2 自適應(yīng)遺傳算法

以往的遺傳算法常使用恒定不變的概率對(duì)粒子進(jìn)行交叉和變異等遺傳操作，這樣會(huì)導(dǎo)致粒子群中適應(yīng)度較大的優(yōu)勢粒子容易被丟棄掉，同時(shí)新的優(yōu)勢粒子也不容易產(chǎn)生，致使算法一旦陷入局部最優(yōu)，就很難跳出。

針對(duì)這一問題，提出一種基于生物遺傳進(jìn)化思想的自適應(yīng)遺傳算法（AGA）。算法中，高適應(yīng)度的優(yōu)勢個(gè)體以較高概率進(jìn)行交叉操作，這樣可以增大優(yōu)勢基因遺傳到子代的可能性，更符合遺傳進(jìn)化規(guī)律；低適應(yīng)度的個(gè)體以較高的概率進(jìn)行變異操作，這樣就更容易通過變異操作產(chǎn)生新的優(yōu)勢個(gè)體，避免算法陷入局部最優(yōu)。通過自適應(yīng)地調(diào)節(jié)遺傳操作中的交叉、變異概率，從而避免遺傳算法中早熟現(xiàn)象的出現(xiàn)。其中，遺傳操作的交叉概率Pc和變異概率Pm可以分別表示為：

1.3 基于自適應(yīng)遺傳算法的隨機(jī)森林回歸參數(shù)優(yōu)化

以往的隨機(jī)森林回歸算法的參數(shù)優(yōu)化多通過繪制學(xué)習(xí)曲線或網(wǎng)格搜索交叉驗(yàn)證的方法實(shí)現(xiàn)，實(shí)施過程中恒定不變的搜索步長使得最優(yōu)參數(shù)的獲取很難在速度和效果上同時(shí)達(dá)到最優(yōu)?；诖?，提出自適應(yīng)遺傳算法輔助下的隨機(jī)森林回歸模型參數(shù)優(yōu)化方法，利用遺傳算法優(yōu)異的全局尋優(yōu)能力，結(jié)合自適應(yīng)方法動(dòng)態(tài)調(diào)整的遺傳操作概率，達(dá)到快速取得全局最優(yōu)解的目的。

隨機(jī)森林回歸是基于bagging 框架的決策樹模型，因此隨機(jī)森林回歸模型的參數(shù)調(diào)整包括2 部分：隨機(jī)森林框架的參數(shù)調(diào)優(yōu)和決策樹的參數(shù)調(diào)優(yōu)。使用自適應(yīng)遺傳算法進(jìn)行隨機(jī)森林回歸模型參數(shù)優(yōu)化的流程如圖1 所示。

圖1 基于自適應(yīng)遺傳算法的隨機(jī)森林回歸模型流程圖Fig. 1 Flow chart of Random Forest regression model based on adaptive genetic algorithm

2 實(shí)驗(yàn)準(zhǔn)備

2.1 數(shù)據(jù)集準(zhǔn)備

為了驗(yàn)證經(jīng)自適應(yīng)遺傳算法優(yōu)化后的隨機(jī)森林回歸模型的有效性，使用Kaggle Boston house price數(shù)據(jù)集進(jìn)行仿真驗(yàn)證。數(shù)據(jù)集中的每一行數(shù)據(jù)都是對(duì)波士頓周邊或城鎮(zhèn)房價(jià)的情況描述，數(shù)據(jù)集共有14 個(gè)特征，分別為：城鎮(zhèn)人均犯罪率（CRIM）、住宅用地所占比例（ZN）、城鎮(zhèn)中非住宅用地所占比例（INDUS）、虛擬變量（CHAS），用于回歸分析；環(huán)保指數(shù)（NOX）、每棟住宅的房間數(shù)（RM）、1940 年以前建成的自住單位的比例（AGE）、距離5 個(gè)波士頓就業(yè)中心的加權(quán)距離（DIS）、距離高速公路的便利指數(shù)（RAD）、每一萬美元的不動(dòng)產(chǎn)稅率（TAX）、城鎮(zhèn)中的教師／學(xué)生比例（PTRATIO）、城鎮(zhèn)中的黑人比例（B）、地區(qū)中有多少房東屬于低收入人群（LSTAT）、自住房屋房價(jià)（PRICE）。其中，PRICE為目標(biāo)變量，其他13 個(gè)特征為模型的輸入自變量特征。各自變量特征的重要性見表1。由表1 可以發(fā)現(xiàn)，不論是RFR 模型、還是自適應(yīng)遺傳算法優(yōu)化后的AGA -RFR 算法模型，各自變量的重要性程度都是相近的，且RM和LASTAT都是對(duì)模型最重要的變量。

表1 模型特征變量重要性Tab.1 Importance of model characteristic variables

模型初始特征集中各項(xiàng)特征之間的相關(guān)性熱力圖如圖2 所示。圖2 中，部分特征間呈現(xiàn)負(fù)相關(guān)性，部分呈現(xiàn)正相關(guān)性。將Kaggle Boston house price 數(shù)據(jù)集按照7 ∶3 的比列劃分為訓(xùn)練集和測試集。

圖2 模型特征相關(guān)性熱力圖Fig. 2 Model characteristic correlation thermodynamic diagram

2.2 評(píng)價(jià)指標(biāo)

為了對(duì)比自適應(yīng)遺傳算法參數(shù)優(yōu)化方法的應(yīng)用對(duì)隨機(jī)森林回歸模型預(yù)測精度的影響，需要對(duì)隨機(jī)森林回歸模型的預(yù)測精度進(jìn)行評(píng)價(jià)。本文使用均方根誤差、決定系數(shù)和平均絕對(duì)誤差這3 個(gè)指標(biāo)對(duì)模型的預(yù)測精度進(jìn)行評(píng)價(jià)。對(duì)此擬給出研究分述如下。

（1）均方根誤差（Root Mean Squared Error，RMSE），也叫回歸系統(tǒng)的擬合標(biāo)準(zhǔn)差。由于均方根誤差對(duì)一組測量值中的特大或特小誤差反映非常敏感，所以，均方根誤差能夠很好地反映出測量的精密度。具體數(shù)學(xué)公式可寫為：

（2）決定系數(shù)（Coefficient of Determination，R2）。表示對(duì)模型進(jìn)行線性回歸后，評(píng)價(jià)回歸模型系數(shù)的擬合優(yōu)度。R2反映了模型因變量的全部變異能通過回歸模型被自變量解釋的比例。R2越大，線性回歸模型解釋的變異越大。具體數(shù)學(xué)公式可寫為：

R2為1 時(shí)，表明模型預(yù)測值和真實(shí)值觀測值沒有任何誤差，表示回歸分析中自變量對(duì)因變量的解釋越好；R2為0 時(shí)，模型中樣本的每項(xiàng)預(yù)測值都等于均值；R2接近于0 時(shí)，表明模型預(yù)測能力差，預(yù)測效果接近于“使用觀測值的平均值作為模型預(yù)測值”。這就表示可能用了錯(cuò)誤模型，或者模型假設(shè)不合理。

（3）平均絕對(duì)誤差（Mean Absolute Error，MAE）計(jì)算公式如下：

其中，MAE的取值范圍為 [0，＋∞），當(dāng)預(yù)測值與真實(shí)值完全吻合時(shí)等于0，即完美模型；誤差越大，該值越大。

3 結(jié)果與分析

研究使用Kaggle Boston house price 訓(xùn)練數(shù)據(jù)集對(duì)經(jīng)過自適應(yīng)遺傳算法優(yōu)化得到的隨機(jī)森林回歸模型進(jìn)行訓(xùn)練，訓(xùn)練后的模型對(duì)測試集進(jìn)行預(yù)測。對(duì)比未經(jīng)過參數(shù)優(yōu)化的RFR 模型與經(jīng)過參數(shù)優(yōu)化的AGA-RFR模型的預(yù)測結(jié)果，預(yù)測效果對(duì)比見表2。

表2 模型預(yù)測精度對(duì)比Tab.2 Comparison of prediction accuracy of models

觀察表2 可以發(fā)現(xiàn)，經(jīng)過自適應(yīng)遺傳算法優(yōu)化參數(shù)后的AGA-RFR 模型的回歸預(yù)測結(jié)果中，RMSE為4.111，優(yōu)于RFR 的4.174；AGA-RFR 的R2為0.868，同樣優(yōu)于RFR 的0.833；對(duì)比2 種模型的MAE也是同樣的情況。綜上可知，經(jīng)過參數(shù)優(yōu)化后的AGA-RFR 模型的MAE要優(yōu)于RFR 模型。這就說明通過使用自適應(yīng)遺傳算法對(duì)隨機(jī)森林回歸模型的參數(shù)進(jìn)行優(yōu)化，使得隨機(jī)森林回歸模型的預(yù)測效果得到了提高。

以Prices為橫坐標(biāo)，Predicted prices為縱坐標(biāo)，繪制出的模型預(yù)測價(jià)格與實(shí)際價(jià)格的對(duì)比結(jié)果圖如圖3 所示。

圖3 模型預(yù)測價(jià)格與實(shí)際價(jià)格對(duì)比圖Fig. 3 Comparison between model predicted prices and actual prices

由圖3 可知，相比于方形所代表的RFR 模型預(yù)測結(jié)果，圓形所代表的AGA-RFR 模型的預(yù)測結(jié)果總體上更接近于代表模型預(yù)測價(jià)格與實(shí)際價(jià)格相等的虛直線。由此說明，AGA-RFR 模型的預(yù)測結(jié)果比RFR 模型的預(yù)測結(jié)果更接近于真實(shí)價(jià)格。

模型預(yù)測值殘差與實(shí)際價(jià)格對(duì)比如圖4 所示。圖4 中，相比于方形所代表的RFR 模型預(yù)測結(jié)果，圓形所代表的AGA-RFR 模型的預(yù)測結(jié)果總體上更接近于代表預(yù)測殘差為0 的虛直線。這也說明，AGA-RFR 模型的預(yù)測結(jié)果比RFR 模型的預(yù)測結(jié)果具有更小的預(yù)測殘差。

圖4 模型預(yù)測值殘差與實(shí)際價(jià)格對(duì)比圖Fig. 4 Comparison between residual error of model predicted value and actual prices

4 結(jié)束語

本文提出一種用于隨機(jī)森林回歸模型參數(shù)優(yōu)化的方法，利用自適應(yīng)遺傳算法在求解全局最優(yōu)解的研究時(shí)不易陷入局部最優(yōu)的優(yōu)勢，通過對(duì)粒子的選擇、交叉和變異操作模擬生物界優(yōu)勝劣汰、適者生存的過程。通過使用Boston house price 數(shù)據(jù)集對(duì)經(jīng)過該方法優(yōu)化后隨機(jī)森林模型的回歸預(yù)測效果進(jìn)行驗(yàn)證，試驗(yàn)結(jié)果表明，經(jīng)過該方法參數(shù)優(yōu)化后的AGARFR 模型的回歸預(yù)測效果要優(yōu)于未經(jīng)過參數(shù)優(yōu)化的RFR 模型的預(yù)測效果。

本文提出的基于自適應(yīng)遺傳算法的隨機(jī)森林模型參數(shù)優(yōu)化方法可以作為隨機(jī)森林回歸模型參數(shù)優(yōu)化的一種有效手段。