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

1(中國石油大學(xué)(北京)石油數(shù)據(jù)挖掘北京市重點實驗室 北京 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ù)進行學(xué)習(xí)建模，少數(shù)類樣本稀少，模型難以獲取數(shù)據(jù)空間分布的內(nèi)部真實規(guī)律，存在潛在分類偏好，從而導(dǎo)致分類精度降低，因此，對此類數(shù)據(jù)的均衡化處理受到關(guān)注。

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

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

1 相關(guān)概念

1.1 高斯混合模型

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

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

(1)

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

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

(2)

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

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

1.2 Jensen-Shannon散度

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

(3)

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

(4)

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

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

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

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

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

(5)

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

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

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

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

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

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

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

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

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

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

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

(6)

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

Clustc的稀疏度sparsityc：

(7)

Clustc的采樣率Rc與densityc成反比，與sparsityc成正比。對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) 選擇種子樣本。對于簇Clustc，記第i個樣本xc_i被選為種子樣本的概率為pc_i：

(11)

(12)

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

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

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

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

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

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

算法1RSMOTE

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

輸出：新樣本xnew。

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

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

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

4.對vunit進行縮放和平移得到新樣本。

xnew=xseed+vunit×rscale

2.4 JS散度閾值計算

通過JS散度評價均衡化程度，提前終止過采樣過程。P1、P2為d維隨機變量X上兩個概率分布，記第f個特征上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)。隨著過采樣過程進行，JSd(Pj‖P0)逐漸增大，意味著樣本分布差異在擴大。為了保持少數(shù)類的分布特性，定義閾值為tjs，當(dāng)JSd(Pj‖P0)>tjs，提前終止采樣過程。

2.5 過采樣過程

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

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

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

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

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

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

3.Forc=1,2,…,Cdo

//對少數(shù)類每個簇

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

5.添加sparsityc至集合sparsity；

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

7.添加probc至集合probseed；

8.End for

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

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

11.Forc=1,2,…,Cdo

//對少數(shù)類每個簇

12.利用式(10)得到第c個簇的采樣數(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 實驗與結(jié)果分析

3.1 實驗數(shù)據(jù)基礎(chǔ)

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

3.2 評價指標(biāo)

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

表2 混淆矩陣

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

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

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

3.3 實驗參數(shù)設(shè)定

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

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

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

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

3.4 實驗結(jié)果對比

為了驗證GJ-RSMOTE的有效性，將其與SMOTE、Borderline-SMOTE、K-means SMOTE和G-SMOTE進行對比，并采用準(zhǔn)確率、F1-measure、G-mean和AUC為評價指標(biāo)。分類器使用C4.5和SVM，SVM的核函數(shù)為高斯核。實驗結(jié)果如表3-表10所示。為了便于觀察與分析，每個數(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ù)集的評價指標(biāo)的最優(yōu)值加粗表示。

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

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

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

續(xù)表6

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

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

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

續(xù)表9

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

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

4 結(jié) 語

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