一種新的過采樣算法DB_SMOTE

劉余霞，劉三民，劉濤，王忠群

1.安徽工程大學(xué)建筑工程學(xué)院，安徽蕪湖 241000

2.安徽工程大學(xué)計算機(jī)與信息學(xué)院，安徽蕪湖 241000

3.南京航空航天大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，南京 210016

4.安徽工程大學(xué)管理工程學(xué)院，安徽蕪湖 241000

◎數(shù)據(jù)庫、數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)◎

一種新的過采樣算法DB_SMOTE

劉余霞1，劉三民2，3，劉濤2，王忠群4

1.安徽工程大學(xué)建筑工程學(xué)院，安徽蕪湖 241000

2.安徽工程大學(xué)計算機(jī)與信息學(xué)院，安徽蕪湖 241000

3.南京航空航天大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，南京 210016

4.安徽工程大學(xué)管理工程學(xué)院，安徽蕪湖 241000

針對非平衡數(shù)據(jù)集中類分布信息不對稱現(xiàn)象，提出一種新的過采樣算法DB_SMOTE（Distance-based Synthetic Minority Over-sampling Technique），通過合成少數(shù)類新樣本解決樣本不足問題。算法基于樣本與類中心距離，結(jié)合類聚集程度提取種子樣本。根據(jù)SMOTE（Synthetic Minority Over-sampling Technique）算法思想，在種子樣本上實(shí)現(xiàn)少數(shù)類新樣本合成。根據(jù)種子樣本與少數(shù)類中心距離構(gòu)造新樣本分布函數(shù)?；诖瞬蓸铀惴ú⒃诙鄠€數(shù)據(jù)集上進(jìn)行分類實(shí)驗(yàn)，結(jié)果表明DB_SMOTE算法是可行的。

非平衡數(shù)據(jù)學(xué)習(xí)；過采樣；數(shù)據(jù)分類

1 引言

非平衡數(shù)據(jù)學(xué)習(xí)（Imbalanced Data Learning，IDL）是指學(xué)習(xí)的數(shù)據(jù)集類別分布不均勻，其中某類樣本數(shù)量在整個數(shù)據(jù)集內(nèi)占據(jù)絕對優(yōu)勢。這一現(xiàn)象廣泛存在各種領(lǐng)域，如醫(yī)療診斷、故障檢測、金融欺詐等[1]。而傳統(tǒng)機(jī)器學(xué)習(xí)算法均是基于樣本分布均勻基礎(chǔ)之上建立的，直接遷移到非平衡數(shù)據(jù)學(xué)習(xí)環(huán)境是不可取的。

非平衡數(shù)據(jù)學(xué)習(xí)的關(guān)鍵問題是如何彌補(bǔ)少數(shù)類樣本在分布信息方面不足的問題，常用方法包括數(shù)據(jù)采樣、代價敏感學(xué)習(xí)、集成學(xué)習(xí)、主動學(xué)習(xí)等[1]。基于數(shù)據(jù)層面的采樣方法簡單、直觀，倍受研究人員青睞。數(shù)據(jù)采樣主要包括過采樣和欠采樣兩種途徑。在過采樣研究中，由Chawla等[2]提出的SMOTE算法成為經(jīng)典，現(xiàn)有很多算法均是基于此原型提出。SMOTE算法是通過尋找樣本的近鄰集，從近鄰集中隨機(jī)選擇樣本與之形成線，并在線上合成新樣本點(diǎn)。為避免SMOTE算法樣本覆蓋問題，文獻(xiàn)[3]提出Borderline-SMOTE算法，它尋找少數(shù)類當(dāng)中“危險”樣本，基于此類樣本合成新樣本。在此基礎(chǔ)上，文獻(xiàn)[4]根據(jù)樣本的“危險”程度，構(gòu)造出合成新樣本的分布函數(shù)，來決定依據(jù)各“危險”樣本合成新樣本的個數(shù)。文獻(xiàn)[5]實(shí)現(xiàn)了基于聚類的抽樣算法CBO（Cluster-based Over-sampling），它適合于類分布中含有多個不連接的聚集點(diǎn)情況。文獻(xiàn)[6]通過保留多數(shù)類邊界附近樣本，實(shí)現(xiàn)欠采樣策略，其中難題是鄰域半徑難以確定。結(jié)合抽樣技術(shù)，Chawla等提出SMOTEBoost算法，它在每次迭代中引入合成樣本，保證各子分類器更多地獲取少數(shù)類樣本信息，使集成分類器獲得更優(yōu)性能[7]。RUSBoost算法應(yīng)用隨機(jī)欠采樣從多數(shù)類中隨機(jī)移出樣本形成多個子分類器進(jìn)行集成，該算法簡單易實(shí)現(xiàn)[8]。李雄飛等[9]提出分類算法PCBoost，它用隨機(jī)采樣方式的數(shù)據(jù)合成方法，平衡樣本分布信息，同時具備及時“擾動修正”和刪除錯分合成樣本的功能。文獻(xiàn)[10]結(jié)合遷移技術(shù)和集成學(xué)習(xí)解決了樣本非平衡問題，在學(xué)習(xí)過程中通過樣本權(quán)重的動態(tài)調(diào)整和冗余樣本的淘汰策略保證分類器的性能。文獻(xiàn)[11]在特征空間合成新樣本，引入核的方法實(shí)現(xiàn)空間轉(zhuǎn)換，保證合成樣本的質(zhì)量，有效提高了SVM的分類效果。文獻(xiàn)[12]針對SMOTE采樣算法的不足，將支持度概念和輪盤選擇技術(shù)，并結(jié)合異類近鄰的分布信息實(shí)現(xiàn)對少數(shù)樣本合成。為解決集成學(xué)習(xí)對少數(shù)類樣本分類準(zhǔn)確率不高問題，把Bagging集成學(xué)習(xí)和SMOTE過采樣方法相結(jié)合，提高了少數(shù)類分類準(zhǔn)確率[13]。

上述文獻(xiàn)所涉及的數(shù)據(jù)合成大多是基于K-近鄰思想，計算量較大，易受噪聲問題影響。本文通過用樣本距離結(jié)合類的聚集程度（類平均距離），提出一種新的非平衡數(shù)據(jù)集學(xué)習(xí)算法DB_SMOTE。算法依據(jù)是假設(shè)凡位于類邊緣的樣本更有助于形成分類邊界，通過直接比較樣本與類中心距離和聚集程度相比得到種子樣本，并在種子樣本和類中心的連線上合成新樣本，實(shí)現(xiàn)過采樣策略。

2 非平衡數(shù)據(jù)集學(xué)習(xí)算法DB_SMOTE

為便于討論，本文主要關(guān)注只有兩類樣本的非平衡數(shù)據(jù)學(xué)習(xí)問題，且規(guī)定少數(shù)類樣本為正類樣本，多數(shù)類樣本為負(fù)類樣本。算法DB_SMOTE主要包括三個階段：首先是尋找少數(shù)類種子樣本；其次是構(gòu)建合成樣本的分布函數(shù)；最后是結(jié)合平衡因子和分布函數(shù)實(shí)現(xiàn)過采樣。

2.1 少數(shù)類樣本數(shù)據(jù)合成

為便于敘述，首先給出下列相關(guān)定義。

設(shè)某類樣本集合S={di，i=1，2，…，n}，其中di表示m維向量，維數(shù)大小代表樣本特征個數(shù)。

定義1類中心（class center）是指某類樣本在數(shù)據(jù)空間的平均中心點(diǎn)。類中心點(diǎn)cc是與樣本維數(shù)相同的向量，計算方法如公式（1）所示：

定義2類平均距離（class average distance）是指某類中各樣本到類中心距離和的平均值，是一標(biāo)量。該距離cd能夠反映出類的聚集程度，值越小類聚集程度越緊，反之較松散。計算如下式所示：

其中函數(shù)D(，)表示歐氏距離計算方法。

基于過采樣策略的新樣本生成關(guān)鍵是找出種子樣本，在此基礎(chǔ)上迭代生成新樣本。在樣本分類過程中，位于類邊緣的樣本是最易出現(xiàn)分類錯誤的，因此其所擁有的分類信息是最多的。在本文結(jié)合類平均距離很容易定義出所需要的種子樣本。

定義3種子樣本（seed sample）指樣本到類中心距離大于類平均距離的樣本。計算如公式（3）所示：

由種子樣本構(gòu)成的樣本集稱為侯選集（candidate set）。為避免在合成樣本中引入過多的噪聲，本文結(jié)合現(xiàn)有文獻(xiàn)進(jìn)行改進(jìn)：指定類中心作為參照點(diǎn)，由侯選集內(nèi)樣本與參照點(diǎn)形成線段，在線段內(nèi)合成新樣本，保證合成樣本位于類的內(nèi)側(cè)。根據(jù)SMOTE算法思想，本文算法合成新樣本（synthetic new sample）生成公式如式（4）所示：

其中si屬于侯選集內(nèi)樣本，r是取值于[0，1]之間的隨機(jī)數(shù)。

由前文所述可知，侯選集內(nèi)的樣本與類中心的距離越遠(yuǎn)，其所帶有效信息相對較多。因此基于此類樣本合成新樣本個數(shù)應(yīng)該越多，越有利于提高分類模型的精度。據(jù)此算法利用距離信息，構(gòu)造出合成樣本分布函數(shù)。

若侯選集cs={csi，i=1，2，…，k}，根據(jù)歐氏距離計算方法易得出每個樣本到中心的距離D(csi，cc)，表示侯選集中第i個樣本與類中心cc間距離，累加可得距離和s。在此基礎(chǔ)上可以得出分布函數(shù)P，具體如公式（5）所示：

把樣本分布概率值乘以樣本合成總數(shù)即可得到基于每個侯選樣本合成新樣本的個數(shù)。

2.2 算法實(shí)現(xiàn)

在上述合成策略的基礎(chǔ)上，可得出具體的學(xué)習(xí)算法DB_SMOTE。

設(shè)樣本集合DS={(di，ci)，i=1，2，…，n}，其中di表示樣本向量，ci表示樣本所屬類別。在本文中以二類問題作為研究對象，ci取值設(shè)定為0和1。

算法：DB_SMOTE(DS，L，σ)

輸入：數(shù)據(jù)集DS，學(xué)習(xí)器L，平衡因子σ

步驟：

（1）調(diào)用分層抽樣對數(shù)據(jù)集DS進(jìn)行處理，形成訓(xùn)練集(tr)和測試集(ts)。

（2）對訓(xùn)練集tr進(jìn)行統(tǒng)計得到少數(shù)類樣本集min和多數(shù)類樣本集maj。

（3）根據(jù)公式（1）和公式（2）求出少數(shù)類樣本中心cc和類平均距離cd。

（4）計算合成樣本總數(shù)num=(|maj|-|min|)*σ。

（5）由公式（3）可得到侯選集cs，在此基礎(chǔ)上根據(jù)公式（5）得到概率分布函數(shù)。

（6）fori=1，|cs|

（7）forj=1，Int(pi*num)

（8）產(chǎn)生隨機(jī)數(shù)r

（9）根據(jù)公式（4）合成新樣本sns

（10）tr=tr∪sns

（11）得到分類模型L(tr)，并在ts測試。

算法中Int（）函數(shù)表示取整。平衡因子σ決定合成樣本總數(shù)，根據(jù)需要可自由設(shè)定。在本文中，平衡因子σ取值為1，保證過采樣后的訓(xùn)練集是平衡的。

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

為驗(yàn)證文中所提算法的可行性，實(shí)驗(yàn)時同另外三種方法（未采樣、SMOTE、Borderline_SMOTE）在九個數(shù)據(jù)集上針對分類器的F-value和G-mean進(jìn)行對比分析。

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

實(shí)驗(yàn)中九個實(shí)驗(yàn)數(shù)據(jù)集源自UCI公開數(shù)據(jù)集。每個數(shù)據(jù)集的樣本總數(shù)、少數(shù)類樣本和多數(shù)類樣本等詳細(xì)信息如表1所示。其中數(shù)據(jù)集yeast_I（CYT和EXC）、yeast_II（NUC和VAC）和yeast_III（MIT和POX）均來自UCI中yeast數(shù)據(jù)集，它們分別由原數(shù)據(jù)集中的樣本構(gòu)成。原數(shù)據(jù)集wine中包含三類樣本，本文實(shí)驗(yàn)過程中把前兩類合并成一類。

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

由文獻(xiàn)[9，14]可知，數(shù)據(jù)集中兩類樣本數(shù)比例超過1∶2，即可認(rèn)為數(shù)據(jù)集是不平衡的。

3.2 評價度量

由于數(shù)據(jù)集的非平衡性，按照傳統(tǒng)方法用準(zhǔn)確率來衡量分類器的性能是不合適的。為客觀、公正地評價分類器的性能，滿足實(shí)際需求（人們常常更關(guān)注的是少數(shù)類的分類情況），應(yīng)尋求新的度量參數(shù)。

文中分類器性能評價參數(shù)是基于表2所示的混淆矩陣定義所得到。

表2 混淆矩陣

由表2很容易得出分類模型的準(zhǔn)確率（accuracy）、精度（precision）、召回率（recall）等概念。

而F-value是精度和召回率的調(diào)和均值，其值接近兩數(shù)的較小者。在非平衡數(shù)據(jù)學(xué)習(xí)中用F-value能全面反映分類器性能，因?yàn)橹挥挟?dāng)精度和召回率均較大時，F(xiàn)-value才會變大，滿足實(shí)際需求。計算方法如公式（7）所示：

在公式（7）中參數(shù)β通常取值1，用以調(diào)節(jié)兩個參數(shù)的重要程度。

若要同時衡量分類器對兩類樣本分類平均性能，可以用G-mean參數(shù)度量，它是兩類召回率的幾何平均值。

綜上，本文在進(jìn)行算法對比時，主要關(guān)注少數(shù)類的F-value值和分類器的G-mean值。

3.3 實(shí)驗(yàn)數(shù)據(jù)分析

本文的仿真實(shí)驗(yàn)均是基于Weka平臺在Eclipse環(huán)境中實(shí)現(xiàn)，記錄了學(xué)習(xí)器（決策樹）在四種實(shí)驗(yàn)方案下的實(shí)驗(yàn)數(shù)據(jù)，即未采樣方案、SMOTE采樣、Borderline_SMOTE采樣和本文的采樣方案。其中學(xué)習(xí)器決策樹是用Weka平臺內(nèi)的J48算法，采用默認(rèn)參數(shù)設(shè)置。由于每個算法中具有隨機(jī)因子，所以每種算法在各數(shù)據(jù)集上運(yùn)行五次，取其平均值作為結(jié)果比較。同原文獻(xiàn)相似，算法SMOTE和Borderline_SMOTE中的K-近鄰參數(shù)均取值為5。

為便于對比算法的優(yōu)勢，圖1和圖2分別表示四種學(xué)習(xí)策略在九個數(shù)據(jù)集上的F-value和G-mean變化趨勢曲線，其中橫坐標(biāo)表示每種具體的實(shí)驗(yàn)方案。圖中九個數(shù)據(jù)集上的曲線表明，本文提出的DB_SMOTE算法是可行的。分類器的F-value值和G-mean值均得到顯著提升，說明通過對少數(shù)類樣本的合成能夠彌補(bǔ)信息不足問題，且其分類器指標(biāo)值均大于未采樣和SMOTE采樣方案，表明本文的算法在樣本合成精度方面優(yōu)于其他算法。圖1主要反映分類器在少數(shù)類樣本上的F-value值，各個數(shù)據(jù)集通過DB_SMOTE過采樣后，其F-value值均得到改善。對于三個嚴(yán)重不平衡數(shù)據(jù)集yeast，四種實(shí)驗(yàn)方案的F-value值變化較大，只有本文的實(shí)驗(yàn)方案F-value值均得到提高，說明在數(shù)據(jù)嚴(yán)重不平衡的環(huán)境下，其他采樣算法并不能充分地彌補(bǔ)少數(shù)類樣本分布信息。從九個數(shù)據(jù)集上的實(shí)驗(yàn)數(shù)據(jù)變化情況分析看，SMOTE、Borderline_SMOTE過采樣算法并不是很穩(wěn)定，它們在某些數(shù)據(jù)集上的F-value值比未采樣方案還要低。從圖2的G-mean值曲線也能得到相似的結(jié)論，九個數(shù)據(jù)集通過DB_SMOTE過采樣后，其G-mean值相比未采樣情況均能得到提升。由前文所述可知，G-mean是用來反映分類器針對兩類樣本綜合分類情況。由圖2可知，DB-SMOTE采樣方案能夠彌補(bǔ)少數(shù)類樣本信息，同時又不影響多數(shù)類樣本信息的表示，相比其他方案來說比較穩(wěn)定。結(jié)合圖表和上述分析可知，不合適的采樣策略并不能明顯提高分類器的相關(guān)性能，同時也說明了DB_SMOTE算法具有更好的適應(yīng)性。

圖1 F_value變化曲線圖

圖2 G-mean變化曲線圖

4 結(jié)束語

針對非平衡數(shù)據(jù)學(xué)習(xí)問題，文中通過改變傳統(tǒng)求K-近鄰的方法，結(jié)合樣本距離和類聚集特點(diǎn)提出了DB_SMOTE算法。算法的關(guān)鍵是提取到種子樣本和構(gòu)建合成樣本分布函數(shù)。從實(shí)驗(yàn)數(shù)據(jù)分析可知，該算法能夠解決非平衡數(shù)據(jù)學(xué)習(xí)問題。目前非平衡數(shù)據(jù)學(xué)習(xí)問題，主要考慮的是靜態(tài)數(shù)據(jù)環(huán)境，如何解決在數(shù)據(jù)流環(huán)境下的非平衡數(shù)據(jù)學(xué)習(xí)將是研究問題之一。同時，噪聲問題的處理也是非平衡數(shù)據(jù)學(xué)習(xí)問題難點(diǎn)。

[1]He Haibo，Garcia E A.Learning from imbalanced data[J]. IEEE Transactions on Knowledge and Data Engineering，2009，21（9）：1263-1284.

[2]Chawla N V，Bowyer K W，Hall L O，et al.SMOTE：Synthetic Minority Over-sampling Technique[J].Journal of Artificial Intelligence Research，2002，16：321-357.

[3]Han H，Wan W Y，Mao B H.Borderline-SMOTE：a new over-sampling method in imbalanced data sets learning[C]// LNCS 3644：ICIC 2005，Part I，2005：878-887.

[4]He H，Bai Y，Garcia E A，et al.ADASYN：adaptive synthetic sampling approach for imbalanced learning[C]//Proc of the International Joint Conference on Neural Networks，2008：1322-1328.

[5]Jo T，Japkowicz N.Class imbalances versus small disjuncts[J].ACM SIGKDD Explorations Newsletter，2004，6（1）：40-49.

[6]程險峰，李軍，李雄飛.一種基于欠采樣的非平衡數(shù)據(jù)分類算法[J].計算機(jī)工程，2011，37（13）：147-149.

[7]Chawla N V，Lazarevic A，Hall L O，et al.SMOTEBoost：improving prediction of the minority class in boosting[C]// Proc of the 7th European Conf Principles and Practice of Knowledge Discovery in Databases，Cavtat-Dubrovnik，Croatia，2003：107-119.

[8]Seiffert C，Kboshgoftaar T M，Hulse J V，et al.RUSBoost：improving classification performance when training data is skewed[C]//Proc of the 19th IEEE International Conference on Pattern Recognition，Tampa，F(xiàn)L，USA，2008：1-4.

[9]李雄飛，李軍，董元方，等.一種新的非平衡數(shù)據(jù)學(xué)習(xí)方法PCBoost[J].計算機(jī)學(xué)報，2012，35（2）：202-209.

[10]于重重，田蕊，譚勵，等.非平衡樣本分類的集成遷移學(xué)習(xí)算法[J].電子學(xué)報，2012（7）：1358-1364.

[11]曾志強(qiáng)，吳群，廖備水.一種基于核SMOTE的非平衡數(shù)據(jù)集分類方法[J].電子學(xué)報，2009（11）：2489-2496.

[12]王超學(xué)，潘正茂，董麗麗，等.基于改進(jìn)SMOTE的非平衡數(shù)據(jù)集分類研究[J].計算機(jī)工程與應(yīng)用，2013，49（2）：184-187.

[13]李明方，張化祥.針對不平衡數(shù)據(jù)的Bagging改進(jìn)算法[J].計算機(jī)工程與應(yīng)用，2013，49（2）：40-42.

[14]Orriols-Puig A，Bernado-Mansilla E.Evolutionary rulebased systems for imbalanced data sets[J].Soft Computing，2009，13（3）：213-225.

LIU Yuxia1,LIU Sanmin2，3,LIU Tao2,WANG Zhongqun4

1.College of Civil Engineering and Architecture,Anhui Polytechnic University,Wuhu,Anhui 241000,China
2.College of Computer and Information,Anhui Polytechnic University,Wuhu,Anhui 241000,China
3.College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China
4.College of Management and Engineering,Anhui Polytechnic University,Wuhu,Anhui 241000,China

In order to solve the asymmetry of class distribution information in imbalanced data,DB_SMOTE（Distance-based Synthetic Minority Over-sampling Technique）algorithm is presented by minority new sample synthetic.According to the distance between sample and the centre of class,seed sample is gained by combining class aggregation.Based on SMOTE（Synthetic Minority Over-sampling Technique）,new sample is synthesized.Based upon the distance between seed sample and the centre of minority class,new sample distribution function is formed.Classification experiment results show DB_SMOTE is feasible.

imbalanced data learning;oversampling;data classification

A

TP391

10.3778/j.issn.1002-8331.1308-0099

LIU Yuxia,LIU Sanmin,LIU Tao,et al.New oversampling algorithm DB_SMOTE.Computer Engineering and Applications,2014,50（6）：92-95.

國家自然科學(xué)基金（No.61300170，No.71371012）；教育部人文社科基金（No.13YJA630098）；安徽省自然科學(xué)基金重點(diǎn)資助項(xiàng)目（No.KJ2013A040）；高校省級優(yōu)秀青年人才基金重點(diǎn)項(xiàng)目（No.2013SQRL034ZD）；校青年基金（No.2013YQ31，No.2012YQ32）。

劉余霞（1980—），女，碩士研究生，研究方向：信號處理、模式識別。E-mail：guiyuxia@163.com

2013-08-09

2013-11-08

1002-8331（2014）06-0092-04