不平衡數據集的分類方法研究

摘要：傳統的分類算法在處理不平衡數據分類問題時會傾向于多數類，而導致少數類的分類精度較低。針對不平衡數據的分類，首先介紹了現有不平衡數據分類的性能評價；然后介紹了現有常用的基于數據采樣的方法及現有的分類方法；最后介紹了基于數據采樣和分類方法結合的綜合方法。

關鍵詞：機器學習; 不平衡數據; 數據分類

中圖分類號：TP181文獻標志碼：A

文章編號：1001-3695(2008)05-1301-03

在過去的幾十年中，全球信息科技的飛速發展導致了功能強大的計算機、數據收集設備和存儲設備的產生。利用這些設備可以收集大量的數據信息以供人們進行事務管理、信息檢索和數據分析。盡管收集得到的數據量非常大，但是對人們有用的數據往往非常有限，通常僅占全部數據的一小部分。這種某類樣本數量明顯少于其他類樣本數量的數據集稱為不平衡數據集。不平衡數據集的分類問題大量存在于人們的現實生活和工業生產之中。例如，尋找電信運行商的逃離客戶[1]，一般情況下逃離的客戶要遠遠少于非逃離客戶；利用檢測數據診斷病人的疾病[2]，如癌癥，人們患癌癥的概率是非常低的，因此癌癥患者要遠遠少于健康的人；其他如從衛星圖片中油井的定位[3]、學習單詞的發音[4]、文本自動分類[5]、分辨惡意的騷擾電話[6]等。在這些應用中，人們主要關心的是數據集中的少數類，而且這些少數類的錯分所產生的代價非常大。把有逃離傾向的客戶判為正常客戶將有可能失去該客戶；把癌癥病人誤診為正常將會延誤治療時機，對病人造成生命威脅。因此在實際應用中，需要提高少數類的分類精度。

近幾年來，不平衡數據集的分類問題也越來越受到數據挖掘和機器學習學術界的重視，已成為數據挖掘和機器學習界的熱點問題之一。2000年美國人工智能協會（AAAI）[7]以及2003年機器學習國際會議（ICML）[8]特別對不平衡數據的學習問題召開了專題討論會。2004年美國計算機協會（ACM）針對這一專題出版了一期通訊[9]。目前，處理不平衡數據集分類較好的方法主要有基于不平衡數據集的數據采樣和基于不平衡數據集的分類。

1不平衡數據分類的性能評價

表1是二類問題的混淆矩陣。表中TP是真實正例的數目；FP是虛假正例的數目；TN是真實負例的數目；FN是虛假負例的數目。

受試者工作特性（receiver operating characteristic， ROC）曲線[10]以及正負例精確率的幾何平均[11]是兩種流行的分類器性能評價方法。它們都獨立于數據集類間的分布，對數據集的不平衡性有很好的魯棒性，因此它們可用于不平衡數據集分類器的評價。

ROC曲線反映了當分類器參數變換時，真實確定率（TP rate）與虛假確定率（FP rate）之間的關系。坐標中的(0，0)點對應于將所有點歸于負類；(1，1)點對應于將所有點歸于正類；直線y=x對應于隨機猜測；(0，1)點對應于最理想的分類情況，即所有樣本均分類正確。ROC曲線越靠近左上角，分類器性能越好。由于ROC曲線沒有給出具體的評價數值，不方便不同分類器間性能的比較，于是人們常使用ROC曲線下的面積（area under ROC， AUC）作為評價指標。較大的AUC值對應于較優的分類器。AUC是基于ROC曲線的惟一數值，它與錯分代價無關，不受與規則應用相關的因素影響。文獻[12]中提出了一種AUC值的估計方法，該方法估計AUC僅需使用后驗概率的排列值，而無須知道具體的ROC曲線。

其中：acc+=TP/n+為正例的精確率；acc-=TN/n-為負例的精確率。g值的大小與ROC點離最優分類的距離密切相關[13]。用g值來衡量分類器處理不平衡數據的性能是直觀和合理的。要使g值大，則需要正負例的精確率都大，且盡量保持兩者平衡；如果負例的精確率大，而正例的精確率小，那么g值仍會比較小。此外，由式（3）可以看出，g值與acc+、acc-的關系是非線性的，acc+（或acc-）值的變化對g值的影響依賴于acc+（或acc-）值的大小：acc+（或acc-）值越小，它引起的g值的變化越大。這就意味著少數類即正類樣本錯分得越多，正類的錯分代價就越大。

2常用的不平衡數據分類方法

處理不平衡數據集分類的方法主要可分為三大類：基于數據采樣、基于分類算法以及將兩種類型方法結合的綜合方法。基于數據采樣的方法主要是改變不平衡數據的分布，以降低數據的不平衡程度；基于分類算法的方法主要是提出新的分類思想，改進傳統的分類算法，以適應不平衡數據分類的需要；綜合方法則是基于數據采樣與分類方法的結合。

2．1基于數據采樣的方法

針對原始數據的處理，提出了多種不同的數據重采樣方法[14]。按照對樣本數量的影響可分為：向上采樣，即人為地增加少數類的樣本；向下采樣，即人為地減少少數類的樣本。根據方法的智能性又可分為啟發式方法和非啟發式方法。下面簡單介紹一些常用的方法：

a)隨機向上采樣。該方法是最簡單的向上采樣方法，它通過隨機復制少數類的樣本來達到增加少數類樣本的目的。由于這種方法僅僅是對少數樣本的簡單復制，容易造成分類器的過學習。

b)隨機向下采樣。該方法是最簡單的向下采樣方法，它隨機去掉多數類的樣本，以降低數據不平衡的程度。由于隨機性，這種方法常常會去掉一些潛在的對分類有用的樣本。

以上兩種方法的原理簡單，都屬于非啟發式方法。下面介紹的方法都屬于啟發式方法，它們引入了啟發式規則，從而可在一定程度上克服非啟發式方法的不足。

c)Tomek links。該方法在文獻[15]中提出，其基本思想如下：給定兩個樣本xi，xj屬于不同的類，它們之間的距離用d(xi，xj)表示。若不存在另一樣本x滿足d(xi，x)＜d(xi，xj)或d(xj，x)＜d(xi，xj)，則樣本對(xi，xj)構成一個Tomek links。如果兩個樣本構成Tomek links，則其中某個樣本為噪點，或者兩個樣本在兩類的邊界上。利用這個性質，Tomek links可作為向下采樣的方法，即去掉構成Tomek links的負例。

d)壓縮最近鄰（condensed nearest neighbor rule，CNN）。該方法最早由Hart[16]提出，當時用于尋找樣本的一致子集。子集E~E稱為集合E的一致子集。如果用最近鄰分類器，E~中樣本可完全正確地分類E中的樣本。文獻[11]提出了一種構造子集E~的算法作為向下采樣的方法：首先將所有正例樣本以及隨機選取一個負例加入E~中進行初始化；然后用E~中的樣本以最近鄰算法（1－NN）對E中樣本分類，將所有錯分的樣本加入到E~中。這種算法產生的一致子集并不一定是最小的，但它保留了負例邊界附加的樣本；同時去掉了負例中遠離邊界的樣本，從而達到減少負例的目的。

e)鄰域清理（neighborhood cleaning rule，NCL）[17]。該方法利用Wilson改進的最近鄰規則（edited nearest neighbor， ENN）[18]對多數類進行向下采樣。ENN的基本思想是去掉那些類標與離它最近的三個樣本中的兩個類標不同的樣本。但多數類的樣本附近通常都是多數類的樣本，因此ENN去掉的樣本是非常有限的。NCL對ENN作了一點改進，以去掉更多的樣本。其基本算法如下：對訓練集中的每個樣本X找出離它最近的三個樣本，若X為負例即屬于多數類，且三個最近鄰樣本中有兩個以上為正例，則去掉X；若X為正例即屬于少數類，且三個最近鄰樣本中有兩個以上為負例，則去掉三個最近鄰樣本中的負例。

f)虛擬少數類向上采樣（synthetic minority over－sampling technique，SMOTE）。該方法是Chawla等人[19]提出的一種向上采樣方法。它建立這樣的假設之上：相距較近的正例之間的樣本仍是正例。其主要思想是在相距較近的正例之間插入人造的正例。具體算法如下：對少數類的每一個樣本X，搜索其k（通常取為5）個最近鄰；然后隨機選取這k個最近鄰中的一個設為X~，再在X與X~之間進行隨機線性插值，構造出新的少數類樣本，即新樣本

其中：rand(0，1)表示區間(0，1)的一個隨機數。若需要更多的虛擬樣本，重復以上步驟即可。SMOTE使分類器的分類平面向多數類的空間伸展，同時可有效地避免隨機向上采樣的過學習問題。

圖1是SMOTE算法的效果，(a)為原始樣本分布圖；（b）為使用SMOTE方法增加了兩倍虛擬樣本后的分布圖。可以看出SMOTE方法增加的虛擬樣本基本保持了原始樣本的分布，但增加的虛擬樣本大多分布于原始樣本內部，而在邊緣附近則較少。

以上是基于數據采樣的幾種處理不平衡數據的基本方法。近幾年專家們針對這些基本方法的不足提出了許多改進的新方法。例如，Kubat等人[11]提出的單邊選擇（one－sided selection， OSS）的向下采樣方法，將Tomek links方法與CNN方法結合起來；Gustavo等人將向上采樣與向下采樣方法結合[14]，提出SMOTE+Tomek links和SMOTE+ENN方法；Taeho等人提出基于聚類的向上采樣方法[20]，可同時處理類間不平衡以及類內不平衡；Guo Hong－yu等人在進行boosting過程中尋找各類的硬樣本，再利用這些特殊樣本生成新的虛擬樣本[21]；Han Hui等人提出Borderline－SMOTE方法[22]，僅對少數類的邊界數據進行向上采樣。

2．2分類方法

分類方法針對的是分類算法而不是數據集，它們通過改進現有分類算法來處理不平衡數據集。下面介紹這類方法的一些研究進展。

標準的Boosting算法如Adaboost[23]沒有考慮不平衡數據集的特點，錯分樣本所增加的權重與正分樣本所減少的權重比例是相同的，因此傳統的Boosting算法對少數類的效果不佳。Joshi等人針對這點不足，提出了一種改進的Boosting算法，在更新權重時，賦予預測正例（TP，FP）權重和預測負例權重（TN，FN）不同的改變量。這種算法有效提高了正例預測的精度[24]。

支持向量機（support vector machine， SVM）在處理不平衡數據時，分類面會偏向于少數類，因此會增加少數類的錯分率。Wu Gang等人提出了一種邊界調準算法，通過修改SVM的核函數來調整分類面[15]。

Huang Kai－zhu等人提出biased minimax probabilitiy machine（BMPM）方法來解決不平衡的問題[25]。只要知道各類樣本可靠的均值和協方差矩陣，BMPM就可通過調整測試集實際準確率的下界來求出決策超平面。此外，還有許多有效的分類算法，如基于代價的學習[26]、one－class學習[27]等。

基于分類算法的方法不改變樣本的分布，其基本原理是使分類器更注重少數類，對少數類的樣本更加敏感。但當少數類樣本不能反映其真實分布時，這類算法容易出現過學習現象。

2．3綜合方法

基于數據采樣的方法和基于分類算法的方法都有自身的長處和不足，目前越來越多的研究將兩種類型方法結合。結合方法是對原始數據進行重采樣，以降低數據的不平衡性，然后采用可補償數據不平衡的分類算法進行分類。例如Rehan Akbani等人[28]所使用的SMOTE+biased－SVM方法，首先使用SMOTE方法對少數類向上采樣，降低數據的不平衡程度；然后在分類算法上使用Veropoulos等人[29]提出的biased－SVM方法賦予正負例不同的錯分代價。Rehan Akbani等人通過對比實驗驗證了他們的方法要優于單純使用基于數據采樣或基于分類算法的方法。

這類算法有效的關鍵在于如何將兩種類型的方法有機結合，使得既可有效發揮兩種類型方法的長處，同時又可避免各自的弱點。目前兩種類型方法結合的綜合方法還比較少，但無論在理論還是實踐上，這類方法都表現出一定的優越性。

3結束語

不平衡數據集的分類問題是數據分類的難題之一，其困難主要是由不平衡數據集自身的特點以及傳統分類算法的局限性造成的。本文首先介紹了不平衡數據分類的性能評價標準和針對不平衡數據本身的數據采樣方法；然后介紹了針對不平衡數據集的改進分類方法；最后介紹了利用不平衡數據本身的數據采樣與不平衡數據集分類兩者結合的方法。

參考文獻：

[1]EZAWA K J， SINGH M， NORTON S W. Learning goal oriented Bayesian networks for telecommunications management[C]//Proc of the 13th International Conference on Machine Learning. San Fransisco: Morgan Kaufmann， 1996:139－147.

[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]KUBAT M， HOLTE R， MATWIN S. Machine learning for the detection of oil spills in satellite radar images[J]. Machine Learning， 1998，30(2):195-215.

[4]BOSCH A T， HERIK H J， DAELEMANS W. When small disjuncts abound， try lazy learning: a case study[C]//Proc of the 7th Belgian－Dutch Conference on Machine Learning. 1997:109－118.

[5]ZHENG Zhao－hui， WU Xiao－yun， SRIHARI R. Feature selection for text categorization on imbalanced data[J]. SIGKDD Explorations， 2004，6(1):80-89.

[6]FAWCETT T， PROVOST F. Combining data mining and machine learning for effective user profile[C]//Proc of the 2nd International Conference on Knowledge Discovery and Data Mining. Portland: AAAI Press， 1996:8－13.

[7]JAPKOWICZ N. Learning form imbalanced data sets: a comparison of various strategies， WS-00-05[R]. Menlo Park: AAAI Press， 2000.

[8]CHAWLA N V， JAPKOWICZ N， KOLCZ A. Proceedings of the ICML workshop on learning from imbalanced data sets[C]. 2003.

[9]CHAWLA N V， JAPKOWICZ N， KOLCZ A. Editorial: special issue on learning from imbalanced data sets[J]. ACM SIGKDD Exploration Newsletter， 2004，6(1):1-6.

[10]BRADLEY A.The use of the area under the ROC curve in the evaluation of machine learning algorithms[J]. Pattern Recognition， 1997，30(6):1145－1159.

[11]KUBAT M， MATWIN S. Addressing the course of imbalanced trai-ning sets: one－sided selection[C]//Proc of the 14th International Conference on Marchine Learning. San Fransisco: Morgan Kaufmann， 1997:179－186.

[12]HAND D J， TILL R J. A simple generalisation of the area under the ROC curve for multiple class classification problems[J]. Machine Learning， 2001，45(2):171－186.

[13]BARANDELA R， VALDOVINOS R M， SANCHEZ J S. New applications of ensembles of classifiers[J]. Pattern Analysis and Applications， 2003， 6(3):245-256.

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

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

[16]HART P E. The condensed nearest neighbor rule[J]. IEEE Trans on Information Theory， 1968，14(3):515-516.

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

[18]WILSON D L. Asymptotic properties of nearest neighbor rules using edited data[J]. IEEE Trans on Systems， Man and Communications， 1972，2(3):408-421.

[19]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.

[20]TAEHO J， NATHALIE J. Class imbalances versus small disjuncts[J]. SIGKDD Explorations， 2004，6(1):40-49.

[21]GUO Hong－yu， HERNA L V. Learning from imbalanced data sets with boosting and data generation: the dataBoost－IM approach[J]. SIGKDD Explorations， 2004，6(1):30-39.

[22]HAN Hui， WANG Wen－yuan， MAO Bing－huan. Borderline－SMOTE: a new over－sampling method in imbalanced data sets learning[C]//Proc of International Conference on Intelligent Computing. 2005:878-887.

[23]FREUND Y， SCHAPIRE R. A decision theoretic generalization of on－line learning and an application to boosting[J]. Journal of Compu-ter and System Sciences， 1997，55(11):119－139.

[24]JOSHI M， KUMAR V， AGARWAL R. Evaluating boosting algorithms to classify rare classes: comparison and improvements[C]//Proc of the 1st IEEE International Conference on Data Mining. Washington DC: IEEE Computer Society， 2001:257-264.

[25]HUANG Kai－zhu， YANG Hai－qin， KING I， et al. Learning classi-fiers from imbalanced data based on biased minimax probability machine[C]//Proc of IEEE Computer Society Conference on Computer Vision and Pattern Recognition. 2004:558-563.

[26]MARGINEANTU D D， DIETTERICH T G. Bootstrap methods for the cost－sensitive evaluation of classifiers[C]//Proc of International Conference on Machine Learning. 2000:582-590.

[27]MANEVITZ L M， YOUSEF M. One－class VMs for document classification[J]. Journal of Machine Learning Research， 2001，2(1):139－154.

[28]AKBANI R， KWEK S， JAPKOWICZ N. Applying support vector machines to imbalanced datasets[C]//Proc of the 15th European Conference on Machines Learning. 2004:39-50.

[29]VEROPOULOS K， CAMPBELL C， CRISTIANINI N. Controlling the sensitivity of support vector machines[C]//Proc of International Joint Conference on AI. 1999:55-60.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”