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

王 誠，高 蕊

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

0 引 言

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

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

1 隨機森林算法

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

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

定義1：隨機森林。

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

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

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

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

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

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

2 算法改進

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

2.1 改進的ReliefF算法

ReliefF，是由Relief算法發展而來的一個經典的特征權重賦值算法，它將特征與正負類之間的相關性作為依據，給每個特征賦予相應的權重。

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

(1)

其中，W(A)為特征A的權重，p(C)為原數據集中類別為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異類的樣本執行此操作，得到特征A在異類樣本間的差異均值。W={w1,w2,…,wn}是最終得到的特征權重向量，按權重從大到小對特征進行排序。

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

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

輸入：訓練集D，抽樣次數m，k=D中少數類樣本個數；

輸出：各個特征的特征權重W。

1.置0所有特征權重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]范圍內；

8.刪除權值<0的特征。

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

2.2 遞歸特征消除法

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

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

輸入:對應特征的權值W={w1,w2,…,wn}，數據集D；

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

1.初始化:讀入原始數據集D，設置FGSort=Null；

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

3.設置6次迭代中每次訓練得到的分類器的分類準確率向量TLAuc[1∶6]=0；

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

5.在數據集(D1-D5)上訓練決策樹分類器，對應特征子集記為FGSorti；

6.計算當前迭代的準確率TLAuci；

7.剔除權重最低的L個特征；

8.end for;

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

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

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

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

3 實驗及結果分析

3.1 評價指標

傳統二分類數據的評價準則有幾個重要指標，其中TP表示正確預測的正類，FN表示錯誤預測的正類，FP表示錯誤預測的負類，TN表示正確預測的負類。樣本總數N=TP+FP+FN+TN。

(1)分類精度(Accuracy)。

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

(3)特異度(Specificity)。

(4)ROC曲線/AUC。

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

圖1 改進的RW_RF算法

3.2 實驗數據集

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

表1 選用的UCI數據集具體參數

3.3 實驗過程

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

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

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

3.4 實驗結果分析

實驗結果如表2所示。

表2 各數據集在3種算法中的性能指標對比

將5個數據集在RF、R_RF和RW_RF算法中的各性能指標結果繪制成折線圖，如圖2所示。

圖2 改進前后各指標對比結果

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

表3 改進前后特征數對比

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

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

4 結束語

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

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