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

陳湘濤，高亞靜

(湖南大學(xué) 信息科學(xué)與工程學(xué)院,湖南 長沙，410082)

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

陳湘濤，高亞靜

(湖南大學(xué) 信息科學(xué)與工程學(xué)院,湖南 長沙，410082)

不平衡分類問題始于二分類任務(wù)中的數(shù)據(jù)偏態(tài)問題，當(dāng)傳統(tǒng)機(jī)器學(xué)習(xí)分類方法應(yīng)用于不平衡數(shù)據(jù)集時(shí)，分類效果往往不盡人意。因此，許多用于處理不平衡數(shù)據(jù)集的分類器模型已經(jīng)被提出,包括數(shù)據(jù)層面的方法、算法層面的方法、混合方法以及集成分類器模型。本文主要通過討論不平衡分類問題的實(shí)質(zhì)，對(duì)不平衡分類問題的研究進(jìn)行綜述，介紹幾種主要的解決策略，針對(duì)不平衡數(shù)據(jù)特點(diǎn)討論適應(yīng)不平衡特點(diǎn)的性能指標(biāo)，并針對(duì)已有研究分析所存在的問題及挑戰(zhàn)。

機(jī)器學(xué)習(xí)；不平衡分類；數(shù)據(jù)層面；算法層面；集成學(xué)習(xí)

不平衡分類問題始于二分類任務(wù)中數(shù)據(jù)存在偏態(tài)的問題[1]，即在二分類任務(wù)中，其中一類的樣本數(shù)目遠(yuǎn)遠(yuǎn)大于另一類的樣本數(shù)目，即類與類之間的樣本不平衡。傳統(tǒng)的機(jī)器學(xué)習(xí)分類算法假設(shè)類的樣本數(shù)量大致相同，然而，在很多的現(xiàn)實(shí)情況中，類的樣本分布是呈現(xiàn)偏態(tài)的。當(dāng)傳統(tǒng)的分類方法應(yīng)用于不平衡數(shù)據(jù)集時(shí)，為了提高分類的整體精度，分類器會(huì)減少對(duì)少數(shù)類的關(guān)注，而偏向于多數(shù)類，從而分類邊界將偏向于擁有樣本數(shù)較少的類別導(dǎo)致多數(shù)類分類空間增大，少數(shù)類樣本難以被識(shí)別出來，分類性能受到嚴(yán)重影響。為此，需要設(shè)計(jì)出智能化的方法克服分類器對(duì)多數(shù)類的偏向問題。

同時(shí)，少數(shù)類在數(shù)據(jù)挖掘時(shí)又很重要，尤其是當(dāng)少數(shù)類攜帶很多重要及有用的信息時(shí)。例如，在欺詐檢測(cè)工作中，更加注重檢測(cè)欺詐的交易[2]；在通訊工程中對(duì)失敗設(shè)備的識(shí)別更感興趣[3]；在工業(yè)工程中更傾向于識(shí)別焊接失敗的情況[4]；在客戶流失檢測(cè)中，流失客戶的數(shù)量相對(duì)較少，屬于少數(shù)類，在實(shí)際應(yīng)用中，正確檢測(cè)流失客戶并采取阻止方案是很重要的，因此，實(shí)際應(yīng)用中更希望正確檢測(cè)出少數(shù)類；在汽車保險(xiǎn)欺詐檢測(cè)的研究中，欺詐客戶只占總樣本數(shù)的很少部分，但對(duì)這種不平衡的數(shù)據(jù)分類時(shí)，傳統(tǒng)方法往往將欺詐客戶誤分類為正?？蛻?，雖然整體的準(zhǔn)確率很高，但是誤分類欺詐客戶將會(huì)給保險(xiǎn)公司造成巨大的損失。因此，現(xiàn)實(shí)應(yīng)用中少數(shù)類具有特殊的意義，如果分類錯(cuò)誤會(huì)帶來很大的損失，因此不平衡分類的研究具有非常重要的實(shí)際研究?jī)r(jià)值。

不平衡分類問題的研究在數(shù)據(jù)挖掘領(lǐng)域引起了很多人的興趣，很多方法相繼被提出，如文獻(xiàn)[5]提出了不平衡分類的研究，García等人[6]針對(duì)不平衡數(shù)據(jù)集提出了各種數(shù)據(jù)處理方法，包括不平衡數(shù)據(jù)預(yù)處理方法、采樣方法以及不平衡數(shù)據(jù)的清理。文獻(xiàn)[7]致力于研究不平衡預(yù)測(cè)模型的建立，文獻(xiàn)[8]則研究了利用集成學(xué)習(xí)來解決不平衡分類問題；López 等人[9]則提出從不平衡數(shù)據(jù)特征這個(gè)新的視角研究不平衡數(shù)據(jù)，并討論針對(duì)偏態(tài)數(shù)據(jù)集分類器的評(píng)價(jià)標(biāo)準(zhǔn)。在過去的幾年里，不平衡分類在實(shí)際的應(yīng)用領(lǐng)域也取得了很多的成就，如電子郵件過濾[10]、欺詐檢測(cè)[11]、衛(wèi)星圖像溢油的檢測(cè)[12]、醫(yī)療診斷[13]、車輛診斷[14]等。

根據(jù)以上的研究背景，本文主要對(duì)不平衡分類問題進(jìn)行研究綜述，討論不平衡分類問題的研究現(xiàn)狀，并分析在現(xiàn)實(shí)背景下我們所面臨的主要問題，試圖為數(shù)據(jù)挖掘等相關(guān)領(lǐng)域的研究提供有益參考。

1 影響稀有類數(shù)據(jù)分類的因素

對(duì)不平衡數(shù)據(jù)集分類，影響其分類的因素來源于其自身特點(diǎn)。研究表明，除類分布不平衡外，還包括數(shù)據(jù)的可分離性、子概念問題等，這些數(shù)據(jù)集內(nèi)部的特點(diǎn)通常嚴(yán)重影響少數(shù)類數(shù)據(jù)的分類。

影響少數(shù)類分類的最主要因素是類分布不平衡。在二分類中，兩類的樣本分布不平衡，其中一類的樣本數(shù)目大于另一類樣本數(shù)目。此時(shí)，少數(shù)類樣本的數(shù)目可能是極少的，因此，少數(shù)類樣本信息不足以正確表達(dá)少數(shù)類，在分類過程中，少數(shù)類樣本提供給分類器的信息太少而使分類器無法正確識(shí)別。另外一種情況是少數(shù)類樣本相對(duì)于多數(shù)類樣本占有比例很小，當(dāng)類分布不平衡時(shí)，其中少數(shù)類的樣本數(shù)，使得分類器不能獲得足夠的信息，分類器偏向多數(shù)類，不利于少數(shù)類分類。文獻(xiàn)[15]研究了不平衡的類分布對(duì)判定樹分類性能的影響；研究表明，在部分應(yīng)用中，類分布不平衡比例超過1∶35時(shí)就難以建立正確的分類器，更有甚者，當(dāng)不平衡比例達(dá)到1∶10時(shí)有些應(yīng)用就很難建立正確的分類器了[16]。

除了數(shù)據(jù)分布不平衡外，影響少數(shù)類分布的因素還有數(shù)據(jù)的可分離性。高度線性可分的數(shù)據(jù)集對(duì)不平衡是不敏感的，即使類分布不平衡，其分類性能也不會(huì)受到影響。然而，當(dāng)數(shù)據(jù)集非線性可分時(shí)，不平衡數(shù)據(jù)分類時(shí)，其性能會(huì)受到明顯影響，性能降低。

另外，類內(nèi)子概念問題也會(huì)影響到分類性能。子概念問題反映的是類內(nèi)不平衡[17]，即同一類樣本的分布不平衡。前面提到的樣本不平衡是指類與類之間的不平衡，子概念問題使得數(shù)據(jù)集內(nèi)部進(jìn)一步變得復(fù)雜，從而導(dǎo)致其分類性能下降。

2 不平衡分類問題解決策略

不平衡分類問題是不平衡問題的重要分支，因此，得到了學(xué)者們的廣泛研究，產(chǎn)生了許多優(yōu)秀的方法?？偨Y(jié)來說，不平衡分類的主要包括數(shù)據(jù)層面、算法層面、集成學(xué)習(xí)的策略。數(shù)據(jù)層面的主要思想是改變?cè)紨?shù)據(jù)集的分布，增加少數(shù)類樣本或減少多數(shù)類樣本，使不平衡數(shù)據(jù)集趨于平衡。算法層面通過直接修改已有的分類器，使之適應(yīng)不平衡數(shù)據(jù)特征。集成方法使用集成的思想提高分類器的性能。

2.1 數(shù)據(jù)層面

通過近些年的研究，數(shù)據(jù)層面的采樣思想在改進(jìn)數(shù)據(jù)集方面展現(xiàn)了極大地潛力[18]。數(shù)據(jù)層面的分類方法旨在改變數(shù)據(jù)分布，對(duì)數(shù)據(jù)集進(jìn)行重采樣，以降低類與類之間樣本不平衡程度，使修改后的數(shù)據(jù)可以應(yīng)用標(biāo)準(zhǔn)的學(xué)習(xí)算法。因此根據(jù)不平衡數(shù)據(jù)集的重采樣方法的不同，分為過采樣方法和欠采樣以及混合采樣方法。

2.1.1 過采樣方法

過采樣方法的思想是增加少數(shù)類樣本。最簡(jiǎn)單的過采樣方法是隨機(jī)過采樣方法(ROS)，但隨即過采樣方法生成的實(shí)體和原數(shù)據(jù)集的實(shí)體相似性大，因此會(huì)產(chǎn)生過擬合問題。為解決過擬合問題，文獻(xiàn)[19]提出樣本生成技術(shù)SMOTE，該方法根據(jù)為每個(gè)稀有類隨機(jī)選取n個(gè)鄰近樣本，在連線上隨機(jī)選取點(diǎn)生成無重復(fù)的新的稀有類樣本。實(shí)驗(yàn)證明，SMOTE方法優(yōu)于ROS方法，SMOTE方法通過生成新的不同的少數(shù)類，避免了過擬合問題。然而，SMOTE方法盲目的生成虛構(gòu)的少數(shù)類，在生成新樣本的過程中并沒有考慮多數(shù)類，因此可能會(huì)引起過生成問題，即生成的實(shí)體和原數(shù)據(jù)集中實(shí)體重疊[20]。為解決過生成問題，很多方法被提出。文獻(xiàn)[21]提出Safe-level SMOTE方法，該方法提出為少數(shù)類樣本計(jì)算“安全層”的思想，然后生成接近安全階段的樣本。文獻(xiàn)[22]提出的Borderline-SMOTE方法，通過分析識(shí)別邊界樣本，對(duì)邊界的少數(shù)類進(jìn)行過采樣，提高邊界的識(shí)別率，但該方法只對(duì)靠近邊界的少數(shù)類樣本進(jìn)行過采樣。另外自適應(yīng)合成抽樣算法(adaptive synthetic sampling，ADASYN)[23]，該方法主要以密度分布作為標(biāo)準(zhǔn)，自動(dòng)生成少數(shù)類樣本，為少數(shù)類樣本賦予權(quán)重，并不斷自適應(yīng)改變，自適應(yīng)為每個(gè)樣本生成相應(yīng)的少數(shù)類樣本。然而，Borderline-SMOTE和ADASYN方法無法識(shí)別出邊界所有的少數(shù)類樣本[18]?；谝陨蠁栴}，文獻(xiàn)[24]中提出A-SUMO方法，使用半監(jiān)督層次聚類對(duì)少數(shù)類聚類，利用分類復(fù)雜性和交叉驗(yàn)證的方法自適應(yīng)決策定過采樣子聚類群的大小，通過考慮每個(gè)子簇中邊界的少數(shù)類實(shí)體來識(shí)別比較難以學(xué)習(xí)的樣本，該思想通過考慮在聚類和過采樣階段中的多數(shù)類，避免生成重疊樣本。

2.1.2 欠采樣方法

欠采樣方法通過舍棄部分多數(shù)類樣本的方法平衡訓(xùn)練數(shù)據(jù)集。最簡(jiǎn)單的欠采樣方法是文獻(xiàn)[15]中提出的隨機(jī)欠采樣方法，該方法隨機(jī)選擇部分多數(shù)類樣本作為訓(xùn)練數(shù)據(jù)集中的多數(shù)類樣本。然而該方法有個(gè)很大的弊端則是隨機(jī)選擇多數(shù)類樣本可能會(huì)去除一些重要的多數(shù)類樣本，因此會(huì)產(chǎn)生決策邊界的失真。在此基礎(chǔ)上，很多先進(jìn)的思想被先后提出，Mani和Zhang[25]提出四種不同的欠采樣思想，NearMiss-1，NearMiss-2，NearMiss-3和MostDistant，該思想主要使用K近鄰的方法。NearMiss欠采樣方法根據(jù)與少數(shù)類相鄰的多數(shù)類被選擇來訓(xùn)練決策邊界[26]。Cateni等人在[27]中提出基于相似性的欠采樣方法(SBU)，為了減少信息的丟失以及平衡數(shù)據(jù)集，SBU趨向于減少密度空間中的多數(shù)類實(shí)體，根據(jù)歐幾里得距離計(jì)算每一對(duì)多數(shù)類的相異值，相異性值小的多數(shù)類被去除。然而現(xiàn)有的欠采樣方法存在的問題是：性能不穩(wěn)定。因此為了最大限度的提高分類器的性能，降低在欠采樣過程中對(duì)多數(shù)類的損失，文獻(xiàn)[28]提出基于遺傳算法的欠抽樣方法來解決不平衡分類問題。該文獻(xiàn)提出GAUS(genetic algorithm based under sampling)，使用遺傳算法進(jìn)行樣本選擇將分類性能作為遺傳算法的適應(yīng)函數(shù)，該方法在一定程度上解決了性能不穩(wěn)定問題，并減少了數(shù)據(jù)分布丟失。另外，欠采樣方法使用之后的數(shù)據(jù)集在訓(xùn)練過程中保持不變，這樣會(huì)導(dǎo)致一些有用的多數(shù)類無法參與訓(xùn)練過程，會(huì)丟失有效信息[29-30]，因此，提出一種ODUNPNN單方面的動(dòng)態(tài)欠采樣技術(shù)，它可以適用訓(xùn)練過程中所有的樣本，并且動(dòng)態(tài)決定哪個(gè)多數(shù)類樣本應(yīng)該被用來進(jìn)行分類器的訓(xùn)練。該方法是單方面動(dòng)態(tài)欠采樣技術(shù)與無傳播神經(jīng)網(wǎng)絡(luò)的結(jié)合，它考慮所有的訓(xùn)練樣本，在每次迭代中動(dòng)態(tài)欠采樣多數(shù)類。以此動(dòng)態(tài)過程減少采樣過程中信息的丟失。文獻(xiàn)[31]根據(jù)對(duì)多個(gè)不平衡數(shù)據(jù)集進(jìn)行不同重采樣方法的試驗(yàn)統(tǒng)計(jì)發(fā)現(xiàn)，SMOTE-ENN是效果較好次數(shù)較多的混合采樣方法，ROS是效果較好次數(shù)較多的過采樣方法，而RUS是效果較好次數(shù)較多的欠采樣方法。但實(shí)驗(yàn)結(jié)果只是對(duì)多個(gè)不平衡數(shù)據(jù)集效果次數(shù)的統(tǒng)計(jì)，針對(duì)不同的不平衡數(shù)據(jù)集，其適應(yīng)的重采樣方法不同，試驗(yàn)統(tǒng)計(jì)結(jié)果對(duì)以后的實(shí)驗(yàn)分析具有指導(dǎo)作用。

2.2 算法層面

算法層面致力于修改已存在的分類器減少對(duì)少數(shù)類的偏向，該思想研究方向主要為修改分類器的視角，以及如何精確預(yù)測(cè)分類結(jié)果的成敗。在構(gòu)造合適分類器方面，文獻(xiàn)[32]通過減小多數(shù)類樣本在訓(xùn)練中所占比例訓(xùn)練合適的分類邊界。

另外，很多研究根據(jù)傳統(tǒng)分類算法的改進(jìn)，減緩分類器對(duì)多數(shù)類的偏向。其中文獻(xiàn)[51]文章通過基于關(guān)聯(lián)規(guī)則的分類方法的研究發(fā)現(xiàn)，基于關(guān)聯(lián)規(guī)則分類方法對(duì)不平衡數(shù)據(jù)集分類時(shí)，由于其根據(jù)置信度選擇規(guī)則的策略，多數(shù)類中置信度高，而少數(shù)類置信度低，因此使用基于關(guān)聯(lián)規(guī)則的分類方法對(duì)不平衡數(shù)據(jù)分類時(shí)，分類結(jié)果會(huì)會(huì)偏向?qū)Χ鄶?shù)類。文章提出類置信度比例的概念，傳統(tǒng)置信度檢驗(yàn)有多少預(yù)測(cè)正、負(fù)樣本是實(shí)際正負(fù)樣本，類置信度專注于有多少實(shí)際正負(fù)樣本是預(yù)測(cè)正確的。用類置信度代替置信度，提出類置信度比例決策樹，通過考慮類之間的聯(lián)系，提高決策樹的魯棒性和對(duì)類大小的敏感性?；诖怂枷耄墨I(xiàn)[52]提出了類置信度加權(quán)kNN算法，通過kNN算法類置信度加權(quán)，對(duì)多數(shù)類的偏向。對(duì)kNN算法的修改，文獻(xiàn)[53]通過少數(shù)類新樣本的生成減緩決策邊界的錯(cuò)誤，在對(duì)樣本檢測(cè)時(shí)，算法考慮了少數(shù)類中群組距離減緩對(duì)多數(shù)類的偏向。文獻(xiàn)[54]通過離子群優(yōu)化算法提高不平衡數(shù)據(jù)分類性能，另外對(duì)SVM的修改[55]，該文獻(xiàn)提出OCSVM算法，該算法被用于不平衡文本分類中取得較好的結(jié)果。另外基于模式不平衡分類的研究，文獻(xiàn)[56]提出ICAEP分類器，它使用最小編碼推理給新樣本分類，這種方法被用在不平衡分類中[57]，實(shí)驗(yàn)證明ICAEP可以使用模式構(gòu)造適合不平衡數(shù)據(jù)集的分類模型。在文獻(xiàn)[58]中，作者提出一種新的基于模式的不平衡算法PBC4cip，該方法結(jié)合不平衡水平下模式的支持度，對(duì)每個(gè)類支持度之和加權(quán)，減緩不平衡對(duì)分類器的影響。

基于算法層面的方法主要是代價(jià)敏感方法[33]，其考慮的是樣本誤分類的代價(jià)，由于可以賦予不同類的分類錯(cuò)誤不同的代價(jià)，對(duì)原本是少數(shù)類而被誤分為多數(shù)類的樣本賦予更高的誤分代價(jià)。因此，基于代價(jià)敏感因子的提出，很多基于代價(jià)敏感的分類算法被提出。其中文獻(xiàn)[34]將代價(jià)敏感思想與松弛變量結(jié)合對(duì)SVM進(jìn)行改進(jìn)，使SVM應(yīng)用超平面分類時(shí)對(duì)代價(jià)敏感。另外，在多類問題中的代價(jià)敏感SVM[35],在此文獻(xiàn)中，也考慮了采樣偏置。文獻(xiàn)[36]中的加權(quán)線性模型WFLD，該判別模型采用加權(quán)Fisher，通過對(duì)多數(shù)類和少數(shù)類的類內(nèi)離散度計(jì)算，根據(jù)離散度矩陣分別對(duì)多數(shù)類和少數(shù)類加權(quán)，根據(jù)類內(nèi)離散度矩陣對(duì)兩類調(diào)節(jié)平衡。總結(jié)以上代價(jià)敏感方法，都是對(duì)全局進(jìn)行代價(jià)學(xué)習(xí)，是全局性模型。另外，文獻(xiàn)[37]提出的局部代價(jià)敏感算法，該方法在對(duì)新樣本預(yù)測(cè)分類時(shí)，對(duì)樣本的k個(gè)近鄰以加權(quán)的方式進(jìn)行訓(xùn)練，根據(jù)對(duì)局部樣本的代價(jià)敏感學(xué)習(xí)，得到預(yù)測(cè)分類器。代價(jià)敏感方法依賴于代價(jià)敏感矩陣，然而存在最大的障礙則是很多數(shù)據(jù)集中并沒有給出代價(jià)敏感矩陣[38]。

通過已有的研究發(fā)現(xiàn)，算法層面的思想并沒有像數(shù)據(jù)層面研究的廣泛，這是因?yàn)樗容^依賴于特殊的分類器，當(dāng)解決類不平衡問題時(shí)，該方法需要針對(duì)某個(gè)特殊的分類器[39]。另外文獻(xiàn)[40]給出基于對(duì)比模式分類器解決不平衡問題，它根據(jù)對(duì)比模式支持度對(duì)數(shù)據(jù)集進(jìn)行加權(quán)，以加權(quán)數(shù)據(jù)集訓(xùn)練分類器，該方法結(jié)合了模式分類的優(yōu)點(diǎn)處理不平衡問題。

2.3 混合方法

該方法主要結(jié)合數(shù)據(jù)層面和算法層面并充分利用它們的優(yōu)點(diǎn)，減少二者的缺點(diǎn)[41]。比較流行的方法是結(jié)合數(shù)據(jù)層面的解決方法和分類器集成，這種結(jié)合可以產(chǎn)生有效的學(xué)習(xí)方法[42]。另外也有很多研究致力于采樣方法和代價(jià)敏感方法的結(jié)合[43]。同時(shí)，混合方法也聚集了數(shù)據(jù)層面和算法層面的缺點(diǎn)，如何使二者的結(jié)合達(dá)到最好的結(jié)果需更多的分析二者的聯(lián)系。

2.4 分類器集成方法

在處理不平衡分類問題中，集成學(xué)習(xí)受到很多學(xué)者的青睞[44]。其中采樣思想和集成學(xué)習(xí)方法的結(jié)合被廣泛應(yīng)用到處理不平衡分類問題中。Chawal等人[58]在SMOTE和Boosting的基礎(chǔ)上提出的SMOTEBoost，Seiffert[59]等人提出的混合集成思想RUSBoost，該方法結(jié)合了隨機(jī)采樣和Boosting集成，實(shí)驗(yàn)證明，RUSBoost方法要優(yōu)于SMOTEBoost方法，Liu[60]等人提出的EasyEnsemble方法，該方法結(jié)合了Bagging、隨機(jī)欠采樣以及AdaBoost[45]。另外。過采樣與集成學(xué)習(xí)方法的結(jié)合[50]，可以平衡樣本，同時(shí)也可以提高整體分類性能。然而，重采樣和集成思想的結(jié)合，在每次迭代中，都會(huì)存在重采樣思想所出現(xiàn)的問題，如過擬合問題以及數(shù)據(jù)丟失問題。因而，為避免出現(xiàn)重采樣所帶來的問題，文獻(xiàn)[62]提出一種新的集成學(xué)習(xí)方法解決不平衡問題，該方法對(duì)原始多數(shù)類樣本采用一種分裂策略，在不改變?cè)紨?shù)據(jù)分布的情況下，將原始不平衡問題轉(zhuǎn)化為多個(gè)平衡的問題，該方法避免了重采樣所遺留的問題。

重采樣和集成的結(jié)合可能會(huì)帶來很多問題，因而，很多基于代價(jià)敏感與集成學(xué)習(xí)的結(jié)合的研究方法被提出。文獻(xiàn)[61]中提出的Metacost算法，該算法采用bagging決定訓(xùn)練數(shù)據(jù)集的最優(yōu)類標(biāo)簽，然而，它仍然很難決定精確地誤分類代價(jià)。另外，由于Adaboost是為了提高整體的精度，因而，會(huì)偏向多數(shù)類[46]。因此，基于此的改進(jìn)方法，如AdaCost[47]、RareBoost[48]，這些方法主要改變迭代過程中的權(quán)重更新策略，對(duì)錯(cuò)分的稀有類樣本賦予更高的權(quán)值。文獻(xiàn)[49]通過研究代價(jià)敏感決策樹集成有效解決不平衡分類問題，在文獻(xiàn)[8]中提出新的集成思想，它將bagging，boosting，混合方法用于集成學(xué)習(xí)，構(gòu)造有效分類器。

3 分類器評(píng)價(jià)指標(biāo)問題

傳統(tǒng)的分類指標(biāo)會(huì)使分類器偏向于多數(shù)類，為了使分類精度更高，一般會(huì)把樣本分為多數(shù)類，但不能正確識(shí)別少數(shù)類。因此，應(yīng)有適應(yīng)于不平衡數(shù)據(jù)集特點(diǎn)的評(píng)價(jià)指標(biāo)。通過對(duì)不平衡數(shù)據(jù)集分類問題的研究，適用于不平衡數(shù)據(jù)集分類的評(píng)價(jià)指標(biāo)主要包括G-mean、F-measure和ROC等。

在混淆矩陣概念的基礎(chǔ)上，提出了不平衡數(shù)據(jù)集分類的評(píng)價(jià)指標(biāo)。在兩類問題中，用混淆矩陣表示兩類中樣本識(shí)別的情況，如表1。

表1 關(guān)于兩類問題的混淆矩陣

在兩類問題中，少數(shù)類表示為正類Positive，多數(shù)類表示為負(fù)類Negative。TP表示正類樣本預(yù)測(cè)仍為正類，F(xiàn)N表示正類樣本預(yù)測(cè)結(jié)果為負(fù)類，F(xiàn)P表示負(fù)類樣本預(yù)測(cè)為正類，TN表示負(fù)類預(yù)測(cè)仍為負(fù)類。

(1)分類器的G-mean標(biāo)準(zhǔn)：

其中Positive Accuracy是正類正確率，Negative Accuracy是負(fù)類正確率。

根據(jù)G-mean的標(biāo)準(zhǔn)定義，改評(píng)價(jià)指標(biāo)根據(jù)同時(shí)考慮了正類準(zhǔn)確率和負(fù)類準(zhǔn)確率，不僅僅是衡量整體的分類準(zhǔn)確率，因此，改評(píng)價(jià)指標(biāo)比較適合用來評(píng)價(jià)不平衡數(shù)據(jù)分類。

(2)分類器的F-measure標(biāo)準(zhǔn)

其中Recall為查全率，Precision為查準(zhǔn)率；β表示調(diào)節(jié)系數(shù)，用來調(diào)節(jié)Recall和Precision，通過定義看出，F(xiàn)-measure同時(shí)考慮到正類和負(fù)類，也更注重對(duì)負(fù)類分類性能的評(píng)價(jià)，因此，該評(píng)價(jià)標(biāo)準(zhǔn)也更適合應(yīng)用于不平衡分類評(píng)價(jià)。

(3)ROC曲線

經(jīng)研究表明，ROC曲線(Receiver Operating Characteristics Curves)可以作為不平衡分類的性能評(píng)價(jià)指標(biāo)，其中ROC曲線越凸，其對(duì)應(yīng)分類器的性能越好，泛化能力越強(qiáng)。其表現(xiàn)方式可以由圖1進(jìn)行表示。其中X軸表示FPR，Y軸表示TPR。其中，兩條ROC曲線L1和L2，，A,B,C,D,E和F表示的是ROC點(diǎn)，從圖中可知，點(diǎn)A(0，1)表示的分類性能最好，B點(diǎn)最接近A點(diǎn)，其對(duì)應(yīng)的分類器性能要比其他幾個(gè)點(diǎn)優(yōu)越。而E點(diǎn)處在對(duì)角線上，這樣的分類器效果相當(dāng)于隨機(jī)分類的分類器，而F點(diǎn)的性能不如E點(diǎn)，即F點(diǎn)的性能不如隨機(jī)分類的分類器性能。

圖1 ROC曲線圖Fig.1 ROC curves

在不平衡分類器評(píng)價(jià)中，通常使用ROC曲線下與X軸所成面積即AUC(Area Under the ROC)，對(duì)分類器性能進(jìn)行量化分析，以面積的形式表示ROC曲線對(duì)應(yīng)的分類器的泛化能力。由圖1可以看出，L1對(duì)應(yīng)面積比L2對(duì)應(yīng)的面積大，因此L1對(duì)應(yīng)的分類器的平均性能要高于L2所對(duì)應(yīng)的分類器的平均性能。

4 問題與挑戰(zhàn)

由于不平衡數(shù)據(jù)集的偏態(tài)分布，以及傳統(tǒng)分類算法的局限性，使不平衡數(shù)據(jù)集的分類成為分類問題中的挑戰(zhàn)及難點(diǎn)之一。另外根據(jù)已有研究，分析在機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘及大數(shù)據(jù)環(huán)境下，不平衡分類問題所面臨的挑戰(zhàn)與問題。

4.1 類結(jié)構(gòu)角度分析：

眾所周知不平衡分類方法主要根據(jù)數(shù)據(jù)層面和算法層面，這兩種方法是從不平衡數(shù)據(jù)集整體出發(fā)解決不平衡分為問題，另外性能的減低也可能由不同樣本的分布產(chǎn)生，尤其是少數(shù)類樣本。文獻(xiàn)[45]對(duì)少數(shù)類樣本的鄰居定義為四部分：安全點(diǎn)、邊界點(diǎn)、稀有類和離群點(diǎn)。因此，可以從類結(jié)構(gòu)的角度分析少數(shù)類結(jié)構(gòu)?？梢杂幸幌骂A(yù)測(cè)方向。

①從不同于分類的角度去解決不平衡問題，可以把少數(shù)類的樣本作為異常點(diǎn)，因此，該問題可以轉(zhuǎn)化為異常檢測(cè)與變化趨勢(shì)檢測(cè)問題。

②在數(shù)據(jù)處理層面，在確立少數(shù)類樣本的結(jié)構(gòu)時(shí)要專注于重要樣本的選擇以及難以識(shí)別樣本?？梢酝ㄟ^重采樣典型樣本，或監(jiān)督學(xué)習(xí)欠采樣處理，避免一些重要的少數(shù)類樣本被去除。

③單獨(dú)研究方向可研究少數(shù)類中噪聲及利群樣本。如何辨別給定的實(shí)體是噪聲數(shù)據(jù)還是離群點(diǎn)？如何鑒定給定點(diǎn)是合適的？

④自適應(yīng)思想，用來調(diào)整分析鄰居的大小。

根據(jù)少數(shù)類結(jié)構(gòu)分析特殊點(diǎn)或重要樣本，可以使少數(shù)類的結(jié)構(gòu)得到維持；分析一些特殊點(diǎn)或重要點(diǎn)，研究樣本的范圍降低，因此可以降低時(shí)間復(fù)雜度，性能也可以提高。

4.2 極度不平衡分類

一般所研究的類不平衡程度在1∶4到1∶100，然而在大數(shù)據(jù)環(huán)境中，會(huì)出現(xiàn)有些類不平衡程度可以達(dá)到1∶1000到1∶1500，缺少對(duì)高度類不平衡現(xiàn)象的研究，在數(shù)據(jù)處理和分類算法分析中將是一個(gè)新的挑戰(zhàn)。在高度不平衡數(shù)據(jù)中，少數(shù)類代表性較差，也缺少一個(gè)清晰的結(jié)構(gòu)。因此普通的不平衡方法應(yīng)用性能會(huì)降低。文獻(xiàn)[46]中對(duì)高度不平衡分類問題，基于SMOTE提出SMOTE-RM采樣方法，對(duì)多數(shù)類樣本進(jìn)行聚類成多個(gè)簇，之后每個(gè)簇與所有的少數(shù)類樣本結(jié)合進(jìn)行分類，該方法則是將原始問題分成多個(gè)子問題。另外預(yù)測(cè)還有以下的方法。

①給少數(shù)類一種授權(quán)，使之可以預(yù)測(cè)或重建一個(gè)潛在的類結(jié)構(gòu)。

②用數(shù)據(jù)特征的方法處理，對(duì)數(shù)據(jù)特征的有效處理可以提高對(duì)少數(shù)類的識(shí)別。

4.3 集成學(xué)習(xí)方法解決不平衡問題

集成方法在解決類不平衡問題中是很受歡迎的方法，Bagging，Boosting、隨機(jī)森林與采樣方法或代價(jià)敏感思想的結(jié)合。但大多數(shù)方法是基于啟發(fā)式的，對(duì)于偏態(tài)分類的分類性能考慮的并不多。根據(jù)已有研究可能存在以下挑戰(zhàn)：

①在使用集成學(xué)習(xí)解決不平衡問題中，缺少對(duì)多樣性的理解，在不平衡數(shù)據(jù)集中，多樣性對(duì)多數(shù)類和少數(shù)類是否都很重要？為提高集成學(xué)習(xí)方法有效解決不平衡分類問題，需要研究不平衡學(xué)習(xí)中多樣性的現(xiàn)象。

②在以往的研究中沒有清晰的指導(dǎo)集成規(guī)模的大小。一般情況下集成規(guī)模的大小是人工選擇的，這會(huì)導(dǎo)致一些相似分類器處于存儲(chǔ)狀態(tài)中。另外對(duì)于研究數(shù)據(jù)集特征和分類器之間的關(guān)系也有很大作用。因此應(yīng)該研究發(fā)展用于不平衡問題中集成修剪技術(shù)。

③在不平衡集成技術(shù)中，大多使用多數(shù)類投票組合的思想，在之后的研究中可以提出新的方法，在組合中要充分利用樣本自身的價(jià)值。

5 總結(jié)

在實(shí)際應(yīng)用中，數(shù)據(jù)分布常常是偏態(tài)的，傳統(tǒng)的機(jī)器學(xué)習(xí)分類方法應(yīng)用在不平衡數(shù)據(jù)中時(shí)，效果往往會(huì)很差，而實(shí)際應(yīng)用中，少數(shù)類的數(shù)據(jù)又是很重要的，具有重要的研究?jī)r(jià)值和使用價(jià)值。針對(duì)不平衡數(shù)據(jù)的分類，學(xué)者們提出很多針對(duì)性的研究方法，本文從數(shù)據(jù)層面、算法層面、集成學(xué)習(xí)三個(gè)角度總結(jié)已有研究，分析不平衡分類中出現(xiàn)的問題及相應(yīng)的解決方法。另外，結(jié)合已有的研究，根據(jù)機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘領(lǐng)域，分析不平衡分類研究中面臨的挑戰(zhàn)，對(duì)今后的研究進(jìn)行方向指導(dǎo)。

[1]Krawczyk B.Learning from imbalanced data:open challenges and future directions[J].Progress in Artificial Intelligence,2016：221-232.

[2]Sahin Y,Bulkan S，Duman E.A cost-sensitive decision tree approach for fraud detection[J].Expert Systems with Applications An International Journal,2013,40(15):5916-5923.

[3]Wei W,Li J,Cao L,et al.Effective detection of sophisticated online banking fraud on extremely imbalanced data[Z].World Wide Web,2013,16(4):449-475.

[4]Liao T W.Classification of weld flaws with imbalanced class data[J].Expert Systems with Applications,2008,35(3):1041-1052.

[5]Sun Y,Wong A K，Kamel M S.Classification of imbalanced data:a review[J].International Journal of Pattern Recognition and Artificial Intelligence,2009,23(4):687-719.

[6]García S,Luengo J，Herrera F.Data preprocessing in data mining[M].Intelligent Systems Reference Library,2015.

[7]Branco P,Torgo L， Ribeiro R.A survey of predictive modelling under imbalanced distributions[Z].arXiv preprint arXiv,2015.

[8]Galar M,Fernandez A,Barrenechea E,et al.A review on ensembles for the class imbalance problem:bagging-,boosting-,and hybrid-based approaches[J].IEEE Transactions on Systems,Man and Cybernetics Part C (Applications and Reviews),2012,42(4):463-484.

[9]RC Prati,GEAPA Batista,DF Silva.Class imbalance revisited:a new experimental setup to assess the performance of treatment methods[J].Knowledge and Information Systems,2015,45(1):1-24.

[10]Dai HL.Class imbalance learning via a fuzzy total margin based support vector machine[J].Applied Soft Computing,2015,31:172-184.

[11]Deng X，Tian X.Nonlinear process fault pattern recognition using statistics kernel PCA similarity factor[J].Neurocomputing,2013,121(18):298-308.

[12]Guo Y，Zhang H Z.Oil spill detection using synthetic aperture radar images and feature selection in shape space[J].International Journal of Applied Earth Observation and Geoinformation,2014,30(1):146-157.

[13]Ozcift A，Gulten A.Classifier ensemble construction with rotation forest to improve medical diagnosis performance of machine learning algorithms[J].Computer Methods Programs Biomedicine,2011,104(3)： 443-51.

[14]Murphey Y L,Chen Z H ，F(xiàn)eldkamp L A.An incremental neural learning framework and its application to vehicle diagnostics[J].Applied Intelligence,2008, 28(1):29-49.

[15]Batista G E,Prati R C，Monard M C.A study of the behavior of several methods for balancing machine learning training data[J].ACM Sigkdd Explorations Newsletter,2004,6(1):20-29.

[16]Joshi M V.Learning Classifier Models for Predicting Rare Phenomena[Z].University of Minnesota,2002.

[17]Japkowicz N.Concept-learning in the presence of between-class and within-class imbalances[J].Biennial Conference of the Canadian Society for Computational Studies of Intelligence,2001,2056:67-77.

[18]Barua S,Islam M M,Yao X,et al.MWMOTE--majority weighted minority oversampling technique for imbalanced data set learning[J].IEEE Transactions on Knowledge and Data Engineering,2014,26(2):405-425.

[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(1):321-357.

[20]López V,Fernández A,García S,et al.An insight into classification with imbalanced data:Empirical results and current trends on using data intrinsic characteristics[J].Information Sciences,2013，250(1):113-141.

[21]Bunkhumpornpat C,Sinapiromsaran K，Lursinsap C.Safe-level-smote:Safe-level-synthetic minority over-sampling technique for handling the class imbalanced problem[C]//in Pacific-Asia Conference on Knowledge Discovery and Data Mining,2009,5476:475-482.

[22]Han H,Wang W Y ，Mao B H.Borderline-SMOTE:a new over-sampling method in imbalanced data sets learning[C]//in International Conference on Intelligent Computing,2005,3644(5):878-887.

[23]He H,Bai Y,Garcia E A,et al.ADASYN:Adaptive synthetic sampling approach for imbalanced learning[C]//in 2008 IEEE International Joint Conference on Neural Networks (IEEE World Congress on Computational Intelligence),2008:1322-1328.

[24]Nekooeimehr I，Lai-Yuen S K.Adaptive semi-unsupervised weighted oversampling (A-SUWO) for imbalanced datasets[J].Expert Systems with Applications,2016,46:405-416.

[25]Mani I，Zhang I.kNN approach to unbalanced data distributions:a case study involving information extraction[C]//in proceedings of workshop on learning from imbalanced datasets,2003.

[26]Prati RC,Batista GEAPA，Monard MC.Data mining with imbalanced class distributions:concepts and methods[J].Indian International Conference on Artifical Intelligence,2009:359-376.

[27]Cateni S,Colla V ，Vannucci M.A method for resampling imbalanced datasets in binary classification tasks for real-world problems[J].Neurocomputing,2014,135(8):32-41.

[28]Ha J，Lee J S.A New Under-Sampling Method Using Genetic Algorithm for Imbalanced Data Classification[C]//in Proceedings of the 10th International Conference on Ubiquitous Information Management and Communication,2016:95.

[29]Lin M,Tang K，Yao X.Dynamic sampling approach to training neural networks for multiclass imbalance classification[J].IEEE transactions on neural networks and learning systems,2013,24(4):647-660.

[30]Fan Q,Wang Z，Gao D.One-sided Dynamic Undersampling No-Propagation Neural Networks for imbalance problem[J].Engineering Applications of Artificial Intelligence,2016,53(C):62-73.

[31]Loyola-González O,Martínez-Trinidad J F,Carrasco-Ochoa J A,et al.Study of the impact of resampling methods for contrast pattern based classifiers in imbalanced databases[J].Neurocomputing,2016,175(PB):935-947.

[32]Seiffert C,Khoshgoftaar T M,J Van Hulse,et al.RUSBoost:A hybrid approach to alleviating class imbalance[J].Systems Man & Cybemetics Part A Systems & Humans IEEE Transactions on,2010,40(1):185-197.

[33]Zhou Z H ，Liu X Y.On multiclass cost-sensitive learning [J].Computational Intelligence,2010,26：232-257.

[34]Raskutti B,Kowalczyk A.Extreme re-balancing for SVMs:a case study[J].ACM Sigkdd Explorations Newsletter ,2004,6(1):60-69.

[35]Lee Y,Wahba G.Multicategory support vector machines,Theory and application to the classification of microarray data and satellite radiance data[J].Journal of the American Statistical Association,2003,99(465):67-81.

[36]XIE J G，QIU Z D.Fisher Linear Discriminant Model with Class Imbalance [J].Journal of Beijing Jiaotong University,2006,30(5):15-18.

[37]Karagiannopoulos MG,Anyfantis DS,Kotsiantis SB,et al.Local cost sensitive learning for handling imbalanced data sets[C]//in Control & Automation 2007.MED’07.Mediterranean Conference on,2007:1-6.

[38]Min F，Zhu W.A competition strategy to cost-sensitive decision trees[C]//in International Conference on Rough Sets and Knowledge Technology,2012,7414:359-368.

[39]Rodda S，Mogalla S.A normalized measure for estimating classification rules for multi-class imbalanced datasets[J].International Journal of Engineering Science and Technology,2011,3(4):3216-3220.

[40]O Loyola-González,MA Medina-Pérez JF Martínez-Trinidad,et al.PBC4cip:A new contrast pattern-based classifier for class imbalance problems[J].Knowledge Based Systems,2017,115 :100-109.

[41]Wozniak M.Hybrid Classifiers:Methods of Data,Knowledge,and Classifier Combination[M].Springer Publishing Company,2013.

[43]Cao Q,Wang SZ.Applying over-sampling technique based on data density and cost-sensitive SVM to imbalanced learning[C]//International Joint Conference on Neural Networks,2011,2:543-548.

[44]Jerzy Blaszczynski,Jerzy Stefanowski.Neighbourhood sampling in bagging for imbalanced data[J].Neurocomputing,2014,150:529-542.

[45]Yoav Freund,Robert E Schapire.Experiments with a new boosting algorithm[C]//international conference on machine learning,1996,13:148-156.

[46]Robert E Schapire,Yoram Singer.Improved boosting algorithms using confidence-rated predictions[J].Machine learning,1999.37(3):297-336.

[47]Wei Fan,Salvatore J Stolfo,Junxin Zhang,et al.AdaCost:misclassification cost-sensitive boosting[C]//international conference on machine learning,1999:97-105.

[48]Mahesh V Joshi,Vineet Kumar,Ramesh C Agarwal.Evaluating boosting algorithms to classify rare classes:Comparison and improvements[C]//international conference on data mining,2001:257-264.

[49]Bartosz Krawczyk,Michal Woniak,Gerald Schaefer.Cost-sensitive decision tree ensembles for effective imbalanced classification[J].Applied Soft Computing,2014,14(1):554-562.

[50]Nitesh V Chawla,Nathalie Japkowicz,Aleksander Kotcz.Editorial:special issue on learning from imbalanced data sets[J].Sigkdd Explorations,2004,6(1):1-6.

[51]Wei Liu,Sanjay Chawla,David A Cieslak, et al.Chawla.A Robust Decision Tree Algorithm for Imbalanced Data Sets[C]//Siam International Conference on Data Mining,2010,21(3):766-777.

[52]Wei Liu,Sanjay Chawla.Class confidence weighted kNN Algorithms for imbalanced data sets[C]//PAKDD(2),2011：345-356.

[53]Yuxuan Li,Xiuzhen Zhang.Improving k nearest neighbor with exemplar generalization for imbalanced class if ication[C]//PAKDD,2011:321-332.

[54]Jinyan Li,Simon Fong,Sabah Mohammed,et al.Improving the classification performance of biological imbalanced datasets by swarm optimization algorithms[J].The Journal of Supercomputing,2016,72(10):3708-3728.

[55]B Sch?lkopf,J Platt,J Shawetaylor,et al.Estimating the support of a high-dimensional distribution[J].Neural Computation.2001,13(7):1443-1471.

[56]Xiuzhen Zhang,Guozhu Dong,Kotagiri Ramamohanarao.Information-based classification by aggregating emerging patterns[Z].Intelligent Data Engineering and Automated Learning,2000,1983:48-53.

[57]X Zhang, G Dong. Overview and analysis of contrast pattern based classification[J].Contrast Data Mining: Concepts, Algorithms, and Applications, Chapman & Hall/CRC, United States of America,2012: 151-170.

[58]Nitesh V Chawla,Aleksandar Lazarevic,Lawrence O Hall,et al.SMOTEBoost:Improving prediction of the minority class in boosting[J].in knowledge discovery in Database:PKDD,2003,2838:107-119.

[59]C Seiffert,Taghi M Khoshgoftaar,J Van Hulse.Improving software-quality predictions with data sampling and boosting[J].Systems man and cybernetics,2009,39 (6):1283-1294.

[60]Xuying Liu,Jianxin Wu,Zhihua Zhou.Exploratory undersampling for class-imbalance learning[J].systems man and cybernetics,2009,39(2):539-550.

[61]P Domingos. Metacost: a general method for making classifiers cost-sensitive[C]//in Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2006:155-164.

[62]Zhongbin Sun,Qinbao Song,Xiaoyan Zhu,et al.A novel ensemble method for classifying imbalanced data[J].Pattern Recognition,2015,48(5):1623-1637.

A survey of imbalanced classification problems

CHEN Xiangtao,GAO Yajing

(School of Information Science and Engineering, Hunan University, Changsha 410082, China)

The imbalanced classification is derived from a data skew issue in the binary classification.When handing imbalanced data using a traditional classifier,its classification result is often unsatisfactory.Therefore,many classifiers for dealing with skewed data set have been put forward,including data-level techniques,algorithm-level techniques,hybrid methods and also ensemble classifiers.The essence of imbalanced classification problem,the related works,the processing strategies,the nature of imbalanced data and the corresponding evaluation indicators are presented in this paper.Aiming at the exiting studies,we also introduce existing problems and future challenges in this field.

machine learning; imbalanced classification; data-level methods;algorithm-level methods;ensemble learning

1672-7010(2017)02-0001-11

2017-01-18

陳湘濤(1973-)，湖南新寧人，副教授，博士，湖南大學(xué)碩士生導(dǎo)師，從事模式識(shí)別、機(jī)器學(xué)習(xí)方面的研究，E-mail：lbcxt@hnu.edu.cn

TP391

A