面向不均衡數據集的過抽樣算法

崔 鑫，徐 華，宿 晨

（江南大學物聯網工程學院，江蘇無錫 214122）

（?通信作者電子郵箱1525754926@qq.com）

0 引言

不均衡數據，即各類別樣本數量分布嚴重不平衡的數據。對于均衡數據，傳統分類算法可以取得良好的分類效果，但在實際問題中，如人臉年齡估計、異常檢測、軟件缺陷預測、圖像標注等，需要分類的數據通常是不均衡的。而傳統分類方法用以解決不均衡數據分類問題，往往在少數類上的分類效果并不能讓人滿意。這是由于不均衡數據中少數類數量過少，導致數據集并沒有包含足夠的分類信息。此外傳統分類方法追求整體的正確率最大化導致分類結果更傾向于多數類，而可能誤分類人們更關注的少數類。所以針對不均衡分類問題，學術界有必要去尋找一種行之有效的算法。

對于不均衡數據分類問題有一系列方法陸續被提出，這些方法可以分為算法層面和數據層面。算法層面包括代價敏感［1］、特征選擇［2］和集成學習方法。在不均衡分類問題中人們通常更關注少數類，因此少數類才是不均衡分類的關鍵。針對不均衡數據中樣本重要性不同的特點，代價敏感學習給予各類別不同的錯分代價。例如在二分類問題中給予少數類更高的錯分代價，迫使分類器對少數類取得較好的識別效果。特征選擇方法在用于不均衡分類問題同樣取得較好的效果。如果數據集中不同類別樣本分布不均衡，則特征分布也可能會不均衡。因此選取最具有區分度的特征不僅可以降低復雜度，還有助于提高少數類的識別精度。集成學習即組合多個弱分類器得到一個強分器，由于其獨立性，集成學習常與抽樣方法、特征選擇方法相結合，例如：Guo等［3］提出了集成學習方法BAK（BPSO-Adaboost-KNN），該算法將基于簡化粒子群優化（Simple Particle Swarm Optimization，BPSO）的特征選擇方法與Adaboost相結合；Liu 等［4］提出了集成算法GU-MOACOFS（Genetic Under-sampling and MultiObjectiveAnt Colony Optimization based Feature Selection），該算法更是同時使用了欠抽樣、特征選擇和集成方法。

數據層面的方法是采用重抽樣方法均衡數據集中樣本分布，重抽樣分為過抽樣和欠抽樣。例如較為簡單的過抽樣方法是隨機過抽樣（Random OverSampling，ROS），該算法隨機復制少數類樣本以增加少數類樣本的數量。由于該算法實現簡單且性能良好，隨機過抽樣算法經常在研究中被用作基準算法進行比較。Ha 等［5］提出了基于遺傳算法的欠抽樣（Genetic Algorithm based Under-Sampling，GAUS），通過對損失函數尋找最優解得到最佳數據子集。與遺傳算法一樣，聚類算法也被用于提高抽樣算法的性能，例如：Rayhan 等［6］提出的欠抽樣算法（Clustering based Under-Sampling approach with BOOSTing algorithm，CUSBOOST），該算法在聚類所得簇中隨機選擇部分樣本；Lin 等［7］提出了兩種基于聚類的欠抽樣方法，則直接使用簇心或最接近簇心的樣本來代替原數據。過抽樣和欠抽樣雖然可以平衡數據分布，但欠抽樣可能會刪除對分類有價值的數據，過抽樣則會增加過擬合的風險而且可能引入不合理的樣本數據。針對過抽樣會引起過擬合的缺點，Chawla 等［8］提出了合成少數類過抽樣技術（Synthetic Minority Over-sampling TEchnique，SMOTE）算法，其思想是用少數類與其近鄰的少數類合成新樣本；但噪聲樣本可能參與合成新樣本，模糊多數類和少數類間的邊界。

針對上述SMOTE 的不足，許多研究人員提出了SMOTE的改進算法［9-11］。Bastista 等［12］提出了將SMOTE 算法和數據清洗方法相結合的方法SMOTE+ENN（Edited Nearest Neighbor）和SMOTE+Tomek links，在一定程度上保證了多數類和少數類的可分性。Han 等［13］提出Borderline-SMOTE 算法，該算法只對邊界附近的少數類進行抽樣。袁銘［14］提出了R-SMOTE 算法，在2個少數類樣本上使用N維球體，使生成的樣本在分布球體之內。R-SMOTE 算法消除了生成少數類實例分布的限制，提高了少數類的分類精度。趙清華等［15］提出了最遠點算法（Max Distance SMOTE，MDSMOTE），摒棄了傳統SMOTE 算法將正類樣本點分組的思想，只關注少數類樣本質心點和距離樣本質心點最遠距離的樣本點。

以上算法的性能與SMOTE 算法相比得到了一定程度的提高，但總體分類性能還是稍顯不足。為了進一步提高SMOTE 算法的性能，避免噪聲樣本參與合成樣本，提高新樣本的合理性，本文結合聚類算法提出了SMOTE 的改進算法

CSMOTE （Clustered Synthetic Minority Over-sampling TEchnique）。CSMOTE算法拋棄SMOTE在最近鄰間線性插值合成樣本的思想，使用少數類的簇心與其對應簇中樣本進行線性插值合成樣本，并根據簇心和樣本間的歐氏距離只選用了部分樣本。由于對參與合成的樣本進行了篩選，所以可以一定程度避免使用噪聲數據合成新樣本，同時保證多數類與少數類間邊界的明確性。最后在多個實際數據上，與四個SMOTE 的改進算法以及兩種欠采樣方法相比較，CSMOTE 算法具有更好的分類效果，說明該算法可以有效解決不均衡數據分類問題。

1 CSMOTE算法

1.1 CSMOTE算法設計思想

在不均衡數據集中，SMOTE 算法雖然可以平衡類分布，卻可能會模糊多數類和少數類的邊界。如圖1（a）所示。假設SMOTE 對圖1（a）中的少數類A 進行過抽樣，在樣本A 的最近鄰中隨機選擇一個樣本，假設選擇了樣本B，樣本A 和B 的線性插值可以合成樣本C。樣本C 因為侵占多數類的樣本空間，所以合成的樣本C 是一個不合理的樣本數據。在這種情況下，合成的樣本C并不會有助于分類器的訓練，反而由于樣本C 的存在會使得數據變得更加難以區分，同時會影響分類器的性能，所以保證新樣本的合理性是十分有必要的。

針對上述問題，本文提出了CSMOTE算法，該算法在少數類數據集的各個簇的范圍內合成新樣本。CSMOTE 算法的基本思想是對于簇中的一個少數類樣本minority，計算minority與其對應簇的中心點center的歐氏距離dis，如果不存在某個多數類樣本majority與center的距離d小于dis，則使用minority和center進行線性插值生成新的少數類樣本，否則放棄使用樣本minority。如圖1（b）所示，在少數類集合上使用k-means 算法得到了簇A 和B。圖中圓形表示多數類，矩形表示少數類，星型代表簇的中心點。在簇A中，由于多數類樣本D 與簇A 中心點的距離小于簇A 中所有少數類樣本與簇A 中心點的距離，所以CSMOTE 放棄在簇A 的范圍內合成新的樣本數據。簇B 中心點與最近的多數類樣本的距離大于簇B 中心點與簇中少數類樣本的距離，所以簇B 中的少數類均可參與新樣本的合成。綜上所述，CSMOTE 在簇B 中使用簇中心點和少數類樣本合成新樣本，且放棄了在簇A中合成新樣本，從而避免了合成的樣本點落入多數類的樣本空間，保證了新樣本的合理性。此外，CSMOTE 將簇的中心點加入到少數類數據集中，這可以豐富數據集中少數類的樣本分布。

1.2 CSMOTE算法流程

CSMOTE 算法流程如圖2 所示，首先將不均衡數據集分為少數類和多數類，在少數類上使用k-means聚類獲得多個子簇。依次在每個子簇中進行過抽樣，在子簇中隨機選擇參與合成的樣本，并根據所選樣本與對應簇心的歐氏距離判斷其是否可以參與合成。然后將簇心與所選樣本進行線性插值獲得新樣本。最后將合成的新樣本、簇心以及原少數類樣本與多數類相結合獲得均衡的數據集，將均衡數據集作為訓練集用于訓練分類器。算法具體步驟如下所示：

輸入 多數類集合maj={x1，x2，…，xm}，少數類集合min={x1，x2，…，xn}，聚類的個數k，過抽樣的倍數Rate，重復選擇的次數T。

輸出 合成的少數類集合newMin。

1）首先對少數類集合使用k-means 聚類，生成k個簇{C1，C2，…，Ck}，其對應的聚類中心為{u1，u2，…，uk}，初始化newMin={u1，u2，…，uk}。

2）如果所有的簇都已遍歷，則轉到步驟6），否則依次遍歷簇集合{C1，C2，…，Ck}取得簇Ci。

3）在簇Ci中隨機選擇一個樣本xj，如果isUse(xj)==True，轉到步驟4）；否則重新選擇樣本xj，如果重新選擇T次均沒有選擇到樣本滿足isUse(xj)==True，則轉到步驟5）。

4）生成一個0到1之間的隨機數Rate，利用簇Ci中心點ui和xj合成一個新樣本xnew：

5）重復步驟3)Rate*|Ci|次，然后轉到步驟2）。

6）輸出合成的少數類newMin。

isUse(xj)：

a）計算xj和聚類中心點ui的歐氏距離dis。

b）遍歷maj集合中樣本xt，計算xt和聚類中心點ui的歐氏距離d。如果存在xt使得d＜dis，則返回False；否則返回True。

CSMOTE 算法中的子步驟isUse(xj)是用于判斷選中的樣本xj是否可以參與合成新樣本。步驟1）對少數類集合進行kmeans聚類獲得k個簇，并將所有的簇心加入到合成的少數類集合。步驟2）對簇集合進行遍歷，步驟3）在當前簇中隨機選擇樣本，并用子步驟isUse(xj)來判斷該樣本是否可以參與合成，如果不滿足條件則重新選?。环駝t跳轉步驟4）使用選中的樣本和對應的簇心合成新樣本并加入到合成的少數類集合。步驟5）控制合成的樣本數量，每個簇合成的樣本數量為對應簇中樣本數量的Rate倍。步驟6）輸出合成的少數類集合。

圖2 CSMOTE算法流程Fig.2 Flowchart of CSMOTE algorithm

1.3 CSMOTE算法復雜度分析

定義n為少數類樣本數量，m為多數類樣本數量，樣本屬性個數為b。子步驟isUse(xj) 的時間復雜度為O(m)。CSMOTE 算法流程中，步驟1）中，對少數類集合使用k-means聚類的時間復雜度為O(bfkn)，其中，f為迭代次數，k為k-means 算法的分類數，由于f和k一般遠小于n，所以k-means算法的時間復雜度可簡化為O(n)。在步驟2）到步驟5）中，算法的時間復雜度為O(kn(Tm+d))，T為重復選擇的次數，本文中將其設為當前簇的樣本數，所以時間復雜度為O(kn(nm+d))=O(n2m)。綜上，CSMOTE算法時間復雜度為O(n2m)。

CSMOTE 算法空間復雜度取決于子步驟isUse(xj)中存儲簇心與所有多數類樣本的距離，因此，CSMOTE 算法空間復雜度為O(kn(nm+d))=O(n2m)。CSMOTE 算法的時間和空間復雜度均高于SMOTE 算法，可知CSMOTE 通過犧牲時間和空間上的效率獲得了分類性能的提高。

2 實驗與結果分析

2.1 數據集和評價指標

本文實驗選用了六個數據集分別為pimax、german3、horseM、breastM、ilpdM、transfusionM。這六個數據集源于不同的實際應用領域，數據集的詳細信息見表1，其中樣本比率表示多數類與少數類的數目之比，數值越大表明該數據集的不均衡程度越大。在實驗中曾嘗試在輸入數據時采用歸一化處理，但是與未采用歸一化處理相比較，除了在transfusionM 數據集上分類性能略有提升之外，其他數據集上所得分類性能均有較為嚴重的下降。此外，嘗試在子步驟isUse(xj)計算歐氏距離時采用歸一化處理，分類性能卻略有下降?；诜诸愋阅芤约皬碗s度的考慮，實驗中將不再對數據進行歸一化處理。

表1 數據集詳細信息Tab.1 Details of datasets

在不均衡分類分類器的評估中，因為分類精度無法反映少數類的分類效果，所以分類精度將不再適用。為此，研究人員提出了許多基于混淆矩陣的評價指標，例如recall、sensitivity、F-measure 以及GM（Geometric Mean prediction accuracy）?；煜仃嚾绫? 所示，少數類為正類，多數類為負類，列表示預測類別，而行表示真實類別。

表2 混淆矩陣Tab.2 Confusion matrix

TP表示正類樣本被正確分類的數量，TN表示負類樣本被正確分類的數量；FN表示正類樣本被錯誤分類為負類的數量，FP表示負類樣本被錯誤分類為正類的數量。本文實驗采用接受者操作特性曲線（Receiver Operating Characteristic curve，ROC）下的面積（Area Under the Curve，AUC）［16］來定量比較不同分類模型的性能，越大的AUC 代表分類的效果越好，AUC 為1 表示達到了最理想的分類效果，而AUC 為0.5 表示是隨機猜測。AUC的計算式如下：

式中：TPrate表示少數類中被正確分類的比率，其取值范圍為［0，1］；FPrate表示多數類中被錯誤分類的比率，其取值范圍為［0，1］。TPrate、FPrate計算式如下：

2.2 實驗步驟

圖3 展示了實驗流程，實驗流程描述如下：給定一個二分類的不均衡數據集，第一步基于K折交叉驗證將數據集分為訓練集和測試集。第二步將訓練集分為多數類子集和和少數類子集，然后使用過抽樣方法增加少數類子集中樣本數量，將過抽樣后的少數類子集和多數類子集相結合獲得均衡數據集。最后，分類器在均衡的訓練集和測試集分別進行訓練和測試。

圖3 實驗流程Fig.3 Flowchart of experiment

2.3 CSMOTE算法聚類參數k的確定

聚類參數k會影響合成少數類的分布情況，所以參數k的確定對CSMOTE 算法的性能十分重要。因此本文將選擇1、3、5、7、9、11 這6個1～11 之間的奇數作為k的值，通過對比CSMOTE 算法在不同參數k下過采樣后分類器所得的AUC 值來確定最佳的k值。不同k值的CSMOTE 算法在pimax、german3、horseM、breastM、ilpdM、transfusionM 數據集上的分類結果如圖4所示。

由圖4 可以看出，在german3、ilpdM 和transfusionM 數據集上CSMOTE 在k=7 時獲得了最大的AUC 值。而在pimax、horseM 和breastM 數據集上，k=7 時CSMOTE 雖然并未取得最優的AUC，但是與最優的AUC 值相比差距較小。其中在horseM 數據集上k=9 時取得最優值0.926，k=7 時則取得了僅次于最優的AUC 值0.925 8，k=7 時AUC 值僅比最優值低了0.000 2。在pimax 數據集，k=3 時取得最優值0.820 5，k=7 時取得的AUC 值為0.819，k=7 時AUC 值僅比最優值低了0.001 5。在breastM 數據集，k=3 和k=9 時取得最優值0.994 8，k=7 時取得的AUC 值為0.994 2，k=7 時AUC 值僅比最優值低了0.000 6。從六個數據集的均值來看，CSMOTE 在k=1，3，5，7，9，11 時獲得的平均AUC 值分別為0.822 5、0.823 8、0.824 0、0.828 5、0.823 0、0.821 7，k=7 時AUC 值比k=1，3，5，9，11 時分別高出0.006、0.004 7、0.004 5、0.005 5、0.006 8，由此可知k=7 與其他k值相比具有一定優勢。綜上所述，在下文的實驗中CSMOTE 的聚類個數k選擇為7。聚類參數k取決于數據集自身的特點，即樣本的分布情況。由于本文選用的數據集均為不均衡數據集，少數類可能被多數類分割為多個子區域，所以經過實驗確定的聚類參數k較大為7。除了通過多次實驗確定k值之外，在實際應用中確定k值的方法有：1）數據可視化，通過觀察數據的聚合程度確定參數k；2）手肘法；3）輪廓系數法。

圖4 不同k值的分類效果Fig.4 Classification effects of different k values on different datasets

2.4 不同算法的性能比較

為了進一步研究CSMOTE 算法的性能，在六個數據集上將CSMOTE 與Borderline-SMOTE、R-SMOTE、MDSMOTE、improvedSMOTE［17］和文獻［7］所提出的兩種欠抽樣方法（分別簡記為UC和UCN）進行比較。除了transfusionM 數據集之外，實驗所采用的數據集的不均衡比均為2 左右，且考慮到CSMOTE 算法選擇參與合成樣本的條件過于苛刻，如果過抽樣的倍數Rate設置過大可能會產生冗余樣本降低算法的效率，所以過抽樣的倍數Rate設置為1。CSMOTE在簇中隨機選擇參與合成新樣本，但是難以保證一次就選到符合條件的樣本，為了合成足夠的新樣本，同時考慮到時間成本，文中實驗將重復選擇的次數T設置為當前簇中樣本個數。CSMOTE 聚類參數為2.3節調優所得k=7，實驗所采用的分類器是以決策樹為基分類器的bagging。實驗中為保證結果的準確性，采用十折交叉驗證法，將數據集平均分為10 份，然后依次選擇其中1 份作為測試集，其余9 份作為訓練集，該過程重復10 次。實驗結果如圖5 所示，不同算法在6 個數據集上AUC 的均值如表3所示。

圖5 不同數據集上七種算法分類性能對比Fig.5 Classification performance comparison of seven algorithms on different datasets

表3 七種算法的分類效果（AUC）對比Tab.3 Classification effect（AUC）comparison of seven algorithms

從圖5和表3可以看出，在所有數據集上CSMOTE均取得了比其他算法更高的AUC，說明CSMOTE 的分類效果更好。其中，在german3 數據集上CSMOTE 的優勢最為明顯，可以比其他算法平均高出0.030 1。在pimax、horseM、ilpdM 和transfusionM 數據集上，CSMOTE 可以比其他算法平均高出約0.013 6。從均值來看，CSMOTE 依然具有優勢，CSMOTE 比Borderline-SMOTE、R-SMOTE、MDSMOTE、improvedSMOTE、UC 和UCN 分別高出了0.011 6、0.012 1、0.009 6、0.013 9、0.025 0、0.017 5。在horseM 數據集上所有算法均取得了0.9以上的AUC，在數據集breastM 上更是達到了0.99 以上的AUC，這表明所有算法在這兩個數據集上均取得了較可靠的效果。

CSMOTE 算法與對比算法相比：1）避免了噪聲數據樣本參與合成新樣本；2）利用簇心和樣本間的歐氏距離實現了對少數類的區別對待；3）根據樣本間的距離只選用了部分少數類參與合成新樣本，所以新樣本不會模糊多數類與少數類的邊界。綜上所述，通過了一系列的實驗驗證表明，針對不均衡數據分類問題，提出的CSMOTE算法是有效的。

3 結語

針對不均衡數據分類問題，本文從數據層面的方法出發提出了CSMOTE 算法。在實際數據集上，CSMOTE 與四個SMOTE 的改進算法以及兩種欠抽樣算法的分類性能進行了比較，結果表明CSMOTE 算法在處理不均衡數據集時具有更好的分類效果。該算法解決了已有算法中的不足，利用簇心和樣本間的歐氏距離選擇部分少數類樣本參與合成新樣本，既避免了噪聲數據樣本參與合成新樣本，又解決了SMOTE 算法模糊多數類與少數類間邊界的問題，從而提高了不均衡數據的整體分類性能。由于CSMOTE選擇少數類樣本參與合成樣本過程的條件較為苛刻，所以對于某些數據分布，參與合成的少數類數量過少導致合成的樣本分布過于集中。故下一階段研究工作就是解決CSMOTE在某些數據集中合成的新樣本分布過于集中的問題。