數據不平衡分類研究綜述

李元菊

（四川大學計算機學院，成都　610065）

數據不平衡分類研究綜述

李元菊

（四川大學計算機學院，成都610065）

數據不平衡；抽樣；代價敏感；集成方法

0　引言

在許多有監督的方法中，不同類別的先驗概率有顯著的差異，這種問題被稱為類別不平衡問題[1-2]。這種問題在很多領域都經常出現，例如電信領域、網絡、金融領域、生態學、生物學、醫學等。在數據挖掘中，類別不平衡問題被認為是重要的待解決問題[3]。一般來說，少數類稱為正類，多數類被稱為負類，正類往往是我們研究的重點，當它不能很好地分類時往往需要花費較大的代價。

不平衡數據集的一個關鍵問題是標準的分類學習算法經常偏置向多數類。因此，對于少數類的樣例來說有很高的誤分類比率，為了解決這個問題專家們提出了很多辦法。有數據層面的方法，也有算法層面的方法。主要分為三種：數據抽樣，算法層面，代價敏感學習。

1　分類中的不平衡問題

1.1不平衡數據冀問題

在分類中，不平衡數據分類經常出現。這種分類問題的主要特點是某一種類別的樣本數目明顯多于其他類別樣本數量[4]。然而少數類往往是我們重點學習的東西，在大多數情況下，不平衡數據分類通常指二分類，但是多分類也會出現這種情況，因為多分類會有多個少數類所以這種情況研究更困難[5-6]。

絕大多數標準學習算法針對的是平衡訓練集，用這種學習算法來訓練不平衡數據集往往產生的是次優的分類模型，例如這個模型可能覆蓋了大多數的多數類樣本，然而少數類樣本經常被誤分類。因此，這種算法在不平衡數據集上往往不能得到最好的效果。主要歸因于下面幾種原因：

①算法的度量指標如精確率、召回率對多數類有優勢。

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

③非常少的少數類簇可以被定義為噪聲，因此它們可能被分類器錯誤丟棄。相反，因為少數類有很少的訓練集，所以少量真正的噪聲實例可以降低少數類的識別。

1.2評估指標

在評估分類器的性能和指導分類器建模方面，評估標準發揮了關鍵作用。在傳統的分類方法中，準確率是常用的指標。然而在不平衡數據分類中，準確率不再是恰當的指標[7-8]。在兩類問題中，正例數目很少但具有很高的識別重要性，另一類為負例。樣本經過分類處理后可以分為四組如下表混合矩陣[25]（表1）。

表1　混合矩陣

從該表我們可以得到下列度量指標：

真陽性率：TPrate=TP/（TP+FN），真陰性率：TNrate=TN/（TN+FP）

假陽性率：FPrate=FP/（TN+FP），假陰性率：FNrate= FN/（TP+FN）

陽性預測值:PPvalue=TP/（TP+FP），假性預測值：NPvalue=TN/（TN+FN）

上述度量指標都不能很好的評估不平衡數據分類，針對不平衡數據分類我們用幾個新的度量指標如下：

（1）F-measure

在信息檢索領域，真陽性率被稱為recall，陽性預測值被稱為精確率分別定義如下：

F-measure[9]是Precision和Recall的調和平均值。兩個數值的調和平均更加接近兩個數當中較小的那個，因此如果要使得F-measure很高的話那么Recall 和Precision都必須很高。

當兩個類別的性能都需要考慮時，TPrate和TNrate需要同時高，Kubat等人[10]提出了G-mean。

G-mean評估一個學習算法的綜合性能。根據之前的研究，為了能夠獲得盡可能多的關于每個類別對最終性能的貢獻大小信息，并且考慮到數據的不平衡率，很多研究者試圖在不平衡領域提出新的度量指標。如論文[11-12]調整了G-mean，提出了Adjusted G-mean。

G-mean評估一個學習算法的綜合性能。根據之前的研究，為了能夠獲得盡可能多的關于每個類別對最終性能的貢獻大小信息，并且考慮到數據的不平衡率，很多研究者試圖在不平衡領域提出新的度量指標。如論文[11-12]調整了G-mean，提出了Adjusted G-mean。

（3）ROC曲線以及AUC

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

圖1　ROC曲線

2　不平衡數據分類解決策略

2.1重新臭樣技術

在一些專業文獻中，我們發現一些文章采用重新抽樣技術來改變不平衡數據集的類分布來調整數據平衡度。重新抽樣技術主要有兩種類型。

（1）欠抽樣方法

欠抽樣方法通過減少多數類樣本的數目來平衡數據集。最簡單的方法就是隨機抽取多數類樣本。但是由于這種方法具有隨機性，所以可能丟失一些重要的信息。因此人們提出了一些改進的方法。

對于欠抽樣技術，絕大多數是基于數據清洗技術。一些有代表性的工作有ENN規則[15]，該方法首先找到一個樣例的k個鄰居，當該樣例的類標與2/3個k個近鄰類標不同時，刪除該樣例。OSS算法[16]和Tomek Links算法[17]都是基于ENN技術。

（2）過抽樣方法

通過增加少數類樣本的數目來平衡數據，也是目前最常用的方法。通過復制原始少數類樣本或者創造新的少數類樣本來增加少數類樣本的數目，來達到數據平衡的目的。

最簡單的處理技術就是非啟發式的方法例如隨機過采樣，這種方法因為它復制已有的實例所以很大可能會導致過度擬合。為了解決這種問題，出現了一些新的復雜方法。其中SMOTE算法[18]是最有名的、應用最廣泛的方法。SMOTE算法利用線性插值的思想來創建少數類樣本。主要思想如下：該方法首先為每個稀有類樣本隨機選出幾個鄰近樣本,并且在該樣本與這些鄰近的樣本的連線上隨機取點,生成無重復的新的稀有類樣本。SMOTE算法示意圖如下：

圖2　SMOTE算法

2.2代價敏感算法

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

表2　代價矩陣

2.3集成算法

集成分類器將多個獨立的分類器集成起來得到一個新的分類器，最終得到的模型優于獨立的分類器。因此，基本的想法是用原始的數據集構造多個分類器，然后預測新樣例時綜合初始構造的多個基本分類器的最終結果。

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

3　結語

現實應用中存在著大量不平衡分類問題，迫切的需求激發了對不平衡分類的研究和分析。隨著新的技術不斷被提出，這一領域的工作也是越來越成熟。但是針對不平衡分類的研究并沒有停止，近年來仍然有越來越多的研究者研究這一領域，同時不平衡數據分類仍然面臨新的挑戰和機遇。

[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]葉志飛,文益民.不平衡分類問題研究綜述.智能系統學報，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]倪黃晶，王蔚.多類不平衡數據上的分類器性能比較研究.計算機工程，2011，37（10）.

[25]董元方，李雄飛.一種不平衡數據漸進學習算法.計算機工程，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-），女，河南人，碩士研究生，學生，研究方向為自然語言處理和數據挖掘

2015-12-08

2016-01-10

在分類領域中，當數據集不平衡時，傳統的分類算法和評估指標都不能很好地對數據分類。因此，多年來不少學者針對這一領域進行研究。主要分為三大類，即抽樣方法、代價敏感方法、集成方法。同時針對這個領域枚舉一些評估指標。

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.