一種加權的MCLP分類模型及其在不平衡數據集上的應用

朱梅紅

（首都經濟貿易大學 統計學院，北京 100070）

0 引言

在數據挖掘的分類問題中，經常出現數據集內類別不平衡現象。如信用卡客戶識別、生產過程的故障檢測等問題中，不同類別的樣本數目相差很大：信用卡客戶中“違約人”明顯少于“守約人”，生產過程中“故障”狀態通常少于“正常”狀態。對于這些不平衡數據集，決策者更希望能夠有效地識別出其中的少數類（以下簡稱小類）。

那么，如何在保證多數類（大類）分類正確率的前提下，提高小類的分類正確率？對于該問題的研究，可追溯到20世紀60-70年代[1-3]。隨著海量數據分析的需要和數據挖掘領域的出現，該研究受到數據挖掘學術界的高度重視，從2000年開始已成為該領域研究的熱點問題之一，對它的研究也變得更成體系和規模。

目前，針對不平衡數據的分類，有來自不同領域、針對不同現實問題、運用不同分類方法、從不同角度進行的研究。主要有三種思路：一是通過改進分類模型，使模型更關注小類；二是使用更合適的分類業績評價標準；三是從訓練數據入手，通過適當的數據處理技術，改變訓練數據的類分布，以提高少數類的正確率。近50年來，基于第三種思路展開的研究，一直經久不衰。主要是利用抽樣(或稱再抽樣)方法，達到訓練數據類間的平衡。其中，抽樣方法包括：(1)對小類進行隨機上抽樣，即通過隨機復制小類內的樣本點，以使訓練集內各類樣本量均衡；(2)對大類進行隨機下抽樣，即通過隨機選擇大類內的樣本點，以使訓練集內各類樣本量均衡；(3)前兩類基本方法的改進：有意識地增加或減少一些樣本點[4-7]；(4)各種不同方法的結合運用[8]。比較而言，每種改進方法都有其合理的思想基礎和實用價值。但是，沒有一種方法是萬能的。實際上，改進方法的效果，還取決于其他諸多因素，包括：分類器本身的特性，如，分類器對數據不平衡現象的敏感程度；數據集的特性，如，線性可分程度，類間交疊程度，數據不平衡的程度，訓練集的大??；等等。

石勇教授提出的多目標線性規劃(Multiple Criteria Linear Programming，以下（簡稱MCLP)[9-10]是一種比較年輕而優秀的線性判別分類方法，在學術界和應用領域已經取得了相當大的成功。但對于其在不平衡數據集上的表現，尚沒有系統的研究。本文以二分類的信用卡客戶數據集為例，根據MCLP的特性，從模型層面，提出適用于MCLP的不平衡數據處理技術，并對有效性進行實證分析。

1 MCLP分類模型

MCLP分類模型通過目標函數控制分類業績，以約束條件作為判別準則。以信用卡客戶數據集為例，一個兩分類問題的MCLP模型為：

假定該數據集內的客戶已經被分為兩類，好人(Good，以下簡稱G)和壞人(Bad，以下簡稱B)，并且兩類之間具有較好的線性可分性。對于客戶i，可以用由r個預測變量構成的向量Ai來刻畫，Ai=(Ai1,Ai2,…,Air)，i=1，2，…，n，n為信用卡客戶數，即樣本量。MCLP的思想是：希望求出一個系數向量X=（x1，...，xr）‘，和一個分類邊界b（標量），由此構成一個線性判別式AX=b,以便把現有數據集內的兩類客戶分開，并對新的客戶進行歸類。對于客戶i(表示為Ai)，通過計算其得分AiX，然后將其與b進行比較，以便對該客戶進行歸類。

為便于直觀表示，假設“壞人”集合B在b的左方，“好人”集合G在邊界b的右方。一般來說，數據集內的兩類數據并不是完全線性可分的，所以它們有一定程度的重疊，如圖1所示。在重疊區域，一些數據可能會被錯誤地分類。假設第i個客戶被錯誤分類，記αi為點Ai到邊界b的距離（即被錯分的程度）；同理，假設第i個客戶被正確分類，記βi為點Ai到b的距離。對于任一點Ai，它要么被正確分類，要么被錯誤分類，所以ai和βi中，至少有一個為0。所有被正確分類的點，有ai=0；所有被錯誤分類的點，有βi=0。因此兩類客戶符合以下等式所反映的條件。

MCLP的目標是同時要求最小化Sai和最大化Sbi。最初的MCLP分類模型表述為：

(M1)Minimizeand MaximizeSubject to:其中，Ai已知，X和b無約束,αi,0,bi,0,i=1,2,…,n M1的幾何意義如圖1所示：

對M1，也可以看作是同時要求最 大 化-Sai和 Sbi。而兩個目標此消彼長，不可能同時達到最大。石勇等人[12]引入妥協解的概念，將問題轉化為在兩個目標之間尋求一個最優的折中，從而將多目標決策問題轉化為單目標決策問題。

圖1 帶有重疊的二分類問題

假設-Sai的理想值為α?＞ 0，Sbi的理想值為β?＞ 0。利用妥協解的存在性，在-Sai和Sbi的關系曲線中尋找一個點A，使A點到理想點（α?，β?）的距離最短。這里，就是要求A點處的-Sai到α?的距離與Sbi到β?的距離之和最小。-Sai到α?的距離就是妥協值-Sai與α?的差距或稱為遺憾，Sbi到β?的距離就是妥協值Sbi與β?的差距或稱遺憾。因而新的目標函數就變成妥協解情況下兩個目標的妥協值與理想值之間的差距或遺憾之和最小。具體來說，如此定義遺憾：如果-Sai＞ a*，定義遺憾為-da+=Sai+a*；否則，-da+=0。如果-Siai＜ a*，定義遺憾為da-=a*+Sai；否則da-=0。因此，總是有0。同理，有

M1進一步演化為單目標線性規劃模型：

Minimize

Subject to

其中，Ai已知，X和b無約束,α?和β?給定

M2的幾何意義如圖2所示：

Min

圖2 基于妥協解的MCLP模型

作為一種線性分類模型，MCLP的原理簡單易懂，易于計算機實現。尤其在計算時，可以靈活地修改參數b，α*，β*。另外，它是一種非參數方法，對數據不需要任何假設。從M2可以看出，要使目標函數達到最小，算法會自動尋找使Sai足夠小和Sbi足夠大的解。其中，為使Sai足夠小，應同時使和足夠小，但兩者此消彼長，不能同時達到足夠?。煌?，為使Sbi足夠大，應同時使和足夠大，同樣，和不能同時達到足夠大。而在不平衡訓練數據集內，兩類數據規模不同。假定B類數目少，G類數目多，所以為使Sai足夠小，模型在求解過程中，會傾向于忽略和的作用，強調和的作用，從而將小類錯分為大類，使得小類錯誤率高于大類。由此可以看出，MCLP對兩類數據樣本量的比例（即類分布）比較敏感。

2 面向不平衡數據集的加權MCLP模型

本文基于MCLP模型本身，提出加權的MCLP分類模型，以改善小類的分類結果。該方法的基本思想是：假定訓練集內小類和大類樣本量分別為n1和n2（n1＜n2）,要求小類中的n1個樣本點與大類中的n2個樣本點在模型求解時發揮近似相同的作用，以達到兩類數據分類結果的均衡。兩類樣本點在模型中發揮作用，是通過各樣本點的αi和βi的取值實現的。這就需要在Sai和Sbi的組成中，兩類樣本點的力量比較均衡，即：在Sai中，；在Sbi中

這就是要求小類中的任何一個樣本點，如果它被錯分，其被錯分的程度αi的作用要發揮至原來的n2/n1倍；同樣，如果它被正確分類，其βi值的作用也要發揮至原來的n2/n1倍。通過修改M2模型中的一個約束條件，即可實現該目標。即：

將AiX=b+αi-βi,Ai∈B修改為：

這里，用n2/n1代表小類中每個樣本點的權數，因而將修改后的MCLP模型稱為加權的MCLP模型。

該方法相當于對每個小類樣本點，通過簡單復制，形成n2/n1個樣本點參與建模，本質上類似于上抽樣。而與隨機上抽樣相比，該方法對小類樣本點的復制更為均勻、全面。

3 實證分析

下面運用美國一家銀行的信用卡客戶數據集，說明該方法的有效性。

3.1 數據準備

經過整理，該數據集含有66個預測變量，5000條數據。由于其不平衡程度較嚴重（小類占16%），數據集較大，線性可分性一般，數據重疊嚴重（后兩個特性可以從下面的分析中反映出來），因此該數據集很有代表性。首先將數據集隨機分為訓練池和測試集，并保證兩者的分布相同。訓練池是所有可用于訓練的數據的集合，但建模時真正的訓練集可能不同于訓練池。各方法的效果用測試集上的分類結果來反映。為減少數據集分割的隨機性產生的影響，對數據集進行3輪隨機分割，用3輪隨機分割的平均結果作為總的分類結果。同時，為使結果更具代表性，還要考察2種不同規模的訓練集和測試集上的結果。分割結果見表1。

表1 信用卡數據集的分割

由于信用卡客戶數據集的維數較高，不易直觀顯示兩類樣本點的分布情況。運用MCLP對其進行分類時，分類結果是滿足M2模型目標函數的最優結果，因而，可以用M2的原始分類結果近似刻畫兩類樣本點的分布情況。在模型求解時，設分界值b=1。

以第一輪分割形成的規模為3744（小類612+大類3132）的訓練數據為例，運用MCLP M2對其分類，計算各樣本點的分值AX，并觀察各分值與判別邊界b的關系。這里，相當于把66維空間中的每個樣本點投影到一維空間中，而b則為該空間中的一個點，并作為兩類樣本點的分界限。從圖3和4可以看出，兩類樣本點的分值都比較密集，由此我們推斷兩類樣本點交疊比較嚴重。這里假定訓練池和測試集的分布特點相同。如果仍按b=1作為分類界限，不論訓練集還是測試集，小類的錯誤率都將接近60%，這是決策者所不能接受的。

圖3 3744個訓練數據中小類樣本點的分值分布圖

圖4 3744個訓練數據中大類樣本點的分值分布圖

3.2 加權MCLP模型中權數的設置

運用加權的MCLP模型時，訓練集使用原始的類分布。在訓練集樣本量為1256和3744時，訓練集內大類與小類的樣本量之比均約為5.2，故在加權的MCLP模型中，每個小類樣本點的權數n2/n1=5.2。

3.3 其他設置

為了顯示本文所提出方法的效果，這里再運用兩種基于數據層面的抽樣技術：隨機下抽樣和隨機上抽樣。為了減少抽樣隨機性的影響，在進行下抽樣時，對于每個比例、每一輪的分割，都從分割形成的訓練池中，選取全部小類數據，對大類獨立進行35次的隨機下抽樣，并保證兩類樣本量的平衡，形成該輪的35個訓練集，并利用這35個訓練集的解在測試集上的結果進行平均，最后再對3輪的結果進行平均。同樣地，在進行上抽樣時，對于每個比例、每一輪的分割，都從分割形成的訓練池中，選取全部大類數據，對小類獨立進行35次的隨機上抽樣，同時保證兩類訓練樣本量的平衡，形成該輪的35個訓練集，并利用這35個訓練集的解在測試集上的結果進行平均。

3.4 各種改進方法的結果比較

為對不同方法進行比較，在模型求解和在測試集上進行判別分類時，判別閾值b統一設置為1。為了比較不同方法的綜合分類結果，這里，也給出了各種方法在測試集上的AUC值。所有結果見表2。

可以看出，（1）根據原始類分布訓練出的模型在測試集上的AUC值相對較高，這主要是由于訓練集的分布和測試集的分布基本相同。但以b=1作為測試集上的判別界限時，小類的正確率太低。相對于原始類分布，其他四種方法對小類的分類結果都有很大提高。（2）運用隨機下抽樣技術時，小類的正確率較高，但大類的正確率相對較低，因而綜合兩類的結果，AUC值最低。這主要是由于小類樣本量較小，因而大類中參與訓練的樣本點比例較低，代表性不足，大類存在信息丟失。（3）在隨機上抽樣中，由于小類點子是被隨機選擇并被復制的，可能出現的情況是，有的小類樣本點被多次復制，而有的小類樣本點則被復制的次數較少。如果小類中不幸存在被誤標簽的樣本點或太多靠近邊界的樣本點，這些點被多次復制，就會不利于小類的分類結果。（4）相比而言，如果所有小類樣本點被同等次數地復制，就不會過度夸大或縮小某個樣本點的作用，訓練集內小類樣本點的分布與原始分布相同，能較好地代表小類數據，因而從AUC看，結果比隨機上抽樣和隨機下抽樣好。（5）運用原始類分布和加權的MCLP模型，本質上相當于將所有小類樣本點均勻復制，所以其結果與第四種方法幾乎相同。而與上述三種數據平衡方法相比，它不需要進行數據集的平衡處理，只需根據訓練集的類分布（假定訓練集和測試集的類分布基本相同），在模型中確定小類樣本點的權數n2/n1。因此，不僅減少了數據操作的麻煩，而且與任何上抽樣技術相比，其運算效率大大提高。

4 結論

本文分析了MCLP分類方法在不平衡數據集上的特性，提出了一種加權的MCLP模型，以減少數據集不平衡對MCLP分類業績的影響。并以信用卡數據集為例，比較分析了幾種不平衡數據處理方法對MCLP業績的影響，顯示了本文所提出方法的有效性和效率方面的優勢。當然，本文只在一個數據集上進行了分析，未來還需要運用更多數據集來驗證該方法的優勢，并提出更多基于MCLP分類模型的不平衡數據處理方法。

表2 各種方法在測試集上的分類結果比較

[1] P E Hart.The Condensed Nearest Neighbor Rule[J].IEEE Transactions on Information Theory,1968，(14).

[2] D L Wilson.Asymptotic Properties of Nearest Neighbor Rules Using Edited Data[J].IEEE Transactions on Systems，Man，and Communications，1972,(3).

[3] I Tomek.Two Modifications of CNN[J].IEEE Transactions on Systems Man and Communications,SMC-6,1976.

[4] M Kubat，S Matwin.Addressing the Curse of Imbalanced Training Sets:One-Sided Selection[A].Proceedings of the Fourteenth International Conference on Machine Learning[C].San Francisco：Morgan Kaufmann，1997.

[5] N V Chawla，K W Bowyer，L O Hall，et al.SMOTE:Synthetic Minority over-sampling Technique[J].Journal of Artificial Intelligence Research,2002,(16).

[6] C Phua，D Alahakoon,V Lee.Minority Report in Fraud Detection:Classification of Skewed Data[J].IGKDD Explorations,2 004，6(1).

[7] G H Nguyen,A Bouzerdoum,S L Phung.A Supervised Learning Approach for Imbalanced Data Sets[A].Proceedings of Nineteenth International Conference on Pattern Recognition[C].IEEE Computer Society,2008.

[8] G E Batista，R C Prati,M C Monard.A Study of the Behavior of Several Methods for Balancing Machine Learning Training Data[J].SIGKDD Explorations，2004,6（1）.

[9] Y Shi，M Wise，M Luo，et al.Data Mining in Credit Card Portfolio Management:A Multiple Criteria Decision Making Approach[A].M Koksalan，S Zionts.Multiple Criteria Decision Making in the New Millennium[M].Berlin:Springer,2001.

[10] Y Shi,Y Peng,W X Xu,X Tang.Data Mining via Multiple Criteria Linear Programming:Applications in Credit Card Portfolio Management[J].Information Technology and Decision Making，2002,1（1）.