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

董明剛，劉 明，敬 超+

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

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

1 引言

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

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

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

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

2 基于選擇權(quán)重的過采樣算法

2.1 MWMOTE算法

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

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

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

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

2.2 自適應(yīng)半監(jiān)督加權(quán)過采樣算法

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

2.3 SMOM算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 SSCMIO算法主框架

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

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

算法3SSCMIO算法主框架

3.4 時間復(fù)雜度分析

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

4 仿真實驗

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

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

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

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

4.2 性能評價指標(biāo)

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

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

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

4.3 實驗結(jié)果對比與分析

Table 2 Comparison of Precision表2 Precision 的對比

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

Table 3 Comparison of Recall表3 Recall的對比

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

表2展示了8個算法在評價指標(biāo)Precision上的結(jié)果，從表中可以看出在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個算法在評價指標(biāo)Recall上的結(jié)果，從表中可以看出在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個算法在評價指標(biāo)F-measure上的結(jié)果，從表中可以看出在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個算法在評價指標(biāo)MG上的結(jié)果，從表中可以看出在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個算法在評價指標(biāo)MAUC上的結(jié)果，從表中可以看出在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的實驗結(jié)果可以表明SSCMIO算法的有效性，這是因為SSCMIO算法考慮了樣本點的局部特性，為樣本點的每一個鄰域計算選擇權(quán)重，從而有效避免了過度泛化；再從全局特性出發(fā)，采用反向近鄰安全系數(shù)減少了噪聲和離群點的影響，也減輕了類別邊界的重疊問題，使得合成的樣本點更加合理，降低了分類器的分類難度，從而提升了算法的總體性能。

4.4 參數(shù)值的討論

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

5 結(jié)束語

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

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