基于PSO優(yōu)化的葉節(jié)點(diǎn)加權(quán)隨機(jī)森林算法

胡明祺，張森昶

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

0 引言

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

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

1 相關(guān)工作

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

2 粒子群算法

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

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

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

將第個(gè)粒子的個(gè)體極值記為

第個(gè)粒子的全局極值記為

更新每個(gè)粒子為

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

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

3.1 隨機(jī)森林算法

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

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

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

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

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

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

算法步驟如下：

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

4 實(shí)驗(yàn)結(jié)果與分析

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

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

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

表2 分類精度

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

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

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

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

5 結(jié)語

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

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

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