不平衡數據集的混合采樣方法

尚旭

摘要：不平衡數據集中，由于某類別數量的不平衡，使得類別數量少的容易被誤分，導致其分類準確率不高。處理不平衡數據集的方法，可以分為算法方面和數據方面，在數據方面中，主要分為兩種方法：過采樣和欠采樣，但是對于將這兩種方法結合的研究不是很多，過采樣和欠采樣都具有一定的優(yōu)勢，因此設想將這兩種方法結合起來，希望可以找到更好的方法。提出兩種混合采樣方法：Random-SMOTE+ENN和Random-SMOTE+TNS，并與幾種典型的抽樣方法在數據集上進行實驗對比，實驗結果表明提出的兩種方法是可行有效的。

關鍵詞：不平衡數據集 過采樣 欠采樣

中圖分類號：TP181 文獻標識碼：A 文章編號：1007-9416（2016）12-0068-04

引言

不平衡數據集[1-2]是指在一個數據集中，有些類別的樣本數量很多，有些類別的樣本數量很少，這就形成了數據集各類別樣本的不均衡，一般稱樣本數量少的一類為少數類，有時也可稱為正類，樣本數量多的一類為多數類，有時也稱為負類[3]。在許多不平衡數據集的實際分類中，樣本數量少的一類往往對分類來說更重要。在現實生活中，存在著許多數據不平衡的例子，如醫(yī)療診斷[4]，垃圾信息的識別，客戶信譽識別[5]。例如在醫(yī)療診斷中，一個沒有病的人被醫(yī)生診斷為有病，這會使人承受精神的壓力，然而假如醫(yī)生把一個有病的患者診斷為沒有病可能就會耽誤治療，有可能會危及病人的生命。正如這些實例，少類數據所擁有的信息往往是所需要的，因此怎樣能在分類過程中正確識別這些數據是應該關注和解決的問題。

目前，已經有很多這方面的處理方法[6]可以從兩方面考慮：算法方面和數據處理方面。算法方面就是不斷完善已有的算法和提出新的分類算法[7]，如代價敏感學習、Bagging算法[8]等。數據方面的方法有兩種[9]：過采樣方法和欠采樣方法[10-11]。常用的采樣方法是隨機過采樣、隨機欠采樣、Tomeklinks[12]、壓縮最近鄰（CNN）[13]、鄰域清理（NCL）[14]、（Synthetic Minority Over-Sampling Techique）SMOTE[15]、Borderline-Smote（BSM）[16]、one-sided selection（OSS）[17]等，還有一些組合算法，如Gustavo[18]等人提出的SMOTE+ENN和SMOTE+Tomeklink。

文中主要研究了過采樣和欠采樣相結合的方法，分別將過采樣方法Random-SMOTE和欠采樣ENN方法、（Total under sampling）TNS方法結合，即Random-SMOTE+ENN方法和Random-SMOTE+TNS方法。將過采樣和欠采樣這兩種方法相結合是因為在樣本數較少的數據集，這兩種方法都有不足，過采樣或欠采樣的效果不好，過采樣會使樣本數據集的少數類過擬合，而欠采樣方法會丟許多樣本的信息，組合方法能夠有效的解決這兩種問題，其次，已經有人研究過將這兩種采樣方法結合，實驗結果表現出良好的效果，最后，這幾種方法在單獨執(zhí)行時就表現出了較好的效果，所以將這兩種采樣方法組合起來，希望會使不平衡數據集的分類效果好。

在預處理階段采用了6種采樣方法，其中包括文章提出的兩種對不平衡數據預處理的方法，在選取的9種不同程度數據集上進行預處理及分類實驗，最后給出6種采樣方法預處理后的分類結果以及實驗結論。

1 相關介紹

目前，在已有的處理不平衡數據分類問題的數據處理方法有兩方面，一方面是過采樣方法，另一方面欠采樣方法。隨機過采樣是對少數類樣本進行復制，這會引起樣本數據的重疊和過擬合現象，而隨機欠采樣方法，是隨機的刪除一些多數類的數據，使各類別的樣本數量平衡，然而這會使一些重要樣本數據信息丟失，會影響分類時的判斷。2002年Chawla N V等人提出了一種啟發(fā)式方法：（Synthetic Minority Over-Sampling Techique）SMOTE，這種方法與隨機過采樣方法不同，人為的在同類近鄰樣本間線性插值來生成新的樣本，有效的解決了數據重疊現象。針對SMOTE方法的提出，研究者們對SMOTE進行了許多的改進工作，取得了非常好的效果。

下面介紹幾種采樣方法：

1.1 SMOTE

SMOTE方法的基本思路是在近鄰少數類樣本之間進行線性插值，合成新的少數類樣本。具體方案是：對數據集中少數類的每一個樣本尋找其（通常取5）個同類最近鄰樣本，根據采樣倍率，在其個同類最近鄰樣本中隨機選擇個同類樣本，記作，在少數類樣本，之間連線上進行隨機線性插值，生成少數類樣本。

其中 是（0，1）內一個隨機數，表示為新的生成的樣本。

1.2 （edited nearest neighbor）ENN

ENN[19]的基本意思是若樣本的3個最近鄰樣本中2個或以上的樣本類別和它不一樣，則刪除此樣本。ENN方法是一種欠采樣算法，首先搜索多數類樣本的3個最近鄰樣本，若該樣本的3個最近鄰樣本中有兩個或以上和該樣本類別不一樣則刪除這個樣本，此算法意在刪除多數類樣本，然而多數類樣本附近往往都是多數類樣本，因此ENN去掉的樣本非常有限的。

1.3 （Neighborhood Cleaning Rule）NCL

NCL方法是在ENN方法的基礎上提出的，以能夠刪除更多的多數類樣本。其基本方案如下：對訓練集中的每個樣本找出它的最近鄰的3個樣本，若該樣本是多數類，且3個最近鄰樣本中有2個或以上與其類別不一樣，則刪除；若屬于少數類，且3個最近鄰樣本中有2個或以上與其類別不同，則刪除3個最近鄰樣本中的多數類樣本。

1.4 Random-SMOTE

Random-SMOTE[20]采樣方法的基本思想是：對于每個少數類樣本，找其個同類最近鄰樣本，從最近鄰少數類樣本集中隨機選出兩個樣本、；以、、三點圍成一個三角形區(qū)域；若向上采樣倍率在該三角形區(qū)域內隨機生成個新的少數類樣本。

生成新的少數類樣本具體步驟如下：

a）在兩個最近鄰樣本、之間生成個臨時樣本

b）然后在臨時樣本之間進行隨機線性插值，生成新的少數類樣本

其中：其中表示為（0，1）內一個隨機數。

以上是基于數據采樣的幾種處理不平衡數據的基本方法，近幾年研究者們在這些方法的基礎上提出了新的處理方法。如Gustaro等人將提出了兩種組合方法：SMOTE+Tomeklink和SMOTE+ENN方法，取得了不錯的效果，但對于其他的算法組合研究的很少，所以文章就Random-SMOTE與ENN和TNS組合并驗證此方法的可行性，通過研究工作發(fā)現將過采樣和欠采樣結合是可行的有意義的。

文中提出的兩種組合方法Random-SMOTE+ENN：首先利用Random-SMOTE對少數類樣本進行過采樣，然后利用ENN方法對多數類數據進行欠采樣處理，Random-SMOTE+TNS：首先利用Random-SMOTE對少數類數據進行過采樣，然后對少數類樣本和多數類樣本均實行欠采樣處理，方法：對數據集中的每個樣本，尋找其最近鄰的3個樣本，比較若3個最近鄰樣本中有兩個或以上的樣本和該樣本的類別不同，則刪除該樣本，稱之為Total under sampling（TNS）。并且通過實驗和其他幾種方法對比驗證文中提出的方法是有效的。

2 評價標準度量

評價標準對分類器的性能好壞和指導分類器做出判斷有著重要的作用。對于不平衡數據分類來說，常用評價標準包括ROC曲線、基于混淆矩陣的若干度量，如查全率、查準率、和等。

在兩分類的情形下。將少數類稱為正類。多數類稱為負類。經過分類以后，數據的分類為混淆矩陣中表示的4種情況[21]（見表1）。

利用混淆矩陣，可以派生出以下度量：

在信息檢索領域，將真實正類率定義為查全率，表示在檢索到的相關對象所占的比例：

將正類預測值定義為查準率，表示相關對象占檢索出的所有對象的比例：

另一種評價標準是查全率和查準率的調和均值：

上式中，表示和之間的相對重要程度，大于1時表示更重要，小于1時表示更重要。通常為1，表示兩者都重要。

是一個衡量整體分類性能的評價指標，為少數類的分類精度， 是多數類的分類精度，只有當二者的值都大時，的值才會大，因此，能衡量不平衡數據集的整體分類性能。

3 仿真實驗

3.1 數據集

實驗驗證的數據集來自UCI數據庫中的9個數據集，每個數據集的基本信息如表2所示。

3.2 實驗結果分析

不平衡數據的分類學習中，標準的分類精度準則不適合評估不平衡數據集的分類效果，本實驗選取F-value準則，G-mean準則和少數類的分類準確率acc+來對實驗結果綜合分析。

在實驗中，選擇了近鄰算法作為分類算法，然后對選取6種不同的采樣方法進行實驗對比，分別是：隨機過采樣、SMOTE、Random-SMOTE、SMOTE+ENN、Random-SMOTE+ENN、Random-SMOTE+TNS，上述不平衡分類方法所使用近鄰算法的近鄰選取5，在各個數據集上所有采樣方法所設置的采樣率相同，為實驗客觀公正，實驗通過五折交叉驗證得到實驗結果。

表3、表4列出個不平衡分類方法在9個UCI數據集上的G-mean和F-value值。

從表3、表4給出的F-value值和G-mean值可以看出，對于組合方法的分類效果在大多數數據集上優(yōu)于過采樣方法的分類效果，尤其在于不平衡度較小的數據集上組合方法的效果更明顯，組合方法先通過過采樣對于少類數據處理，然后對于多類數據進行欠采樣處理，不僅增加了少類數據數目，而且盡可能的刪除處于邊界的多類數據，大大提高了少類分類正確率，分類效果明顯更好。文中提出的兩種分類方法也具有很好的分類效果，其中Random-smote+TNS的分類效果在9個數據集上的表現均好于其他幾種分類方法的表現。另一種組合方法Random-SMOTE+ENN的分類效果低于SMOTE+ENN的分類效果，但和其他三種方法分類效果對比具有一定的優(yōu)勢，只在數據集glass-I比SMOTE和Random-SMOTE低，在數據集Balance-II上比隨機過采樣低。文中提出的分類方法分類效果良好。

不平衡數據集中，少數類往往是我們感興趣的類別，因此對于少數類的分類準確率acc+是衡量不平衡分類性能的重要指標，圖1給出了各采樣方法的acc+圖，由圖可知，除了數據集Feritilty和Balance-II上，Random-smote+TNS的acc+值低于隨機過采樣，在其他數據集上Random-smote+TNS的acc+值均大于其他采樣方法，特別在Pima數據集和blood數據上，acc+值明顯高于其他采樣方法。另一種組合方法Random-smote+ENN的acc+和Somte+ENN表現持平，但好于過采樣方法Random-smote，可見組合方法的分類率好于單純的過采樣方法。從整個實驗數據的分析得出文中的兩種組合方法是可行有效的。

4 結語

文章通過在多個數據上使用多種數據采樣方法，進行仿真實驗對比得到兩種較好混合采樣方法和有效的結果，通過實驗數據分析得出這兩種混合采樣方法在試驗中大多數據集上具有良好的分類效果，然而也可以看出所提出的方法并不是在所有的數據集上具有好的效果。其次，沒有研究其他采樣方法組合的合理性，希望在下一步研究中能將過采樣和欠采樣方法進行不同的組合嘗試，希望能夠找到更好的處理方法在保證整體正確率的前提下提高少數類的分類正確率。

參考文獻

[1]Han Jiawei， KAMBER M.數據挖掘概念與技術[M].范明，孟小峰，譯.北京：機械工業(yè)出版，2001.

[2]楊明，尹軍梅，吉銀林.不平衡數據分類方法綜述[J].南京師范大學學報：工程技術版，2008，8（4）：7-12.

[3]Paolo S. A multi-objective optimization approach for class imbalance learning [J]. Pattern Recognition， 2011， 44（8）：1801-1810.

[4]Li DC，Liu CW，Susan CH.A learning method for the class imbalance problem with medical data sets [J]. Computers in biology and medicine， 2010， 40（5）：509-518.

[5]徐麗麗，閆德勤，高晴.基于聚類欠采樣的極端學習機[J].微型機與應用，2015（17）：81-84.

[6]王和勇，范泓坤，姚正安，等.不平衡數據集分類方法研究[J]計算機應用研究，2008，25（5）：1301-1308.

[7]胡小生，張潤晶，鐘勇.一種基于聚類提升的不平衡數據分類算法[J].集成技術，2014（2）：35-41.

[8]李明方，張華祥.針對不平衡數據的Bagging改進算法[J].計算機工程應用，2013，49（2）：40-42.

[9]吳磊，房斌，刁麗萍，等.融合過抽樣和欠抽樣的不平衡數據重抽樣方法[J].計算機工程與應用，2013，49（21）：172-176.

[10]丁福利，孫立民.處理不平衡樣本集的欠采樣算法[J].計算機工程與設計，2013，34（12）：4345-4350.

[11]林舒楊，李翠華，江戈，等.不平衡數據的降采樣方法研究[J].計算機研究與發(fā)展，2011，48（2）：47-53.

[12]TOMEK I. Two modifications of CNN[J].IEEE Trans on Systems， Man and Communications， 1976， 6：769-772.

[13]HART P E. The condensed nearest neighbor rule[J]. IEEE Trans on Information Theory， 1968，14（3）：515-516.

[14]LAURIKKALA J. Improving identification of difficult small classes by balancing class distribution[C]. Proc of the 8th Conference on AI in Medicine. Europe， Artificial Intelligence Medicine， 2001：63-66.

[15]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.

[16]Han H， Want 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.

[17]KUBAT M， MATWIN S. Addressing the course of imbalanced training sets： one-sided selection[C]. Proc of the 14th International Conference on Machine learning. San Francisco， Morgan Kaufmann， 1997：179-186.

[18]Gustavo E A， Batista P A， Ronaldo C，et al A study of the behavior of several methods for balancing machine learning training data[J]. SIGKDD Explorations， 2004，6（1）：20-29.

[19]WISON D L. Asymptotic properties of nearest neighbor rules using edited data [J].IEEE Trans on Systems， Man and Communications， 1972，2（3）：408-421.

[20]Dong Yanjie，WangXuehua. A new over-sampling approach：Random-SMOTE for learning from imbalanced data sets [C]//LNCS 7091： Proceedings of the 5th International Conference on Knowledge Science， Engineering and Management（KSEM11）. Berlin，Heidelberg：Springer-Verlag 2011：343-352.

[21]董元方，李雄飛，李軍.一種不平衡數據漸進學習算法[J].計算機工程，2010，36（24）：161-163.