一種改進(jìn)的不平衡數(shù)據(jù)過(guò)采樣算法BN-SMOTE?

楊賽華 周從華 蔣躍明 張付全 張 婷

（1.江蘇大學(xué)計(jì)算機(jī)科學(xué)與通信工程學(xué)院 鎮(zhèn)江 212013）（2.無(wú)錫市第五人民醫(yī)院 無(wú)錫 214073）（3.無(wú)錫市婦幼保健院 無(wú)錫 214002）（4.無(wú)錫市精神衛(wèi)生中心 無(wú)錫 214151）

1 引言

不平衡學(xué)習(xí)問(wèn)題包含不同類(lèi)別之間數(shù)據(jù)樣本的不均衡分布，其中大多數(shù)樣本屬于某種類(lèi)別，而剩余的樣本屬于其它類(lèi)別。許多實(shí)際的應(yīng)用領(lǐng)域中都存在不均衡數(shù)據(jù)集的分類(lèi)問(wèn)題，例如醫(yī)療診斷［1］、信息檢索系統(tǒng)［2］、欺詐性電話的檢測(cè)［3］、直升機(jī)故障檢測(cè)［4］等。傳統(tǒng)的分類(lèi)方法傾向于對(duì)多數(shù)類(lèi)有較高的識(shí)別率，對(duì)于少數(shù)類(lèi)的識(shí)別率卻很低。因此不均衡數(shù)據(jù)集的分類(lèi)問(wèn)題的研究需要尋求新的分類(lèi)方法和判別準(zhǔn)則。

目前最流行的處理不平衡學(xué)習(xí)問(wèn)題的方法多是基于過(guò)采樣方法來(lái)延伸的。在本文中，首先介紹了SMOTE 算法以及它的一種改進(jìn)方案Border?line—SMOTE 算法，同時(shí)指出在某些情況下，Bor?derline—SMOTE 算法無(wú)法正確識(shí)別出所有的邊界樣本?；谶@一問(wèn)題，我們提出一種新的過(guò)采樣方法Borderline Neighbor Synthetic Minority Oversam?pling Technical（BN-SMOTE），其目標(biāo)是構(gòu)建出一個(gè)難以學(xué)習(xí)的邊界少數(shù)類(lèi)樣本集，再?gòu)闹羞x擇少數(shù)類(lèi)樣本參與到樣本合成中?；舅枷胧牵?）對(duì)原始少數(shù)類(lèi)樣本進(jìn)行過(guò)濾操作去除噪聲；2）構(gòu)建難以學(xué)習(xí)的邊界少數(shù)類(lèi)樣本集；3）合成新的少數(shù)類(lèi)樣本。

2 相關(guān)工作

2.1 相關(guān)算法研究

近些年關(guān)于不平衡數(shù)據(jù)分類(lèi)的研究已經(jīng)引起了廣泛的關(guān)注。He 和Garcia［5］將這些不同的不平衡數(shù)據(jù)研究方法主要分成了以下四類(lèi)：采樣方法；代價(jià)敏感學(xué)習(xí)方法；基于核的方法與主動(dòng)學(xué)習(xí)方法以及如單分類(lèi)算法、新奇檢測(cè)等方法。本文將對(duì)目前已經(jīng)提出的一些經(jīng)典過(guò)采樣方法作簡(jiǎn)單介紹。

最簡(jiǎn)單的方法是隨機(jī)過(guò)采樣算法，其中合成的少數(shù)類(lèi)樣本都是隨機(jī)重復(fù)的，但是這樣容易產(chǎn)生模型過(guò)擬合的問(wèn)題［6］。過(guò)采樣中另一種主要的方法是根據(jù)數(shù)據(jù)合成樣本，其中最著名的算法就是SMOTE［7］。SMOTE 的基本思想是對(duì)少數(shù)類(lèi)樣本進(jìn)行分析，并根據(jù)少數(shù)類(lèi)樣本人工合成新的樣本添加到數(shù)據(jù)集中。

為了提高SMOTE 算法的性能，目前已經(jīng)提出了很多對(duì)于SMOTE 的延伸算法。Han［8］等提出一種命名為Borderline-SMOTE 的過(guò)采樣算法。Bor?derline-SMOTE算法最主要的目的是尋找在邊界區(qū)域類(lèi)的少數(shù)類(lèi)樣本，在這個(gè)方法中只使用這些邊界區(qū)域內(nèi)的少數(shù)類(lèi)樣本來(lái)合成新樣本，因?yàn)檫@些少數(shù)類(lèi)樣本是最容易被誤分類(lèi)的樣本。

Sáez等［9］提出了一種名為SMOTE-IPF的框架，在這個(gè)框架中，首先利用SMOTE 算法對(duì)少數(shù)類(lèi)樣本進(jìn)行過(guò)采樣處理，之后通過(guò)迭代分割濾波器［IPF］方法對(duì)存在的噪聲數(shù)據(jù)進(jìn)行濾波操作，通過(guò)一系列的數(shù)值實(shí)驗(yàn)，結(jié)果表明這個(gè)框架具有很好的效率。過(guò)采樣方法可能會(huì)對(duì)分類(lèi)器產(chǎn)生額外的偏差，這會(huì)降低分類(lèi)器在大多數(shù)類(lèi)樣本上的性能。為了防止這種劣化，S. Chen 等［10］將過(guò)采樣和bost?ing 相結(jié)合，提出一種RAMOBoost 算法來(lái)有效地學(xué)習(xí)不平衡數(shù)據(jù)。H.Guo［11］等也提出DataBoost IM 方法，通過(guò)bosting和數(shù)據(jù)生成來(lái)學(xué)習(xí)不平衡數(shù)據(jù)。

2.2 Borderline—SMOTE算法

原始的SMOTE 算法對(duì)所有的少數(shù)類(lèi)樣本都是一視同仁的，但在實(shí)際建模過(guò)程中，我們發(fā)現(xiàn)那些處于邊界位置的樣本更容易被錯(cuò)分，因此利用邊界位置的樣本信息產(chǎn)生新樣本可以給模型帶來(lái)更大的提升。Borderline-SMOTE 便是在SMOTE 方法的基礎(chǔ)上進(jìn)行了改進(jìn)，只對(duì)少數(shù)類(lèi)的邊界樣本進(jìn)行過(guò)采樣，從而改善樣本的類(lèi)別分布。具體步驟描述如下。

假設(shè)原始樣本集為T(mén)，其少數(shù)類(lèi)樣本集P，多數(shù)類(lèi)為N。P={p1，p2，…pi，…，ppnum}，N={n1，n2，…ni，…，nnnum}，其中ppnum，nnnum分別表示少數(shù)類(lèi)樣本個(gè)數(shù)和多數(shù)類(lèi)樣本個(gè)數(shù)。

1）計(jì)算少數(shù)類(lèi)樣本中的每個(gè)樣本點(diǎn)pi與所有訓(xùn)練樣本的歐氏距離，獲得該樣本點(diǎn)的m近鄰（m值為用戶設(shè)定）。

2）對(duì)少數(shù)類(lèi)樣本進(jìn)行劃分。設(shè)在m近鄰中有m'個(gè)多數(shù)類(lèi)樣本點(diǎn)，顯然0 ?m'?m。若m'=m，即m近鄰均為多數(shù)類(lèi)樣本，pi則被認(rèn)為是噪聲；若0 ?m'?m2 ，則pi被 劃 分 為 安 全 樣 本；m2 ?m'＜m，則pi被劃分為邊界樣本。將邊界樣本 記 為 {，…，} ， 其 中 0?dnum?pnum，其中dnum為少數(shù)類(lèi)樣本中邊界樣本的個(gè)數(shù)。

3）計(jì)算邊界樣本點(diǎn)pi' 與少數(shù)類(lèi)樣本P的k近鄰，根據(jù)采樣倍率N，選擇s個(gè)k近鄰點(diǎn)與進(jìn)行線性插值，合成少數(shù)類(lèi)樣本：

其中rj是介于0 與1 之間的隨機(jī)數(shù)；dj表示樣本點(diǎn)與其s個(gè)近鄰的距離。

4）將新合成的少數(shù)類(lèi)樣本與原始訓(xùn)練樣本T合并，構(gòu)成新的訓(xùn)練樣本T'。

與SMOTE 方法相比，Borderline-SMOTE 方法只針對(duì)邊界樣本進(jìn)行近鄰線性插值，使得合成后的少數(shù)類(lèi)樣本分布更為合理。 但是Border?line-SMOTE 算法仍存在許多缺陷，其中一個(gè)問(wèn)題就是無(wú)法有效地分辨出噪聲樣本。在這個(gè)算法中，只有當(dāng)最近鄰所有樣本都為多數(shù)類(lèi)時(shí)，少數(shù)類(lèi)才會(huì)被判斷為噪聲。然而當(dāng)只有兩個(gè)少數(shù)類(lèi)樣本被大多數(shù)類(lèi)包圍時(shí)，依然會(huì)認(rèn)為這兩個(gè)少數(shù)類(lèi)樣本處于邊界區(qū)域，但是顯然它們是屬于噪聲的。

另一個(gè)主要問(wèn)題則是在某些情況下，上述判定方法并不能找到邊界位置的少數(shù)類(lèi)樣本點(diǎn)［12］。如圖1 所示，其中五角星代表多數(shù)類(lèi)樣本，圓圈代表少數(shù)類(lèi)樣本。從圖中我們可以看出，A、B點(diǎn)為離決策邊界最近的少數(shù)類(lèi)樣本點(diǎn)，用這兩個(gè)點(diǎn)進(jìn)行樣本生成能夠得到好的新樣本。假設(shè)m=5，可以發(fā)現(xiàn)少數(shù)類(lèi)樣本點(diǎn)A與B的最近m近鄰樣本中，均為少數(shù)類(lèi)樣本點(diǎn)而沒(méi)有多數(shù)類(lèi)樣本，即m'=0。而根據(jù)上述判定方式，此時(shí)0 ?m'?m2，則A、B 點(diǎn)均被劃分為安全樣本，這種錯(cuò)分方式將會(huì)導(dǎo)致之后的新樣本生成過(guò)程中，不會(huì)使用到A、B兩點(diǎn)進(jìn)行樣本生成。由此造成的決策邊界附近的少數(shù)類(lèi)樣本信息減少，會(huì)大大影響模型的性能。

圖1 被錯(cuò)分的邊界樣本少數(shù)類(lèi)樣本

3 一種新的算法BN-SMOTE

在新樣本的合成過(guò)程中，并不是所有的少數(shù)類(lèi)樣本都是重要的，因?yàn)槠渲杏幸徊糠挚赡芎苋菀妆粚W(xué)習(xí)，對(duì)于新樣本的合成提供的信息少。因此，我們有必要確定一組難以學(xué)習(xí)的少數(shù)類(lèi)樣本，并通過(guò)它們合成新的樣本。這些樣本通常位于決策邊界附近，大多數(shù)現(xiàn)有的過(guò)采樣方法［7～8］沒(méi)有明確地識(shí)別難以學(xué)習(xí)的樣本。雖然Borderline-SMOTE 算法試圖找到一組邊界少數(shù)類(lèi)（難以學(xué)習(xí)）樣本，但我們?cè)谏瞎?jié)已經(jīng)說(shuō)明了它無(wú)法正確識(shí)別出所有的邊界樣本?；谠撍惴ǖ乃枷?，我們采用一種新方法BN-SMOTE來(lái)識(shí)別難以學(xué)習(xí)的少數(shù)類(lèi)樣本，并構(gòu)建成一個(gè)少數(shù)類(lèi)樣本集。該方法分為兩個(gè)階段：在第一階段，BN-SMOTE從原始少數(shù)類(lèi)樣本集Smin中識(shí)別出最難學(xué)習(xí)的少數(shù)類(lèi)樣本，并通過(guò)所識(shí)別出的樣本構(gòu)建一組Simin樣本集；第二階段，BN-SMOTE 從Simin樣本集中選擇少數(shù)類(lèi)樣本來(lái)進(jìn)行新樣本的合成，并將合成出的新樣本添加到Smin中來(lái)生成輸出集Somin。主要步驟描述如下：

算法BN-SMOTE（Smax，Smin，N，k1，k2，k3）

輸入：

1）Smax：多數(shù)類(lèi)樣本集；

2）Smin：少數(shù)類(lèi)樣本集；

3）N ：需要生成的新樣本數(shù)量；

4）k1：用來(lái)去除噪聲的k近鄰值；

5）k2：用來(lái)生成少數(shù)類(lèi)集合的多數(shù)類(lèi)集合的數(shù)量；

6）k3：用來(lái)生成少數(shù)類(lèi)集合的少數(shù)類(lèi)鄰居的數(shù)量。

程序開(kāi)始：

1）對(duì)于每個(gè)少數(shù)類(lèi)樣本xi∈Smin，計(jì)算其最近鄰集合NN(xi)，其中NN(xi)包含了與xi歐式距離相距最近的k1個(gè)樣本。

2）去除掉那些在其k1 近鄰中沒(méi)有其他少數(shù)類(lèi)存在的少數(shù)類(lèi)樣本，組成一個(gè)過(guò)濾后的少數(shù)類(lèi)樣本集Sminf：

3）對(duì)于每個(gè)少數(shù)類(lèi)樣本xi∈Sminf，計(jì)算其最近鄰的多數(shù)類(lèi)樣本集合Nmaj(xi)，其中Nmaj(xi)包含了與xi歐氏距離最近的k2 個(gè)多數(shù)類(lèi)樣本。

4）對(duì)所有的Nmaj(xi)集合作合并操作得到處于邊界區(qū)域的多數(shù)類(lèi)樣本集合：

5）對(duì)于每個(gè)多數(shù)類(lèi)樣本yi∈Sbmaj，計(jì)算其最近鄰的少數(shù)類(lèi)樣本集合Nmin(yi)。其中Nmin(yi)包含了與yi歐式距離相距最近的k3 個(gè)少數(shù)類(lèi)樣本。

6）對(duì)所有得到的Nmin(yi)少數(shù)類(lèi)樣本

作并集，得到處于邊界區(qū)域最難學(xué)習(xí)的少數(shù)類(lèi)樣本集Simin：

7）初始化集合Somin，使得Somin=Smin。

8）Do forj=1…N。

（1）從少數(shù)類(lèi)樣本集合Simin中選擇一個(gè)樣本x，再隨機(jī)選擇另一個(gè)樣本y；

（2）生成一個(gè)新樣本s：s=x+α×(y-x)，其中α是處于［0，1］的隨機(jī)數(shù)；

（3）將s放入集合Somin中：Somin=Somin∪{s} 。

9）結(jié)束循環(huán)。

輸出：過(guò)采樣處理的少數(shù)類(lèi)樣本集合Somin。

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

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

本文實(shí)驗(yàn)數(shù)據(jù)來(lái)自于UCI 機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中的3組真實(shí)數(shù)據(jù)集［13］。其中Abalone和Pima數(shù)據(jù)集是二分類(lèi)不平衡數(shù)據(jù)集，Phoneme 是多分類(lèi)數(shù)據(jù)集，我們將Phoneme 數(shù)據(jù)集中的Class’1’作為少數(shù)類(lèi)，其他類(lèi)共同作為多數(shù)類(lèi)。具體描述如表1所示。

表1 數(shù)據(jù)集描述

4.2 評(píng)價(jià)指標(biāo)

對(duì)一個(gè)二分問(wèn)題來(lái)說(shuō)，會(huì)出現(xiàn)四種情況，如表2所示。

表2 二分類(lèi)的混淆矩陣

通過(guò)表2 的混淆矩陣，我們就可以計(jì)算出一些評(píng)價(jià)指標(biāo)。其中最常見(jiàn)的就是正確率，通常來(lái)說(shuō)，正確率越高，分類(lèi)器的性能越好。但是由于分類(lèi)器對(duì)少數(shù)類(lèi)的不敏感，當(dāng)對(duì)不平衡數(shù)據(jù)進(jìn)行分類(lèi)時(shí)，少數(shù)類(lèi)在很大程度上被判為多數(shù)類(lèi)，導(dǎo)致少數(shù)類(lèi)樣本的識(shí)別率較低，因此正確率不適用于評(píng)價(jià)不平衡問(wèn)題［14］。本文選用其它目前常用于評(píng)價(jià)不平衡問(wèn)題的指標(biāo)G-mean和F-measure 。

G-mean表示只有當(dāng)分類(lèi)器對(duì)樣本中少數(shù)類(lèi)和多數(shù)類(lèi)的分類(lèi)效果都很好的情況下，此時(shí)G-mean的值最大［14～15］。定義如下：

F-measure 同時(shí)結(jié)合了精確度和召回率，是它們的加權(quán)調(diào)和平均，用于最大限度地提高對(duì)單個(gè)類(lèi)性能的評(píng)價(jià)程度，因此可用于測(cè)量分類(lèi)器在少數(shù)類(lèi)樣本上的分類(lèi)性能。定義如下：

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

本文的對(duì)比實(shí)驗(yàn)主要包括三個(gè)算法的對(duì)比，分別是SMOTE、Borderline-SMOTE 和本文提出的BN-SMOTE 算法。為了測(cè)試這些算法在不同分類(lèi)器下的效果，在通過(guò)算法對(duì)三組數(shù)據(jù)集過(guò)采樣處理結(jié)束后，分別利用SVM 和C4.5 決策樹(shù)對(duì)合成后的數(shù)據(jù)集進(jìn)行分類(lèi)，最終得到G-mean 和F-measure值對(duì)結(jié)果進(jìn)行評(píng)價(jià)。

4.3.1 實(shí)驗(yàn)環(huán)境和相關(guān)參數(shù)設(shè)置

本文實(shí)驗(yàn)環(huán)境為操作系統(tǒng)Windows 8 64 bit，CPU/Intel（R）Core（TM）i5-3210M 雙核處理器，主頻2.5GHz，內(nèi)存8G，硬盤(pán)容量1T，編譯工具Python 3.6.0。其中SVM 算法核函數(shù)使用RBF 核函數(shù)，系數(shù)σ＝0.5，懲罰因子cost=2。對(duì)于BN-SMOTE 算法，設(shè)置k1=5，k2=3，k3=|Smin|/2，所有的這些值都是在一些初步運(yùn)行后的選擇。對(duì)于SMOTE 和Borderline-SMOTE算法，近鄰個(gè)數(shù)k值都設(shè)置為5，同時(shí)評(píng)價(jià)指標(biāo)F-measure 中的β取值為1，即F-Value。為避免數(shù)據(jù)重復(fù)計(jì)算，客觀評(píng)價(jià)算法的性能，實(shí)驗(yàn)均采用10 次10 折交叉驗(yàn)證的平均值作為數(shù)值結(jié)果［16］。

4.3.2 實(shí)驗(yàn)結(jié)果對(duì)比

表3 為各算法（SMOTE、Borderline-SMOTE、BN-SMOTE）分 別 在SVM 和C4.5 決 策 樹(shù) 下 的F-Value、G-mean 結(jié)果對(duì)比。從三組不平衡數(shù)據(jù)集（Abalone、Pima、Phoneme）的實(shí)驗(yàn)中可以看出，在SVM 分類(lèi)器下，三個(gè)算法的F-Value 值相差不大，各有優(yōu)劣，但BN-SMOTE 的G-mean 值要大于其它兩個(gè)算法，而在C4.5 決策樹(shù)分類(lèi)器下，三個(gè)算法中BN-SMOTE 算 法 的F-Value 和G-mean 都 明 顯 更高，由此可知無(wú)論在SVM 和C4.5 決策樹(shù)中，BN-SMOTE 算法的表現(xiàn)都不差甚至更好。同時(shí)在對(duì)同一數(shù)據(jù)集的實(shí)驗(yàn)中，我們發(fā)現(xiàn)BN-SMOTE 算法在C4.5 決策樹(shù)下的表現(xiàn)要更優(yōu)于在SVM 分類(lèi)器下的表現(xiàn)。

表3 SVM分類(lèi)器下不同算法的F-Value和G-mean對(duì)比

4.3.3 實(shí)驗(yàn)結(jié)果與過(guò)采樣率N的關(guān)系

圖2～4 分 別 表 示 的 是 在Abalone、Pima、Pho?neme 數(shù)據(jù)集的實(shí)驗(yàn)中，G-mean 關(guān)于采樣率N 的變化情況。對(duì)于Abalone 數(shù)據(jù)集，當(dāng)采樣率N=3 時(shí)，BN-SMOTE 算法在SVM 和C4.5 決策樹(shù)中達(dá)到最大值，此時(shí)數(shù)據(jù)集內(nèi)部達(dá)到類(lèi)別平衡的狀態(tài)，而隨著采樣率N 的增大，分類(lèi)精度逐漸減少，原因是少數(shù)類(lèi)樣本的不斷增多而產(chǎn)生了新的不平衡。同時(shí)從圖2（a）和圖2（b）對(duì)比中可以看出，BN-SMOTE 算法在C4.5 決策樹(shù)中表現(xiàn)明顯更好于SVM。同理在Pima 數(shù) 據(jù) 集 中N=4，Phoneme 數(shù) 據(jù) 集N=8 時(shí)，BN-SMOTE算法達(dá)到最大值，且整體表現(xiàn)優(yōu)于其它兩個(gè)算法。因此從以上分析中可以得出結(jié)論：1）當(dāng)采樣率N接近于數(shù)據(jù)集的不平衡率，此時(shí)數(shù)據(jù)集趨于平衡，分類(lèi)效果最好；2）BN-SMOTE 算法在分類(lèi)器C4.5決策樹(shù)中的表現(xiàn)更好。

圖2 Abalone的G-mean關(guān)于采樣率N的變化曲線

圖3 Pima的G-mean關(guān)于采樣率N的變化曲線

圖4 Phoneme的G-mean關(guān)于采樣率N的變化曲線

5 結(jié)語(yǔ)

本文進(jìn)行了廣泛的實(shí)驗(yàn)對(duì)BN-SMOTE 在不同數(shù)據(jù)集上的表現(xiàn)進(jìn)行評(píng)估，并與其他方法比較，實(shí)驗(yàn)表明無(wú)論在SVM 和C4.5 決策樹(shù)中，該算法都具有很好的表現(xiàn)。本文的后續(xù)工作主要有兩點(diǎn)：一是考慮使用名義特征的數(shù)據(jù)集，在本文中，我們只選用了具有連續(xù)的特征的數(shù)據(jù)集，因此可以使BN-SMOTE 通用化來(lái)處理任何類(lèi)型的特征；二是BN-SMOTE 可以與其他一些欠采樣和邊界估計(jì)方法集成，以研究它們是否能夠比單個(gè)BN-SMOTE過(guò)采樣提供更好的結(jié)果。