張忠林，曹婷婷

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

1 引 言

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

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

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

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

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

2 算 法

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

2.1 BSL 采樣

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

算法 1.BSL-Sampling

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

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

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

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

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

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

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

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

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

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

Step 5.合成的少數(shù)類樣本與原始訓練樣本T 合并，構(gòu)成新的訓練樣本T'1.

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

2.2 BSL-FSRF 算法

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

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

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

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

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

算法 2.BSL-FSRF

輸入:樣本訓練集D，抽樣次數(shù)t，特征權(quán)重閾值σ.

輸出:參數(shù)調(diào)優(yōu)后隨機森林分類器模型，以及分類結(jié)果.

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

Step 2.對訓練集T″1用ReliefF 特征選擇算法，利用公式(3)賦予所有和類別相關(guān)性高的特征較高的權(quán)重，更新并得到新的數(shù)據(jù)集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 采樣，有放回地為每棵樹構(gòu)造訓練集，大小為N.在每個節(jié)點處隨機選擇m 個特征，根據(jù)最小Gini 指數(shù)，比較并選擇佳特征，劃分數(shù)據(jù)集;

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

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

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

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

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

Step 9.返回參數(shù)調(diào)優(yōu)后隨機森林分類器模型以及分類結(jié)果.

Step 10.在測試集中T2中，測試調(diào)優(yōu)模型的分類效果，并進行評價.

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

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

3 評價指標

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

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

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

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

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

4 實驗及結(jié)果分析

4.1 數(shù)據(jù)集

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

表2 二分類不平衡數(shù)據(jù)集Table 2 Two-class unbalanced data sets

4.2 實驗及結(jié)果分析

4.2.1 實驗設(shè)計思路

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

1)進行基礎(chǔ)實驗的驗證.

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

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

4)與其他相關(guān)算法的對比.

經(jīng)過整體實驗對比分析，證明本文所提出的BSL-FSRF算法在不均衡數(shù)據(jù)分類問題上體現(xiàn)出一定的優(yōu)勢.

4.2.2 參數(shù)設(shè)置

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

4.2.3 實驗結(jié)果分析

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

表3 BSL-Sampling 前后數(shù)據(jù)分布Table 3 Data distribution before and after BSL-Sampling

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

圖2 特征權(quán)重比較Fig.2 Comparison of feature weights

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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

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

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