基于隨機森林的自適應特征選擇算法

劉 凱，鄭山紅，蔣 權，趙天傲

(長春工業大學 計算機科學與工程學院，吉林 長春 130012)

0 引 言

隨機森林(random forest，RF)是在數據挖掘、生物信息學、管理學、醫學等領域中解決高維度和非線性樣本的一種分類器[1]。如何從高維度的數據選擇最優的特征選擇算法[2]，構建分類和回歸算法，從而達到更好的預測精度，是眾多學者研究的重要方向。

Tang F等[3]針對海量數據集中數據嚴重缺失的問題基于RF算法提出了mForest算法，利用RF算法的插補性能進一步增強了隨機特征之間的相關性，實驗表明mForest算法相比于missForest算法在效率上提升高達10倍；Vrushali Y Kulkarni等[4]通過對隨機森林算法中樣本進行不同維度的劃分并賦予相應的權值，在一定程度上提升了隨機森林算法的分類精準度和運行效率，但對于多類數據集的分類效果不是非常明顯；Oshiro T M等[5]通過大量的數學理論解釋了隨機森林在重復抽樣中選擇不同的訓練集能得到更高準確度；Bernard S等[6]重點研究了隨機森林算法中每個子分類器的強度與相關性的關系，但不能在構建子樹之前對森林的強度和相關度進行有效預估；Gall J等[7]采用序列和廣義序列的后向選擇方法進行特征選擇，并提出了一種基于隨機森林的封裝式特征選擇算法，但該算法在高維數據集中并不能確定廣義后向搜索方法中的L值。

綜上所述，上面都對隨機森林算法進行了有意義的改進，但本質上沒有很好地解決隨機森林算法自身的缺陷。所以，針對RF在隨機選擇屬性時屬性權值可信度低以及在構造單棵決策樹時算法整體分割能力差的問題，提出了一種基于隨機森林的自適應特征選擇算法SARFFS。

1 隨機森林算法

定義1：隨機森林[1,8]是一個在多個決策樹分類器{h(X,Θk),k=1,2,…,K}構建Bagging集成的基礎上進一步組合而成的大型集成分類器。構建RF算法的基本思想：首先，從原始數據集中利用bootstrap方法有放回地隨機抽取K個新樣本集，并用新樣本構建K棵分類回歸樹；其次，假設有n個特征，在每棵樹的每個節點隨機選擇mtry個特征，其中mtry

2 SARFFS算法

算法SARFFS是基于Spark分布式大數據計算平臺[9-10]，本節主要分成三部分：一種新的多元特征提取方法的提出、Group LASSO對RF特征選擇的優化和SARFFS算法生成及核心推理過程。

2.1 新的多元特征提取方法

隨機森林構建CART樹的整個過程中會有兩點不足：一是特征隨機選擇會影響屬性權重計算的不準確，二是隨著迭代次數的增加，數據集逐步增大，導致算法的運行效率大大降低。文中提出一種新的多元特征提取方法，充分考慮到每個特征對最終分類能力影響的差異性[11]，使用卡方檢驗[12]計算樣本之間的關聯度權重，并提出一種計算特征代表類的權重的計算方法，最后利用線性加權在內的兩種權重計算方法來代替傳統算法中依靠隨機性進行特征選擇的方法。

新的多元特征提取方法特征值對類的代表能力程度=特征值在全部分類中的分布的集中程度﹡特征值在某個類中出現的次的計算方法來給特征賦予有意義的權重最終的特征代表類的能力大小實質上就是給每個特征賦予一個區分程度的權重，樣本間的關聯程度可以通過卡方檢驗公式計算得出。

這種融合的方法充分利用了兩個分類算法的特性，SARFFS算法不僅很好地克服了傳統決策樹在多元特征時整體優化的不足，而且大大提升了隨機森林區分子決策樹并進行分割的能力。

2.2 Group LASSO優化特征的選擇

傳統的隨機森林算法存在對隨機選擇最優的特征對決策樹進行切分而導致沒有考慮特征之間關聯性的問題，比如每次從總的特征集中隨機抽取一組特征時，一方面會導致相關性的特征會重復抽取，另一方面具有代表性的一組特征又出現被分開的問題[13]。對此，Friedman等[14]指定一組變量同時選進或者選出，提出稀疏Group LASSO方法來保留樣本內重要的變量。該方法不僅去除了Group LASSO不重要的組，同時讓組中的變量選擇更有靈活性，其公式如下：

(1)

其中，當α=0時，式1就是LASSO；當β=0，就是Group LASSO。文中采取的方法是設置，用該方法能夠在每次隨機抽取的部分特征中保持內部特征對分類結果的一致性，即多分類作業非常強的特征會挑選在同一組，而相反比較弱的特征就會進入到下次的采樣過程中，這樣很好地保證了每次選擇出的特征是最優的，從而達到特征選擇優化的效果。

2.3 SARFFS算法的生成過程

利用2.1節提出的特征提取方法，并引用2.2中建立的架構算法代替RF算法中的傳統決策樹算法，建立了以傳統隨機森林為基本架構的優化算法SARFFS，保留了傳統算法的業務解釋和穩定性。

SARFFS算法的構建主要分兩步：一是通過多元特征提取方法對訓練集篩選出候選集；二是把候選集放入到邏輯回歸和決策樹融合的算法中，從而產生多棵隨機生成樹。其中采用Bagging抽樣獲得樣本的個數n，多元特征提取方法采用線性加權樣本的卡方檢驗關聯度W1來度量，計算如式2：

(2)

其中，Ai為實際特征的頻數；np1為理論特征的頻數；W1反映特征間的相關聯程度。

計算特征代表類的能力程度W2，如式3所示：

(3)

通過Group LASSO優化特征的選擇后放入算法中訓練出的算法函數為：

(4)

最后通過反復調參得到最優分類器，對算法的分類精確度、最優特征的集合進行輸出，并在驗證集上進行算法的驗證和評估。綜上所述，列出SARFFS算法的生成過程，如圖1所示。

圖1 SARFFS算法的生成過程

3 實 驗

3.1 實驗數據與實驗環境

實驗數據均來自UCI機器學習數據庫,挑選了Sonar_lisan、Ionosphere、Glass_lisan、Vehicle_lisan等10個數據集進行測試，如表1所示。

表1 實驗數據

實驗采用3臺虛擬機搭建集群環境，每臺虛擬機的硬件配置為8 cores、8 G內存、50 G磁盤，操作系統版本為Centos6.5，Spark版本為1.6.5，Hadoop版本為2.6.2。

3.2 實驗結果分析

選擇最佳的參數設置[15-16]，根據SARFFS算法中新的多元特征提取方法，可以得到特征的選擇過程和結果以及特征個數與分類精度之間的關系，如圖2所示。

圖2 特征個數與分類精度關系曲線

從圖2中可以得出結論，當特征數為60時，分類精度達到最高，這主要是因為SARFFS在迭代計算過程中會對一些不重要和不相關的特征進行動態消除或更替，這樣可以確保權重高的特征被優先選擇；當分類準確率達到最高峰值后會呈現下降趨勢，這主要是因為算法刪除了一些有用特征之后，可以根據實驗效果人為地控制特征選擇，SARFFS算法可以在每次迭代過程中輸出當前最優的特征和分類準確率。如表2所示，經過多元特征提取方法提取的最優特征比隨機選擇的特征具有更好的分類能力，這里的最優特征并不是指所有的特征。這8組實驗結果是在最高分類點時不斷刪除或替換最優特征而得到的，此外可以通過最優特征之間的變化情況及時調整特征的參數。這充分說明SARFFS算法具有高效的最優特征提取率，并可以判斷哪些特征對其相應的類別信息代表程度高一些，進而提升分類器的分類精準度。

表3列出了SARFFS算法與RF算法在相同數據集上分類精度的對比。從中可以明顯看出，在不同的數據集上SARFFS算法相比于傳統RF算法的分類性能都要好一點，這主要是因為SARFFS算法采用整體分類能力強的邏輯回歸與決策樹融合替代RF算法中的傳統決策樹算法，克服了RF算法整體分割能力差的問題。

表2 最優特征下對應的分類正確率

表3 SARFFS與RF的分類誤差對比

表3采用F1分數[17]分析SARFFS和RF分類算法的對比效果，進一步通過平衡F1分數比較SARFFS與RF的分類性能。

文中選擇了Sonar_lisan、Ionosphere、Glass_lisan等8個數據集，分別計算了分類算法的準確率、召回率和F1的值。從表4中可以得出，SARFFS算法比傳統RF算法在分類精度上提升了將近9%，說明SARFFS算法使用邏輯回歸和決策樹融合代替決策樹分類器在一定程度上解決了傳統決策樹整體分割能力不足的問題。

表4 SARFFS和RF在不同數據集下的效果對比 %

4 結束語

提出了一種新的隨機森林算法SARFFS，該算法主要采用一種新的多元特征提取計算方法代替以前的隨機特征選取策略，并利用Group LASSO方法對特征選擇進行優化,通過UCI數據進行實驗，結果表明SARFFS算法的線性加權計算方法能選擇出更優的特征，并在分類性能上使平衡F1分數提高近9%。

未來的研究工作將會從兩方面著手：第一，在特征選擇上繼續優化選擇的策略；第二，與梯度提升決策樹(gradient boost decision tree，GBDT)算法進行對比分析。