數(shù)據(jù)不平衡分類研究綜述

李元菊

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都　610065）

數(shù)據(jù)不平衡分類研究綜述

李元菊

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065）

數(shù)據(jù)不平衡；抽樣；代價(jià)敏感；集成方法

0　引言

在許多有監(jiān)督的方法中，不同類別的先驗(yàn)概率有顯著的差異，這種問(wèn)題被稱為類別不平衡問(wèn)題[1-2]。這種問(wèn)題在很多領(lǐng)域都經(jīng)常出現(xiàn)，例如電信領(lǐng)域、網(wǎng)絡(luò)、金融領(lǐng)域、生態(tài)學(xué)、生物學(xué)、醫(yī)學(xué)等。在數(shù)據(jù)挖掘中，類別不平衡問(wèn)題被認(rèn)為是重要的待解決問(wèn)題[3]。一般來(lái)說(shuō)，少數(shù)類稱為正類，多數(shù)類被稱為負(fù)類，正類往往是我們研究的重點(diǎn)，當(dāng)它不能很好地分類時(shí)往往需要花費(fèi)較大的代價(jià)。

不平衡數(shù)據(jù)集的一個(gè)關(guān)鍵問(wèn)題是標(biāo)準(zhǔn)的分類學(xué)習(xí)算法經(jīng)常偏置向多數(shù)類。因此，對(duì)于少數(shù)類的樣例來(lái)說(shuō)有很高的誤分類比率，為了解決這個(gè)問(wèn)題專家們提出了很多辦法。有數(shù)據(jù)層面的方法，也有算法層面的方法。主要分為三種：數(shù)據(jù)抽樣，算法層面，代價(jià)敏感學(xué)習(xí)。

1　分類中的不平衡問(wèn)題

1.1不平衡數(shù)據(jù)冀問(wèn)題

在分類中，不平衡數(shù)據(jù)分類經(jīng)常出現(xiàn)。這種分類問(wèn)題的主要特點(diǎn)是某一種類別的樣本數(shù)目明顯多于其他類別樣本數(shù)量[4]。然而少數(shù)類往往是我們重點(diǎn)學(xué)習(xí)的東西，在大多數(shù)情況下，不平衡數(shù)據(jù)分類通常指二分類，但是多分類也會(huì)出現(xiàn)這種情況，因?yàn)槎喾诸悤?huì)有多個(gè)少數(shù)類所以這種情況研究更困難[5-6]。

絕大多數(shù)標(biāo)準(zhǔn)學(xué)習(xí)算法針對(duì)的是平衡訓(xùn)練集，用這種學(xué)習(xí)算法來(lái)訓(xùn)練不平衡數(shù)據(jù)集往往產(chǎn)生的是次優(yōu)的分類模型，例如這個(gè)模型可能覆蓋了大多數(shù)的多數(shù)類樣本，然而少數(shù)類樣本經(jīng)常被誤分類。因此，這種算法在不平衡數(shù)據(jù)集上往往不能得到最好的效果。主要?dú)w因于下面幾種原因：

①算法的度量指標(biāo)如精確率、召回率對(duì)多數(shù)類有優(yōu)勢(shì)。

②預(yù)測(cè)正類的分類規(guī)則是高度專業(yè)化的，同時(shí)他們的覆蓋率很低。因此，我們通常拋棄這些規(guī)則，取而代之的是可以預(yù)測(cè)負(fù)例的一般規(guī)則。

③非常少的少數(shù)類簇可以被定義為噪聲，因此它們可能被分類器錯(cuò)誤丟棄。相反，因?yàn)樯贁?shù)類有很少的訓(xùn)練集，所以少量真正的噪聲實(shí)例可以降低少數(shù)類的識(shí)別。

1.2評(píng)估指標(biāo)

在評(píng)估分類器的性能和指導(dǎo)分類器建模方面，評(píng)估標(biāo)準(zhǔn)發(fā)揮了關(guān)鍵作用。在傳統(tǒng)的分類方法中，準(zhǔn)確率是常用的指標(biāo)。然而在不平衡數(shù)據(jù)分類中，準(zhǔn)確率不再是恰當(dāng)?shù)闹笜?biāo)[7-8]。在兩類問(wèn)題中，正例數(shù)目很少但具有很高的識(shí)別重要性，另一類為負(fù)例。樣本經(jīng)過(guò)分類處理后可以分為四組如下表混合矩陣[25]（表1）。

表1　混合矩陣

從該表我們可以得到下列度量指標(biāo)：

真陽(yáng)性率：TPrate=TP/（TP+FN），真陰性率：TNrate=TN/（TN+FP）

假陽(yáng)性率：FPrate=FP/（TN+FP），假陰性率：FNrate= FN/（TP+FN）

陽(yáng)性預(yù)測(cè)值:PPvalue=TP/（TP+FP），假性預(yù)測(cè)值：NPvalue=TN/（TN+FN）

上述度量指標(biāo)都不能很好的評(píng)估不平衡數(shù)據(jù)分類，針對(duì)不平衡數(shù)據(jù)分類我們用幾個(gè)新的度量指標(biāo)如下：

（1）F-measure

在信息檢索領(lǐng)域，真陽(yáng)性率被稱為recall，陽(yáng)性預(yù)測(cè)值被稱為精確率分別定義如下：

F-measure[9]是Precision和Recall的調(diào)和平均值。兩個(gè)數(shù)值的調(diào)和平均更加接近兩個(gè)數(shù)當(dāng)中較小的那個(gè)，因此如果要使得F-measure很高的話那么Recall 和Precision都必須很高。

當(dāng)兩個(gè)類別的性能都需要考慮時(shí)，TPrate和TNrate需要同時(shí)高，Kubat等人[10]提出了G-mean。

G-mean評(píng)估一個(gè)學(xué)習(xí)算法的綜合性能。根據(jù)之前的研究，為了能夠獲得盡可能多的關(guān)于每個(gè)類別對(duì)最終性能的貢獻(xiàn)大小信息，并且考慮到數(shù)據(jù)的不平衡率，很多研究者試圖在不平衡領(lǐng)域提出新的度量指標(biāo)。如論文[11-12]調(diào)整了G-mean，提出了Adjusted G-mean。

G-mean評(píng)估一個(gè)學(xué)習(xí)算法的綜合性能。根據(jù)之前的研究，為了能夠獲得盡可能多的關(guān)于每個(gè)類別對(duì)最終性能的貢獻(xiàn)大小信息，并且考慮到數(shù)據(jù)的不平衡率，很多研究者試圖在不平衡領(lǐng)域提出新的度量指標(biāo)。如論文[11-12]調(diào)整了G-mean，提出了Adjusted G-mean。

（3）ROC曲線以及AUC

ROC曲線指受試者工作特征曲線（receiver operating characteristic curve）,是反映敏感性和特異性連續(xù)變量的綜合指標(biāo),用構(gòu)圖法揭示敏感性和特異性的相互關(guān)系。在分類中每個(gè)樣本屬于不同類別對(duì)應(yīng)的有概率值，最終類別預(yù)測(cè)根據(jù)設(shè)置的不同概率閾值，類別也會(huì)變化。每一個(gè)閾值對(duì)應(yīng)的有一組衡量指標(biāo)（FPrate, TPrate）,將FPrate為x軸，TPrate為y軸，在坐標(biāo)軸上繪制圖形。即可得到ROC曲線，曲線下方形成的面積即為AUC[13-14,24]。AUC從總體上度量了分類器的性能，一般來(lái)說(shuō)面積越大，算法性能越好。圖1 是一個(gè)ROC曲線的例子。

圖1　ROC曲線

2　不平衡數(shù)據(jù)分類解決策略

2.1重新臭樣技術(shù)

在一些專業(yè)文獻(xiàn)中，我們發(fā)現(xiàn)一些文章采用重新抽樣技術(shù)來(lái)改變不平衡數(shù)據(jù)集的類分布來(lái)調(diào)整數(shù)據(jù)平衡度。重新抽樣技術(shù)主要有兩種類型。

（1）欠抽樣方法

欠抽樣方法通過(guò)減少多數(shù)類樣本的數(shù)目來(lái)平衡數(shù)據(jù)集。最簡(jiǎn)單的方法就是隨機(jī)抽取多數(shù)類樣本。但是由于這種方法具有隨機(jī)性，所以可能丟失一些重要的信息。因此人們提出了一些改進(jìn)的方法。

對(duì)于欠抽樣技術(shù)，絕大多數(shù)是基于數(shù)據(jù)清洗技術(shù)。一些有代表性的工作有ENN規(guī)則[15]，該方法首先找到一個(gè)樣例的k個(gè)鄰居，當(dāng)該樣例的類標(biāo)與2/3個(gè)k個(gè)近鄰類標(biāo)不同時(shí)，刪除該樣例。OSS算法[16]和Tomek Links算法[17]都是基于ENN技術(shù)。

（2）過(guò)抽樣方法

通過(guò)增加少數(shù)類樣本的數(shù)目來(lái)平衡數(shù)據(jù)，也是目前最常用的方法。通過(guò)復(fù)制原始少數(shù)類樣本或者創(chuàng)造新的少數(shù)類樣本來(lái)增加少數(shù)類樣本的數(shù)目，來(lái)達(dá)到數(shù)據(jù)平衡的目的。

最簡(jiǎn)單的處理技術(shù)就是非啟發(fā)式的方法例如隨機(jī)過(guò)采樣，這種方法因?yàn)樗鼜?fù)制已有的實(shí)例所以很大可能會(huì)導(dǎo)致過(guò)度擬合。為了解決這種問(wèn)題，出現(xiàn)了一些新的復(fù)雜方法。其中SMOTE算法[18]是最有名的、應(yīng)用最廣泛的方法。SMOTE算法利用線性插值的思想來(lái)創(chuàng)建少數(shù)類樣本。主要思想如下：該方法首先為每個(gè)稀有類樣本隨機(jī)選出幾個(gè)鄰近樣本,并且在該樣本與這些鄰近的樣本的連線上隨機(jī)取點(diǎn),生成無(wú)重復(fù)的新的稀有類樣本。SMOTE算法示意圖如下：

圖2　SMOTE算法

2.2代價(jià)敏感算法

代價(jià)敏感學(xué)習(xí)賦予每個(gè)類別不同的誤分類代價(jià)[19]，用C（i，j）表示將類別i誤分為j的懲罰因子。針對(duì)二元分類我們定義一個(gè)代價(jià)矩陣如下表2所示。圖中C（i，j）的值可以由專家給定，也可以通過(guò)方法學(xué)習(xí)得到[20-21]。具體地說(shuō)當(dāng)處理不平衡數(shù)據(jù)時(shí)我們感興趣的是識(shí)別出正例而不是負(fù)例，所以誤分類正例的代價(jià)要大于誤分類負(fù)例代價(jià)。

表2　代價(jià)矩陣

2.3集成算法

集成分類器將多個(gè)獨(dú)立的分類器集成起來(lái)得到一個(gè)新的分類器，最終得到的模型優(yōu)于獨(dú)立的分類器。因此，基本的想法是用原始的數(shù)據(jù)集構(gòu)造多個(gè)分類器，然后預(yù)測(cè)新樣例時(shí)綜合初始構(gòu)造的多個(gè)基本分類器的最終結(jié)果。

近些年，集成分類器被用來(lái)解決數(shù)據(jù)不平衡分類。集成方法將集成算法與之前討論的技術(shù)相結(jié)合，也就是數(shù)據(jù)層面和算法層面的方法。權(quán)重投票算法[14]提出了一個(gè)概率框架來(lái)進(jìn)行分類器集成，這篇文章提出了四種結(jié)合方法，并給出了嚴(yán)格的最優(yōu)條件即最小的誤差。EasyEnsemble算法和BalanceCascade算法[22]利用了集成的方法，EasyEnsemble算法首先從多數(shù)類中欠抽樣多個(gè)數(shù)據(jù)集，然后用AdaBoost算法分別訓(xùn)練抽樣得到的多個(gè)數(shù)據(jù)集和少數(shù)類樣本組成的多組訓(xùn)練集，EasyEnsemble是個(gè)無(wú)監(jiān)督的算法。BalanceCascade算法是個(gè)有監(jiān)督的算法，該方法仍然采用Adaboost算法，只不過(guò)每次從總的多數(shù)類數(shù)據(jù)集樣本中去掉上次已被正確分類的樣本。Cost-sensitive boosting[23]仍然采用boost算法，只不過(guò)給不同的樣例分配不同的代價(jià)敏感因子。

3　結(jié)語(yǔ)

現(xiàn)實(shí)應(yīng)用中存在著大量不平衡分類問(wèn)題，迫切的需求激發(fā)了對(duì)不平衡分類的研究和分析。隨著新的技術(shù)不斷被提出，這一領(lǐng)域的工作也是越來(lái)越成熟。但是針對(duì)不平衡分類的研究并沒(méi)有停止，近年來(lái)仍然有越來(lái)越多的研究者研究這一領(lǐng)域，同時(shí)不平衡數(shù)據(jù)分類仍然面臨新的挑戰(zhàn)和機(jī)遇。

[1]N.V.Chawla,N.Japkowicz,A.Kotcz,Editorial:Special Issue on Learning from Imbalanced Data Sets,SIGKDD Explorations，2004，6（1）：1-6.

[2]H.He,E.A.Garcia,Learning from Imbalanced Data,IEEE Transactions on Knowledge and Data Engineering，2009，21（9）：1263-1284.

[3]Q.Yang,X.Wu,10 Challenging Problems in Data Mining Research,International Journal of Information Technology and DecisionMaking，2006，5（4）：597-604.

[4]Y.Sun,A.K.C.Wong,M.S.Kamel,Classification of Imbalanced Data:a Review,International Journal of Pattern Recognition and Artificial Intelligence，2009，23（4）：687-719.

[5]A.Fernandez,V.Lopez,M.Galar,M.J.del Jesus,F.Herrera,Analysing the Classification of Imbalanced Data-Sets with Multiple Classes:Binarization Techniques and Ad-hoc Approaches,Knowledge-Based Systems 42，2013：97-110.

[6]M.Lin,K.Tang,X.Yao,Dynamic Sampling Approach to Training Neural Networks for Multiclass Imbalance Classification,IEEE Transactions on Neural Networks and Learning Systems，2013，24（4）：647-660.

[7]G.Weiss,Mining with Rarity:a Unifying Framework,SIGKDD Explorations Special Issue on Learning from Imbalanced Datasets, 2004，6（1）：7-19.

[8]M.V.Joshi,V.Kumar,R.C.Agarwal,Evaluating Boosting Algorithms to Classify Rare Classes:Comparison and Improvements,in: Proceedings of the First IEEE International Conference on Data Mining（ICDM’01），2001.

[9]D.Lewis,W.Gale,Training Text Classifiers by Uncertainty Sampling,in:Proceedings of the Seventeenth Annual International ACM SIGIR Conference on Research and Development in Information,New York,NY,August 1998：73-79

[10]M.Kubat,R.Holte,S.Matwin,Machine Learning for the Detection of Oil Spills in Satellite Radar Images,Mach.Learn.30，1998：195-215.

[11]R.Batuwita,V.Palade,AGm:a New Performance Measure for Class Imbalance Learning.Application to Bioinformatics Problems,in: Proceedings of the 8th International Conference on Machine Learning and Applications（ICMLA 2009）,2009：545-550.

[12]R.Batuwita,V.Palade,Adjusted Geometric-Mean:a Novel Performance Measure for Imbalanced Bioinformatics Datasets Learning, Journal of Bioinformatics and Computational Biology，2012，10（4）.

[13]Victoria LopezAlberto Fernandez.An Insight into Classification with Imbalanced Data:Empirical Results and Current Trends on Using Data Intrinsic Characteristics,Information Sciences，2013，250：113-141.

[14]葉志飛,文益民.不平衡分類問(wèn)題研究綜述.智能系統(tǒng)學(xué)報(bào)，2009，4（2）.

[15]D.L.Wilson,Asymptotic Properties of Nearest Neighbor Rules Using Edited Data,IEEE Transactions on Systems,Man and Cybernetics，1972，2（3）：408-421.

[16]M.Kubat,S.Matwin,Addressing the Curse of Imbalanced Training Sets:one-Sided Selection,in:Proceedings of the 14th International Conference on Machine Learning（ICML'97）,1997：179-186.

[17]I.Tomek,Two modifications of CNN,IEEE Transactions on Systems Man and Communications，1976，6：769-772.

[18]N.V.Chawla,K.W.Bowyer,L.O.Hall,W.P.Kegelmeyer,SMOTE:Synthetic Minority Over-Sampling Technique,Journal of Artificial Intelligent Research，2002，16.

[19]P.Domingos,Metacost:a General Method for Making Classifiers Cost-Sensitive,in:Proceedings of the 5th International Conference on Knowledge Discovery and Data Mining（KDD'99）,1999：155-164.

[20]Y.Sun,M.S.Kamel,A.K.C.Wong,Y.Wang,Cost-Sensitive Boosting for Classification of Imbalanced Data,Pattern Recognition 40 2007（12）：3358-3378.

[21]Y.Sun,A.K.C.Wong,M.S.Kamel,Classification of Imbalanced Data:a Review,International Journal of Pattern Recognition and Artificial Intelligence 23

[22]X.-Y.Liu,J.Wu,Z.-H.Zhou,Exploratory Undersampling for Class-Imbalance Learning,IEEE Transactions on System,Man and Cybernetics B，2009，39（2）：539-550.

[23]Y.Sun,M.S.Kamel,A.K.C.Wong,Y.Wang,Cost-Sensitive Boosting for Classification of Imbalanced Data,Pattern Recognition 40, 2007，12：3358-3378.

[24]倪黃晶，王蔚.多類不平衡數(shù)據(jù)上的分類器性能比較研究.計(jì)算機(jī)工程，2011，37（10）.

[25]董元方，李雄飛.一種不平衡數(shù)據(jù)漸進(jìn)學(xué)習(xí)算法.計(jì)算機(jī)工程，2010，36（24）.

Imbalanced Data;Resample;Cost-Sensitive Learning;Ensemble Technique

Survey of Classification with Imbalanced Data

LI Yuan-ju
（College of Computer Science,Sichuan University,Chengdu 610065）

李元菊（1990-），女，河南人，碩士研究生，學(xué)生，研究方向?yàn)樽匀徽Z(yǔ)言處理和數(shù)據(jù)挖掘

2015-12-08

2016-01-10

在分類領(lǐng)域中，當(dāng)數(shù)據(jù)集不平衡時(shí)，傳統(tǒng)的分類算法和評(píng)估指標(biāo)都不能很好地對(duì)數(shù)據(jù)分類。因此，多年來(lái)不少學(xué)者針對(duì)這一領(lǐng)域進(jìn)行研究。主要分為三大類，即抽樣方法、代價(jià)敏感方法、集成方法。同時(shí)針對(duì)這個(gè)領(lǐng)域枚舉一些評(píng)估指標(biāo)。

In classification field,when the data is imbalanced,the traditional classification algorithms and evaluation criteria are not good for it.So, a lot of researchers study it recent years.Mainly divides into three categories,such as resample technique,cost-sensitive learning and ensemble techniques.At the same time,puts forward some new standards to evaluate the algorithms in this field.