優化合成樣本分布的加權過采樣方法

張忠林，趙喆梅，馬海云

（1.蘭州交通大學電子與信息工程學院，蘭州 730079；2.天水師范學院電子信息與電氣工程學院，甘肅 天水 741001）

0 引言

隨著大數據時代的到來和數據采集系統的不斷完善，不平衡數據處理已成為學術界和應用領域的研究熱點。傳統的分類算法對不平衡數據進行分類使得類分布向多數類嚴重傾斜，容易產生錯誤的分類結果，這會誤導人們做出錯誤的判斷從而造成不可挽回的損失。因此，最大限度提高少數類樣本分類精度是很多學者的研究目標。在分類任務中處理數據不平衡問題的方法可分為以下兩個層面：算法層面和數據層面。算法層面的方法主要是從根本上改進現有的分類算法，包括集成學習[1]、代價敏感等[2,3]。集成分類器的性能往往優于單個分類器的性能，常見的集成方法有提升（Boosting）[4]和袋裝（Bagging）[5]，隨機森林（Random Forests）[6]是袋裝的一個變種。代價敏感實質上是為錯分到多數類的少數類賦予更大的錯分代價[7]，降低少數類的誤分率。數據層面的方法指通過改變樣本數量來處理數據不平衡問題，有兩種方法：合成新的少數類樣本的過采樣[8]和刪除部分多數類樣本的欠采樣[9]。相比過采樣，欠采樣在刪除樣本的過程中可能會丟失一部分關鍵信息，降低了分類器的泛化性能。

近年來研究者更多地關注過采樣方法。過采樣方法中最經典的方法是Chawla 等（2002）[10]提出的SMOTE 算法（Synthetic Minority Oversampling Technique），該算法通過在兩個已有少數類樣本之間插值來生成新的少數類樣本。SMOTE算法雖然提高了少數類的預測精度，但在合成新樣本時沒有區別地選擇每個樣本，當少數類樣本個數較少并含有較多噪聲信息時，SMOTE算法會受近鄰隨機性干擾，易合成冗余樣本和噪聲樣本。針對SMOTE 算法的局限性，文獻[11]提出了Borderline-SMOTE 算法，此算法應用k近鄰算法判斷少數類樣本位置，認為少數類邊界處的樣本含有更重要的信息，只在少數類邊界處應用SMOTE 合成新的樣本。He 等（2008）[12]提出一種基于少數類樣本分布的自適應過采樣算法（Adaptive Synthetic Sampling Method，ADASYN），該算法根據少數類樣本的學習復雜程度來確定每個少數類樣本需合成新樣本的個數，能有效提升分類器的分類性能，但該方法易受離群點影響而生成代表性不足的少數類樣本。Douzas 等（2018）[13]提出基于K-means 聚類的過采樣方法K-means SMOTE，該算法可以有效改善類不平衡問題，但其采樣結果受K-means 聚類效果的影響，易放大少數類樣本的誤差，降低分類器分類性能。

上述過采樣方法基于不同的側重點來處理不平衡數據，但這些方法在選擇種子樣本時仍存在一定的不足。基于此，本文提出了一種根據權重選擇種子樣本，優化生成樣本分布的方法，使合成的新樣本更有類別代表性，有利于分類器識別少數類樣本邊界。

1 理論基礎

1.1 SMOTE算法

2002 年Chawla 等提出了SMOTE 算法[10]，該算法是處理不平衡數據問題最經典的過采樣方法之一，避免了隨機過采樣存在的過擬合風險。這項技術產生了人工樣本，而不再僅僅是復制已有的樣本。如下頁圖1所示，這是通過線性插值一個隨機選擇的少數類樣本和它鄰近的少數類樣本來實現的。SMOTE算法執行三個步驟來生成新的樣本。首先，選擇一個隨機的少數類樣本a；然后，在其k個鄰近的少數類中，隨機選擇樣本b；最后，通過對兩個樣本進行插值，生成一個新的樣本x=a+w(b-a),其中，w為在區間[0,1]中隨機取的權重。

圖1 SMOTE線性插值一個隨機選擇的少數類樣本及其k=6 的最近鄰

1.2 WKMeans算法

聚類是將一組對象劃分為多個類的過程，使同一聚類中的對象比不同聚類中的對象更相似。K-means 算法[14]由于其原理比較簡單、收斂速度快、容易實現等優點被廣泛應用。但K-means算法由于對所有的特征都一視同仁，因此在聚類過程中無法區別不同特征的重要性。因此Huang 等（2005）[15]提出了一種改進的K-means 算法，即WKMeans 算法，它可以根據特征屬性在聚類中的重要性對特征自動加權，該方法基于迭代K-means算法過程中的當前劃分，根據聚類內聚類的方差計算每個變量的新權值，新權值用于確定下一次迭代中對象的聚類成員關系。在算法收斂時找到最優權值，權值越大表示該特征對聚類結果越重要。WKMeans算法的目標函數為：

其中，U是簇分配矩陣；Z是簇中心矩陣；W是權重矩陣；ui,l表示將樣本i分配到簇l中；為權重參數，β控制權重W的分布；xi,j表示各目標點；zl,j表示各聚類中心；k為簇數；n為各聚類簇；d是數據集維數；d(xi,j,zl,j)為目標點到聚類中心的距離。

其中，Dj表示所有樣本點在第j個特征屬性上的距離和，d(xi,j,zl,j)=(xi,j-zl,j)2。

各個參數服從的約束條件為：

1.3 隨機森林算法

隨機森林算法是一種基于決策樹的集成算法，通過添加基本模型的預測來做出決定。訓練樣本通過自助抽樣獲得，且每個基本模型都是一個簡單的決策樹。算法步驟為：首先，對樣本集自助抽樣生成訓練集；然后，在生成的訓練集上隨機選擇部分特征構建決策樹；最后，采用投票的方式得到模型的輸出：

其中，x為數據集；C為類別數；T為決策樹數量；ht(x)是決策樹t的模型；I(·)為指示函數，參數為真時取值為1，否則為0。

隨機森林模型整合了每棵樹的預測，從而降低了模型的誤差。此外，因為該模型具有泛化能力較強、能夠容忍少量的異常值和缺失值、訓練速度快等優點，因此在機器學習中被廣泛使用。圖2為隨機森林模型示意圖。

圖2 隨機森林模型

2 基于WKSMOTE和隨機森林的分類模型

2.1 WKSMOTE方法思想

針對原有過采樣方法在合成新樣本時沒有區別地選擇每個樣本的問題，本文提出了根據權重選擇種子樣本，優化合成樣本分布的加權過采樣方法。應用特征加權的聚類算法WKMeans對原數據集進行預處理。對少數類樣本的劃分，以少數類樣本的近鄰含有多數類樣本的個數Δ為閾值標準，將少數類樣本劃分為兩類：安全樣本和邊界樣本。對邊界樣本賦予較大的權重，安全樣本權重相對較小，根據樣本權重計算邊界樣本和安全樣本分別需要合成的樣本個數。根據安全樣本和邊界樣本到P個多數類樣本間的歐氏距離賦予少數類樣本中每個樣本權重，距離越小，則樣本越靠近決策邊界，權重越大，合成越多新樣本，從而得到每個少數類樣本需要合成新樣本的個數。應用SMOTE算法依照每個少數類樣本需要合成新樣本個數對少數類樣本進行過采樣。最后將采樣過的均衡數據集在隨機森林分類器中進行訓練。

2.2 WKSMOTE方法描述

設不平衡數據集為D，訓練集為T，測試集為S，T中少數類樣本個數為Tmin，多數類樣本個數為Tmaj。

WKSMOTE方法的步驟如下：

步驟1：將不平衡數據集D劃分為訓練集T和測試集S。

步驟2：應用WKMeans算法對T中樣本進行預處理。

步驟3：計算訓練集T需要合成的樣本數n_to_sample=Tmaj-Tmin。

步驟4：以少數類樣本的k 近鄰含有多數類樣本的個數Δ為閾值標準，將少數類樣本劃分為安全樣本T_safe和邊界樣本T_border。

對于訓練集Tsample={(xi,yi)|i=1,2,…,p,yi?{0,1}}，xi是特征為i的樣本，yi是類標簽。集合Tmin={(xmin,i,yi)|i=1,2,…,p,yi=0}是Tsample中的少數類樣本，集合Tmaj={(xmaj,i,yi)|i=1,2,…,p,yi=1}是Tsample中的多數類樣本，對于任意一點P?Tmin，若滿足sum(y=1)≤sum(y=0)，則稱P點為邊界樣本點；若滿足sum(y=1)>sum(y=0)，則稱P點為安全樣本點。

步驟5：統計安全樣本和邊界樣本個數nT_safe、nT_border，分別取其倒數為bsafe、bborder，則式（5）為安全樣本區域權重，式（6）為邊界樣本區域權重。

步驟6：計算T_border和T_safe分別需要合成的樣本個數n_T_safe（式（7））和n_T_border（式（8））。

步驟7：計算T_border和T_safe中每個樣本到P個最近的多數類樣本的歐氏距離，式（9）為樣本i和樣本j間的歐氏距離，其中，C為特征數。

步驟8：計算步驟7 中P個距離之和Di，設權重為1Di。

步驟9：分別計算T_border和T_safe中所有樣本權重之和BNDi和SNDi。

步驟10：根據式（10）和式（11）計算T_border和T_safe中每個樣本需要合成的樣本個數NBe和NSe。

步驟11：對于Tmin中的每個樣本xi, 應用SMOTE 算法按照每個樣本需要合成新的樣本個數合成新樣本Tnew。

步驟12：將合成的新樣本Tnew加入訓練集T中生成新的數據集Dnew。

2.3 模型構建

本文利用WKSMOTE方法合成新樣本，并將其加入原訓練集中來改善數據集不平衡問題，使用隨機森林分類器進行學習，建立WKSMOTE-隨機森林模型。整體流程如圖3所示。

圖3 整體算法流程圖

具體過程如下：（1）輸入數據集，應用WKSMOTE方法合成新的少數類樣本，并將其加入數據集中，構成新的數據集。（2）利用隨機森林分類器對數據集進行訓練，并用網格搜索方法進行參數尋優，得到分類模型。（3）用測試集進行測試，驗證模型分類性能。

在用SMOTE 方法合成新樣本時，每個少數類樣本生成的新樣本個數相同，導致合成了一些類別區分不大的樣本，進而影響分類模型訓練結果。由于每個樣本區分類別的價值不一樣，決策邊界處的樣本更有利于正確區分類別，因此，本文通過建立WKSMOTE-隨機森林模型，改進SMOTE方法，在少數類的類邊界處合成更多新樣本，強化決策邊界，提高少數類樣本的分類性能。隨機森林作為經典集成分類算法，將多個弱分類器分類結果投票選擇組成一個強分類器，優于單分類做出的預測。在隨機森林分類過程中采用網格搜索方法選擇最優參數，提高預測準確性。

2.4 WKSMOTE方法時間復雜度分析

WKSMOTE 方法時間復雜度主要由步驟2、步驟4、步驟7、步驟11決定。在步驟2中，WKMeans算法和KMeans時間復雜度相似，約減后都為O(n)。步驟4中將樣本劃分為邊界樣本和安全樣本是基于KNN 算法進行的，時間復雜度為O(dn2),d是樣本特征數。步驟7計算每個正類樣本與每個負類樣本間的歐氏距離并求出p個距離最小值時間復雜度為O(pTminTmaj) ，其中，p是常數且Tmin

3 實例分析

3.1 實驗數據集

為了評價本文方法的有效性，選取UCI機器學習庫中的7 個不平衡數據集wave、abalone、car、haberman、yeast、ecoli、spect 和5 個KEEI 機器學習庫中的不平衡數據集balance、pima、phoneme、page-blocks、winequality 進行實驗驗證。對于包含兩個以上類的數據集，將其中樣本數目較少的幾類標記為少數類，并將其他所有樣本合并到多數類中。數據集具體信息如表1 所示。最后一列的IR 值表示數據集不平衡比率，本文選取數據集的不平衡比率在1.17至12.49之間。

表1 數據集信息

3.2 評價指標

在對不平衡數據進行分類時，通常稱數目多的樣本為負樣本，數目少的樣本為正樣本。在非平衡數據學習中，主要目標是提高正樣本的分類性能，同時對負樣本保持合理的性能。分類評估指標將每個觀測值的真實隸屬度與分類器的預測值進行比較，對于分類問題，混淆矩陣通常用來記錄樣本正確或錯誤分類的結果。混淆矩陣如表2所示，其中，TP為正確分類的少數類樣本數；TN為正確分類的多數類樣本數；FP 為誤分為少數類的多數類樣本個數；FN為誤分為多數類的少數類樣本個數。

表2 混淆矩陣

對于均衡數據集，常用準確率（式（12））來評價分類性能，但用它來評價非均衡數據集的分類是不合理的。為此，有學者提出了一些新的不平衡數據分類評價指標，其中最常用的評價指標是F-measure，F-measure同時考慮了準確率（Precision）和召回率（Recall），是一個較全面的評價指標。Kubat 等（1997）[16]提出的G-mean 值主要關注少數類樣本和多數類樣本的召回率情況，只有多數類樣本分類精度和少數類樣本分類精度都比較大時，G-mean 才能比較大。Roc 曲線是以False Positive Rate（FPR）為橫坐標軸、True Positive Rate（TPR）為縱坐標軸的曲線，其下方的面積用數值表示就是AUC（Area Under the Roc Curve）。馬修斯相關系數（Matthews Correlation Coefficient，MCC）考慮了TP、TN、FN、FP，是一個比較綜合的指標，描述了預測分類與實際分類之間的相關系數。

本文采用F-measure、G-mean 和MCC 值來評價不均衡數據集的整體分類性能，采用AUC 值評價分類模型的穩定性。各分類評價指標計算如下：

β為調節Precision 和Recall 相對重要性的系數，當β=1時，即F1-Score。其中：Precision=，Recall=。

其中，specificity=TN/（TN+FP）。

3.3 結果分析

為了驗證WKSMOTE 方法的有效性，本文將其與SMOTE[10]及現有的改進SMOTE 算法Borderline SMOTE[11]、ADASYN[12]、SVMSMOTE 和Kmeans SMOTE[13]在balance、pima、wave、abalone、car、haberman、yeast、ecoli、spect、phoneme、page-blocks、winequality 12 個數據集上進行實驗驗證，上述方法都使用隨機森林分類器。本文為保留類別比例，用分層劃分將數據集按7：3的比例劃分為訓練集和測試集，并使用五折交叉驗證方法得到最終的分類結果。

本文實驗環境為：Inter i7-7500u，4核CPU，主頻2.70GHz，內存4G，操作系統為Windows 10 64 位，仿真環境為Python 3.7。實驗中，k的取值為5；WKMeans 算法中方聚類簇數設為5；最近歐氏距離P取值為5。下頁表3至表5分別列出了6 種方法在8 個不均衡數據集上的F-measure、G-mean 和AUC 值，最后一行為每種方法在8 個數據集上的平均提高率，倒數第二行為每種方法在8個數據集上的平均結果。

表3 6種方法在8個數據集上的F-measure對比

表4 6種方法在8個數據集上的G-mean對比

表5 6種方法在8個數據集上的AUC對比

由表3 至表5 可知，本文提出的WKSMOTE 方法與其他5種方法相比，在處理不均衡數據分類問題上有了一定的提升。與SMOTE方法相比，F-measure值平均提高率為2.04%，G-mean 值平均提高率為2.62%，AUC 值平均提高率為1.01%。WKSMOTE方法相比SMOTE方法，在決策邊界合成更多新樣本，進而在一定程度上更具優勢。與Borderline SMOTE 方法相比，WKSMOTE 方法在yeast 數據集上的F-measure 值和在winequality 數據集上的AUC 值略低，在haberman數據集上的F-measure值和AUC值提升最明顯，分別提高了16.03%和8.93%；在balance 數據集上G-mean 值提高了5.02%。WKSMOTE 方法相比Borderline SMOTE方法在少數類樣本非邊界區域也合成了部分新樣本，使生成樣本分布更合理，實驗效果相對更好。與ADASYN 方法相比，在balance 數據集上，F-measure 值沒有取得最佳結果，在其他兩個指標上效果最佳，尤其在haberman數據集上，AUC值提升了10.36%。WKSMOTE方法相比ADASYN方法，在權重分配上更優化，使合成的樣本更有代表性，提高了分類準確率。與SVMSMOTE 方法相比，WKSMOTE 方法在8 個數據集上的F-measure 值和AUC值相差不大，但均有所提高，在haberman數據集上提高率達到最大，F-measure 值提高了7.2%；AUC 值提高了3.13%。和Borderline SMOTE 方法相似，SVMSMOTE 方法也只是對邊界樣本進行采樣，存在一定的局限性。WKSMOTE方法和Kmeans SMOTE方法在各個數據集上的分類性能比較接近。WKSMOTE方法相比Kmeans SMOTE方法，F-measure 值平均提高率為1.17%，G-mean 值平均提高率為1.08%，AUC 值平均提高率為0.60%。Kmeans SMOTE 方法相比其他4 種方法的平均提高率較低。總體來說，WKSMOTE 方法在大部分數據集上的分類性能優于其他5種方法。印證了本文所提采樣方法在F-measure、G-mean、AUC 這3 個評價指標上分類效果有一定的提升。

由6種方法在8個數據集上MCC值的柱形圖（圖略）可以看出，WKSMOTE方法相比其他5種方法在MCC評價指標上有了一定的提升，尤其在haberman 數據集上提升幅度較大，相比5種方法中效果最好的Kmeans SMOTE 算法，WKSMOTE 方法提高了8.57%。再次印證了本文所提采樣方法的分類效果有一定的提升。

為了進一步衡量本文過采樣方法的性能，與文獻[17]中的NodeStrength-SMOTE 方法進行實驗對比，表6 為兩種采樣方法在C4.5 決策樹上的訓練結果，參數設置同文獻[17]。表6結果顯示：在分類器C4.5決策樹上，WKSMOTE方法在wave 數據集上的G-mean 值和spect 數據集上的F-measure 值低于NodeStrength-SMOTE 方法，其他分類結果均優于對比方法。綜上所述，WKSMOTE方法可以有效提升分類效果，原因在于該方法生成的樣本更具代表性，有利于少數類樣本的正確分類。

表6 兩種方法在4個數據集上的性能對比

下頁表7 為3 種模型在8 個數據集上的F-measure、G-mean、AUC 和MCC 值對比，其中的最大值加下劃線表示。由F-measure、G-mean和MCC值可得，WKSMOTE-RF模型在多個數據集上取得了最優值，說明對于經WKSMOTE方法采樣后的數據，采用隨機森林作為分類器更利于樣本分類。從AUC 值看，在特征維度較高的page-blocks 和winequality 數據集上，WKSMOTE-RF 模型沒有WKSMOTE-SVM 模型穩定，在其他6 個數據集上都是最穩定的，由此可知WKSMOTE-RF模型更適用于低維數據集。

表7 3種模型在8個數據集上的性能對比

3.4 各采樣方法運算復雜度對比

下頁表8 為6 種模型在8 個數據集上的運行時間，其中的最小值加下劃線表示。6 種模型都以隨機森林為分類器，因此其運行時間差異主要在采樣方法上。聚類算法WKMeans 對整體運行時間影響很小，所以影響過采樣方法運行時間是在樣本的分配及合成新樣本環節。本文方法WKSMOTE在對樣本進行劃分之前應用WKMeans算法進行聚類，使得相似的樣本更相近，減少了樣本分配和合成新樣本的時間，進而減少了整體模型運行時間。從表8可知，隨著數據集規模增大，運行時間大幅度增加，在balance、phoneme、ecoli、yeast、page-blocks 和winequality 數據集上，WKSMOTE-RF 模型相比于其他5 種模型運行時間都有所減少，在規模較小的數據集上運行時間和其他5種模型相近，隨著數據規模增加，運行時間減少幅度較大。在abalone和haberman數據集上，WKSMOTE-RF模型運行時間大于Borderline SMOTE-RF，是由于WKSMOTE 方法在安全樣本區域需要合成的樣本遠多于在邊界樣本區域需合成樣本，而Borderline SMOTE 只在邊界合成新樣本，學習規模小于WKSMOTE方法。winequality數據集總的數據量小于phoneme數據集，但除WKSMOTE-RF模型外，其他5 種模型運行時間卻大于phoneme 數據集，是因為winequality 數據集的不平衡度更高，需要合成的新樣本更多，所以花費時間更長。

表8 6種模型在8個數據集上的運行時間對比

4 結束語

針對傳統過采樣方法在生成樣本分布上存在的不足，本文提出了一種優化合成樣本分布的加權過采樣方法，根據權重分配在少數類邊界區域合成較多新樣本，在安全區域也合成一定的新樣本，強化了決策邊界。實驗結果表明，本文提出的WKSMOTE 方法與原有的過采樣方法相比，在同樣采用隨機森林作為分類器對過采樣得到的數據集進行學習的情況下，本文方法對不均衡數據集整體分類效果有一定的提升，有效地解決了數據失衡問題，改善了分類結果偏向多數類樣本的問題。