董明剛，劉 明，敬 超+

1.桂林理工大學信息科學與工程學院，廣西桂林 541004

2.廣西嵌入式技術與智能系統(tǒng)重點實驗室，廣西桂林 541004

1 引言

近年來，多類不平衡問題引起了學術界和工業(yè)界的廣泛關注，如癌癥檢測、故障檢查等。多類不平衡問題指的是個別類（小類）的樣本數(shù)量比其他類（大類）要少得多，并且小類更加重要，這對于傳統(tǒng)分類算法來說是一個巨大的挑戰(zhàn)[1-2]；因為傳統(tǒng)分類算法都是針對平衡數(shù)據(jù)集或以誤判代價相等為前提的，因此它往往偏向于大類，這就導致了算法整體分類效果的下降[3]。

多類不平衡學習問題主要有兩大類解決方法[1-2]：（1）算法級，例如代價敏感學習算法[3]、集成學習算法[4]；（2）數(shù)據(jù)級，例如欠采樣算法[5]（減少大類樣本的數(shù)量）、過采樣算法[6-14]（增加小類樣本的數(shù)量）。盡管欠采樣和過采樣方法對解決多類不平衡問題都具有較好的效果，但欠采樣方法在刪除樣本時可能會損失重要的樣本信息，而過采樣算法不會遇到這種問題[9]。

2002年，Chawla等提出了合成少數(shù)過采樣技術[6]（synthetic minority oversampling technique,SMOTE）算法，通過在小類樣本點和同類近鄰之間合成樣本點來生成平衡數(shù)據(jù)集，取得了較好的效果，但它沒有對小類樣本點進行區(qū)分性選擇，從而會出現(xiàn)過度泛化和加重類別邊界的重疊等問題。針對上述不足，學者們提出了大量的改進算法。自適應合成過采樣[7]（adaptive synthetic sampling，ADASYN）通過學習難度來自適應決定合成樣本點的數(shù)量，從而避免出現(xiàn)過度泛化問題。Han等提出的邊界線合成少數(shù)過采樣技術[8]（borderline synthetic minority over-sampling technique，BSMOTE）只著重于決策邊界的小類樣本點，其他小類樣本點不合成樣本點。嚴遠亭等提出了一種構造性覆蓋算法的SMOTE過采樣方法[9]，認為被孤立的少數(shù)類樣本點也很重要，提出了基于覆蓋內樣本點個數(shù)與基于覆蓋密度這兩種選擇關鍵樣本的方法來有效地選取典型的少數(shù)類樣本點進行過采樣，從而有效地防止過度泛化。黃海松等提出了一種基于樣本特性的新型過采樣方式[10]，它綜合考慮了數(shù)據(jù)集中不同類別的類內距離、類間距離與不平衡度之間的關系，對數(shù)據(jù)集進行距離帶劃分，可以很好地區(qū)分開不同類別，從而有效地防止了類別重疊問題。很多研究也將選擇權重與過采樣算法相結合，Barua等在2014年提出了大類加權小類過采樣技術[11]（majority weighted minority oversampling technique,MWMOTE），該算法根據(jù)學習難度來計算權重，并且只在同一個聚類簇的范圍內生成新的樣本點，可以有效地避免邊界重疊問題。Zhu等提出的多類不平衡過采樣[12]（synthetic minority oversampling for multiclass，SMOM）技術則是考慮到了過度泛化問題，首先利用聚類方法對樣本點進行劃分，再計算每個鄰域方向的權重，從而避免了過度泛化。

綜上所述，盡管在多類不平衡學習上已經(jīng)取得了大量的優(yōu)異成果，但過度泛化問題和多類不平衡問題中更嚴重的類別重疊問題仍然沒有得到很好的解決，總體的分類性能還是稍顯不足，因此本文提出了一種利用采樣安全系數(shù)的多類不平衡過采樣（sampling safety coefficient for multi-class imbalance oversampling，SSCMIO）算法。首先利用樣本點的局部特性，本文提出了近鄰采樣安全系數(shù)，為那些會產(chǎn)生過度泛化的鄰域方向分配較小的選擇權重，選擇那些較為安全的鄰域方向合成樣本點，從而避免過度泛化?？紤]到多類不平衡問題更加嚴重的類別重疊問題，本文提出了反向近鄰采樣安全系數(shù)，為那些異常的樣本點分配一個較小的選擇權重，從而避免合成樣本點侵入到其他類別區(qū)域，減輕多類不平衡數(shù)據(jù)集中更為嚴重的類別重疊問題。最后將SSCMIO算法與7種典型的過采樣算法對來自KEEL[15]和UCI[16]機器學習數(shù)據(jù)庫上的16個數(shù)據(jù)集進行了預處理，使用基于C4.5決策樹的RIPPER[17]分類器進行分類，結果表明經(jīng)過SSCMIO算法預處理過的數(shù)據(jù)集有更好的分類效果。

2 基于選擇權重的過采樣算法

2.1 MWMOTE算法

MWMOTE[11]算法主要是考慮到某些小類樣本點難以學習和類別邊界重疊問題，首先它重新定義了邊界點，將邊界點作為難以學習的小類樣本點，再與聚類方法結合。算法的主要描述如下：

（1）首先找出大類的邊界點，再根據(jù)大類邊界點定義出小類的邊界點，這些小類的邊界點就是難以學習的小類樣本點。

（2）根據(jù)密度因子和靠近因子每個樣本點計算選擇權重，詳細信息參見文獻[11]。

（3）根據(jù)選擇權重在同一個聚類簇的范圍內合成新的樣本點。

2.2 自適應半監(jiān)督加權過采樣算法

Nekooeimehr等在2016年提出了自適應半監(jiān)督加權過采樣[13]（adaptive semi-unsupervised weighted oversampling，A-SUWO）算法。首先，為了防止過度重疊，該算法使用半監(jiān)督聚類算法對小類樣本點進行聚類，為同一簇內的樣本點計算選擇權重，并且在聚類過程中對小類樣本的簇邊界進行嚴格限制，從而避免重疊樣本的產(chǎn)生。同時對原始的數(shù)據(jù)集先進行一次分類，根據(jù)分類錯誤率和混淆矩陣來自適應確定每個樣本點所需要的合成樣本點數(shù)量。在合成樣本點的時候，只有在同一簇內的小類樣本點才能合成樣本點，減少合成樣本點侵入到其他類區(qū)域，降低了生成重疊樣本的機會。

2.3 SMOM算法

SMOM[12]算法是Zhu等在2017年提出來的，與SMOTE算法的隨機合成新的樣本點不同，SMOM將選擇權重分配給每個鄰域方向，對于可以產(chǎn)生過度泛化的鄰域方向賦予較小的選擇權重，從而避免過度泛化。算法主要描述如下：

（1）使用聚類算法將小類樣本點劃分為優(yōu)秀樣本點和被困樣本點。

（2）對于每個被困樣本點，根據(jù)過度泛化因子和復雜因子來計算其選擇權重，對于那些優(yōu)秀樣本點則賦予一個定值權重，詳細信息參見文獻[12]。

（3）若樣本點為被困樣本點，則根據(jù)選擇權重來選擇近鄰，運用式（1）來合成樣本點，否則隨機選擇近鄰，運用式（1）來合成樣本點。

其中，Xnew表示新合成的樣本點，X和Xneighbor分別表示某一樣本點和它的任意一個近鄰，rand為隨機函數(shù)，可以產(chǎn)生一個[0,1]之間的隨機數(shù)。

3 利用采樣安全系數(shù)的多類不平衡過采樣算法

如今多類不平衡問題已經(jīng)引起了廣泛的關注，但現(xiàn)有的過采樣算法有可能會導致過度泛化問題，使得算法整體的分類性能下降[12]。并且多類不平衡問題相較于兩類不平衡問題擁有更加復雜的類別邊界，從而導致了不同類別之間會出現(xiàn)更加嚴重的類別重疊現(xiàn)象，增加了分類難度。針對以上兩個問題，本文提出了利用采樣安全系數(shù)的多類不平衡過采樣算法。首先為了防止過度泛化，提出了近鄰采樣安全系數(shù)，為那些過度泛化的鄰域分配一個較小的選擇權重，然后運用反向近鄰采樣安全系數(shù)來防止合成樣本點侵入到其他類別區(qū)域，從而降低了類的識別難度，提升了算法的整體性能。

3.1 近鄰采樣安全系數(shù)

現(xiàn)有的過采樣方法在處理多類不平衡這一更具挑戰(zhàn)性的問題時，往往會導致過度泛化。考慮到數(shù)據(jù)集中的每個樣本點的近鄰對分類結果的貢獻都不同，這意味著一些近鄰更重要，對分類結果影響更大，故本文提出了近鄰采樣安全系數(shù)，它考慮了樣本點的局部特性，為那些會產(chǎn)生過度泛化的鄰域方向分配較小的選擇權重，選擇那些較為安全的鄰域方向合成樣本點，從而避免過度泛化，提升算法的整體性能。

如圖1所示，以二維數(shù)據(jù)為例，圖中有3類數(shù)據(jù)，圓形樣本點表示當前需要過采樣的小類，其他為大類。小類中任意樣本點Xi的k1個近鄰分布在虛線圓內，虛線圓被相互垂直的兩條實線分成了A、B、C、D四部分。將Xi點的右上區(qū)域按圖中的垂直虛線分為3個區(qū)域A1、A2、A3。由于SMOTE方法是在樣本點Xi和其近鄰Yj之間隨機合成樣本點，由圖可知，在區(qū)域A2和A3內存在其他類別樣本點對合成樣本點的影響遠比區(qū)域A1要小得多，故選定區(qū)域A1作為鄰域。在區(qū)域D中樣本點Xn，鄰域內其他類別的樣本點相對而言較少，分配較高的選擇權重，并且為其他鄰域方向分配一個較小的權重，可以很好地避免過度泛化問題，提高了算法的總體分類性能。

Fig.1 Neighbor sampling safety coefficient圖1 近鄰采樣安全系數(shù)

近鄰安全系數(shù)很好地反映了樣本點的局部特性，用來衡量樣本點Xi和其近鄰Yj之間的泛化程度，對于那些會產(chǎn)生嚴重過度泛化的鄰域方向分配較小的選擇權重，從而提升合成樣本點的質量，降低類的識別難度。它可以表示為：

其中，MaxNumc表示Xc內其他類別樣本點的最大數(shù)量，Num(Xi,Yj)表示Xj i鄰域內其他類別樣本點的數(shù)量，NeiSafe(Xi,Yj)表示樣本點Xi和其第j個近鄰Yj之間的采樣安全系數(shù)。

近鄰采樣安全系數(shù)的偽代碼如算法1所示。

算法1近鄰采樣安全系數(shù)

3.2 反向近鄰采樣安全系數(shù)

相較于兩類不平衡問題，多類不平衡問題中不同類別之間重疊現(xiàn)象更加嚴重，類別邊界更加模糊?？紤]到不同類別之間的重疊問題，防止合成樣本點侵入到其他類別區(qū)域，故采用了反向近鄰采樣安全系數(shù)，從而避免合成侵入到其他類別區(qū)域的樣本點。它的定義如下：

其中，max、mean分別表示最大值函數(shù)和平均值函數(shù)；RN表示同一類別所有樣本的反向近鄰數(shù)量的集合；NeiSafe表示樣本點的反向近鄰與該樣本點的近鄰安全系數(shù)的集合。

反向近鄰安全系數(shù)很好地反映了樣本點的全局特性，若樣本點的反向近鄰安全系數(shù)很小，那么該樣本點很可能是潛在的異常樣本點，并且侵入了其他類別區(qū)域，因此為此類樣本點分配一個較小的權重，可以很好地減輕多類不平衡中更嚴重的類別重疊問題，提高了類的識別度。如圖2所示，給出了小類樣本點X1、X2、X3和X4的近鄰虛線圓，由圖可知樣本點X1的反向近鄰有X2、X3和X4，其反向近鄰采樣安全系數(shù)很小，故該樣本點是異常的樣本點，存在于重疊的邊界區(qū)域，若對其合成大量樣本就會加重類別重疊問題，使得分類性能大大降低，故采用反向近鄰采樣安全系數(shù)為此類樣本點分配一個較小的選擇權重，減輕類別重疊問題。

Fig.2 Reverse neighbor sampling safety coefficient圖2 反向近鄰采樣安全系數(shù)

反向近鄰采樣安全系數(shù)的偽代碼如算法2所示。

算法2反向近鄰采樣安全系數(shù)

3.3 SSCMIO算法主框架

采樣安全系數(shù)決定應該選擇哪些樣本點來合成樣本點。更高的安全系數(shù)意味著其合成樣本點不會導致過度泛化，也能避免侵入到其他類別區(qū)域，減輕類別重疊，提升了合成樣本點的質量，因此將這些合成樣本添加到數(shù)據(jù)集中可以獲得更高的分類精度。采樣安全系數(shù)的定義如下：

SSCMIO算法主框架偽代碼如算法3所示。首先為了防止過度泛化，利用樣本點的局部特性，采用近鄰采樣安全系數(shù)為小類樣本點的每個鄰域分配選擇權重，并且若該近鄰采樣安全系數(shù)為0，則不在該鄰域內合成樣本點；考慮到不同類別之間的重疊問題，利用樣本點的全局特性，計算出樣本點的反向近鄰采樣安全系數(shù)，從而避免合成的樣本點侵入到其他類別區(qū)域，利用式（4）為每個樣本點分配采樣安全系數(shù)。

算法3SSCMIO算法主框架

3.4 時間復雜度分析

假定數(shù)據(jù)集中的第c個小類數(shù)量為Nc，設所有的小類點的數(shù)量為n，即n=，計算一個樣本點的近鄰采樣安全系數(shù)和反向近鄰采樣安全系數(shù)的時間復雜度均為O(logn+k1)，其中k1為計算安全系數(shù)時的近鄰和反向近鄰數(shù)量，O(logn)為計算一個樣本點的k1個近鄰的時間復雜度，且k1遠小于n，故SSCMIO算法時間復雜度為O(nlogn)。

4 仿真實驗

4.1 實驗設置與數(shù)據(jù)集

本文是在Windows 8系統(tǒng)下實現(xiàn)的，使用了WEKA平臺[18]中基于C4.5決策樹的RIPPER分類器[17]進行分類，分類器參數(shù)使用了WEKA平臺下算法的默認值，并且采用5折交叉驗證，獨立運行10次，取平均值作為最終結果。對比算法有SMOTE[6]、ADASYN[7]、BSMOTE[8]，基于分類超平面的混合采樣算法（hybrid sampling algorithm based on support vector machine，SVM_HS）[19]、MWMOTE[11]、SMOM[12]、ASUWO[13]，這些算法的參數(shù)均采用算法的默認參數(shù)，經(jīng)過實驗對比，發(fā)現(xiàn)算法中的k1取值為4可以取得最好的性能，具體的實驗對比見4.4節(jié)。

為了驗證算法的有效性，本文采用了來自KEEL[15]和UCI[16]機器學習數(shù)據(jù)庫的16個數(shù)據(jù)集進行驗證，將過采樣后得到的平衡數(shù)據(jù)集用基于C4.5決策樹的RIPPER[17]分類器進行分類，文中的數(shù)據(jù)集在不平衡率（imbalance rate，IR）大于1.45時判定為小類，IR為最大類與最小類的數(shù)量比值，數(shù)據(jù)集的基本信息如表1所示。

Table 1 Basic information of datasets表1 數(shù)據(jù)集的基本信息

4.2 性能評價指標

采用多類不平衡數(shù)據(jù)集中常用的Precision[1,20-21]、Recall[1,20-21]、F-measure[22]、MG[23]、MAUC[24]這5個指標來評價算法的優(yōu)劣性。其定義如式（5）～式（9）所示：

其中，TP表示正類樣本預測為正類的數(shù)量；FN表示正類樣本預測為負類的數(shù)量；FP表示負類樣本預測為正類的數(shù)量；β一般設置為1；A(ci,cj)=表示類i和類j的AUC面積，且A(ci|cj)與A(cj|ci)不相等。

Precision、Recall和F-measure僅計算最小的類，其中MG和MAUC分別是在二類評價指標G-mean[25]和AUC[26-27]（area under ROC curve）的基礎上擴展的多類不平衡學習的評價指標，可以很好地評價算法的整體性能[20]。

4.3 實驗結果對比與分析

Table 2 Comparison of Precision表2 Precision 的對比

表2到表6給出了SSCMIO算法和其他7種算法在16個數(shù)據(jù)集上的5種評價指標對比結果，加粗表示當前數(shù)據(jù)集的最優(yōu)值。

Table 3 Comparison of Recall表3 Recall的對比

Table 4 Comparison of F-measure表4 F-measure的對比

表2展示了8個算法在評價指標Precision上的結果，從表中可以看出在16個數(shù)據(jù)集中，SSCMIO算法取得了11個最優(yōu)值，相比于SMOTE、BSMOTE、SVM_HS、ADASYN、MWMOTE、SMOM、A-SUWO平均提升了0.066 5、0.030 4、0.108 6、0.059 8、0.069 2、0.091 2、0.025 5，16個數(shù)據(jù)集中相比表現(xiàn)最差的算法提升最多的是voice96，提升了0.481 8。

表3展示了8個算法在評價指標Recall上的結果，從表中可以看出在16個數(shù)據(jù)集中，SSCMIO算法取得了11個最優(yōu)值，相比于SMOTE、BSMOTE、SVM_HS、ADASYN、MWMOTE、SMOM、A-SUWO平均提升了0.085 8、0.044 6、0.008 4、0.101 2、0.123 3、0.125 3、0.073 9，16個數(shù)據(jù)集中相比表現(xiàn)最差的算法提升最多的是voice9，提升了0.305 3。

Table 5 Comparison of MG表5 MG 的對比

Table 6 Comparison of MAUC表6 MAUC 的對比

表4展示了8個算法在評價指標F-measure上的結果，從表中可以看出在16個數(shù)據(jù)集中，SSCMIO算法取得了11個最優(yōu)值，相比于SMOTE、BSMOTE、SVM_HS、ADASYN、MWMOTE、SMOM、A-SUWO平均提升了0.080 9、0.038 8、0.057 0、0.087 4、0.104 6、0.116 0、0.056 0，16個數(shù)據(jù)集中相比表現(xiàn)最差的算法提升最多的是voice96，提升了0.342 0。

Fig.3 Comparison of k1 value圖3 k1值對比

表5展示了8個算法在評價指標MG上的結果，從表中可以看出在16個數(shù)據(jù)集中，SSCMIO算法取得了11個最優(yōu)值，其中數(shù)據(jù)集ERA有個別類別被全部分錯，故MG值均為0。相比于SMOTE、BSMOTE、SVM_HS、ADASYN、MWMOTE、SMOM、A-SUWO平均提升了0.096 4、0.054 5、0.073 3、0.098 8、0.113 1、0.101 2、0.070 9，16個數(shù)據(jù)集中相比表現(xiàn)最差的算法提升最多的是voice96，提升了0.266 4。

表6展示了8個算法在評價指標MAUC上的結果，從表中可以看出在16個數(shù)據(jù)集中，SSCMIO算法取得了12個最優(yōu)值，相比于SMOTE、BSMOTE、SVM_HS、ADASYN、MWMOTE、SMOM、A-SUWO平均提升了0.038 8、0.024 0、0.056 2、0.042 6、0.045 4、0.042 6、0.029 6，16個數(shù)據(jù)集中相比表現(xiàn)最差的算法提升最多的是ERA，提升了0.130 7。

表2到表6的實驗結果可以表明SSCMIO算法的有效性，這是因為SSCMIO算法考慮了樣本點的局部特性，為樣本點的每一個鄰域計算選擇權重，從而有效避免了過度泛化；再從全局特性出發(fā)，采用反向近鄰安全系數(shù)減少了噪聲和離群點的影響，也減輕了類別邊界的重疊問題，使得合成的樣本點更加合理，降低了分類器的分類難度，從而提升了算法的總體性能。

4.4 參數(shù)值的討論

如圖3所示，本文給出了SSCMIO算法在k1取不同值時的折線圖，圖中縱坐標分別表示在16個數(shù)據(jù)集上的MG和MAUC這兩個指標上的百分比之和，橫坐標表示不同的k1值。MG和MAUC均是由二類評價指標拓展而來，能夠很好地描述算法的總體性能。從圖中可以看出當k1取值為4時，SSCMIO算法的效果是最佳的。相比k1的其他取值，在MG上，16個數(shù)據(jù)集總的最大提升為0.413 0，在MAUC上的最大提升為0.071 7，故本文將k1的值設置為4。

5 結束語

本文提出了一種利用采樣安全系數(shù)的多類不平衡過采樣算法（SSCMIO）來處理多類不平衡問題。首先為了防止過度泛化，充分利用樣本點的局部特性，提出了近鄰采樣安全系數(shù)；然后利用樣本點的全局特性，提出了反向近鄰采樣安全系數(shù)，防止合成樣本點侵入到其他類別區(qū)域，很好地減輕了不同類別之間的重疊問題。將SSCMIO算法與7種典型的過采樣算法在16種不同平衡度的真實數(shù)據(jù)集上進行了對比實驗，實驗結果表明在大多數(shù)的數(shù)據(jù)集上SSCMIO算法表現(xiàn)得更優(yōu)。

下一步工作將從以下兩方面開展：（1）用于實驗的數(shù)據(jù)集都是數(shù)值型的，未來將研究SSCMIO算法應用到非數(shù)值型數(shù)據(jù)集和混合型數(shù)據(jù)集；（2）可以研究如何將采樣安全系數(shù)和聚類方法相結合，以便更好地防止過度泛化和重疊問題。