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

張維,張浩晨

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

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

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

1 OTE-GWRFFS算法

隨機森林在對高維小樣本數(shù)據(jù)進行分類過程中，存在因樣本量的缺乏導致訓練深度不夠以及過擬合現(xiàn)象。而利用袋外數(shù)據(jù)進行特征重要性度量值計算時，又有可信度低以及特征排序穩(wěn)定性差問題。針對小樣本數(shù)據(jù)在特征提取過程出現(xiàn)的問題，本文提出了一種基于最優(yōu)集成隨機森林的小樣本數(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)建的隨機森林的決策樹個數(shù)n

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

算法：

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

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

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

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

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

step6 for (i=1 ton)

計算所有決策樹的精度Ai

(1)

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

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

for(i=1 Ton)

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

if (A減小)

break

step7 for(i=1 ton-n′)

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

(2)

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

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

(3)

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

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

(4)

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

1.2 時間復雜度分析

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

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

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

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

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

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

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

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

(6)

式中

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

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

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

1) 分類錯誤率

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

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

2) 特征重要性度量

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

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

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

(9)

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

4 實驗驗證

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

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

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

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

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

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

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

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

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

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

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

圖4 降維精度對比圖

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

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

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

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

5 結(jié) 論

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