劉 凱，鄭山紅，蔣 權(quán)，趙天傲

(長(zhǎng)春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，吉林 長(zhǎng)春 130012)

0 引 言

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

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

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

1 隨機(jī)森林算法

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

2 SARFFS算法

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

2.1 新的多元特征提取方法

隨機(jī)森林構(gòu)建CART樹的整個(gè)過程中會(huì)有兩點(diǎn)不足：一是特征隨機(jī)選擇會(huì)影響屬性權(quán)重計(jì)算的不準(zhǔn)確，二是隨著迭代次數(shù)的增加，數(shù)據(jù)集逐步增大，導(dǎo)致算法的運(yùn)行效率大大降低。文中提出一種新的多元特征提取方法，充分考慮到每個(gè)特征對(duì)最終分類能力影響的差異性[11]，使用卡方檢驗(yàn)[12]計(jì)算樣本之間的關(guān)聯(lián)度權(quán)重，并提出一種計(jì)算特征代表類的權(quán)重的計(jì)算方法，最后利用線性加權(quán)在內(nèi)的兩種權(quán)重計(jì)算方法來代替?zhèn)鹘y(tǒng)算法中依靠隨機(jī)性進(jìn)行特征選擇的方法。

新的多元特征提取方法特征值對(duì)類的代表能力程度=特征值在全部分類中的分布的集中程度﹡特征值在某個(gè)類中出現(xiàn)的次的計(jì)算方法來給特征賦予有意義的權(quán)重最終的特征代表類的能力大小實(shí)質(zhì)上就是給每個(gè)特征賦予一個(gè)區(qū)分程度的權(quán)重，樣本間的關(guān)聯(lián)程度可以通過卡方檢驗(yàn)公式計(jì)算得出。

這種融合的方法充分利用了兩個(gè)分類算法的特性，SARFFS算法不僅很好地克服了傳統(tǒng)決策樹在多元特征時(shí)整體優(yōu)化的不足，而且大大提升了隨機(jī)森林區(qū)分子決策樹并進(jìn)行分割的能力。

2.2 Group LASSO優(yōu)化特征的選擇

傳統(tǒng)的隨機(jī)森林算法存在對(duì)隨機(jī)選擇最優(yōu)的特征對(duì)決策樹進(jìn)行切分而導(dǎo)致沒有考慮特征之間關(guān)聯(lián)性的問題，比如每次從總的特征集中隨機(jī)抽取一組特征時(shí)，一方面會(huì)導(dǎo)致相關(guān)性的特征會(huì)重復(fù)抽取，另一方面具有代表性的一組特征又出現(xiàn)被分開的問題[13]。對(duì)此，F(xiàn)riedman等[14]指定一組變量同時(shí)選進(jìn)或者選出，提出稀疏Group LASSO方法來保留樣本內(nèi)重要的變量。該方法不僅去除了Group LASSO不重要的組，同時(shí)讓組中的變量選擇更有靈活性，其公式如下：

(1)

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

2.3 SARFFS算法的生成過程

利用2.1節(jié)提出的特征提取方法，并引用2.2中建立的架構(gòu)算法代替RF算法中的傳統(tǒng)決策樹算法，建立了以傳統(tǒng)隨機(jī)森林為基本架構(gòu)的優(yōu)化算法SARFFS，保留了傳統(tǒng)算法的業(yè)務(wù)解釋和穩(wěn)定性。

SARFFS算法的構(gòu)建主要分兩步：一是通過多元特征提取方法對(duì)訓(xùn)練集篩選出候選集；二是把候選集放入到邏輯回歸和決策樹融合的算法中，從而產(chǎn)生多棵隨機(jī)生成樹。其中采用Bagging抽樣獲得樣本的個(gè)數(shù)n，多元特征提取方法采用線性加權(quán)樣本的卡方檢驗(yàn)關(guān)聯(lián)度W1來度量，計(jì)算如式2：

(2)

其中，Ai為實(shí)際特征的頻數(shù)；np1為理論特征的頻數(shù)；W1反映特征間的相關(guān)聯(lián)程度。

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

(3)

通過Group LASSO優(yōu)化特征的選擇后放入算法中訓(xùn)練出的算法函數(shù)為：

(4)

最后通過反復(fù)調(diào)參得到最優(yōu)分類器，對(duì)算法的分類精確度、最優(yōu)特征的集合進(jìn)行輸出，并在驗(yàn)證集上進(jìn)行算法的驗(yàn)證和評(píng)估。綜上所述，列出SARFFS算法的生成過程，如圖1所示。

圖1 SARFFS算法的生成過程

3 實(shí) 驗(yàn)

3.1 實(shí)驗(yàn)數(shù)據(jù)與實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)數(shù)據(jù)均來自UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù),挑選了Sonar_lisan、Ionosphere、Glass_lisan、Vehicle_lisan等10個(gè)數(shù)據(jù)集進(jìn)行測(cè)試，如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)采用3臺(tái)虛擬機(jī)搭建集群環(huán)境，每臺(tái)虛擬機(jī)的硬件配置為8 cores、8 G內(nèi)存、50 G磁盤，操作系統(tǒng)版本為Centos6.5，Spark版本為1.6.5，Hadoop版本為2.6.2。

3.2 實(shí)驗(yàn)結(jié)果分析

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

圖2 特征個(gè)數(shù)與分類精度關(guān)系曲線

從圖2中可以得出結(jié)論，當(dāng)特征數(shù)為60時(shí)，分類精度達(dá)到最高，這主要是因?yàn)镾ARFFS在迭代計(jì)算過程中會(huì)對(duì)一些不重要和不相關(guān)的特征進(jìn)行動(dòng)態(tài)消除或更替，這樣可以確保權(quán)重高的特征被優(yōu)先選擇；當(dāng)分類準(zhǔn)確率達(dá)到最高峰值后會(huì)呈現(xiàn)下降趨勢(shì)，這主要是因?yàn)樗惴▌h除了一些有用特征之后，可以根據(jù)實(shí)驗(yàn)效果人為地控制特征選擇，SARFFS算法可以在每次迭代過程中輸出當(dāng)前最優(yōu)的特征和分類準(zhǔn)確率。如表2所示，經(jīng)過多元特征提取方法提取的最優(yōu)特征比隨機(jī)選擇的特征具有更好的分類能力，這里的最優(yōu)特征并不是指所有的特征。這8組實(shí)驗(yàn)結(jié)果是在最高分類點(diǎn)時(shí)不斷刪除或替換最優(yōu)特征而得到的，此外可以通過最優(yōu)特征之間的變化情況及時(shí)調(diào)整特征的參數(shù)。這充分說明SARFFS算法具有高效的最優(yōu)特征提取率，并可以判斷哪些特征對(duì)其相應(yīng)的類別信息代表程度高一些，進(jìn)而提升分類器的分類精準(zhǔn)度。

表3列出了SARFFS算法與RF算法在相同數(shù)據(jù)集上分類精度的對(duì)比。從中可以明顯看出，在不同的數(shù)據(jù)集上SARFFS算法相比于傳統(tǒng)RF算法的分類性能都要好一點(diǎn)，這主要是因?yàn)镾ARFFS算法采用整體分類能力強(qiáng)的邏輯回歸與決策樹融合替代RF算法中的傳統(tǒng)決策樹算法，克服了RF算法整體分割能力差的問題。

表2 最優(yōu)特征下對(duì)應(yīng)的分類正確率

表3 SARFFS與RF的分類誤差對(duì)比

表3采用F1分?jǐn)?shù)[17]分析SARFFS和RF分類算法的對(duì)比效果，進(jìn)一步通過平衡F1分?jǐn)?shù)比較SARFFS與RF的分類性能。

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

表4 SARFFS和RF在不同數(shù)據(jù)集下的效果對(duì)比 %

4 結(jié)束語(yǔ)

提出了一種新的隨機(jī)森林算法SARFFS，該算法主要采用一種新的多元特征提取計(jì)算方法代替以前的隨機(jī)特征選取策略，并利用Group LASSO方法對(duì)特征選擇進(jìn)行優(yōu)化,通過UCI數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，結(jié)果表明SARFFS算法的線性加權(quán)計(jì)算方法能選擇出更優(yōu)的特征，并在分類性能上使平衡F1分?jǐn)?shù)提高近9%。

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