周建偉

（南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 南京 210094）

1 引言

近二十年來(lái)，不平衡學(xué)習(xí)（Imbalanced Data Learning）問(wèn)題作為機(jī)器學(xué)習(xí)中的一個(gè)分支得到了產(chǎn)業(yè)界、學(xué)術(shù)界、和政府基金機(jī)構(gòu)的密切關(guān)注，成為了業(yè)界各大會(huì)議研討的重要主題之一［1～2］?，F(xiàn)實(shí)生活中，數(shù)據(jù)不平衡問(wèn)題廣泛存在于各個(gè)不同領(lǐng)域，如網(wǎng)絡(luò)入侵檢測(cè)、圖像識(shí)別、信息檢索、金融欺詐檢測(cè)、風(fēng)險(xiǎn)管理、生物醫(yī)學(xué)應(yīng)用和石油溢出檢測(cè)等［3～4］。對(duì)于這些問(wèn)題，相比較于多數(shù)類(lèi)，少數(shù)類(lèi)樣本往往包含著重要的信息，且常常具有更高的錯(cuò)判代價(jià)，因此我們更關(guān)注少數(shù)類(lèi)樣本的分類(lèi)準(zhǔn)確性。比方說(shuō)，信用卡欺詐檢測(cè)的案例，欺詐行為在全部交易記錄中往往占非常小的比例，將一個(gè)正常交易行為誤判成欺詐行為，也許會(huì)失去一個(gè)信用良好的客戶(hù)，帶來(lái)一定的損失?？墒菍⒁粋€(gè)欺詐行為歸類(lèi)為了正常交易行為所帶來(lái)的損害則更為嚴(yán)重。

對(duì)于不平衡學(xué)習(xí)。其根本問(wèn)題是數(shù)據(jù)分布不均衡導(dǎo)致很多傳統(tǒng)機(jī)器學(xué)習(xí)的分類(lèi)算法性能大大減弱。因?yàn)榇蠖鄶?shù)分類(lèi)算法事先假設(shè)訓(xùn)練集具有相等的誤分類(lèi)代價(jià)或平衡的數(shù)據(jù)分布［5］，所以這些算法在面對(duì)相對(duì)復(fù)雜的不平衡數(shù)據(jù)集時(shí)便不能有效地反應(yīng)出數(shù)據(jù)的分布特征。如此一來(lái)，當(dāng)這些傳統(tǒng)分類(lèi)算法在樣本不平衡的數(shù)據(jù)集上訓(xùn)練時(shí)，經(jīng)常會(huì)出現(xiàn)分類(lèi)面偏倚的現(xiàn)象，使得最終無(wú)法獲得令人滿(mǎn)意的分類(lèi)效果，甚至?xí)霈F(xiàn)模型完全失效的糟糕情況［6～7］。

不平衡學(xué)習(xí)因其重大研究意義而在機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域備受矚目，多個(gè)業(yè)內(nèi)主流的期刊和會(huì)議都專(zhuān)門(mén)針對(duì)此問(wèn)題舉辦過(guò)專(zhuān)刊或研討會(huì)［8］。例如 AAAI'2000［9］、ICML'2003［10］、ACM SIGKDD Exploration'2004［11］和 PAKDD'2009［12］。

2 基于高斯混合模型的下采樣

處理類(lèi)不平衡問(wèn)題的方法通常可以分為數(shù)據(jù)、算法和集成這三個(gè)層面，其中從數(shù)據(jù)層面的解決方法一般有上采樣、下采樣和混合采樣。而下采樣技術(shù)的關(guān)鍵就是如何通過(guò)減少多數(shù)類(lèi)樣本使得兩類(lèi)數(shù)據(jù)達(dá)到相對(duì)平衡狀態(tài)，并且保持多數(shù)類(lèi)樣本的整體分布。概率論中的中心極限定理證明了大量相互獨(dú)立的隨機(jī)變量，其均值（或者和）的分布的極限是正態(tài)分布，即高斯分布。我們由高斯混合模型（Gaussian Mixture Model，GMM）的定義可知，它實(shí)質(zhì)上就是單高斯分布模型的一種擴(kuò)展，可以有效地近似模擬各種復(fù)雜的數(shù)據(jù)分布?；谝陨纤伎?，論文提出了一種基于高斯混合模型的下采樣算法（Gaussian Under-Sampling，GUS）。首先利用高斯混合模型對(duì)負(fù)類(lèi)數(shù)據(jù)進(jìn)行擬合，然后再依據(jù)每個(gè)子模型上數(shù)據(jù)的分布情況，即概率區(qū)間按比例進(jìn)行下采樣。

2.1 高斯混合模型

高斯混合模型其實(shí)就是由K個(gè)單高斯模型組合而成的，這K個(gè)子模型就是混合模型的隱變量（Hidden Variable）。其概率分布密度函數(shù)為

其中，x表示服從GMM分布的隨機(jī)變量，K表示GMM中的子模型的個(gè)數(shù)，μk和∑k則分別表示第k個(gè)子模型的均值與方差，表示第k個(gè)子模型的概率密度函數(shù)，αk是觀測(cè)數(shù)據(jù)屬于第k個(gè)子模型的概率，即第k個(gè)子模型的權(quán)重，并且滿(mǎn)足以下條件:

高斯混合模型假定所有的樣本點(diǎn)都是由有限個(gè)單高斯模型生成的，對(duì)于此模型的求解就是對(duì)其概率密度函數(shù)的參數(shù)求解，通常我們利用最大期望算法（Expectation Maximization，EM）對(duì)高斯混合模型的參數(shù)進(jìn)行求解。

2.2 決策樹(shù)與隨機(jī)森林

決策樹(shù)（decision tree）是一種基于樹(shù)的結(jié)構(gòu)進(jìn)行決策的分類(lèi)方法，它的構(gòu)建過(guò)程就是選擇特征和確定決策規(guī)則的過(guò)程［13］。

ID3，C4.5和CART算法都是經(jīng)典的決策樹(shù)算法。

隨機(jī)森林（Random Forest，RF），簡(jiǎn)單來(lái)說(shuō)，就是建立很多決策樹(shù)，構(gòu)建一個(gè)決策樹(shù)的“森林”，通過(guò)各個(gè)決策樹(shù)的投票來(lái)進(jìn)行決策［14］。隨機(jī)森林算法的基本步驟為

1）通過(guò)自舉重采樣的方式從N個(gè)原始的樣本中有放回地隨機(jī)抽取N個(gè)樣本，從而產(chǎn)生多個(gè)樣本集；

2）利用每次重采樣產(chǎn)生的樣本集作為訓(xùn)練樣本構(gòu)建一棵決策樹(shù)。并且在構(gòu)建決策樹(shù)的過(guò)程中先從該結(jié)點(diǎn)的候選特征中隨機(jī)選擇一個(gè)包含k個(gè)特征的子集，作為當(dāng)前結(jié)點(diǎn)的備選特征，然后再?gòu)倪@些備選特征中選擇一個(gè)最優(yōu)屬性用于劃分；

3）構(gòu)建了指定數(shù)目的決策樹(shù)后，RF對(duì)這些決策樹(shù)的輸出進(jìn)行匯總，得票最多的類(lèi)就作為RF的輸出。

2.3 GUS算法

GUS算法的主要思想是利用高斯混合模型對(duì)負(fù)類(lèi)數(shù)據(jù)進(jìn)行擬合，得到多數(shù)類(lèi)樣本對(duì)應(yīng)的高斯混合模型，然后根據(jù)每個(gè)單高斯模型上數(shù)據(jù)的分布情況，按照概率區(qū)間內(nèi)樣本的的比例進(jìn)行下采樣，從而使得多數(shù)類(lèi)樣本數(shù)與少數(shù)類(lèi)樣本數(shù)達(dá)到相對(duì)平衡的狀態(tài)。

高斯混合模型能夠有效地描述數(shù)據(jù)的分布情況，但同時(shí)高斯混合模型對(duì)參數(shù)具有一定敏感性，例如高斯分量的個(gè)數(shù)。為了更好地觀察高斯分量的個(gè)數(shù)對(duì)描述數(shù)據(jù)分布的影響，我們選擇了常常用來(lái)做聚類(lèi)分析的二維數(shù)據(jù)集TwoMoons來(lái)進(jìn)行測(cè)試。實(shí)驗(yàn)結(jié)果如圖1所示，可以發(fā)現(xiàn)高斯分量的個(gè)數(shù)選擇對(duì)數(shù)據(jù)的擬合是有一定影響。所以在我們正式利用高斯混合模型對(duì)多數(shù)類(lèi)數(shù)據(jù)進(jìn)行擬合之前，需要對(duì)數(shù)據(jù)有一定的了解。查詢(xún)數(shù)據(jù)集的來(lái)源和應(yīng)用背景、了解數(shù)據(jù)的屬性特征以及利用相關(guān)算法進(jìn)行參數(shù)尋優(yōu)，都有利于我們對(duì)參數(shù)進(jìn)行更好的選擇。目前，對(duì)于高斯分量個(gè)數(shù)確定的方法中最常用的兩種方法就是利用赤池信息準(zhǔn)則（Akaike information criterion，AIC，又稱(chēng)最小信息準(zhǔn)則）和貝葉斯信息準(zhǔn)則（Bayesian Information Criterion，BIC）來(lái)進(jìn)行參數(shù)尋優(yōu)。本次實(shí)驗(yàn)中，我們采用了赤池信息準(zhǔn)則來(lái)確定混合高斯模型中高斯分量的個(gè)數(shù)。

記原始訓(xùn)練集S=S+∪S-，其中S+和S-分別表示少數(shù)類(lèi)樣本集和多數(shù)類(lèi)樣本集。

GUS算法的主要步驟為

第一步:置新的多數(shù)類(lèi)樣本集Snew為空，并利用赤池信息準(zhǔn)則AIC進(jìn)行參數(shù)尋優(yōu)，確定高斯分量的個(gè)數(shù)K。

圖1 不同高斯分量下的TwoMoons數(shù)據(jù)集的數(shù)據(jù)分布等高線(xiàn)圖，第一行從左到右高斯分量的個(gè)數(shù)分別為1、2、3，第二行從左到右高斯分量的個(gè)數(shù)分別為4、5、6

第二步:利用高斯混合模型對(duì)多數(shù)類(lèi)S-進(jìn)行擬合，建立一個(gè)高斯混合模型。

第三步:依照各個(gè)高斯分量中的數(shù)據(jù)分布以及每個(gè)高斯分量里概率區(qū)間中的數(shù)據(jù)分布情況，然后根據(jù)各個(gè)概率區(qū)間內(nèi)的樣本所占比例進(jìn)行隨機(jī)下采樣，得到第i個(gè)高斯分量上的采樣數(shù)據(jù)集Ci, i=1:K。

第四步:將從每個(gè)高斯分量中采樣獲得的樣本納入新的多數(shù)類(lèi)樣本集合Snew。

第五步:輸出下采樣后新的訓(xùn)練集S'=S+∪Snew。

2.4 評(píng)估指標(biāo)

在機(jī)器學(xué)習(xí)的二分類(lèi)問(wèn)題中，通常將多數(shù)類(lèi)記為負(fù)類(lèi)（Negative），而將具有高識(shí)別重要性的少數(shù)類(lèi)記為正類(lèi)（Positive）。二分類(lèi)問(wèn)題的混淆矩陣（Confusionmatrix）如表1所示。

表1 混淆矩陣

從表1我們可以看出，TP和TN分別表示樣本本身就是正類(lèi)/負(fù)類(lèi)，然后被正確預(yù)測(cè)為正類(lèi)/負(fù)類(lèi)的樣本數(shù)，F(xiàn)P和FN則表示樣本實(shí)際標(biāo)簽是負(fù)類(lèi)/正類(lèi)，但是卻被錯(cuò)誤地預(yù)測(cè)為正類(lèi)/負(fù)類(lèi)的樣本數(shù)［15］。根據(jù)混淆矩陣的定義:

查全率:Recall=TP/（TP+FN）

查準(zhǔn)率:Precision=TP/（TP+FP）

F-measure是查全率和查準(zhǔn)率的調(diào)和均值，其定義如下:

其中，β是用于調(diào)節(jié)Recall和Precision的相對(duì)重要度的參數(shù)，通常取1，此時(shí)F-measure的實(shí)質(zhì)是Recall和Precision的調(diào)和平均數(shù)，即有:

評(píng)估指標(biāo)G-mean則是計(jì)算了正類(lèi)和負(fù)類(lèi)樣本分類(lèi)準(zhǔn)確度的幾何均值，其定義如下:

不平衡學(xué)習(xí)中另一個(gè)重要的評(píng)估指標(biāo)就是馬氏 相 關(guān) 系 數(shù)（Matthew's correlation coefficient，MCC），其定義如下:

可以看出，以上幾個(gè)指標(biāo)都是基于閾值的，所以我們還選取了另一種評(píng)估指標(biāo)AUC（Area Under ROCCurve），即 ROC（Receiver Operating Characteristic Curve）曲線(xiàn)下方的面積。AUC值與閾值的選取無(wú)關(guān)，是一個(gè)衡量分類(lèi)器的整體性能重要指標(biāo)。

因?yàn)镸CC綜合考慮了各方面的評(píng)估指數(shù)，可以作為分類(lèi)模型總體性能的衡量標(biāo)準(zhǔn)。本文我們則是選擇MCC最大時(shí)的其他各項(xiàng)指標(biāo)值作為實(shí)驗(yàn)的評(píng)估結(jié)果。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 采樣前后的數(shù)據(jù)分布比較

統(tǒng)計(jì)學(xué)中，可以從數(shù)據(jù)分布的集中趨勢(shì)、離散程度以及形狀這三個(gè)方面對(duì)數(shù)據(jù)集的分布特征進(jìn)行描述。

本文就從這三個(gè)方面分析利用高斯混合模型進(jìn)行下采樣后樣本集的數(shù)據(jù)分布，分別選擇均值和方差作為描述指標(biāo)，并繪制數(shù)據(jù)在采樣前后的分布形狀。與此同時(shí)利用高斯混合模型做聚類(lèi)分析，并繪制聚類(lèi)后的結(jié)果圖。為了方便我們觀察數(shù)據(jù)分布的形狀，選擇二維的數(shù)據(jù)集進(jìn)行驗(yàn)證。數(shù)據(jù)均值與方差的統(tǒng)計(jì)結(jié)果如表2所示，樣本集在采樣前后的數(shù)據(jù)分布的形狀如圖2、圖3、圖4和圖5所示。分析發(fā)現(xiàn)，兩組數(shù)據(jù)在采樣前后的均值和方差非常接近，并且采樣后數(shù)據(jù)集的分布形狀保持得很好。并且，我們針對(duì)三個(gè)高斯分布合成的數(shù)據(jù)在采樣前后分別進(jìn)行了聚類(lèi)分析，得到聚類(lèi)的結(jié)果分別如圖6和圖7所示，從最后的聚類(lèi)結(jié)果來(lái)看，采樣前后數(shù)據(jù)的聚類(lèi)結(jié)果基本保持不變。所以，可以看出我們提出的GUS算法在減少負(fù)類(lèi)樣本數(shù)目的同時(shí)也很好地保持了數(shù)據(jù)的整體分布。

表2 兩組數(shù)據(jù)集采樣前后均值與方差對(duì)比

圖2 TwoMooms數(shù)據(jù)集采樣前的數(shù)據(jù)分布圖

圖3 TwoMoons數(shù)據(jù)集采樣后的數(shù)據(jù)分布圖

圖4 三個(gè)高斯分布合成的數(shù)據(jù)集采樣前的數(shù)據(jù)分布圖

圖5 三個(gè)高斯分布合成的數(shù)據(jù)集采樣后的數(shù)據(jù)分布圖

圖6 三個(gè)高斯分布合成的數(shù)據(jù)集采樣前的聚類(lèi)結(jié)果

圖7 三個(gè)高斯分布合成的數(shù)據(jù)集采樣后的聚類(lèi)結(jié)果

3.2 UCI數(shù)據(jù)集上的結(jié)果

本次我們選取了6組具有不同應(yīng)用背景的不平衡數(shù)據(jù)集來(lái)進(jìn)行實(shí)驗(yàn)。數(shù)據(jù)集的詳細(xì)信息如表3所示。

為了方便和文獻(xiàn)［16］中的其他方法進(jìn)行實(shí)驗(yàn)結(jié)果的比較，實(shí)驗(yàn)選擇隨機(jī)森林作為分類(lèi)器。與GUS算法進(jìn)行比較的有:Random Forest（簡(jiǎn)稱(chēng)RF），表示的是對(duì)數(shù)據(jù)沒(méi)有采取任何重采樣技術(shù)的情況下直接使用隨機(jī)森林進(jìn)行分類(lèi)的結(jié)果，隨機(jī)下采樣（簡(jiǎn)稱(chēng) Under）、BalanceCascade（簡(jiǎn)稱(chēng) Cascade）和EasyEnsemble（簡(jiǎn)稱(chēng)Easy），這三種方法都是經(jīng)典的下采樣方法。表4～表6詳細(xì)地描述了使用GUS方法與其他方法進(jìn)行分類(lèi)的結(jié)果。

表3 數(shù)據(jù)集信息

表4 GUS方法與其他方法在AUC值上的比較

表5 GUS方法與其他方法在F-measure值上的比較

表6 GUS方法與其他方法在G-mean值上的比較

從第一個(gè)性能評(píng)估指標(biāo)AUC值上觀察，GUS方法在pima這組不平衡數(shù)據(jù)集上的AUC值高于其他方法。在剩下六組數(shù)據(jù)集上的值雖然不是最高的，但是結(jié)果相差不大，基本保持平均水平。

對(duì)于F-measure的考察，從表5可以明顯看出，GUS方法的結(jié)果在6組實(shí)驗(yàn)數(shù)據(jù)上都是最優(yōu)的，特別是在balance、mf-zernike和housing這三組數(shù)據(jù)上的值遠(yuǎn)遠(yuǎn)高于其他方法。說(shuō)明GUS算法在處理不平衡數(shù)據(jù)的分類(lèi)問(wèn)題上的查全率和查準(zhǔn)率都非常高。

從表6觀察G-mean值，不難發(fā)現(xiàn)除了在mf-zernike數(shù)據(jù)集上的結(jié)果略低于EasyEnsemble方法，在剩下的5組不平衡數(shù)據(jù)集上的結(jié)果都高于別的方法。

通過(guò)與其他方法在三個(gè)評(píng)估指標(biāo)上的比較，可以看出GUS算法在F-measure和G-mean上的值普遍高于其他方法，在AUC上的值也不低。整體上而言，GUS算法在研究不平衡學(xué)習(xí)的問(wèn)題上取得了可觀的結(jié)果。

4 結(jié)語(yǔ)

對(duì)于二分類(lèi)不平衡學(xué)習(xí)，本文提出了一種新的下采樣算法，通過(guò)高斯混合模型對(duì)多數(shù)類(lèi)樣本進(jìn)行擬合，得到多數(shù)類(lèi)樣本的數(shù)據(jù)分布模型，利用各個(gè)子模型中數(shù)據(jù)的概率分布區(qū)間，按照樣本所占比例在每個(gè)區(qū)間內(nèi)進(jìn)行隨機(jī)下采樣，從而獲得新的多數(shù)類(lèi)樣本集，以達(dá)到平衡整個(gè)數(shù)據(jù)集分布的目的。通過(guò)在6組具有不同應(yīng)用背景的不平衡數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，并與其他幾種常用的方法進(jìn)行比較，以AUC、F-measure和G-mean值作為評(píng)價(jià)指標(biāo)。從實(shí)驗(yàn)結(jié)果上看，GUS算法取得了可觀的結(jié)果，說(shuō)明了GUS算法在處理不平衡數(shù)據(jù)問(wèn)題上具有很大的優(yōu)勢(shì)。