面向不平衡數(shù)據(jù)集的一種精化Borderline-SMOTE方法

楊 毅，盧誠波，徐根海

(麗水學(xué)院 工學(xué)院，麗水 323000)

面向不平衡數(shù)據(jù)集的一種精化Borderline-SMOTE方法

楊 毅，盧誠波，徐根海

(麗水學(xué)院 工學(xué)院，麗水 323000)

合成少數(shù)類過采樣技術(shù)(SMOTE)是一種被廣泛使用的用來處理不平衡問題的過采樣方法，SMOTE方法通過在少數(shù)類樣本和它們的近鄰間線性插值來實現(xiàn)過采樣.Borderline-SMOTE方法在SMOTE方法的基礎(chǔ)上進行了改進，只對少數(shù)類的邊界樣本進行過采樣，從而改善樣本的類別分布.通過進一步對邊界樣本加以區(qū)分，對不同的邊界樣本生成不同數(shù)目的合成樣本，提出了面向不平衡數(shù)據(jù)集的一種精化Borderline-SMOTE方法(RB-SMOTE).仿真實驗采用支持向量機作為分類器對幾種過采樣方法進行比較，實驗中采用了10個不平衡數(shù)據(jù)集，它們的不平衡率從0.0647到0.5360.實驗結(jié)果表明：RB-SMOTE方法能有效地改善不平衡數(shù)據(jù)集的類分布的不平衡性.

不平衡數(shù)據(jù)集；分類；過采樣；支持向量機

不平衡數(shù)據(jù)集在現(xiàn)實生活中廣泛存在，如信用卡欺詐檢測、網(wǎng)絡(luò)攻擊識別、醫(yī)學(xué)疾病診斷識別、文本分類等各個領(lǐng)域均存在不平衡數(shù)據(jù)集[1-2].不平衡數(shù)據(jù)集的主要特性是類分布不平衡性，少數(shù)類的樣本數(shù)量遠小于多數(shù)類的樣本數(shù)量[3].傳統(tǒng)的分類方法如支持向量機、決策樹、貝葉斯網(wǎng)絡(luò)、k近鄰等都是基于整體分類精度最大化而設(shè)計的，這往往導(dǎo)致分類時多數(shù)類的分類精度較高而少數(shù)類的分類精度較低.

但在實際生活當中，少數(shù)類樣本被錯分的代價往往會高于多數(shù)類樣本的錯分代價.如醫(yī)療診斷當中，把病人(少數(shù)類)錯誤地診斷為正常人(多數(shù)類)，將會延誤病情，嚴重的甚至?xí)＜安∪说纳?，因此提高不平衡問題中少數(shù)類樣本的分類性能是一個有意義的研究課題.

目前，對于不平衡問題的解決方法主要從分類算法層面和數(shù)據(jù)層面進行研究.

分類算法層面上，比較常用的方法有代價敏感學(xué)習(xí)[4-5]、單分類器方法[6-7]和集成學(xué)習(xí)方法[8-9].代價敏感學(xué)習(xí)的思想是根據(jù)不平衡數(shù)據(jù)集的樣本數(shù)量對不同的類別賦予不一樣的懲罰參數(shù)，通過提高少數(shù)類樣本的懲罰參數(shù)使得少數(shù)類樣本盡可能地被正確分類[10-11].單類學(xué)習(xí)算法的主要思想是只對目標類的樣本進行學(xué)習(xí)，通過比較新樣本與目標類樣本的相似度判別新樣本是否屬于目標類.Hippo[12]就是一種單類學(xué)習(xí)算法，它利用神經(jīng)網(wǎng)絡(luò)作為分類算法，只對少數(shù)類樣本進行學(xué)習(xí)，從而識別少數(shù)類中存在的模式，并不對少數(shù)類和多數(shù)類進行區(qū)別.集成學(xué)習(xí)方法的基本思想是將若干個弱分類器組合起來，賦予弱分類器不同的權(quán)重整合成一個強分類器.集成學(xué)習(xí)方法中最有代表性的算法之一就是AdaBoost算法，它是在Bossting算法的基礎(chǔ)上發(fā)展起的.

數(shù)據(jù)層面上，是通過某些策略來改變樣本的分布，將不平衡樣本轉(zhuǎn)化為相對平衡分布的狀態(tài)，最簡單的做法就是隨機采樣.隨機采樣主要分為隨機過采樣和隨機欠采樣兩種方式.隨機過采樣指的是通過多次有放回的從少數(shù)類樣本中隨機地抽取數(shù)據(jù)集，增加原始的少數(shù)類樣本數(shù)量，與多數(shù)類樣本構(gòu)成新的相對平衡的新數(shù)據(jù)集.隨機欠采樣正好相反，即通過從多數(shù)類樣本中隨機地選擇部分樣本，與少數(shù)類樣本合成新的數(shù)據(jù)集.

隨機過采樣方法雖然簡單方便，但該方法不能給予樣本新的信息，反而可能會導(dǎo)致過擬合.Chawla等提出了“合成少數(shù)類過采樣技術(shù)”(Synthetic Minority Oversampling Technique,SMOTE)[13]，該方法通過內(nèi)插的方式合成新生的少數(shù)類樣本，能更好地改善不平衡數(shù)據(jù)集的分布.文獻[14]在SMOTE方法的基礎(chǔ)上提出了Borderline-SMOTE方法，該方法把少數(shù)類樣本分為安全樣本、邊界樣本和噪聲樣本3類，并對邊界樣本進行近鄰插值，該方法考慮到了少數(shù)類內(nèi)部的分布不均的現(xiàn)象，但對邊界樣本之間的差異未做考慮.

本文在Borderline-SMOTE方法的基礎(chǔ)上對邊界樣本做了進一步的精細化，提出了面向不平衡數(shù)據(jù)集的一種精化Borderline-SMOTE方法(Refined Borderline-SMOTE,RB-SMOTE).根據(jù)邊界樣本的具體分布，對其設(shè)置不同的過采樣倍率，再通過近鄰插值增加少數(shù)類樣本的數(shù)量，進一步改善數(shù)據(jù)集的不平衡分布.

1 相關(guān)工作

1.1SMOTE方法

假設(shè)原始訓(xùn)練樣本為T，其少數(shù)類為P，多數(shù)類為N，且P={p1,p2,…,pi,…，pp num}，N={n1,n2,…,ni,…,nn mum}，其中pnum,nmum分別表示少數(shù)類樣本個數(shù)和多數(shù)類樣本個數(shù).SMOTE方法可描述如下.

步1 計算少數(shù)類樣本中的每個樣本點pi與少數(shù)類樣本P的歐氏距離，獲得該樣本點的k近鄰.

步2 根據(jù)采樣倍率U，在k近鄰中選擇合適的個數(shù)s，pi與s個近鄰進行線性插值.

步3 合成新的少數(shù)類樣本syntheticj=pi+rj×dj(j=1,2,…,s)，其中：dj表示pi與其s個近鄰的距離；rj是介于0與1之間的隨機數(shù).

步4 新合成的少數(shù)類樣本與原始訓(xùn)練樣本T合并，構(gòu)成新的訓(xùn)練樣本T′.

該方法合成新生樣本的規(guī)則賦予了少數(shù)類樣本更多的新信息，避免了隨機過采樣的盲目性學(xué)習(xí).

1.2Borderline-SMOTE方法

Borderline-SMOTE是在SMOTE基礎(chǔ)上發(fā)展起來的一種過采樣方法，具體步驟描述如下.

步1 計算少數(shù)類樣本中的每個樣本點pi與所有訓(xùn)練樣本的歐氏距離，獲得該樣本點的m近鄰.

步4 合成的少數(shù)類樣本與原始訓(xùn)練樣本T合并，構(gòu)成新的訓(xùn)練樣本T′.

與SMOTE方法相比，Borderline-SMOTE方法只針對邊界樣本進行近鄰線性插值，使得合成后的少數(shù)類樣本分布更為合理.

2 RB-SMOTE方法的具體步驟

不平衡數(shù)據(jù)的分類學(xué)習(xí)過程中，其邊界類的點更容易被錯誤地分類，因此很多分類算法在訓(xùn)練過程中都嘗試對其邊界的樣本點進行重點學(xué)習(xí)[14].本文在Borderline-SMOTE的基礎(chǔ)上對少數(shù)類中的邊界樣本加以區(qū)分，選取合適的采樣倍率，精細化分配新生成的樣本數(shù)量，該方法稱之為精化Borderline-SMOTE方法(RB-SMOTE)，根據(jù)過采樣倍率的取法不同，我們分別提出RB-SMOTE1和RB-SMOTE2兩種方法.

下面給出RB-SMOTE1的具體步驟.

步1 計算少數(shù)類樣本與訓(xùn)練樣本的近鄰.

計算少數(shù)類樣本P的樣本點pi(i=1,2,…,pnum)在原始訓(xùn)練樣本T中的m近鄰，設(shè)在m近鄰中有m′個屬于多數(shù)類樣本，顯然0≤m′≤m.

步2 對少數(shù)類樣本進行劃分：

若m′=m，表示pi的所有m近鄰都屬于多數(shù)類樣本，此時pi被認為是噪聲；

若m/t≤m′

若0≤m′

步3 設(shè)置采樣倍率Ui(i=1，2，…，pnum).

步4 邊界樣本與少數(shù)類樣本插值合成新生的少數(shù)類樣本.

步5 合成的少數(shù)類樣本與原始訓(xùn)練樣本T合并，構(gòu)成新的訓(xùn)練樣本T′.

RB-SMOTE2在第3步設(shè)置采樣倍率時與RB-SMOTE1有所不同.RB-SMOTE2的第3步具體描述如下：

RB-SMOTE1與RB-SMOTE2的基本思想是一致的，都是對少數(shù)類樣本中的邊界樣本加以區(qū)別，“按需分配”設(shè)置不同的采樣倍率，使得接近于多數(shù)類樣本的少數(shù)類邊界樣本的采樣倍率更高，合成的少數(shù)類樣本分布更為合理，從而提高分類器的分類效果.

圖1為未經(jīng)處理的原始數(shù)據(jù)集的分布，圖2～圖4為分別使用SMOTE、Borderline-SMOTE和RB-SMOTE等方法處理后的數(shù)據(jù)集的分布.

圖1 原始數(shù)據(jù)分布Fig.1 The original distribution of data

圖2 SMOTE方法合成新的樣本Fig.2 New samples synthesized by SMOTE method

圖3 Borderline-SMOTE方法合成新的樣本Fig.3 New samples synthesized by Borderline-SMOTE method

圖4 RB-SMOTE方法合成新的樣本Fig.4 New samples synthesized by RB-SMOTE method

以下分別用SMOTE、Borderline-SMOTE和RB-SMOTE3個過采樣算法增加少數(shù)類樣本點，合成訓(xùn)練樣本，并把圖1中的少數(shù)類樣本點從8個增加到24個，以達到少數(shù)類樣本點與多數(shù)類樣本點在數(shù)量上的平衡.

圖2中“△”表示原始少數(shù)類樣本與其近鄰合成的少數(shù)類樣本.采樣倍率U=2，即與其近鄰合成新生的少數(shù)類樣本點有16個.此時，“*”的k近鄰所包含的多數(shù)類樣本點的個數(shù)仍然大于少數(shù)類樣本點的個數(shù)，用k近鄰方法判斷其類別時，還是會錯誤地將“*”判斷為多數(shù)類樣本.

從這個例子可以看出，對少數(shù)類邊界樣本進行精細化處理，能進一步改善數(shù)據(jù)集的不平衡分布.

3 仿真實驗

實驗采用5折交叉驗證法，運行20次，取平均值.使用的仿真軟件為Matlab R2012a，實驗的環(huán)境為：Windows10 64bit操作系統(tǒng)，Intel Core i7-2620M 2.70GHz,12GB內(nèi)存.利用支持向量機(Support Vector Machine,SVM)作為分類器，分類過程中選取核寬為0.8的徑向基核.

表1 數(shù)據(jù)集的描述Tab.1 Description of datasets

3.1測試數(shù)據(jù)集描述

實驗選取了不平衡率不一的10個數(shù)據(jù)集，分別來源于UCI數(shù)據(jù)庫(https:∥archive.ics.uci.edu/ml/index.html)和KEEL數(shù)據(jù)庫(http:∥sci2s.ugr.es/keel/study.php?cod=24)，具體描述見表1.表1中的不平衡率(Imbalance Ratio，IR)反映了數(shù)據(jù)集各類之間的不平衡程度，對于二分類集，不平衡率

(1)

數(shù)據(jù)預(yù)處理將訓(xùn)練集和測試集歸一化到[0，1]區(qū)間.

3.2不平衡數(shù)據(jù)集分類的評價準則

在對不平衡數(shù)據(jù)集進行分類時，不能簡單地采用整體精度的高低來評價分類器的好壞.這是因為在不平衡數(shù)據(jù)集中各類的樣本數(shù)量相差較大，如果分類器能夠完全識別多數(shù)類樣本，即使對少數(shù)類樣本的識別完全錯誤，總體的分類精度也會維持在一個較高的水準.目前常用的評價標準有查全率、查準率、G-mean值、F-value等.

表2 二分類不平衡數(shù)據(jù)的混合矩陣Tab.2 Confusion matrix of two-class datasets

表2給出了二分類不平衡數(shù)據(jù)的混合矩陣，它是評價分類性能的一種常用方法.表2中TP表示少數(shù)類被準確分類的樣本個數(shù)，F(xiàn)N表示少數(shù)類被錯誤分類的樣本個數(shù)，F(xiàn)P表示多數(shù)類被錯誤分類的樣本個數(shù)，TN表示多數(shù)類被正確分類的樣本個數(shù).

查全率：

(2)

另外，

(3)

查準率：

(4)

G-mean值：

(5)

綜合查全率和查準率的F值：

(6)

其中G-mean值是少數(shù)類樣本和多數(shù)類樣本的分類準確度的乘積，它從整體上綜合分析了兩類分類準確度[15]，只有當rTP，rTN都比較大時，G-mean值才會比較高.Fvalue中的β≥0并且可以調(diào)節(jié)，通常是取β=1的情況，只有當查全率和查準率都比較高時，F(xiàn)value才會高.

以下分別用SMOTE、Borderline-SMOTE、RB-SMOTE 1和RB-SMOTE 2方法把10個數(shù)據(jù)集的不平衡率提高到1，利用SVM對合成后的數(shù)據(jù)集進行分類，結(jié)果見表3.

表3 各種方法的G-mean值比較Tab.3 Comparison of G-mean values of various methods

從表3可以看出，各種方法和未做處理的方法相比，G-mean值都有很大地提高，相比之下，RB-SMOTE方法表現(xiàn)得更好一些.RB-SMOTE1方法和RB-SMOTE2方法沒有明顯區(qū)別.

以下分別對Glass4、Ecoli1、Haberman、Pima 4個數(shù)據(jù)集使用SMOTE、Borderline-SMOTE、RB-SMOTE1、RB-SMOTE2這4種過采樣方法，逐步增加合成樣本的個數(shù)，并利用SVM進行分類，圖5～圖12分別刻畫了Fvalue與rTP的數(shù)據(jù)比較.

圖5 4種方法在Glass4數(shù)據(jù)集上Fvalue的比較Fig.5 Comparison of Fvalue of 4 methods on Glass4

圖6 4種方法在Glass4數(shù)據(jù)集上rTP的比較Fig.6 Comparison of rTP of 4 methods on Glass4

圖7 4種方法在Ecoli1數(shù)據(jù)集上Fvalue的比較Fig.7 Comparison of Fvalue of 4 methods on Ecoli1

圖8 4種方法在Ecoli1數(shù)據(jù)集上rTP的比較Fig.8 Comparison of rTP of 4 methods on Ecoli1

圖9 4種方法在Haberman數(shù)據(jù)集上Fvalue的比較Fig.9 Comparison of Fvalue of 4 methods on Haberman

圖10 4種方法在Haberman數(shù)據(jù)集上rTP的比較Fig.10 Comparison of rTP of 4 methods on Haberman

由圖5～圖12可以看出，對于這4種方法來說，隨著少數(shù)類樣本個數(shù)的增加，F(xiàn)value與rTP均有增加的趨勢，當合成樣本數(shù)量剛開始增加時，F(xiàn)value與rTP都增加的較快，但當合成樣本數(shù)量增加到一定數(shù)量后Fvalue與rTP的變化就趨于平緩.比較各圖的Fvalue與rTP數(shù)據(jù)，總體來說RB-SMOTE1、RB-SMOTE2兩種方法取得了更好的效果.

圖11 4種方法在Pima數(shù)據(jù)集上Fvalue的比較Fig.11 Comparison of Fvalue of 4 methods on Pima

圖12 4種方法在Pima數(shù)據(jù)集上rTP的比較Fig.12 Comparison of rTP of 4 methods on Pima

4 結(jié) 語

本文在Borderline-SMOTE方法的基礎(chǔ)上，進一步精細化邊界樣本的采樣倍率，提出了RB-SMOTE方法，該方法使得不平衡數(shù)據(jù)的分布得到進一步改善，代價是增加了采樣方法的復(fù)雜度，但這仍然是可以接受的.仿真實驗的結(jié)果進一步驗證了RB-SMOTE方法能夠有效地提高不平衡數(shù)據(jù)集的少數(shù)類的分類性能和整體的分類性能.

[1] TRIVEDI I,MONIKA,MRIDUSH M.Credit card fraud detection [J].InternationalJournalofAdvancedResearchinComputerandCommunicationEngineering,2016,5(1)：39-50.

[2] BAHNSEN A C,AOUADA D,STOJANOVIC A,etal.Feature engineering strategies for credit card fraud detection [J].ExpertSystemswithApplications,2016,51:134-142.

[3] WEISS G M.Mining with rarity: A unifying framework [J].SIGKDDExplorations,2004,6(1):7-19.

[4] HUANG Y.Cost-sensitive incremental classification under the map reduce framework for mining imbalanced massive data streams [J].JournalofDiscreteMathematicalSciences&Cryptography，2015,18(1-2):177-194.

[5] HUANG Y.Dynamic cost-sensitive ensemble classification based on extreme learning machine for mining imbalanced massive data streams [J].InternationalJournalofu-ande-Service,ScienceandTechnology,2015,8(1):333-346.

[6] ZHU W X,ZHONG P.A new one-class SVM based on hidden information [J].Knowledge-BasedSystems,2014,60(2): 35-43.

[7] WANG T,CHEN J,ZHOU Y,etal.Online least squares one-class support vector machines-based abnormal visual event detection [J].Sensors,2013,13(12):17130-17155.

[8] SCHAPIRE R E.A brief introduction to boosting [C]∥Proceedings of the Sixteenth International Joint Conference on Artificial intelligenc.San Francisco: Morgan Kaufmann Publishers Inc,1999:1401-1406.

[9] FREUND Y,SCHAPIRE R.Experiments with a new Bossting algorithm [C]∥Proceedings of the Thirteenth International Conference on Machine Learning.San Francisco：Morgan Kaufmann Publishers Inc,1996:148-156.

[10] OUSSALAH M.A new classification strategy for human activity recognition using cost sensitive support vector machines for imbalanced data [J].Kybernetes,2014,43(8):1150-1164.

[11] ZONG W W,HUANF G B,CHEN Y Q.Weighted extreme learning machine for imbalance learning [J].Neurocomputing,2013,101(3)：229-242.

[12] JAPKOWICZ N,MYERS C,GLUCK M A.A novelty detection approach to classification [C]∥Proceedings of the fourteenth Joint Conference on Artificial Intelligence.San Francisco: Morgan Kaufmann Publishers Inc,1995:518-523.

[13] CHAWLA N V,BOWYER K W,HALL L O,etal.SMOTE: Synthetic minority over-sampling technique [J].JournalofMachineLearningResearch,2002,16:321-357.

[14] WAN K J,ADRIAN A M,CHEN K H,etal.A hybrid classifier combining borderline-SMOTE with AIRS algorithm for estimating brain metastasis from lung cancer: A case study in China Taiwan [J].ComputerMethods&ProgramsinBiomedicine,2015,119(2):63-76.

[15] YEN S J,LEE Y S.Cluster-based under-sampling approaches for imbalanced data distributions [J].ExpertSystemswithApplications,2009,36(3):5718-5727.

ARefinedBorderline-SMOTEMethodforImbalancedDataSet

YANGYi,LUChengbo,XUGenhai

(FacultyofEngineering,LishuiUniversity,Lishui323000,China)

One of the most popular over-sampling approaches to deal with the class imbalance problem is SMOTE(Synthetic Minority Over-sampling Technique),which generated new synthetic samples along the line between the minority examples and their selected nearest neighbors.Based on SMOTE method,borderline-SMOTE only over-samples the minority samples near the borderline.In this paper,we propose a refined borderline-SMOTE(RB-SMOTE) method which generates different number of new synthetic samples according to different borderline minority samples.In experiments,SVMs are used as classifiers,the proposed RB-SMOTE method is evaluated on 10 imbalanced datasets whose imbalance ratios vary from drastic 0.0647 to 0.5360 and is shown to be very effective to improve the performance of classification of imbalance data sets.

imbalanced data set; classification; over sampling; support vector machine

0427-7104(2017)05-0537-08

2016-08-23

浙江省自然科學(xué)基金(LY18F030003)；國家自然科學(xué)基金(61373057)

楊 毅(1980—)，女，講師，碩士；盧誠波(1977—)，男，副教授，博士，通信聯(lián)系人， E-mail: lu.chengbo@aliyun.com.

TP183;TP181

A