一種基于最優(yōu)集成隨機(jī)森林的小樣本數(shù)據(jù)特征提取方法

張維,張浩晨

(西北工業(yè)大學(xué) 機(jī)電學(xué)院,陜西 西安 710072)

在特征選擇算法的研究中,隨機(jī)森林(random forest,RF)算法[1]在構(gòu)建決策樹的過程中基于不純度降低方法(mean decrease impurity)給特征進(jìn)行排序。基于隨機(jī)森林的RVS特征選擇算法[2]，利用給特征加入噪聲后的袋外數(shù)據(jù)(out of bag data)預(yù)測(cè)準(zhǔn)確率與原始袋外數(shù)據(jù)預(yù)測(cè)準(zhǔn)確率之差，描述特征重要性度量值，因其能夠有效去除冗余信息、處理時(shí)間短且效率高，成為特征選擇的主流方法[3]。以上2種傳統(tǒng)的隨機(jī)森林特征選擇法在處理數(shù)據(jù)量充足且分布均衡的數(shù)據(jù)時(shí)特征提取效果良好，但是在處理小樣本數(shù)據(jù)時(shí)由于訓(xùn)練樣本少，構(gòu)建決策樹分類時(shí)極易出現(xiàn)過擬合[4]，導(dǎo)致計(jì)算特征重要性度量值時(shí)不穩(wěn)定且精度低，降低了特征提取的有效性。

采用隨機(jī)森林對(duì)高維小樣本數(shù)據(jù)進(jìn)行特征提取的難點(diǎn)主要在于樣本量缺乏以及決策樹的穩(wěn)定性差、精度低。徐少成等[5]提出了基于隨機(jī)森林的加權(quán)特征選擇算法，采用單棵決策樹的權(quán)重與特征重要性度量值加權(quán)平均得到最終的特征重要性度量值，提升了隨機(jī)森林特征提取的精度，但是該方法在處理小樣本數(shù)據(jù)時(shí)不能有效提升決策樹集合的穩(wěn)定性[6]。Khan等[7]總結(jié)了最優(yōu)樹集合思想(optimal tree ensemble)，認(rèn)為隨機(jī)森林中單株樹的預(yù)測(cè)精度對(duì)最終分類有極大影響，提出了一種基于個(gè)體準(zhǔn)確性和多樣性的決策樹選擇方法，提升了隨機(jī)森林分類的精度以及穩(wěn)定性，該方法應(yīng)用于小樣本數(shù)據(jù)特征提取中可大大提升決策樹集合的穩(wěn)定性，但是該方法并未考慮小樣本所帶來的過擬合和特征提取精度低問題[8]。本文結(jié)合小樣本數(shù)據(jù)在特征提取過程中出現(xiàn)的難點(diǎn)，提出了OTE-GWRFFS算法，結(jié)合生成式對(duì)抗網(wǎng)絡(luò)(GAN)生成相似數(shù)據(jù)[9]，并采用改進(jìn)的非局部均值去噪算法[10]修正生成數(shù)據(jù)的分布誤差，利用基于權(quán)重的最優(yōu)樹算法計(jì)算特征的重要性度量值，提高了小樣本數(shù)據(jù)特征提取的精度、穩(wěn)定性以及有效性。

1 OTE-GWRFFS算法

隨機(jī)森林在對(duì)高維小樣本數(shù)據(jù)進(jìn)行分類過程中，存在因樣本量的缺乏導(dǎo)致訓(xùn)練深度不夠以及過擬合現(xiàn)象。而利用袋外數(shù)據(jù)進(jìn)行特征重要性度量值計(jì)算時(shí)，又有可信度低以及特征排序穩(wěn)定性差問題。針對(duì)小樣本數(shù)據(jù)在特征提取過程出現(xiàn)的問題，本文提出了一種基于最優(yōu)集成隨機(jī)森林的小樣本數(shù)據(jù)特征提取方法(OTE-GWRFFS算法)。OTE-GWRFFS算法的流程如圖1所示。

圖1 OTE-GWRFFS算法流程圖

1.1 OTE-GWRFFS算法流程

OTE-GWRFFS算法的具體步驟如下所示。

輸入：原始數(shù)據(jù)集S：包括樣本數(shù)N和樣本特征A=(A1,A2,A3,…,AM)

構(gòu)建的隨機(jī)森林的決策樹個(gè)數(shù)n

輸出：樣本特征Aj的最終特征重要性度量值Fj

算法：

step1 初始化原始數(shù)據(jù)集S，設(shè)置構(gòu)建隨機(jī)森林的決策樹個(gè)數(shù)n

step2 利用GAN算法對(duì)原始數(shù)據(jù)集進(jìn)行數(shù)據(jù)增強(qiáng)，得到生成數(shù)據(jù)集S′

step3 利用改進(jìn)的NL-Means對(duì)生成數(shù)據(jù)集S′進(jìn)行個(gè)別離群點(diǎn)的擬合得到數(shù)據(jù)集S″

step4 采用bagging抽樣，構(gòu)成L個(gè)訓(xùn)練數(shù)據(jù)集S1i(i=1,2,…,L)，一個(gè)測(cè)試數(shù)據(jù)集S2，每個(gè)訓(xùn)練數(shù)據(jù)集中有N′個(gè)樣本數(shù)據(jù)，m個(gè)樣本特征

step5 對(duì)數(shù)據(jù)集S1i進(jìn)行決策樹的構(gòu)建

step6 for (i=1 ton)

計(jì)算所有決策樹的精度Ai

(1)

式中：Ai為第i棵決策樹的分類精度；T為測(cè)試集樣本數(shù)量；ti,s為第i棵決策樹對(duì)測(cè)試樣本的分類與樣本真實(shí)分類相同的樣本數(shù)目

將所有樹的Ai按照由大到小排序

for(i=1 Ton)

逐次去除后n′棵樹并計(jì)算最終的分類精度A

if (A減小)

break

step7 for(i=1 ton-n′)

計(jì)算決策樹的權(quán)重ωi

(2)

式中：ωi代表第i棵樹的權(quán)重；ti,e代表第i棵決策樹對(duì)測(cè)試樣本的分類與隨機(jī)森林所有樹對(duì)測(cè)試樣本的分類相同的樣本數(shù)目；T代表測(cè)試集的樣本數(shù)量。

計(jì)算第i棵決策樹中第j特征的重要性度量值Mi,j

(3)

式中，Ac,j定義為給測(cè)試集中第j個(gè)特征加入高斯噪聲后的平均分類精度。

step8 最終的特征重要性度量值Fj

(4)

在計(jì)算完特征重要性度量值后，需要摒棄重要程度不高的特征，即采用后向搜索法，逐一去除重要程度靠后的特征并計(jì)算去除該特征后的平均分類精度，保留剩余最優(yōu)特征子集的評(píng)判標(biāo)準(zhǔn)即去除該特征及排名低于該特征的其他特征后的平均分類精度達(dá)到最高。

1.2 時(shí)間復(fù)雜度分析

本文所提出的OTE-GWRFFS算法中基分類器選擇CART算法。假設(shè)本算法中訓(xùn)練數(shù)據(jù)集的特征維數(shù)為M，訓(xùn)練樣本個(gè)數(shù)為N，隨機(jī)森林在構(gòu)建CART樹的過程中，從N個(gè)訓(xùn)練樣本中利用bagging抽取N′個(gè)訓(xùn)練樣本，從M個(gè)特征中隨機(jī)選擇m個(gè)特征計(jì)算信息增益，并且對(duì)樹的生長(zhǎng)不進(jìn)行剪枝。在本實(shí)驗(yàn)中，采用序列后向選擇策略進(jìn)行最優(yōu)樹的選擇需要循環(huán)(n-p)次，特征選擇需要循環(huán)(m-p)次(p由數(shù)據(jù)集特征數(shù)決定，一般不少于5個(gè))，根據(jù)排序后的特征集合生成新的訓(xùn)練數(shù)據(jù)集需要進(jìn)行(m-p)次計(jì)算，每次計(jì)算時(shí)間為常數(shù)，故本算法總的時(shí)間復(fù)雜度可以近似表示為

由(5)式可見，OTE-GWRFFS算法的時(shí)間復(fù)雜度與特征維數(shù)m呈近似平方關(guān)系，與訓(xùn)練數(shù)據(jù)集樣本個(gè)數(shù)N′呈近似立方關(guān)系，對(duì)于高維小樣本數(shù)據(jù)，運(yùn)算時(shí)間是可以接受的，算法具有較好的擴(kuò)展性。

2 小樣本數(shù)據(jù)擴(kuò)充

數(shù)據(jù)量小在特征選擇過程中是影響特征排序精度以及穩(wěn)定性的主要原因，從算法層面改進(jìn)超參數(shù)設(shè)定的方法始終存在局限性[11]，從數(shù)據(jù)層面通過數(shù)據(jù)增強(qiáng)技術(shù)擴(kuò)充數(shù)據(jù)解決數(shù)據(jù)量小的問題，是提高特征選擇精度以及穩(wěn)定性的一種有效方法。本文依據(jù)表格數(shù)據(jù)與圖像之間的等價(jià)性利用GAN對(duì)小樣本數(shù)據(jù)集進(jìn)行數(shù)據(jù)擴(kuò)充。由于生成的數(shù)據(jù)在反歸一化過程中會(huì)因小程度的偏差最終反映出較大的偏離，本文采用基于表格數(shù)據(jù)的非局部均值算法(NLM)對(duì)生成數(shù)據(jù)進(jìn)行修正，提高生成數(shù)據(jù)與原始數(shù)據(jù)之間的分布相似性。數(shù)據(jù)生成模型如圖2所示。

圖2 數(shù)據(jù)生成模型圖

1) 數(shù)據(jù)生成

任意高斯噪聲序列通過生成器將原低維向量投影成為與原始數(shù)據(jù)維度一致的高維向量，通過判別器將歸一化后的原始數(shù)據(jù)S與生成的高維向量進(jìn)行分布相似性判斷，經(jīng)過不斷訓(xùn)練生成器和判別器，最終可以生成分布相似的數(shù)據(jù)，再經(jīng)反歸一化得到生成數(shù)據(jù)S′。

2) 數(shù)據(jù)分布修正

(6)

式中

該數(shù)據(jù)生成模型通過提升生成數(shù)據(jù)S′和原始數(shù)據(jù)S的數(shù)據(jù)分布相似性解決了表格數(shù)據(jù)生成的偏離問題，同時(shí)數(shù)據(jù)量的擴(kuò)增也避免了過擬合現(xiàn)象，提升了特征排序精度以及穩(wěn)定性。

3 基于權(quán)重的最優(yōu)樹集合

在生成對(duì)抗網(wǎng)絡(luò)的小樣本數(shù)據(jù)擴(kuò)充后，擴(kuò)充樣本與原始數(shù)據(jù)集有著一定的偏離性，不能真實(shí)地還原原始數(shù)據(jù)集的特征分布，因此在訓(xùn)練隨機(jī)森林的過程中，某些決策樹在隨機(jī)分配訓(xùn)練數(shù)據(jù)集時(shí)被分到過多的生成數(shù)據(jù)，導(dǎo)致在測(cè)試數(shù)據(jù)集中分類效果極差[12]，影響了特征重要性度量值的準(zhǔn)確度，為了避免該問題的出現(xiàn)，本文采用集合高精度以及高多樣性基分類器的方法，將訓(xùn)練好的基分類器按照分類精度排序并選取精度高的分類器作為最優(yōu)決策樹集合，可以在不影響決策樹多樣性的前提下降低不同類型模型的歸納偏差。

1) 分類錯(cuò)誤率

為了挑選出分類性能最優(yōu)的樹，每棵樹對(duì)測(cè)試集的分類錯(cuò)誤率(分類精度)按(1)式計(jì)算。

根據(jù)所計(jì)算出每棵樹的分類錯(cuò)誤率(分類精度)將所有樹的Ai按照由大到小排序，按照后向搜索法逐次選取前n′棵樹并計(jì)算最終的平均分類精度A，選取終止條件為最終平均分類精度A呈現(xiàn)下降趨勢(shì)且基分類器數(shù)量有集成決策意義即可。

2) 特征重要性度量

在得到最優(yōu)樹集合后，對(duì)決策樹給予不同權(quán)重再次綜合評(píng)估特征重要性度量值。原始數(shù)據(jù)集S通過bagging抽樣后會(huì)獲得L個(gè)訓(xùn)練樣本集S1i(i=1,2,…,L)和一個(gè)樣本數(shù)為T的測(cè)試集S2，這n個(gè)訓(xùn)練樣本集可以產(chǎn)生n棵決策樹，根據(jù)決策樹的預(yù)測(cè)結(jié)果可以獲得一個(gè)T×(n+2)的矩陣，如表1所示。

表1 n=7，T=5的決策矩陣

表1中第i棵決策樹的可信度(權(quán)重)可由(9)式得到

(9)

式中：ti,e代表第i棵樹中對(duì)T個(gè)測(cè)試樣本的分類結(jié)果和決策結(jié)果中一致的數(shù)量，Aensemble表示集成預(yù)測(cè)的準(zhǔn)確率，即決策結(jié)果與原始分類的相符程度。由于每棵決策樹的Aensemble值都是一樣的，是否考慮Aensemble的作用對(duì)排序結(jié)果沒有影響，在計(jì)算權(quán)重時(shí)加入這個(gè)因素，其目的是盡量縮小各決策樹間權(quán)重的相對(duì)差距。

4 實(shí)驗(yàn)驗(yàn)證

為驗(yàn)證本OTE-GWRFFS算法在高維小樣本數(shù)據(jù)集上的有效性，在UCI數(shù)據(jù)集中挑選了5個(gè)具有代表性的小樣本數(shù)據(jù)集。對(duì)于每個(gè)數(shù)據(jù)集，都首先利用GAN進(jìn)行樣本擴(kuò)充，樣本擴(kuò)充的原則即保證原始數(shù)據(jù)集的分布特征，樣本擴(kuò)充量不能超過原始數(shù)據(jù)集的樣本數(shù)，保證了在bagging抽樣時(shí)訓(xùn)練集有足夠充分的原始樣本。表2列出了這些數(shù)據(jù)集名稱、特征以及數(shù)據(jù)擴(kuò)充結(jié)果。

表2 UCI中小樣本實(shí)驗(yàn)數(shù)據(jù)匯總

為了驗(yàn)證最優(yōu)樹集合算法(OTE)的有效性，圖3展示了5個(gè)數(shù)據(jù)集在后向搜索法過程中摒棄分類精度低的決策樹后對(duì)測(cè)試集的分類精度。可以看出每個(gè)數(shù)據(jù)集在選擇最優(yōu)樹過程中都有一個(gè)精度峰值，此峰值所對(duì)應(yīng)的決策樹量即最優(yōu)樹數(shù)量，表明最優(yōu)樹集合算法(OTE)可以有效選擇出分類精度最高的樹。

圖3 最優(yōu)樹集分類精度圖

表3列出了所用數(shù)據(jù)集在利用RFFS、WRFFS以及OTE-GWRFFS算法進(jìn)行特征選擇后得到的特征子集個(gè)數(shù)，選擇依據(jù)為各算法對(duì)特征重要性度量值進(jìn)行排序并采用后向搜索法選擇后分類精度達(dá)到最高時(shí)的特征子集個(gè)數(shù)。經(jīng)過特征子集個(gè)數(shù)的篩選，RFFS、WRFFS以及OTE-GWRFFS算法的維數(shù)平均下降率分別為25.68%,25.04%和34.20%。

表3 各算法特征選擇結(jié)果

表4給出了所有數(shù)據(jù)集在進(jìn)行特征選擇前的分類精度，以及利用RFFS、WRFFS和OTE-GWRFFS算法進(jìn)行特征選擇后，再次對(duì)特征選擇后的數(shù)據(jù)集進(jìn)行分類，經(jīng)過對(duì)比，RFFS、WRFFS以及OTE-GWRFFS算法的分類精度平均提升率分別為7.91%,9.42%和13.39%。

表4 各算法特征選擇前后分類精度對(duì)比 %

表5給出了所有數(shù)據(jù)集在未進(jìn)行特征提取前以及經(jīng)過各算法特征提取后的F1-score值。

為了清楚表達(dá)本算法在特征提取方面優(yōu)于RFFS、WRFFS算法，圖4展示了3種算法在特征提取過程中隨著特征數(shù)的降低，其分類精度的變化曲線。

表5 各算法特征選擇前后的F1-score值

圖4 降維精度對(duì)比圖

表6給出了數(shù)據(jù)擴(kuò)充算法前后的最優(yōu)特征子集數(shù)和分類精度對(duì)比，經(jīng)數(shù)據(jù)擴(kuò)充后算法的維數(shù)平均篩除提升率為9.16%,分類精度平均提升率為6.96%，驗(yàn)證最優(yōu)樹集合算法對(duì)小樣本數(shù)據(jù)擴(kuò)充的有效性。

表6 數(shù)據(jù)擴(kuò)充前后OTE算法的特征選擇精度對(duì)比

根據(jù)對(duì)表3的特征選擇結(jié)果和表4的特征選擇前后分類精度對(duì)比以及表5計(jì)算的分類F1-score值可知，本算法在基于相同的數(shù)據(jù)集進(jìn)行特征選擇后維數(shù)的平均下降率為34.20%，而RFFS以及WRFFS算法的維數(shù)平均下降率大約僅有25%，且經(jīng)過本算法特征降維后再次分類的F1-score值達(dá)到最高。可以證明本文算法相比于RFFS以及WRFFS算法有較大提升。表4展示了刪除冗余特征后本算法再次進(jìn)行分類，分類精度提升率達(dá)到13.39%，而RFFS以及WRFFS算法的分類精度提升率大約僅有8%，同時(shí)在特征提取后進(jìn)行再次分類的F1-score值有明顯提升，說明本算法能夠最大程度地對(duì)特征進(jìn)行降維處理，能夠更有效地刪除冗余特征，并且特征選擇精度更高。表6用數(shù)據(jù)擴(kuò)充前后的分類精度作為對(duì)比，可以看出在用于驗(yàn)證的數(shù)據(jù)集中，數(shù)據(jù)擴(kuò)充對(duì)維數(shù)平均篩除提升率約為9.16%，分類精度的提升率大約在6.96%，可以證明數(shù)據(jù)擴(kuò)充在處理小樣本數(shù)據(jù)時(shí)有效地提升了特征選擇的精度以及穩(wěn)定性。

結(jié)合實(shí)驗(yàn)結(jié)果，在特征選擇的維數(shù)平均下降率以及在分類精度方面，本算法都比其他2種算法更有效、精度更高。由于選取的數(shù)據(jù)具有廣泛的代表性，所以說本算法在特征選擇上具有更強(qiáng)的適用性。且本算法在針對(duì)于極小樣本數(shù)據(jù)集時(shí)也具有有效性，可以完全避免過擬合現(xiàn)象且特征提取效果良好。

5 結(jié) 論

高維小樣本數(shù)據(jù)的特征降維極容易出現(xiàn)特征排序不穩(wěn)定，經(jīng)常會(huì)將關(guān)鍵特征作為不重要特征處理，大大影響了降維的精度，不利于后續(xù)數(shù)據(jù)挖掘工作。本文基于小樣本的降維問題，提出了基于最優(yōu)集成隨機(jī)森林的小樣本數(shù)據(jù)特征提取方法OTE-GWRFFS。建立數(shù)據(jù)增強(qiáng)模型，在數(shù)據(jù)擴(kuò)充的基礎(chǔ)上，采用改進(jìn)的NL-Means去噪法以及最優(yōu)樹集合OTE思想改善數(shù)據(jù)擴(kuò)增過程中出現(xiàn)的數(shù)據(jù)偏差性質(zhì)，通過給予最優(yōu)樹集合以不同權(quán)重再次提升每棵決策樹的重要性度量的可靠性。實(shí)驗(yàn)表明OTE-GWRFFS算法可以避免隨機(jī)森林過擬合問題，提升了特征排序的穩(wěn)定性及精度，在經(jīng)過特征選擇后，隨機(jī)森林分類精度明顯提升。