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

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

0 引言

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

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

1 不均衡數(shù)據(jù)分類策略

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

1.1 數(shù)據(jù)層面的處理方法

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

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

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

1.2 算法層面處理方法

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

1.2.1 代價敏感算法

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

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

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

1.2.2 集成學習算法

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

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

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

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

2 不均衡數(shù)據(jù)分類器評估指標

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

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

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

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

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

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

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

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

3 各種策略分析實驗

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

3.1 實驗方法與結(jié)果

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

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

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

（2）3 種代價敏感算法在不同數(shù)據(jù)集上的性能比較。實驗結(jié)果見表5。C4.5CS 表示代價敏感決策樹算法，SVMCS 表示代價敏感支持向量機算法，NNCS 表示代價敏感神經(jīng)網(wǎng)絡(luò)算法。

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

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

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

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

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

3.2 實驗結(jié)果分析

（1）重采樣方法分析。根據(jù)表4 的實驗結(jié)果，過采樣方法SMOTE 在大部分數(shù)據(jù)集上的G-mean值和AUC 值都高于欠采樣方法Tomek links，只有在一個數(shù)據(jù)集“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 以內(nèi)時，SMOTE 方法的G-mean 值和AUC 值高于SMOTE_ENN 方法或是與其接近。當不平衡率超過30 時，SMOTE_ENN 方法的G-mean 值和AUC值才會高于SMOTE 方法。

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

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

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

4 結(jié)束語

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