面向不平衡數(shù)據(jù)基于高斯混合聚類的SMOTE改進(jìn)算法

陶葉輝，趙壽為

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

0 引言

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

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

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

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

1 SMOTE過(guò)采樣

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

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

其中，隨機(jī)插值公式為：

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

2 肘部法則及GMM-SMOTE過(guò)采樣算法

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

2.1 肘部法則

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

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

2.2 高斯混合模型

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

2.3 GMM-SMOTE算法步驟

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

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

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

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

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

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

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

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

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

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

（2）對(duì)少數(shù)類進(jìn)行過(guò)采樣，合成少數(shù)類樣本集Snewmin。

輸入：樣本集Snew

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

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

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

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

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

實(shí)驗(yàn)采用來(lái)自UCI 數(shù)據(jù)庫(kù)中的6 組標(biāo)準(zhǔn)公開(kāi)數(shù)據(jù)集，分別為Balancescale、CMC、Vehicle、G-lass、Haberman、Aggregation，且通過(guò)10折交叉驗(yàn)證（10-fold cross validation）估計(jì)算法精度。實(shí)驗(yàn)前需對(duì)原數(shù)據(jù)集進(jìn)行處理，將多類別數(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 評(píng)價(jià)指標(biāo)

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

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

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

Table 2 Confusion matrix表2 混淆矩陣

少數(shù)類召回率：

多數(shù)類召回率：

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

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

3.3 結(jié)果分析

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

表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ù)值（已加粗標(biāo)記）高于或等于RF 和SMOTE+RF 兩種模型，AUC 值均優(yōu)于其他兩種模型。相比于傳統(tǒng)模型SMOTE+RF，本文模型的AUC 值平均提高了6.09%，有較好表現(xiàn)。

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

4 結(jié)語(yǔ)

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

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