孫永明，楊 進

上海理工大學(xué)理學(xué)院，上海 200093

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

對于非平衡樣本分類主要研究為：加入代價損失函數(shù)與集成學(xué)習(xí)；構(gòu)造新的分類評判標準；對數(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ù)類樣本難以被學(xué)習(xí)到。ADASYN插值以每個少數(shù)類樣本為中心，在周圍生成新樣本，容易生成噪聲數(shù)據(jù)?；谶^采樣、欠采樣的缺點，很多學(xué)者提出了綜合采樣，取得了良好的效果。如SMOTEENN、SMOTETomek。有學(xué)者將采樣與集成算法結(jié)合研究大數(shù)據(jù)分類問題，如SMOTEBoost、SMOTEBagging。大部分學(xué)者研究將過采樣與集成算法結(jié)合，易造成算法學(xué)習(xí)到過采樣的噪聲數(shù)據(jù)，影響分類效果，且易過擬合。文獻[2]提出BSL（borderline SMOTE and tomeklink）綜合采樣與隨機森林結(jié)合的方法，改善了少數(shù)類樣本的分布，取得了良好的分類效果。

特征壓縮對于研究機器學(xué)習(xí)與數(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ā)式算法復(fù)雜，用時久，不適用于高維大數(shù)據(jù)。因此，結(jié)合Filter、Wrapper方法與集成算法壓縮特征成為一種新的思想[17]。文獻[18]提出一種結(jié)合信息增益率與隨機森林壓縮特征的方法。文獻[19]提出一種結(jié)合互信息、鄰域和SBS（sequential backward selection）的特征壓縮法。根據(jù)互信息、鄰域判別指數(shù)，用隨機森林的準確率作為評價指標，利用SBS 壓縮特征。但是，隨機森林容易學(xué)習(xí)到噪聲數(shù)據(jù)，造成過擬合。SBS 方法的時間成本高，降維結(jié)果不理想。文獻[20]提出一種XGBoost 與PCC（pearson correlation coefficient）相結(jié)合的特征壓縮法。目前，研究XGDT 算法的特征壓縮問題較少。很少有人將XGDT與Filter、Wrapper結(jié)合來研究特征壓縮問題。

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

1 算法

1.1 ASE綜合采樣

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

設(shè)少數(shù)類樣本數(shù)目ms，多數(shù)類樣本數(shù)目ml，xi為任意的少數(shù)類樣本，則總共需要合成的少數(shù)類樣本數(shù)G=(ml-ms)×β，β為平衡程度。設(shè)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ù)，進行刪除，減少學(xué)習(xí)器受錯誤樣本的影響，提高了分類精度。

算法1 ASE-Sampling

1.2 RFXT特征選擇與分類

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

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

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

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

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

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

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

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

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

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

算法2 ASE-RFXT

1.3 復(fù)雜度分析

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

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

2 實驗設(shè)計

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 評價指標

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

2.3 實驗方案

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

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

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

3 實驗結(jié)果

3.1 綜合采樣結(jié)果

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

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

3.2 特征選擇結(jié)果

由于KNN分類器方便高效，基于Wrapper的特征選擇算法中，很多文獻采用KNN作為評價指標[23-24]。然而，它的準確率并不高。本文以XGDT 的準確率為評價指標，并對比了不同分類器為評價指標壓縮特征空間后的特征個數(shù)（SF）與分類準確率（Acc）。實驗在Studentlife數(shù)據(jù)上進行，采用SFS搜索，結(jié)果如表3所示。表3中，SF與Acc表示在XRM、XRE特征加權(quán)法下不同分類器選擇的特征個數(shù)與對應(yīng)的準確?？梢钥闯?，在XRM與XRE的并行加權(quán)下，以SVM分類精度為評價指標搜索的特征子集的分類準確率最高，分別為90.3%、90.9%?；贙NN的分類準確率最低，分別為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ù)集并行加權(quán)后，按照權(quán)重排序，以XGDT 分類結(jié)果為評價指標，利用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 不同搜索方式的分類結(jié)果Table 4 Classification results for different search methods

如表5 對比了BSL、ASE 采樣后，不同特征壓縮法的特征個數(shù)（SF）與分類精度（Acc）?？梢钥闯觯瑢τ赟tudentlife、Phishing，在BSL 采樣下，基于XRE 并行加權(quán)的準確率是最高的，分別為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 結(jié)合的方法在對數(shù)據(jù)運用的特征個數(shù)更少情況下，達到較高準確率。XLVW 的特征個數(shù)是根據(jù)其他算法的特征個數(shù)進行設(shè)置的。各方法中，XRE 并行加權(quán)的準確率最高，XRM的降維效果相對較好。

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

如表6，對比了基于XRM 與XRE 構(gòu)造的特征選擇法、FSIGR[20]方法、文獻[15]方法的結(jié)果。文獻[15]是基于遺傳算法，由于原文未具體說明種群個數(shù)與迭代次數(shù)等參數(shù)。本文多次調(diào)參，選擇較優(yōu)參數(shù)，設(shè)置種群個數(shù)為30，迭代100 次，交叉與變異率均為0.2，記錄迭代最優(yōu)的10個特征子集的特征個數(shù)平均值和在XGDT上準確率的平均值。對于FSIGR方法，本文采用網(wǎng)格搜索對參數(shù)調(diào)優(yōu)，選擇基尼系數(shù)為分裂策略，設(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ù)較少。因此，提出的并行加權(quán)的特征選擇法對高維數(shù)據(jù)的分類具有一定效果。

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

3.3 分類結(jié)果

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

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

4 結(jié)論

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