一種基于最優集成隨機森林的小樣本數據特征提取方法

張維,張浩晨

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

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

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

1 OTE-GWRFFS算法

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

圖1 OTE-GWRFFS算法流程圖

1.1 OTE-GWRFFS算法流程

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

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

構建的隨機森林的決策樹個數n

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

算法：

step1 初始化原始數據集S，設置構建隨機森林的決策樹個數n

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

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

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

step5 對數據集S1i進行決策樹的構建

step6 for (i=1 ton)

計算所有決策樹的精度Ai

(1)

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

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

for(i=1 Ton)

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

if (A減小)

break

step7 for(i=1 ton-n′)

計算決策樹的權重ωi

(2)

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

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

(3)

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

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

(4)

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

1.2 時間復雜度分析

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

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

2 小樣本數據擴充

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

圖2 數據生成模型圖

1) 數據生成

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

2) 數據分布修正

(6)

式中

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

3 基于權重的最優樹集合

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

1) 分類錯誤率

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

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

2) 特征重要性度量

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

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

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

(9)

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

4 實驗驗證

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

表2 UCI中小樣本實驗數據匯總

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

圖3 最優樹集分類精度圖

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

表3 各算法特征選擇結果

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

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

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

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

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

圖4 降維精度對比圖

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

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

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

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

5 結 論

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