自適應插值與特征壓縮的小樣本數(shù)據(jù)分類研究

孫永明，楊 進

上海理工大學理學院，上海 200093

目前，人工智能的迅速發(fā)展產(chǎn)生了海量數(shù)據(jù)，高維且類型復雜的大數(shù)據(jù)導致預測效率低，結果不準確[1-2]，尤其是多分類問題[3]。集成學習在解決這個問題上得到了很快的發(fā)展，應用較廣泛的有GBDT（gradient boosting dart tree）[4]、XGDT（extreme gradient boosting dart tree）[5]。對比隨機森林與GBDT，XGDT 防止過擬合，對數(shù)據(jù)擬合度更高。然而，XGDT 對非均衡數(shù)據(jù)分類時，仍會存在對少數(shù)類樣本學習不足，預測不準確的問題。并且它以決策樹為基學習器，容易受到高維冗余特征的干擾，對于劃分多的特征也會過擬合。研究XGDT 算法對于高維不均衡小樣本的分類問題十分必要。

對于非平衡樣本分類主要研究為：加入代價損失函數(shù)與集成學習；構造新的分類評判標準；對數(shù)據(jù)重采樣。如SMOTE（synthetic minority ove sampling technique）[6]、BorderlineSMOTE[7]、ADASYN（adaptive synthetic sampling approach）[8]過采樣；Tomek link[9]、ENN（edit nearest neighbor）[10]欠采樣等。SMOTE 插值對于稀疏的少數(shù)類樣本難以被學習到。ADASYN插值以每個少數(shù)類樣本為中心，在周圍生成新樣本，容易生成噪聲數(shù)據(jù)。基于過采樣、欠采樣的缺點，很多學者提出了綜合采樣，取得了良好的效果。如SMOTEENN、SMOTETomek。有學者將采樣與集成算法結合研究大數(shù)據(jù)分類問題，如SMOTEBoost、SMOTEBagging。大部分學者研究將過采樣與集成算法結合，易造成算法學習到過采樣的噪聲數(shù)據(jù)，影響分類效果，且易過擬合。文獻[2]提出BSL（borderline SMOTE and tomeklink）綜合采樣與隨機森林結合的方法，改善了少數(shù)類樣本的分布，取得了良好的分類效果。

特征壓縮對于研究機器學習與數(shù)據(jù)挖掘十分重要[11]。經(jīng)典的特征壓縮法有Filter、Wrapper、Embedding。Filter簡單高效，有Relief、ReliefF[12]等；Wrapper 準確但費時，有LVW（las vegas wrapper）[13]；Embedding 有LARS（least angle regresion）[14]。基于啟發(fā)式算法的思想，文獻[15]提出一種大數(shù)據(jù)下壓縮特征的遺傳算法。文獻[16]改進了森林優(yōu)化特征選擇算法。啟發(fā)式算法復雜，用時久，不適用于高維大數(shù)據(jù)。因此，結合Filter、Wrapper方法與集成算法壓縮特征成為一種新的思想[17]。文獻[18]提出一種結合信息增益率與隨機森林壓縮特征的方法。文獻[19]提出一種結合互信息、鄰域和SBS（sequential backward selection）的特征壓縮法。根據(jù)互信息、鄰域判別指數(shù)，用隨機森林的準確率作為評價指標，利用SBS 壓縮特征。但是，隨機森林容易學習到噪聲數(shù)據(jù)，造成過擬合。SBS 方法的時間成本高，降維結果不理想。文獻[20]提出一種XGBoost 與PCC（pearson correlation coefficient）相結合的特征壓縮法。目前，研究XGDT 算法的特征壓縮問題較少。很少有人將XGDT與Filter、Wrapper結合來研究特征壓縮問題。

本文針對小樣本數(shù)據(jù)的高維不均衡以及算法XGDT在大數(shù)據(jù)背景下研究不足的問題，構造了一種基于插值與特征壓縮的分類方法ASE-RFXT。首先構造ASE 采樣方法。改進ADASYN 的插值中心，計算每個少數(shù)類樣本近鄰內(nèi)同類樣本的中心作為插值中心，保持了數(shù)據(jù)原有信息，減少了自適應插值引入的噪聲，結合ENN降采樣方法，從而減少錯誤數(shù)據(jù)對分類的影響。其次構造了綜合ReliefF與XGDT的特征壓縮法RFXT，提出改進ReliefF 的統(tǒng)計量與XGDT 的特征平均信息增益對特征進行并行加權的方法，使得對特征重要性的評估更全面準確；利用PCC過濾低權重的相關特征，去除冗余信息，以集成算法XGDT的分類精度為評價指標，對特征空間進行SFS尋優(yōu)。最后，將方法ASE-RFXT在UCI數(shù)據(jù)集上進行實驗，從采樣、特征壓縮、分類三方面與常用方法進行對比，結果顯示具有一定的優(yōu)勢。

1 算法

1.1 ASE綜合采樣

ASE方法結合了ADASYN與ENN的優(yōu)點。ADASYN以每個少數(shù)類樣本為中心，在近鄰的同類之間隨機插值。由于有些少數(shù)類數(shù)據(jù)可能是噪聲數(shù)據(jù)，也可能處于分類邊界處，如果進行大量插值容易引入更多噪聲，如果直接刪除可能會導致信息丟失。因此，改進ADASYN的插值中心，計算少數(shù)類樣本k近鄰中同類樣本的中心，以此中心為插值中心，生成新樣本。同時將中心點與近鄰同類樣本的距離所乘的隨機數(shù)范圍改為[0，0.7]，使得生成的樣本更加靠近類別中心點。這樣減少了插值數(shù)據(jù)受異常數(shù)據(jù)的影響，減少生成噪聲的可能，保持了數(shù)據(jù)原有信息。

設少數(shù)類樣本數(shù)目ms，多數(shù)類樣本數(shù)目ml，xi為任意的少數(shù)類樣本，則總共需要合成的少數(shù)類樣本數(shù)G=(ml-ms)×β，β為平衡程度。設xi的k近鄰中多數(shù)類樣本數(shù)為Δi，則xi附近需要合成的少數(shù)類樣本數(shù)目為：

依據(jù)中心點xim進行插值，隨機選擇在xi的k近鄰內(nèi)的一個同類樣本xzi，生成隨機數(shù)λ∈[0,0.7]，則生成新樣本：

盡管對ADASYN 方法進行了改進，減少了噪聲數(shù)據(jù)的引入，然而，仍然不可避免存在一些錯誤樣本（包括原數(shù)據(jù)）。利用ENN降采樣，將每個樣本的k近鄰內(nèi)超過k2 的樣本是異類的數(shù)據(jù)視為噪聲數(shù)據(jù)，進行刪除，減少學習器受錯誤樣本的影響，提高了分類精度。

算法1 ASE-Sampling

1.2 RFXT特征選擇與分類

RFXT 算法是一種結合ReliefF 和XGDT 的特征壓縮法。主要思想是改進ReliefF 計算特征權重的統(tǒng)計量，并結合XGDT 的平均信息增益對特征并行加權，運用PCC刪除與低權重特征相關性強的特征，降低特征冗余度。以XGDT分類器的分類準確率為評價指標，利用SFS 技術搜索特征，直到準確率不再增加，從而得到最優(yōu)特征子集及其準確率。

XGDT算法用損失函數(shù)與正則項作為目標函數(shù)：

其中Fi是預測值，設類別數(shù)為K，則損失函數(shù)為：

將特征j在所有樹中的分裂次數(shù)設為FScore，則XGDT 計算特征j的權重為j在所有樹中的平均增益gj（加權方法記為X）為：

設xi的類別個數(shù)為k，xim，xih,l分別表示xi的同類樣本與異類樣本；c(c=k-1)表示與xi不同類別的那些類，設pl為第c類樣本在數(shù)中所占比例；特征j的權重統(tǒng)計量公式為（記為R權重統(tǒng)計量）：

考慮到不同的特征數(shù)值大小差異，公式（9）會導致數(shù)值大的特征權重偏大。定義新的距離公式為：

此外，R統(tǒng)計量只考慮與最近單個樣本之間的距離，權重易受最近鄰的影響。因此，本文計算樣本與所有同類樣本以及所有異類樣本之間距離的平均值，來衡量特征權重，減少了特征權重受單個近鄰值的影響，使得權重評估更加精確。記RE統(tǒng)計量為：

運用兩種特征加權方法，分別將RM與RE統(tǒng)計量計算的特征權重δj和XGDT的增益gj相結合，對特征進行并行加權。先標準化δj與gj，再計算δj與gj的平均值作為最終的特征權重wj=(δj+gj) 2。并行加權考慮了不同類別特征之間的距離也考慮了特征對分類的貢獻，減少了噪聲對特征權重的影響，使得最終的特征權重更具有魯棒性。將RM與XGDT結合的加權方法記為XRM，將RE與XGDT記為XRE。

本文整個算法分為三部分：對數(shù)據(jù)進行采樣、對數(shù)據(jù)進行特征選擇與分類。算法流程圖如圖1所示。

圖1 算法整體流程圖Fig.1 Overall flow chart of algorithm

算法2 ASE-RFXT

1.3 復雜度分析

ASE-RFXT算法的時間復雜度主要由采樣，特征加權，特征子集搜索構成。設樣本數(shù)量為m，特征維數(shù)為n，ASE的時間復雜度僅與m有關為O(m)。RE與RM是通過計算不同類別樣本之間的距離衡量特征權重，它的時間復雜度與m和n成線性關系，為O(m,n) 。設XGDT算法由深度為d的k棵樹組成，則XGDT時間復雜度為k×O(mnd)。利用SFS搜索尋找最優(yōu)特征子集，比較次數(shù)最多為n(n-1) 2，由于算法設置準確率不再增加為停止原則，因此，實際比較次數(shù)遠小于n(n-1) 2。則算法ASE-RFXT總的時間復雜度為：

故它的時間復雜度在合理范圍內(nèi)，它的空間所占內(nèi)存與樣本和特征數(shù)成線性關系，也在合理范圍內(nèi)。

2 實驗設計

2.1 實驗數(shù)據(jù)

實驗使用數(shù)據(jù)集Studentlife[21]，它來源于智能手機傳感器記錄的人的日常行為數(shù)據(jù)。從中提取了79個特征，2 138條有標簽的樣本，特征提取方法參考文獻[22]。此外，選取了UCI 數(shù)據(jù)集中常用分類數(shù)據(jù)集進行實驗。對數(shù)據(jù)集類型為名詞的特征進行Onehot 編碼，對所有數(shù)據(jù)進行標準化，數(shù)據(jù)分布如表1所示。

表1 所用數(shù)據(jù)集Table 1 Data sets used

2.2 評價指標

設分類器對樣本的預測結果為ypred，對應樣本的真實類別標簽為ytrue。由于研究的數(shù)據(jù)集不均衡，因此，本文利用Accuracy、Precision、Recall、Fβ值作為分類器預測結果的評價指標（取β=0.5），計算公式為：

2.3 實驗方案

本文是在2.20 Ghz CPU，8 GB RAM的Windows10，PyCharm 編程環(huán)境基于Scikit-learn 庫進行的實驗。在采樣上，對數(shù)據(jù)進行無采樣、BSL 采樣、ASE 采樣的對比；在特征加權上，對比了XGDT 增益（X），基于RM、RE，以及并行加權XRM、XRE的結果；對特征尋優(yōu)，對比了GS（貪心搜索）、SFS、SBS結果，并對比了SFS搜索在各分類器上的結果。同時，對比了XGDT 與LVW 結合（記為XLVW），以及其他文獻的特征選擇法的結果。進行實驗的分類器為極限梯度提升決策樹（XGDT）、隨機森林（SF）、支持向量機（SVM）、K近鄰（KNN）、決策樹（TREE）、多層感知機（MLP）。

分類器參數(shù)均在數(shù)據(jù)Studentlife上通過網(wǎng)格搜索與十折交叉驗證結合的方式進行調(diào)節(jié)。首先將數(shù)據(jù)集Studentlife 按照3∶1 劃分為訓練集與測試集，然后利用網(wǎng)格搜索調(diào)節(jié)分類器的參數(shù)，對訓練集進行十折交叉驗證，同時記錄驗證集準確率，將驗證集準確率最高時的參數(shù)保留下來。最終參數(shù)設置如表2所示。

表2 重要參數(shù)設置Table 2 Important parameters setting

3 實驗結果

3.1 綜合采樣結果

對BSL 與ASE 采樣方法中的近鄰個數(shù)k設置為5。對數(shù)據(jù)集Studentlife、Credit、Phishing、Winequality 進行無采樣（No），BSL與ASE綜合采樣結果如圖2所示。利用ASE 方法采樣后的數(shù)據(jù)分類準確率是最高的。這說明，提出的ASE方法可以提高不均衡數(shù)據(jù)分類準確率，與分類器的結合效果更佳。在Studentlife、Winequality多分類數(shù)據(jù)集上，對比結果較明顯，說明ASE方法對多分類問題更敏感。

圖2 采樣前后分類效果Fig.2 Classification effects before and after sampling

3.2 特征選擇結果

由于KNN分類器方便高效，基于Wrapper的特征選擇算法中，很多文獻采用KNN作為評價指標[23-24]。然而，它的準確率并不高。本文以XGDT 的準確率為評價指標，并對比了不同分類器為評價指標壓縮特征空間后的特征個數(shù)（SF）與分類準確率（Acc）。實驗在Studentlife數(shù)據(jù)上進行，采用SFS搜索，結果如表3所示。表3中，SF與Acc表示在XRM、XRE特征加權法下不同分類器選擇的特征個數(shù)與對應的準確。可以看出，在XRM與XRE的并行加權下，以SVM分類精度為評價指標搜索的特征子集的分類準確率最高，分別為90.3%、90.9%。基于KNN的分類準確率最低，分別為68.5%、67.6%。但是，基于SVM進行搜索的最優(yōu)特征子集的個數(shù)最多，這說明它的特征壓縮效果最差。而本文基于XGDT 搜索的特征子集的分類準確率低于基于SVM的1.8個百分點、1.3個百分點，但選擇的最優(yōu)特征子集的特征個數(shù)分別為13、16遠少于SVM的30、27。因此，綜合考慮準確率與選擇的特征個數(shù)，本文方法在準確率較高的情況下也可以有效降低特征維度，針對高維數(shù)據(jù)具有更高的實用價值。

表3 基于不同評價指標的特征選擇效果Table 3 Effectiveness of feature selection based on different evaluation indicators

如表4對比了對不同數(shù)據(jù)集并行加權后，按照權重排序，以XGDT 分類結果為評價指標，利用GS、SFS、SBS 三種策略壓縮特征空間的效果。實驗對比了最終搜索的特征子集數(shù)（SF）與分類精度（Acc）。從表4 看出，GS 方法在Studentlife、Credit、Phishing 數(shù)據(jù)集上，搜索的特征個數(shù)最少，但準確率最低。在其他數(shù)據(jù)集上，特征個數(shù)不是最少的情況下，準確率也很低。這說明GS方法容易陷入局優(yōu)；SBS方法，在所有數(shù)據(jù)集上的準確率都是最高的，但是它選擇的特征個數(shù)較多，特征壓縮效果不理想。在Student life、Phishing數(shù)據(jù)集上，用SFS搜索的精度分別比SBS 略低0.7 個百分點與1.6 個百分點，但搜索的特征個數(shù)分別為16、16，遠小于SBS的76、22；在數(shù)據(jù)Credit 上，SFS 與SBS 的精度相同，但SFS 選擇的特征個數(shù)為3，明顯低于SBS選擇的9。對比GS與SBS方法，SFS方法可以在達到較高的分類精度下選擇較少的特征。

表4 不同搜索方式的分類結果Table 4 Classification results for different search methods

如表5 對比了BSL、ASE 采樣后，不同特征壓縮法的特征個數(shù)（SF）與分類精度（Acc）。可以看出，對于Studentlife、Phishing，在BSL 采樣下，基于XRE 并行加權的準確率是最高的，分別為75.9%、86.2%。它選擇的特征個數(shù)分別為17、18。基于XRM的準確率稍低，分別為74.2%、95.0%，但它的特征個數(shù)較少，分別為12、17。對于Studentlife、Credit、Phishing，在ASE 采樣下，基于XRE 的準確率最高，分別為89.6%、95.2%、97.1%，它的特征個數(shù)也較少，分別為16、3、16。基于XRM的準確率稍低，分別為88.5%、92.9%、95.5%，但它的特征個數(shù)非常少，分別為13、2、11。所有特征選擇法在ASE采樣下的準確率都比在BSL 下高，且ASE 與XRE 結合的方法在對數(shù)據(jù)運用的特征個數(shù)更少情況下，達到較高準確率。XLVW 的特征個數(shù)是根據(jù)其他算法的特征個數(shù)進行設置的。各方法中，XRE 并行加權的準確率最高，XRM的降維效果相對較好。

表5 不同特征選擇的效果Table 5 Effects of different feature choices

如表6，對比了基于XRM 與XRE 構造的特征選擇法、FSIGR[20]方法、文獻[15]方法的結果。文獻[15]是基于遺傳算法，由于原文未具體說明種群個數(shù)與迭代次數(shù)等參數(shù)。本文多次調(diào)參，選擇較優(yōu)參數(shù)，設置種群個數(shù)為30，迭代100 次，交叉與變異率均為0.2，記錄迭代最優(yōu)的10個特征子集的特征個數(shù)平均值和在XGDT上準確率的平均值。對于FSIGR方法，本文采用網(wǎng)格搜索對參數(shù)調(diào)優(yōu)，選擇基尼系數(shù)為分裂策略，設置生成350 棵深度為13 的樹。可以看出，在Glass、Credit 上，基于XRE 的準確率最高，分別為93.16%、95.16%，特征選擇的特征個數(shù)為4、3，少于FSIGR的7、14；雖然在Phishing上的準確率97.15%，低于FSIGR 的97.4%，但選擇的特征個數(shù)16 少于FSIGR 的23；在Wine、Iris 上的準確率略低于文獻[15]，但選擇的特征個數(shù)較少。因此，提出的并行加權的特征選擇法對高維數(shù)據(jù)的分類具有一定效果。

表6 不同特征選擇算法的分類結果對比Table 6 Comparison of classification results of different feature selection algorithms

3.3 分類結果

如圖3，對比了Studentlife 數(shù)據(jù)運用BSL、ASE 采樣與XRM、XRE 構造的特征選擇法，在分類器上的Accuracy、Precision、Recall、Fβ值。可以看出，ASE 與XRE的結合在各分類器上的Accuracy、Precision、Recall、Fβ值都是最高的。說明將ASE 與XRE 的特征壓縮法結合，對解決高維不平衡數(shù)據(jù)具有良好的效果，且在XGDT分類器上的準確率高于其余的分類器，驗證了給出的ASE-RFXT 方法與XGDT 分類器結合能夠很好地解決高維不平衡數(shù)據(jù)的分類問題。

圖3 不同采樣與不同特征選擇方法結合的分類效果Fig.3 Classification effects of combining different samplings and different feature selection methods

4 結論

針對高維不平衡小樣本數(shù)據(jù)的分類效率低、準確率低的問題，本文構造了一種方法ASE-RFXT。提出了一種改進的自適應插值法并結合ENN降采樣構造ASE綜合采樣法，改善了不均衡樣本的分布，提高了分類準確率。通過改進ReliefF 特征加權法，提出了一種將ReliefF 與XGDT 結合對特征并行加權的REXT 特征選擇法，壓縮了特征空間，減少了信息冗余度，在不損失分類準確率的前提下提高了分類效率。從多個數(shù)據(jù)集的實驗對比中得出，構造的ASE-RFXT 方法，對不平衡高維數(shù)據(jù)、特征冗余數(shù)據(jù)的分類具有較好的效果。今后的研究展望：（1）對自適應采樣增加條件設置，可以根據(jù)高斯模型選擇采樣比例，檢驗采樣后的數(shù)據(jù)是否符合正態(tài)分布；（2）不同特征加權方法效果不一樣，根據(jù)需要進行選擇；（3）可以將雙向搜索方法運用于梯度提升決策樹的特征選擇中。