一種增強(qiáng)少數(shù)類邊界的多類不平衡過(guò)抽樣算法

曹 蘭

（漳州職業(yè)技術(shù)學(xué)院電子工程學(xué)院，福建 漳州 363000）

引 言

數(shù)據(jù)挖掘應(yīng)用所面臨的一個(gè)相對(duì)新的挑戰(zhàn)是如何從不平衡的數(shù)據(jù)集中提取少數(shù)類規(guī)則。在當(dāng)前實(shí)際應(yīng)用中，Web挖掘、文本分類及生物醫(yī)學(xué)數(shù)據(jù)分析等［1-3］，它們都面臨著少數(shù)類的實(shí)例數(shù)量比多類的實(shí)例數(shù)量少很多的情形，從而造成了如何在機(jī)器學(xué)習(xí)中準(zhǔn)確地識(shí)別這些少數(shù)類的困難。例如，在金融領(lǐng)域中，怎樣在大量交易中發(fā)現(xiàn)欺詐性信用卡活動(dòng)［4-7］；探測(cè)衛(wèi)星圖像的溢油［8］；在生物醫(yī)學(xué)數(shù)據(jù)分析中，與正常的非癌癥病例相比，不同類型癌癥的數(shù)據(jù)實(shí)例通常非常有限，所以能盡早為患者預(yù)測(cè)癌癥的類型并提供適當(dāng)及時(shí)的治療非常重要［9］。因此，在數(shù)據(jù)集中，當(dāng)某些類型的數(shù)據(jù)分布顯著支配實(shí)例空間時(shí)，就會(huì)發(fā)生數(shù)據(jù)不平衡。如何從不平衡的數(shù)據(jù)集中提取少數(shù)類規(guī)則，越來(lái)越受到學(xué)術(shù)界和工業(yè)界的關(guān)注。

當(dāng)前處理數(shù)據(jù)集中不平衡問(wèn)題主要是抽樣方法，該方法主要解決數(shù)據(jù)集中的類實(shí)例平衡問(wèn)題。目前有兩種抽樣方法：欠采樣和過(guò)采樣。過(guò)采樣抽樣方法是數(shù)據(jù)集中少數(shù)類，從而使不平衡分布達(dá)到平衡狀態(tài)［10-13］。例如，成本曲線技術(shù)被用于研究過(guò)采樣和欠采樣與基于決策樹(shù)的學(xué)習(xí)算法的交互作用，該技術(shù)研究了將概率估計(jì)、剪枝和數(shù)據(jù)預(yù)處理相結(jié)合的采樣技術(shù)用于決策樹(shù)學(xué)習(xí)［14-15］。此外，“JOUS-Boost”通過(guò)將自適應(yīng)增強(qiáng)與抖動(dòng)采樣技術(shù)相結(jié)合的方式來(lái)處理不平衡的數(shù)據(jù)學(xué)習(xí)［16］。最近的一些研究是基于支持向量機(jī)從不平衡數(shù)據(jù)集中主動(dòng)學(xué)習(xí)，這種學(xué)習(xí)方式不需要搜索整個(gè)訓(xùn)練數(shù)據(jù)空間，而是可以有效地從隨機(jī)的訓(xùn)練種群中選擇信息實(shí)例，從而大大降低了處理大型不平衡數(shù)據(jù)集的計(jì)算成本［17］。

以上這些處理數(shù)據(jù)集中不平衡數(shù)據(jù)的方法確實(shí)起到了一定作用，但都是基于現(xiàn)有數(shù)據(jù)集上充分利用對(duì)實(shí)例進(jìn)行評(píng)估、剪枝、選擇和計(jì)算等來(lái)減少樣本產(chǎn)生偏差。由于少數(shù)類實(shí)例數(shù)量的局限性，這些處理不平衡方法始終難以突破少數(shù)類樣本數(shù)量本身局限所帶來(lái)的偏差，且可改進(jìn)的偏差空間有限。因此，過(guò)抽樣SMOTE算法［18］通過(guò)生成任意數(shù)量的合成少數(shù)類實(shí)例，再將分類器學(xué)習(xí)偏差轉(zhuǎn)移到少數(shù)類，從而通過(guò)人工生成數(shù)據(jù)樣本克服原始數(shù)據(jù)集的不平衡。在該思想的基礎(chǔ)上進(jìn)行擴(kuò)展的SMOTEBoost算法是合成過(guò)程與自適應(yīng)增強(qiáng)技術(shù)相結(jié)合，以改變更新權(quán)重，從而更好地補(bǔ)償偏斜分布［19］。為了保證少數(shù)類和多數(shù)類的最優(yōu)分類精度，Boost-IM算法通過(guò)使用“種子”樣本為少數(shù)類和多數(shù)類生成合成數(shù)據(jù)示例［20-21］。這種在原數(shù)據(jù)集基礎(chǔ)上為不平衡數(shù)據(jù)生成合成實(shí)例的方法對(duì)解決樣本偏差提供了另一種思路，并能較好地解決樣本偏差問(wèn)題。但在生成合成實(shí)例上沒(méi)能很好地細(xì)分到每一少數(shù)類實(shí)例，且未能明確區(qū)分少數(shù)類與多數(shù)類的邊界，而邊界的區(qū)分對(duì)提高分類準(zhǔn)確率是非常重用的。

本文提出一種增強(qiáng)少數(shù)類實(shí)例邊界的多類不平衡過(guò) 抽 樣 分 類 算 法（MEBMI，a Method to Enhance the Boundary of Minority Instances in the Multi-class Balance）。該算法核心思想是自主地隨少數(shù)類中樣本的K鄰近樣本的分布情況自動(dòng)生成合適數(shù)量的少數(shù)類樣本，對(duì)于那些與多數(shù)類鄰近的少數(shù)類樣本所生成合適數(shù)量的合成實(shí)例，能夠起到進(jìn)一步區(qū)分少數(shù)類與多數(shù)類的界限的作用。因此，該算法將決策邊界自適應(yīng)地轉(zhuǎn)移到那些難以學(xué)習(xí)的少數(shù)類樣本上，同時(shí)也減少了因原始不平衡數(shù)據(jù)分布問(wèn)題而引入的學(xué)習(xí)偏差。

1 改進(jìn)的少數(shù)類過(guò)抽樣算法

1.1 基本定義

設(shè)訓(xùn)練數(shù)據(jù)集D含有m個(gè)實(shí)例｛Xi，Yi｝（其中i=1，2，…，m），Xi含有n個(gè)屬性，對(duì)應(yīng)類標(biāo)簽為Yi。定義ms和ml分別為數(shù)據(jù)集中少數(shù)類與多數(shù)類的實(shí)例數(shù)量。因此，ms≤ml，ms+ml=m。

定義1不平衡數(shù)據(jù)集中少數(shù)類的比率為：d=m s/m l，其中d∈(0,1]。

定義2 生成合成少數(shù)類實(shí)例數(shù)量為：G=(m lm s)×β，其中，β∈[0,1]是合成實(shí)例后少數(shù)與多數(shù)實(shí)例的比率。如果β=1，則少數(shù)類與多數(shù)類實(shí)例平衡。

定義3少數(shù)類實(shí)例的K最近鄰數(shù)量中多數(shù)實(shí)例的比率：r i=?i/K(i=1,2,……,m s)，?i是K最近鄰數(shù)量中多數(shù)實(shí)例數(shù)量，r i∈[0,1]。

定義4少數(shù)類實(shí)例的K最近鄰數(shù)量中多數(shù)實(shí)例的密度

1.2 算法實(shí)現(xiàn)過(guò)程

為了通過(guò)過(guò)采樣少數(shù)類實(shí)例來(lái)平衡少數(shù)類實(shí)例與多數(shù)類實(shí)例之間的數(shù)量不平衡，需要合成一定數(shù)量的少數(shù)類實(shí)例，同時(shí)也能加強(qiáng)其邊界。本算法步驟是：首先，依據(jù)β確定生成合成少數(shù)類實(shí)例數(shù)量（定義2）；其次，統(tǒng)計(jì)各少數(shù)類實(shí)例的K最近鄰數(shù)量中多數(shù)實(shí)例的比率（定義3）；再次，計(jì)算各個(gè)少數(shù)類實(shí)例的K最近鄰數(shù)量中多數(shù)實(shí)例的密度（定義4）；最后，計(jì)算各個(gè)少數(shù)類實(shí)例對(duì)應(yīng)生成合成實(shí)例數(shù)（定義5）。

因此，越靠近邊界處，少數(shù)類實(shí)例的K最近鄰所含的多數(shù)類實(shí)例就越多，故其密度越高，且合成少數(shù)類實(shí)例也越多。

合成少數(shù)類實(shí)例算法如下：

1.3 β參數(shù)的選取

本算法中測(cè)試數(shù)據(jù)集來(lái)自UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)，具有一定的現(xiàn)實(shí)意義。表1詳細(xì)地描述了數(shù)據(jù)集的特點(diǎn)，其中數(shù)據(jù)集abalone、vowel和shuttle中的少數(shù)類實(shí)例數(shù)量明顯比多數(shù)類實(shí)例數(shù)量少很多，大概只有多數(shù)類實(shí)例的1/10，數(shù)據(jù)集diabetes和spambase中的少數(shù)類實(shí)例也只有多數(shù)類實(shí)例實(shí)例的1/2左右。

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

圖1顯示了合成實(shí)例后少數(shù)與多數(shù)實(shí)例的比率β值對(duì)分類精度的影響，本算法使用基于C4.5分類器的J48決策樹(shù)算法對(duì)表1中的數(shù)據(jù)集經(jīng)過(guò)10次的交叉驗(yàn)證實(shí)驗(yàn)，以少數(shù)類樣本為正類計(jì)算精度，其中K值取為5。由圖1可見(jiàn)，當(dāng)β參數(shù)為1時(shí)，所有數(shù)據(jù)集獲得了最好的精度，且相對(duì)較為穩(wěn)定。

圖1 β對(duì)于分類精度的影響

2 評(píng)價(jià)度量

在評(píng)價(jià)分類性能時(shí)，評(píng)估度量起到了至關(guān)重要的作用。對(duì)不平衡數(shù)據(jù)分類的常用評(píng)價(jià)標(biāo)準(zhǔn)包括AUC、ROC曲線和基于混淆矩陣的度量，比如：查全率、查準(zhǔn)率、Fmeasure和G-mean等。表2所示為在兩類別情況下，將少數(shù)類作為正類，多數(shù)類作為負(fù)類，通過(guò)分類之后，訓(xùn)練集中的實(shí)例可分為混淆矩陣的4種情況。

表2 分類器的混淆矩陣

根據(jù)表2中的混淆矩陣，可計(jì)算出幾個(gè)度量：F-measure（F1）是查全率和查準(zhǔn)率的值的調(diào)和均值，其值接近兩數(shù)的較小者，故而當(dāng)F1值較大時(shí)，說(shuō)明Recall值和Precisi on值都較大。

其中，β是用來(lái)調(diào)整Recall和Precis ion的權(quán)重，通常值設(shè)為1。

如果同時(shí)關(guān)注多數(shù)類和少數(shù)類的性能，即希望負(fù)類率與查全率都取得較好性能，則使用G-mean來(lái)度量?jī)蓚€(gè)的平均性能。

本文將采用OA、F-Measure和G-mean作為評(píng)價(jià)度量。

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

所有實(shí)驗(yàn)是在Weka平臺(tái)環(huán)境上運(yùn)行的，選擇的實(shí)驗(yàn)數(shù)據(jù)集來(lái)自UCI數(shù)據(jù)集，采用C4.5實(shí)現(xiàn)的J48決策樹(shù)算法對(duì)每個(gè)組數(shù)據(jù)集用10-折交叉法驗(yàn)證，采用多種評(píng)估算法來(lái)評(píng)估分類性能。實(shí)驗(yàn)參數(shù)設(shè)置如下：設(shè)置β為1，K為5(K值的選擇最為困難，需要根據(jù)不同的數(shù)據(jù)集的不平衡度及特點(diǎn)進(jìn)行選擇，此處選擇一個(gè)對(duì)大多數(shù)數(shù)據(jù)集都較為適用的值)，不平衡數(shù)據(jù)集中少數(shù)類的比率d設(shè)為0.75。

圖2顯示了在采用MEBMI算法生成合成實(shí)例之前與之后的數(shù)據(jù)集結(jié)果，為了便于顯示，選取數(shù)據(jù)集中2個(gè)屬性進(jìn)行可視化，圖中藍(lán)色代表多數(shù)類，紅色代表少數(shù)類，圖2（a）—圖2（e）的下部分（過(guò)抽樣后）代表已采用MEBMI算法，上半部分（過(guò)抽樣前）代表原始數(shù)據(jù)集。從圖2中可知原始數(shù)據(jù)集中少數(shù)類的數(shù)據(jù)較為稀疏，特別在多數(shù)類數(shù)據(jù)邊界鄰近數(shù)據(jù)的這種稀少性極易引起分類過(guò)程的樣本偏差，但經(jīng)過(guò)MEBMI算法生成合成實(shí)例后，在少數(shù)類數(shù)據(jù)邊界上的樣例明顯增多，且少數(shù)類與多數(shù)類的邊界數(shù)據(jù)更加經(jīng)緯分明，從而減少分類時(shí)樣本偏差。

圖2 5個(gè)數(shù)據(jù)集過(guò)抽樣前后對(duì)比（單位：個(gè)）

圖3 (a)—圖3(e)顯示了采用本算法之前與之后，分別對(duì)五個(gè)數(shù)據(jù)集進(jìn)行分類的情況，從圖中可以看出采用本算法后，當(dāng)數(shù)據(jù)集中多數(shù)類與少數(shù)類數(shù)據(jù)達(dá)到一定平衡，并且多數(shù)類與少數(shù)類的邊界數(shù)據(jù)更加清晰時(shí)，在常用的分類評(píng)價(jià)指標(biāo)查全率、查準(zhǔn)率、F1等明顯高于原始的不平衡數(shù)據(jù)。因此，本算法對(duì)分類預(yù)測(cè)準(zhǔn)確率起到了實(shí)質(zhì)作用。

圖3 過(guò)抽樣前后評(píng)價(jià)指標(biāo)比較

傳統(tǒng)SMOTE算法生成合成實(shí)例是建立在兩個(gè)少數(shù)類原始樣例的連接線上，并不能很好體現(xiàn)樣例的分布情況，特別是在多數(shù)類與少數(shù)類邊界上生成的合成實(shí)例有一定的局限性，也不能很好反映少數(shù)類實(shí)例邊界的真實(shí)分布。本算法MEBMI在生成合成實(shí)例中引入了隨機(jī)參數(shù)，并在合成實(shí)例數(shù)量上加上了權(quán)重系數(shù)來(lái)強(qiáng)調(diào)邊界實(shí)例的重要性，從而進(jìn)一步加強(qiáng)了合成實(shí)例的真實(shí)分布并加固了多數(shù)類與少數(shù)類的邊界界限。

表3所示為本算法與SMOTE算法的評(píng)價(jià)比較。表3中，在多個(gè)不平衡數(shù)據(jù)評(píng)價(jià)方法上，通過(guò)與傳統(tǒng)SMOTE過(guò)抽樣算法進(jìn)行比較，MEBMI算法明顯優(yōu)于傳統(tǒng)SMOTE算法，特別在F-Measur e和G-mean評(píng)價(jià)度量上，本算法獲得了較高的查全率和查準(zhǔn)率，同時(shí)也取得了較高的正類率和負(fù)類率，即提高了多數(shù)類和少數(shù)類的分類準(zhǔn)確率。

表3 本算法與SMOTE算法的評(píng)價(jià)比較

實(shí)驗(yàn)結(jié)果表明，根據(jù)每個(gè)少數(shù)類實(shí)例周圍的密度情況，添加相應(yīng)的權(quán)重系數(shù)，能自動(dòng)調(diào)整生成合成少數(shù)類實(shí)例數(shù)量，且能更加真實(shí)體現(xiàn)少數(shù)類實(shí)例的分布，不但提高了整體準(zhǔn)確率，而且提高了多數(shù)類及少數(shù)類樣例的預(yù)測(cè)能力。

4 結(jié)束語(yǔ)

針對(duì)傳統(tǒng)SMOTE算法在過(guò)抽樣生產(chǎn)合成實(shí)例中存在的一些不足，提出了一種改進(jìn)的過(guò)抽樣算法來(lái)平衡不平衡數(shù)據(jù)，在合成實(shí)例時(shí)引入隨機(jī)參數(shù)，根據(jù)少數(shù)類實(shí)例的密度分布加入權(quán)重，既克服了傳統(tǒng)SMOTE算法少數(shù)類合成實(shí)例的固定性質(zhì)，也能更加真實(shí)地區(qū)分多數(shù)類與少數(shù)類邊界，使得平衡后的整個(gè)少數(shù)類實(shí)例更加真實(shí)有效。實(shí)驗(yàn)測(cè)試結(jié)果表明，在多數(shù)類預(yù)測(cè)評(píng)價(jià)指標(biāo)不受影響且有所提高的情況下，確實(shí)對(duì)少數(shù)類樣本預(yù)測(cè)評(píng)估指標(biāo)產(chǎn)生了良性影響，使分類器能更好地減少由數(shù)據(jù)不平衡帶來(lái)的誤差。