王 亮，冶繼民

西安電子科技大學 數(shù)學與統(tǒng)計學院，西安 710126

1 引言

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

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

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

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

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

2 理論知識

2.1 SMOTE算法

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

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

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

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

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

2.2 DBSCAN算法

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

定義1（Eps-鄰域） 對于xi∈D,xi的Eps-鄰域包含數(shù)據(jù)集D中與xi的距離不大于Eps的數(shù)據(jù)點，即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等傳統(tǒng)過采樣算法存在的問題，如：忽略類內(nèi)不平衡現(xiàn)象、合成的少數(shù)類樣本意外入侵多數(shù)類樣本區(qū)域以及合成高度相似的新樣本，本文先將SMOTE 算法進行改進，并結(jié)合DBSCAN 聚類算法，提出了DB-MCSMOTE過采樣算法。

3.1 簇密度分布函數(shù)和過采樣權(quán)重

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

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

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

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

3.2 改進的SMOTE算法

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

MCSMOTE算法具體的過采樣過程如圖1所示：分別從近質(zhì)心集合Xmin和遠質(zhì)心集合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 個分布均勻的新少數(shù)類樣本。

圖1 MCSMOTE合成少數(shù)類樣本示意圖

3.3 DB-MCSMOTE算法

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

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

4 實驗設(shè)計與結(jié)果分析

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

4.1 數(shù)據(jù)集

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

表1 數(shù)據(jù)集的基本信息

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

4.2 評價指標

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

圖2 二維合成數(shù)據(jù)集

表2 混淆矩陣

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

4.3 實驗環(huán)境設(shè)置

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

4.4 實驗結(jié)果與分析

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

圖3 SMOTE過采樣結(jié)果

圖4 K-means SMOTE過采樣結(jié)果

圖5 DB-MCSMOTE過采樣結(jié)果

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

表3 KNN分類器實驗結(jié)果對比

表4 SVM分類器實驗結(jié)果對比

表5 RF分類器實驗結(jié)果對比

5 結(jié)束語

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