胡明祺，張森昶

（鄭州大學(xué)網(wǎng)絡(luò)空間安全學(xué)院，鄭州 450000）

0 引言

隨機森林（random forest）由加利福尼亞大學(xué)的Leo Breiman提出，后來經(jīng)過YL Pavlov的改善， 提高了隨機森林算法的基本性能，并在研究和工業(yè)等各領(lǐng)域得到廣泛應(yīng)用。傳統(tǒng)隨機森林算法的隨機性來自于兩個隨機化過程：一是從原始數(shù)據(jù)集中隨機生成若干訓(xùn)練集，二是用來分支的最優(yōu)特征屬性是從隨機生成的部分特征屬性中選擇的，最終其輸出結(jié)果為一個包含分類能力各不相同的決策樹的集合。由于傳統(tǒng)的隨機森林算法隨機程度高且對每棵決策樹的分類能力不做評估，因此極易出現(xiàn)同一集合中同時存在權(quán)重相同的、分類能力較強和較弱的決策樹分類器，使隨機森林的整體性能下降。這也導(dǎo)致傳統(tǒng)隨機森林算法準(zhǔn)確度不高，易出現(xiàn)過擬合現(xiàn)象。

目前，對隨機森林中的決策樹加權(quán)以區(qū)分不同決策樹的投票性能成為提高隨機森林算法分類精度的一個研究方向。本文提出了一種基于PSO 優(yōu)化的葉節(jié)點加權(quán)隨機森林算法，通過bagging 算法進(jìn)行抽樣和特征選擇，并在每棵樹的葉節(jié)點上進(jìn)行加權(quán)，從而賦予每個葉節(jié)點不同的投票權(quán)重，提高分類的精確度。此外，我們引入粒子群算法（PSO）對權(quán)重向量進(jìn)行優(yōu)化，使加權(quán)不再由人工設(shè)置，提高算法的科學(xué)性與合理性，在整體上改善了算法的性能。

1 相關(guān)工作

近年來，大量學(xué)者從各個方面對傳統(tǒng)隨機森林算法進(jìn)行了許多優(yōu)化。林楓等提出了用果蠅算法進(jìn)行優(yōu)化的隨機森林算法， 解決了傳統(tǒng)參數(shù)選擇方法存在主觀干擾性的問題， 該算法有利于較大數(shù)據(jù)集的提取，但無法作用于較小數(shù)據(jù)集且未對隨機森林算法的重要問題，即投票問題，進(jìn)行優(yōu)化。莊巧蕙對隨機森林算法的泛化能力進(jìn)行提升，使其能夠參與實際應(yīng)用，但是僅僅提高泛化能力會在某些情況下降低隨機森林算法的準(zhǔn)確性。楊彪使用基于誤判率比較的二次訓(xùn)練的方法對決策樹的葉結(jié)點進(jìn)行加權(quán)，提高了隨機森林算法的性能，但在權(quán)重優(yōu)化方面仍有提升的空間。

2 粒子群算法

自適應(yīng)優(yōu)化算法可以根據(jù)當(dāng)前數(shù)據(jù)的處理特征，自動調(diào)整模型參數(shù)或處理辦法，以達(dá)到增強模型分類性能的目的。粒子群算法是一種性能較好的自適應(yīng)優(yōu)化算法。本文采用粒子群算法對隨機森林進(jìn)行葉節(jié)點權(quán)重優(yōu)化，使權(quán)重向量更加科學(xué)合理。

粒子群優(yōu)化算法可以處理連續(xù)優(yōu)化問題和組合優(yōu)化問題。在傳統(tǒng)粒子群算法中，模型會初始化一群隨機解，將這些潛在的解稱作粒子，這些粒子通過跟蹤兩個極值來更新自己。

此時，每個粒子的優(yōu)劣性可以由目標(biāo)函數(shù)來得到，將第個粒子的“飛翔”速度記為

將第個粒子的個體極值記為

第個粒子的全局極值記為

更新每個粒子為

其中= 1,2,…,,= 1,2,…,；和為非負(fù)的常數(shù)；和是介于[ 0,1] 之間的隨機數(shù)。v∈[ -,]；是常數(shù)。以上操作迭代進(jìn)行直至滿足迭代終止條件。

3 加權(quán)的隨機森林算法

3.1 隨機森林算法

隨機森林是一個以若干決策樹為其基分類器的組合分類器，傳統(tǒng)的隨機森林算法主要由三步組成：①采用bootstrap抽樣的方法從原始數(shù)據(jù)集中隨機生成若干訓(xùn)練集。②用各訓(xùn)練集分別訓(xùn)練決策樹，并不進(jìn)行剪枝，其用來分支的最優(yōu)特征屬性是從隨機生成的部分特征屬性中選擇的。③各個決策樹分類器的集合構(gòu)成一片隨機森林，此隨機森林的模型輸出為：

其中為測試集，為類別數(shù)，為隨機森林模型的規(guī)模，f()表示第棵決策樹的分類結(jié)果，(?)是一個判斷函數(shù)，當(dāng)基分類器的輸出結(jié)果滿足條件時為1，不滿足時為0。

對于隨機森林中決策樹的生成算法，我們選擇CART決策樹算法，此算法遞歸地在每個內(nèi)部節(jié)點處進(jìn)行基于基尼指數(shù)的特征分割，最終生成一棵二叉樹。CART決策樹對特征值的選取及特征取值的數(shù)目有很好的適應(yīng)性，因此被廣泛使用。

3.2 基于PSO優(yōu)化的葉加權(quán)隨機森林算法

作為一種分類器的組合方法，隨機森林算法在訓(xùn)練數(shù)據(jù)集選取和特征值選取時的隨機化可以有效避免決策樹易于過擬合的缺點，增強模型的泛化能力。但實際上，正是由于決策樹生成算法的兩個隨機化過程，各個決策樹甚至同一決策樹的每個葉節(jié)點的分類精度都有較大的差異。在傳統(tǒng)隨機森林模型中，每棵決策樹的投票權(quán)重都是相等的，這就導(dǎo)致一些性能較差的決策樹或葉節(jié)點的投票會影響整個隨機森林分類器的最終分類結(jié)果。因此，本文提出基于PSO 優(yōu)化的葉加權(quán)隨機森林算法，對隨機森林中每棵決策樹的每片葉節(jié)點加以不同權(quán)值，并使用PSO 算法進(jìn)行自適應(yīng)優(yōu)化，進(jìn)而達(dá)到提高隨機森林分類器整體性能的目的。

此外，針對隨機森林分類器在某些噪聲較大的分類或回歸問題上會出現(xiàn)過擬合的問題，我們通過bagging 算法對特征集和訓(xùn)練集進(jìn)行特征選取，以此來訓(xùn)練分類器，并提升算法在特征選取方面的準(zhǔn)確性。在特征選取之后，我們?yōu)槊總€子葉隨機分配初始可信度，構(gòu)成可信度向量，并使用PSO 算法對可信度向量進(jìn)行優(yōu)化，直至其性能達(dá)到預(yù)先設(shè)置的完成閾值。最后，我們記錄葉節(jié)點可信度向量，并將其作用于測試中最終得到的葉節(jié)點，以此來對子葉加權(quán)，最終采取投票法得出隨機森林的結(jié)果。

算法步驟如下：

其中為測試集，為類別數(shù)，為隨機森林模型的規(guī)模，f()表示第棵決策樹的分類結(jié)果，(?)是一個判斷函數(shù)，當(dāng)基分類器的輸出結(jié)果滿足條件時為1，不滿足時為0。

4 實驗結(jié)果與分析

為了檢驗此算法的性能，我們使用標(biāo)準(zhǔn)UCI測試數(shù)據(jù)集對算法進(jìn)行測試。選擇的數(shù)據(jù)集詳細(xì)信息如表1所示。

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

為了測試算法的可靠性，我們在每一個數(shù)據(jù)集中加入30%的隨機噪聲，隨后用上述數(shù)據(jù)集對隨機森林算法和加權(quán)隨機森林算法分別進(jìn)行了十折交叉驗證，以達(dá)到對比效果。測試結(jié)果如表2所示。

表2 分類精度

可以看出，相較于原本的隨機森林算法，PSO 優(yōu)化的加權(quán)隨機森林算法在各數(shù)據(jù)集上的分類精度都有明顯的提升。通過對比可以發(fā)現(xiàn)，PSO 優(yōu)化的加權(quán)隨機森林算法對于大數(shù)據(jù)集的適應(yīng)性更好，性能提升度可達(dá)19.1%。

此外，為了測試PSO 優(yōu)化過程對本算法分類精度的影響，我們嘗試改變PSO 算法的種群數(shù)量和最深迭代次數(shù)兩個參數(shù)，并進(jìn)行了多次對比實驗，測試選用的數(shù)據(jù)集為Bank Marketing數(shù)據(jù)集。在Python 環(huán)境下測試的輸出結(jié)果如圖1所示。

圖1 Python環(huán)境下測試的輸出結(jié)果

其中，var 表示最深迭代次數(shù)iter=60+2×pop 的情況；cons 表示iter=150 的情況。從實驗結(jié)果可以看出，pop 和iter 對PSO 性能并無明顯影響，PSO 優(yōu)化的加權(quán)隨機森林算法有較好的適應(yīng)性和穩(wěn)定性。

5 結(jié)語

本文提出了一種基于PSO 優(yōu)化的葉加權(quán)隨機森林算法。這種算法針對決策樹生成算法的兩個隨機化過程，對隨機森林中每棵決策樹的每片葉節(jié)點加以不同的權(quán)值，使各個葉節(jié)點的投票權(quán)重與其分類精度達(dá)到平衡。利用PSO 算法全局搜索能力強、收斂速度快的優(yōu)勢，我們對葉節(jié)點權(quán)值進(jìn)行優(yōu)化，以此提高分類性能較強的葉節(jié)點的投票權(quán)重，降低分類性能較弱的葉節(jié)點的投票權(quán)重，有效避免決策樹易于過擬合的缺點，增強模型的泛化能力，進(jìn)而達(dá)到提高隨機森林分類器整體性能的效果。

理論分析和實驗結(jié)果表明，基于PSO 優(yōu)化的葉加權(quán)隨機森林算法是可行的。與傳統(tǒng)的隨機森林算法相比，該算法在分類精度及模型穩(wěn)定性上都有明顯提升，且對于大數(shù)據(jù)集的適應(yīng)性更好，性能可比傳統(tǒng)的隨機森林算法提升19.1%，有一定的研究和應(yīng)用價值。

目前，本文算法在提高模型適應(yīng)性方面還存在改進(jìn)的空間，在降低算法時間復(fù)雜度方面仍需作進(jìn)一步的研究。