邊界與密度適應的SMOTE算法研究

摘 要： 針對合成少數類過采樣技術等基于近鄰值的過采樣算法在處理數據類不平衡時，不能根據少數類樣本分布情況及時調整模型參數，導致過采樣后的數據集引入噪聲，并且在原始分布區域上無差別地合成少數類實例造成過擬合等問題，提出了一種特征邊界和密度適應的SMOTE算法（SMOTE algorithm for feature boundary and density adaptation，BDA-SMOTE）。該算法為每一個少數類樣本規劃安全區域，增加少數類的分布，同時基于數據的分布密度動態地調整模型參數，確保生成的數據具有明顯的特征邊界，防止過擬合。在公開數據集KEEL上與常用的SMOTE算法進行實驗對比，結果BDA-SMOTE的性能優于其他基于近鄰SMOTE算法。表明該算法較好地擴展了原數據集的分布，同時合成的噪聲樣本更少。

關鍵詞： 合成少數類過采樣； 類不平衡； 特征邊界； 密度適應

中圖分類號： TP391"" 文獻標志碼： A

文章編號： 1001-3695（2022）05-032-1478-05

doi：10.19734/j.issn.1001-3695.2021.09.0410

Research on SMOTE algorithm based on boundary and density adaptation

Mei Dachenga，b， Chen Jianga，b， Zheng Taoa

（a.School of Computer Science amp; Technology， b.Key Laboratory of Sichuan University of Petroleum Engineering Computer Simulation Technology， Southwest Petroleum University， Chengdu 610500， China）

Abstract： For oversampling algorithms based on nearest neighbor values，such as synthetic minority oversampling technology，when dealing with imbalances in data categories，cannot modify the model parameters in time according to the distribution of minority samples，resulting in the introduction of noise in the oversampled data set，synthesize minority instances indiscriminately on the original distribution area causes problems such as over-fitting，this paper proposed a feature boundary and density adaptation SMOTE algorithm （BDA-SMOTE）.The algorithm planned a safe area for each minority sample，increased the distribution of the minority class，and dynamically adjusted the model parameters based on the distribution density of the data to ensure that the generated data had obvious characteristic boundaries.An experimental comparison with the commonly used SMOTE algorithm on the public data set KEEL shows that the performance of BDA-SMOTE is better than other SMOTE algorithms based on nearest neighbors.It shows that the algorithm expands the distribution of the original data set better with fewer synthesized noise samples.

Key words： synthetic minority oversampling； class imbalance； feature boundary； density adaptation

近年來隨著人工智能和大數據技術的迅速發展，許多行業的數據樣本類不平衡問題引起廣泛關注，例如醫學診斷、欺詐檢測、企業信用評估、垃圾郵件識別、漏油檢測等［1，2］。數據類不平衡是指數據樣本中的一個類與另一個類數據分布不均，使得少數類代表性弱，多數類的代表性過強，機器學習算法更偏向于多數類的學習和識別，導致少數類樣本比多數類樣本更容易分錯［3，4］。一般情況下少數類是本文關注的對象，然而由于數據類不平衡導致機器學習算法識別少數類的效果差，處理類數據不平衡成為一個亟待解決的問題。目前處理類不平衡數據常用的方法有欠采樣法、過采樣法和混合采樣法，其中欠采樣法是通過減少多數類樣本的數量來平衡數據［5，6］，不過這種方法容易丟失多數類的有用信息。混合采樣法是將欠采樣和過采樣結合使用，很顯然也會面臨欠采樣同樣的問題。合成少數類過采樣技術具有改變原樣本的分布、獨立于分類模型兩個明顯的優勢［7］，因此，使用過采樣技術處理不平衡數據無疑是最優選擇。

二分類是最常見的分類需求，本文旨在研究二分類的過采樣，通過分析當前常見的過采樣技術，結合這些過采樣技術的優缺點進行討論，最終給出一種新的解決方案。

1 相關工作

Chawla等人［8］最早提出了合成少數類過采樣（SMOTE）算法技術并廣泛應用于不平衡數據的過采樣，該算法基于K近鄰隨機在兩個少數類連線上合成樣本，使不同類間樣本趨于平衡，不過這樣會產生較多的噪聲，破壞了原始數據的分布。此后不斷有人提出多種方法改進SMOTE算法，ADASYN［9］是一種常見的SMOTE改進算法，它基于K近鄰自動為每個少數類樣本規劃生成實例個數，這種SMOTE變體規劃了生成實例樣本的個數，然而卻忽視了線性插值會引入噪聲的問題。Borderline-SMOTE［10］通過鄰域樣本數量區分邊界與非邊界區域，以合成邊界樣本的方法平衡數據集，是目前最流行的SMOTE變體之一，但是此方法沒有處理噪聲樣本的干擾，在一定的條件下模型無法識別邊界樣本。其中MWMOTE［11］算法、KernelADASYN［12］算法與Borderline-SMOTE類似，利用邊界信息識別少數類和多數類。SMOTE-LOF算法［13］通過引入局部異常因子識別SMOTE合成的噪聲。文獻［1］提出NaNSMOTE動態給出最鄰近樣本數k的選擇，通過減少邊界區域合成新樣本以減少噪聲的合成，在一定程度上抑制了噪聲數據的生成。文獻［14，15］提出基于聚類的SMOTE算法，這種算法通過聚類識別噪聲，以線性插值的方式合成新的樣本。以上這些方法生成的數據是在固定方向上分布，不利于泛化。AdaN-SMOTE算法［16］在超矩形鄰域中查找少數樣本精度下降最陡點合成新的樣本，解決SMOTE算法被動就近選擇鄰值問題。G-SMOTE算法［17］是一種基于幾何的SMOTE算法，合成的數據分布在一個靈活的超球影響區域，在一定程度上減少了產生噪聲的幾率，但是忽略了離群值合成噪聲的情況。總之，現有的SMOTE以及它的變體仍存在一些不足之處。

2 相關理論

2.1 AdaN-SMOTE算法

AdaN-SMOTE算法通過跟蹤超矩形鄰域中少數類樣本的精度確定合成樣本的范圍，所謂精度是指少數類樣本數量占整個超矩形區域樣本的比重，然后采用插值法在超矩形區域內隨機生成新樣本，其簡要步驟如下：a）在少數類樣本xi的超矩形鄰域內搜索精度下降最快點ki，確定少數類K近鄰樣本的個數，同時確定合成少數類樣本的范圍comik ；b）在comik范圍內隨機生成一個向量δ，并滿足|δ|∈［0，1］；

c）隨機選擇一個K近鄰樣本點xk，根據插值公式xgen=xi+δ（xk-xi）合成新的樣本。

2.2 G-SMOTE算法

G-SMOTE的思想是在每個選定的少數類樣本附近定義一個超球安全區域，在安全區域內合成樣本從而減少噪聲樣本的合成，通過幾何變換擴大生成樣本的多樣性。其簡要步驟如下：

a）根據超參數調節安全區域的邊界點Xsurface的三種選擇模式。即從最近鄰的k個少數類樣本中隨機選擇一個樣本、從多數類中選擇一個距離最近的樣本和根據方式1、2選出一個最近的樣本。根據Xcenter和Xsurface確定一個半徑為R的安全區域。

b）隨機生成一個服從正態分布的p維向量單位e和服從均勻分布的p維向量r，則Xgen=r1/pe。

c）通過超參數αtrunc和αdef對Xgen進行幾何變換，具體變換方式可參考文獻［17］，這里不再贅述。

d）根據式子Xgen=Xcenter+RXgen合成新的樣本。

2.3 特征邊界

Pujol等人［18］提出特征邊界點（CBP）的概念，認為特征邊界點能夠有效地抑制過擬合，對噪聲具有良好的魯棒性。其中文獻［11～13，19～22］等佐證了邊界的優勢和增強邊界對分類的作用。特征邊界點位于少數類與多數類最近兩個樣本的中點，數學表示為Xcbp=1/2（Xmin+Xmaj），其中Xcbp為特征邊界點，Xmin為少數類樣本，Xmaj為多數類樣本。將所有的特征邊界點用分段線性函數連接起來構成特征邊界，它是局部最優的超平面，可以將任意兩個類無歧義地劃分開來。特征邊界的碰撞區包含了大量劃分類的信息，在過采樣的過程中應當充分考慮到特征邊界數據的重要性。根據特征邊界在歐氏幾何空間創造了一個超球安全區域，確保生成的數據不會滲透到多數類中，極大可能地避免了噪聲數據的生成。圖1直觀地展示了特征邊界點和特征邊界。

2.4 密度適應調整

眾所周知，在實際應用中機器學習模型的泛化能力十分重要，這決定了訓練好的模型是否可以應用于實際預測。目前SMOTE和它的改進算法比較依賴于原始數據集的分布，如果原始數據集的少數類分布密度比較大，合成的數據大多會覆蓋到原數據上，不利于泛化。因此，可以根據數據的分布密度調整某個幾何空間中合成數據的概率。同時，為了消除離群點對分類的影響，在歐氏幾何空間中引入密度集群的思想，即把密度相似的數據歸為一類［23］，通過密度區分正常的數據和離群點，一般來說離群值的密度遠低于集群的密度，只需要對密度過小的區域進行動態調整，就可以防止擴大噪聲數據的優勢。

2.5 噪聲和復雜邊界

不平衡數據集往往是含有噪聲的，現有的SMOTE算法總是引入較多的噪聲，且當數據集邊界比較復雜時，經過某些過采樣算法處理后將破壞原始的數據分布。噪聲數據一般是指位于多數類區域中的少數類離群樣本，復雜邊界是指非線性的分類邊界。當前大多數合成少數類過采樣算法難以判斷噪聲數據，尤其是當分類邊界比較復雜時，合成的少數類往往會落在多數類區域中，給分類器的分類任務增加難度。BDA-SMOTE算法通過密度適應和邊界安全區域約束減少了噪聲的合成。針對少數類中的噪聲數據，以下給出了BDA-SMOTE和幾種常見SMOTE過采樣算法的實例，為了方便理解，僅以二維的數據進行展示。

圖2分別給出了數據集中包含噪聲和復雜邊界時不同過采樣器處理數據后的實例，最左側的是數據的原始分布圖，隨后依次是標簽對應的過采樣器處理后的數據分布示意圖。上半部分對應的原數據集包含噪聲，下半部分原數據集分類邊界比較復雜。從圖中不難發現，基于幾何的過采樣算法無法完全避免噪聲數據的合成，相同情況下對比其他幾種過采樣算法，其中BDA-SMOTE算法合成的噪聲數據最少。對比復雜邊界的情況可以看出，BDA-SMOTE和AdaN-SMOTE引入噪聲的數量最少，G-SMOTE算法能夠較好地擴展數據分布，而通過SMOTE、B1-SMOTE和ADASYN過采樣破壞了原數據的分布。AdaN-SMOTE依賴于原數據集的分布密度，當原數據分布比較密集時，合成的數據也會比較密集地集中在一個區域，缺少樣本的多樣性。G-SMOTE算法對原數據的分布擴展較好，但是該算法會引入較多的噪聲。BDA-SMOTE處理后的數據不僅擴展了原數據分布，在引入較少噪聲的前提下自適應地調整合成樣本的分布密度，增強數據的泛化能力，彌補了傳統SMOTE的不足。

5 實驗結果分析

每個分類器10次5折交叉驗證對應的各種平均評估指標和過采樣器的類型如表2所示。從表2可以看出，過采樣器與分類準確率并無明顯的聯系，因此把accuracy視為一般指標，把recall、F1-score和AUC認為是重要的性能評估指標。經過BDA-SMOTE過采樣后，recall、F1-score和AUC明顯高于原數據集，其中AUC分別提升了8%和10%。BDA-SMOTE的各項重要分類指標優于其他過采樣器，在SVM分類器上表現最佳，表明BDA-SMOTE過采樣算法具有一定的可靠性。

RF對于不平衡數據具有較強的適應能力，原數據集的各項分類指標與過采樣器的各項分類指標差異相對較小。KNN分類比較依賴于原數據樣本的近鄰樣本類型，對噪聲十分敏感。SVM分類器是一種基于決策邊界的分類器，少數類和多數類的支持向量決定了分類結果，如果合成的噪聲樣本較多時，會使得SVM分類器的約束條件變得過于復雜從而導致過擬合，或由于少數類樣本的數量較少，在進行數據集劃分時導致邊界信息丟失導致欠擬合，這些原因都會導致SVM分類性能變差。BDA-SMOTE的各項重要分類指標優于其他過采樣器，是因為BDA-SMOTE算法進行分步相對密度調整，在不破壞原樣本分布的前提下，最終使合成的少數類樣本整體上逐步收斂到一個中心區域，使分類任務變得更加簡單。使用安全區域和相對密度適應調整，擴展了原樣本的分布，在合成少數類樣本時會盡量避免噪聲數據。在特征邊界點和支持邊界點之間的安全區域構造分類邊界，擴展和增強了分類邊界的信息，能夠通過邊界因子進行調整。邊界因子αenh表征對特征邊界的關注度。αenh越大，表明對邊界的關注度越高。其中調整邊界因子αenh∈{0.5，0.6，0.7，0.8，0.9，1}與αenh=0.7作對比，不同分類器與不同增強因子對應的平均評估指標結果如表3所示。

表3實驗結果表明，當邊界因子αenh=0.7時，在以上36個數據集上分類器的性能最佳，綜合來看αenh的調節效果不是特別明顯，這是因為αenh是根據支持邊界點的比重Ps調節邊界樣本的分布密度，不同的數據集對αenh調節反映有所差異。設置αenh∈（0，1］，步長為0.1，分別在數據集Wisconsin和winequality-red-3_vs_5上測試AUC變化，其中數據集Wisconsin的Pinit約為5%，數據集winequality-red-3_vs_5的Pinit約為85%，其結果如圖4所示。根據圖4可知，當Pinit值較小時，樣本的分類邊界比較簡單，邊界因子αenh的調節作用不明顯。當Pinit值較大時，邊界一般比較復雜，甚至少數類和多數類出現層疊混淆，此時邊界因子αenh的調節作用比較明顯，新合成的樣本會逐步收斂到特征邊界。當合成邊界樣本的比例Ps為100%時，αenh的調節效果不再變化。

6 結束語

本文提出了一種基于特征邊界和密度自適應調節的過采樣算法BDA-SMOTE。該算法主要貢獻如下：a）在特征邊界和支持邊界點之間重構決策邊界，使過采樣數據集有一個明顯的分類邊界，防止少數類與多數類層疊混淆；b）自適應性給不同密度分布的數據規劃了非線性映射區間，使生成的數據實例自適應地分布在安全區域內，減小過擬合和噪聲數據的產生；c）給出一個超參數邊界因子，可以通過調參修改對特征邊界的重視程度，使BDA-SMOTE可以適用于所有數據集的合成少數類過采樣。BDA-SMOTE的性能在36個不同失衡程度的數據集上進行了測試，與常見的過采樣器SMOTE、ADSYN、B1-SMOTE等進行了對比，實驗結果證明了BDA-SMOTE的性能更優，并且，BDA-SMOTE可解釋性強，算法容易復現，可廣泛用于合成少數類過采樣。由于該算法動態計算局部的分布密度，合成數據的平均時長大于傳統的SMOTE算法。在接下來的時間里，本文將致力于進一步優化BDA-SMOTE算法，將該算法應用于高維稀疏的不平衡數據集的過采樣。

參考文獻：

［1］Li Junnan，Zhu Qingsheng，Wu Quanwang，et al.A novel oversampling technique for class-imbalanced learning based on SMOTE and natural neighbors［J］.Information Sciences，2021，565：438-455.

［2］Yan Yuanting，Liu Ruiqing，Ding Zihan，et al.A parameter-free clea-ning method for SMOTE in imbalanced classification［J］.IEEE Access，2019，7：23537-23548.

［3］Johnson J M，Khoshgoftaar T M.Survey on deep learning with class imbalance［J］.Journal of Big Data，2019，6（1）：article No.27.

［4］Sez A J，Luengo J，Stefanowski J，et al.SMOTE-IPF：addressing the noisy and borderline examples problem in imbalanced classification by a re-sampling method with filtering［J］.Information Sciences，2015，291：184-203.

［5］孟東霞，李玉鑑.基于特征邊界欠采樣的不平衡數據處理方法［J］.統計與決策，2021，37（11）：30-33. （Meng Dongxia，Li Yujian.Unbalanced data processing method based on feature boundary undersampling[J].Statistics and Decision，2021，37（11）：30-33.）

［6］Arefeen M A，Nimi S T，Rahman M S.Neural network-based undersampling techniques［J］.IEEE Trans on Systems，Man，and Cybernetics：Systems，2022，52（2）：1111-1120.

［7］Cheng Ke，Zhang Chen，Yu Hualong，et al.Grouped SMOTE with noise filtering mechanism for classifying imbalanced data［J］.IEEE Access，2019，7：170668-170681.

［8］Chawla N V，Bowyer K W，Hall L O，et al.SMOTE：synthetic minority over-sampling technique［EB/OL］. （2016-03-31）.https：//www3.nd.edu/～dial/publications/chawla2002smote.pdf.

［9］He Haibo，Yang Bai，Garcia E A，et al.ADASYN：adaptive synthetic sampling approach for imbalanced learning［C］//Proc of IEEE International Joint Conference on Neural Networks.Piscataway，NJ：IEEE Press，2008.

［10］Han Hui，Wang Wenyuan，Mao Binghuan.Borderline-SMOTE：a new over-sampling method in imbalanced data sets learning［C］//Proc of International Conference on Intelligent Computing.2005.

［11］Barua S，Islam M M，Yao Xin，et al.MWMOTE-majority weighted minority oversampling technique for imbalanced data set learning［J］.IEEE Trans on Knowledge amp; Data Engineering，2013，26（2）：405-425.

［12］Tang Bo，He Haibo.KernelADASYN：kernel based adaptive synthetic data generation for imbalanced learning［C］//Proc of IEEE Congress on Evolutionary Computation.Piscataway，NJ：IEEE Press，2015：664-671.

［13］Asniar，Maulidevi N U，Surendro K.SMOTE-LOF for noise identification in imbalanced data classification［J］.Journal of King Saud University-Computer and Information Sciences，2021：doi.org/10.1016/j.jksuci.2021.01.014.

［14］Georgios D，Fernando B，Felix L.Improving imbalanced learning through a heuristic oversampling method based on K-means and SMOTE［J］.Information Sciences，2018，465：1-20.

［15］Bunkhumpornpat C，Sinapiromsaran K，Lursinsap C.DBSMOTE：density-based synthetic minority over-sampling technique［J］.Applied Intelligence，2012，36（3）：664-684.

［16］王芳，吳文通，張立立，等.鄰域自適應SMOTE算法研究［J］.計算機應用研究，2021，38（6）：1673-1677. （Wang Fang，Wu Wentong，Zhang Lili，et al.Research on neighborhood adaptive SMOTE algorithm［J］.Application Research of Computers，2021，38（6）：1673-1677.）

［17］Douzas G，Bacao F.Geometric SMOTE a geometrically enhanced drop-in replacement for SMOTE［J］.Information Sciences，2019，501：118-135.

［18］Pujol O，Masip D.Geometry-based ensembles：toward a structural characterization of the classification boundary［J］.IEEE Trans on Pattern Analysis and Machine Intelligence，2009，31（6）：1140-1146.

［19］Varando G，Bielza C，Larraaga P，et al.Decision boundary for discrete Bayesian network classifiers［J］.Journal of Machine Learning Research，2015，16：2725-2749.

［20］Cho J H，Song W，Choi H，et al.Hole filling method for depth image based rendering based on boundary decision［J］.IEEE Signal Processing Letters，2017，24（3）：329-333.

［21］Kaneda Y，Zhao Qiangfu.Inducing high performance and compact neural networks based on decision boundary making［J］.IEEE Trans on Electronics Information and Systems，2014，134（9）：1299-1309.

［22］Burduk R.Integration base classifiers based on their decision boundary［C］//Proc of International Conference on Artificial Intelligence and Soft Computing.2017：13-20.

［23］Lian Duan，Xiong Deyi，Lee J，et al.A local density based spatial clustering algorithm with noise［C］//Proc of IEEE International Conference on Systems，Man and Cybernetics.Piscataway，NJ：IEEE Press，2006.