二類不均衡數據分類問題常用策略研究

楊小軍，劉 志，王力猛，劉 文

（國防大學 聯(lián)合勤務學院，北京 100858）

0 引言

分類是數據挖掘領域的一類重要問題，現(xiàn)有的分類方法都很成熟，如決策樹、支持向量機、樸素貝葉斯方法等，并利用這些方法成功地解決了許多實際問題。但隨著應用范圍的擴大和研究的深入，分類方法在使用過程中遇到了數據樣本分布不均衡問題。通常稱數據分布不均衡的數據集為不均衡數據集，數據分布不均衡表現(xiàn)為兩種形式：一是類間數據分布不均衡；二是在某一類樣本的內部存在著類內不均衡。在不均衡數據集中，將樣本數量少的類稱為少數類或正類，樣本數量多的類稱為多數類或負類。

對不均衡數據進行正確分類，是數據分類的一個難題。問題來源于不均衡數據集的樣本分布特點，以及傳統(tǒng)分類算法固有的局限性。傳統(tǒng)分類算法的重要前提是：數據集中各樣本比例是均衡的；以總體最大精度為目標，很容易忽略少數類；所有的分類錯誤代價都相同。因此，如果用傳統(tǒng)的分類器來直接處理不均衡數據集，會造成少數類樣本的分類精度較差，尤其是數據不均衡嚴重時更是如此。鑒于目前研究不均衡分類問題都是基于不均衡的兩類問題，則本文主要研究比較二類不均衡數據分類問題的常用策略。

1 不均衡數據分類策略

常用的不均衡數據分類策略主要有如下幾類：在數據層面，通過重采樣來解決數據分布不均衡狀況；在算法層面，通過代價敏感算法或是集成算法提升不均衡數據分類時的性能；通過數據層面與算法層面相結合的策略進行改進。

1.1 數據層面的處理方法

由于不均衡數據集是數據樣本之間比例不均衡，可通過對各類別數據的增刪，重新實現(xiàn)不同類別數據樣本之間的平衡。數據重采樣是最具代表性的數據層面處理辦法，可將其分為欠采樣、過采樣，以及二者結合的混合采樣方法。最簡單的重采樣為隨機過采樣（ROS）方法和隨機欠采樣（RUS）方法。通過簡單復制／刪除部分樣本的方式，達到平衡二類樣本比例的目的。而隨機方法的缺點是增加了過學習的概率。因此目前考慮更多的是啟發(fā)式方法。

Chawla 提出的SMOTE［1］方法，是一種經典的啟發(fā)式過采樣方法。SMOTE 方法首先為每一個少數類樣本隨機地挑選出幾個相鄰的樣本，然后在這個少數類樣本和挑出的鄰近樣本的連接線上，以隨機方式取點，生成沒有重復的少數類樣本。因此，在很大程度上解決了隨機過采樣方法產生的過擬合問題。此后，在SMOTE 方法的基礎上形成了大量的改進算法：如D-SMOTE 過抽樣算法，是采用求最近鄰樣本均值點的方法來生成少數類樣本；N-SMOTE算法［2］，則采用了周圍空間結構信息的鄰居計算公式來生成少數類樣本等等。

啟發(fā)式欠采樣方法為達到更好的分類效果，采用方法去除掉那些遠離分類邊界的、有數據重疊的、且對分類作用不大的多數類樣本。典型的欠采樣方法有Tomek links 方 法［3］和ENN 方 法 等。Tomek links 方法是先判斷兩個不同類樣本之間是否構成了Tomek links，是則進行樣本剪輯；ENN 算法的基本思想是，刪除離每個多數類樣本最近的3 個近鄰樣本中的2 個。在實際應用中，為了達到最佳效果，一般將各種欠采樣和過采樣方法混合使用。在增加少數類數據樣本同時，減少了多數類數據樣本，最終達到兩類數據樣本平衡的目的。SMOTE+Tomek links、SMOTE+ENN［4］是典型的混合采樣方法。

1.2 算法層面處理方法

在算法層面，不均衡數據學習常用的方法有：代價敏感算法、集成學習方法、單類學習方法和特征選擇方法。

1.2.1 代價敏感算法

傳統(tǒng)分類器以實現(xiàn)樣本整體誤差最小為最終目標。在訓練過程中，由于數量偏少的緣故，少數類樣本的預測準確率很低，甚至出現(xiàn)被忽略的情況。為了提升少數類的重要程度，代價敏感算法給少數類樣本造成的誤差施加更大的懲罰。算法的中心思想是：運用該方法訓練分類器的目標是最小化樣本的整體誤分代價，不再追求實現(xiàn)樣本整體誤差最小化。代價敏感算法的核心是代價矩陣的設計，其設計是否合理，最終決定了分類模型的性能。在二分類問題中，代價矩陣見表1。

其中，Cij表示第i 類樣本被誤分成j 類的代價，應賦大于0 的值。左對角線上的元素Cii表示被正確分類的代價，其取值應為0。重要的類別應賦更大的代價，如Cij＞Cji表示第i 類樣本比第j 類更重要。在類不均衡學習中，一般更為關心少數類樣本。如癌癥檢測中的指標異常、機器故障檢測中出現(xiàn)的異常等。因此可將少數類視為重要類，在代價敏感學習中賦予更大的錯分代價［5］。但誤分代價具體取值難以確定。

表1 二分類問題的代價矩陣Tab.1 The cost matrix of binary classification

1.2.2 集成學習算法

集成算法是將多個弱分類器組合構造成一個強分類器。由于單個算法能力有限，找到的多數是局部最優(yōu)解，而非全局最優(yōu)解。集成學習算法對多個局部最優(yōu)解進行綜合，可以提升分類器的性能，已被證明是一種能有效解決不均衡問題的技術。典型的集成算法有裝袋方法（Bagging）和提升方法（Boosting），其主要思想是先對訓練集進行不同方式的訓練，得到不同的基分類器；再對基分類器進行組合，最終達到提升集成分類器學習效果的目的。在Bagging 算法中，為了提高集成分類器泛化能力，以有放回的方式從原始訓練集中隨機選取出若干樣例形成訓練集，多次選取不同訓練集以增加基分類器差異度。AdaBoost 算法是Boosting 方法中的代表，通過在迭代中加大被錯誤分類樣本的權重，減少被正確分類樣本的權重，由有差異的訓練樣本集得到不同的基分類器，最終經過加權集成為最終的分類器。在迭代過程中，Bagging 算法每個樣本的權重都一樣，而Boosting 算法卻能夠根據樣本的錯誤率不斷調整樣本的權重。因此，在處理不均衡分類問題時，基于Boosting 的算法在一定程度上優(yōu)于基于Bagging 的算法［6］。

在實際處理不均衡數據分類時，通常將數據層面的方法與算法層面的方法相結合，解決不均衡分類問題。如，將采樣技術和集成算法結合。其中最典型的是Nitesh V.Chawla 提出的SMOTEBoost［7］方法。該方法通過結合 SMOTE 過采樣技術和AdaBoost 提升方法，來解決不均衡數據分類問題。SMOTEBoost 算法在訓練開始前，先使用SMOTE 方法生成少數類樣本，再使用Adaboost 方法對樣本分類，提升了少數類樣本的分類準確率，避免了過擬合。此外，將采樣和代價敏感算法相結合，也是不均衡數據學習的一類重要方法。

對常用的集成算法進一步集成就形成了混合集成算法。為防止采用降采樣技術后，造成多數類樣本信息丟失的情況，Liu 等提出EasyEnsemble 和BalanceCascade 算法［3］。EasyEnsemble 算法首先利用Bagging 技術對多數類樣本進行多次有放回隨機采樣，形成多個與少數類樣本數量相同的多數類樣本子集；接著將每個多數類樣本子集與少數類樣本組合，用AdaBoost 方法訓練分類器；最后將所有的多數類子集所形成的分類器再組合。BalanceCascade 算法與EasyEnsemble 算法的原理類似，區(qū)別之處在于每一次形成多數類樣本子集時，已正確分類的多數類樣本將被從多數類樣本集中去掉。

此外，單類學習方法是在分類時，只識別樣本中的少數類，主要應用于異常檢測領域。特征選擇從已知的特征集合中選擇出代表性特征子集，從而保留原數據的主要信息，其目的是去除冗余特征。在不均衡數據集中選出關鍵的區(qū)分特征，將會增強少數類和多數類的區(qū)分度，提升分類器中少數類和整體的正確率。

2 不均衡數據分類器評估指標

評價分類器性能的指標有查準率、召回率（查全率）、F -measure、AUC等。對于傳統(tǒng)分類器來說，數據集中多數類和少數類的分布大致保持均衡，分類準確率是最常用的性能評價指標。對不均衡數據集，則不能用準確率去評價一個分類器的好壞了，而常用G -mean和F -measure、AUC作為分類器性能的評估指標。

表2 分類結果的混淆矩陣Tab.2 Confusion matrix of classification results

表2 表達的是二類分類結果的混淆矩陣。表中TP和TN分別表示被正確預測的正類、負類樣本數，F(xiàn)P和FN則分別表示被錯誤預測為正類的負類樣本數和被錯誤預測為負類的正類樣本數。因TP+TN是分類器正確預測的樣本數，F(xiàn)P+FN則是分類錯誤的樣本數量，TP +TN +FP +FN是所有數據樣本數量。則分類準確率Acc可以由式（1）得出：

查準率Precision、召回率（查全率）Recall、真正率TPR、真負率TNR等指標，也可由這4 個變量，通過以下各式得到：

其中，查準率和召回率是一對矛盾的度量指標，一個指標高時，另一指標往往偏低。為實現(xiàn)兩者之間的平衡，將其合并為一個F -measure度量。只有當查準率和召回率都高時，F(xiàn) -measure的值才會大，其計算公式如下：

此外，采用G -mean來衡量真正率TPR和真負率TNR之間的關系。只有當正類和負類的準確率同時都高時，G -mean值才會高，G -mean值可用來衡量不均衡分類器的整體準確率，其計算公式如下：

在不均衡數據學習中，還有一種常用的性能評價標準：受控者操縱特征曲線下面積（AUC）。受控者操縱特征曲線（ROC）顯示了分類模型真正率和假正率之間的關系，是對各樣本的決策輸出值排序而形成的。ROC曲線下的面積就是AUC測度，AUC能很好地評價不均衡分類器的泛化性能。

F -measure、G -mean與AUC的取值范圍均為［0，1］，分類器性能與其值成正比，即指標值越大，分類器性能越好。

3 各種策略分析實驗

各種處理不均衡數據集的方法各有優(yōu)劣。在不同的應用場景下，對各種不同的數據類型，需要采用不同的處理方法。下面對常用的3 種類不均衡分類策略：重采樣方法、代價敏感學習、集成學習及其組合方法進行實驗分析比較。本文試驗數據來自于KEEL 數據集（http：／ ／www.keel.es／），本文從中選取了10 個樣本數據集，見表3。使用基于Java 語言的開源軟件KEEL 實現(xiàn)了不均衡數據集的分類學習。KEEL 軟件有專門的不均衡數據學習模塊，集成了大部分主流的不均衡數據處理方法。實驗采用G -mean和AUC值作為評價不均衡分類學習能力的指標，用G -mean值衡量分類器的準確率，AUC值衡量分類器的泛化性能，取值越大，性能越優(yōu)。實驗采用5 折交叉驗證法。實驗環(huán)境具體配置為：處理器為Intel i7-4720 2.60GHz；8G 內存；64 位windows 操作系統(tǒng)。

3.1 實驗方法與結果

（1）重采樣方法在不均衡數據集上的分類性能比較。實驗選用了過采樣方法SMOTE、欠采樣方法Tomek links 方法、混合采樣方法SMOTE_Tomek links 和SMOTE_ENN 方法。通過重采樣方法實現(xiàn)了數據集的再平衡之后，選用常用的決策樹算法C4.5 進行分類。各種重采樣方法與C4.5 算法的結合在不同數據集上的性能見表4。表中的TL 表示Tomek links 欠采樣方法，SMOTE_TL 表示SMOTE_Tomek links 混合采樣方法。

表3 不均衡數據集基本信息Tab.3 Basic information about imbalanced data sets

表4 重采樣方法性能比較Tab.4 Performance comparison of resample method

（2）3 種代價敏感算法在不同數據集上的性能比較。實驗結果見表5。C4.5CS 表示代價敏感決策樹算法，SVMCS 表示代價敏感支持向量機算法，NNCS 表示代價敏感神經網絡算法。

表5 代價敏感方法性能比較Tab.5 Performance comparison of cost-sensitive learning method

（3）重采樣方法SMOTE 和SMOTE_ENN 方法性能比較。選用經典的重采樣方法SMOTE 和SMOTE_ENN 方法，將其與代價敏感決策樹算法C4.5CS進行組合，觀察其是否比與普通決策樹算法C4.5 結合性能提升更大，結果見表6。

表6 重采樣與代價敏感集成方法性能比較Tab.6 Performance comparison of ensemble learning method about resample and cost-sensitive learning

（4）經典集成方法性能比較。比較3 種經典集成方法SMOTEBoost、EasyEnsemble、BalanceCascade在不同數據集上的性能，這3 種集成方法均以C4.5決策樹算法作為弱分類器，結果見表7。

表7 經典集成方法性能比較Tab.7 Performance comparison of classical ensemble learning method

3.2 實驗結果分析

（1）重采樣方法分析。根據表4 的實驗結果，過采樣方法SMOTE 在大部分數據集上的G-mean值和AUC 值都高于欠采樣方法Tomek links，只有在一個數據集“ecoli-0-1-3-7_vs_2-6”上出現(xiàn)例外，而且隨著不平衡率的增加，二者之間的差值有逐漸增大的趨勢，這說明SMOTE 方法的性能全面優(yōu)于Tomek links 方法?；旌喜蓸臃矫?，當不均衡率小于3 時，SMOTE_TL 采樣方法的G-mean 值和AUC 值都高于SMOTE_ENN 方法。不均衡率大于3 后，SMOTE_ENN 方法的G-mean 值和AUC 值普遍高于SMOTE_TL 方法，說明SMOTE_ENN 的準確率和泛化性能優(yōu)于SMOTE_TL 方法。比較SMOTE 和SMOTE_ENN 這兩種相對更好的方法，當不平衡率在30 以內時，SMOTE 方法的G-mean 值和AUC 值高于SMOTE_ENN 方法或是與其接近。當不平衡率超過30 時，SMOTE_ENN 方法的G-mean 值和AUC值才會高于SMOTE 方法。

（2）代價敏感學習方法分析。根據表5 的實驗結果，代價敏感支持向量機算法SVMCS 的G-mean值和AUC 值，大多數情況下都高于另外兩種代價敏感算法。在不均衡比例較高時，代價敏感決策樹方法C4.5CS 的性能與代價敏感支持向量機算法SVMCS 的性能相差不大，在兩個數據集中C4.5CS的準確率與泛化性能甚至超過了SVMCS 方法。當不均衡比例超過100 時，如在“abalone19”數據集中，SVMCS 的性能比另外兩種代價敏感方法要高出很多。相比較而言，代價敏感神經網絡算法的性能比另外兩種算法差。

（3）重采樣方法與代價敏感方法集成分析。根據表6 的實驗結果，當不平衡率小于10 時，二種集成方法在不同數據集上所表現(xiàn)出的性能沒有明顯的規(guī)律可循。不平衡率在10～20 時，SMOTE+C4.5CS集成方法的性能要強于SMOTE_ENN+C4.5CS集成方法。當不平衡率在20～100 時則相反，SMOTE_ENN+C4.5CS 方法的性能要強于SMOTE+C4.5CS 方法。當數據分布嚴重不均衡時，SMOTE+C4.5CS 方法的性能又超過了SMOTE_ENN+C4.5CS 方法。總體而言，重采樣方法與代價敏感方法的集成方法其性能表現(xiàn)出的規(guī)律性不強。

（4）C4.5 為基分類器的3 種經典集成方法比較分析。根據表7 的實驗結果，當不均衡率小于3 時，EasyEnsemble 方法的性能優(yōu)于其它二種方法。不平衡率在8～30 之間時，BalanceCascade 的性能要強于SMOTEBoost 方法和EasyEnsemble 方法。當不均衡率超過40 后，EasyEnsemble 較另外兩種集成方法重新取得了性能優(yōu)勢。當不均衡率超過100 時，SMOTEBoost 方法的G-mean 值明顯下降，AUC 值也不如另外兩種算法。

4 結束語

迄今為止，對于不均衡數據分類的理論成果非常少，本文所作的研究也只是在實驗數據的基礎上，總結出一些經驗性的結果，迫切需要進行更深入的理論分析和研究。另外，目前研究不均衡分類問題都是基于不均衡的二分類問題，即使是不均衡的多類問題，也是通過將原問題分解成二類問題的方法去解決，并沒有針對多類不均衡問題公認的評價指標。因此，需要進一步的深入研究，提出針對多類不均衡分類問題的評價指標和相應的學習算法。