面向不平衡數據基于高斯混合聚類的SMOTE改進算法

陶葉輝，趙壽為

（上海工程技術大學數理與統計學院，上海 201620）

0 引言

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

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

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

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

1 SMOTE過采樣

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

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

其中，隨機插值公式為：

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

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

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

2.1 肘部法則

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

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

2.2 高斯混合模型

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

2.3 GMM-SMOTE算法步驟

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

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

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

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

式（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 聚類的組數k，冗余樣本個數n；

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

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

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

輸入：樣本集Snew

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

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

所需過采樣數量為：

3 實驗結果與分析

3.1 數據集介紹

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

Table 1 Eight groups of two-category data表1 八組二分類數據

3.2 評價指標

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

混淆矩陣僅僅統計了分類結果個數，難以衡量模型優劣。

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

Table 2 Confusion matrix表2 混淆矩陣

少數類召回率：

多數類召回率：

本文選擇的幾何均數G-mean：

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

3.3 結果分析

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

表3 為8 組不同數據集在RF、SMOTE+RF 以及GMMSMOTE+RF 3種算法下的性能表現。

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

分析表3可知：

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

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

4 結語

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

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