面向分類模型學習的樣本類別均衡化方法

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

1(中國石油大學(北京)石油數據挖掘北京市重點實驗室 北京 102249) 2(中國石油大學(北京)信息科學與工程學院 北京 102249) 3(塔里木油田克拉油氣開發部 新疆 庫爾勒 841000) 4(中國反侵權假冒創新戰略聯盟 浙江 杭州 310010) 5(廈門瀚影物聯網應用研究院 福建 廈門 361021)

0 引 言

類別不均衡數據廣泛存在于生產生活中，如醫療診斷、信用卡欺詐和文本分類等[1-3]，直接采用此類數據進行學習建模，少數類樣本稀少，模型難以獲取數據空間分布的內部真實規律，存在潛在分類偏好，從而導致分類精度降低，因此，對此類數據的均衡化處理受到關注。

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

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

1 相關概念

1.1 高斯混合模型

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

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

(1)

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

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

(2)

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

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

1.2 Jensen-Shannon散度

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

(3)

當X為連續型隨機變量時，KL散度表示為：

(4)

KL散度具有如下兩個性質：

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

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

由上述性質可知，如果兩個概率分布P1、P2越相似，則KL散度值越小；當P1=P2時，KL散度值為0。

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

(5)

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

JS散度具有如下兩個性質：

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

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

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

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

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

2.1 少數類樣本聚類

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

2.2 采樣數量設定

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

(6)

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

Clustc的稀疏度sparsityc：

(7)

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

(8)

總的采樣數量為numsample_sum：

numsample_sum=nummaj-nummin

(9)

即多數類樣本數量nummaj減去少數類樣本nummin數量。

Clustc的采樣數量numsample_c：

numsample_c=numsample_sum×Rc

(10)

2.3 少數類樣本生成

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

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

(11)

(12)

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

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

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

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

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

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

算法1RSMOTE

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

輸出：新樣本xnew。

1.生成一個隨機的d維向量vnorm，每一維服從標準正態分布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)逐漸增大，意味著樣本分布差異在擴大。為了保持少數類的分布特性，定義閾值為tjs，當JSd(Pj‖P0)>tjs，提前終止采樣過程。

2.5 過采樣過程

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

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

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

輸出：采樣后的訓練集sampledTrain。

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

2.利用GMM對少數類樣本進行聚類；

3.Forc=1,2,…,Cdo

//對少數類每個簇

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

5.添加sparsityc至集合sparsity；

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

7.添加probc至集合probseed；

8.End for

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

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

11.Forc=1,2,…,Cdo

//對少數類每個簇

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

3.1 實驗數據基礎

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

3.2 評價指標

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

表2 混淆矩陣

F1-measure是召回率Recall和精確率Precision的調和平均值：

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

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

3.3 實驗參數設定

GJ-RSMOTE參數包括近鄰K值和閾值tjs。

(1) 近鄰參數K。在Harberman、Vehicle和Page數據集上對近鄰參數K進行效果驗證。數據集不均衡等級分別為“低”“中”和“高”，采用G-mean和AUC作為評價指標。K取值范圍為[3,8],步長為1，實驗結果如圖1至圖3所示。可以看出，對于同一個數據集，隨著K值的增加，G-mean和AUC呈現相同的變化趨勢；對于不同數據集，評價指標取最優值時K的取值不同。K的取值范圍為3～8之間。

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

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

3.4 實驗結果對比

為了驗證GJ-RSMOTE的有效性，將其與SMOTE、Borderline-SMOTE、K-means SMOTE和G-SMOTE進行對比，并采用準確率、F1-measure、G-mean和AUC為評價指標。分類器使用C4.5和SVM，SVM的核函數為高斯核。實驗結果如表3-表10所示。為了便于觀察與分析，每個數值均放大了100倍，算法Borderline-SMOTE、K-means SMOTE、G-SMOTE和GJ-RSMOTE分別用縮寫B-S、K-S、G-S和GJ-S代替，數據集Harberman、Spectf_heart、Segment和Yeast- 02579分別用縮寫Har、Spe、Seg和Y02579代替，每組數據集的評價指標的最優值加粗表示。

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

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

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

續表6

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

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

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

續表9

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

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

4 結 語

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