整合DBSCAN和改進SMOTE的過采樣算法

王 亮，冶繼民

西安電子科技大學 數學與統計學院，西安 710126

1 引言

不平衡數據集是指數據集中某些類的樣本個數明顯小于其他類的數據集[1]。在二分類問題中，定義擁有較多樣本數量的類別為負類，將樣本數量少的類別稱為正類[2]。目前，在實際應用中不平衡數據集的分類問題普遍存在，比如：銀行欺詐檢測[3]、文本分類[4]、醫療診斷[5]以及衛星圖像中的溢油識別等[6]。在類不平衡數據集的分類問題中，由于少數類樣本的誤分代價更大，所以少數類樣本比其他類別數據更重要[7]。傳統分類算法對不平衡數據集中多數類樣本的識別率較高，易忽略少數類樣本，從而削弱分類器對少數類數據的預測能力，降低分類器的分類性能[8]。因此，如何有效地解決不平衡數據集的分類問題成為了數據挖掘領域中的重要研究內容。

數據集的不平衡狀態可以細分為兩種：類間不平衡和類內不平衡[9]。其中類間不平衡是指數據集中各個類別之間樣本數量的不平衡，而類內不平衡是指在某一類樣本空間內部數據分布密度的不均衡，即形成了多個具有相同類別、不同數據分布的子類[10]。

目前，解決不平衡數據集分類問題的方法主要分為兩個方面：算法層面和數據層面[11-12]，前者對標準的分類算法進行改進，使分類器適應不平衡數據集下的分類[13]；后者則是對數據進行處理，減少數據集的不平衡程度，從而使分類器能夠在平衡的數據集上進行學習[14]，其中最為常見的方法是數據層面的欠采樣和過采樣技術[15]。將多數類樣本數量減少到與少數類樣本數量大致相等的方法稱為欠采樣，例如：隨機欠采樣是隨機刪除多數類樣本，以平衡數據集中不同類別樣本的個數，但是，此方法容易丟失多數類樣本中有價值的分類信息[16]。與欠采樣相反，過采樣技術是通過增加少數類樣本的數量使數據集達到平衡的狀態[17]。其中最具有代表性的過采樣方法是Chawla 等人提出的SMOTE 算法[18]，SMOTE 在少數類樣本和其相鄰少數類鄰居的連線上引入合成樣本，通過人為構造新少數類樣本從而消除原始數據集的類間不平衡度。但是，SMOTE 算法忽略了少數類樣本類內不平衡現象的存在，并且易受噪聲的影響，擴展少數類的分類區域。當不平衡度較高時，合成的新少數類樣本點會與原始數據高度相似，甚至重復，很難為分類器提供新的分類信息。

基于SMOTE過采樣算法，Han等人[19]提出了Borderline-SMOTE 算法，其核心思想是重點對位于分類邊界的少數類樣本進行過采樣，加強對分類邊界樣本的學習以提高分類性能。He等人[20]提出的ADASYN算法根據數據分布自動確定每個少數類樣本需要生成新樣本的數量，擁有越多多數類鄰居的少數類樣本生成更多的新樣本。相比于SMOTE算法，Borderline-SMOTE和ADASYN算法只對樣本的分布進行了細致劃分，因此依然存在SMOTE算法出現的問題。Douzas等人[21]提出了K-means SMOTE 算法，該算法首先使用K-means 算法對整體數據集聚類，然后僅在少數類樣本數量大于多數類樣本數量的簇中使用SMOTE過采樣算法。該算法可以有效降低噪聲的影響，抑制合成的少數類樣本入侵多數類區域。然而，K-means SMOTE算法過濾了少數類樣本數量占比小的簇，這些簇中包含的少數類樣本極有可能位于分類邊界，包含了大量有價值的分類信息，并且使用SMOTE 算法進行過采樣，合成的少數類樣本之間依然高度相似，甚至重復。

針對以上過采樣算法存在的問題，本文提出了DB-MCSMOTE算法。首先，對少數類樣本使用DBSCAN算法聚類，過濾噪聲樣本；其次，根據本文提出的簇密度分布函數，計算各個簇需要生成的樣本數量；最后，在每個簇中使用改進的SMOTE算法（MCSMOTE）進行過采樣，得到類間和類內均達到平衡的新數據集，并且合成的少數類樣本具有多樣性。

2 理論知識

2.1 SMOTE算法

SMOTE算法的基本思想是：根據采樣倍率N%，在特征空間中通過對少數類樣本點和其相鄰的k個少數類鄰居之間進行隨機線性插值，從而合成新的少數類樣本。具體步驟如下：

（1）根據歐式距離，使用KNN算法搜索每個少數類樣本xi的k個近鄰，記為：y1,y2,…,yk，其中k值的選取默認為5。

（2）在xi的k個少數類鄰居中隨機選擇N個，并根據以下公式生成新樣本xg：

其中，g=1,2,…,N,j=1,2,…,k，rand(0,1)表示0到1之間的隨機數。

（3）將生成的新樣本全部加入原始訓練數據中，消除訓練數據集的不平衡度。

2.2 DBSCAN算法

DBSCAN 是一種常用的密度聚類算法，它利用樣本點的局部密度來劃分簇，不需要提前設定簇的個數k，同一簇中的樣本點是緊密相連的。假設數據集D={x1,x2,…,xm} ，給出如下關鍵定義[22]：

定義1（Eps-鄰域） 對于xi∈D,xi的Eps-鄰域包含數據集D中與xi的距離不大于Eps的數據點，即NEps(xi)={xj∈D|dist(xi,xj)≤Eps} 。

定義2（核心點）對于xi∈D，若xi的Eps-鄰域中至少有MinPts個點，則稱點xi為核心點。

定義3（直接密度可達）對于xi,xj∈D，若滿足條件：xi是核心點，且xj∈NEps(xi)，則稱xj可由xi直接密度可達。

定義4（密度可達）如果存在一系列的點y1,y2,…,yl，滿足xi=y1，xj=yl，且yi+1是由yi直接密度可達的，則稱xj可由xi密度可達。

定義5（密度相連）若存在樣本點y，使得xi和xj均由y密度可達，則稱xi和xj密度相連。

DBSCAN 算法將一系列密度相連的樣本點的最大集合定義為一個聚類簇，不屬于任何簇的一組樣本點被定義為噪聲集。不同于通常只適用凸樣本集的K-means算法[23]，DBSCAN 算法不僅可以挖掘任意形狀的簇，還可以有效過濾噪聲點[24]。

3 整合DBSCAN和改進SMOTE的過采樣算法

針對SMOTE等傳統過采樣算法存在的問題，如：忽略類內不平衡現象、合成的少數類樣本意外入侵多數類樣本區域以及合成高度相似的新樣本，本文先將SMOTE 算法進行改進，并結合DBSCAN 聚類算法，提出了DB-MCSMOTE過采樣算法。

3.1 簇密度分布函數和過采樣權重

假設原始少數類樣本集合經過DBSCAN算法聚類之后，得到m個簇：C1,C2,…,Cm。為了解決類內不平衡的問題，對于每個聚類簇Ci，本文定義了簇密度分布函數和過采樣權重。

定義6（簇密度分布函數）簇Ci的密度分布函數定義為簇Ci中所包含樣本點的個數與其所包含樣本點構成的超球體體積的比例型函數。簇Ci的密度分布函數公式如下：

其中，NCi表示簇Ci中樣本點的個數；volCi(Sd(ri))表示簇Ci中樣本點構成的d維超球體的體積；ri表示簇Ci中離質心ui最遠的樣本點到質心ui的歐式距離；質心。簇Ci的密度分布函數值越大，代表簇Ci中的數據分布越密集。

定義7（過采樣權重）簇Ci的過采樣權重定義為其密度分布函數的倒數除以所有簇密度分布函數倒數的總和。簇Ci的過采樣權重公式如下：

3.2 改進的SMOTE算法

本文提出了一種改進的SMOTE 過采樣算法，即中點質心合成少數類過采樣算法（MCSMOTE），其基本思想是：原始少數類樣本集合經過DBSCAN 算法聚類后得到m個簇：C1,C2,…,Cm，在各個簇中選擇相距較遠的樣本點進行兩兩配對，并在配對之后的樣本點連線的中點處合成新樣本，即公式（1）中rand(0,1)固定為0.5。隨后不斷地在合成樣本和其相鄰的父代樣本點之間連線的中點處合成新子代樣本，使合成的新樣本不斷靠近質心。具體步驟如算法1。

MCSMOTE算法具體的過采樣過程如圖1所示：分別從近質心集合Xmin和遠質心集合Xmax中選擇第一個樣本點x1和xmid+1。第一輪中，MCSMOTE 算法在兩個相距較遠的樣本點x1和xmid+1連線的中點處合成新樣本。在第二輪中，MCSMOTE 算法分別在第一輪合成樣本和其相鄰的父代樣本x1,xmid+1的連線中點處合成新樣本，即在x1和xmid+1連線的四分位點處合成新樣本。在第三輪中，MCSMOTE算法分別在第二輪合成樣本和其相鄰父代樣本的連線中點處合成新樣本，即在x1和xmid+1連線的八分位點處合成新樣本。以此類推：在第n輪中，MCSMOTE 算法將在x1和xmid+1的連線上共生成2n-1 個分布均勻的新少數類樣本。

圖1 MCSMOTE合成少數類樣本示意圖

3.3 DB-MCSMOTE算法

DB-MCSMOTE算法主要包括三個步驟：DBSCAN聚類、計算簇密度分布函數和采樣權重、MCSMOTE 合成新少數類樣本。具體步驟如算法2。

相比于SMOTE 等傳統算法，DB-MCSMOTE 算法引入簇密度分布函數和采樣權重的定義，因此該算法可以有效解決少數類樣本類內不平衡的問題。其次，DB-MCSMOTE 算法過濾了噪聲樣本集并且在各個少數類簇中不斷產生靠近該簇質心的新少數類樣本點，有效克服了SMOTE 算法意外擴展少數類分類區域的弊端。最后，DB-MCSMOTE 算法沒有使用KNN 算法搜索少數類樣本的近鄰，而是在兩個相距較遠的樣本點的連線上不斷合成新樣本，因此可以提高合成少數類樣本的多樣性，避免生成高度相似，甚至重復的新少數類樣本，為分類器提供更多有效的分類信息。

4 實驗設計與結果分析

為了評估上述算法的性能，本文將UCI庫中九個實際數據集和一個二維人工合成不平衡數據集作為實驗數據集，將SMOTE、Borderline-SMOTE、ADASYN、K-means SMOTE 和 DB-MCSMOTE 五種過采樣算法分別應用在實驗數據集上，得到新的平衡數據集，并使用K近鄰（KNN）、支持向量機（SVM）和隨機森林（RF）進行分類，以評估每種過采樣算法的性能。KNN、SVM和RF 算法已廣泛應用于不平衡數據集的分類研究中[25-26]，其中RF 是一種經典的集成算法。RF 是由多個分類決策樹組成的分類器，每一個基分類器中采用的獨立同分布的隨機向量決定了樹的生長過程，最終通過多數投票機制來確定RF分類器的輸出結果[27]。

4.1 數據集

（1）本文從UCI數據庫中選取的九個實際數據集的詳細信息如表1所示。在具有多個類別的數據集中，選擇一類樣本作為少數類，并將其他類別樣本組合成多數類。其中Yeast-02579 是將Yeast 數據集中部分類別（ME1，EXC，POX）和（MIT，CYT，ME3，VAC，ERL）分別合并為少數類和多數類。在二分類問題中不平衡度IR的定義如下：

表1 數據集的基本信息

（2）為了更加直觀闡明DB-MCSMOTE 算法的優勢，本文使用人工合成的二維不平衡數據集，如圖2 所示，不平衡度IR=3.2。該二維合成數據集不僅存在類間不平衡，并且在少數類類內也存在不平衡現象。與此同時，在該數據集的少數類樣本中也存在著噪聲。

4.2 評價指標

機器學習中的評價指標都是建立在混淆矩陣（見表2）上，其中：TP和TN分別代表正確分類的正類（少數類）和負類（多數類）樣本數量，FP和FN分別代表錯誤分類的負類和正類樣本數量。

圖2 二維合成數據集

表2 混淆矩陣

由于不平衡學習旨在提高少數類樣本的分類性能，所以在評估分類性能的各種傳統評價指標中，當類分布不均勻時，并非所有評估指標都適用，目前已有一些評估指標被專門用在不平衡數據集的分類問題中。本文選擇F-value，G-mean和AUC三個評價指標來評估分類器的性能，其中AUC表示ROC曲線下各部分的面積之和，它表示分類器將隨機測試的正實例排序高于隨機測試的負實例的概率。F-value和G-mean的定義如下：

4.3 實驗環境設置

本文使用Python語言，Spyder集成開發環境對各種算法進行仿真實驗。根據原文獻，將SMOTE、Borderline-SMOTE、ADASYN算法的近鄰數k取值為5，Borderline-SMOTE 算法的參數m設置為10。K-means SMOTE算法參數k和knn的取值范圍分別為k∈{2,20,50,100,250,500} 、knn∈{3,5,20} 。DB-MCSMOTE算法的參數Eps,MinPts通過k-距離曲線（k-dist graph）確定[22]。KNN算法近鄰數k的取值為k∈{3,5,8} 。SVM算法中核函數選擇高斯徑向基函數（RBF kernel），懲罰因子C和核函數參數gamma取值范圍為C∈{20,21,…,210},gamma∈{1 0-5,10-4,…,102} 。RF 算法中決策樹的數量N_tree的取值范圍為N_tree∈{1 0,50,100,200,500,800} 。為了獲得所有分類器和過采樣器的最佳結果，利用網格搜索算法確定最優參數組合。實驗中使用十次十折（10-fold）交叉驗證的平均值作為最終性能度量的結果。

4.4 實驗結果與分析

（1）合成數據集實驗結果：本文分別利用SMOTE、K-means SMOTE 和 DB-MCSMOTE 三種算法對二維合成數據集進行過采樣，實驗結果如圖3、圖4和圖5所示。通過對比實驗結果，得到如下結論：①在使用SMOTE 算法之后，降低了數據集的類間不平衡度。但是由于原始少數類樣本中存在噪聲，新合成的少數類樣本意外入侵多數類樣本區域，進一步放大了數據中的噪聲，并且新生成的樣本之間高度相似，甚至與原始少數類樣本重疊。②K-means SMOTE 算法有效過濾了噪聲，抑制了SMOTE 算法意外擴展少數類樣本分類區域的現象。但是新合成的少數類樣本之間依然高度相似，甚至重復。③DB-MCSMOTE 算法不僅克服了類間不平衡現象，也有效解決了少數類樣本類內不平衡的現象。并且該算法不僅能避免新生成的少數類樣本入侵多數類樣本區域，降低噪聲的影響，而且合成的新樣本具有多樣性，為分類器提供了更多的分類信息。

圖3 SMOTE過采樣結果

圖4 K-means SMOTE過采樣結果

圖5 DB-MCSMOTE過采樣結果

（2）實際數據集實驗結果：本文使用KNN、SVM 和RF分類器對原始數據集和經過采樣之后的平衡數據集進行分類，實驗結果見表3、表4 和表5，其中F-value、G-mean和AUC取得最優值的數據用黑色粗體表示。對于每個數據集中的每個評價指標通過得分制來對各種算法進行排序，分值設置為1到6，其中性能最好的算法得6 分，最差的得1 分。針對未經過采樣和五種過采樣算法，對于每個數據集中的三種評價指標的平均得分再取均值，可以得到每種算法的最終平均得分。通過對比實驗結果可以得出如下結論：①在相同的數據集中，使用RF分類器可以獲得優于KNN和SVM分類器的分類效果，這是因為RF 分類器將多個單一的弱分類器集合成一個強分類器，并且由于“隨機性”的引入，使得RF分類器不易過擬合，同時具有較強的抗噪聲能力。②相比于只對原始數據集使用KNN、SVM 和RF 分類器進行分類，使用SMOTE、Borderline-SMOTE、ADASYN、K-means SMOTE 和 DB-MCSMOTE 過采樣算法可以不同程度地提高分類器對數據集的分類性能。并且相比于SMOTE 等傳統過采樣算法，使用DB-MCSMOTE算法可更大幅度提升分類器的分類性能，即DB-MCSMOTE算法可以獲得最高的最終平均得分。因此DB-MCSMOTE算法不僅可以提高KNN 等單一分類器的性能，同時也可以提升RF 集成分類器對不平衡數據集的分類效果。③ 在Pima、Segment、Vehicle、Yeast1和Yeast-02579五個數據集中，使用DB-MCSMOTE算法可以同時取得最優的F-value值、G-mean值和AUC值，這是因為上述實際數據集不僅存在類間不平衡，并且在少數類類內也存在樣本分布的不均衡，SMOTE 等傳統過采樣算法未考慮少數類類內樣本的分布情況。④在所有數據集中，使用DB-MCSMOTE 算法在Yeast-02579 數據集上取得的F-value值和G-mean值相比于SMOTE 等算法的提升幅度最大，這是因為Yeast-02579 數據集的不平衡度最高，需要合成更多新少數類樣本，SMOTE等算法合成的新樣本之間高度相似，而DB-MCSMOTE算法合成具有多樣性的新少數類樣本，可以為分類器提供更多的分類信息。以上結果總體來看，本文提出的DBMCSMOTE 過采樣算法可以有效提升分類器對少數類樣本和整體數據集的分類性能。

表3 KNN分類器實驗結果對比

表4 SVM分類器實驗結果對比

表5 RF分類器實驗結果對比

5 結束語

不平衡數據集的分類問題廣泛存在于實際應用中，對訓練數據中的少數類樣本進行過采樣是一種有效的解決方法。本文對SMOTE算法進行改進，并結合DBSCAN聚類算法，提出了DB-MCSMOTE過采樣算法。該算法首先使用DBSCAN 算法對少數類樣本聚類，過濾數據集中的噪聲；其次，通過本文提出的簇密度分布函數計算各個簇的采樣權重，確定每個簇中合成新樣本的數量；最后，使用改進的SMOTE過采樣算法（MCSMOTE）合成新少數類樣本。實驗結果表明，DB-MCSMOTE算法可以有效克服SMOTE等傳統過采樣算法存在忽略類內不平衡、合成少數類樣本入侵多數類區域以及合成樣本高度相似等問題，并且可以有效提高分類器對少數類樣本和整體數據集的分類性能。如何利用聚類算法將數據集進一步細分為噪聲樣本、邊界樣本和安全區樣本，并重點對邊界樣本進行過采樣是未來需要進一步研究的方向。