一種新的過采樣算法DB_SMOTE

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

1.安徽工程大學建筑工程學院，安徽蕪湖 241000

2.安徽工程大學計算機與信息學院，安徽蕪湖 241000

3.南京航空航天大學計算機科學與技術學院，南京 210016

4.安徽工程大學管理工程學院，安徽蕪湖 241000

◎數據庫、數據挖掘、機器學習◎

一種新的過采樣算法DB_SMOTE

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

1.安徽工程大學建筑工程學院，安徽蕪湖 241000

2.安徽工程大學計算機與信息學院，安徽蕪湖 241000

3.南京航空航天大學計算機科學與技術學院，南京 210016

4.安徽工程大學管理工程學院，安徽蕪湖 241000

針對非平衡數據集中類分布信息不對稱現象，提出一種新的過采樣算法DB_SMOTE（Distance-based Synthetic Minority Over-sampling Technique），通過合成少數類新樣本解決樣本不足問題。算法基于樣本與類中心距離，結合類聚集程度提取種子樣本。根據SMOTE（Synthetic Minority Over-sampling Technique）算法思想，在種子樣本上實現少數類新樣本合成。根據種子樣本與少數類中心距離構造新樣本分布函數。基于此采樣算法并在多個數據集上進行分類實驗，結果表明DB_SMOTE算法是可行的。

非平衡數據學習；過采樣；數據分類

1 引言

非平衡數據學習（Imbalanced Data Learning，IDL）是指學習的數據集類別分布不均勻，其中某類樣本數量在整個數據集內占據絕對優勢。這一現象廣泛存在各種領域，如醫療診斷、故障檢測、金融欺詐等[1]。而傳統機器學習算法均是基于樣本分布均勻基礎之上建立的，直接遷移到非平衡數據學習環境是不可取的。

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

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

2 非平衡數據集學習算法DB_SMOTE

為便于討論，本文主要關注只有兩類樣本的非平衡數據學習問題，且規定少數類樣本為正類樣本，多數類樣本為負類樣本。算法DB_SMOTE主要包括三個階段：首先是尋找少數類種子樣本；其次是構建合成樣本的分布函數；最后是結合平衡因子和分布函數實現過采樣。

2.1 少數類樣本數據合成

為便于敘述，首先給出下列相關定義。

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

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

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

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

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

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

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

其中si屬于侯選集內樣本，r是取值于[0，1]之間的隨機數。

由前文所述可知，侯選集內的樣本與類中心的距離越遠，其所帶有效信息相對較多。因此基于此類樣本合成新樣本個數應該越多，越有利于提高分類模型的精度。據此算法利用距離信息，構造出合成樣本分布函數。

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

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

2.2 算法實現

在上述合成策略的基礎上，可得出具體的學習算法DB_SMOTE。

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

算法：DB_SMOTE(DS，L，σ)

輸入：數據集DS，學習器L，平衡因子σ

步驟：

（1）調用分層抽樣對數據集DS進行處理，形成訓練集(tr)和測試集(ts)。

（2）對訓練集tr進行統計得到少數類樣本集min和多數類樣本集maj。

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

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

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

（6）fori=1，|cs|

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

（8）產生隨機數r

（9）根據公式（4）合成新樣本sns

（10）tr=tr∪sns

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

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

3 實驗分析

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

3.1 數據集

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

表1 數據集

由文獻[9，14]可知，數據集中兩類樣本數比例超過1∶2，即可認為數據集是不平衡的。

3.2 評價度量

由于數據集的非平衡性，按照傳統方法用準確率來衡量分類器的性能是不合適的。為客觀、公正地評價分類器的性能，滿足實際需求（人們常常更關注的是少數類的分類情況），應尋求新的度量參數。

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

表2 混淆矩陣

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

而F-value是精度和召回率的調和均值，其值接近兩數的較小者。在非平衡數據學習中用F-value能全面反映分類器性能，因為只有當精度和召回率均較大時，F-value才會變大，滿足實際需求。計算方法如公式（7）所示：

在公式（7）中參數β通常取值1，用以調節兩個參數的重要程度。

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

綜上，本文在進行算法對比時，主要關注少數類的F-value值和分類器的G-mean值。

3.3 實驗數據分析

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

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

圖1 F_value變化曲線圖

圖2 G-mean變化曲線圖

4 結束語

針對非平衡數據學習問題，文中通過改變傳統求K-近鄰的方法，結合樣本距離和類聚集特點提出了DB_SMOTE算法。算法的關鍵是提取到種子樣本和構建合成樣本分布函數。從實驗數據分析可知，該算法能夠解決非平衡數據學習問題。目前非平衡數據學習問題，主要考慮的是靜態數據環境，如何解決在數據流環境下的非平衡數據學習將是研究問題之一。同時，噪聲問題的處理也是非平衡數據學習問題難點。

[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]程險峰，李軍，李雄飛.一種基于欠采樣的非平衡數據分類算法[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，FL，USA，2008：1-4.

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

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

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

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

[13]李明方，張化祥.針對不平衡數據的Bagging改進算法[J].計算機工程與應用，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.

國家自然科學基金（No.61300170，No.71371012）；教育部人文社科基金（No.13YJA630098）；安徽省自然科學基金重點資助項目（No.KJ2013A040）；高校省級優秀青年人才基金重點項目（No.2013SQRL034ZD）；校青年基金（No.2013YQ31，No.2012YQ32）。

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

2013-08-09

2013-11-08

1002-8331（2014）06-0092-04