于艷麗 江開(kāi)忠 盛靜文

(上海工程技術(shù)大學(xué)數(shù)理與統(tǒng)計(jì)學(xué)院 上海 201620)

0 引 言

不平衡數(shù)據(jù)指的是數(shù)據(jù)集中存在不同類別樣本的數(shù)目相差很大。以二分類數(shù)據(jù)為例，征信領(lǐng)域中誠(chéng)信與違約、醫(yī)療領(lǐng)域中健康與絕癥、郵箱里正常郵件與垃圾郵件，這些二分類數(shù)據(jù)中某一類數(shù)據(jù)數(shù)量遠(yuǎn)多于另一類，這樣的數(shù)據(jù)就稱為不平衡數(shù)據(jù)[1-4]。將數(shù)量較少的類別稱為少數(shù)類，將數(shù)量較多的稱為多數(shù)類。現(xiàn)實(shí)世界中，隨處都有不平衡數(shù)據(jù)，且錯(cuò)分兩類數(shù)據(jù)的代價(jià)是不同的，通常對(duì)少數(shù)類的正確判斷更有意義[5]。傳統(tǒng)的分類方法對(duì)于平衡的樣本數(shù)據(jù)已經(jīng)表現(xiàn)出很好的性能，但是對(duì)于不平衡數(shù)據(jù)，分類器的性能在下降。如何提升傳統(tǒng)分類方法對(duì)少數(shù)類的識(shí)別準(zhǔn)確率成為機(jī)器學(xué)習(xí)中一個(gè)急需解決的問(wèn)題[1,6]。目前，解決不平衡數(shù)據(jù)問(wèn)題的方法可以分為如下兩類：

1) 改進(jìn)分類算法以提高對(duì)少數(shù)類樣本的識(shí)別，如：代價(jià)敏感學(xué)習(xí)[7]、集成學(xué)習(xí)[8]和單類學(xué)習(xí)等。AdaBoost算法[9]就是其中比較經(jīng)典的處理不平衡數(shù)據(jù)的集成算法，本身就具有代價(jià)敏感的特性，能夠給予誤判樣本更高的權(quán)重。一些算法通過(guò)更改AdaBoost算法中樣本更新權(quán)重來(lái)增加正確率，如AdaCost算法[10]和RareBoost算法[11]。還有些算法將采樣算法與集成算法相結(jié)合，例如NIBoost[12]、RSBoost[13]和PCBoost[14]。另外還有其他分類算法，如：SVM[2]、決策樹、神經(jīng)網(wǎng)絡(luò)等，它們也經(jīng)常被用來(lái)處理不平衡數(shù)據(jù)。

2) 通過(guò)處理原始數(shù)據(jù)來(lái)提高對(duì)少數(shù)類樣本的識(shí)別，即對(duì)數(shù)據(jù)進(jìn)行欠采樣或者過(guò)采樣來(lái)達(dá)到數(shù)據(jù)平衡的目的。欠采樣是剔除多數(shù)類樣本數(shù)量，過(guò)采樣是增加少數(shù)類樣本數(shù)量。欠采樣算法有基于密度的欠采樣[1]、基于權(quán)重的欠采樣[15]等，其很容易造成有用信息的減少。過(guò)采樣算法中的SMOTE[16]算法是主流算法，其通過(guò)線性插值的方法增加少數(shù)類虛擬個(gè)體，使得分類結(jié)果得到改善，但具有如下缺點(diǎn)：① 參與合成的少數(shù)類可能是噪聲樣本，進(jìn)而影響新樣本質(zhì)量；② 沒(méi)有根據(jù)少數(shù)類樣本的重要性，進(jìn)行區(qū)別化選擇；③ 生成新樣本時(shí)，正負(fù)類樣本混雜，從而導(dǎo)致邊界模糊問(wèn)題；④ 合成樣本僅在2個(gè)點(diǎn)的連線上產(chǎn)生，分類器易過(guò)擬合等[17]。針對(duì)SMOTE算法存在的問(wèn)題，學(xué)者提出了很多改進(jìn)的SMOTE算法。董燕杰[18]研究了Random-SMOTE方法，把直線插點(diǎn)改成三角形內(nèi)插點(diǎn)；袁銘[19]提出了R-SMOTE算法，在n維球體進(jìn)行插點(diǎn)。這些方法對(duì)減少過(guò)擬合現(xiàn)象均有一定作用，但都是對(duì)全體少數(shù)類樣本進(jìn)行過(guò)采樣，準(zhǔn)確率提升有限。候貝貝等[20]用np-SMOTE方法在邊界少數(shù)類周圍合成少數(shù)類，使其從非安全樣本變成安全樣本，突破了原有的少數(shù)類樣本點(diǎn)的范圍，但易產(chǎn)生噪聲。Han等[21]用Borderline-SMOTE算法定義了邊界，解決了沒(méi)有區(qū)分少數(shù)類點(diǎn)重要性的問(wèn)題，但對(duì)于邊界的定義僅依靠異類點(diǎn)的數(shù)量，不夠細(xì)致。古平等[5]提出了SD-ISMOTE算法，采用了不同的過(guò)采樣算法，能夠解決過(guò)擬合的問(wèn)題，但是目標(biāo)依舊是全體少數(shù)類樣本。Batista等[22]提出了SMOTE與Tome Link結(jié)合的算法，Last等[23]提出了一種基于k-means聚類的SMOTE過(guò)采樣方法，兩者都有效地解決了噪聲問(wèn)題。上述過(guò)采樣方法的改進(jìn)在處理不平衡數(shù)據(jù)上都有一定優(yōu)勢(shì)，但大部分沒(méi)有對(duì)參與新樣本合成的少數(shù)類樣本進(jìn)行區(qū)別化對(duì)待，或者區(qū)分度不高，從而導(dǎo)致少數(shù)類的識(shí)別率不夠高。

本文提出一種不平衡數(shù)據(jù)中基于異類k距離的邊界混合采樣算法，主要目標(biāo)是區(qū)分邊界樣本與非邊界樣本，對(duì)參與合成的邊界少數(shù)類樣本做精細(xì)區(qū)分，以便增加產(chǎn)生新樣本的質(zhì)量，提高少數(shù)類樣本的分類正確性。首先，生成邊界集，只對(duì)其中的少數(shù)類樣本進(jìn)行過(guò)采樣，從而對(duì)少數(shù)類樣本點(diǎn)進(jìn)行區(qū)別選擇；其次，根據(jù)支持度對(duì)邊界集中的少數(shù)類樣本進(jìn)行細(xì)分，能夠更加細(xì)致嚴(yán)謹(jǐn)?shù)亟o每一個(gè)少數(shù)類樣本定位，少數(shù)類樣本虛擬個(gè)體的產(chǎn)生根據(jù)類別的不同分別采用SMOTE、R-SMOTE、Random-SMOTE的過(guò)采樣方法，改善過(guò)擬合現(xiàn)象；最后，對(duì)非邊界集多數(shù)類樣本基于異類k距離進(jìn)行剔除，保留有意義的樣本。

1 相關(guān)知識(shí)

1.1 分類問(wèn)題

1.1.1二分類理論

假設(shè)在一個(gè)兩分類問(wèn)題中，數(shù)據(jù)集C=C0∪C1，C0∩C1=?，其中C0為多數(shù)類樣本，C1為少數(shù)類樣本。標(biāo)準(zhǔn)化后的樣本觀測(cè)矩陣為：

當(dāng)xi∈C1時(shí)，yi=1，稱個(gè)體xi為陽(yáng)性個(gè)體；即少數(shù)類個(gè)體；否則，yi=0，稱個(gè)體xt為陰性個(gè)體，即多數(shù)類個(gè)體。

分類器超平面表示為：

w1x1+w2x2+…+wpxp=wTx=c

(1)

通常，超平面的系數(shù)和常數(shù)的估計(jì)可表示為下面優(yōu)化問(wèn)題的解：

(2)

即分類器的超平面法向量和常數(shù)是使得F1取最大值時(shí)的(w1,w2,…,wp,c)，F(xiàn)1指分類評(píng)價(jià)指標(biāo)中的F1分類(F-Score)。

1.1.2分類評(píng)價(jià)指標(biāo)

通常來(lái)說(shuō)混淆矩陣是評(píng)價(jià)一個(gè)算法分類效果的不二選擇，混淆矩陣如表1所示。

表1 混淆矩陣

將實(shí)際為正類的樣本分為預(yù)測(cè)為正類和預(yù)測(cè)為負(fù)類兩部分，將實(shí)際為負(fù)類的樣本分為預(yù)測(cè)為負(fù)類和預(yù)測(cè)為正類兩部分，它們的個(gè)數(shù)分別簡(jiǎn)記為：TP、FN、TN和FP，則分類器的性能表示如下：

1.1.3最小距離分類法

已知類C及其中心μ，個(gè)體x到類C的距離定義為：

d(x,C)=d(x,μ)=(x-μ)T(x-μ)

最小距離判別準(zhǔn)則為：已知兩類C0和C1，對(duì)任意x，若d(x,C0)

1.2 相關(guān)過(guò)采樣算法

1.2.1SMOTE算法[16]

SMOTE算法流程如下:

1) 對(duì)于少數(shù)類樣本中每一個(gè)個(gè)體x，以歐氏距離為標(biāo)準(zhǔn)計(jì)算它到少數(shù)類樣本集C1中所有樣本的距離，對(duì)所有距離排序，距離其最近的k個(gè)樣本便是其k近鄰。

2) 根據(jù)樣本不平衡比例設(shè)置一個(gè)采樣比例以確定采樣倍率N，對(duì)于每一個(gè)少數(shù)類樣本x，從其k近鄰中隨機(jī)選擇樣本yi。

3) 對(duì)于每一個(gè)隨機(jī)選出的近鄰yi，分別與原樣本按下式構(gòu)建新的樣本：

xnew,i=x+rand(0,1)×|x-yi|

(3)

1.2.2R-SOMTE算法[19]

R-SMOTE算法在n維球體內(nèi)插值，算法流程如下:

1) 根據(jù)數(shù)據(jù)集不平衡比例設(shè)置一個(gè)采樣倍率N，從少數(shù)類樣本C1中循環(huán)選擇樣本x。

2) 從x的k個(gè)同類最近鄰中隨機(jī)選擇樣本y，構(gòu)建新樣本。

zi,j=xj-|yj-xj|

(4)

z2,j=xj+|yj-xj|

(5)

xnew,j=xj+rand(0,1)×|z2,j-z1,j|

(6)

式中：xj代表樣本x的第j個(gè)屬性。

3) 如果D(x,xnew)>D(x,y)，則廢棄xnew，重新生成xnew。

4)xnew加入C1，當(dāng)C1的樣本數(shù)等于或相當(dāng)于C0的樣本時(shí)，結(jié)束過(guò)采樣。

1.2.3Randmon-SOMTE算法[18]

Random-SMOTE算法在三角形內(nèi)生成新的樣本點(diǎn)，算法流程如下：

1) 根據(jù)數(shù)據(jù)集不平衡比例設(shè)置一個(gè)采樣倍率N，從少數(shù)類樣本C1中循環(huán)選擇個(gè)體x。

2) 在x的k近鄰中隨機(jī)尋找兩個(gè)同類個(gè)體a、b，在兩點(diǎn)連線上隨機(jī)確定一點(diǎn)y，最后在個(gè)體x與y之間合成新的樣本點(diǎn)xnew：

xnew=x+rand(0,1)×(x-y)

(7)

2 邊界混合采樣的BHSK算法

2.1 算法思想

BHSK算法作為混合采樣算法，綜合過(guò)采樣與欠采樣算法于一體。主要思路是凸顯不同位置樣本不同的采樣重要性，所以采樣方法要因樣本位置而異，這樣能產(chǎn)生有助于提高分類精確度的新樣本，而如何區(qū)分樣本的重要性是本文算法的重點(diǎn)之一。對(duì)于過(guò)采樣部分，BHSK算法采用兩種方法實(shí)現(xiàn)了對(duì)少數(shù)類樣本遞進(jìn)式區(qū)分，分別是基于異類k距離邊界集的識(shí)別、支持度的判定，從而篩選出不同層次的少數(shù)類邊界點(diǎn)。對(duì)于欠采樣部分，BHSK算法主要是通過(guò)異類k距離判別，從而刪除遠(yuǎn)離邊界的多數(shù)類點(diǎn)。

另一個(gè)相關(guān)問(wèn)題是如何尋找適合各種不同位置少數(shù)類樣本的采樣方法與采樣倍率。根據(jù)不同位置樣本的不同特點(diǎn)，本文算法采用了三種過(guò)采樣算法和倍率，有針對(duì)性地對(duì)不同樣本進(jìn)行過(guò)采樣，產(chǎn)生更有意義的位于邊界的新樣本。

2.2 基于異類k距離的邊界集識(shí)別

從數(shù)據(jù)層面對(duì)數(shù)據(jù)集進(jìn)行分類，為了使類之間的樣本數(shù)量均衡，實(shí)現(xiàn)較好的分類效果，基于支持向量機(jī)(SVM)的分類思想，超平面只與支持向量有關(guān)，而支持向量大都位于多數(shù)類樣本和少數(shù)類樣本的邊界，所以在處理不平衡數(shù)據(jù)時(shí)邊界集的識(shí)別是極其重要的[20]。BHSK算法的邊界集是基于異類k距離來(lái)定義的，本文通過(guò)改進(jìn)文獻(xiàn)[24]中的k距離，提出一種異類k距離。

換言之，x的異類k距離是所有與x異類的點(diǎn)中，由近到遠(yuǎn)第k個(gè)異類點(diǎn)到x的距離。異類k距離可以評(píng)價(jià)一個(gè)樣本點(diǎn)附近異類點(diǎn)的密度，異類k距離越大，說(shuō)明附近異類點(diǎn)密度越小，反之則越大。

(8)

(9)

定義4邊界噪聲點(diǎn)。若x=A0或A1，且其k近鄰全是異類點(diǎn)，可以理解為深入異類點(diǎn)內(nèi)部，則x為邊界噪聲點(diǎn)；由邊界噪聲點(diǎn)產(chǎn)生的新樣本，可能存在質(zhì)量較差的問(wèn)題，所以以下B0和B1表示已經(jīng)刪除了噪聲點(diǎn)的邊界0類點(diǎn)與邊界1類點(diǎn)。

2.3 少數(shù)類邊界樣本集的細(xì)分

定義5支持度。設(shè)x∈B1，m(x)表示x的最近k個(gè)近鄰中屬于B1的個(gè)體數(shù)，則m(x)為x的支持度。

根據(jù)支持度將B1分為三類，具體情況如下：

(10)

在區(qū)分邊界集的基礎(chǔ)上再對(duì)邊界集進(jìn)行細(xì)分，目的是為了更加細(xì)致地對(duì)每一個(gè)少數(shù)類樣本進(jìn)行重要性評(píng)估，從而選擇出每一個(gè)類別少數(shù)類樣本適合的采樣方法。

2.4 邊界集的過(guò)采樣方法與數(shù)量

對(duì)于邊界集少數(shù)類樣本B1進(jìn)行過(guò)采樣。對(duì)于過(guò)采樣方法，BHSK算法根據(jù)每個(gè)點(diǎn)對(duì)分類做出的貢獻(xiàn)不同對(duì)三類邊界點(diǎn)采用不同的過(guò)采樣方法和過(guò)采樣倍率，按照近邊界則優(yōu)的原則進(jìn)行如下采樣?？偛蓸訑?shù)量是D=C0-C1，按照3∶2∶1的比例確定三個(gè)類別中新生成樣本的數(shù)量。

2.5 非邊界集的欠采樣

2.6 算法步驟

本文提出的BHSK算法具體如下：

輸入：訓(xùn)練數(shù)據(jù)集C，近鄰參數(shù)k，插值數(shù)量D。

輸出：均衡數(shù)據(jù)集T。

2) 將B1根據(jù)支持度細(xì)分為B11、B12和B13。

5) 將train 1和train 2合并為train。

3 實(shí) 驗(yàn)

3.1 數(shù)據(jù)集的選擇與分析

本文從UCI數(shù)據(jù)庫(kù)選取8個(gè)數(shù)據(jù)集Abalone、biodeg、Ecoli、Shuttle、pima、glass、yeast、spambase，其中有些數(shù)據(jù)集是二分類數(shù)據(jù)集，比如biodeg、spambase、pima；有些是多分類數(shù)據(jù)集，比如Abalone、Ecoli、shuttle、glass、yeast。將abalone中”F”定義為少數(shù)類，其余為多數(shù)類；Ecoli數(shù)據(jù)中的標(biāo)簽為“pp，om”的樣本定義為少數(shù)類，其他為多數(shù)類；將shuttle數(shù)據(jù)集中標(biāo)簽為“1”定義為多數(shù)類，其他為少數(shù)類；將glass標(biāo)簽中“2”定義為少數(shù)類，其他為多數(shù)類；將yeast數(shù)據(jù)集標(biāo)簽中“MIT”定義為少數(shù)類其他為多數(shù)類。數(shù)據(jù)集信息如表2所示。

表2 數(shù)據(jù)集信息

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

表3 不同算法在8個(gè)數(shù)據(jù)集上Recall對(duì)比結(jié)果

表4 不同算法在8個(gè)數(shù)據(jù)集上的F1-score對(duì)比結(jié)果

(a) Abalone (b) biodeg (c) ecoli

從表3可以看出，BHSK算法在少數(shù)類的識(shí)別上是比較有優(yōu)勢(shì)的，大部分?jǐn)?shù)據(jù)集在本文算法的處理后得到的Recall值都高于文中列舉的其他對(duì)比算法。因?yàn)楸疚脑谔幚頂?shù)據(jù)時(shí)，對(duì)少數(shù)類的邊界點(diǎn)做了相應(yīng)處理，較好地降低了由邊界點(diǎn)分錯(cuò)而帶來(lái)的不良影響，同時(shí)對(duì)非邊界的多數(shù)類基于異類k距離進(jìn)行刪除，較好地保留了對(duì)分類有價(jià)值的樣本點(diǎn)。雖然在Yeast、Spambase數(shù)據(jù)集上沒(méi)有取得最優(yōu)值，但相差不大，說(shuō)明BHSK算法能夠在一定程度上提高少數(shù)類的分類性能。

從表4可見(jiàn)，針對(duì)Yeast數(shù)據(jù)集，R-SMOTE算法的結(jié)果優(yōu)于本文，由于該數(shù)據(jù)集的不平衡比率較大，且邊界點(diǎn)重疊度較大，本文邊界集閾值的設(shè)定可能對(duì)該數(shù)據(jù)集的分類性能產(chǎn)生影響，使得球體插值更適合于這個(gè)數(shù)據(jù)集。但是從整體來(lái)看，BHSK算法經(jīng)過(guò)一系列處理以后，能夠使少數(shù)類的準(zhǔn)確性提高。

為了更加可視化本文算法與其他算法的比較情況，圖1列舉了本文算法與所有對(duì)比算法在不同數(shù)據(jù)集不同指標(biāo)的得分情況，橫坐標(biāo)都表示打分的指標(biāo)Precision、Recall、F1-score和Accuracy?？v坐標(biāo)是分類結(jié)果打分情況，其范圍在0～1之間。綜上所述，BHSK算法優(yōu)于SMOTE、R-SMOTE、Borderline-SMOTE和KOCDE算法，它可以更合理且有效地改善不均衡數(shù)據(jù)集中樣本分布的不均衡程度，從而提高分類器的性能。

4 結(jié) 語(yǔ)

本文針對(duì)非平衡數(shù)據(jù)分類問(wèn)題，提出一種基于異類k距離邊界混合采樣分類算法。一方面能夠通過(guò)兩次判別：邊界判別與支持度判別，更加具體區(qū)分少數(shù)類樣本重要性，并對(duì)細(xì)分的不同類別少數(shù)類采取不同的分類方法和不同的采樣倍率，給距離邊界越近的少數(shù)類越高重視；另一方面對(duì)非邊界集的多數(shù)類點(diǎn)根據(jù)異類k距離閾值，刪除遠(yuǎn)離邊界的一部分點(diǎn)，從而構(gòu)造平衡數(shù)據(jù)。實(shí)驗(yàn)結(jié)果表明，本文算法在一定程度上提高了數(shù)據(jù)集的分類性能，可將其應(yīng)用于一系列評(píng)估和檢測(cè)問(wèn)題。但本文算法也存在一些不足，如邊界集閾值與多數(shù)類非邊界集閾值的選取方面理論依據(jù)不足，未來(lái)將在閾值方面進(jìn)行研究。