基于特征約簡的隨機森林改進算法研究

王 誠，高 蕊

(南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003)

0 引 言

隨著計算機網(wǎng)絡(luò)的飛速發(fā)展，電子數(shù)據(jù)庫的規(guī)模呈爆炸式增長，為幫助計算機更好地處理數(shù)據(jù)，得出可行的方法論，各分類回歸算法不斷煥發(fā)出新的生機。其中，隨機森林算法是以決策樹為基礎(chǔ)的分類回歸模型，它將多個單分類器集成，共同參與決策，因此分類精度要高于一般的單分類器。算法應(yīng)用領(lǐng)域涵蓋信用貸款[1]、生物醫(yī)學(xué)[2]、圖像[3]、銷售[4]等。雖然其在大部分場景中能達(dá)到很好的效果，但在處理某些特殊數(shù)據(jù)，如不平衡且特征維度高的醫(yī)療數(shù)據(jù)時，過多的冗余特征使得模型極易過擬合；且模型為了提升整體分類精度，習(xí)慣將少數(shù)類歸為多數(shù)類處理，得到虛假的分類精度。因此，算法不得不做出針對性的改進。

多年來學(xué)者們對原算法進行了很多改進，如通過聚類方式[5]、貪婪方法[6]挑選出一批具有代表性的高精度低相似性決策樹，提高了部分?jǐn)?shù)據(jù)集的分類精度，但對于上文提到的特殊數(shù)據(jù)集效果甚微；其他改進如針對不平衡數(shù)據(jù)：改變性能評價標(biāo)準(zhǔn)[7]、重采樣數(shù)據(jù)[8-9]、生成合成數(shù)據(jù)[10-11]等；又如針對特征選擇的：粗糙集[12]、鄰域互信息[13]、聚類[14]等，這些改進有一定成效，但很難融合以同時解決上述兩種問題。其中Marwa Hammami[15]提出了Filter與Wrapper結(jié)合的高維數(shù)據(jù)特征構(gòu)造的多目標(biāo)混合濾波器包裝進化算法，在消除冗余特征方面效果顯著；李碩[16]提出的基于改進的ReliefF算法結(jié)合支持向量機的非均衡特征選擇方法有效解決了不平衡數(shù)據(jù)的問題。這兩種改進一個針對特征排序，另一個針對特征約簡，能很好互補。受此啟發(fā)，文中提出一種基于特征約簡的隨機森林改進算法[17]：RW_RF。在隨機森林的決策樹構(gòu)建過程中引入Wrapper遞歸特征消除與ReliefF算法結(jié)合的特征選擇方法，盡可能挑選出擁有最佳分類性能的特征集，來減輕特征冗余和數(shù)據(jù)不平衡問題對模型的影響。

1 隨機森林算法

隨機森林算法(random forest，RF)，本質(zhì)是由多棵相互之間并無關(guān)聯(lián)的決策樹整合而成的多分類器，單條數(shù)據(jù)經(jīng)過每一棵決策樹投票，得票數(shù)最多的類別即為最終分類結(jié)果。

假設(shè)原始樣本集D(X,Y)，樣本個數(shù)為n，要建立k棵樹，隨機森林的具體步驟大致如定義1所示。

定義1：隨機森林。

(1)抽取樣本集：從原始訓(xùn)練集中隨機有放回地抽取n個樣本(子訓(xùn)練集)并重復(fù)n次，每一個樣本被抽中的概率均為1/n。被剩下的樣本組成袋外數(shù)據(jù)集(OOB)，作為最終的測試集。

(2)抽取特征：從總數(shù)為M的特征集合中隨意抽取m個組成特征子集，其中m

(3)特征選擇：計算節(jié)點數(shù)據(jù)集中每個特征對該數(shù)據(jù)集的基尼指數(shù)，選擇基尼指數(shù)最小的特征及其對應(yīng)的切分點作為最優(yōu)特征與最優(yōu)切分點，從節(jié)點生成兩個子節(jié)點，將剩余訓(xùn)練數(shù)據(jù)分配到兩個子節(jié)點中。

(4)生成CART決策樹：在每個子節(jié)點的樣本子集中重復(fù)執(zhí)行步驟(3)，遞歸地進行節(jié)點分割，直到生成所有葉節(jié)點。

(5)隨機森林：重復(fù)執(zhí)行步驟(2)～(4)，得到k棵不同的決策樹。

(6)測試數(shù)據(jù)：每一棵決策樹都對測試集中的每一條數(shù)據(jù)進行分類，統(tǒng)計k個分類結(jié)果，票數(shù)最多的類別，即為該樣本的最終類別。

2 算法改進

隨機森林算法在處理不平衡且特征數(shù)非常多的數(shù)據(jù)時有幾點弊端：第一，算法的分類思想是少數(shù)服從多數(shù)，因此在面對類別樣本數(shù)相差懸殊的數(shù)據(jù)集時，容易將少數(shù)類歸為多數(shù)類，造成很高的假分類精度；第二，過多的冗余特征會擾亂模型的學(xué)習(xí)能力，導(dǎo)致模型過擬合，限制了模型的普適性。因此，找出冗余度最小，且最能代表正負(fù)類數(shù)據(jù)之間的差異的特征子集，再生成隨機森林，是文中算法改進的思路?；诖?，提出了改進的隨機森林算法RW_RF。首先在構(gòu)建CART決策樹的特征選擇步驟中，使用改進的ReliefF算法初步篩選掉一批不相關(guān)特征，并將留下的特征根據(jù)權(quán)重排序；接著運用Wrapper的遞歸特征選擇思想，依次刪除低相關(guān)特征和冗余特征，得到最佳分類特征子集；最后在隨機森林中構(gòu)建整個分類模型。

2.1 改進的ReliefF算法

ReliefF，是由Relief算法發(fā)展而來的一個經(jīng)典的特征權(quán)重賦值算法，它將特征與正負(fù)類之間的相關(guān)性作為依據(jù)，給每個特征賦予相應(yīng)的權(quán)重。

ReliefF算法的思路為：首先從測試集中任意抽取一個樣本Rn，接著隨機抽取數(shù)量相同的k個Rn的同類與不同類樣本(Same spe/Diff spe)，分別計算特征A在Same spe和 Diff spe樣本間的距離，如果兩類距離的均值相差懸殊，說明該特征對此類樣本有較大的區(qū)分能力，繼而增加該特征的權(quán)重；反之，若距離相同，說明沒有區(qū)分能力，則降低該特征的權(quán)重。重復(fù)m次后得到的均值，作為該特征的權(quán)重。權(quán)重計算如下：

(1)

其中，W(A)為特征A的權(quán)重，p(C)為原數(shù)據(jù)集中類別為C的樣本所占比例，Mj(C)為類C?class(R)中第j個最近鄰樣本。diff(A,R1,R2)表示樣本R1和R2在特征A上的差，如下：

diff(A,R1,R2)=

(2)

由式(1)知，ReliefF將xi與異類C中距離xi最近的k個樣本在特征A上的差異取平均，再乘以C類樣本占所有與xi異類樣本的比例，對所有與xi異類的樣本執(zhí)行此操作，得到特征A在異類樣本間的差異均值。W={w1,w2,…,wn}是最終得到的特征權(quán)重向量，按權(quán)重從大到小對特征進行排序。

考慮到數(shù)據(jù)不平衡的問題，對以上的ReliefF算法稍作改進。為彌補非平衡數(shù)據(jù)對分類性能的影響，通過修改抽樣參數(shù)使它相對類均衡。具體做法是，計算權(quán)值時，將原本需要設(shè)定的k值固定為當(dāng)前樣本集中少數(shù)類個數(shù)，保證計算權(quán)重時當(dāng)前特征對應(yīng)的正負(fù)樣本數(shù)量均衡，理論上避免了分類結(jié)果偏向多數(shù)類的情況。具體步驟如定義2所示。

定義2：改進的ReliefF特征排序法。

輸入：訓(xùn)練集D，抽樣次數(shù)m，k=D中少數(shù)類樣本個數(shù)；

輸出：各個特征的特征權(quán)重W。

1.置0所有特征權(quán)重W={0,0,…,0}，T為空集；

2.fori=1 tomdo；

3.從D中隨機選擇一個樣本R；

4.從R的同類樣本集中找到R的k個最近鄰Hj(j=1,2,…,k)，從每一個不同類樣本集中找到k個最近鄰Mj(C)；

5.forA=1 toN(all features) do；

6.將所有特征值歸一化映射到[0,1]范圍內(nèi)；

8.刪除權(quán)值<0的特征。

此改進目的是，先刪除對分類效果有害的特征，再將剩余特征相對正類和負(fù)類的區(qū)分能力排序，以便接下來更方便地去除冗余和不相關(guān)的特征。

2.2 遞歸特征消除法

使用改進ReliefF算法快速篩選出分類性能最佳的特征，但沒有達(dá)到消除冗余特征的要求，還需要進一步優(yōu)化。文中借助Wrapper的遞歸特征選擇思想來剔除冗余特征，找到最佳特征子集。具體方法為，將特征按計算好的權(quán)重排序，每次從特征集合中去掉L個權(quán)值最小的特征生成CART分類決策樹，并計算其AUC值(具體見3.1節(jié))。逐次迭代，直到找到AUC值最高的一組特征子集。這個過程采用k折交叉驗證法來分割數(shù)據(jù)集，計算每次迭代的AUC值，選擇值最大的一次迭代作為刪除冗余特征的依據(jù)，具體過程如定義3所示。

定義3：遞歸特征消除法。

輸入:對應(yīng)特征的權(quán)值W={w1,w2,…,wn}，數(shù)據(jù)集D；

輸出:最佳分類特征子集FGSort。

1.初始化:讀入原始數(shù)據(jù)集D，設(shè)置FGSort=Null；

2.采用分層采樣技術(shù)將數(shù)據(jù)集D劃分為6等份，表示為:D=D1∪D2∪…∪D6；

3.設(shè)置6次迭代中每次訓(xùn)練得到的分類器的分類準(zhǔn)確率向量TLAuc[1∶6]=0；

4.for(i從1到[N/L]) //i代表循環(huán)變量，N代表數(shù)據(jù)集中所有特征個數(shù)，L為每次刪除的特征數(shù)量；

5.在數(shù)據(jù)集(D1-D5)上訓(xùn)練決策樹分類器，對應(yīng)特征子集記為FGSorti；

6.計算當(dāng)前迭代的準(zhǔn)確率TLAuci；

7.剔除權(quán)重最低的L個特征；

8.end for;

9.輸出6次分類準(zhǔn)確率最高的特征子集FGSorti。

此改進目的是將排好序的特征按末尾淘汰制訓(xùn)練決策樹，選出分類性能最佳的子集。

2.3 改進特征選擇法與隨機森林算法結(jié)合的RW_RF算法

RW_RF算法相比于原始隨機森林算法有兩點改進：第一，隨機森林隨機選擇特征的步驟替換為上述改進的ReliefF算法，在初步排除一批不相關(guān)特征的同時，對剩下特征的分類能力進行排序；第二，建立決策樹時，采用遞歸特征選擇思想依次刪除低權(quán)值特征，得到分類性能最好的特征子集，最后構(gòu)建隨機森林分類模型。改進算法部分流程如圖1所示。

3 實驗及結(jié)果分析

3.1 評價指標(biāo)

傳統(tǒng)二分類數(shù)據(jù)的評價準(zhǔn)則有幾個重要指標(biāo)，其中TP表示正確預(yù)測的正類，F(xiàn)N表示錯誤預(yù)測的正類，F(xiàn)P表示錯誤預(yù)測的負(fù)類，TN表示正確預(yù)測的負(fù)類。樣本總數(shù)N=TP+FP+FN+TN。

(1)分類精度(Accuracy)。

(2)靈敏度/召回率/查全率(Sensitivity)。

(3)特異度(Specificity)。

(4)ROC曲線/AUC。

(a)隨機森林流程 (b)特征選擇流程

圖1 改進的RW_RF算法

3.2 實驗數(shù)據(jù)集

實驗分別選擇美國加州大學(xué)UCI公開數(shù)據(jù)集中共5個用于分類問題的數(shù)據(jù)集。其中包含特征數(shù)相對較少且類平衡的數(shù)據(jù)，如糖尿病引起的視網(wǎng)膜病變數(shù)據(jù)集、垃圾郵件區(qū)分?jǐn)?shù)據(jù)集；還包括特征數(shù)相對較多且類不平衡的數(shù)據(jù)集，如癲癇診斷數(shù)據(jù)集、麝香判定數(shù)據(jù)集；最后是斯堪尼亞卡車故障數(shù)據(jù)集，此數(shù)據(jù)集極不平衡，正負(fù)類比例接近40∶1。這5個具有代表性的數(shù)據(jù)集，可以全面地展現(xiàn)改進的RW_RF算法在特征選擇和處理不平衡數(shù)據(jù)方面的優(yōu)勢。具體參數(shù)如表1所示。

表1 選用的UCI數(shù)據(jù)集具體參數(shù)

3.3 實驗過程

實驗所用的RW_RF算法采用Java編程實現(xiàn)，主要用到Weka包來封裝。硬件執(zhí)行環(huán)境配置為：Intel(R) Core(TM) i7-7700HQ CPU @2.80 GHz處理器、16 GB內(nèi)存、64位Windows 10企業(yè)版操作系統(tǒng)。隨機森林決策樹個數(shù)設(shè)置為50，取樣次數(shù)m設(shè)置為當(dāng)前數(shù)據(jù)集少數(shù)類個數(shù)k；構(gòu)建CART決策樹時基尼指數(shù)設(shè)為0.01。

此外，文中通過3種算法的對比來驗證提出的RW_RF算法的分類效果。第一種算法是未經(jīng)任何改進的原始隨機森林算法；第二種是在原始隨機森林算法中加入上文所提的改進ReliefF算法，命名為R_RF算法；第三種即提出的RW_RF算法。

分別將5個數(shù)據(jù)集在上述3種算法中進行分類，比較各自的分類精度(Accuracy)、靈敏度(Sensitivity)、特異度(Specificity)和AUC(area under the curve)指標(biāo)以及相關(guān)的參數(shù)。

3.4 實驗結(jié)果分析

實驗結(jié)果如表2所示。

表2 各數(shù)據(jù)集在3種算法中的性能指標(biāo)對比

將5個數(shù)據(jù)集在RF、R_RF和RW_RF算法中的各性能指標(biāo)結(jié)果繪制成折線圖，如圖2所示。

圖2 改進前后各指標(biāo)對比結(jié)果

圖2展示了5個數(shù)據(jù)集在原始RF、改進R_RF和最終RW_RF算法下分類精度、靈敏度、特異度的對比結(jié)果。其中DB和SB數(shù)據(jù)集本身的特征數(shù)和樣本數(shù)較少，由結(jié)果可知改進的R_RF算法模型沒有帶來太大的性能提升。然而，在特征數(shù)較多的數(shù)據(jù)集ES、MUSK和APS中，兩種改進算法均達(dá)到了很好的分類效果。結(jié)合表3可知，在改進的R_RF模型中訓(xùn)練后，3個數(shù)據(jù)集的特征數(shù)由原來的179、168、171，分別約簡到165、143、139，初步刪除了大量無關(guān)特征值后，4個分類指標(biāo)結(jié)果都有大幅提升，參見圖2(d)，在數(shù)據(jù)集ES、MUSK中整體分類性能提升最為明顯，說明加入改進的ReliefF算法有效刪除了不相關(guān)的特征，提高了模型分類性能。在RW_RF算法中，特征被進一步約簡至138、127、114，各指標(biāo)結(jié)果相較R_RF又有或多或少的提升，說明Wrapper遞歸特征消除法能在ReliefF的基礎(chǔ)上進一步約簡冗余特征，盡可能得到對分類最有幫助的特征集合。

表3 改進前后特征數(shù)對比

在處理數(shù)據(jù)不平衡問題中，改進的算法也體現(xiàn)了優(yōu)越性。APS數(shù)據(jù)集不平衡問題最嚴(yán)重，由圖2(a)可知，在原始RF中Accuracy分類精度非常高，但是由圖2(b)、(c)可知，其正類分類準(zhǔn)確率接近100%，負(fù)類分類準(zhǔn)確率都不足50%。但是經(jīng)過改進算法模型訓(xùn)練后，負(fù)類分類正確率有明顯提升，在R_RF中特異度達(dá)到了60%，在RW_RF中更是達(dá)到了69%，說明所提出的ReliefF抽樣改進方式確實能減輕隨機森林算法在處理不平衡數(shù)據(jù)集中的短板。參見圖2(d)，RW_RF的折線均在R_RF和RF之上，說明提出的RW_RF算法具有最佳的分類性能。

綜上所述，RW_RF算法不論在消除冗余特征還是減輕不平衡數(shù)據(jù)對模型的影響方面，都帶來了有效的提升。相比于初始隨機森林算法，RW_RF算法更適用于解決特征維度高且不平衡的數(shù)據(jù)分類問題。

4 結(jié)束語

圍繞多特征及不平衡數(shù)據(jù)的特殊性對隨機森林算法做出了一些改進。將ReliefF算法和Wrapper遞歸特征選擇法融合來代替隨機森林算法中的特征選擇過程，得到RW_RF算法，并選擇5組有代表性的UCI數(shù)據(jù)集進行分類測試。結(jié)果表示，RW_RF算法有更好的分類性能，證明了該改進算法對解決數(shù)據(jù)的特征冗余和數(shù)據(jù)不平衡問題有積極意義。

由于使用了遞歸構(gòu)造決策樹的方法，使得算法時間復(fù)雜度大大增加。為了進一步優(yōu)化模型性能，接下來考慮實現(xiàn)算法并行化，如將模型在Spark并行計算框架中運行，以此來提高整體運算效率。