基于重采樣與特征選擇的不均衡數據分類算法

張忠林，曹婷婷

(蘭州交通大學電子與信息工程學院，蘭州730070)

1 引 言

在現實世界中存在大量不平衡數據，給研究帶來了一定的挑戰.不均衡數據分類，在許多領域中有著重要的應用，如信用卡欺詐［1］、醫療健康預測［2］、異常檢測［3］.傳統的分類方法旨在最大化整體分類準確性.對于不均衡數據分類，少數類的錯分代價相對較大，比如在醫療診斷數據中，人們更加關注的是異常錯誤診斷的數據;在氣象預測上，人們更加關注沙塵暴、暴雨、霜凍等極端天氣的預測精度.

國內外學者們對不均衡數據的研究主要集中在以下四方面，第一方面從數據層面上主要采用不同的抽樣方法平衡各類別的樣本數，如欠采樣［4］(Under-Sampling)、過采樣(Over-Sampling)、混合采樣(Mixed Sampling)以及相應的改進算法SMOTE［5］(Synthetic Minority Oversampling Technique)、Borderline-SMOTE［6］、CBNM［7］(Clustering-Based NearMiss)等;胡峰等［8］提出TWDIDO 算法，結合三支決策理論，對邊界域和負域中的小類樣本進行不同的過采樣處理，有效解決不平衡數據的二分類問題.第二方面是降維，常用的降維方法有特征提取和特征選擇.Sherif F.Abdoh 等人［9］用隨機森林(RF)和SMOTE 結合遞歸特征消除(RFE)和主成分分析技術(PCA)兩種降維技術，發現RF 與SMOTE 結合提高了分類性能.第三方面是算法層面，為了對不均衡的數據分類有較好的適應性，對傳統算法進行適當修改，代價敏感與集成算法取得較好的結果.最后一個方面就是找出新的合適的分類評價度量指標，使分類器不向多數類偏倚.

目前，將采樣技術與集成方法結合也是一種有效解決不均衡數據分類問題的有效途徑，SMOTEBoost［10］、SMOTEBagging［11］、RUSBagging［12］等算法均先運用采樣技術降低數據不平衡度，再采用集成策略進行相關研究.

學者們已經對不均衡數據分類問題進行了大量研究，但依舊存在一些不足，一般的欠采樣方法容易刪除有用的部分數據，造成一些重要信息的缺失;隨機過采樣只是簡單的復制樣本來增加少數類樣本的數量，模型產生過擬合的幾率比較大;SMOTE 過采樣算法產生的模糊邊界問題;按照經驗選擇參數一般很難得到性能最優的分類器［13］.

本文針對以上不均衡數據分類中存在的問題，從特征選擇與重采樣方法出發提出BSL-FSRF 方法，首先提出BSLSampling 對數據重采樣，進行數據均衡化操作，其次對各個維度上的特征的分類能力進行評價，進行特征刪減，因為猜中近鄰nearHit 和猜錯近鄰nearMiss 也不再只選一個，而是選擇幾個進行平均，擁有更好的穩定性，且改善了SMOTE 算法模糊邊界問題，可用于多類的問題;最后運用改進的Gridsearch 算法對隨機森林參數進行優化.通過公共數據集進行驗證，結果表明本文所提出的算法BSL-FSRF 在Kappa 系數，F-measure和AUC 值方面有一定的提升，針對不平衡數據分類偏向多數類的問題有一定的參考價值.

2 算 法

BSL-FSRF 算法首先提出一種BSL 重采樣，將少數類樣本進行邊界區分后只對邊界樣本進行SMOTE 插值，之后再利用Tomek link 進行欠采樣，在使數據集基本達到均衡的同時，減少噪聲樣本的數量;其次引入“假設間隔”(hypothesis margin)思想對各個特征維度進行度量，設定合適的閾值，將與類別相關性不高的特征移除，對數據進行降維，減少運行時間，提高模型精確度，并可擴展到多類別分類問題;最后采用隨機森林對數據進行分類，用Gridsearch 對參數進行尋優，對尋優方式進行改進.

2.1 BSL 采樣

SMOTE 算法基本思想是對少數類樣本進行分析并根據樣本間的歐氏距離人工合成一定數量的新樣本，針對其容易產生模糊邊界問題，BSL 采樣算法首先將少數類樣本分為安全樣本，噪聲樣本和邊界樣本，只對邊界樣本進行SMOTE 插值，對插值的邊界進行限制，從而使合成后的少數類樣本分布更合理.再利用Tomek link 數據清洗技術進行欠采樣，刪除Tomek link 對中多數類樣本，進一步去除噪聲.Tomek Link 對表示兩個分別屬于不同類別的樣本距離最近的一對樣本，其中一個是噪音樣本，或者兩個樣本都位于邊界附近.通過移除Tomek Link 對，清洗掉類間重疊樣本，從而更好地進行分類.BSL 采樣算法具體步驟如下:

算法 1.BSL-Sampling

輸入:原始樣本訓練集D，最近鄰樣本個數k

輸出:新的樣本訓練集T ″1

Step 1.將原始樣本訓練集D 按照4:1 切分為訓練集T1和測試集T2.

Step 2.按照式(1)計算少數類樣本每個樣本點Xi與所有T1中訓練樣本的歐氏距離，獲得該樣本點k 個近鄰樣本.

Step 3.對少數類樣本進行劃分.設在k 近鄰中有k ″(0≤k ″≤k)個屬于多數類樣本.

若k″=k，Xi被定義為噪聲樣本;

若 k/2≤k ″≤k，Xi被定義為邊界樣本;

若 0≤k ″＜k/2，Xi被定義為安全樣本;

邊界樣本記為{x'1，x'2，x'3，…，x'i，…，x'num}，num 表示少數類邊界樣本個數.

Step 4.計算邊界樣本點與少數類樣本Xi的k 近鄰，根據采樣倍率N，根據式(2)進行線性插值.

Step 5.合成的少數類樣本與原始訓練樣本T 合并，構成新的訓練樣本T'1.

Step 6.對整個訓練集樣本T'1進行Tomek link 數據清洗完成欠采樣，刪除Tomek link 對中的多數類樣本，更新訓練集為 T″1

2.2 BSL-FSRF 算法

隨機森林［14］作為一種改進的Bagging 集成方法，是集成學習領域中一個重要組成部分.文獻［15］對179 個分類算法分別在121 個數據集進行了研究分析，結果表明RF 算法是最優秀的.網格搜索算法(Gridsearch)通過窮舉法遍歷所給定的參數組合來優化模型，遍歷完成需要耗費大量訓練時間，文獻［16］提出了一種基于袋外數據估計的分類誤差，改進了網格搜索算法，通過不斷縮小網格間距，優化RF 的參數決策樹數量k'和候選分裂屬性數mtry，該方法克服了交叉驗證的缺點，提高了訓練速度，節省了時間.

基于重采樣與特征選擇的隨機森林算法(BSL-FSRF)主要包括數據預處理階段與分類兩個階段.

1)數據預處理階段，從重采樣與特征選擇兩個方面出發，首先對訓練集中的樣本進行BSL-Sampling，使樣本基本達到均衡并去除噪聲樣本，更新訓練集.其次對新的訓練集進行ReliefF 特征選擇，根據特征重要性進行一定的刪減，再次更新數據集;

2)分類階段，分類采用隨機森林算法，并運用改進Gridsearch 網格搜索算法，先采用大步長進行大范圍搜索，再進行小范圍尋優，用于優化隨機森林的決策樹數量k'和候選分裂屬性數mtry兩個參數;最后進行基于混淆矩陣的分類模型的評價.

BSL-FSRF 算法的具體步驟如下:

算法 2.BSL-FSRF

輸入:樣本訓練集D，抽樣次數t，特征權重閾值σ.

輸出:參數調優后隨機森林分類器模型，以及分類結果.

Step 1.調用算法1，生成新的平衡樣本訓練集T″1

Step 2.對訓練集T″1用ReliefF 特征選擇算法，利用公式(3)賦予所有和類別相關性高的特征較高的權重，更新并得到新的數據集T″1;

diff(A，R1，R2)表示兩個樣本 R1、R2在特征 A 上的差，R為訓練集D 中隨機選擇的一個樣本，Sj(C)表示類別C ∈Class(R)中的第 j 個最近鄰樣本，Hj(j=1，2，…，k)表示 R 同類中的k 個近鄰.

Step 3.將 T″1作為隨機森林的輸入，采取 boostrap 采樣，有放回地為每棵樹構造訓練集，大小為N.在每個節點處隨機選擇m 個特征，根據最小Gini 指數，比較并選擇佳特征，劃分數據集;

Step 4.遞歸生成決策樹，不剪枝;

Step 5.根據公式(4))計算未知樣本x 分類為M 的概率;

Step 6.采用多數投票法確定類別M ←arg max P(M |x)，并計算分類誤差;

Step 7.返回隨機森林分類器模型，分類結果.

Step 8.通過改進的Gridsearch 算法選擇合適的參數，優化生成決策樹的數目k'，候選分裂屬性數mtry兩個參數.網格搜索時，先選擇較大范圍的參數與步長，再逐漸縮小閾值范圍與步長大小，不斷調整搜索范圍找到較優參數.

Step 9.返回參數調優后隨機森林分類器模型以及分類結果.

Step 10.在測試集中T2中，測試調優模型的分類效果，并進行評價.

BSL-FSRF 整體算法流程圖如圖1 所示.

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

3 評價指標

傳統的用于衡量分類模型性能的整體正確率(Accuracy)已不再適用不均衡數據集，會對分類結果產生誤導.因此在處理不平衡的數據時，選擇有效的評價指標是非常有必要的，不均衡數據分類模型評價指標通常在混淆矩陣的基礎上，二分類混淆矩陣如表1 所示.

表1 二分類混淆矩陣Table 1 Two-class confusion matrix

公式(5)中β 表示查準率(Precision)和查全率(Recall)的重要性相對關系，一般取值為1，表示兩者的重要性相同.

其中F-measure［17］值是查準率(Precision)和查全率(Recall)的調和平均值;Kappa 系數評價分類器與真實分類之間的差異，此統計量越接近于1，表明分類器越優秀.ROC 曲線［18］的繪制需要經過調整不同的判定閾值，FPR 作為x 軸，TPR 作為y 軸，可以通過ROC 曲線評價一個分類器好壞，AUC 值越大，則正確率越高，分類器越好.

對于不均衡數據集，我們更加關注對少數類的分類結果，因此本文選取kappa 系數，少數類分類的F-measure 值以及ROC 曲線下的面積AUC 作為評價標準.

4 實驗及結果分析

4.1 數據集

本文使用類別不均衡的二分類公共數據集對提出的算法進行驗證，其中8 個數據集來自KEEL 數據庫，2 個來自加州大學歐文分校提出的用于機器學習的UCI 數據庫，具體信息描述如表2 所示，每個數據集的類分布是不均衡的，不平衡度IR(Maj/Min)從 1.79 到 41.4.(其中 glass 數據集代表 glass-0-1-2-3_vs_4-5-6)

表2 二分類不平衡數據集Table 2 Two-class unbalanced data sets

4.2 實驗及結果分析

4.2.1 實驗設計思路

為了驗證所提出的BSL-FSRF 算法在解決不均衡數據分類問題上的有效性，從四個角度進行相關的實驗驗證.

1)進行基礎實驗的驗證.

2)分類階段均采用RF，數據處理階段采用SMOTE 結合不同的降維方法，記為 SMOTE-CFS、SMOTE-PCA 算法、SMOTE-ReliefF，分別與本文數據預處理階段算法BSL-FS(FS 代表ReliefF 特征選擇算法)進行對比.

3)數據處理階段均采用BSL-FS 算法，分類階段分別采用不同的分類器J48，Naive Bayes，Adaboost 與改進網格搜索參數尋優后的隨機森林算法進行相應對比.

4)與其他相關算法的對比.

經過整體實驗對比分析，證明本文所提出的BSL-FSRF算法在不均衡數據分類問題上體現出一定的優勢.

4.2.2 參數設置

本文實驗重采樣算法用Jupyter Notebook 實現，分類算法基于Weka 平臺.對BSL-FSRF 算法中ReliefF 的特征權值閾σ 的選取針對每個數據集的實際情況，進行了初步探索.采樣算法SMOTE 的最近鄰k 值是提高隨機森林分類效果的關鍵參數，根據國內外學者大量的實驗研究，表明在多種情況下當k 值取5 時［19］，采樣有很好的效果，借鑒其研究本文 k 值選取5，上采樣倍率N 設為1，所有實驗均采用10 折交叉驗證(10-fold cross-validation).為提高實驗的可對比性，AdaBoost集成算法基分類器的選取與隨機森林保持一致，均為分類回歸樹(CART).

4.2.3 實驗結果分析

將未經采樣的隨機森林RF 模型、只經過BSL 采樣的BSL-RF 模型，只經過ReliefF 特征選擇的FS-RF 模型和同時經過 ReliefF 與 BSL-Sampling 處理的 BSL-FSRF 模型(未進行參數尋優)在10 個公共數據集進行了基礎實驗比較，可以看出重采樣與特征選擇結合算法的BSL-FSRF 模型有一定的優勢.經過BSL 采樣前后數據分布如表3，ReliefF 算法在10個數據集上各特征權重比較如圖2，表4 給出了選取的各個數據集特征信息，分類后的結果如表5 所示，其中AVG 行代表10 個數據集上各少數類評價指標的平均值.

表3 BSL-Sampling 前后數據分布Table 3 Data distribution before and after BSL-Sampling

分析各數據集上不同特征的權重，認為出現負值的情況表明該特征起到負作用，直接將其刪除.經過對ReliefF 算法閾值的初步探索，所選取的特征如表3 所示.分析表3，經過 BSL-sampling 算法在一定上采樣比率處理后數據的不均衡性得到了很好的改善且去掉了部分噪聲樣本.從表5 可以看出，同RF算法相比，BSL-FSRF 算法Kappa 平均值從69.0%提升到86.1%，F-measure 平均值從 73.2%提升到 89.7%，AUC 平均值從94.4%提升到97.32%，本文方法在評價指標 Kappa 系數，F-measure 以及AUC 上都有一定的提升;經過重采樣，均衡了樣本分布，ReliefF 特征選擇算法算法根據給定的權重進行數據的降維，減少冗余特征，使分類具有更好的效果，BSL-FSRF 算法比分別單個使用ReliefF、BSL-sampling 算法的使用具有更高的泛化能力，相對未采樣各個指標有一定提升.

圖2 特征權重比較Fig.2 Comparison of feature weights

為了比較數據處理階段的BSL-FS 算法的性能，分類器均使用RF，將本文算法與SMOTE-CFS 算法、SMOTE-ReliefF算法、文獻［9］中提出的SMOTE-PCA 算法在不平衡不比不同的10 個數據集上進行了對比，用柱狀圖對比了三種不同的方法在兩個指標上的少數類的平均值，更加清晰直觀，其F-measure、AUC 值分別如圖3、圖4 所示，數據集按照表1 順序進行編號分別為1-10.

表4 選取的特征信息Table 4 Selected feature information

圖3 不同數據處理在10 個數據集上F-measure 對比Fig.3 Comparison of F-measure values on 10 data sets for different data processing

圖4 不同數據處理在10 個數據集上AUC 值對比Fig.4 Comparison of AUC values on 10 data sets for different data processing

分析圖3 和圖4，數據集上的AUC 值沒有顯著地改善，但是本次實驗算法側重點在于預處理階段方法即BSL-FS的對比，所以更多關注評價指標 F-measure，7 個數據集上F-measure 都有一定的提升，在數據集Abalone9-18 上，BSL-FS算法比SMOTE-PCA 算法提升 26.3%，比 SMOTE-CFS 算法提升了21.7%，比SMOTE-ReliefF 算法提升了9.9%，因為主成分分析法按照各個特征的貢獻率取一定的特征個數，因此可能會有部分重要信息的丟失.

進一步驗證BSL-FSRF 算法的有效性與通用性，預處理階段均選用 BSL-FS 進行處理，分別選取J48，Naive Bayes，Adaboost 分類器進行研究，并優化隨機森林參數決策樹數量k'和候選分裂屬性數mtry兩個參數，尋優過程以abalone9-18數據集和對k'的優化為例.因為隨機森林算法在默認參數下能取得較好的分類效果，其它參數均保持一致，用袋外數據進行分類誤差估計，在100 附近先進行大步長搜索，范圍設置為［0，200］，步長為20，經過搜索，在決策樹數量為60 時最優，范圍縮小至［40，80］，步長縮小到 5，依舊為 60 最優，［55，65］，步長設為1，搜索后當數量為63 時最優.實驗結果kappa值以及少數類的F-measure、AUC 值，如表6 所示，圖5 給出了四種算法在所選取的6 組數據集(Ionosphere、abalone9-18、yeast6、Vehicle0、cleveland-0_vs_4、pima)上的 ROC 曲線圖.

表5 不同方法的 kappa 系數 F-measure、AUC 值比較Table 5 Comparison of kappa coefficient F-measure and AUC values of different methods

分析實驗結果，BSL-FSRF 算法對在三個評價指標上有一定提升，取得最優次數最多且均值最高.從表6 看出相較于J48 決策樹與樸素貝葉斯算法，集成方法有一定的優勢，Ada boost 僅次于RF，相較取得較好效果的BSL-FSAdaboost 算法，在 Kappa 系數上提高了 1.5 個百分點，F-measure 提高了0.9 個百分點，AUC 提高了 1.0 個百分點，RF 比 Adaboost 算法在pima 數據集上提升效果更明顯.另外，對比表5 與表6中BSL-FSRF 算法三列可以看出，經過改進的Gridsearch 參數尋優選定合適參數后分類器性能有一定提升.

圖5 不同分類器在6 個不同數據集上的ROC 曲線對比Fig.5 Comparison of ROC curves of different classifiers on 6 different data sets

將 SMOTEBoost，SMOTEBagging，RUSBagging 相關算法與BSL-FSRF 算法進行對比，結果如圖7-圖9 所示.分析可知，BSL-FSRF 算法在8 個數據集上表現良好，因為BSL 采樣算法限定了邊界且刪除了部分重疊樣本，改善了SMOTE 算法容易產生模糊邊界的問題;其次是RUSBagging算法，相較于 SMOTEBagging 算法，RUSBagging 算法結合了 SMOTE 與RUS-Sampling 采樣算法，進一步驗證了結合過采樣與欠采樣算法的有效性.

表6 不同分類方法下AUC、kappa 系數、F-measure 比較Table 6 Comparison of AUC，kappa coefficient and F-measure under different classification methods

從10 個二分類數據集的實驗結果對比可以看出，相對于文中的其他方法，BSL-FSRF 算法可以較好地解決數據失衡問題，對不均衡數據分類的各個指標都有一定的提高，整體上算法性能較優.

5 結束語

本文從特征選擇與重采樣方法出發提出了一種BSL-FS-RF 算法.該算法:1)提出BSL-Sampling 算法進行數據均衡化重采樣;2)刪除幾乎沒有相關性的噪聲數據，然后人工插入數據，在一定程度上提高了不平衡數據集的分類性能;3)引入“假設間隔”思想，對數據集各個維度特征進行度量，通過設定合適的閾值，移除與類別相關性較小的特征，通過去除冗余達到降維的目的，克服了原始數據中噪聲數據可能會引起數據分布改變的不足，為維度較高的二分類問題提出了解決思路，并可擴展到多分類;4)以集成算法隨機森林作為分類器，并進行Gridsearch 參數尋優，改進尋優方式，節省了運行時間，相較于傳統網格搜索算法，當數據維數越多，節省時間越多，優化后的參數能一定程度上提高隨機森林的分類性能.從實驗結果可以看出，BSL-FSRF 算法適用于大多數不均衡數據集，但是不適用于每一個數據集，本文的算法從特征選擇與采樣方法進行的研究，進一步優化采樣方法增強決策邊界可作為今后研究的切入點.

圖7 10 個數據集上的Kappa 系數對比Fig.7 Comparison of Kappa coefficients on 10 data sets

圖8 10 個數據集上的F-measure 值對比Fig.8 Comparison of F-measure values on 10 data sets

圖9 10 個數據集上的AUC 對比Fig.9 Comparison of AUC values on 10 data sets