董永峰，董彥琦，張亞娟

（1.河北工業(yè)大學(xué) 人工智能與數(shù)據(jù)科學(xué)學(xué)院，天津 300401；2.河北省大數(shù)據(jù)計(jì)算重點(diǎn)實(shí)驗(yàn)室，天津 300401）

0 引言

不平衡數(shù)據(jù)是指數(shù)據(jù)集中某一類別的樣本數(shù)量明顯少于其他類別的樣本數(shù)量，其中樣本數(shù)量較少的一類稱為少數(shù)類，樣本數(shù)量較多的一類稱為多數(shù)類。在實(shí)際應(yīng)用中，不平衡數(shù)據(jù)是經(jīng)常存在的，特別是在網(wǎng)絡(luò)安全、醫(yī)療診斷、客戶流失預(yù)測等領(lǐng)域[1]。以隨機(jī)森林為代表的傳統(tǒng)分類器在處理不平衡數(shù)據(jù)分類問題時(shí)，分類結(jié)果往往會(huì)傾向于多數(shù)類，而忽略少數(shù)類，從而導(dǎo)致算法性能大幅下降[2]。為了提高分類器對(duì)不平衡數(shù)據(jù)的分類性能，學(xué)者們主要從算法和數(shù)據(jù)層面進(jìn)行了改進(jìn)。算法層面的改進(jìn)主要是結(jié)合不平衡數(shù)據(jù)集的內(nèi)在特征，在現(xiàn)有分類算法基礎(chǔ)上進(jìn)行改進(jìn)或設(shè)計(jì)新的分類算法，以適應(yīng)不平衡數(shù)據(jù)進(jìn)行分類的需要，主要包括代價(jià)敏感學(xué)習(xí)[3]、單類學(xué)習(xí)[4]和特征選擇[5]等方法。數(shù)據(jù)層面的改進(jìn)主要是結(jié)合重采樣技術(shù)，使不平衡數(shù)據(jù)集在訓(xùn)練之前就趨于平衡，再利用分類器進(jìn)行訓(xùn)練，重采樣技術(shù)主要包含欠采樣[6]和過采樣[7]兩種方法。以上方法中使用最為廣泛的是文獻(xiàn)[8]中提出的SMOTE算法，該算法在少數(shù)類樣本及其近鄰樣本之間合成新樣本，但SMOTE算法沒有對(duì)少數(shù)類樣本進(jìn)行區(qū)別性的選擇，因此在合成新樣本時(shí)存在盲目性與邊緣化等問題，眾多學(xué)者對(duì)其進(jìn)行了改進(jìn)。

文獻(xiàn)[9]中提出了Borderline-SMOTE算法，該算法只對(duì)決策邊界附近的少數(shù)類樣本進(jìn)行過采樣，從而改善了SMOTE的盲目性，但會(huì)丟失其他少數(shù)類樣本所包含的信息。文獻(xiàn)[10]中提出了ADASYN算法，該算法規(guī)定每個(gè)少數(shù)類樣本合成新樣本的個(gè)數(shù)與模型學(xué)習(xí)該樣本的困難程度成正比，但學(xué)習(xí)難度越大的樣本是噪聲的可能性也越大，在其周圍生成新樣本會(huì)進(jìn)一步放大數(shù)據(jù)集中的噪聲。文獻(xiàn)[11]中提出了ISMOTE算法，該算法在以少數(shù)類樣本為中心，以該樣本到其最近鄰樣本之間的距離為半徑的n維球體內(nèi)進(jìn)行過采樣，從而消除了少數(shù)類樣本分布的限制，但在插值的過程中容易造成新樣本與多數(shù)類樣本的重疊，進(jìn)一步加大分類難度。文獻(xiàn)[12]中提出了KM-SMOTE算法，該算法對(duì)數(shù)據(jù)集中的少數(shù)類樣本進(jìn)行聚類，在簇心及對(duì)應(yīng)簇樣本之間生成新樣本，但在插值的過程中會(huì)使新樣本集中分布于簇心周圍，導(dǎo)致樣本之間的重疊。為了克服SMOTE算法及以上改進(jìn)算法的不足，論文基于聚類劃分和重心牽引的思想提出了一種改進(jìn)算法BSMOTE，該算法有效改善了SMOTE算法生成新樣本時(shí)存在的盲目性和邊緣化的問題，從而保證了新樣本的有效性，同時(shí)由于新樣本的加入使不平衡數(shù)據(jù)集在訓(xùn)練之前就趨于平衡，再利用隨機(jī)森林進(jìn)行訓(xùn)練，從而提升了傳統(tǒng)分類器在不平衡數(shù)據(jù)集上的分類性能。

1 SMOTE算法

合成少數(shù)類過采樣技術(shù)（Synthetic Minority Over-sampling Technique，SMOTE）是基于傳統(tǒng)隨機(jī)過采樣的一種改進(jìn)算法，該算法避免了數(shù)據(jù)集內(nèi)少數(shù)類樣本大量重復(fù)出現(xiàn)，有效降低了過擬合問題出現(xiàn)的機(jī)率。SMOTE算法流程如下。

輸入：不平衡數(shù)據(jù)集D，近鄰數(shù)K，采樣率N。

輸出：平衡數(shù)據(jù)集Dnew。

1）篩選出原始數(shù)據(jù)集D中的全部少數(shù)類樣本，構(gòu)成少數(shù)類樣本集Dmin，其余樣本構(gòu)成多數(shù)類樣本集Dmaj。

2）對(duì)于Dmin中少數(shù)類樣本xi，計(jì)算它到Dmin中所有樣本的距離，得到其K近鄰，從其K近鄰中任取一個(gè)樣本xj，xi與xj之間的距離d(xi,xj)計(jì)算公式如式（1）所示：

式中：xi=(xi1,xi2,…,xin)，xj=(xj1,xj2,…,xjn)表示2個(gè)n維屬性的數(shù)據(jù)樣本。

3）計(jì)算樣本xi與xj各個(gè)對(duì)應(yīng)屬性上的屬性值之差，將差值乘以區(qū)間（0，1）內(nèi)的一個(gè)隨機(jī)數(shù)，再加上樣本xi各個(gè)對(duì)應(yīng)的屬性值，即可生成一個(gè)新的少數(shù)類樣本xnew，具體計(jì)算公式如式（2）所示：

式中：rand（0，1）表示區(qū)間（0，1）上的一個(gè)隨機(jī)數(shù)。

4）循環(huán)執(zhí)行步驟2）～3），算法終止條件為達(dá)到預(yù)先設(shè)置的采樣倍率N，將生成的全部少數(shù)類樣本加入原始數(shù)據(jù)集D中，得到平衡數(shù)據(jù)集Dnew。

2 SMOTE的改進(jìn)算法：BSMOTE

2.1 BSMOTE算法原理

SMOTE算法認(rèn)為在距離相近的少數(shù)類樣本之間生成的新樣本仍為少數(shù)類，為了確保新樣本的有效性，未改進(jìn)的SMOTE算法在插值過程中需要找到少數(shù)類樣本的K個(gè)最近鄰，并在其與隨機(jī)的一個(gè)近鄰樣本之間生成新樣本，但該算法在插值過程中未考慮少數(shù)類樣本的分布，具有一定的盲目性。SMOTE算法生成新樣本的示意圖如圖1a）所示，圖中圓形表示多數(shù)類樣本，空心五角星表示少數(shù)類樣本，實(shí)心五角星表示新合成的少數(shù)類樣本。假設(shè)采用SMOTE算法對(duì)少數(shù)類樣本A進(jìn)行過采樣，該算法首先在樣本A的5個(gè)近鄰少數(shù)類樣本中隨機(jī)選擇了樣本B，然后在樣本A和樣本B之間線性插值生成新的少數(shù)類樣本A1，但從圖中可知新樣本A1位于多數(shù)類樣本較多的區(qū)域，因此該樣本是一個(gè)噪聲樣本，并不會(huì)有助于分類算法進(jìn)行訓(xùn)練。

同時(shí)，SMOTE算法還存在樣本分布邊緣化的問題，如果一個(gè)少數(shù)類樣本處在多數(shù)類與少數(shù)類樣本的決策邊界，則由此樣本和近鄰樣本生成的新樣本也將處在這個(gè)邊界，且越來越邊緣化。如圖1a）所示，少數(shù)類樣本B和少數(shù)類樣本C均處在多數(shù)類與少數(shù)類樣本的決策邊界，采用SMOTE算法在2個(gè)樣本之間生成的新樣本C1也處在這個(gè)邊界，從而將邊界模糊化，加大了分類算法進(jìn)行分類的難度。

圖1 a）SMOTE算法生成新樣本的示意圖；b）BSMOTE算法生成新樣本的示意圖Fig.1 a)Schematic diagram of SMOTE algorithm generating new samples;b)Schematic diagram of BSMOTE algorithm generating new samples

針對(duì)以上2個(gè)問題，論文提出了改進(jìn)算法BSMOTE，該算法首先采用K-means聚類算法對(duì)少數(shù)類樣本進(jìn)行聚類產(chǎn)生k個(gè)簇，以此確定少數(shù)類樣本的分布情況，同時(shí)基于距離的聚類劃分使得簇中樣本的相似性較高，故該算法省去了SMOTE算法求解少數(shù)類K近鄰的步驟，直接在各個(gè)簇中選擇少數(shù)類樣本以生成新樣本。然后在聚類產(chǎn)生的各個(gè)簇Ci(i=1,2,…,k)中隨機(jī)選取3個(gè)樣本點(diǎn)構(gòu)造三角形，計(jì)算其重心樣本數(shù)據(jù)，在三角形重心與頂點(diǎn)之間隨機(jī)生成新的少數(shù)類樣本，新樣本會(huì)向所在三角形的重心位置靠攏并遠(yuǎn)離決策邊界，從而使新樣本的生成過程具有一定的方向性。最后將不斷生成的新樣本加入到原始數(shù)據(jù)集D中以降低不平衡率，直至數(shù)據(jù)集中的少數(shù)類樣本數(shù)量不小于多數(shù)類樣本數(shù)量時(shí)終止算法，得到平衡數(shù)據(jù)集Dnew。

BSMOTE算法生成新樣本的示意圖如圖1b）所示，圖中圓形表示多數(shù)類樣本，空心五角星表示少數(shù)類樣本，實(shí)心五角星表示新合成的少數(shù)類樣本，橢圓虛線表示BSMOTE算法采用K-means對(duì)少數(shù)類樣本聚類得到的2個(gè)簇，生成新樣本僅在各個(gè)簇中進(jìn)行，由此避免了SMOTE算法生成新樣本的盲目性問題。圖中的實(shí)心點(diǎn)表示少數(shù)類樣本B、C、D所構(gòu)成三角形的重心，BSMOTE算法在三角形重心與頂點(diǎn)之間生成新的少數(shù)類樣本，因此生成的新樣本會(huì)向重心位置靠攏，從而遠(yuǎn)離決策邊界，有效克服了SMOTE算法生成新樣本的邊緣化問題。

圖2 BSMOTE算法流程圖Fig.2 Flow chart of BSMOTE algorithm

2.2 BSMOTE算法設(shè)計(jì)

在樣本類別不平衡問題中，通常將數(shù)量較少的少數(shù)類樣本視為正類樣本，數(shù)量占優(yōu)的多數(shù)類樣本視為負(fù)類樣本。BSMOTE算法流程圖如圖2所示，算法流程如下。

輸入：不平衡數(shù)據(jù)集D，聚類個(gè)數(shù)k。

輸出：平衡數(shù)據(jù)集Dnew。

1）篩選出原始數(shù)據(jù)集D中的正類樣本，構(gòu)成正類樣本集Dmin，其余樣本構(gòu)成負(fù)類樣本集Dmaj。

2）在正類樣本集Dmin中隨機(jī)選取k個(gè)樣本，作為首次聚類的中心點(diǎn)。

3）采用公式（1）計(jì)算其余各樣本到每個(gè)聚類中心點(diǎn)的距離d(xi,xj)，并將該樣本劃分到與之最近的聚類中心所在的簇Ci(i=1,2,…,k)中。

4）重新計(jì)算各簇的聚類中心，重復(fù)Step2調(diào)整所有樣本的劃分，聚類中心更新迭代公式如式（3）所示：

式中：mi為簇Ci的聚類中心；|Ci|為簇Ci的樣本數(shù)量；xp=(xp1,xp2,…,xpn)表示簇Ci內(nèi)n維屬性的數(shù)據(jù)樣本。

5）計(jì)算正類樣本集Dmin中全部樣本及其所屬簇的聚類中心之間距離的平方和，即誤差平方和SSE，計(jì)算公式如式（4）所示：

6）迭代執(zhí)行步驟3）～5），直到聚類劃分不再發(fā)生變化或者SSE值收斂，至此聚類結(jié)束得到k個(gè)簇Ci(i=1,2,…,k)。

7）在任意一簇Cj中隨機(jī)選取的3個(gè)正類樣本xr，xs，xt構(gòu)造三角形，計(jì)算其重心樣本向量xB，重心樣本xB計(jì)算公式如式（5）所示：

式中：xB表示由xj(j=r,s,t)所構(gòu)成三角形的n維重心向量。

8）在三角形重心xB與頂點(diǎn)xj(j=r,s,t)之間隨機(jī)生成一個(gè)新的正類樣本xnew，將其加入正類樣本集Dmin，生成的新樣本xnew計(jì)算公式如式（6）所示：

式中：xnew表示由三角形頂點(diǎn)xj(j=r,s,t)及重心xB生成的n維新向量。

9）在k個(gè)簇Ci(i=1,2,…,k)中循環(huán)執(zhí)行步驟7）～8），算法終止條件為正類樣本個(gè)數(shù) |Dmin|不小于負(fù)類樣本個(gè)數(shù) |Dmaj|。

10）合并正類樣本集Dmin與負(fù)類樣本集Dmaj，得到平衡數(shù)據(jù)集Dnew。

3 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

論文采用KEEL數(shù)據(jù)庫的7個(gè)不平衡數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，分別為new-thyroid2，ecoli1，ecoli2，ecoli3，glass0，wisconsin和vehicle0。表1中描述了數(shù)據(jù)集的基本特征，其中包括總樣本個(gè)數(shù)、屬性個(gè)數(shù)、負(fù)類樣本個(gè)數(shù)、正類樣本個(gè)數(shù)和不平衡比率。

3.2 實(shí)驗(yàn)設(shè)計(jì)

論文在Window 10（64位）操作系統(tǒng)，Intel Core i7-7700HQ CPU@2.8 GHz，8GB RBM的環(huán)境下使用Python進(jìn)行實(shí)驗(yàn)。為了驗(yàn)證BSMOTE算法的有效性，對(duì)比了原始數(shù)據(jù)集和經(jīng)過SMOTE算法、ADASYN算法、Borderline-SMOTE（簡記為BL-SMOTE）算法、ISMOTE算法以及KM-SMOTE算法處理后的數(shù)據(jù)集對(duì)分類器分類性能的影響。分類器采用傳統(tǒng)機(jī)器學(xué)習(xí)算法隨機(jī)森林（Random Forest，RF），該算法是一個(gè)由決策樹分類器集合所構(gòu)成的集成學(xué)習(xí)模型，有著良好的泛化性和魯棒性。RF首先采用Bootstrap有放回抽樣的方法從數(shù)據(jù)集D中隨機(jī)采樣，生成s個(gè)子數(shù)據(jù)集Di(i=1,2,…,s)；然后基于每個(gè)Di訓(xùn)練決策樹模型hi(x)，在樹生成的過程中，隨機(jī)從M個(gè)屬性中選擇m個(gè)屬性參與節(jié)點(diǎn)分裂（m＜M且m值恒定）；而后計(jì)算每個(gè)屬性值的基尼系數(shù)，選擇基尼系數(shù)最小的屬性作為分裂節(jié)點(diǎn)進(jìn)行分裂，由此生成s棵決策樹；最后采用多數(shù)表決機(jī)制集成s棵決策樹的預(yù)測結(jié)果得到待測樣本x的預(yù)測標(biāo)簽。在本實(shí)驗(yàn)中，SMOTE、ADASYN和BL-SMOTE中正類樣本的近鄰個(gè)數(shù)K為5，KM-SMOTE和BSMOTE中正類樣本的聚類個(gè)數(shù)k為5，森林中決策樹的數(shù)量s為100，每棵決策樹選用的屬性數(shù)量m為log2M+1。

表1 數(shù)據(jù)集特征Tab.1 Data set features

3.3 評(píng)價(jià)指標(biāo)

對(duì)于不平衡數(shù)據(jù)集的二分類問題，傳統(tǒng)的性能評(píng)價(jià)指標(biāo)準(zhǔn)確率、靈敏度、特異度和查準(zhǔn)率并不能很好地反映出一個(gè)分類算法的性能，論文將選取不平衡數(shù)據(jù)分類的常用評(píng)價(jià)指標(biāo)G-mean值、F-measure值和ROC曲線的量化標(biāo)準(zhǔn)AUC值來反映模型性能的優(yōu)劣，為方便指標(biāo)描述，首先建立混淆矩陣如表2所示。

其中，TP（True Positive）表示模型正確分類的正類樣本數(shù)量，F(xiàn)N（False Negative）表示模型錯(cuò)誤分類的正類樣本數(shù)量，F(xiàn)P（False Positive）表示模型錯(cuò)誤分類的負(fù)類樣本數(shù)量，TN（True Negative）表示模型正確分類的負(fù)類樣本數(shù)量。

幾何均值（G-mean）綜合反映了算法模型對(duì)正、負(fù)兩類樣本的分類性能，計(jì)算公式如式（7）所示：

表2 二分類問題混淆矩陣Tab.2 Confusion matrix of binary classification problem

只有當(dāng)正、負(fù)兩類樣本的分類精度都處于較高的水準(zhǔn)時(shí)，G-mean才會(huì)較大，該指標(biāo)的數(shù)值越大，模型的總體分類效果越好。

正類檢驗(yàn)值（F-measure）綜合反映了算法模型對(duì)少數(shù)類樣本的分類性能，計(jì)算公式如式（8）所示：

該指標(biāo)的數(shù)值越大，模型對(duì)少數(shù)類樣本的分類效果越好。

受試者工作特征曲線（Receiver Operating Characteristic，ROC）上點(diǎn)的坐標(biāo)通過模型在獲取分類結(jié)果時(shí)的概率閾值進(jìn)行計(jì)算，不同的概率閾值對(duì)應(yīng)不同的坐標(biāo)點(diǎn)，其中點(diǎn)的橫坐標(biāo)表示負(fù)類樣本分類錯(cuò)誤的概率（False Positive Rate，F(xiàn)PR），點(diǎn)的縱坐標(biāo)表示正類樣本分類正確的概率（True Positive Rate，TPR），F(xiàn)PR和TPR計(jì)算公式分別如公式（9）～（10）所示：

ROC曲線下面積的大小稱為AUC（Area Under the Curve）值，是通過ROC曲線來評(píng)判模型分類效果的量化標(biāo)準(zhǔn)，當(dāng)AUC值等于0.5時(shí)表示該算法的分類性能等同于完全隨機(jī)分類，該指標(biāo)的數(shù)值越大，模型的分類效果越好。

3.4 結(jié)果分析

實(shí)驗(yàn)結(jié)果取100次運(yùn)行結(jié)果的平均值，無重采樣處理的隨機(jī)森林和基于6種重采樣算法的隨機(jī)森林在不同數(shù)據(jù)集上的G-mean值、F-measure值和AUC值如表3～5所示，表格中加粗?jǐn)?shù)據(jù)為各個(gè)性能評(píng)價(jià)指標(biāo)在每個(gè)數(shù)據(jù)集上取得的最優(yōu)值，G-mean值、F-measure值和AUC值的對(duì)比圖如圖3～5所示。

表3 不同數(shù)據(jù)集上的G-mean值Tab.3 G-mean values on different data sets

表4 不同數(shù)據(jù)集上的F-measure值Tab.4 F-measure values on different data sets

表5 不同數(shù)據(jù)集上的AUC值Tab.5 AUC values on different data sets

從表3～表5和圖3～圖5中可以看出：

1）在大部分不平衡數(shù)據(jù)集上，6種重采樣算法均有效提升了RF的分類性能，不過在glass0數(shù)據(jù)集上，基于ADASYN算法和KM-SMOTE算法的RF表現(xiàn)不是很穩(wěn)定，F(xiàn)-measure值和AUC值比未經(jīng)過重采樣算法處理的RF所得結(jié)果更低。

2）在new-thyroid2、ecoli1、ecoli3、glass0和vehicle0數(shù)據(jù)集上，BSMOTE算法與其他重采樣算法相比具有更好的不平衡數(shù)據(jù)處理能力，各項(xiàng)指標(biāo)值均達(dá)到最優(yōu)，最大程度上提升了RF在不平衡數(shù)據(jù)上的分類性能。

3）在ecoli2數(shù)據(jù)集上，BSMOTE算法的G-mean值和AUC值達(dá)到最優(yōu)，F(xiàn)-measure值比KM-SMOTE算法略低0.43%，總體上差距不大。同時(shí)，BSMOTE算法在該數(shù)據(jù)集上對(duì)RF的提升程度最大，G-mean值、F-measure值和AUC值分別提高了20.61%、22.36%和24.34%。

4）在wisconsin數(shù)據(jù)集上，BSMOTE算法的AUC值比ISMOTE算法低0.98%，不過G-mean值和F-measure值均達(dá)到最優(yōu)，保證了正類樣本的分類精度。

5）在全部數(shù)據(jù)集上，基于BSMOTE算法的RF的分類性能均優(yōu)于傳統(tǒng)RF，G-mean值、F-measure值和AUC值平均提升了11.71%、11.69%和12.81%，證明了BSMOTE算法對(duì)RF進(jìn)行優(yōu)化的有效性。

圖3 G-mean值的對(duì)比圖Fig.3 Comparison graph of G-mean values

圖4 F-measure值的對(duì)比圖Fig.4 Comparison graph of F-measure values

圖5 AUC值的對(duì)比圖Fig.5 Comparison graph of AUC values

通過上述分析可以看出，基于SMOTE的改進(jìn)算法BSMOTE有效解決了不平衡數(shù)據(jù)分類的問題，同時(shí)改善了SMOTE算法合成新樣本時(shí)的盲目性與邊緣化，提升了傳統(tǒng)分類器隨機(jī)森林在不平衡數(shù)據(jù)集上分類性能，從而證明了BSMOTE是一種有效的改進(jìn)算法。

4 結(jié)論

論文針對(duì)SMOTE算法生成新樣本時(shí)存在的盲目性和邊緣化的問題，提出了一種改進(jìn)算法BSMOTE，該算法通過聚類劃分和重心牽引的思想保證了新樣本的有效性，同時(shí)由于新樣本的加入使不平衡數(shù)據(jù)集在訓(xùn)練之前就趨于平衡，再利用隨機(jī)森林分類器進(jìn)行訓(xùn)練，從而有效提升了分類器對(duì)正類樣本的分類精度。最后通過與5種重采樣算法在7個(gè)不平衡數(shù)據(jù)集上進(jìn)行對(duì)比實(shí)驗(yàn)，驗(yàn)證了BSMOTE算法在解決不平衡數(shù)據(jù)分類問題中的優(yōu)勢(shì)。