SMOTE 過采樣及其改進算法研究綜述

石洪波，陳雨文，陳鑫

（山西財經大學 信息學院，山西 太原 030031）

不平衡數據的分類問題在疾病檢測[1]、欺詐檢測[2]以及故障診斷[3]等應用領域中受到了廣泛關注。不平衡數據是指類分布明顯不均衡的數據，其中樣本數目多的類為多數類，而樣本數目少的類為少數類。由于少數類樣本數目過少，導致傳統分類器的準確率偏向于多數類，即便準確率很高也無法保證少數類樣本均分類正確。然而在現實生活中，少數類樣本的預測結果才是人們關注的重點，如疾病檢測中，人們對陽性病人檢測為陰性的容忍度要遠遠低于陰性病人檢測為陽性的容忍度。

為了提高不平衡數據的分類模型性能，近年來不少學者做了大量研究工作，主要分為算法層面和數據層面。本文重點關注數據層面的研究。在分類之前通過移除或添加一部分數據來平衡類分布是數據層面常用的做法，主要包括欠采樣和過采樣。傳統的處理不平衡數據集的采樣方法主要有隨機欠采樣和隨機過采樣。隨機欠采樣是指隨機地移除部分多數類樣本，但該方法可能會丟失部分有用的信息，導致分類器性能下降。隨機過采樣則是隨機的復制少數類樣本，使得數據的類分布平衡，但該方法由于反復復制少數類樣本，增加了分類模型過擬合的可能性。為解決上述問題，Chawla 等[4]提出了SMOTE(synthetic minority oversampling technique)方法，該方法通過在數據中增加人工合成的少數類樣本使類分布平衡，降低了過擬合的可能性，提高了分類器在測試集上的泛化性能。

SMOTE 為解決不平衡問題提供了新的方向，成為處理不平衡數據有效的預處理技術，并成功地應用于許多不同領域。SMOTE 促進了解決不平衡分類問題方法的產生，同時為新的監督學習范式做出了重大貢獻，如多標簽分類、增量學習、半監督學習以及多實例學習等[5]。許多研究人員根據SMOTE 提出了改進的算法，以克服SMOTE導致的過泛化等問題，從而提高不同應用背景下不平衡問題的分類模型性能。SMOTE 方法已經成為現階段不平衡分類領域的熱點技術之一。在CNKI 庫與Web of Science 核心集中，以“SMOTE”為關鍵詞的近10 年的發文數量總體呈逐年上升趨勢，其中2018 年CNKI 發文量達到61 篇，SCI發文量達到106 篇。而以“SMOTE”和“不平衡數據”為聯合關鍵詞的近10 年的發文數量總體也呈上升趨勢，這種現象說明了SMOTE 研究不平衡數據分類問題的重要性。此外，SMOTE 論文[4]在SCI 庫中的引用頻次逐年上升，尤其在2018 年達到644 次。這些數據從另一種角度說明了SMOTE 方法的重要性。

1 SMOTE 原理

SMOTE 方法是Chawla 等[4]提出的應用于不平衡問題的數據預處理技術。不同于隨機過采樣的簡單復制樣本機制，SMOTE 通過線性插值的方法在兩個少數類樣本間合成新的樣本，從而有效緩解了由隨機過采樣引起的過擬合問題。

SMOTE 的基本原理通過圖1 進行說明。首先從少數類樣本中依次選取每個樣本xi作為合成新樣本的根樣本；其次根據向上采樣倍率n，從xi的同類別的k(k一般為奇數，如k=5)個近鄰樣本中隨機選擇一個樣本作為合成新樣本的輔助樣本，重復n次；然后在樣本xi與每個輔助樣本間通過式(1)進行線性插值，最終生成n個合成樣本。

圖1 SMOTE 算法插值說明圖Fig.1 The interpolation illustration of SMOTE algorithm

算法SMOTE 算法

輸入少數類樣本集T，向上采樣倍率n，樣本近鄰數k；

輸出合成少數類樣本集S。

1) fori= 1 to |T| do

2) 計算xi的k個近鄰樣本并存入Xik集合；

3) forl= 1 tondo

4) 從Xik中隨機選取樣本xij；

5) 生成[0, 1]之間的隨機數 γ；

6) 利用公式(1)合成xij與xi間新樣本xnew的每個屬性值xnew,attr；

7) 將xnew添加到集合S中。

8) endfor

9) endfor

SMOTE 是基于特征空間的一種過采樣方法，在少數類樣本及其最近鄰樣本間合成新特征，然后組成新樣本。SMOTE 通過人工合成樣本緩解了由隨機復制樣本引起的過擬合，并在許多領域得到了廣泛應用，但同時也存在一些問題。

① 合成樣本的質量問題

由SMOTE 算法可知，新樣本的合成取決于根樣本與輔助樣本的選擇。若根樣本與輔助樣本均處于少數類區域，則合成的新樣本被視為是合理的。然而，若根樣本與輔助樣本中有一個屬于噪聲樣本，則新樣本將極有可能落在多數類區域，即新樣本將會成為噪聲而擾亂數據集的正確分類，此時該新樣本通常被視為不合理的。

② 模糊類邊界問題

SMOTE 算法在合成少數類樣本時不考慮多數類樣本的分布。如果SMOTE 從處于類邊界的少數類樣本中合成新樣本，其k近鄰樣本也處于類的邊界，則經插值合成的少數類樣本同樣會落在兩類的重疊區域，從而更加模糊兩類的邊界。

③ 少數類分布問題

少數類樣本分布不均勻，既有密集區也有稀疏區時，經SMOTE 過采樣合成的少數類樣本根據近鄰原則也會分布在相應的位置，即原少數類分布密集區經SMOTE 后依然相對密集，而分布稀疏區依然相對稀疏，因此，分類算法不易識別稀疏區的少數類樣本而影響分類的準確性。

如果少數類樣本分布稀疏且由若干碎片塊組成，即使采用SMOTE 方法，生成的樣本也極有可能仍位于每個碎片塊內，幾乎不改變數據集的分布，導致識別稀疏區的樣本更加困難。

2 SMOTE 的改進與擴展

針對上述問題，不少學者開展了新的研究，旨在提升SMOTE 合成樣本后數據的分類模型性能。本文搜集并整理了SMOTE 算法的主要相關文獻，并將其劃分成SMOTE 改進算法和其他方法與SMOTE 相結合的算法。

2.1 SMOTE 的改進算法

多數SMOTE 改進算法的關鍵在于根樣本和輔助樣本的選擇。由于根樣本是少數類樣本，如果輔助樣本分布在多數類周圍時，則合成的新樣本會加重兩類的重疊。基于此，許多學者對SMOTE做了相應的改進，以提高少數類的分類效果，部分經典的改進方法見表1。

表1 SMOTE 改進算法Table 1 The improved SMOTE algorithms

Han 等[6]只考慮分布在分類邊界附近的少數類樣本，并將其作為根樣本，提出了Borderline -SMOTE 方法。首先通過k-NN 方法將原始數據中的少數類樣本劃分成“Safe”、“Danger”和“Noise”3 類，其中“Danger”類樣本是指靠近分類邊界的樣本。根據SMOTE 插值原理，對屬于“Danger”類少數類樣本進行過采樣，可增加用于確定分類邊界的少數類樣本。Safe-Level-SMOTE 算法[7]則關注SMOTE 帶來的類重疊問題，在合成新樣本前分別給每個少數類樣本分配一個安全系數，新合成的樣本更加接近安全系數高的樣本，從而保證新樣本分布在安全區域內。ADASYN 算法[8]根據少數類樣本的分布自適應地改變不同少數類樣本的權重，自動地確定每個少數類樣本需要合成新樣本的數量，為較難學習的樣本合成更多的新樣本，從而補償偏態分布。SMOM 算法是Zhu等[9]為多類不平衡問題提出的一種過采樣技術，通過對輔助樣本的選擇，進而確定合成樣本的位置。SMOM 算法通過給每個少數類樣本xi的k個近鄰方向分配不同的選擇權重來改善SMOTE引起的過泛化問題，其中選擇權重的大小代表沿該方向合成樣本的概率，權重越大說明沿該方向合成的樣本越安全。G-SMOTE 算法[10]通過在每個選定的少數類樣本周圍的幾何區域內生成人工樣本，加強了SMOTE 的數據生成機制。

2.2 欠采樣與SMOTE 結合的方法

數據集中存在噪聲樣本時，采用SMOTE 過采樣會加劇兩類樣本的重疊，從而影響該數據集的分類效果。文獻[11-12]的實驗結果表明，混合采樣后數據的分類模型性能往往優于單個采樣方法。融合欠采樣和過采樣的混合采樣成為改進SMOTE 方法的一種新的思路，本文介紹了部分經典的融合算法，如表2 所示。

表2 欠采樣與SMOTE 結合的方法Table 2 Methods combining undersampling with SMOTE

AdaBoost-SVM-MSA 算法[13]按一定規則將SVM 分錯的樣本劃分成噪聲樣本、危險樣本與安全樣本，然后直接刪除噪聲樣本，采用約除法處理危險樣本，并對安全樣本進行SMOTE 過采樣。基于聚類的混合采樣(BDSK)[14]將SMOTE的過采樣與基于K-means 的欠采樣相結合，旨在擴大少數類樣本集的同時有效剔除噪聲樣本。BMS 算法[15]通過設置變異系數閾值將樣本劃分成邊界域和非邊界域，然后使用SMOTE 以及基于歐氏距離的隨機欠采樣方法(OSED)[16]分別對邊界域的少數類樣本和非邊界域的多數類樣本進行采樣，旨在解決在剔除噪聲時由于誤刪少數類樣本而丟失部分樣本信息的問題。OSSU-SMOTEO算法[17]使用單邊選擇(OSS)欠采樣移除多數類樣本中冗余樣本和邊界樣本，然后采用SMOTE 對少數類樣本過采樣，從而平衡數據集，提高SVM在預測蛋白質s-磺酰化位點的分類精度。文獻[18]的HybridSampling 使用DBSCAN 和KNN 剔除多數類中的模糊樣本；然后采用SMOTE 對重疊區域的少數類樣本過采樣，達到平衡數據集的目的。SDS-SMOT 算法[19]利用安全雙篩選丟棄遠離決策邊界的多數類樣本和噪聲樣本，實現原始數據集的欠采樣，采用SMOTE 合成新樣本實現過采樣，使數據集達到基本平衡。基于SVM分類超平面的混合采樣算法(SVM_HS)分別對多數類樣本和較為重要的少數類樣本進行欠采樣和過采樣從而平衡數據集[20]。

2.3 過濾技術與SMOTE 結合的方法

混合采樣是克服不平衡問題中噪聲樣本的一種手段，然而結合噪聲過濾技術同樣可以消除由SMOTE 合成的錯誤樣本，如表3 所示。常見的過濾技術包括基于粗糙集的過濾、數據清洗等。

表3 過濾技術與SMOTE 結合的方法Table 3 Methods combining filtering technique with SMOTE

Ramentol 等[21]將粗糙集理論的編輯技術與SMOTE 算法融合，提出了SMOTE-RSB*算法。SMOTE-IPF 算法[22]采用迭代分區濾波器(iterative-partitioning filter，IPF) 將噪聲過濾器與SMOTE 融合，旨在克服不平衡問題中的噪聲和邊界問題。BST-CF 算法[23]將SMOTE 與噪聲過濾器CF(classification filter)結合，在平衡數據集的同時，從多數類中消除位于邊界區域的噪聲樣本。SSMNFOS 算法[24]是一種基于隨機靈敏度測量(SSM)的噪聲過濾和過采樣的方法，從而提高過采樣方法對噪聲樣本的魯棒性。NN-FRIS-SMOTE算法[25]則先篩選出代表性的樣本，再使用模糊粗糙實例選擇(RSIS)技術過濾噪聲樣本，然后使用SMOTE 過采樣少數類樣本，從而增加了正確識別產品缺陷的可能性。基于數據清洗的過濾算法中典型的有SMOTE-Tomek 和SMOTE-ENN 算法[26]，SMOTE-Tomek 利用SMOTE 對原始數據過采樣來擴大樣本集，移除采樣后數據集中的Tome Link 對，從而刪除類間重疊的樣本，其中Tome Link 對是指分屬不同類別且距離最近的一對樣本，這類樣本通常位于類間或者是噪聲樣本。SMOTE-ENN 則是通過對采樣后的數據集采用k-NN 方法分類，進而剔除判錯的樣本。

2.4 聚類算法與SMOTE 結合的方法

聚類算法和SMOTE 結合是調整數據分布的另一種思路，其主要策略通常有兩種：一是直接采用聚類算法將少數類樣本劃分成多個簇，在簇內進行插值；二是利用聚類算法識別樣本類型，對不同類型的樣本采用不同的方式處理，然后再使用SMOTE 進行過采樣，部分算法如表4 所示。

MWMOTE 算法[27]按照與多數類樣本的距離對難以學習的少數類樣本分配權重，采用聚類算法從加權的少數類樣本合成樣本，從而保證這些新樣本位于少數類區域內。對于多類不平衡問題，FCMSMT 算法[28]使用模糊C 均值(FCM)對樣本多的目標類聚類，選出與平均樣本數相同數量的樣本，而對樣本少的目標類使用SMOTE 過采樣，從而降低類內與類間的錯誤，提高分類性能。K-means SMOTE 算法[29]利用K-means 對輸入數據集聚類，在少數類樣本多的簇內進行SMOTE過采樣，從而避免噪聲的生成，有效改善類間不平衡。

CB-SMOTE 算法[30]根據“聚類一致性系數”找出少數類的邊界樣本，再根據最近鄰密度刪除噪聲樣本，同時確定合成樣本的數量，然后從這些邊界樣本中人工合成新樣本。CURE-SMOTE 算法[31]采用CURE(clustering using representatives)對少數類樣本聚類并移除噪聲和離群點，然后使用SMOTE 在代表性樣本和中心樣本間插值以平衡數據集。HPM 算法[32]通過整合DBSCAN 的離群檢測、SMOTE 和隨機森林，從而成功預測糖尿病和高血壓疾病。IDP-SMOTE 算法[33]利用改進的密度峰值聚類算法(improved-DP)對各個類進行聚類，識別并剔除噪聲樣本，然后采用自適應的方法對每個少數類樣本進行SMOTE 過采樣。

3 面向特定應用背景的SMOTE

3.1 面向高維數據的SMOTE

高維不平橫數據中的數據分布稀疏、特征冗余或特征不相關等問題是影響傳統學習算法難以識別少數類樣本的原因。SMOTE 在處理這類問題時效果甚至不如隨機欠采樣方法[34]，而目前常見的做法是在分類前使用現有的技術對數據進行降維，然后在新的維度空間下學習。常見的降維技術有主成分分析(PCA)[35]、特征選擇、Bagging[36]、內核函數(kernel functions)[37]、流形技術(manifold techniques)[38]和自動編碼器(auto-encoders)[39]等。

Li 等[40]提出了基于LASSO 的特征選擇模型，首先使用特征選擇和其他方法刪除數據中冗余和不相關的特征，然后采用基于LASSO 的特征權重選擇模型增加關鍵數據的權重，再利用SMOTE 平衡數據集，從而有效消除高維數據中噪聲和不相關數據。Zhang 等[41]通過改進的SVMRFE[42]算法(SVM-BRFE)對高維數據進行特征選擇，并采用改進的重采樣PBKS 算法對不平衡數據進行過采樣，提出了針對高維不平衡數據二分類的BRFE-PBKS-SVM 算法。在處理高維不平衡的醫療數據時，許召召等[43]將SMOTE 與Filter-Wrapper 特征選擇算法相融合，并將其應用于支持臨床醫療決策。Guo 等[44]使用基于隨機森林(RF)的特征選擇方法降低計算復雜度，然后通過結合SMOTE 和Tomek Link 的重采樣平衡數據集，從而提高膜蛋白預測的準確性。

3.2 面向回歸問題的SMOTE

不平衡數據的回歸問題是指預測連續目標變量的罕見值的問題。目標變量為離散值的不平衡分類問題一直以來得到了深入的研究，而不平衡回歸問題的研究成果卻少之又少。回歸問題可以分為兩類：傳統回歸與序數回歸。

傳統回歸是指在不考慮數據集有序特性的情況下，對連續型目標變量的預測問題。SMOTER算法[45]是處理不平衡回歸數據的一種改進的SMOTE 過采樣方法，通過人為給定的閾值將極少數實例定義成極高值和極低值，并將這兩種類型作為單獨的情況處理，而合成樣本的目標變量值則是通過兩個所選樣本目標變量的加權平均值確定。Moniz 等[46]考慮時間序列的特性，將SMOTER 算法推廣到不平衡的時間序列問題中，從而提出了SM_B、SM_T 和SM_TPhi 3 種方法。Branco等[47]結合SMOTER 方法，提出了基于bagging 的集成方法(REBAGG)，以解決不平衡回歸問題。

序數回歸則考慮數據集的有序特征，將原始數據的目標變量值按人為給定的閾值依次劃分成多個有序的類標簽，然后對這些類標簽分類。在序數回歸的有序類標簽中，兩端的類通常是極端情況，這類樣本也占少數，因此序數回歸本質上是一種類不平衡問題。Pérez-Ortiz 等[48]提出了OGONI, OGOISP 和 OGOSP 3 種基于圖的過采樣方法，旨在平衡有序信息。但是，這3 種方法只考慮到少數類及其相鄰類的局部排序，忽略了其他類的排序。因此，Zhu 等[49]提出了SMOR 算法，對每個少數類樣本，找到與其類別相同和相鄰的k個近鄰樣本，沿每個近鄰樣本分配不同的權重，以控制合成的樣本更加靠近少數類，從而保證樣本結構的有序性。

3.3 面向分類型數據的SMOTE

SMOTE 過采樣是從特征的角度生成新樣本，新樣本的特征是從根樣本與輔助樣本對應的特征間插值產生，而插值的關鍵在于距離的度量。SMOTE 過采樣所選擇的歐氏距離只能處理數值型數據，而對分類型數據過采樣的方法有兩種：分類型數據數值化和改進距離度量公式。

分類型數據數值化方法對數值化后的數據使用SMOTE 插值，是處理分類型數據常用的方法之一。然而，插值后屬性值是否合理是SMOTE方法面臨的問題。Chawla 等[4]對含有分類型屬性數據分別提出了SMOTE-NC 和SMOTE-N 算法，前者仍采用歐氏距離來計算，對分類型屬性間的距離則采用連續屬性標準差的中值來代替；后者則采用VDM(value difference metric)距離公式[50]來度量兩個樣本間的距離。Kurniawati 等[51]也利用VDM 改進了ADASYN，提出了ADASYNN 和ADASYN-KNN 算法，用來處理具有分類型數據的多類數據集。針對含有分類型屬性的距離度量，現階段已經得到了廣泛研究，相比VDM 度量，HVDM(heterogeneous value difference metric)度量[52]在處理混合屬性的數據時更具優勢。其他處理含有分類型屬性的距離度量包括Ahmad’s距離度量[53]、KL 散度[54]以及基于context 的距離度量[55]等。圖2 總結了上述3 種不同應用背景下處理不平衡數據的相關技術或方法。

圖2 面向不同應用的SMOTE 改進方法Fig.2 The improved SMOTE methods for different applications

4 SMOTE 研究展望

SMOTE 算法在處理不平衡數據時表現出良好的優勢，然而現實中數據的表現形式多種多樣，在面臨不同類型不平衡數據(如大數據、流數據等)時，如何利用SMOTE 等技術來提升學習算法性能仍需深入研究。

4.1 不平衡大數據

基于分布式計算的分類算法是處理大數據的主要解決思路。典型的分布式計算技術MapReduce 及其開源實現Hadoop-MapReduce 為處理大數據提供了成熟的框架和平臺。然而，在處理不平衡大數據時，由于高維、缺乏少數類樣本等因素，以至于分布在每個站點的數據塊所包含的少數類樣本更少，而直接采用SMOTE 過采樣將變得更加困難。Rio 等[56]將SMOTE 算法應用于大數據的MapReduce 工作流中，將輸入數據分割成若干個獨立的數據塊并傳輸到各個機器，每個Map 任務負責使用SMOTE 從相應的分區中生成數據，Reduce 階段隨機化Map 階段的輸出，最終形成一個平衡的數據集。當數據集中存在小碎片時，結果可能會產生嚴重的偏差。SMOTE 合成樣本是基于k-NN 算法的，對同一個少數類樣本而言，其在獨立數據塊的近鄰樣本極有可能與原始數據不同，因此經過插值得到的數據很可能有偏，甚至擾亂原始數據的分布。如何改進分布式環境中的SMOTE 算法，提高分布式系統中合成樣本的質量需要繼續探索。

4.2 不平衡流數據

不平衡分類問題處理的數據通常是靜態的，然而現實中的數據大多是以流的方式出現的動態數據，其數據分布也會隨時間延續而不斷變化。不平衡流數據在網絡監控、故障檢測等領域廣泛出現，在線學習是處理流數據的關鍵技術，但在線實時學習數據流時可能會面臨一些困難[57]。一方面，流數據的分布隨時間而改變，導致內在結構不穩定從而產生概念漂移[58]。另一方面，由于缺乏先驗知識，無法事先獲取新增數據的類標簽，導致數據的不平衡狀態不穩定，無法確定哪個類是少數類或者多數類[59-60]。集成框架下的代價敏感學習[61-62]與SMOTE 預處理技術[63]是解決上述問題的主要手段。從SMOTE 預處理技術的角度而言，窗口化過程意味著只向預處理算法提供總數據的一個子集，從而影響了合成數據的質量[5]。因此如何有效利用流數據，提高合成數據質量，進而提升SMOTE 算法性能是下一步需要解決的問題。

4.3 少量標簽的不平衡數據

監督學習的重要前提是獲得足夠多的有標簽數據來訓練預測模型。然而現實中的數據通常是未經標記的無標簽數據，有標簽數據只占少數，且獲得大量有標簽數據非常困難。特別是在不平衡數據中，從少量少數類數據中獲取帶標簽的數據更是難上加難。如何利用少量標簽數據提升學習器的泛化性能是目前不平衡分類問題的瓶頸之一。主動學習是處理這類問題的技術之一，通過引入專家知識對信息量大的無標簽數據進行標記從而提高模型精度。半監督學習[57]則是另一種技術，該技術不依賴于外界交互，而是自動地利用無標簽數據的內在信息改進分類模型，從而提高學習性能。此外一些學者試圖在這種學習范式中，利用SMOTE 生成新的數據，從而彌補由大量無標簽數據引起的缺陷[64-67]。然而如何選擇和使用信息量豐富的數據仍需進一步深入研究。

4.4 其他類型數據

除上述3 種類型的數據外，還存在其他不同類型的不平衡數據，如高維數據、數值型標簽數據以及二值屬性數據等。盡管關于這類型數據取得了一些成果(見第3 節)，但仍面臨一些問題。

高維數據由于其分布稀疏、特征維數高的特點，導致傳統學習算法處理起來過于困難，在預處理前對數據進行降維是目前主要解決方案。雖然已經研究出許多可用的降維技術，但是，如何擴展或修改SMOTE 算法，使其能夠直接應用于高維數據，避免數據降維工作，是一個值得深入研究的方向。

調整數值型標簽數據的分布是回歸領域中預處理所面臨的問題，將數值型標簽轉換為離散型是一種解決思路。但對一些特殊的回歸問題，經過離散化標簽后的數據本質上存在一種有序關系，如何調整合成樣本的區域，使得生成的新樣本位于其類內或相鄰類內，而不改變原始數據的本質特性是這類問題的關鍵。

二值屬性數據是分類型數據的特殊形式，分類型數據數值化是其中一種處理方式，使用SMOTE 對數值化后的數據進行過采樣，是對這類問題常見的預處理解決方案。但合成的新樣本通常會不合理，如某二值屬性取值為0(紅)和1(藍)，經過插值生成的新樣本的對應特征值為0.65，則該特征值顯然沒有任何意義，因此，合成新樣本的特征取值需要考慮其原始屬性值的范圍，然后對其進行調整，以符合實際意義。將分類型數據的距離度量與SMOTE 融合是處理分類型不平衡數據的另一個流行方法，因此，合理考慮這類問題的本質特性，探索有效的距離度量方法是目前另一個研究熱點。

5 結束語

SMOTE 過采樣解決了隨機過采樣的過擬合問題，是數據層面流行的預處理技術。本文主要闡述了SMOTE 過采樣的研究現狀與工作原理，針對SMOTE 存在的問題，對一些改進的SMOTE算法進行了綜述，同時概述了不同應用背景下關于SMOTE 算法的研究工作，最后分析了SMOTE算法在處理不平衡大數據、不平衡流數據、少量標簽的不平衡數據等數據時需要進一步探索和研究的問題。本文可為SMOTE 的研究和應用提供有價值的借鑒和參考。