一種加權(quán)的MCLP分類模型及其在不平衡數(shù)據(jù)集上的應(yīng)用

朱梅紅

（首都經(jīng)濟(jì)貿(mào)易大學(xué) 統(tǒng)計(jì)學(xué)院，北京 100070）

0 引言

在數(shù)據(jù)挖掘的分類問題中，經(jīng)常出現(xiàn)數(shù)據(jù)集內(nèi)類別不平衡現(xiàn)象。如信用卡客戶識(shí)別、生產(chǎn)過程的故障檢測(cè)等問題中，不同類別的樣本數(shù)目相差很大：信用卡客戶中“違約人”明顯少于“守約人”，生產(chǎn)過程中“故障”狀態(tài)通常少于“正?！睜顟B(tài)。對(duì)于這些不平衡數(shù)據(jù)集，決策者更希望能夠有效地識(shí)別出其中的少數(shù)類（以下簡稱小類）。

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

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

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

1 MCLP分類模型

MCLP分類模型通過目標(biāo)函數(shù)控制分類業(yè)績，以約束條件作為判別準(zhǔn)則。以信用卡客戶數(shù)據(jù)集為例，一個(gè)兩分類問題的MCLP模型為：

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

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

MCLP的目標(biāo)是同時(shí)要求最小化Sai和最大化Sbi。最初的MCLP分類模型表述為：

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

對(duì)M1，也可以看作是同時(shí)要求最 大 化-Sai和 Sbi。而兩個(gè)目標(biāo)此消彼長，不可能同時(shí)達(dá)到最大。石勇等人[12]引入妥協(xié)解的概念，將問題轉(zhuǎn)化為在兩個(gè)目標(biāo)之間尋求一個(gè)最優(yōu)的折中，從而將多目標(biāo)決策問題轉(zhuǎn)化為單目標(biāo)決策問題。

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

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

M1進(jìn)一步演化為單目標(biāo)線性規(guī)劃模型：

Minimize

Subject to

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

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

Min

圖2 基于妥協(xié)解的MCLP模型

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

2 面向不平衡數(shù)據(jù)集的加權(quán)MCLP模型

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

這就是要求小類中的任何一個(gè)樣本點(diǎn)，如果它被錯(cuò)分，其被錯(cuò)分的程度αi的作用要發(fā)揮至原來的n2/n1倍；同樣，如果它被正確分類，其βi值的作用也要發(fā)揮至原來的n2/n1倍。通過修改M2模型中的一個(gè)約束條件，即可實(shí)現(xiàn)該目標(biāo)。即：

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

這里，用n2/n1代表小類中每個(gè)樣本點(diǎn)的權(quán)數(shù)，因而將修改后的MCLP模型稱為加權(quán)的MCLP模型。

該方法相當(dāng)于對(duì)每個(gè)小類樣本點(diǎn)，通過簡單復(fù)制，形成n2/n1個(gè)樣本點(diǎn)參與建模，本質(zhì)上類似于上抽樣。而與隨機(jī)上抽樣相比，該方法對(duì)小類樣本點(diǎn)的復(fù)制更為均勻、全面。

3 實(shí)證分析

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

3.1 數(shù)據(jù)準(zhǔn)備

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

表1 信用卡數(shù)據(jù)集的分割

由于信用卡客戶數(shù)據(jù)集的維數(shù)較高，不易直觀顯示兩類樣本點(diǎn)的分布情況。運(yùn)用MCLP對(duì)其進(jìn)行分類時(shí)，分類結(jié)果是滿足M2模型目標(biāo)函數(shù)的最優(yōu)結(jié)果，因而，可以用M2的原始分類結(jié)果近似刻畫兩類樣本點(diǎn)的分布情況。在模型求解時(shí)，設(shè)分界值b=1。

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

圖3 3744個(gè)訓(xùn)練數(shù)據(jù)中小類樣本點(diǎn)的分值分布圖

圖4 3744個(gè)訓(xùn)練數(shù)據(jù)中大類樣本點(diǎn)的分值分布圖

3.2 加權(quán)MCLP模型中權(quán)數(shù)的設(shè)置

運(yùn)用加權(quán)的MCLP模型時(shí)，訓(xùn)練集使用原始的類分布。在訓(xùn)練集樣本量為1256和3744時(shí)，訓(xùn)練集內(nèi)大類與小類的樣本量之比均約為5.2，故在加權(quán)的MCLP模型中，每個(gè)小類樣本點(diǎn)的權(quán)數(shù)n2/n1=5.2。

3.3 其他設(shè)置

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

3.4 各種改進(jìn)方法的結(jié)果比較

為對(duì)不同方法進(jìn)行比較，在模型求解和在測(cè)試集上進(jìn)行判別分類時(shí)，判別閾值b統(tǒng)一設(shè)置為1。為了比較不同方法的綜合分類結(jié)果，這里，也給出了各種方法在測(cè)試集上的AUC值。所有結(jié)果見表2。

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

4 結(jié)論

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

表2 各種方法在測(cè)試集上的分類結(jié)果比較

[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）.