改進(jìn)SMOTE的過采樣算法

覃 琴， 楊 悅， 陳名松,3， 王 鑫,

(1.桂林電子科技大學(xué) 計(jì)算機(jī)與信息安全學(xué)院,廣西 桂林 541004；2.桂林電子科技大學(xué) 北海校區(qū),廣西 北海 536000；3.桂林電子科技大學(xué) 信息與通信學(xué)院,廣西 桂林 541004)

不平衡樣本數(shù)據(jù)集是指數(shù)據(jù)集中某些類包含比其他類更多樣本數(shù)的數(shù)據(jù)集[1]。在二分類問題中，通常將樣本數(shù)較少的一類稱為少數(shù)類，樣本數(shù)較多的一類稱為多數(shù)類[2]。在現(xiàn)實(shí)生活中有很多不平衡數(shù)據(jù)的分類應(yīng)用場景，如信用卡欺詐檢測[3]、醫(yī)療診斷[4]、網(wǎng)絡(luò)攻擊識別[5]等場景。采用傳統(tǒng)分類算法對不平衡數(shù)據(jù)進(jìn)行分類，分類結(jié)果會傾向于多數(shù)類，出現(xiàn)分類失誤的情況[6]。這種存在于兩類之間樣本量的不平衡稱為類間不平衡，而另一種導(dǎo)致分類失誤的不平衡是類內(nèi)不平衡[7]，指的是某類樣本空間內(nèi)部數(shù)據(jù)分布密度的不均衡，即形成了多個(gè)具有相同類別、不同數(shù)據(jù)分布的子類[8]。另外，過采樣方法中存在合成樣本重疊[9]以及樣本分布“邊緣化”[10]問題也是分類性能下降的原因。

對不平衡數(shù)據(jù)分類問題主要從數(shù)據(jù)處理和分類算法2個(gè)方面進(jìn)行研究。分類算法的代表性算法有代價(jià)敏感學(xué)習(xí)和集成學(xué)習(xí)；數(shù)據(jù)處理最常見的方法為過采樣和欠采樣,分別通過增加少數(shù)類樣本數(shù)和減少多數(shù)類樣本數(shù)來平衡兩類的樣本數(shù)。相比之下，基于數(shù)據(jù)層面的采樣方法簡單、直觀，但其中欠采樣方法一般會造成信息丟失，而過采樣方法則使原數(shù)據(jù)集趨于平衡，因此在數(shù)據(jù)分類領(lǐng)域，通常采用過采樣方法。

目前最常用的過采樣方法是Chawla等[11]在2002年提出的SMOTE算法，算法思路是通過尋找樣本的近鄰集，在樣本點(diǎn)與其近鄰集隨機(jī)選擇的樣本連線上合成新的樣本點(diǎn)。Han等[12]在2005年提出了Borderline-SMOTE算法，該算法將少數(shù)類樣本分為邊界區(qū)域、安全區(qū)域、危險(xiǎn)區(qū)域，通過選擇邊界區(qū)域的樣本點(diǎn)進(jìn)行樣本合成，避免了SMOTE不加區(qū)別地選擇少數(shù)類樣本而導(dǎo)致大量的冗余新樣本的合成。He等[13]提出了ADASYN合成，根據(jù)數(shù)據(jù)分布自動確定每個(gè)少數(shù)類樣本需要生成的樣本數(shù)，近鄰多數(shù)類樣本多的少數(shù)類樣本生成更多的樣本，相比于SMOTE，對樣本分布進(jìn)行了細(xì)致劃分。Cluster-SMOTE[14]利用K-means算法對少數(shù)類樣本進(jìn)行聚類，找到少數(shù)類簇，然后分別應(yīng)用SMOTE算法，但該方法未確定最佳類簇個(gè)數(shù)，且未計(jì)算出每類簇該生成的樣本數(shù)。Kmeans-SMOTE[15]將K-means聚類算法與SMOTE算法相結(jié)合，相比Cluster-SMOTE，Kmeans-SMOTE對整個(gè)數(shù)據(jù)集進(jìn)行聚類，發(fā)現(xiàn)重疊的類區(qū)域且避免在不安全區(qū)域中進(jìn)行過采樣，并將合成樣本限制在目標(biāo)區(qū)域內(nèi)，消除了類間和類內(nèi)不平衡，同時(shí)避免了產(chǎn)生噪音樣本，效果較好。CBSO[16]將聚類與現(xiàn)有的合成過采樣技術(shù)的數(shù)據(jù)生成機(jī)制相結(jié)合，確保生成的合成樣本始終位于少數(shù)類區(qū)域，避免了錯(cuò)誤樣本的生成。上述的過采樣方法在一定程度上提高了分類精度，但仍存在以下不足：1)過采樣時(shí)更多地解決類間的不平衡，而未充分考慮類內(nèi)的不平衡。2)雖然通過聚類可以較好地解決類間和類內(nèi)不平衡，但在聚類過程中也加劇了兩類樣本的混疊，導(dǎo)致合成新樣本產(chǎn)生重疊樣本。傳統(tǒng)k-means聚類算法聚類時(shí)需要設(shè)置k值，算法對于球形數(shù)據(jù)集比較有效且算法復(fù)雜度較高。3)少數(shù)類邊界未最大化，影響樣本的合成質(zhì)量。4)對合成樣本不加限制目的區(qū)域，造成合成樣本分布“邊緣化”。5)存在噪聲樣本干擾問題。鑒于此，提出一種改進(jìn)的過采樣算法AGNES-SMOTE。

1 預(yù)備理論

1.1 SMOTE算法

SMOTE基本思想是通過人工合成新樣本，以平衡原始數(shù)據(jù)中的類別失衡。SMOTE算法的步驟如下：

1)根據(jù)歐式距離計(jì)算兩兩樣本之間的距離，對少數(shù)類數(shù)據(jù)中的每個(gè)數(shù)據(jù)樣本X使用KNN算法，搜索它的K個(gè)最近鄰樣本。

2)對每個(gè)原始樣本，隨機(jī)選擇其K個(gè)近鄰樣本中的N個(gè)樣本，在原始樣本數(shù)據(jù)與它的近鄰樣本之間進(jìn)行插值操作:

xns=x+rand×(y(i)-x)，

(1)

其中：i=1,2,…,N；xns為新插值的樣本；x為選擇的原始樣本數(shù)據(jù)；rand為0到1之間的隨機(jī)數(shù);y(i)為原始樣本數(shù)據(jù)x的最近鄰K個(gè)樣本中選取的N個(gè)樣本。

3)在原始訓(xùn)練數(shù)據(jù)中加入所有生成的新樣本，降低訓(xùn)練數(shù)據(jù)集的不平衡度。

2 AGNES-SMOTE算法

2.1 劃分少數(shù)類簇

AGNES-SMOTE算法首先做噪音樣本處理，再采用AGNES算法對樣本進(jìn)行聚類，將數(shù)據(jù)集劃分成類簇。AGNES是一種層次聚類算法，該算法將每個(gè)樣本點(diǎn)看作一個(gè)類簇，然后將這些簇根據(jù)某種規(guī)則進(jìn)行合并，直到達(dá)到預(yù)設(shè)類簇個(gè)數(shù)或設(shè)定的閾值。與傳統(tǒng)質(zhì)心方式聚合樣本點(diǎn)的方法相比，AGNES算法可以不受樣本點(diǎn)周圍分布的形狀限制，同時(shí)可以將特征空間范圍不同的樣本點(diǎn)聚合到一起，更好地解決類內(nèi)不平衡問題。在確定類簇是否合并時(shí)，采用平均距離計(jì)算方法，直到類簇間距離超過設(shè)定的閾值，停止聚類。為了避免重疊樣本的生成，還需要考慮多數(shù)類樣本的分布。采用AGNES算法先對多數(shù)類樣本進(jìn)行聚類，再根據(jù)獲得的多數(shù)類簇對少數(shù)類樣本進(jìn)行聚類。若某一多數(shù)類簇到兩少數(shù)類簇的距離小于兩少數(shù)類簇的最小距離，則表明合并后的少數(shù)類簇合成樣本時(shí)會產(chǎn)生重疊樣本，不應(yīng)該將兩類簇進(jìn)行合并。劃分少數(shù)類簇的步驟如下：

1)給定原始數(shù)據(jù)集I，利用K近鄰的思想過濾數(shù)據(jù)集I中的噪聲樣本。設(shè)定K=5，遍歷I中的樣本，若I中樣本的K個(gè)近鄰中超過4/5的樣本為該選取樣本的相反樣本類別，則判定該樣本為噪聲樣本，剔除該噪聲樣本，將剩下的樣本點(diǎn)組成樣本集合I′。

(2)

其中：x和y分別為類簇Ca和Cb中的樣本點(diǎn)；|Ca|和|Cb|表示類簇中總的樣本數(shù)。

4)由式(2)計(jì)算兩兩少數(shù)簇間的距離，令Dmin=d(Ca,Cb)并記錄下其最小距離對應(yīng)的類簇編號a和b。

5)遍歷多數(shù)類簇集合，找到多數(shù)簇Ckmaj，滿足其到少數(shù)類簇Camin和Cbmin的距離均小于兩少類簇最小距離Dmin，將這些多數(shù)類簇加入集合B。

6)若B≠?，則少數(shù)類簇Camin和Cbmin不進(jìn)行合并，將最小距離Dmin設(shè)為一個(gè)較大的值，避免再次合并時(shí)被考慮，并將B中元素清空。否則，將少數(shù)類簇Camin和Cbmin合并成少數(shù)類簇Ccmin，則少數(shù)類簇集合A中將減少一個(gè)元素。

設(shè)置距離閾值Th，判斷是否做類簇合并。先定義：

(3)

Th=davgf。

(4)

參數(shù)f用于調(diào)整聚類算法的輸出。

2.2 確定采樣權(quán)重和概率分布

通過AGNES聚類獲得若干樣本數(shù)不同的少數(shù)類簇，類簇內(nèi)的密集程度也不同，需要考慮類內(nèi)不平衡對分類性能的影響。于是對所有少數(shù)類簇根據(jù)樣本數(shù)賦予不同權(quán)重，不僅可以保證所有的少數(shù)類簇都進(jìn)行過采樣，不會忽略孤立的小類簇，而且有利于避免過擬合現(xiàn)象。因此，根據(jù)少數(shù)類簇中樣本數(shù)為其分配不同的采樣權(quán)重：

(5)

其中：N為總的少數(shù)類簇?cái)?shù)，num(i)為第i個(gè)少數(shù)類簇包含的樣本數(shù)。由式(5)可知，某少數(shù)類簇中樣本數(shù)越多，在總的少數(shù)類簇中樣本數(shù)和中的占比越大，則得到的W(i)越小，即分配的權(quán)重越小，合成樣本數(shù)越小，最終實(shí)現(xiàn)同類樣本之間的平衡分布。

由各類簇的采樣權(quán)重W(i)和剔除噪聲樣本后，剩余的多數(shù)類樣本與少數(shù)類樣本的差額Nmaj-Nmin，可以確定每個(gè)少數(shù)類簇的采樣數(shù)：

num(i)=(Nmaj-Nmin)W(i)。

(6)

此外，在分類任務(wù)中，越容易被錯(cuò)分的往往是越靠近決策邊界的少數(shù)類樣本，因而增加了少數(shù)類樣本的學(xué)習(xí)難度，為此還需要篩選進(jìn)行過采樣的樣本。這里引入少數(shù)類簇的概率分布，根據(jù)概率分布挑選難以學(xué)習(xí)的包含重要信息的少數(shù)類樣本作為“種子樣本”，以保證樣本的合成質(zhì)量，每個(gè)樣本被選中的概率設(shè)置為

(7)

少數(shù)類簇的概率分布為

(8)

其中：ya為x的第a個(gè)多數(shù)類近鄰樣本，1≤a≤k；dxya為少數(shù)類子簇中樣本x與多類樣本ya的歐式距離；i為少數(shù)類簇中的某樣本；n為某少數(shù)類簇中的樣本數(shù)；k為近鄰樣本數(shù)。由式(8)可知，每個(gè)樣本被選中的概率是由該樣本與多數(shù)類邊界的距離確定，距離多數(shù)類邊界越近的少數(shù)類樣本被選擇的概率越大于距離較遠(yuǎn)的樣本，再由每個(gè)樣本被選中的概率構(gòu)成少數(shù)類簇的概率分布，這樣不僅考慮了樣本的分布特性，而且有效地?cái)U(kuò)展了少數(shù)類決策邊界。

2.3 限制合成樣本的生成區(qū)域

確定了每個(gè)少數(shù)類簇合成數(shù)，并根據(jù)各少數(shù)類簇的概率分布選取“種子樣本”，還需考慮合成樣本的生成區(qū)域，進(jìn)一步提高分類器的性能，防止合成樣本分布“邊緣化”。因此在進(jìn)行樣本合成時(shí)，需要將新生成的樣本點(diǎn)分布考慮進(jìn)去。在“種子樣本”中隨機(jī)選取一個(gè)樣本，然后從該樣本在同一少數(shù)類簇中的近鄰少數(shù)類樣本中再隨機(jī)選擇2個(gè)樣本，將這3個(gè)樣本組成一個(gè)三角形，樣本本身作為三角形的頂點(diǎn)。3個(gè)頂點(diǎn)到其質(zhì)心的連線上分別隨機(jī)生成一個(gè)樣本,一個(gè)三角形產(chǎn)生3個(gè)合成樣本，采用質(zhì)心方式來限制樣本點(diǎn)的生成區(qū)域。設(shè)置3個(gè)樣本點(diǎn)分布為x1、x2、x3。由式(9)計(jì)算出3個(gè)樣本的質(zhì)心：

(9)

其中：xi為3個(gè)頂點(diǎn)橫坐標(biāo)；yi為3個(gè)頂點(diǎn)縱坐標(biāo)。按該方式生成樣本點(diǎn)向樣本點(diǎn)質(zhì)心方向靠攏，考慮樣本點(diǎn)分布。

2.4 算法步驟

AGNES-SMOTE算法首先采用K近鄰思想對原數(shù)據(jù)集做噪音樣本剔除；然后采用AGNES算法對多數(shù)類樣本進(jìn)行聚類，劃分成若干個(gè)多數(shù)類簇；再對少數(shù)類樣本進(jìn)行聚類，并根據(jù)得到的多數(shù)類簇合并相近少數(shù)類簇，當(dāng)超出設(shè)定閾值時(shí)停止聚類，得到少數(shù)類簇。為每個(gè)少數(shù)類簇分配權(quán)重，同時(shí)計(jì)算出每個(gè)少數(shù)類簇的概率分布，結(jié)合兩者對少數(shù)類簇中的樣本進(jìn)行過采樣,合成過程中采用質(zhì)心方式對合成樣本限制生成區(qū)域。具體算法如下：

1)對原始數(shù)據(jù)集進(jìn)行噪音處理，將處理完噪音后的數(shù)據(jù)集分為多數(shù)類樣本集和少數(shù)類樣本集。采用AGNES算法對多數(shù)類樣本集進(jìn)行聚類，得到多數(shù)類簇，再對少數(shù)類樣本集聚類，聚類過程中判斷距離最近的兩少數(shù)類簇間是否有多數(shù)類樣本存在，再進(jìn)行類簇的合并。

2)計(jì)算是少數(shù)類簇中的樣本數(shù)，為少數(shù)類簇分配采樣權(quán)重，計(jì)算出需要合成的樣本數(shù)，再計(jì)算出每個(gè)少數(shù)類簇的概率分布。

3)通過每個(gè)少數(shù)類簇需要合成的樣本數(shù)和概率分布選取“種子樣本”,在所有“種子樣本”中選取一樣本，再隨機(jī)選取該樣本所在類簇的2個(gè)近鄰少數(shù)類樣本,將3個(gè)樣本組成一個(gè)三角形，在3個(gè)樣本點(diǎn)到其質(zhì)心的連線上合成新樣本，再將合成樣本添加到合成樣本集中。

3 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

3.1 評價(jià)指標(biāo)

傳統(tǒng)分類算法采用混淆矩陣[17]來進(jìn)行評價(jià)，如表1所示。

表1 混淆矩陣

分類器進(jìn)行分類采用準(zhǔn)確率(Precision)和召回率(Recall)兩個(gè)基礎(chǔ)指標(biāo)[18]，分別定義如下：

Precision=TP/(TP+FP)；

(10)

Recall=TP/(TP+FN)。

(11)

在不平衡數(shù)據(jù)的處理中，一般采用常用F-measure、G-mean和AUC這3個(gè)指標(biāo)來評價(jià)分類算法的優(yōu)劣。其中F-measure是召回率和準(zhǔn)確率的調(diào)和平均數(shù)，實(shí)驗(yàn)中將β設(shè)置為1[19]。G-mean則結(jié)合了分類器在多數(shù)類樣本和少數(shù)類樣本上準(zhǔn)確性，AUC表示ROC曲線下各部分的面積之和。F-measure和G-mean定義如下[20]：

(12)

(13)

3.2 實(shí)驗(yàn)分析

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

選取6組UCI數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，數(shù)據(jù)表結(jié)構(gòu)如表2所示。

表2 不平衡數(shù)據(jù)

3.2.2 確定參數(shù)f

將6組數(shù)據(jù)集作為測試數(shù)據(jù)集，確定參數(shù)f的范圍，如表3所示。對于f，以0.2為初始值，步長為0.2，進(jìn)行實(shí)驗(yàn)。經(jīng)過測試，分別有1組數(shù)據(jù)集在f取0.4時(shí)取得最大F-measure值，3組數(shù)據(jù)集在f取0.6時(shí)取得最大F-measure值，2組數(shù)據(jù)集在f取0.8時(shí)取得最大F-measure值，所以參數(shù)f的參考范圍為0.2～0.8。

表3 不同f值下的F-measure值

3.2.3 實(shí)驗(yàn)結(jié)果與分析

分別用SVM、KNN和邏輯回歸分類器對采樣后的數(shù)據(jù)集進(jìn)行分類，各分類器實(shí)驗(yàn)結(jié)果如表4、5、6所示。通過對比數(shù)據(jù)可得到如下結(jié)論。

表4 SVM分類器實(shí)驗(yàn)結(jié)果

表5 KNN分類器實(shí)驗(yàn)結(jié)果

表6 邏輯回歸分類器實(shí)驗(yàn)結(jié)果

1)在處理相同數(shù)據(jù)集過程中，用SVM分類器取得的分類結(jié)果優(yōu)于KNN和邏輯回歸分類器。這是因?yàn)镾VM的最終決策函數(shù)只由少數(shù)的支持向量確定，這不但可以抓住關(guān)鍵樣本、“剔除”大量冗余樣本,而且該方法既算法簡單,又具有較好的“魯棒”性。

2)用過采樣算法對數(shù)據(jù)進(jìn)行處理可以提高分類器對數(shù)據(jù)集的分類性能。將本算法與SMOTE、Kmeans-SMOTE、Cluster-SMOTE進(jìn)行對比實(shí)驗(yàn)。從實(shí)驗(yàn)結(jié)果可看出，AGNES-SMOTE算法在數(shù)據(jù)集Heart、Wine、Iris和LEV上得到的AUC值、F-measure值和G-mean值大部分優(yōu)于其他采樣算法。原因是本算法在SMOTE算法及其改進(jìn)算法存在的不足上做了改進(jìn)，在不平衡數(shù)據(jù)處理上，不僅考慮了類內(nèi)不平衡，而且對樣本加以選擇的同時(shí)限制了樣本的生成區(qū)域，減少了樣本重疊的可能，進(jìn)一步保證了樣本的合成質(zhì)量，為分類器提供了多樣的樣本信息。

3)在數(shù)據(jù)集中，AGNES-SMOTE算法處理不平衡比例較小及特征數(shù)較少的數(shù)據(jù)集時(shí)表現(xiàn)效果較好。在數(shù)據(jù)集Heart、Wine和Iris上取得了較高的AUC值、F-measure值和G-mean值，而在數(shù)據(jù)集Eucal、LEV和Balance上取得的值相對較低，這是因?yàn)閿?shù)據(jù)集的不平衡比例增大且其中數(shù)據(jù)集Eucal包含較多的特征數(shù)，使得數(shù)據(jù)結(jié)構(gòu)表現(xiàn)較為復(fù)雜，過采樣算法處理這一類型數(shù)據(jù)集時(shí)產(chǎn)生干擾，因而對分類器分類性能的提升較差。而對于不平衡比例較大的數(shù)據(jù)集，AGNES-SMOTE算法相比其他采樣算法依然能取得較好的AUC值、F-measure值和G-mean值。

因此，AGNES-SMOTE算法在不平衡數(shù)據(jù)處理上，降低了噪音干擾，減少了合成重疊樣本，對容易錯(cuò)分的邊緣樣本加以選擇，考慮了類內(nèi)不平衡及生成樣本點(diǎn)的分布，提升了分類性能。

4 結(jié)束語

針對不平衡數(shù)據(jù)集分類問題，現(xiàn)有的過采樣算法更多地解決類間不平衡，而未考慮少數(shù)類類內(nèi)不平衡，未篩選進(jìn)行過采樣的樣本以及去除噪音，合成過程中存在樣本重疊以及樣本分布“邊緣化”的問題，提出了一種基于層次聚類和改進(jìn)SMOTE的過采樣方法AGNES-SMOTE。該算法首先對數(shù)據(jù)集過濾噪音樣本，使用AGNES算法分別對多數(shù)類和少數(shù)類樣本進(jìn)行聚類，根據(jù)得到的多數(shù)類簇劃分少數(shù)類簇；其次，根據(jù)少數(shù)類簇的采樣權(quán)重和概率分布挑選進(jìn)行過采樣的樣本；最后，采用質(zhì)心方式來限制合成樣本點(diǎn)的生成區(qū)域。AGNES-SMOTE對數(shù)據(jù)集處理過后，結(jié)合分類器在UCI數(shù)據(jù)集上與其他算法進(jìn)行對比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，選用SVM分類器可以更好地提高少數(shù)類樣本的分類準(zhǔn)確度和整體分類性能。該過采樣方法只針對于二分類數(shù)據(jù)，而實(shí)際中的數(shù)據(jù)大多屬于多類別數(shù)據(jù)。下一步將研究針對多類別數(shù)據(jù)的分類算法，進(jìn)一步優(yōu)化模型。