面向不平衡數據集的改進SMOTE算法

董永峰，董彥琦，張亞娟

（1.河北工業大學 人工智能與數據科學學院，天津 300401；2.河北省大數據計算重點實驗室，天津 300401）

0 引言

不平衡數據是指數據集中某一類別的樣本數量明顯少于其他類別的樣本數量，其中樣本數量較少的一類稱為少數類，樣本數量較多的一類稱為多數類。在實際應用中，不平衡數據是經常存在的，特別是在網絡安全、醫療診斷、客戶流失預測等領域[1]。以隨機森林為代表的傳統分類器在處理不平衡數據分類問題時，分類結果往往會傾向于多數類，而忽略少數類，從而導致算法性能大幅下降[2]。為了提高分類器對不平衡數據的分類性能，學者們主要從算法和數據層面進行了改進。算法層面的改進主要是結合不平衡數據集的內在特征，在現有分類算法基礎上進行改進或設計新的分類算法，以適應不平衡數據進行分類的需要，主要包括代價敏感學習[3]、單類學習[4]和特征選擇[5]等方法。數據層面的改進主要是結合重采樣技術，使不平衡數據集在訓練之前就趨于平衡，再利用分類器進行訓練，重采樣技術主要包含欠采樣[6]和過采樣[7]兩種方法。以上方法中使用最為廣泛的是文獻[8]中提出的SMOTE算法，該算法在少數類樣本及其近鄰樣本之間合成新樣本，但SMOTE算法沒有對少數類樣本進行區別性的選擇，因此在合成新樣本時存在盲目性與邊緣化等問題，眾多學者對其進行了改進。

文獻[9]中提出了Borderline-SMOTE算法，該算法只對決策邊界附近的少數類樣本進行過采樣，從而改善了SMOTE的盲目性，但會丟失其他少數類樣本所包含的信息。文獻[10]中提出了ADASYN算法，該算法規定每個少數類樣本合成新樣本的個數與模型學習該樣本的困難程度成正比，但學習難度越大的樣本是噪聲的可能性也越大，在其周圍生成新樣本會進一步放大數據集中的噪聲。文獻[11]中提出了ISMOTE算法，該算法在以少數類樣本為中心，以該樣本到其最近鄰樣本之間的距離為半徑的n維球體內進行過采樣，從而消除了少數類樣本分布的限制，但在插值的過程中容易造成新樣本與多數類樣本的重疊，進一步加大分類難度。文獻[12]中提出了KM-SMOTE算法，該算法對數據集中的少數類樣本進行聚類，在簇心及對應簇樣本之間生成新樣本，但在插值的過程中會使新樣本集中分布于簇心周圍，導致樣本之間的重疊。為了克服SMOTE算法及以上改進算法的不足，論文基于聚類劃分和重心牽引的思想提出了一種改進算法BSMOTE，該算法有效改善了SMOTE算法生成新樣本時存在的盲目性和邊緣化的問題，從而保證了新樣本的有效性，同時由于新樣本的加入使不平衡數據集在訓練之前就趨于平衡，再利用隨機森林進行訓練，從而提升了傳統分類器在不平衡數據集上的分類性能。

1 SMOTE算法

合成少數類過采樣技術（Synthetic Minority Over-sampling Technique，SMOTE）是基于傳統隨機過采樣的一種改進算法，該算法避免了數據集內少數類樣本大量重復出現，有效降低了過擬合問題出現的機率。SMOTE算法流程如下。

輸入：不平衡數據集D，近鄰數K，采樣率N。

輸出：平衡數據集Dnew。

1）篩選出原始數據集D中的全部少數類樣本，構成少數類樣本集Dmin，其余樣本構成多數類樣本集Dmaj。

2）對于Dmin中少數類樣本xi，計算它到Dmin中所有樣本的距離，得到其K近鄰，從其K近鄰中任取一個樣本xj，xi與xj之間的距離d(xi,xj)計算公式如式（1）所示：

式中：xi=(xi1,xi2,…,xin)，xj=(xj1,xj2,…,xjn)表示2個n維屬性的數據樣本。

3）計算樣本xi與xj各個對應屬性上的屬性值之差，將差值乘以區間（0，1）內的一個隨機數，再加上樣本xi各個對應的屬性值，即可生成一個新的少數類樣本xnew，具體計算公式如式（2）所示：

式中：rand（0，1）表示區間（0，1）上的一個隨機數。

4）循環執行步驟2）～3），算法終止條件為達到預先設置的采樣倍率N，將生成的全部少數類樣本加入原始數據集D中，得到平衡數據集Dnew。

2 SMOTE的改進算法：BSMOTE

2.1 BSMOTE算法原理

SMOTE算法認為在距離相近的少數類樣本之間生成的新樣本仍為少數類，為了確保新樣本的有效性，未改進的SMOTE算法在插值過程中需要找到少數類樣本的K個最近鄰，并在其與隨機的一個近鄰樣本之間生成新樣本，但該算法在插值過程中未考慮少數類樣本的分布，具有一定的盲目性。SMOTE算法生成新樣本的示意圖如圖1a）所示，圖中圓形表示多數類樣本，空心五角星表示少數類樣本，實心五角星表示新合成的少數類樣本。假設采用SMOTE算法對少數類樣本A進行過采樣，該算法首先在樣本A的5個近鄰少數類樣本中隨機選擇了樣本B，然后在樣本A和樣本B之間線性插值生成新的少數類樣本A1，但從圖中可知新樣本A1位于多數類樣本較多的區域，因此該樣本是一個噪聲樣本，并不會有助于分類算法進行訓練。

同時，SMOTE算法還存在樣本分布邊緣化的問題，如果一個少數類樣本處在多數類與少數類樣本的決策邊界，則由此樣本和近鄰樣本生成的新樣本也將處在這個邊界，且越來越邊緣化。如圖1a）所示，少數類樣本B和少數類樣本C均處在多數類與少數類樣本的決策邊界，采用SMOTE算法在2個樣本之間生成的新樣本C1也處在這個邊界，從而將邊界模糊化，加大了分類算法進行分類的難度。

圖1 a）SMOTE算法生成新樣本的示意圖；b）BSMOTE算法生成新樣本的示意圖Fig.1 a)Schematic diagram of SMOTE algorithm generating new samples;b)Schematic diagram of BSMOTE algorithm generating new samples

針對以上2個問題，論文提出了改進算法BSMOTE，該算法首先采用K-means聚類算法對少數類樣本進行聚類產生k個簇，以此確定少數類樣本的分布情況，同時基于距離的聚類劃分使得簇中樣本的相似性較高，故該算法省去了SMOTE算法求解少數類K近鄰的步驟，直接在各個簇中選擇少數類樣本以生成新樣本。然后在聚類產生的各個簇Ci(i=1,2,…,k)中隨機選取3個樣本點構造三角形，計算其重心樣本數據，在三角形重心與頂點之間隨機生成新的少數類樣本，新樣本會向所在三角形的重心位置靠攏并遠離決策邊界，從而使新樣本的生成過程具有一定的方向性。最后將不斷生成的新樣本加入到原始數據集D中以降低不平衡率，直至數據集中的少數類樣本數量不小于多數類樣本數量時終止算法，得到平衡數據集Dnew。

BSMOTE算法生成新樣本的示意圖如圖1b）所示，圖中圓形表示多數類樣本，空心五角星表示少數類樣本，實心五角星表示新合成的少數類樣本，橢圓虛線表示BSMOTE算法采用K-means對少數類樣本聚類得到的2個簇，生成新樣本僅在各個簇中進行，由此避免了SMOTE算法生成新樣本的盲目性問題。圖中的實心點表示少數類樣本B、C、D所構成三角形的重心，BSMOTE算法在三角形重心與頂點之間生成新的少數類樣本，因此生成的新樣本會向重心位置靠攏，從而遠離決策邊界，有效克服了SMOTE算法生成新樣本的邊緣化問題。

圖2 BSMOTE算法流程圖Fig.2 Flow chart of BSMOTE algorithm

2.2 BSMOTE算法設計

在樣本類別不平衡問題中，通常將數量較少的少數類樣本視為正類樣本，數量占優的多數類樣本視為負類樣本。BSMOTE算法流程圖如圖2所示，算法流程如下。

輸入：不平衡數據集D，聚類個數k。

輸出：平衡數據集Dnew。

1）篩選出原始數據集D中的正類樣本，構成正類樣本集Dmin，其余樣本構成負類樣本集Dmaj。

2）在正類樣本集Dmin中隨機選取k個樣本，作為首次聚類的中心點。

3）采用公式（1）計算其余各樣本到每個聚類中心點的距離d(xi,xj)，并將該樣本劃分到與之最近的聚類中心所在的簇Ci(i=1,2,…,k)中。

4）重新計算各簇的聚類中心，重復Step2調整所有樣本的劃分，聚類中心更新迭代公式如式（3）所示：

式中：mi為簇Ci的聚類中心；|Ci|為簇Ci的樣本數量；xp=(xp1,xp2,…,xpn)表示簇Ci內n維屬性的數據樣本。

5）計算正類樣本集Dmin中全部樣本及其所屬簇的聚類中心之間距離的平方和，即誤差平方和SSE，計算公式如式（4）所示：

6）迭代執行步驟3）～5），直到聚類劃分不再發生變化或者SSE值收斂，至此聚類結束得到k個簇Ci(i=1,2,…,k)。

7）在任意一簇Cj中隨機選取的3個正類樣本xr，xs，xt構造三角形，計算其重心樣本向量xB，重心樣本xB計算公式如式（5）所示：

式中：xB表示由xj(j=r,s,t)所構成三角形的n維重心向量。

8）在三角形重心xB與頂點xj(j=r,s,t)之間隨機生成一個新的正類樣本xnew，將其加入正類樣本集Dmin，生成的新樣本xnew計算公式如式（6）所示：

式中：xnew表示由三角形頂點xj(j=r,s,t)及重心xB生成的n維新向量。

9）在k個簇Ci(i=1,2,…,k)中循環執行步驟7）～8），算法終止條件為正類樣本個數 |Dmin|不小于負類樣本個數 |Dmaj|。

10）合并正類樣本集Dmin與負類樣本集Dmaj，得到平衡數據集Dnew。

3 實驗設計與結果分析

3.1 實驗數據

論文采用KEEL數據庫的7個不平衡數據集進行實驗，分別為new-thyroid2，ecoli1，ecoli2，ecoli3，glass0，wisconsin和vehicle0。表1中描述了數據集的基本特征，其中包括總樣本個數、屬性個數、負類樣本個數、正類樣本個數和不平衡比率。

3.2 實驗設計

論文在Window 10（64位）操作系統，Intel Core i7-7700HQ CPU@2.8 GHz，8GB RBM的環境下使用Python進行實驗。為了驗證BSMOTE算法的有效性，對比了原始數據集和經過SMOTE算法、ADASYN算法、Borderline-SMOTE（簡記為BL-SMOTE）算法、ISMOTE算法以及KM-SMOTE算法處理后的數據集對分類器分類性能的影響。分類器采用傳統機器學習算法隨機森林（Random Forest，RF），該算法是一個由決策樹分類器集合所構成的集成學習模型，有著良好的泛化性和魯棒性。RF首先采用Bootstrap有放回抽樣的方法從數據集D中隨機采樣，生成s個子數據集Di(i=1,2,…,s)；然后基于每個Di訓練決策樹模型hi(x)，在樹生成的過程中，隨機從M個屬性中選擇m個屬性參與節點分裂（m＜M且m值恒定）；而后計算每個屬性值的基尼系數，選擇基尼系數最小的屬性作為分裂節點進行分裂，由此生成s棵決策樹；最后采用多數表決機制集成s棵決策樹的預測結果得到待測樣本x的預測標簽。在本實驗中，SMOTE、ADASYN和BL-SMOTE中正類樣本的近鄰個數K為5，KM-SMOTE和BSMOTE中正類樣本的聚類個數k為5，森林中決策樹的數量s為100，每棵決策樹選用的屬性數量m為log2M+1。

表1 數據集特征Tab.1 Data set features

3.3 評價指標

對于不平衡數據集的二分類問題，傳統的性能評價指標準確率、靈敏度、特異度和查準率并不能很好地反映出一個分類算法的性能，論文將選取不平衡數據分類的常用評價指標G-mean值、F-measure值和ROC曲線的量化標準AUC值來反映模型性能的優劣，為方便指標描述，首先建立混淆矩陣如表2所示。

其中，TP（True Positive）表示模型正確分類的正類樣本數量，FN（False Negative）表示模型錯誤分類的正類樣本數量，FP（False Positive）表示模型錯誤分類的負類樣本數量，TN（True Negative）表示模型正確分類的負類樣本數量。

幾何均值（G-mean）綜合反映了算法模型對正、負兩類樣本的分類性能，計算公式如式（7）所示：

表2 二分類問題混淆矩陣Tab.2 Confusion matrix of binary classification problem

只有當正、負兩類樣本的分類精度都處于較高的水準時，G-mean才會較大，該指標的數值越大，模型的總體分類效果越好。

正類檢驗值（F-measure）綜合反映了算法模型對少數類樣本的分類性能，計算公式如式（8）所示：

該指標的數值越大，模型對少數類樣本的分類效果越好。

受試者工作特征曲線（Receiver Operating Characteristic，ROC）上點的坐標通過模型在獲取分類結果時的概率閾值進行計算，不同的概率閾值對應不同的坐標點，其中點的橫坐標表示負類樣本分類錯誤的概率（False Positive Rate，FPR），點的縱坐標表示正類樣本分類正確的概率（True Positive Rate，TPR），FPR和TPR計算公式分別如公式（9）～（10）所示：

ROC曲線下面積的大小稱為AUC（Area Under the Curve）值，是通過ROC曲線來評判模型分類效果的量化標準，當AUC值等于0.5時表示該算法的分類性能等同于完全隨機分類，該指標的數值越大，模型的分類效果越好。

3.4 結果分析

實驗結果取100次運行結果的平均值，無重采樣處理的隨機森林和基于6種重采樣算法的隨機森林在不同數據集上的G-mean值、F-measure值和AUC值如表3～5所示，表格中加粗數據為各個性能評價指標在每個數據集上取得的最優值，G-mean值、F-measure值和AUC值的對比圖如圖3～5所示。

表3 不同數據集上的G-mean值Tab.3 G-mean values on different data sets

表4 不同數據集上的F-measure值Tab.4 F-measure values on different data sets

表5 不同數據集上的AUC值Tab.5 AUC values on different data sets

從表3～表5和圖3～圖5中可以看出：

1）在大部分不平衡數據集上，6種重采樣算法均有效提升了RF的分類性能，不過在glass0數據集上，基于ADASYN算法和KM-SMOTE算法的RF表現不是很穩定，F-measure值和AUC值比未經過重采樣算法處理的RF所得結果更低。

2）在new-thyroid2、ecoli1、ecoli3、glass0和vehicle0數據集上，BSMOTE算法與其他重采樣算法相比具有更好的不平衡數據處理能力，各項指標值均達到最優，最大程度上提升了RF在不平衡數據上的分類性能。

3）在ecoli2數據集上，BSMOTE算法的G-mean值和AUC值達到最優，F-measure值比KM-SMOTE算法略低0.43%，總體上差距不大。同時，BSMOTE算法在該數據集上對RF的提升程度最大，G-mean值、F-measure值和AUC值分別提高了20.61%、22.36%和24.34%。

4）在wisconsin數據集上，BSMOTE算法的AUC值比ISMOTE算法低0.98%，不過G-mean值和F-measure值均達到最優，保證了正類樣本的分類精度。

5）在全部數據集上，基于BSMOTE算法的RF的分類性能均優于傳統RF，G-mean值、F-measure值和AUC值平均提升了11.71%、11.69%和12.81%，證明了BSMOTE算法對RF進行優化的有效性。

圖3 G-mean值的對比圖Fig.3 Comparison graph of G-mean values

圖4 F-measure值的對比圖Fig.4 Comparison graph of F-measure values

圖5 AUC值的對比圖Fig.5 Comparison graph of AUC values

通過上述分析可以看出，基于SMOTE的改進算法BSMOTE有效解決了不平衡數據分類的問題，同時改善了SMOTE算法合成新樣本時的盲目性與邊緣化，提升了傳統分類器隨機森林在不平衡數據集上分類性能，從而證明了BSMOTE是一種有效的改進算法。

4 結論

論文針對SMOTE算法生成新樣本時存在的盲目性和邊緣化的問題，提出了一種改進算法BSMOTE，該算法通過聚類劃分和重心牽引的思想保證了新樣本的有效性，同時由于新樣本的加入使不平衡數據集在訓練之前就趨于平衡，再利用隨機森林分類器進行訓練，從而有效提升了分類器對正類樣本的分類精度。最后通過與5種重采樣算法在7個不平衡數據集上進行對比實驗，驗證了BSMOTE算法在解決不平衡數據分類問題中的優勢。