陶葉輝，趙壽為

（上海工程技術(shù)大學數(shù)理與統(tǒng)計學院，上海 201620）

0 引言

實際生活中，不平衡分類的場景出現(xiàn)在多方面，且不同類別的樣本數(shù)量通常呈現(xiàn)高度的不平衡，如銀行信貸［1］、癌癥診斷［2］、網(wǎng)頁檢測［3］等。有關不平衡分類正成為數(shù)據(jù)分析中非常廣泛的一類問題。不平衡學習問題處理主要從算法層與數(shù)據(jù)層兩方面解決?，F(xiàn)有的很多研究是通過對原數(shù)據(jù)進行處理來達到平衡，其中包括過采樣、欠采樣［4］、過采樣與欠采樣結(jié)合［5］3種方法。

過采樣是通過對少數(shù)類樣本進行簡單復制達到與多數(shù)類樣本的平衡，很容易導致過擬合問題。為此，Chawla等［6］提 出SMOTE（Synthetic Minority Oversampling Technique，SMOTE）算法，很大程度上避免了此類問題。該算法主要有兩個缺點：①SMOTE 算法在選擇K 近鄰上具有一定的盲目性；②SMOTE 算法容易產(chǎn)生邊緣化問題。

不少學者針對SMOTE 算法的不足進行了大量研究。鐘龍申等［7］提出K-SMOTE 算法，將原始數(shù)據(jù)中的負類替換為“新增負類”，再利用SMOTE 算法得出新數(shù)據(jù)集，提高了分類性能；陳斌等［8］提出了KM-SMOTE 算法，使少數(shù)類數(shù)據(jù)集形成以簇為中心的數(shù)據(jù)聚集，有針對性地進行插值，提高了分類效果。針對K-means 算法存在初始中心選擇不足等問題，郭朝有等［9］提出融合Canopy 和K-means 的SMOTE 改進算法，有效克服了K-means 算法初始中心選擇隨機性問題；樓曉俊等［10］通過引入“聚類一致性系數(shù)”和最近鄰密度，使得合成的新樣本更加均勻有效，提高了分類效果；韓旭等［11］提出了GMMUSA，在不改變類別空間結(jié)構(gòu)基礎上，刪除多數(shù)類的冗余信息，提高了算法在信貸數(shù)據(jù)方面的分類性能。

以上文獻均沒有考慮少數(shù)類空間結(jié)構(gòu)這一因素。因此，本文提出一種新的算法“GMM-SMOTE”。首先選擇將高斯混合模型（Gaussian Mixture Model，GMM）算法運用于少數(shù)類樣本集中，通過生成不同組數(shù)達到聚類目的；然后在保證少數(shù)類樣本空間結(jié)構(gòu)不變的情況下，刪除與聚類中心點重疊的冗余樣本；最后利用SMOTE 算法分別對不同的聚簇進行過采樣，達到與多數(shù)類樣本集樣本量平衡的目的。采用UCI（University of California，Irvine）標準數(shù)據(jù)庫［12］中的6 組數(shù)據(jù)集，基于隨機森林（Random Forests，RF）分類器進行實驗對比，結(jié)果顯示本文模型的AUC 值平均提高6.09%，可以有效平衡不平衡的數(shù)據(jù)集。

1 SMOTE過采樣

SMOTE 算法的基本思想是基于少數(shù)類樣本隨機插值生成新樣本，即一種合成少數(shù)類的過采樣技術(shù)算法。它是對以往隨機過采樣的一種改進方法，能有效解決傳統(tǒng)采樣方法容易發(fā)生過擬合的問題，提高了算法的泛化能力。

SMOTE 算法步驟如下：①對少數(shù)類的每一個樣本xi，計算其到少數(shù)類樣本集Smin中所有樣本的歐式距離，得到k 近鄰；②根據(jù)樣本不平衡比例設置采樣比例以確定采樣倍率，對每個少數(shù)類樣本xi從其k 個近鄰中隨機選擇若干個樣本，假設選擇的近鄰為xold；③對每個隨機選擇的近鄰xold，分別與xi按照隨機插值公式（1）生成新的樣本xnew，最終合成一個插值樣本均衡數(shù)據(jù)集。

其中，隨機插值公式為：

式（1）中，rand(0，1)表示(0，1)區(qū)間的隨機數(shù)。

2 肘部法則及GMM-SMOTE過采樣算法

本文提出的GMM-SMOTE 過采樣算法是在傳統(tǒng)SMOTE 算法基礎上引入高斯混合聚類思想。同時，以肘部法則確定高斯混合聚類的初始組數(shù)，即聚簇數(shù)。下面從肘部法則、高斯混合模型、GMM-SMOTE 算法步驟3個方面分別闡述。

2.1 肘部法則

肘部法則（Elbow Method）通常被用于K-means 算法［13］中，根據(jù)每個簇與簇內(nèi)樣本間的和方差（SSE）來反映簇內(nèi)結(jié)構(gòu)情況。線條畸變程度高低代表簇內(nèi)樣本的空間變化，畸變程度越高，說明簇內(nèi)結(jié)構(gòu)越松散，反之則越緊密。當某個k 點的畸變程度開始明顯變緩時，此點通常為最佳組數(shù)點［14］。如圖1所示，當k=3時，其為最佳聚類組數(shù)。

Fig.1 Elbow method description圖1 肘部法示意

2.2 高斯混合模型

高斯混合模型GMM 是由k個單高斯分布模型根據(jù)一定的權(quán)重組合而成［15］。每個高斯分布可稱為一個組數(shù)（Component），這些組數(shù)線性加成組成GMM 的概率密度函數(shù)公式如下：

2.3 GMM-SMOTE算法步驟

實驗前，先對實驗數(shù)據(jù)進行預處理。采用10 折交叉驗證［16］將不平衡數(shù)據(jù)樣本集X劃分為訓練樣本集S和測試樣本集T。將訓練集S分成二分類問題：多數(shù)類樣本集Smax，所含樣本數(shù)為Nmax；少數(shù)類樣本集Smin，所含樣本數(shù)為Nmin。GMM-SMOTE 算法流程如圖2所示。

（1）采用GMM 聚類對少數(shù)類樣本集Smin中的冗余樣本進行刪除。

對樣本集Smin進行GMM 聚類，聚簇中心點為Ck，定義與中心點存在重疊的樣本點為冗余樣本并將其刪除。

其中，設定冗余樣本個數(shù)刪除的閾值為：

式（4）中，meanDist表示其聚簇中心點Ck到其樣本集Smin中其他樣本點xi的平均距離，其表達式為：

Fig.2 Synthetic new samples based on GMM-SMOTE algorithm圖2 基于GMM-SMOTE算法合成新樣本

式（5）中，Dist(xi，Ck)為聚簇中心點Ck到其他樣本點xi的距離。

輸入：訓練樣本集S，GMM 聚類的組數(shù)k，冗余樣本個數(shù)n；

輸出：已被刪除冗余樣本后的少數(shù)類樣本集Snew。

詳細流程如下：①利用肘部法則確定最佳組數(shù)k，得到簇數(shù)k1、k2、k3......；②對于每個簇集，利用公式（4）和（5）刪除冗余樣本。

（2）對少數(shù)類進行過采樣，合成少數(shù)類樣本集Snewmin。

輸入：樣本集Snew

輸出：平衡后的新樣本集Xnew

流程：①利用公式（1）對完成步驟（1）后的樣本集采用SMOTE 過采樣算法生成Snewmin；②合并Smax與Snewmin形成新樣本集Xnew。

所需過采樣數(shù)量為：

3 實驗結(jié)果與分析

3.1 數(shù)據(jù)集介紹

實驗采用來自UCI 數(shù)據(jù)庫中的6 組標準公開數(shù)據(jù)集，分別為Balancescale、CMC、Vehicle、G-lass、Haberman、Aggregation，且通過10折交叉驗證（10-fold cross validation）估計算法精度。實驗前需對原數(shù)據(jù)集進行處理，將多類別數(shù)據(jù)集分成二分類數(shù)據(jù)集。本文共采用8 組不同平衡度的數(shù)據(jù)集，如表1 所示。Balancescale0 數(shù)據(jù)集將類別3、1 合并為多數(shù)類，類別2 為少數(shù)類；Balancescale1 數(shù)據(jù)集將類別2、3 合并為多數(shù)類，類別1 為少數(shù)類；CMC0 數(shù)據(jù)集將類別1、3 合并為多數(shù)類，類別2 為少數(shù)類；CMC1 數(shù)據(jù)集將類別1、2 合并為多數(shù)類，類別3 為少數(shù)類；Vehicle 數(shù)據(jù)集將類別1、2、3合并為多數(shù)類，類別4為少數(shù)類；Glass 數(shù)據(jù)集將類別1、3、4、5、6 合并為多數(shù)類，類別2 為少數(shù)類；Haberman 為二分類數(shù)據(jù)集；Aggregation 數(shù)據(jù)集將類別2、3、4、6、7 合并為多數(shù)類，其余為少數(shù)類，具體如表1所示。

Table 1 Eight groups of two-category data表1 八組二分類數(shù)據(jù)

3.2 評價指標

評價分類器性能常用指標有準確率（accuracy）、精確率（precision）、召回率（recall）、F1-score、AUC（area under ROC curve）和ROC 等［17］。對于不平衡二分類問題，準確率是無法衡量分類器性能優(yōu)劣的。由于不平衡二分類的復雜性，本文選擇幾何均數(shù)G-mean 和AUC 值作為評價分類器優(yōu)劣的指標［18］，采用混淆矩陣來表示分類結(jié)果（本文假設少數(shù)類為正例，多數(shù)類為負例）［19］，如表2所示。

混淆矩陣僅僅統(tǒng)計了分類結(jié)果個數(shù)，難以衡量模型優(yōu)劣。

基于混淆矩陣表2，可以得到召回率（recall）、特異度（specificity）、G-mean 等指標。

Table 2 Confusion matrix表2 混淆矩陣

少數(shù)類召回率：

多數(shù)類召回率：

本文選擇的幾何均數(shù)G-mean：

AUC 值是基于ROC 曲線得到的。以兩個分類器為例，若其中一條ROC 曲線完全包住另一條，則前者分類效果優(yōu)于后者；若二者相交，則無法通過ROC 曲線直接得出。因而，引入AUC 值，即利用ROC 曲線下的面積來進行比較［20］。

3.3 結(jié)果分析

為了橫向比較GMM-SMOTE 算法的性能優(yōu)劣，選擇以隨機森林（random forests）為分類器進行3 組實驗：①隨機森林算法對未進行平衡處理的數(shù)據(jù)集進行分類；②先利用SMOTE 過采樣算法對原始不平衡數(shù)據(jù)集進行處理，變?yōu)槠胶鈹?shù)據(jù)集后，再利用隨機森林算法進行分類；③先利用GMM 聚類算法對少數(shù)類數(shù)據(jù)集進行聚類，刪除冗余樣本點之后，再通過SMOTE 過采樣算法以不同聚簇為單位生成人工樣本點，使數(shù)據(jù)集平衡，最后利用隨機森林算法進行分類。

表3 為8 組不同數(shù)據(jù)集在RF、SMOTE+RF 以及GMMSMOTE+RF 3種算法下的性能表現(xiàn)。

Table 3 Comparison result of RF，SMOTE+RF and the algorithm proposed表3 本文算法與RF、SMOTE+RF比較結(jié)果

分析表3可知：

（1）在8組數(shù)據(jù)集中，GMM-SMOTE+RF模型的Gmean 值有6 組數(shù)值（已加粗標記）高于或等于RF 和SMOTE+RF 兩種模型，AUC 值均優(yōu)于其他兩種模型。相比于傳統(tǒng)模型SMOTE+RF，本文模型的AUC 值平均提高了6.09%，有較好表現(xiàn)。

（2）Aggregation數(shù)據(jù)集中，GMM-SMOTE算法的Gmean 值持平于SMOTE 算法，但AUC 值相對較高。GMMSMOTE 算法在Balancescale1 和CMC0 兩個數(shù)據(jù)集的Gmean 值略低于SMOTE+RF。另外，Balancescale1 和Aggregation 兩個數(shù)據(jù)集基于RF 模型的G-mean 值為0，且Aggregation 數(shù)據(jù)集的AUC 值為1。對于高不平衡數(shù)據(jù)集，RF 算法不穩(wěn)定，容易造成過擬合問題，分類效果差。

4 結(jié)語

傳統(tǒng)的分類算法更多考慮的是類間不平衡，而對于類內(nèi)不平衡的研究較少。本文提出一種基于GMM 聚類的過采樣算法，能較好地處理類內(nèi)不平衡問題。利用GMM 算法先聚類后插值，與傳統(tǒng)SMOTE 算法相比插值更具有針對性，避免了新生成偏頗的數(shù)據(jù)而造成的過擬合問題。在保證少數(shù)類樣本空間結(jié)構(gòu)不改變的情況下，刪除與聚類中心點重疊的冗余樣本，極大保留了少數(shù)類樣本的關鍵信息。采用UCI 標準數(shù)據(jù)庫中的6 組數(shù)據(jù)集基于隨機森林分類器進行實驗對比，結(jié)果表明，本文GMM-SMOTE 算法比傳統(tǒng)算法表現(xiàn)更優(yōu)。

本文基于公開數(shù)據(jù)集驗證了GMM-SMOTE 算法能提升分類效果。但該算法還有一些不足，如冗余樣本的刪除需要不斷去調(diào)試刪除的個數(shù)，具有一定的隨機性。因此，本文算法仍需進一步改進。