胡明祺,張森昶
(鄭州大學(xué)網(wǎng)絡(luò)空間安全學(xué)院,鄭州 450000)
隨機(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ī)程度高且對每棵決策樹的分類能力不做評估,因此極易出現(xiàn)同一集合中同時(shí)存在權(quán)重相同的、分類能力較強(qiáng)和較弱的決策樹分類器,使隨機(jī)森林的整體性能下降。這也導(dǎo)致傳統(tǒng)隨機(jī)森林算法準(zhǔn)確度不高,易出現(xiàn)過擬合現(xiàn)象。
目前,對隨機(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)對權(quán)重向量進(jìn)行優(yōu)化,使加權(quán)不再由人工設(shè)置,提高算法的科學(xué)性與合理性,在整體上改善了算法的性能。
近年來,大量學(xué)者從各個(gè)方面對傳統(tǒng)隨機(jī)森林算法進(jìn)行了許多優(yōu)化。林楓等提出了用果蠅算法進(jìn)行優(yōu)化的隨機(jī)森林算法, 解決了傳統(tǒng)參數(shù)選擇方法存在主觀干擾性的問題, 該算法有利于較大數(shù)據(jù)集的提取,但無法作用于較小數(shù)據(jù)集且未對隨機(jī)森林算法的重要問題,即投票問題,進(jìn)行優(yōu)化。莊巧蕙對隨機(jī)森林算法的泛化能力進(jìn)行提升,使其能夠參與實(shí)際應(yīng)用,但是僅僅提高泛化能力會在某些情況下降低隨機(jī)森林算法的準(zhǔn)確性。楊彪使用基于誤判率比較的二次訓(xùn)練的方法對決策樹的葉結(jié)點(diǎn)進(jìn)行加權(quán),提高了隨機(jī)森林算法的性能,但在權(quán)重優(yōu)化方面仍有提升的空間。
自適應(yīng)優(yōu)化算法可以根據(jù)當(dāng)前數(shù)據(jù)的處理特征,自動調(diào)整模型參數(shù)或處理辦法,以達(dá)到增強(qiáng)模型分類性能的目的。粒子群算法是一種性能較好的自適應(yīng)優(yōu)化算法。本文采用粒子群算法對隨機(jī)森林進(jìn)行葉節(jié)點(diǎn)權(quán)重優(yōu)化,使權(quán)重向量更加科學(xué)合理。
粒子群優(yōu)化算法可以處理連續(xù)優(yōu)化問題和組合優(yōu)化問題。在傳統(tǒng)粒子群算法中,模型會初始化一群隨機(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)行直至滿足迭代終止條件。
隨機(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ī)森林的模型輸出為:
其中為測試集,為類別數(shù),為隨機(jī)森林模型的規(guī)模,f()表示第棵決策樹的分類結(jié)果,(?)是一個(gè)判斷函數(shù),當(dāng)基分類器的輸出結(jié)果滿足條件時(shí)為1,不滿足時(shí)為0。
對于隨機(jī)森林中決策樹的生成算法,我們選擇CART決策樹算法,此算法遞歸地在每個(gè)內(nèi)部節(jié)點(diǎn)處進(jìn)行基于基尼指數(shù)的特征分割,最終生成一棵二叉樹。CART決策樹對特征值的選取及特征取值的數(shù)目有很好的適應(yīng)性,因此被廣泛使用。
作為一種分類器的組合方法,隨機(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)的投票會影響整個(gè)隨機(jī)森林分類器的最終分類結(jié)果。因此,本文提出基于PSO 優(yōu)化的葉加權(quán)隨機(jī)森林算法,對隨機(jī)森林中每棵決策樹的每片葉節(jié)點(diǎn)加以不同權(quán)值,并使用PSO 算法進(jìn)行自適應(yīng)優(yōu)化,進(jìn)而達(dá)到提高隨機(jī)森林分類器整體性能的目的。
此外,針對隨機(jī)森林分類器在某些噪聲較大的分類或回歸問題上會出現(xiàn)過擬合的問題,我們通過bagging 算法對特征集和訓(xùn)練集進(jìn)行特征選取,以此來訓(xùn)練分類器,并提升算法在特征選取方面的準(zhǔn)確性。在特征選取之后,我們?yōu)槊總€(gè)子葉隨機(jī)分配初始可信度,構(gòu)成可信度向量,并使用PSO 算法對可信度向量進(jìn)行優(yōu)化,直至其性能達(dá)到預(yù)先設(shè)置的完成閾值。最后,我們記錄葉節(jié)點(diǎn)可信度向量,并將其作用于測試中最終得到的葉節(jié)點(diǎn),以此來對子葉加權(quán),最終采取投票法得出隨機(jī)森林的結(jié)果。
算法步驟如下:
其中為測試集,為類別數(shù),為隨機(jī)森林模型的規(guī)模,f()表示第棵決策樹的分類結(jié)果,(?)是一個(gè)判斷函數(shù),當(dāng)基分類器的輸出結(jié)果滿足條件時(shí)為1,不滿足時(shí)為0。
為了檢驗(yàn)此算法的性能,我們使用標(biāo)準(zhǔn)UCI測試數(shù)據(jù)集對算法進(jìn)行測試。選擇的數(shù)據(jù)集詳細(xì)信息如表1所示。
表1 數(shù)據(jù)集
為了測試算法的可靠性,我們在每一個(gè)數(shù)據(jù)集中加入30%的隨機(jī)噪聲,隨后用上述數(shù)據(jù)集對隨機(jī)森林算法和加權(quán)隨機(jī)森林算法分別進(jìn)行了十折交叉驗(yàn)證,以達(dá)到對比效果。測試結(jié)果如表2所示。
表2 分類精度
可以看出,相較于原本的隨機(jī)森林算法,PSO 優(yōu)化的加權(quán)隨機(jī)森林算法在各數(shù)據(jù)集上的分類精度都有明顯的提升。通過對比可以發(fā)現(xiàn),PSO 優(yōu)化的加權(quán)隨機(jī)森林算法對于大數(shù)據(jù)集的適應(yīng)性更好,性能提升度可達(dá)19.1%。
此外,為了測試PSO 優(yōu)化過程對本算法分類精度的影響,我們嘗試改變PSO 算法的種群數(shù)量和最深迭代次數(shù)兩個(gè)參數(shù),并進(jìn)行了多次對比實(shí)驗(yà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 的情況。從實(shí)驗(yàn)結(jié)果可以看出,pop 和iter 對PSO 性能并無明顯影響,PSO 優(yōu)化的加權(quán)隨機(jī)森林算法有較好的適應(yīng)性和穩(wěn)定性。
本文提出了一種基于PSO 優(yōu)化的葉加權(quán)隨機(jī)森林算法。這種算法針對決策樹生成算法的兩個(gè)隨機(jī)化過程,對隨機(jī)森林中每棵決策樹的每片葉節(jié)點(diǎn)加以不同的權(quán)值,使各個(gè)葉節(jié)點(diǎn)的投票權(quán)重與其分類精度達(dá)到平衡。利用PSO 算法全局搜索能力強(qiáng)、收斂速度快的優(yōu)勢,我們對葉節(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)定性上都有明顯提升,且對于大數(shù)據(jù)集的適應(yīng)性更好,性能可比傳統(tǒng)的隨機(jī)森林算法提升19.1%,有一定的研究和應(yīng)用價(jià)值。
目前,本文算法在提高模型適應(yīng)性方面還存在改進(jìn)的空間,在降低算法時(shí)間復(fù)雜度方面仍需作進(jìn)一步的研究。