面向分類模型學(xué)習(xí)的樣本類別均衡化方法

李國和 劉順欣 張予杰 鄭藝峰 洪云峰 周曉明

1(中國石油大學(xué)(北京)石油數(shù)據(jù)挖掘北京市重點(diǎn)實(shí)驗(yàn)室 北京 102249) 2(中國石油大學(xué)(北京)信息科學(xué)與工程學(xué)院 北京 102249) 3(塔里木油田克拉油氣開發(fā)部 新疆 庫爾勒 841000) 4(中國反侵權(quán)假冒創(chuàng)新戰(zhàn)略聯(lián)盟 浙江 杭州 310010) 5(廈門瀚影物聯(lián)網(wǎng)應(yīng)用研究院 福建 廈門 361021)

0 引 言

類別不均衡數(shù)據(jù)廣泛存在于生產(chǎn)生活中，如醫(yī)療診斷、信用卡欺詐和文本分類等[1-3]，直接采用此類數(shù)據(jù)進(jìn)行學(xué)習(xí)建模，少數(shù)類樣本稀少，模型難以獲取數(shù)據(jù)空間分布的內(nèi)部真實(shí)規(guī)律，存在潛在分類偏好，從而導(dǎo)致分類精度降低，因此，對(duì)此類數(shù)據(jù)的均衡化處理受到關(guān)注。

類別均衡化方法主要在算法層面或數(shù)據(jù)層面進(jìn)行，以提升對(duì)少數(shù)類樣本識(shí)別率。在算法層面，主要是改進(jìn)分類算法或設(shè)計(jì)對(duì)不均衡分布不敏感的新算法，如代價(jià)敏感學(xué)習(xí)[4]、單類學(xué)習(xí)[5]和集成學(xué)習(xí)[6]等。在數(shù)據(jù)層面，通過過采樣(生成樣本)或欠采樣(刪除樣本)以均衡化樣本類別分布。過采樣通過復(fù)制或人工生成少數(shù)類樣本，更多保留樣本信息，得到廣泛研究。隨機(jī)過采樣通過隨機(jī)地復(fù)制少數(shù)類樣本，方法簡單，但存在大量重復(fù)樣本，容易造成過擬合。為了避免過擬合問題，SMOTE算法[7]利用K近鄰和線性插值生成少數(shù)類樣本。這些樣本的分布取決于所選擇的樣本(即種子樣本)及其近鄰樣本(輔助樣本)。如果種子樣本或輔助樣本為噪聲樣本，容易生成新的噪聲樣本。樣本空間中處于邊界的少數(shù)類樣本具有更重要的信息，Borderline-SMOTE算法僅對(duì)邊界樣本進(jìn)行SMOTE采樣[8]。根據(jù)數(shù)據(jù)分布的自適應(yīng)生成采樣算法ADASYN[9]，通過決定每個(gè)少數(shù)類樣本的權(quán)重生成不同數(shù)量的樣本。K-means SMOTE算法[10]通過K-means算法對(duì)原始樣本進(jìn)行聚類，并過濾少數(shù)類與多數(shù)類之比小于給定閾值的簇，在滿足給定閾值的簇中使用SMOTE方法進(jìn)行過采樣。G-SMOTE算法[11]通過在每個(gè)種子樣本周圍的幾何區(qū)域內(nèi)生成新樣本，擴(kuò)大了樣本的生成范圍。FTL-SMOTE算法[12]利用SVM對(duì)數(shù)據(jù)集分類后，使用噪聲樣本識(shí)別三原則對(duì)噪聲樣本進(jìn)行剔除，再對(duì)少數(shù)類進(jìn)行采樣。

上述方法根據(jù)少數(shù)類樣本的分布特點(diǎn)生成少數(shù)類新樣本，但主要存在以下問題：(1) 采用線性插值容易導(dǎo)致生成重復(fù)樣本；(2) 部分算法未考慮類內(nèi)分布不均衡；(3) 對(duì)邊界樣本進(jìn)行采樣可能使邊界更加模糊。為此本文提出基于高斯混合模型和Jensen-Shannon(JS)散度的過采樣方法GJ-RSMOTE，生成合理分布的少數(shù)類樣本，完善樣本空間。

1 相關(guān)概念

1.1 高斯混合模型

中心極限定理證明了大量相互獨(dú)立的隨機(jī)變量的均值分布的極限是正態(tài)分布，即高斯分布。

(1) 單高斯模型。多維高斯分布的概率密度函數(shù)：

(1)

式中：μ和Σ分別表示d維隨機(jī)變量X的均值向量和協(xié)方差矩陣。

(2) 高斯混合模型。高斯混合模型(Gaussian Mixture Model,GMM)為若干個(gè)單高斯模型按一定比例組合而成的模型，可近似地模擬出任意分布，其定義如下：

(2)

式中：C為高斯混合模型中子模型的個(gè)數(shù)；αc為第c個(gè)子模型的權(quán)重；μc和Σc分別表示第c個(gè)子模型的均值向量和協(xié)方差矩陣；P(x|μc,Σc)為第c個(gè)子模型的概率密度函數(shù)，即單高斯模型。

對(duì)GMM的概率估計(jì)就是對(duì)參數(shù)αc、μc和Σc的求解，如EM(Expectation Maximization)算法[13]。

1.2 Jensen-Shannon散度

1) KL散度。KL散度(Kullback-Leibler Divergence)(又稱KL距離或相對(duì)熵)用于度量兩個(gè)概率分布之間的差異。設(shè)P1、P2為隨機(jī)變量X上兩個(gè)概率分布，當(dāng)X為離散型隨機(jī)變量時(shí)，KL散度計(jì)算式表示為：

(3)

當(dāng)X為連續(xù)型隨機(jī)變量時(shí)，KL散度表示為：

(4)

KL散度具有如下兩個(gè)性質(zhì)：

(1) 非負(fù)性：KL(P1‖P2)≥0

(2) 不對(duì)稱性：KL(P1‖P2)≠KL(P1‖P2)

由上述性質(zhì)可知，如果兩個(gè)概率分布P1、P2越相似，則KL散度值越??；當(dāng)P1=P2時(shí)，KL散度值為0。

2) JS散度。在KL散度基礎(chǔ)上，定義JS散度(Jensen-Shannon divergence)[14]描述兩個(gè)概率分布的近似程度，其計(jì)算式表示為：

(5)

式中：M=(P1+P2)/2。

JS散度具有如下兩個(gè)性質(zhì)：

(1) 對(duì)稱性：JS(P1‖P2)=JS(P2‖P1)

(2) 有界性：0≤JS(P1‖P2)≤1

由上述性質(zhì)可知，如果兩個(gè)概率分布P1、P2越相似，則JS散度值越小。當(dāng)P1=P2時(shí)，JS散度值為0。

2 基于GMM和JS散度的過采樣過程

基于GMM和JS散度的過采樣過程包括:(1) 利用高斯混合模型對(duì)少數(shù)類進(jìn)行聚類；(2) 根據(jù)簇的密度為每個(gè)簇分配采樣數(shù)量；(3) 以簇為單位，根據(jù)樣本權(quán)重選擇種子樣本，并以種子樣本的K近鄰中多數(shù)類的分布選擇不同的半徑，在超球體范圍內(nèi)生成樣本；(4) 根據(jù)JS散度的閾值控制采樣的數(shù)量，加速采樣過程。

2.1 少數(shù)類樣本聚類

為了采樣后的新樣本更加符合數(shù)據(jù)的真實(shí)分布，利用GMM對(duì)少數(shù)類樣本進(jìn)行建模。通過赤池信息量準(zhǔn)則(Akaike Information Criterion,AIC)[15]確定子模型的個(gè)數(shù)C。

2.2 采樣數(shù)量設(shè)定

由GMM得到C個(gè)少數(shù)類簇，針對(duì)每個(gè)簇在樣本空間中的范圍及密度不同導(dǎo)致類內(nèi)不均衡，對(duì)稀疏的簇采樣較多的樣本，提高識(shí)別率，而對(duì)于密集的簇，采樣較少的樣本，減少過擬合風(fēng)險(xiǎn)。記第C個(gè)少數(shù)類簇為Clustc(c=1,2,…,C)，其密度由簇中樣本數(shù)量和樣本之間的歐氏距離確定：

(6)

式中：numc為Clustc中樣本的數(shù)量；d為樣本維數(shù)；aveDistc為Clustc中兩兩樣本之間的歐氏距離的平均值。

Clustc的稀疏度sparsityc：

(7)

Clustc的采樣率Rc與densityc成反比，與sparsityc成正比。對(duì)sparsityc歸一化，可得到Clustc的采樣率Rc：

(8)

總的采樣數(shù)量為numsample_sum：

numsample_sum=nummaj-nummin

(9)

即多數(shù)類樣本數(shù)量nummaj減去少數(shù)類樣本nummin數(shù)量。

Clustc的采樣數(shù)量numsample_c：

numsample_c=numsample_sum×Rc

(10)

2.3 少數(shù)類樣本生成

生成樣本由種子樣本和輔助樣本共同決定。為了保證樣本多樣性，拓寬少數(shù)類樣本的潛在區(qū)域，以種子樣本為中心，在一定半徑超球體內(nèi)生成樣本。

1) 選擇種子樣本。對(duì)于簇Clustc，記第i個(gè)樣本xc_i被選為種子樣本的概率為pc_i：

(11)

(12)

式中：d為樣本特征的維數(shù)；μc、Σc和numc分別為第c個(gè)簇的均值向量、協(xié)方差矩陣和樣本個(gè)數(shù)。

由式(11)可知，如果樣本距離聚類中心越近，則其權(quán)重越大，被選擇作為種子樣本xseed的概率也越大，反之亦然。

2) 確定少數(shù)類樣本生成范圍(半徑)。根據(jù)種子樣本K近鄰中是否存在多數(shù)類樣本進(jìn)行判斷，分兩種情況：

(1) 如果種子樣本xseed的K個(gè)近鄰樣本的標(biāo)簽全為少數(shù)類，則選擇K個(gè)近鄰樣本中距離xseed最遠(yuǎn)的樣本作為輔助樣本xsup，xseed與xsup的距離dist(xseed,xsup)作為半徑r。此時(shí)，r值較大，避免生成的少數(shù)類樣本的局限性。

(2) 如果種子樣本的K個(gè)近鄰中存在多數(shù)類樣本，則選擇距離xseed最近的多數(shù)類樣本作為輔助樣本xsup，xseed與xsup的距離dist(xseed,xsup)，以dist(xseed,xsup)/2作為半徑r。此時(shí)，r值較小，避免少數(shù)類樣本落入多數(shù)類樣本區(qū)域中。

3) 生成少數(shù)類樣本。在確定了種子樣本xseed和半徑r之后，可通過算法RSMOTE生成樣本，具體過程如算法1所示。

算法1RSMOTE

輸入：種子樣本xseed，半徑r。

輸出：新樣本xnew。

1.生成一個(gè)隨機(jī)的d維向量vnorm，每一維服從標(biāo)準(zhǔn)正態(tài)分布N(0,1)；

2.vnorm除以自身的模得到單位向量vunit；

3.對(duì)半徑r進(jìn)行縮放得到rscale=r×rand(0,1)；

4.對(duì)vunit進(jìn)行縮放和平移得到新樣本。

xnew=xseed+vunit×rscale

2.4 JS散度閾值計(jì)算

通過JS散度評(píng)價(jià)均衡化程度，提前終止過采樣過程。P1、P2為d維隨機(jī)變量X上兩個(gè)概率分布，記第f個(gè)特征上JS散度為JS(P1f‖P2f)，其中，P1f、P2f為第f特征上的概率分布。P1、P2之間的JS散度JSd(P1‖P2)：

(13)

原始樣本概率分布P0，第j次采樣后概率分布Pj(j=1,2,…,numsample_sum)，P0與Pj之間的JS散度為JSd(Pj‖P0)。隨著過采樣過程進(jìn)行，JSd(Pj‖P0)逐漸增大，意味著樣本分布差異在擴(kuò)大。為了保持少數(shù)類的分布特性，定義閾值為tjs，當(dāng)JSd(Pj‖P0)>tjs，提前終止采樣過程。

2.5 過采樣過程

過采樣算法GJ-RSMOTE的完整流程如算法2所示。

算法2基于高斯混合模型和JS散度的過采樣算法GJ-RSMOTE

輸入：采樣前的訓(xùn)練集rawTrain，近鄰個(gè)數(shù)K，聚類個(gè)數(shù)C，閾值tjs。

輸出：采樣后的訓(xùn)練集sampledTrain。

1.初始化簇的稀疏度集合sparsity、新樣本集合newData、種子樣本概率集合probseed；

2.利用GMM對(duì)少數(shù)類樣本進(jìn)行聚類；

3.Forc=1,2,…,Cdo

//對(duì)少數(shù)類每個(gè)簇

4.利用式(6)和式(7)得到第c個(gè)簇的稀疏度sparsityc；

5.添加sparsityc至集合sparsity；

6.利用式(11)和式(12)得到第c個(gè)簇的種子樣本概率集合probc；

7.添加probc至集合probseed；

8.End for

9.利用式(8)得到采樣率集合R；

10.利用式(9)得到總的采樣數(shù)量numsample_sum；

11.Forc=1,2,…,Cdo

//對(duì)少數(shù)類每個(gè)簇

12.利用式(10)得到第c個(gè)簇的采樣數(shù)量numsample_c；

13.Forj=1,2,…,numsample_cdo

14.依概率分布probc得到種子樣本xseed；

15.半徑選擇策略得到半徑r；

16.利用算法RSMOTE生成新樣本xnew；

17.添加xnew至集合newData；

18.利用式(13)得到Pj與P0之間的JS散度JSd(Pj‖P0)；

19.IfJSd(Pj‖P0)>tjs:

20.Break；

//采樣過程提前終止

21.End for

22.End for

23.sampledTrain=clearTrain∪newData；

24.ReturnsampledTrain；

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

3.1 實(shí)驗(yàn)數(shù)據(jù)基礎(chǔ)

9個(gè)數(shù)據(jù)集來自UCI數(shù)據(jù)庫(如表1所示)，其中不均衡度是指多數(shù)類樣本數(shù)與少數(shù)類類樣本數(shù)的比值。不均衡度范圍在(1,3]、(3,6]、(6,9]和(9,+∞)分別定義為“低”“中”“高”和“極高”四個(gè)等級(jí)。每個(gè)數(shù)據(jù)集每次采用10折交叉驗(yàn)證，即數(shù)據(jù)集被隨機(jī)地分為等額的10份，其中9份作為訓(xùn)練集，結(jié)合過采樣算法并訓(xùn)練分類器，剩下的1份作為測試集，重復(fù)10次實(shí)驗(yàn)，以10×10次實(shí)驗(yàn)結(jié)果平均值作為最終結(jié)果。算法參數(shù)的實(shí)驗(yàn)以決策樹C4.5為分類器，對(duì)比實(shí)驗(yàn)以C4.5和SVM作為分類器。以Python為開發(fā)語言。硬件環(huán)境為CPU：Intel(R) Core(TM) i7- 8750H；內(nèi)存：8 GB。

3.2 評(píng)價(jià)指標(biāo)

使用混淆矩陣的準(zhǔn)確率(Accuracy)、F1-measure、G-mean和AUC評(píng)估分類效果。混淆矩陣如表2所示，其中：TP、TN分別表示實(shí)際正確類別的正類樣本數(shù)量和負(fù)類樣本數(shù)量；FP、FN分別表示實(shí)際錯(cuò)誤類別的正類樣本數(shù)量和負(fù)類樣本數(shù)量。

表2 混淆矩陣

F1-measure是召回率Recall和精確率Precision的調(diào)和平均值：

G-mean為召回率和真負(fù)率(TNR)的幾何平均值:

ROC為受試者工作特征曲線，其與坐標(biāo)圍成的面積(AUC)評(píng)價(jià)分類效果，以上評(píng)價(jià)指標(biāo)的取值范圍均在[0,1]內(nèi)，值越大則分類效果越好。

3.3 實(shí)驗(yàn)參數(shù)設(shè)定

GJ-RSMOTE參數(shù)包括近鄰K值和閾值tjs。

(1) 近鄰參數(shù)K。在Harberman、Vehicle和Page數(shù)據(jù)集上對(duì)近鄰參數(shù)K進(jìn)行效果驗(yàn)證。數(shù)據(jù)集不均衡等級(jí)分別為“低”“中”和“高”，采用G-mean和AUC作為評(píng)價(jià)指標(biāo)。K取值范圍為[3,8],步長為1，實(shí)驗(yàn)結(jié)果如圖1至圖3所示?？梢钥闯?，對(duì)于同一個(gè)數(shù)據(jù)集，隨著K值的增加，G-mean和AUC呈現(xiàn)相同的變化趨勢；對(duì)于不同數(shù)據(jù)集，評(píng)價(jià)指標(biāo)取最優(yōu)值時(shí)K的取值不同。K的取值范圍為3～8之間。

(2) 閾值tjs。Ecoli、Page和Yeast- 02579數(shù)據(jù)集上對(duì)閾值tjs進(jìn)行效果驗(yàn)證。數(shù)據(jù)集不均衡等級(jí)分別為“高”“高”和“極高”，采用G-mean和AUC作為評(píng)價(jià)指標(biāo)，實(shí)驗(yàn)結(jié)果如圖4-圖9所示。除了對(duì)比評(píng)價(jià)指標(biāo)G-mean和AUC外，還比較了在不同閾值tjs下，采樣及訓(xùn)練模型的平均時(shí)間。

從圖4和圖5中可以看出，Ecoli數(shù)據(jù)集在tjs=0.024之后的時(shí)間不發(fā)生變化，而在tjs=0.018時(shí)分類效果上升緩慢。由圖6和圖7可知，Page數(shù)據(jù)集在tjs=0.028時(shí)，分類效果達(dá)到最優(yōu)。由圖8和圖9可知，Yeast- 02579數(shù)據(jù)集在tjs=0.016時(shí)分類效果達(dá)到最優(yōu)。綜上所述，tjs閾值越大，則最終采樣的樣本數(shù)越多，運(yùn)行時(shí)間越長。因此，選擇合適的tjs能在保證分類效果的同時(shí)減少訓(xùn)練時(shí)間。

3.4 實(shí)驗(yàn)結(jié)果對(duì)比

為了驗(yàn)證GJ-RSMOTE的有效性，將其與SMOTE、Borderline-SMOTE、K-means SMOTE和G-SMOTE進(jìn)行對(duì)比，并采用準(zhǔn)確率、F1-measure、G-mean和AUC為評(píng)價(jià)指標(biāo)。分類器使用C4.5和SVM，SVM的核函數(shù)為高斯核。實(shí)驗(yàn)結(jié)果如表3-表10所示。為了便于觀察與分析，每個(gè)數(shù)值均放大了100倍，算法Borderline-SMOTE、K-means SMOTE、G-SMOTE和GJ-RSMOTE分別用縮寫B(tài)-S、K-S、G-S和GJ-S代替，數(shù)據(jù)集Harberman、Spectf_heart、Segment和Yeast- 02579分別用縮寫Har、Spe、Seg和Y02579代替，每組數(shù)據(jù)集的評(píng)價(jià)指標(biāo)的最優(yōu)值加粗表示。

表4 過采樣算法在C4.5上的F1-measure對(duì)比(%)

表5 過采樣算法在C4.5上的G-mean對(duì)比(%)

表6 過采樣算法在C4.5上的AUC對(duì)比(%)

續(xù)表6

表7 過采樣算法在SVM上的準(zhǔn)確率對(duì)比(%)

表8 過采樣算法在SVM上的F1-measure對(duì)比(%)

表9 過采樣算法在SVM上的G-mean對(duì)比(%)

續(xù)表9

表10 過采樣算法在SVM上的AUC對(duì)比(%)

在表3中，GJ-RSMOTE算法在6個(gè)數(shù)據(jù)集上的準(zhǔn)確率最佳。在表4中，GJ-RSMOTE算法在7個(gè)數(shù)據(jù)集上的F1-measure值最佳。值得注意的是，Borderline-SMOTE算法在Seg數(shù)據(jù)集上F1-measure值最優(yōu)，但在Hab、Page和Y02579數(shù)據(jù)集上F1-measure值比原始數(shù)據(jù)上效果還差。在表5中，GJ-RSMOTE在8個(gè)數(shù)據(jù)集上G-mean最優(yōu)，而Borderline-SMOTE在Hab、Page、Y02579數(shù)據(jù)集上G-mean比原始數(shù)據(jù)集上效果差。在表6中，GJ-RSMOTE算法在8個(gè)數(shù)據(jù)集上AUC值最優(yōu)，而Borderline-SMOTE在Hab、Page和Y02579數(shù)據(jù)集上AUC比原始數(shù)據(jù)集上效果差。說明Borderline-SMOTE使用邊界過采樣有一定的風(fēng)險(xiǎn)使邊界模糊，加大學(xué)習(xí)器的學(xué)習(xí)難度。在表7中，GJ-RSMOTE在6個(gè)數(shù)據(jù)集上的準(zhǔn)確率得分第一。在表8中，GJ-RSMOTE在6個(gè)數(shù)據(jù)集上的F-measure得分最佳。在表9中，GJ-RSMOTE在7個(gè)數(shù)據(jù)集上G-mean最優(yōu)。在表10中，GJ-RSMOTE算法在7個(gè)數(shù)據(jù)集上AUC值最佳。GJ-RSMOTE同時(shí)考慮樣本的整體分布與局部分布，使得生成的樣本在樣本空間中有較為合理的分布，對(duì)于各種不平衡度數(shù)據(jù)集的分類性能均有一定提升。

4 結(jié) 語

監(jiān)督學(xué)習(xí)是機(jī)器學(xué)習(xí)重要分支，其根據(jù)學(xué)習(xí)算法從有監(jiān)督數(shù)據(jù)集中自動(dòng)獲取分類模型的過程。如果有監(jiān)督數(shù)據(jù)集中樣本的標(biāo)簽類別分布極度不均衡，即有些標(biāo)簽樣本極少，將會(huì)導(dǎo)致分類模型過度偏好，從而降低少數(shù)類樣本的識(shí)別率。為了最終提高分類器的分類效果，需要對(duì)類別極度不均衡的訓(xùn)練樣本集進(jìn)行均衡化預(yù)處理。采用過采樣生成少數(shù)類樣本，其關(guān)鍵完善合理的樣本空間分布。為了有效解決少數(shù)類樣本類內(nèi)不均衡，GJ-RSMOTE利用高斯混合模型對(duì)少數(shù)類進(jìn)行聚類，并根據(jù)簇的密度分配采樣數(shù)量，并在一定半徑范圍內(nèi)的超球體中生成少數(shù)類新樣本，增大生成樣本的多樣性，降低學(xué)習(xí)過擬合。此外，利用Jensen-Shannon散度控制最終生成樣本的數(shù)量，從而達(dá)到加速采樣過程的目的。GJ-RSMOTE與其他均衡化算法對(duì)比，在各種不均衡度的數(shù)據(jù)集上具有良好的適應(yīng)性，有效地提升均衡效果，均衡化后的數(shù)據(jù)集用于分類學(xué)習(xí)表現(xiàn)良好。關(guān)于均衡化參數(shù)的選擇需通過實(shí)驗(yàn)確定，下一步將研究均衡化參數(shù)的自適應(yīng)選取。