一種基于粒子群算法優(yōu)化的加權(quán)隨機(jī)森林模型

王 杰， 程學(xué)新， 彭金柱

(鄭州大學(xué) 電氣工程學(xué)院 河南 鄭州 450001)

0 引言

隨機(jī)森林(RF)算法是一種分類模型，其本質(zhì)是將Bagging算法和random subspace算法結(jié)合起來(lái)[1-3]，通過(guò)構(gòu)造多棵決策樹分類器對(duì)測(cè)試樣本進(jìn)行分類，然后對(duì)這些決策樹采取投票選取機(jī)制確定最終的分類結(jié)果.由于隨機(jī)森林模型對(duì)噪聲和異常值的容忍度較高，且隨機(jī)森林直接通過(guò)數(shù)據(jù)進(jìn)行分類，不需要分類樣本的先驗(yàn)知識(shí)，因此可省略數(shù)據(jù)預(yù)處理的工作.隨機(jī)森林算法自提出之后，被廣泛地運(yùn)用于數(shù)據(jù)挖掘與分類問(wèn)題中[4-6].

針對(duì)隨機(jī)森林算法中存在的一些問(wèn)題，學(xué)者們提出了不同的方案，對(duì)隨機(jī)森林算法進(jìn)行改進(jìn).文獻(xiàn)[7]從選取特征、訓(xùn)練樣本等多個(gè)方面對(duì)隨機(jī)森林進(jìn)行改進(jìn)，提升了訓(xùn)練準(zhǔn)確率.文獻(xiàn)[8]提出了基于生存樹的隨機(jī)森林模型(RSF)，證明了隨機(jī)生存森林對(duì)于高維樣本的分類能力大于普通隨機(jī)森林.文獻(xiàn)[9]將分位數(shù)回歸理論引入隨機(jī)森林中，提出了分位數(shù)回歸森林(QRF).在處理生長(zhǎng)較差的決策樹方面，文獻(xiàn)[10]將隨機(jī)森林算法中每棵決策樹按分類性能進(jìn)行排序，并淘汰掉分類性能差的決策樹.但此方法的弊端在于容易淘汰掉僅對(duì)某一類別分類較好的決策樹，從而影響該類別最終的分類效果.文獻(xiàn)[11]提出了加權(quán)投票的概念，但其權(quán)值的計(jì)算方式不夠優(yōu)秀，很容易出現(xiàn)特別大的權(quán)值，從而使隨機(jī)森林的投票都集中于較少的幾棵樹.隨后，文獻(xiàn)[12]將以上兩種方法相結(jié)合，采用out-of-bag準(zhǔn)確率作為決策樹投票權(quán)重并保留70%的決策樹.此方法的弊端在于每棵決策樹out-of-bag樣本不同從而導(dǎo)致投票不能保證其公平性.此外，至今為止較少有文獻(xiàn)提及隨機(jī)森林中各參數(shù)對(duì)模型的影響，決策樹棵數(shù)或剪枝閾值的選取也沒(méi)有理論上的支持，通常只能靠經(jīng)驗(yàn)選取.

為解決以上問(wèn)題，本文提出了一種基于粒子群算法優(yōu)化的加權(quán)隨機(jī)森林算法(PSOWRF)，采用粒子群算法對(duì)隨機(jī)森林模型進(jìn)行優(yōu)化，通過(guò)迭代優(yōu)化的方式選取決策樹棵數(shù)、剪枝閾值等參數(shù).同時(shí)，為解決投票權(quán)重問(wèn)題，本文從訓(xùn)練樣本中提取出一部分樣本，作為預(yù)測(cè)試樣本，用來(lái)計(jì)算每棵決策樹的權(quán)值，從而保證其投票的公平性.而本文對(duì)權(quán)值的計(jì)算方式加以簡(jiǎn)化，僅采用預(yù)測(cè)試樣本的分類正確率作為每棵決策樹的權(quán)值.其原因在于過(guò)于復(fù)雜的權(quán)值計(jì)算方式會(huì)極大地增加訓(xùn)練時(shí)間，而采用較為簡(jiǎn)單的正確率加權(quán)方法，經(jīng)過(guò)粒子群算法優(yōu)化之后，同樣可保證其分類精確度.

1 決策樹算法

1.1 ID3算法

隨機(jī)森林算法是由多棵決策樹分類器構(gòu)成，故在研究隨機(jī)森林算法之前，需要對(duì)決策樹有一定的了解.目前有很多種決策樹生成算法，但最有影響力的是Quinlan的ID3算法.該算法在決策樹中引入信息論的概念，并定義了信息增益.ID3算法的原理如下所示：假設(shè)樣本S可按照目標(biāo)屬性分成c個(gè)不同的類別，則其分類的熵的定義為

(1)

其中：pi為目標(biāo)屬性的第i個(gè)值所對(duì)應(yīng)的樣本在總樣本S中所占的比例.

以上定義的分類熵可作為樣本S的純度判別標(biāo)準(zhǔn)，即Entropy(S)=0表示樣本S屬于同一種類別.根據(jù)此定義，可進(jìn)一步引伸出樣本S中決策屬性A的信息增益Gain(S,A)的定義為

(2)

其中：V(A)是決策屬性A的值域，|Sv|是屬性A的值為v的樣本數(shù)量，|S|是總樣本數(shù)量.

ID3算法就是每次都選取擁有最大信息增益的屬性作為其分類屬性進(jìn)行分類，而分類屬性臨界值的選取也要最大化信息增益，直到所有結(jié)點(diǎn)的分類熵值為0.若樣本的所有屬性均參與分類后分類熵仍大于0，則返回該樣本中目標(biāo)屬性的眾數(shù)所對(duì)應(yīng)的分類作為該樣本最終的分類結(jié)果.

1.2 C4.5算法

ID3算法雖可正確地進(jìn)行分類，但仍存在許多問(wèn)題.ID3算法只能對(duì)離散的數(shù)據(jù)進(jìn)行分類，無(wú)法處理連續(xù)數(shù)據(jù).且ID3算法沒(méi)有剪枝的步驟，甚至可能導(dǎo)致每個(gè)葉結(jié)點(diǎn)只包含一個(gè)樣本，產(chǎn)生過(guò)擬合現(xiàn)象.C4.5算法是對(duì)ID3算法的一個(gè)改進(jìn)，它采用信息增益率而非信息增益來(lái)選擇決策屬性.信息增益率的定義為：

(3)

此外，C4.5算法還加入了前剪枝的步驟.即在分類過(guò)程中，當(dāng)某集合的樣本數(shù)小于一個(gè)給定的閾值ε時(shí)，就直接將此集合看作一個(gè)葉結(jié)點(diǎn)，然后返回目標(biāo)屬性的眾數(shù)作為分類結(jié)果.閾值ε直接決定了決策樹是否會(huì)出現(xiàn)過(guò)擬合現(xiàn)象或者出現(xiàn)分類不準(zhǔn)確，但ε只能憑經(jīng)驗(yàn)選取，并無(wú)理論上的支持.

2 隨機(jī)森林模型及其優(yōu)化

2.1 隨機(jī)森林模型

隨機(jī)森林模型的實(shí)質(zhì)是一個(gè)有多棵互不相關(guān)決策樹的分類器.每棵決策樹均采用Bootstrap方法進(jìn)行采樣，然后再?gòu)乃械腗個(gè)決策屬性中隨機(jī)挑選出m個(gè)屬性進(jìn)行分類.在整個(gè)訓(xùn)練過(guò)程中，一般m的取值不變.訓(xùn)練完成后，當(dāng)測(cè)試樣本輸入時(shí)，每棵決策樹均對(duì)測(cè)試樣本進(jìn)行分類，并采取投票的方法決定該測(cè)試樣本的最終分類結(jié)果.假設(shè)對(duì)于一個(gè)測(cè)試樣本x，第l棵決策樹的輸出為ftree,l(x)=i，i=1,2,…,c，即為其對(duì)應(yīng)的類別，l=1,2,…,L，L為隨機(jī)森林中的決策樹棵數(shù),則隨機(jī)森林模型(RF)的輸出為

(4)

其中：I(·)表示滿足括號(hào)中表達(dá)式的樣本個(gè)數(shù).

2.2 隨機(jī)森林模型加權(quán)

在傳統(tǒng)的隨機(jī)森林模型中，每棵決策樹在投票時(shí)權(quán)重都相等，但又不能保證每棵決策樹的分類精度一致.因此，總會(huì)有一些訓(xùn)練精度不高的決策樹投出錯(cuò)誤的票數(shù)，從而影響了整個(gè)隨機(jī)森林的分類能力.為了降低訓(xùn)練精度不高的決策樹對(duì)整個(gè)模型的影響，本文提出了一種加權(quán)隨機(jī)森林模型.其核心是將訓(xùn)練樣本分為兩部分：一部分作為傳統(tǒng)隨機(jī)森林模型的訓(xùn)練樣本，對(duì)所有的隨機(jī)數(shù)進(jìn)行訓(xùn)練；另一部分為預(yù)測(cè)試樣本，在訓(xùn)練完成之后，對(duì)每棵決策樹分別進(jìn)行測(cè)試，并計(jì)算其分類正確率，

(5)

其中：Xcorrect,l為第l棵樹分類正確的樣本數(shù)，X為預(yù)測(cè)試樣本數(shù).

將此正確率作為對(duì)應(yīng)決策樹的權(quán)重，每棵決策樹在進(jìn)行投票時(shí)，都要乘以此權(quán)值.則加權(quán)隨機(jī)森林模型(WRF)的輸出為：

(6)

2.3 隨機(jī)森林模型PSO加權(quán)優(yōu)化

以上算法中，剪枝閾值ε、決策樹棵數(shù)L、預(yù)測(cè)試樣本數(shù)X、隨機(jī)屬性個(gè)數(shù)m等參數(shù)對(duì)整個(gè)模型的輸出具有一定的影響.但所有參數(shù)均需要通過(guò)經(jīng)驗(yàn)選取，并沒(méi)有理論上的支持.粒子群算法通過(guò)對(duì)鳥類捕食行為進(jìn)行模擬，能夠快速地選取最優(yōu)解.本文通過(guò)將粒子群算法引入模型，對(duì)加權(quán)隨機(jī)森林算法中的參數(shù)進(jìn)行迭代優(yōu)化，最終達(dá)到了較好的分類效果.

粒子群優(yōu)化加權(quán)隨機(jī)森林算法的步驟如下：

Step1 確定算法的參數(shù)，隨機(jī)設(shè)定出剪枝閾值ε、決策樹棵數(shù)L、預(yù)測(cè)試樣本數(shù)X、隨機(jī)屬性個(gè)數(shù)m的初值；

Step2 采用Bootstrap算法采樣，隨機(jī)生產(chǎn)L個(gè)訓(xùn)練集，并在每個(gè)訓(xùn)練集中選出X個(gè)預(yù)測(cè)試樣本；

Step3 利用每個(gè)訓(xùn)練集剩下的樣本分別生成決策樹，共L棵，在生成過(guò)程中，每次選擇屬性前，均從全部屬性中選出m個(gè)屬性作為當(dāng)前結(jié)點(diǎn)的決策屬性；

Step4 當(dāng)結(jié)點(diǎn)內(nèi)包含的樣本數(shù)少于閾值ε時(shí)，將該結(jié)點(diǎn)作為葉結(jié)點(diǎn)，并返回其目標(biāo)屬性的眾數(shù)作為該決策樹的分類結(jié)果；

Step5 當(dāng)所有決策樹生成后，對(duì)每棵決策樹進(jìn)行預(yù)測(cè)試，并利用式(5)計(jì)算其權(quán)值；

Step6 利用式(6)計(jì)算出模型的分類結(jié)果；

Step7 將分類結(jié)果作為適應(yīng)度值，采用粒子群算法對(duì)Step1中提到的參數(shù)進(jìn)行迭代優(yōu)化，確定最終模型的參數(shù).

3 實(shí)驗(yàn)驗(yàn)證及分析

本文中用到的實(shí)驗(yàn)數(shù)據(jù)均來(lái)自于加利福尼亞大學(xué)的UCI數(shù)據(jù)庫(kù)，并選取了其中Abalone、Banks、Car Evaluation、Letter、Wine Quality和Yeast共6個(gè)數(shù)據(jù)集.為了驗(yàn)證模型參數(shù)對(duì)加權(quán)隨機(jī)森林算法分類能力的影響，本文選取Wine Quality數(shù)據(jù)集作為驗(yàn)證數(shù)據(jù)集，分別對(duì)剪枝閾值ε和決策樹棵數(shù)L進(jìn)行驗(yàn)證.實(shí)驗(yàn)1對(duì)剪枝閾值ε在0到30之間進(jìn)行取值，并記錄所得分類準(zhǔn)確率.實(shí)驗(yàn)1的結(jié)果如圖1所示.實(shí)驗(yàn)2對(duì)決策樹棵數(shù)L分別取值為10到100之間的10的整數(shù)倍，其結(jié)果如圖2所示.

圖1 剪枝閾值對(duì)分類性能的影響Fig.1 Effect of pruning threshold on test accuracy

圖2 決策樹棵數(shù)對(duì)性能的影響Fig.2 Effect of tree’s number on test accuracy

通過(guò)圖1可看出，隨著剪枝閾值ε的不斷增加，分類性能呈現(xiàn)一個(gè)下降的趨勢(shì).因此對(duì)于數(shù)據(jù)集Wine Quality來(lái)說(shuō)，剪枝閾值ε為0可取得最高的分類準(zhǔn)確率.從圖2可發(fā)現(xiàn)，決策樹棵數(shù)在50以后，分類的準(zhǔn)確率在0.59左右開(kāi)始波動(dòng).故對(duì)于數(shù)據(jù)集Wine Quality，最佳的決策樹棵數(shù)為50.因此可說(shuō)明，Step1中提及的參數(shù)對(duì)模型的分類性能具有一定的影響.為保證選取到最優(yōu)值，本文采用粒子群算法對(duì)模型進(jìn)行優(yōu)化，提出粒子群優(yōu)化加權(quán)隨機(jī)森林算法(PSOWRF)，并在6組數(shù)據(jù)集上進(jìn)行測(cè)試.將其訓(xùn)練結(jié)果與文獻(xiàn)[12]中提到的普通加權(quán)隨機(jī)森林(WRF)、分位數(shù)回歸森林(QRF)、隨機(jī)生存森林(RSF)、傳統(tǒng)隨機(jī)森林(RF)、C4.5決策樹分類器(DT)、支持向量機(jī)(SVM)和BP神經(jīng)網(wǎng)絡(luò)等傳統(tǒng)分類器進(jìn)行對(duì)比，結(jié)果如表1所示.表1中記錄了所有算法對(duì)6個(gè)數(shù)據(jù)集的平均分類正確率. 每個(gè)數(shù)據(jù)集名之后括號(hào)中的兩個(gè)數(shù)字分類代表了該數(shù)據(jù)集的屬性個(gè)數(shù)和類別個(gè)數(shù).

表1 不同算法分類性能比較

注：粗體代表了每個(gè)數(shù)據(jù)集的最優(yōu)正確率，下劃線代表了與最優(yōu)正確率無(wú)統(tǒng)計(jì)學(xué)差異.

根據(jù)表1可以得到，PSOWRF在Abalone、Car Evaluation、Letter 3個(gè)數(shù)據(jù)集上均取得了最優(yōu)分類正確率，同時(shí)在Banks和Wine Quality兩個(gè)數(shù)據(jù)集上的分類正確率與最優(yōu)正確率無(wú)統(tǒng)計(jì)學(xué)差異.對(duì)于Abalone數(shù)據(jù)集，PSOWRF取得了最優(yōu)結(jié)果，WRF、RSF、QRF和SVM的表現(xiàn)情況相差不大，均比RF、DT和BP算法更加優(yōu)秀.對(duì)于高維的數(shù)據(jù)集Banks和Wine Quality，RSF充分展示了其對(duì)高維數(shù)據(jù)的分類能力，取得最優(yōu)解，而PSOWRF也表現(xiàn)良好，與RSF無(wú)明顯差異.對(duì)于數(shù)據(jù)集Car Evaluation，PSOWRF和QRF、SVM同時(shí)取得較好的分類結(jié)果，優(yōu)于其他算法.對(duì)于多類別的Letter數(shù)據(jù)集，PSOWRF遠(yuǎn)遠(yuǎn)領(lǐng)先于其他算法，取得最優(yōu)結(jié)果.最后，對(duì)于Yeast數(shù)據(jù)集，SVM算法超過(guò)了所有的隨機(jī)森林算法及改進(jìn).綜上所述，本文所提出的PSOWRF算法在除Yeast之外的5個(gè)數(shù)據(jù)集上均能夠取得不錯(cuò)的表現(xiàn)，而且在Abalone和Letter數(shù)據(jù)集上要明顯優(yōu)于其他算法.

4 結(jié)論

本文對(duì)隨機(jī)森林模型的投票機(jī)制做出了一定的改進(jìn)，從訓(xùn)練樣本中提取出一部分預(yù)測(cè)試樣本，并將每棵決策樹對(duì)預(yù)測(cè)試樣本的分類正確率作為其投票權(quán)值.為保證模型參數(shù)能夠取得最優(yōu)值，本文還利用粒子群算法對(duì)模型進(jìn)行優(yōu)化，提出了基于粒子群優(yōu)化的加權(quán)隨機(jī)森林算法.該算法在6組實(shí)驗(yàn)數(shù)據(jù)集上均取得了良好的結(jié)果.在今后的工作中，我們將會(huì)對(duì)隨機(jī)森林模型的采樣機(jī)制進(jìn)行研究.通過(guò)對(duì)比不同采樣算法對(duì)分類性能的影響，決定出最優(yōu)的采樣算法，而不局限于僅用Bootstrap算法進(jìn)行采樣.

[1] BREIMAN L. Random forests[J]. Machine learning, 2001, 45(1):5-32.

[2] BREIMAN L. Bagging predictors[J]. Machine learning, 1996, 24(2):123-140.

[3] HO T. The random subspace method for constructing decision forests[J]. IEEE transactions on pattern analysis and machine intelligence, 1998, 20(8):832-844.

[4] 李欣海. 隨機(jī)森林模型在分類與回歸分析中的應(yīng)用[J]. 應(yīng)用昆蟲學(xué)報(bào), 2013, 50(4):1190-1197.

[5] 林成德, 彭國(guó)蘭. 隨機(jī)森林在企業(yè)信用評(píng)估指標(biāo)體系確定中的應(yīng)用[J]. 廈門大學(xué)學(xué)報(bào)(自然科學(xué)版), 2007, 46(2):199-203.

[6] 楊帆, 林琛, 周綺鳳，等. 基于隨機(jī)森林的潛在k近鄰算法及其在基因表達(dá)數(shù)據(jù)分類中的應(yīng)用[J]. 系統(tǒng)工程理論與實(shí)踐, 2012, 32(4):815-825.

[7] ROBNIK-IKONJA M. Improving random forests[C]∥15th European Conference on Machine Learning. Italy, 2004.

[8] ISHWARAN H, KOGALUR U B, BLACKSTONE E H, et al. Random survival forests[J]. Journal of thoracic oncology official publication of the international association for the study of lung cancer, 2008, 6(12):1974-1975.

[9] NICOLAI M. Quantile regression forests[J]. Journal of machine learning research, 2006, 7(2):983-999.

[10] CROUX C, JOOSSENS K, LEMMENS A. Trimmed bagging[J]. Computational statistics & data analysis, 2007, 52(1):362-368.

[11] AMARATUNGA D, CABRERA J, LEE Y S. Enriched random forests[J]. Bioinformatics, 2008, 24(18):2010-2014.

[12] XU B, GUO X, YE Y, et al. An improved random forest classifier for text categorization[J]. Journal of computers, 2012, 7(12):2913-2920.