不平衡多分類算法綜述

李蒙蒙，劉藝*，李庚松，鄭奇斌，秦偉，任小廣

不平衡多分類算法綜述

李蒙蒙1，劉藝1*，李庚松1，鄭奇斌2，秦偉1，任小廣1

（1.軍事科學院 國防科技創新研究院，北京 100071； 2.軍事科學院，北京 100091）（?通信作者電子郵箱albertliu20th@163.com）

不平衡數據分類是機器學習領域的重要研究內容，但現有的不平衡分類算法通常針對不平衡二分類問題，關于不平衡多分類的研究相對較少。然而實際應用中的數據集通常具有多類別且數據分布具有不平衡性，而類別的多樣性進一步加劇了不平衡數據的分類難度，因此不平衡多分類問題已經成為亟待解決的研究課題。針對近年來提出的不平衡多分類算法展開綜述，根據是否采用分解策略把不平衡多分類算法分為分解方法和即席方法，并進一步將分解方法按照分解策略的不同劃分為“一對一（OVO）”架構和“一對多（OVA）”架構，將即席方法按照處理技術的不同分為數據級方法、算法級方法、代價敏感方法、集成方法和基于深度網絡的方法。系統闡述各類方法的優缺點及其代表性算法，總結概括不平衡多分類方法的評價指標，并通過實驗深入分析代表性方法的性能，討論了不平衡多分類的未來發展方向。

不平衡分類；多類別分類；不平衡多分類；分類算法；機器學習

0 引言

近年來，大數據的發展使數據規模顯著增長，不平衡性成為當前數據的明顯特點，不平衡多分類數據的應用已經成為亟待解決的重點課題。例如，醫藥系統檢測［1］、情感分類［2-3］、郵件分類［4］、風力發電斜坡事件預測［5］、網絡入侵檢測［6］、信用卡欺詐檢測［7］等實際工程應用都與不平衡多分類問題密切相關。數據不平衡也稱為“數據傾斜”，主要指不同類別的樣本分布具有顯著差異。以不平衡數據集為訓練樣本，構建學習模型，并用來預測新樣本類別的問題稱為不平衡數據分類問題［8］。在該類問題中通常利用不平衡率描述數據集的不平衡性。不平衡率指數據集中多數類樣本數量與少數類樣本數量的比值，當不平衡率大于1時，認為該數據集具有不平衡性。傳統的分類算法通常假設類別間樣本數量均衡，且樣本的誤分代價一致。然而，這些前提條件在現實應用中很難滿足，數據的不平衡可能導致學習算法性能下降，使傳統方法在處理不平衡數據分類時具有一定的局限性。為了解決不平衡數據分類問題，近些年出現了一系列優異的不平衡數據分類方法。以“不平衡多分類”和“imbalanced multi?class data classification”為關鍵詞分別在中國知網（CNKI）數據庫和Elsevier、IEEE、Springer數據庫中搜索，得到的相關文獻數目如圖1所示，可以發現，近些年國內外關于不平衡多分類的文獻正逐年增加，在短短十五年的時間里，相關文獻數目增長了數十倍，這表明關于不平衡多分類的研究正逐漸得到重視，相關研究成果也正逐漸豐富。為方便相關學者了解該領域的進展，對近些年提出的研究成果展開綜述變得十分必要。近些年，一些相關的綜述也相繼發表：Sahare等［9］從數據級和算法級兩個角度進行分類，并對近些年經典的算法進行總結闡述；Tanha等［10］對基于Boosting的不平衡多分類集成方法進行了詳細綜述，并利用典型算法進行了大量實驗。與現有綜述闡述的角度不同，本文主要以多分類為切入點，從“分解方法”和“即席方法”兩個角度展開綜述，在多分類的基礎上進一步考慮數據的不平衡性。

與二分類數據集中僅包含正類和負類不同，多分類數據集中通常包含更多類別的樣本，這使得各類別間關系更加多樣，而隨著類別數目的增加，整個問題的難度也隨之增加，因此直接將二分類算法應用到多分類問題中通常難以有效解決問題。尤其面對不平衡數據，樣本規模不一致使得各類別間的分布關系更加復雜，導致分類模型對少數類的識別更加困難。

不平衡多分類問題的特性主要體現在類別間樣本數目不均衡和多類別兩個層面。類別間樣本數目不均衡導致訓練出的分類模型偏向多數類，而多類別問題不僅要考慮分類器本身性能，還要深入探究分類器的組合問題［11］。根據解決問題的角度不同可以把現有不平衡多分類算法分為兩類：基于分解的方法和即席方法。基于分解的方法將不平衡多分類問題分解為多個不平衡二分類問題進行求解；即席方法是將不平衡多分類問題作為一個整體進行求解［12］。更進一步地，按照采用架構的不同，分解方法可以分為基于“一對一（One Vs. One， OVO）”的方法和基于“一對多（One Vs. All， OVA）”的方法；根據采用技術的不同，即席方法可以分為數據級方法、算法級方法、代價敏感方法、集成方法和基于深度網絡的方法［13-14］，如圖2所示。

圖1　不平衡多分類文獻數量的趨勢

圖2　不平衡多分類算法分類

根據圖2中的分類方法，本文詳細總結了各大數據庫中近三年提出的比較有代表性的不平衡多分類算法，為從事不平衡多分類研究的學者了解該領域的近幾年的進展提供參考。首先將不平衡多分類算法分為分解方法和即席方法，詳細介紹兩種方法的研究進展和特點，并進行比較；其次，本文還總結概括了不平衡多分類領域的評估指標，主要包括經典的評估指標和近些年提出的改進的評估指標；接著通過實驗對幾種典型的不平衡多分類算法展開了對比并進行深入分析；最后總結并闡述了不平衡多分類領域存在的幾個難點問題，為該領域未來的研究提供方向。

1 分解方法

由于目前對二分類問題的研究較為深入，因此很多學者采用“分解法”的思想把多分類問題轉換成多個二分類問題，并通過利用或修改現有的二分類算法求解轉換后的二分類問題。典型的分解架構主要有“一對一（OVO）”和“一對多（OVA）”。

1.1　“一對一”架構

Lango［2］認為對于不平衡多分類問題而言，OVO要優于OVA，因為通過OVA方法構造出來的二分類問題可能會比原始問題更加不平衡，從而增加了分類難度。?ak等［15］則通過大量實驗對不平衡多分類問題中幾種分解策略的性能進行了分析，并得出結論：在相同的條件下，以G?mean為評價指標，OVO比OVA方法性能更好。Zhang等［16］結合數據采樣法和OVO分解方法共同解決不平衡多分類問題，提出基于距離的相對權重自適應采樣方法來平衡數據，通過該方法提高OVO中每個二分類器的性能。Liang等［17］利用隨機欠采樣（Randomly Under?Sampling， RUS）和SMOTE（Synthetic Minority Oversampling TEchnique）方法［18］平衡數據集，然后采用彈性網絡來選擇特征，最后用支持向量機（Support Vector Machine， SVM）為二分類器進行分類，并將提出的模型成功運用于心律失常疾病檢測。Zhang等［13］提出結合集成思想的OVO方法來提升每個類別對的分類效果，最后通過實驗表明OVO與SMOTE+AdaBoost（Adaptive Boosting）或EasyEnsemble結合得到的算法比與UnderBagging、SMOTEBagging、RUSBoost（Randomly Under?Sampling Boosting）、SMOTEBoost等集成方法結合得到的算法在平均精度上表現更好［19-23］。

OVO架構雖然在不平衡多分類問題中表現出比較好的性能，但是也存在一定的局限性。例如，OVO架構在訓練每個二分類器時僅利用兩類數據，這將造成一定的信息丟失［12，16］；此外，該架構需要訓練多個二分類器，因此當類別數目較大時，算法的時間開銷也較大［12，24］。

1.2　“一對多”架構

Sen等［25］基于OVA模式提出一種新的多分類模型，稱為基于Boosting集成和過采樣技術的二值化方法（Binarization with Boosting and Oversampling， BBO）。該模型利用SMOTE過采樣技術解決OVA帶來的不平衡問題，并使用5種不同的二分類器在帶標簽的數據集和部分數據帶標簽的數據集上進行測試比較，此外該模型還利用Boosting集成技術進一步提升了分類器的性能。Jiang等［26］結合特征選擇和OVA架構對產品評論進行分類，設計了3個獨立的子分類器分別對應不同類別，并利用二叉樹將這3個子分類器組合在一起進行多分類。

圖3　OVO和OVA架構流程示意圖

2 即席方法

即席方法是將多分類問題看作一個整體，直接利用多類別之間的關系進行分類的一種方法。按照處理不平衡問題的角度不同可以分為數據級方法、算法級方法、代價敏感方法、集成方法和基于深度網絡的方法，如圖4所示。

數據級方法從數據分布的角度進行分析，通過重采樣技術平衡數據集，避免數據不平衡帶來的影響；算法級方法則通過提出新的算法或者對已有的算法進行改進來提升算法在不平衡多分類問題中的性能，該類方法不會增加或刪除數據樣本，因此不會影響數據的分布；代價敏感方法從實際應用的角度出發，給少數類樣本分配較大的誤分代價，并以最小化整體誤分代價為優化目標；單獨使用集成方法難以有效解決不平衡問題，因此通常將集成方法與其他方法相結合，共同解決不平衡問題；基于深度網絡的方法是近些年比較受關注的方法，該類方法主要是構建新的網絡架構來對不平衡多類別數據進行分類，通過不斷調整模型參數來優化分類結果，提升分類性能。

圖4　即席方法的分類

2.1　數據級方法

數據級方法旨在從數據層面出發利用重采樣技術降低數據集的不平衡率，通過構建相對平衡的數據集來降低數據不平衡給分類模型帶來的影響，從而可以利用傳統分類模型解決不平衡多類別數據分類問題。數據級方法先對數據集進行重采樣，然后再利用平衡后的數據集訓練分類器，重采樣過程與分類器訓練過程無關，因此可以根據數據集特性選擇合適的重采樣技術和分類器。按照采樣方式的不同，數據重采樣技術可以分為：過采樣和欠采樣。

2.1.1過采樣方法

過采樣方法通常是對少數類樣本進行處理，通過重復采樣或者合成新的少數類樣本，增加少數類樣本數量，提高分類器對少數類的識別度，提升算法分類性能。常用的過采樣方法是隨機過采樣，即隨機重復復制少數類樣本，該方法簡單易操作，但是隨機重復采樣會帶來嚴重的過擬合問題。針對此問題，研究學者相繼提出了一系列新的過采樣方法，主要包括基于線性插值的過采樣方法、基于深度網絡的過采樣方法以及一些其他過采樣方法。基于線性插值的過采樣方法通過考慮少數類樣本及其近鄰樣本之間的位置關系，采用插值的方式合成新樣本，并將新生成的樣本與原始樣本結合構成新的數據集；基于深度網絡的過采樣方法主要利用對抗神經網絡進行樣本生成與分類，該類算法通過生成器生成新樣本，再利用判別器進行判別和分類；基于聚類的過采樣方法考慮了數據樣本的位置分布，首先將樣本分組為多個簇，再從每個簇中過采樣樣本；基于距離的過采樣方法通過計算各樣本之間的距離選擇合適的少數類樣本，并結合其他策略生成新樣本。

1）基于線性插值的過采樣方法。SMOTE方法［18］是最早提出利用隨機線性插值在少數類樣本和其近鄰同類樣本之間合成新樣本的方法，它在一定程度上緩解了隨機過采樣帶來的過擬合問題。受到SMOTE的啟發，Han等［29］和He等［30］分別提出了Borderline?SMOTE和ADASYN（ADAptive SYNthetic sampling approach）過采樣方法。與SMOTE方法平等對待所有少數類樣本的策略不同，Borderline?SMOTE首先利用近鄰機制選擇出少數類邊界樣本，然后再利用隨機線性插值生成新樣本；ADASYN則根據少數類樣本的困難程度為其分配權重，然后按照不同的權重合成對應數量的新樣本。SMOTE、Borderline?SMOTE和ADASYN使用較為簡單且效果顯著，在不平衡數據分類中得到了廣泛的應用。

Zhang等［16］把Galar等［31］提出的基于距離的相對能力加權OVO方法（Distance?based Relative Competence Weighting for OVO strategy， DRCW?OVO）應用到了不平衡多分類問題中。他們認為DRCW?OVO是一種很好的多分類方法，但是并不適用于不平衡多分類問題，因為DRCW?OVO方法在測試新樣本時依據的是新樣本到不同類別的近鄰平均距離，在類別不平衡的情況下，少數類樣本通常比多數類樣本更加稀疏，導致預測結果更偏向多數類。針對此問題，他們又提出了一種基于距離的相對能力加權與自適應樣本合成（Distance?based Relative Competence Weighting with Adaptive Synthetic Example Generation， DRCW?ASEG）方法。DRCW? ASEG方法首先為每個少數類線性插值合成新樣本以消除樣本不平衡帶來的偏差，再計算測試樣本到不同類別的近鄰平均距離，最后依據計算出的平均距離給不同類別設置權重值，提高把測試樣本分類為少數類的可能性。Zhang等［32］首先利用歐氏距離選擇邊界多數類樣本和邊界少數類樣本，然后計算邊界少數類樣本的權重值，再由不平衡率決定少數類的合成率，采用聚類方法對少數類樣本分組，并在每個簇中以隨機線性插值的方式合成新樣本。Patil等［33］在SMOTE的基礎上提出了三種過采樣技術并用于解決大數據時代龐大的數據集分類問題，分別是：MEMMOT（MEre Mean Minority Over_sampling Technique）、MMMmOT（Minority Majority Mix mean Over_sampling Technique）和CMEOT（Clustering Minority Examples Over_sampling Technique）。這三種過采樣技術都是基于樣本安全等級［34］提出的，其中MEMMOT僅對少數類樣本進行合成，首先根據其近鄰中少數類樣本的數目確定所有少數類樣本的安全等級，然后利用該安全等級合成新樣本，該方法避免了SMOTE方法隨機采樣導致大量重復樣本的問題；MMMmOT則同時對多數類樣本和少數類樣本進行處理，避免邊界樣本合成錯誤類別的新樣本；CMEOT則利用聚類的思想對所有少數類樣本進行分組，并在各簇內部合成新樣本。Mathew等［35］提出了一種基于加權核的SMOTE（Weighted Kernel?based SMOTE， WK?SMOTE）。WK?SMOTE方法通過在SVM分類器的特征空間中對少數類樣本進行過采樣來克服SMOTE對于非線性問題的局限性。

2）基于深度網絡的過采樣方法。在故障診斷問題中，正常的樣本數要多于故障樣本數，Zareapoor等［36］提出了能夠同時分類和故障檢測的少數類樣本過采樣生成對抗網絡（Minority oversampling Generative Adversarial Network， MoGAN）。MoGAN由兩個相互依賴的網絡組成，其中生成網絡根據多數類樣本的分布合成少數類樣本，而判別網絡則與其他判別方法［37-38］同時具有判別器和分類器不同，MoGAN提出的判別網絡可以同時充當分類器和故障檢測器。為了解決多類不平衡數據線上分類過程中模型自適應更新的問題，Yu等［39］利用兩階段博弈策略設計了一個動態的多分類方法，在數據生成階段，利用兩個結合博弈策略的動態極限學習機生成少數類樣本以平衡數據分布，在模型更新階段設置了新的目標函數，該目標函數同時考慮了模型的預測性能和成本開銷。Lee等［40］提出了一種基于生成對抗網絡的入侵檢測系統。該系統首先將數據集分成訓練數據集和測試數據集，然后利用對抗網絡對訓練集中的少數類樣本進行過采樣，再結合所有多數類樣本構成新的訓練數據集，最后利用機器學習的方法構建分類模型。Shamsolmoali等［41］針對圖像數據集不平衡給深度學習技術帶來了嚴峻的挑戰等問題，提出了一種結合生成對抗網絡和膠囊網絡的方法來平衡圖像數據集。該模型中生成器根據多元概率分布生成新的樣本，結合了多數類樣本的分布結構，判別器則與Zareapoor等［36］提出的鑒別器類似，在對樣本進行鑒別的同時進行樣本分類。此外為了提高模型的收斂速度，Shamsolmoali等［41］使用了特征匹配損失函數對生成器進行訓練。此外，Pouyanfar等［42］針對視頻不平衡分類問題提出了一種深度學習框架，該框架首先利用時間和空間綜合過采樣技術在兩個維度上分別處理數據不平衡問題，然后利用預訓練的卷積神經網絡（Convolutional Neural Network， CNN）提取空間特征，利用殘差雙向長短期記憶網絡捕獲視頻數據集中的時間信息，最后利用全連接網絡生成預測結果。Liu等［43］提出了一種基于對抗神經網絡和多傳感器數據融合技術的機械故障診斷框架。根據數據融合的位置不同，Liu等［43］提出兩種不同的模式：融合前對抗神經網絡模式和融合后對抗神經網絡模式；最后利用兩個不平衡機械數據集驗證該框架，實驗結果表明，兩種模式在機械故障診斷中均具有良好的性能。

3）其他過采樣方法。Yang等［44］在MDO（Mahalanobis Distance? based Over?sampling）［45］方法的基礎上進行改進，提出基于馬氏距離的自適應過采樣方法（Adaptive MDO， AMDO），并將其推廣到了混合類型不平衡數據集分類問題中。AMDO方法利用馬氏距離選擇合適的少數類樣本，并將其映射到主成分空間，再利用廣義奇異值分解策略生成新的少數類樣本。Li等［46］結合OVO分解方法和譜聚類技術提出了一種新的不平衡多分類數據預處理方法。該方法使用OVO架構給所有類別兩兩配對，使用譜聚類技術把各類別對中的少數類樣本劃分為多個子空間，再根據數據的特征對其進行過采樣。基于譜聚類技術的過采樣方法考慮了數據的分布，有效避免了對異常值的過度采樣。針對多分類問題中類別不平衡和類別重疊等問題，Chen等［47］提出了基于聚類的自適應分解和基于編輯的多樣化過采樣（Clustering?based Adaptive Decomposition and Editing?based Diversified Oversamping procedure， CluAD?EdiDO）方法。CluAD?EdiDO由兩個關鍵部分組成：基于聚類的自適應分解和基于編輯的多樣化過采樣技術。前者對數據集中的相似數據樣本進行分組，通過聚類的方式生成多個簇；后者則應用于不同的簇中，通過在近鄰過采樣方法（?Neighbor Over?Sampling， KNOS）［48］的基礎上提出的動態近鄰過采樣（Dynamic?Neighbor Over?Sampling， DKNOS）方法對少數類樣本進行過采樣，解決類別不平衡和類重疊問題。Koziarski等［49］針對不平衡多分類問題中類重疊和離群點等挑戰提出了多類別組合清洗和重新采樣（Multi?Class Combined Cleaning and Resampling， MC?CCR）方法。MC?CCR方法利用基于能量的方法對適合于過采樣的區域進行建模，與SMOTE相比，該區域受離群值的影響較小。此外，該方法與提出的清理操作相結合，其目的是減少類重疊對學習算法性能的影響。最后，通過合并處理多分類問題的專用策略［12］，與傳統的多類別分解策略相比，MC?CCR受類間信息丟失的影響較小。

2.1.2欠采樣方法

欠采樣通常是對多數類樣本進行處理，通過在多數類樣本中選擇與少數類樣本數目大概一致的樣本，再與所有少數類樣本結合，組成平衡數據集。隨機欠采樣是最簡單的一種欠采樣方法，其通過隨機選擇部分多數類樣本實現欠采樣目的，但是其隨機性也可能導致大量有用信息丟失。針對此問題，研究學者提出了一些新的欠采樣方法，主要包括基于信息最大化理論的欠采樣方法和基于演化算法的欠采樣方法。基于信息最大化理論的欠采樣方法與隨機選擇多數類樣本不同，它通過一定的方法選擇出有代表性且有助于分類的多數類樣本，將選擇出的多數類樣本與所有少數類樣本進行結合構成新的數據集。基于演化算法的欠采樣方法將欠采樣過程看成是所有樣本的組合優化問題，通過不斷迭代選擇出較優的樣本組合以形成新的數據集。

2.2　算法級方法

算法級方法旨在通過修改分類模型的學習過程來提升分類器對少數類的識別度，提升算法性能。該類方法不會增加或刪除原始樣本，因此不會影響數據分布的變化，更適合數據分布較復雜的不平衡分類問題。常見的算法級方法主要有特征法和單類學習法。

2.2.1特征法

特征法是指通過特征選擇方法從原始特征空間中選取具有區分能力的特征子集，以提高模型對少數類識別度的一類方法。數據是由特征組成的，數據分布不均衡將直接導致特征分布不均衡，因此選擇具有強區分性的特征至關重要。

按照特征選擇過程與分類器是否相關可以把特征選擇方法分為過濾式（Filter）、包裹式（Wrapper）和嵌入式（Embedded）三類：過濾式方法依據一定的評價準則進行特征選擇，該過程與分類器無關，即先對數據集進行特征選擇，再訓練分類器；包裹式方法直接將分類器的性能作為特征選擇的評價準則，即為給定的分類器選擇最合適的特征子集；嵌入式方法則將特征選擇過程與分類器訓練過程融為一體，即在訓練分類器的過程中自動地進行特征選擇，例如基于決策樹和隨機森林的分類方法。特征選擇方法不僅可以提高模型的分類性能，還可以降低算法開銷，因此得到了眾多學者的青睞。

Liu等［59］提出了一種基于極限學習機的混合方法來解決癌癥微陣列多類不平衡數據分類問題，該方法同時在特征層面和算法層面進行分析，首先采用過濾式方法選擇特征，再利用極限學習機進行多分類，在分類過程中通過計算特征的重要性為每個輸入節點生成權重，最后通過構建集成分類器來提升算法的泛化性能。Sar?kaya等［60］認為相對于某個特定的分類器，包裹式方法比過濾式方法選擇的特征子集更加高效，因此提出了利用包裹式方法進行特征選擇，利用隨機森林進行多分類的方法。Li等［61］提出了一種典型的嵌入式方法，稱為結合LASSO（Least Absolute Shrinkage and Selection Operator）懲罰的自適應多項式回歸方法，該方法被應用在評估肺癌數據基因的重要性中，其中原始特征中僅對應著稀疏解非零分量的特征才是最終選擇的特征。

2.2.2單類學習法

使用單類學習法會丟棄其他類別信息，因此Bellinger等［63］和Hempstalk等［64］建議應盡量避免使用單類學習法。但是Krawczyk等［65］則指出單類學習法可以捕獲目標類別中足以區分其他未知類別的獨特屬性，因此適用于分布較復雜的數據，尤其在類不平衡、類噪聲、類重疊等情況下可以表現出比其他多分類方法更加優異的性能。Pérez?Sánchez等［66］也指出單類學習法不考慮類之間的不均衡性，因此可以訓練出無偏的模型，對于解決類不平衡問題具有較好的魯棒性。Krawczyk等［67］則詳細比較了單類學習法與基于分解策略的OVO和OVA多分類方法之間的不同，并詳細闡述了單類學習法的特點。Gao等［68］將單類學習法應用到醫療圖像數據分類問題中，提出使用深度學習模型來學習目標類別圖像特征，并使用圖像復雜度進行擾動。Krawczyk等［67］則針對單類學習法中分類器覆蓋重疊和由遠程訓練樣本引起的分類器涵蓋大量空白區域等問題，提出了動態選擇分類器的方法，該過程根據每個樣本的近鄰樣本決定分類器是否有效，并通過設置閾值動態刪除無效分類器，最終通過集成所有選擇的分類器提高模型魯棒性。

2.3　代價敏感方法

經典的分類方法通常以最小化誤分率為目標，并假設各類別誤分代價相等，但在現實生活中，不同類別的誤分代價通常是不一樣的，因此很多學者認為訓練分類算法時應符合實際需求，重點關注誤分代價較高的樣本，以最小化整體誤分代價為目標，針對此觀點，提出了基于代價敏感理論的分類方法［8］。在類別不平衡問題中，人們往往更關注少數類樣本的分類結果，因此在訓練分類模型時可通過提高少數類樣本的誤分代價來提升模型對少數類樣本的重視度，進而提升模型整體分類性能。

萬建武等［69］根據解決問題的階段不同將代價敏感方法分為數據前處理方法、結果后處理方法以及直接的代價敏感學習方法，并對代價敏感理論、應用和經典模型進行了詳細闡述。與之相對應的是，Zhang等［70］把代價敏感方法分為了調整數據分布、閾值移動和代價敏感決策三類。調整數據分布方法類似數據前處理方法，即以代價矩陣為依據，對誤分代價較高的樣本進行過采樣，對誤分代價較低的樣本進行欠采樣，使類別之間代價敏感［71］。萬建武等［69］得出，在實驗條件下，使用代價敏感欠采樣方法比使用代價敏感過采樣方法的分類結果更準確。閾值移動則通過調整決策閾值讓分類器偏向誤分代價較高的類別，比較典型的方法是元代價［72］。元代價方法的基本思想是利用貝葉斯風險理論最小化準則對訓練樣本重新標記，然后再利用重新標記的樣本訓練最終的分類模型。代價敏感決策方法是近年來研究的重點，它通過修改模型的訓練過程來構建代價敏感分類器，即把不同類別的代價信息嵌入到模型訓練的目標函數中，通過最小化期望損失來獲得最優分類模型［73-75］。

雖然代價敏感方法的理論基礎比較完備，但將其廣泛應用在一些實際問題中仍存在一些困難。例如，在多分類問題中難以權衡各類別之間的代價權重，生成合理的代價矩陣比較困難；此外，代價矩陣的生成通常由該領域的專家完成，開銷高昂且很多時候難以實現。

2.4　集成方法

在機器學習領域，集成方法由于表現出了優異的性能而得到了眾多研究學者的關注。與傳統方法僅訓練單個學習器不同，集成方法通過訓練多個學習器來解決問題。已有理論證明，當基學習器性能優于隨機學習器時，集成學習器的性能將得到顯著提升。集成方法通常以提高整體準確度為目標，難以適用于類別不平衡問題［50］，只有與其他平衡策略相結合才能更好地解決不平衡分類問題。

2.4.1基于Bagging的集成方法

Bagging方法的原理是首先自助采樣得到多個數據集，再利用這些數據集獨立地訓練多個基分類器，最后利用一定的結合策略將訓練出的基分類器組合成一個集成分類器。比較經典的方法是隨機森林，它以決策樹為基分類器，通過集成多個決策樹的分類結果，并利用投票機制得到最終的結果。Lango等［76］認為粗糙平衡Bagging（Roughly Balanced Bagging， RBBag）［77］是解決不平衡二分類問題算法中較為成功的一種集成方法，并從基分類器個數、基分類器多樣性等方面深入研究了促使其性能較優的本質原因，最后通過分析得出基分類器個數在10～15時RBBag算法性能均值最好；此外RBBag算法的精度高低可能與基分類器的多樣性并無直接關系。Lango等［76］進一步將RBBag擴展到了不平衡多分類問題中，還提出了兩個多類別粗糙平衡Bagging方法（Multi?class Roughly Balanced Bagging， MRBBag），即基于粗糙平衡Bagging的多類過采樣方法（oversampling Multi?class Roughly Balanced Bagging， oMRBBag）和基于粗糙平衡Bagging的多類欠采樣方法（undersampling Multi?class Roughly Balanced Bagging， uMRBBag）。

2.4.2基于Boosting的集成方法

與Bagging獨立地訓練基分類器不同，Boosting采用序列式方法依次訓練基分類器。Boosting在每次訓練完一個基分類器之后都會重新調整樣本權重，增大被分錯樣本的權重，使其在下一個基分類器中得到重視并盡可能被分對，最后采用線性加權的方式結合所有基分類器，形成最終的集成分類器。在不平衡多分類問題中，Wu等［50］提出了一種基于樞紐度感知的Boosting集成方法以解決高維不平衡數據分類問題，它通過聚類欠采樣解決類不平衡問題，并引入折扣因子減緩由樣本權重過度增長帶來的負面影響。Taherkhani等［78］將AdaBoost與CNN結合提出了AdaBoost?CNN算法，該算法利用遷移學習的思想把訓練好的CNN分類器遷移到下一個CNN分類器中，以此降低傳統AdaBoost算法在大規模數據集上訓練時產生的巨大的時間開銷。Rodríguez等［14］考慮隨機平衡策略與Boosting方法的結合在不平衡二分類中的良好表現［79］，將其擴展到了不平衡多分類問題中，提出了多分類隨機平衡算法。Fernández?Baldera等［80］結合了Boosting方法和代價敏感方法提出了一個多類別代價敏感分類算法（Boosting Adapted for Cost matrix， BAdaCost），該算法利用一系列的代價敏感基分類器構造成一個集成分類器，并通過實驗驗證了所提算法的有效性。

直觀地，訓練集成分類器通常比訓練單個分類器更加耗時，但是，Schwenker等［81］指出構建集成分類器的代價未必會顯著高于構建單個分類器的代價，這是因為訓練單個分類器時，對模型的選擇和不斷調參也會產生多個版本的模型，這與訓練集成分類器中多個基分類器的代價基本相當；此外集成分類器中的結合策略通常比較簡單，并不會帶來巨大的時間開銷，因此，當同時考慮模型時間開銷和分類效果時，集成方法是個較好的選擇。

2.5　基于深度網絡的方法

由于深度網絡的快速發展，近些年提出了大量基于深度網絡的不平衡多分類方法［82］。Rendón等［83］深入分析了基于深度神經網絡的啟發式采樣方法在不平衡多分類問題中的性能，它首先利用SMOTE和欠采樣方法平衡數據集，然后利用處理好的數據集訓練人工神經網絡，再利用Editing Nearest Neighbor［84］或者Tomek’s Links［85］消除神經網絡輸出噪聲對應的訓練數據集中的樣本，最終利用新生成的數據集再次訓練人工神經網絡。Raghuwanshi等［86］將極限學習機分類模型［87］從二分類問題擴展到多分類問題中，采用高斯核函數將輸入數據轉換到核空間，避免非優隱藏節點問題，此外，該算法為每個類別分配權重，這與傳統算法為每個樣本分配權重不同，有效降低了算法時間開銷。

2.6　分解方法和即席方法的比較

相較于分解方法，即席方法可以更加客觀且充分地利用所有樣本信息，這更加接近多分類問題的本質，因此通常具有較好的分類性能。但是由于即席方法不能直接使用現有的二分類方法，因此通常需要開發新的分類算法，這伴隨著復雜的算法設計和巨大的時間開銷［12］，給即席方法的發展帶來了一定的挑戰。

從大量關于分解方法和即席方法的研究成果中可以發現，兩類算法都具有一定的優勢和局限性，總結分解方法和即席方法的優缺點，如表1所示。由于分解方法通常把多分類問題轉化為較為簡單的二分類問題，因此其單個二分類器的訓練過程通常比即席方法訓練多分類器的過程更加簡單；但是即席方法的訓練過程可以充分利用數據集中所有樣本的分布信息，因此訓練出的多分類器更加具有針對性，可以適用于數據分布較為復雜的情況，而分解方法中，OVO架構在訓練二分類器時僅考慮兩個類別的樣本，造成信息丟失，OVA架構則將除正類以外的其他類別都作為負類，人為引入不平衡，加大了訓練難度。此外，分解方法可以利用現有的比較成熟的二分類算法，這不僅可以節約開發成本，還可以節省開發算法的時間開銷；而即席方法則只能針對多分類問題研究新型算法。

表1　分解方法和即席方法的比較

3 評價指標

傳統的分類算法通常以提高準確度為目標，但是在面對不平衡分類問題時，準確度則難以客觀反映算法性能。例如，某數據集包含90個負類樣本和10個正類樣本，在訓練學習器的過程中，如果算法把所有樣本都標記為負類仍可以獲得0.9的準確度，但是很明顯該算法是無效的。因此，為了準確地評估不平衡算法的性能，研究學者們提出了一系列具有針對性的評價指標。下面主要從兩個方面進行闡述：經典的評價指標和改進的評價指標。

3.1　經典的評價指標

在不平衡多分類問題中常用的評價指標有：準確率（Accuracy）、F、幾何平均值（Geometric?mean， G?mean）、受試者工作特征（Receiver Operating Characteristic， ROC）、ROC曲線下面積（Area Under ROC Curve， AUC）、類平衡準確度（Class Balanced Accuracy， CBA）［88］、宏觀F1（Macro?F1）［89］和微觀F1（Micro?F1）［89］等。為了詳細說明各種指標的計算方式和意義，給出混淆矩陣如表2所示。

表2　二分類混淆矩陣

3.1.1F和G?mean

3.1.2ROC和AUC

3.1.3類平衡準確度

類平衡準確度是專門針對不平衡數據提出的評價指標，主要用來衡量分類器把新樣本分類正確的能力［88］，如式（3）所示：

3.1.4Macro?F1和Micro?F1

3.2　改進的評價指標

Mortaz等［90］指出在三種特殊情況下使用經典評價指標并不能客觀反映分類器性能，因此提出了基于混淆矩陣的不平衡準確度指標（Imbalance Accuracy Metric， IAM）。該指標是基于CBA的一個改進版本，在CBA的基礎上進一步考慮了混淆矩陣的非對角線元素，使用簡單且具有較好的可解釋性。計算公式如式（6）：

Branco等［93］根據用戶偏好給每個類別設置了一個相關性，并用于分類器的評估。以召回率、精確度、F和CBA為例，分別如式（9）～（13）所示。

Gorodkin等［94］針對馬修斯相關系數（Matthews Correlation Coefficient， MCC）［95］只能應用于二分類問題這一局限性，提出了一個可以用來評估多分類的相關系數指標。計算方式如式（14）所示。

雖然針對不平衡多分類問題的指標較多，但指標的選取要結合具體應用場景和關注重點進行合理選擇，有時甚至需要同時結合多種指標的結果來綜合評估分類器的性能。

4 實驗與結果分析

4.1　實驗設置

實驗數據包括10個來自KEEL、UCI的不平衡多分類數據集，其基本信息如表3所示。其中不平衡率涵蓋范圍從1.48至175.46，類別數目從3類到6類不等。選擇了10種不同類型的不平衡多分類方法展開實驗，即OVO方法，OVA方法，OVO和OVA的組合（All?and?One， A&O）方法［96］，OVO_SMOTE方法［97］，OVA_SMOTE方法［97］，不平衡模糊粗糙有序加權平均最近鄰分類（Imbalanced Fuzzy?rough ordered weighted average nearest neighbor classification， FuzzyImb）方法［98］，一對后序（One?Against?Higher?Order， OAHO）方法［28］，用于不平衡多分類的基于集成和過采樣策略的二值化（Binarization with Boosting and Oversampling for multiclass classification， BBO）方法［25］，多元化糾錯輸出編碼（Diversified Error Correcting Output Codes， DECOC）方法［99］，多元化一對一（Diversified One?Vs.?One， DOVO）方法［100］。其中：OVO、OVA、A&O、DOVO、DECOC方法是基于不同思想的分解方法；OVO_SMOTE和OVA_SMOTE是基于數據級的方法；FuzzyImb是基于代價敏感的方法；OAHO是通過緩解數據的不平衡性來提高分類器對少數類識別度的方法，可以認為是一種算法級方法；BBO是結合數據級方法的集成方法。

實驗過程中采用的分類指標為：準確度、F、AUC、G?mean、Kappa。其中，準確度以整體分類正確率為目標，是分類問題中最常用的指標；F指標更重視較小值，可以反映算法整體分類情況，實驗過程中=1；AUC和G?mean則是不平衡分類問題中常用的指標；Kappa則體現了分類模型的可信度。實驗基于單機環境，以Windows 10為操作系統，Matlab 2018a為實驗平臺，采用5重交叉檢驗，獨立運行20次，對運行結果取均值。

4.2　實驗結果及分析

實驗結果如表4～8所示，其中：最后一行代表方法在所有數據集上的平均值；加粗表示最優值；NaN表示空值，指該方法在分類過程中出現了將某一類完全分錯的情況。

表3　實驗數據集屬性

表4　典型方法在實驗數據集上的準確度值

表5　典型方法在實驗數據集上的F1值

分析表4可知：首先，DECOC和DOVO的平均值在0.9以上，其他8種方法的平均值在0.8～0.9，從統計學的角度分析可以認為DECOC和DOVO方法較其他8種方法性能更好，且在不平衡多分類數據集上可以獲得優異的分類結果；其次，OVO和OVA方法的分類準確度比結合SMOTE方法的OVO?SMOTE和OVA?SMOTE的分類準確度更高，表明在多分類問題中簡單采用SMOTE方法不一定會提升方法分類準確度，甚至會由于引入大量新合成的樣本而影響方法分類性能；最后，從實驗結果中可以看出，在contraceptive和splice兩個數據集上，OAHO取得了最好的分類準確度，在newthyroid和flare兩個數據集上，DECOC取得了最好的分類準確度，而在其他數據集上，即balance、thyroid、wine、car、page_blocks和satimage，DOVO方法取得了最好的分類準確度。由于DOVO方法與傳統多分類方法采用固定的二分類器不同，它為每個類別對分別選擇最合適的二分類器，說明選擇良好的基分類器可以顯著提升方法的分類性能。

從表5可以看出，在contraceptive、newthyroid和splice三個數據集上，OAHO的F1值最好；在page_blocks數據集上DECOC的F1值最好；在其他數據集上DOVO的F1值最好。從平均值看，DOVO和DECOC的結果最好，均在0.9以上，而其他8種方法的均值在0.6～0.9。

從表6、7可以看出，雖然AUC和G?mean的最優值在各個方法上比較分散，但從AUC和G?mean的平均值上可以看出，DOVO方法取得了最好的均值結果，與次優值OVO方法和DECOC方法的結果分別相差0.01和0.06。結合表4～7可以看出，基于OVO改進的DOVO方法在處理不平衡數據集上較其他幾種對比方法性能更好。

從表8可以看出，DOVO和OAHO的Kappa均值比其他8種方法的Kappa均值更高，能達到0.8以上，表明DOVO和OAHO訓練出的模型更加可靠；此外，所有方法的Kappa均值都在0.4以上，表明這些方法訓練出的模型基本都可以達到可信程度。結合表4～7的分類結果，可以得出結論：DOVO方法不僅分類效果明顯，而且分類模型可信度較高，因此可以認為DOVO方法是一種優異的不平衡多分類方法。

表6　典型方法在實驗數據集上的AUC值

表7　典型方法在實驗數據集上的G?mean值

表8　典型方法在實驗數據集上的Kappa值

下面從四個方面對實驗結果進行總結：

1）分解方法DOVO的性能總體上要優于其他幾種對比方法，除了Kappa均值為0.842 5，其他四種指標的結果均值均在0.9以上，在5個指標上分別高于次優值0.02、0.015、0.01、0.06、0.025，表明在不平衡多分類問題中，提升每個二分類器的性能可顯著提高最終的分類結果。

2）通過比較對比方法的結果，可以發現在實驗條件下，OVO在5個評價指標上均要優于OVA，這可能是由于OVA模型人為引入不平衡造成的，因此，可以認為在處理不平衡多分類問題時采用OVO方法比OVA方法更合適。

3）分解方法A&O在5個指標上均要優于OVA，但不如OVO，表明基于OVO和OVA兩者結合的改進方法的性能并不一定能同時優于兩種基模型。算法級方法OAHO在5個指標上的結果均優于基模型OVA，表明OAHO采用一對后序的策略相較OVA一對所有的策略可以更好地緩解類別之間的不平衡，通過利用較平衡的數據集訓練分類模型，進而提升方法對不平衡數據集的分類性能。

4）數據級方法OVO?SMOTE和OVA?SMOTE的性能要低于分解方法OVO和OVA，表明在不平衡多分類問題中簡單采用分解策略和SMOTE過采樣方法的結合并不能顯著提高方法的分類性能，甚至還會因為引入了大量合成樣本影響了原始數據分布，造成方法分類性能的下降。

5 結語

不平衡多分類問題具有廣泛的研究意義和應用價值，是機器學習領域重要的研究內容。本文從分解方法、即席方法以及不平衡多分類評價指標三個層面進行了總結。首先介紹了基于“一對一”架構的分解方法和基于“一對多”架構的分解方法，并從數據級方法、算法級方法、代價敏感方法、集成方法和基于深度網絡的方法五個角度系統地闡述了即席方法；然后描述了不平衡多分類領域的評價指標；最后通過實驗對比了幾種典型的不平衡多分類方法。

近些年關于不平衡多分類的研究雖然得到了重視和發展，但仍存在一些具有挑戰性的問題亟待解決：目前關于如何進行過采樣和欠采樣的方法很多，但是關于樣本采樣率的研究相對較少，在利用數據重采樣技術平衡數據集的過程中，具體采樣多少，如何獲得最優采樣率至關重要，但目前采取的方法主要是依靠人為經驗或者優化算法，缺少一定的理論支持；數據不平衡分類問題的根本難點在于數據的分布，不同類別間數據分布越復雜，分類器的訓練越困難，尤其是在多分類問題中，類別數目的增加直接導致類別關系的多樣化，增加了整個問題的難度，但是目前的研究主要集中在如何在數量上平衡數據樣本，而關于數據分布的研究則相對較少；近些年由于集成方法表現優異，相關學者提出了大量基于集成方法的分類算法，但是在集成分類器中如何合理地設置基分類器的權重系數仍是一個開放性問題；此外，如何將數據級方法、算法級方法和代價敏感方法與集成方法更好地結合起來，共同解決不平衡多分類問題也是今后需要進一步研究的問題。

[1] SHILASKAR S， GHATOL A. Diagnosis system for imbalanced multi?minority medical dataset［J］. Soft Computing， 2019， 23（13）： 4789-4799.

[2] LANGO M. Tackling the problem of class imbalance in multi?class sentiment classification： an experimental study［J］. Foundations of Computing and Decision Sciences， 2019， 44（2）： 151-178.

[3] KRAWCZYK B， McINNES B T， CANO A. Sentiment classification from multi?class imbalanced twitter data using binarization［C］// Proceedings of the 2017 International Conference on Hybrid Artificial Intelligence Systems， LNCS 10334. Cham： Springer， 2017： 26-37.

[4] KULKARNI R， VINTRó M， KAPETANAKIS S， et al. Performance comparison of popular text vectorising models on multi?class email classification［C］// Proceedings of the 2018 SAI Intelligent Systems Conference， AISC 868. Cham： Springer， 2019： 567-578.

[5] DORADO?MORENO M， GUTIéRREZ P A， CORNEJO?BUENO L， et al. Ordinal multi?class architecture for predicting wind power ramp events based on reservoir computing［J］. Neural Processing Letters， 2020， 52（1）： 57-74.

[6] YUAN Y L， HUO L W， HOGREFE D. Two layers multi?class detection method for network intrusion detection system［C］// Proceedings of the 2017 IEEE Symposium on Computers and Communications. Piscataway： IEEE， 2017： 767-772.

[7] BENCHAJI I， DOUZI S， EL OUAHIDI B. Using genetic algorithm to improve classification of imbalanced datasets for credit card fraud detection［C］// Proceedings of the 2019 International Conference on Advanced Information Technology， Services and Systems， LNNS 66. Cham： Springer， 2019： 220-229.

[8] 李艷霞，柴毅，胡友強，等. 不平衡數據分類方法綜述［J］. 控制與決策， 2019， 34（4）： 673-688.（LI Y X， CHAI Y， HU Y Q， et al. Review of imbalanced data classification methods［J］. Control and Decision， 2019， 34（4）： 673-688.）

[9] SAHARE M， GUPTA H. A review of multi?class classification for imbalanced data［J］. International Journal of Advanced Computer Research， 2012， 2（5）： 160-164.

[10] TANHA J， ABDI Y， SAMADI N， et al. Boosting methods for multi?class imbalanced data classification： an experimental review［J］. Journal of Big Data， 2020， 7： No.70.

[11] KAUR H， PANNU H S， MALHI A K. A systematic review on imbalanced data challenges in machine learning［J］. ACM Computing Surveys， 2019， 52（4）： No.79.

[12] KRAWCZYK B， KOZIARSKI M， WO?NIAK M. Radial?based oversampling for multiclass imbalanced data classification［J］. IEEE Transactions on Neural Networks and Learning Systems， 2020， 31（8）： 2818-2831.

[13] ZHANG Z L， KRAWCZYK B， GARCìA S， et al. Empowering one?vs?one decomposition with ensemble learning for multi?class imbalanced data［J］. Knowledge?Based Systems， 2016， 106： 251-263.

[14] RODRíGUEZ J J， DíEZ?PASTOR J F， ARNAIZ?GONZáLEZ á， et al. Random balance ensembles for multiclass imbalance learning［J］. Knowledge?Based Systems， 2020， 193： No.105434.

[15] ?AK M， WO?NIAK M. Performance analysis of binarization strategies for multi?class imbalanced data classification［C］// Proceedings of the 2020 International Conference on Computational Science， LNCS 12140. Cham： Springer， 2020： 141-155.

[16] ZHANG Z L， LUO X G， GONZáLEZ S， et al. DRCW?ASEG： One?versus?one distance?based relative competence weighting with adaptive synthetic example generation for multi?class imbalanced datasets［J］. Neurocomputing， 2018， 285： 176-187.

[17] LIANG L J， JIN T T， HUO M Y. Feature identification from imbalanced data sets for diagnosis of cardiac arrhythmia［C］// Proceedings of the 11th International Symposium on Computational Intelligence and Design. Piscataway： IEEE， 2018： 52-55.

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

[19] LIU X Y， WU J X， ZHOU Z H. Exploratory undersampling for class?imbalance learning［J］. IEEE Transactions on Systems， Man， and Cybernetics， Part B （Cybernetics）， 2009， 39（2）： 539-550.

[20] BARANDELA R， VALDOVINOS R M， SáNCHEZ J S. New applications of ensembles of classifiers［J］. Pattern Analysis and Applications， 2003， 6（3）： 245-256.

[21] WANG S， YAO X. Diversity analysis on imbalanced data sets by using ensemble models［C］// Proceedings of the 2009 IEEE Symposium on Computational Intelligence and Data Mining. Piscataway： IEEE， 2009： 324-331.

[22] SEIFFERT C， KHOSHGOFTAAR T M， HULSE J van， et al. RUSBoost： a hybrid approach to alleviating class imbalance［J］. IEEE Transactions on Systems， Man， and Cybernetics — Part A： Systems and Humans， 2010， 40（1）： 185-197.

[23] CHAWLA N V， LAZAREVIC A， HALL L O， et al. SMOTEBoost： improving prediction of the minority class in boosting［C］// Proceedings of the 2003 European Conference on Principles of Data Mining and Knowledge Discovery， LNCS 2838. Berlin： Springer， 2003： 107-119.

[24] JEGIERSKI H， SAGANOWSKI S. An “outside the box” solution for imbalanced data classification［J］. IEEE Access， 2020， 8： 125191-125209.

[25] SEN A， ISLAM M M， MURASE K， et al. Binarization with boosting and oversampling for multiclass classification［J］. IEEE Transactions on Cybernetics， 2016， 46（5）： 1078-1091.

[26] JIANG C Q， LIU Y， DING Y， et al. Capturing helpful reviews from social media for product quality improvement： a multi?class classification approach［J］. International Journal of Production Research， 2017， 55（12）： 3528-3541.

[27] SáEZ J A， GALAR M， LUENGO J， et al. Analyzing the presence of noise in multi?class problems： alleviating its influence with the One?vs?One decomposition［J］. Knowledge and Information Systems， 2014， 38（1）： 179-206.

[28] MURPHEY Y L， WANG H X， OU G B， et al. OAHO： an effective algorithm for multi?class learning from imbalanced data［C］// Proceedings of the 2007 International Joint Conference on Neural Networks. Piscataway： IEEE， 2007： 406-411.

[29] HAN H， WANG W Y，MAO B H. Borderline?SMOTE： a new over?sampling method in imbalanced data sets learning［C］// Proceedings of the 2005 International Conference on Intelligent Computing， LNCS 3644. Berlin： Springer， 2005： 878-887.

[30] HE H B， BAI Y， GARCIA E A， et al. ADASYN： adaptive synthetic sampling approach for imbalanced learning［C］// Proceedings of the 2008 IEEE International Joint Conference on Neural Network （IEEE World Congress on Computational Intelligence）. Piscataway： IEEE， 2008： 1322-1328.

[31] GALAR M， FERNáNDEZ A， BARRENECHEA E， et al. DRCW?OVO： distance?based relative competence weighting combination for One?vs?One strategy in multi?class problems［J］. Pattern Recognition， 2015， 48（1）： 28-42.

[32] ZHANG J H， CUI X Q， LI J R， et al. Imbalanced classification of mental workload using a cost?sensitive majority weighted minority oversampling strategy［J］. Cognition， Technology and Work， 2017， 19（4）： 633-653.

[33] PATIL S S， SONAVANE S P. Enriched over_sampling techniques for improving classification of imbalanced big data［C］// Proceedings of the IEEE 3rd International Conference on Big Data Computing Service and Applications. Piscataway： IEEE， 2017： 1-10.

[34] RIVERA W， ASPAROUHOV O. Safe level OUPS for improving target concept learning in imbalanced data sets［C］// Proceedings of the 2015 IEEE SoutheastCon. Piscataway： IEEE， 2015： 1-8.

[35] MATHEW J， PANG C K， LUO M， et al. Classification of imbalanced data by oversampling in kernel space of support vector machines［J］. IEEE Transactions on Neural Networks and Learning Systems， 2018， 29（9）： 4065-4076.

[36] ZAREAPOOR M， SHAMSOLMOALI P， YANG J. Oversampling adversarial network for class?imbalanced fault diagnosis［J］. Mechanical Systems and Signal Processing， 2021， 149： No.107175.

[37] XIA M， LI T， XU L， et al. Fault diagnosis for rotating machinery using multiple sensors and convolutional neural networks［J］. IEEE?ASME Transactions on Mechatronics， 2018， 23（1）： 101-110.

[38] LIU H， ZHOU J Z， XU Y H， et al. Unsupervised fault diagnosis of rolling bearings using a deep neural network based on generative adversarial networks［J］. Neurocomputing， 2018， 315： 412-424.

[39] YU H Y， CHEN C Y， YANG H M. Two?stage game strategy for multiclass imbalanced data online prediction［J］. Neural Processing Letters， 2020， 52（3）： 2493-2512.

[40] LEE J， PARK K. GAN?based imbalanced data intrusion detection system［J］. Personal and Ubiquitous Computing， 2021， 25（1）： 121-128.

[41] SHAMSOLMOALI P， ZAREAPOOR M， SHEN L L， et al. Imbalanced data learning by minority class augmentation using capsule adversarial networks［J］. Neurocomputing， 2020， 459： 481-493.

[42] POUYANFAR S， CHEN S C， SHYU M L. Deep spatio?temporal representation learning for multi?class imbalanced data classification［C］// Proceedings of the 2018 IEEE International Conference on Information Reuse and Integration. Piscataway： IEEE， 2018： 386-393.

[43] LIU Q J， MA G J， CHENG C. Data fusion generative adversarial network for multi?class imbalanced fault diagnosis of rotating machinery［J］. IEEE Access， 2020， 8： 70111-70124.

[44] YANG X B， KUANG Q M， ZHANG W S， et al. AMDO： an over?sampling technique for multi?class imbalanced problems［J］. IEEE Transactions on Knowledge and Data Engineering， 2018， 30（9）： 1672-1685.

[45] ABDI L， HASHEMI S. To combat multi?class imbalanced problems by means of over?sampling techniques［J］. IEEE Transactions on Knowledge and Data Engineering， 2016， 28（1）： 238-251.

[46] LI Q M， SONG Y J， ZHANG J， et al. Multiclass imbalanced learning with one?versus?one decomposition and spectral clustering［J］. Expert Systems with Applications， 2020， 147： No.113152.

[47] CHEN X T， ZHANG L， WEI X H， et al. An effective method using clustering?based adaptive decomposition and editing?based diversified oversamping for multi?class imbalanced datasets［J］. Applied Intelligence， 2021， 51（4）： 1918-1933.

[48] SANTOSO B， WIJAYANTO H， NOTODIPUTRO K A， et al. K?Neighbor over?sampling with cleaning data： a new approach to improve classification performance in data sets with class imbalance［J］. Applied Mathematical Sciences， 2018， 12（10）： 449-460.

[49] KOZIARSKI M， WO?NIAK M， KRAWCZYK B. Combined cleaning and resampling algorithm for multi?class imbalanced data with label noise［J］. Knowledge?Based Systems， 2020， 204： No.106223.

[50] WU Q， LIN Y P， ZHU T F， et al. HUSBoost： a hubness?aware boosting for high?dimensional imbalanced data classification［C］// Proceedings of the 2019 International Conference on Machine Learning and Data Engineering. Piscataway： IEEE， 2019： 36-41.

[51] RAYHAN F， AHMED S， MAHBUB A， et al. CUSBoost： cluster? based under?sampling with boosting for imbalanced classification［C］// Proceedings of the 2nd International Conference on Computational Systems and Information Technology for Sustainable Solution. Piscataway： IEEE， 2017： 1-5.

[52] LI Y， WANG J， WANG S G，et al. Local dense mixed region cutting + global rebalancing： a method for imbalanced text sentiment classification［J］. International Journal of Machine Learning and Cybernetics， 2019， 10（7）： 1805-1820.

[53] LI L S， HE H B， LI J. Entropy?based sampling approaches for multi?class imbalanced problems［J］. IEEE Transactions on Knowledge and Data Engineering， 2020， 32（11）： 2159-2170.

[54] GALAR M， FERNáNDEZ A， BARRENECHEA E， et al. EUSBoost： enhancing ensembles for highly imbalanced data?sets by evolutionary undersampling［J］. Pattern Recognition， 2013， 46（12）： 3460-3471.

[55] GARCíA S， HERRERA F. Evolutionary undersampling for classification with imbalanced datasets： proposals and taxonomy［J］. Evolutionary Computation， 2009， 17（3）： 275-306.

[56] FERNANDES E R Q， DE CARVALHO A C P L F. Evolutionary inversion of class distribution in overlapping areas for multi?class imbalanced learning［J］. Information Sciences， 2019， 494： 141-154.

[57] DEB K， PRATAP A， AGARWAL S， et al. A fast and elitist multiobjective genetic algorithm： NSGA?Ⅱ［J］. IEEE Transactions on Evolutionary Computation， 2002， 6（2）： 182-197.

[58] GOLDBERG D E. Genetic Algorithms in Search， Optimization， and Machine Learning［M］. Boston： Addison?Wesley Professional， 1989： 95-99.

[59] LIU Z， TANG D Y， CAI Y M， et al. A hybrid method based on ensemble WELM for handling multi class imbalance in cancer microarray data［J］. Neurocomputing， 2017， 266： 641-650.

[60] SARIKAYA A， KILI? B G. A class?specific intrusion detection model： hierarchical multi?class IDS model［J］. SN Computer Science， 2020， 1（4）： No.202.

[61] LI J T， WANG Y Y， SONG X K， et al. Adaptive multinomial regression with overlapping groups for multi?class classification of lung cancer［J］. Computers in Biology and Medicine， 2018， 100： 1-9.

[62] DUFRENOIS F. A one?class kernel fisher criterion for outlier detection［J］. IEEE Transactions on Neural Networks and Learning Systems， 2015， 26（5）： 982-994.

[63] BELLINGER C， SHARMA S， JAPKOWICZ N. One?class versus binary classification： which and when？［C］// Proceedings of the 11th International Conference on Machine Learning and Applications. Piscataway： IEEE， 2012： 102-106.

[64] HEMPSTALK K， FRANK E. Discriminating against new classes： one?class versus multi?class classification［C］// Proceedings of the 2008 Australasian Joint Conference on Artificial Intelligence， LNCS 5360. Berlin： Springer， 2008： 325-336.

[65] KRAWCZYK B， WO?NIAK M， HERRERA F. On the usefulness of one?class classifier ensembles for decomposition of multi?class problems［J］. Pattern Recognition， 2015， 48（12）： 3969-3982.

[66] PéREZ?SáNCHEZ B， FONTENLA?ROMERO O， SáNCHEZ? MARO?O N. Selecting target concept in one?class classification for handling class imbalance problem［C］// Proceedings of the 2015 International Joint Conference on Neural Networks. Piscataway： IEEE， 2015： 1-8.

[67] KRAWCZYK B， GALAR M， WO?NIAK M， et al. Dynamic ensemble selection for multi?class classification with one?class classifiers［J］. Pattern Recognition， 2018， 83： 34-51.

[68] GAO L， ZHANG L， LIU C， et al. Handling imbalanced medical image data： a deep?learning?based one?class classification approach［J］. Artificial Intelligence in Medicine， 2020， 108： No.101935.

[69] 萬建武，楊明. 代價敏感學習方法綜述［J］. 軟件學報， 2020， 31（1）： 113-136.（WAN J W， YANG M. Survey on cost?sensitive learning method［J］. Journal of Software， 2020， 31（1）： 113-136.）

[70] ZHANG Z L， LUO X G， GARCíA S， et al. Cost?sensitive back? propagation neural networks with binarization techniques in addressing multi?class problems and non?competent classifiers［J］. Applied Soft Computing， 2017， 56： 357-367.

[71] LING C X， SHENG V S. Cost?sensitive learning and the class imbalance problem［M］// Encyclopedia of Machine Learning. Boston： Springer， 2010： 171， 231-235.

[72] DOMINGOS P. MetaCost： a general method for making classifiers cost?sensitive［C］// Proceedings of the 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 1999： 155-164.

[73] IRANMEHR A， MASNADI?SHIRAZI H， VASCONCELOS N. Cost?sensitive support vector machines［J］. Neurocomputing， 2019， 343： 50-64.

[74] GU B， SHENG V S， TAY K Y， et al. Cross validation through two?dimensional solution surface for cost?sensitive SVM［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2017， 39（6）： 1103-1121.

[75] ZHANG C， TAN K C， LI H Z， et al. A cost?sensitive deep belief network for imbalanced classification［J］. IEEE Transactions on Neural Networks and Learning Systems， 2019， 30（1）： 109-122.

[76] LANGO M， STEFANOWSKI J. Multi?class and feature selection extensions of roughly balanced bagging for imbalanced data［J］. Journal of Intelligent Information Systems， 2018， 50（1）： 97-127.

[77] HIDO S， KASHIMA H， TAKAHASHI Y. Roughly balanced bagging for imbalanced data［J］. Statistical Analysis and Data Mining， 2009， 2（5/6）： 412-426.

[78] TAHERKHANI A， COSMA G， McGINNITY T M. AdaBoost? CNN： an adaptive boosting algorithm for convolutional neural networks to classify multi?class imbalanced datasets using transfer learning［J］. Neurocomputing， 2020， 404： 351-366.

[79] DíEZ?PASTOR J F， RODRíGUEZ J J， GARCíA?OSORIO C， et al. Random Balance： ensembles of variable priors classifiers for imbalanced data［J］. Knowledge?Based Systems， 2015， 85： 96-111.

[80] FERNáNDEZ?BALDERA A， BUENAPOSADA J M， BAUMELA L. BAdaCost： multi?class Boosting with costs［J］. Pattern Recognition， 2018， 79： 467-479.

[81] SCHWENKER F. Ensemble methods： foundations and algorithms ［Book Review］［J］. IEEE Computational Intelligence Magazine， 2013， 8（1）： 77-79.

[82] JOHNSON J M， KHOSHGOFTAAR T M. Survey on deep learning with class imbalance［J］. Journal of Big Data， 2019， 6： No.27.

[83] RENDóN E， ALEJO R， CASTORENA C， et al. Data sampling methods to deal with the big data multi?class imbalance problem［J］. Applied Sciences， 2020， 10（4）： No.1276.

[84] WILSON D L. Asymptotic properties of nearest neighbor rules using edited data［J］. IEEE Transactions on Systems， Man and Cybernetics， 1972， SMC?2（3）： 408-421.

[85] TOMEK I. Two modifications of CNN［J］. IEEE Transactions on Systems， Man and Cybernetics， 1976， SMC?6（11）： 769-772.

[86] RAGHUWANSHI B S， SHUKLA S. Generalized class?specific kernelized extreme learning machine for multiclass imbalanced learning［J］. Expert Systems with Applications， 2019， 121： 244-255.

[87] RAGHUWANSHI B S， SHUKLA S. Class?specific kernelized extreme learning machine for binary class imbalance learning［J］. Applied Soft Computing， 2018， 73： 1026-1038.

[88] MOSLEY L S D. A balanced approach to the multi?class imbalance problem［D］. Ames， IA： Iowa State University， 2013： 15-25.

[89] SOKOLOVA M， LAPALME G. A systematic analysis of performance measures for classification tasks［J］. Information Processing and Management， 2009， 45（4）： 427-437.

[90] MORTAZ E. Imbalance accuracy metric for model selection in multi?class imbalance classification problems［J］. Knowledge? Based Systems， 2020， 210： No.106490.

[91] VIERA A J， GARRETT J M. Understanding interobserver agreement： the kappa statistic［J］. Family Medicine， 2005， 37（5）： 360-363.

[92] WEI J M， YUAN X J， HU Q H， et al. A novel measure for evaluating classifiers［J］. Expert Systems with Applications， 2010， 37（5）： 3799-3809.

[93] BRANCO P， TORGO L， RIBEIRO R P. Relevance?based evaluation metrics for multi?class imbalanced domains［C］// Proceedings of the 2017 Pacific?Asia Conference on Knowledge Discovery and Data Mining， LNCS 10234. Cham： Springer， 2017： 698-710.

[94] GORODKIN J. Comparing two?category assignments by a?category correlation coefficient［J］. Computational Biology and Chemistry， 2004， 28（5/6）： 367-374.

[95] MATTHEWS B W. Comparison of the predicted and observed secondary structure of T4 phage lysozyme［J］. Biochimica et Biophysica Acta （BBA） — Protein Structure， 1975， 405（2）： 442-451.

[96] GARCíA?PEDRAJAS N， ORTIZ?BOYER D. Improving multiclass pattern recognition by the combination of two strategies［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2006， 28（6）： 1001-1006.

[97] FERNáNDEZ A， LóPEZ V， GALAR M， et al. Analysing the classification of imbalanced data?sets with multiple classes： Binarization techniques and ad?hoc approaches［J］. Knowledge? Based Systems， 2013， 42： 97-110.

[98] RAMENTOL E， VLUYMANS S， VERBIEST N， et al. IFROWANN： imbalanced fuzzy?rough ordered weighted average nearest neighbor classification［J］. IEEE Transactions on Fuzzy Systems， 2015， 23（5）： 1622-1637.

[99] BI J J， ZHANG C S. An empirical comparison on state?of?the?art multi?class imbalance learning algorithms and a new diversified ensemble learning scheme［J］. Knowledge?Based Systems， 2018， 158： 81-93.

[100] KANG S， CHO S， KANG P. Constructing a multi?class classifier using one?against?one approach with different binary classifiers［J］. Neurocomputing， 2015， 149（Pt B）： 677-682.

Survey on imbalanced multi?class classification algorithms

LI Mengmeng1， LIU Yi1*， LI Gengsong1， ZHENG Qibin2， QIN Wei1， REN Xiaoguang1

（1，，100071，；2，100091，）

Imbalanced data classification is an important research content in machine learning， but most of the existing imbalanced data classification algorithms foucus on binary classification， and there are relatively few studies on imbalanced multi?class classification. However， datasets in practical applications usually have multiple classes and imbalanced data distribution， and the diversity of classes further increases the difficulty of imbalanced data classification， so the multi?class classification problem has become a research topic to be solved urgently. The imbalanced multi?class classification algorithms proposed in recent years were reviewed. According to whether the decomposition strategy was adopted， imbalanced multi?class classification algorithms were divided into decomposition methods and ad?hoc methods. Furthermore， according to the different adopted decomposition strategies， the decomposition methods were divided into two frameworks： One Vs. One （OVO） and One Vs. All （OVA）. And according to different used technologies， the ad?hoc methods were divided into data?level methods， algorithm?level methods， cost?sensitive methods， ensemble methods and deep network?based methods. The advantages and disadvantages of these methods and their representative algorithms were systematically described， the evaluation indicators of imbalanced multi?class classification methods were summarized， the performance of the representative methods were deeply analyzed through experiments， and the future development directions of imbalanced multi?class classification were discussed.

imbalanced classification; multi?class classification; imbalanced multi?class classification; classification algorithm; machine learning

This work is partially supported by National Natural Science Foundation of China （61802426）.

LI Mengmeng， born in 1992， M. S. candidate. Her research interests include data quality， evolutionary algorithms.

LIU Yi， born in 1990， Ph. D.， research assistant. His research interests include robot operating system， data quality， evolutionary algorithms.

LI Gengsong， born in 1999， M. S. candidate. His research interests include big data， algorithm selection.

ZHENG Qibin， born in 1990， Ph. D.， research assistant. His research interests include data engineering， data mining， machine learning.

QIN Wei， born in 1983， M. S.， research assistant. His research interests include intelligent information system management.

REN Xiaoguang， born in 1986， Ph. D.， associate research fellow. His research interests include robot operation system， high?performance computing， numerical computation and simulation.

TP391

A

1001-9081（2022）11-3307-15

10.11772/j.issn.1001-9081.2021122060

2021?12?06；

2021?12?30；

2022?01?18。

國家自然科學基金資助項目（61802426）。

李蒙蒙（1992—），女，河北邯鄲人，碩士研究生，主要研究方向：數據質量、演化算法；劉藝（1990—），男（回族），安徽蚌埠人，助理研究員，博士，主要研究方向：機器人操作系統、數據質量、演化算法；李庚松（1999—），男，湖南長沙人，碩士研究生，主要研究方向：大數據、算法選擇；鄭奇斌（1990—），男，甘肅蘭州人，助理研究員，博士，主要研究方向：數據工程、數據挖掘、機器學習；秦偉（1983—），男，安徽阜陽人，助理研究員，碩士，主要研究方向：智能信息系統管理；任小廣（1986—），男，湖北隨州人，副研究員，博士，主要研究方向：機器人操作系統、高性能計算、數值計算和模擬。