王 曜，鄭 列

(湖北工業(yè)大學(xué) 理學(xué)院，武漢 430068)

0 引言

不平衡數(shù)據(jù)分類問題廣泛地存在于許多領(lǐng)域之中，包括生命科學(xué)［1］、金融部門［2］、工程圖紙分析［3］等。數(shù)據(jù)不平衡指的是在數(shù)據(jù)中一種類的樣本數(shù)量遠(yuǎn)遠(yuǎn)大于另一種類的樣本數(shù)量，通常，將樣本數(shù)量較多的類稱為負(fù)類，樣本數(shù)量較少的類稱為正類。絕大多數(shù)分類器是基于平衡數(shù)據(jù)設(shè)計的，在對不平衡數(shù)據(jù)進行分類時，由于正類樣本數(shù)量較少，分類器難以獲取到正類樣本的特征，從而無法識別到正類樣本。

為了解決不平衡數(shù)據(jù)分類問題，從數(shù)據(jù)層面上出發(fā)的各種過采樣技術(shù)被提出，過采樣技術(shù)是從正類出發(fā)，通過生成新的正類樣本，提高正類的可視性。Chawla 等［4］提出一種在正類樣本及其近鄰的正類樣本之間，隨機進行線性插值生成新樣本的算法SMOTE。自從SMOTE 被提出后，研究人員基于此算法提出了很多擴展，有只在類邊界的正類樣本之間進行SMOTE 的邊界合成少數(shù)過采樣技術(shù)(borderline synthetic minority over-sampling technique，Borderline-SMOTE)［5］;通過不同正類樣本點的學(xué)習(xí)難度來自適應(yīng)地決定合成樣本數(shù)量的自適應(yīng)綜合過采樣技術(shù)(adaptive synthetic sampling approach，ADASYN)［6］;給每一個正類樣本點分配一個安全水平，通過安全水平比值和SMOTE把新樣本點生成在安全等級較高樣本附近的安全水平合成少數(shù)過采樣技術(shù)(safe-level-synthetic minority over-sampling technique，Safe-level-SMOTE)［7］;以及最近提出的半徑合成少數(shù)過采樣技術(shù)(radius synthetic minority over-sampling technique，Radius-SMOTE)［8］，先剔除噪聲點，然后根據(jù)正類樣本中多數(shù)點位置確定安全半徑距離，新樣本僅在該半徑內(nèi)創(chuàng)建，同時利用合成數(shù)據(jù)的限制區(qū)域，減少SMOTE 方法中重疊數(shù)據(jù)的發(fā)生?；诰垲惖姆椒ㄒ脖粡V泛應(yīng)用于過采樣，先通過K-means 算法將正類分為若干類，然后將每個簇心作為根樣本，依次選取簇內(nèi)正類樣本作為輔助樣本進行新樣本生成的K 均值聚類合成少數(shù)過采樣技術(shù)(K-means synthetic minority over-sampling technique，KMSMOTE)［9-10］;將少數(shù)類數(shù)據(jù)通過有噪空間的密度聚類(density-based spatial clustering of applications with noise，DBSCAN)分簇，過濾噪聲樣本集合，以各個簇的邊界數(shù)據(jù)作為主體，插值合成新的樣本的聚類插值過采樣(density-based spatial clustering of applications with noise-synthetic minority over-sampling technique，DB-SMOTE)［11］;先使用分類器對原始數(shù)據(jù)進行分類，剔除部分誤判點，將剩余的正類樣本聚類，并將新樣本點生成在簇心固定范圍內(nèi)的限制半徑合成少數(shù)過采樣技術(shù)(limiting radius synthetic minority over-sampling technique，LR-SMOTE)［12］，聚類技術(shù)的應(yīng)用，一定程度上維持了正類樣本的原始分布。

綜上所述，雖然這些算法在處理不平衡數(shù)據(jù)分類問題時取得了較大的突破，但是也存在一些不足，例如生成噪聲點、數(shù)據(jù)分布邊緣化、未增強足夠特征等問題［13］。受現(xiàn)有研究成果的啟發(fā)，定義了新指標(biāo)正類安全水平、簇安全水平率，提出了試探性少數(shù)類過采樣技術(shù)(TSMOTE)，該算法在對正類樣本聚類后，將試探性的思想融入過采樣技術(shù)中，不局限于簇心和樣本點之間，根據(jù)原始數(shù)據(jù)集分布特點，找出最有可能的正類區(qū)域，利用SMOTE 生成新樣本，增強正類可視性。

1 相關(guān)算法述評

1.1 Safe-level-SMOTE 算法

Safe-level-SMOTE 算法［7］同時考慮正類和負(fù)類的分布情況，基于最近鄰樣本中正類樣本的數(shù)量來分配安全水平，將新樣本生成在較為安全的樣本附近。Safe-level-SMOTE 算法的基本流程如下:

1)計算出每個正類樣本最近K 個樣本點，以其中包含的n 個正類樣本個數(shù)作為安全水平slp。

2)只對正類進行KNN 算法，找出每個正類樣本最近鄰的k 個正類樣本，最近鄰樣本的安全水平為sln，分別計算出正類樣本與其最近鄰正類樣本的安全水平比值slp/sln。

3)依次以安全水平大于0 的正類樣本作為根樣本pi，隨機從其最近鄰k 個正類樣本中選取一個作為輔助樣本ui，式(1)為新樣本pnew的生成公式，對于不同情況下g 的取值如表1 所示。

表1 不同情況下的g 值

真實世界的數(shù)據(jù)集通常是正態(tài)分布，正態(tài)分布的核心是密集的，邊界是稀疏的，分類器會正確地學(xué)習(xí)核心的特征，不幸的是，正類核心太小，無法被分類器識別，因此需要對這個核心進行過采樣［12］。雖然Safe-level-SMOTE 算法合成的新樣本更接近正類，但是合成的少數(shù)類的核心并不集中，因此可能不被分類器所識別。從圖1 中看到，當(dāng)KNN 中K 值設(shè)置不合理時，新生成的樣本依舊會落在負(fù)類區(qū)域，同時由于Safe-level-SMOTE 算法對于新樣本的生成過于謹(jǐn)慎，將最下面的一個正類當(dāng)作噪聲，極大可能屬于正類的黑虛線區(qū)域，沒有得到相應(yīng)增強，從而導(dǎo)致分類準(zhǔn)確性下降。

圖1 Safe-level-SMOTE 算法

1.2 KM-SMOTE 算法

KM-SMOTE 算法［9］將K-means 算法與SMOTE結(jié)合，以簇心為根樣本，依次以簇內(nèi)樣本點為輔助樣本，利用SMOTE 進行新樣本生成，算法流程簡單易于操作。KM-SMOTE 算法的基本流程如下:

1)通過K-means 算法直接對正類樣本進行聚類，將其分為m 類，求出聚類簇心。

2)以簇心為根樣本ci，依次以該簇內(nèi)樣本點為輔助樣本pi，按照式(2)進行線性插值，生成新樣本pnew。

該算法把新生成的點放在了簇心附近，但是并沒有排除噪聲點。如圖2 所示，噪聲點參與聚類導(dǎo)致簇心更偏向負(fù)類，黑虛線范圍為算法增強正類特征區(qū)域，與負(fù)類區(qū)域明顯重疊，新樣本可能生成在負(fù)類區(qū)域或類邊界，導(dǎo)致分類效果下降，違背了算法設(shè)計的初始理念，當(dāng)聚類簇心與正類樣本點空間歐式距離太近時，還可能造成樣本點重合的問題。

圖2 KM-SMOTE 算法

存在與KM-SMOTE 相似的，只對正類樣本使用K-means 算法并與SMOTE 相結(jié)合的過采樣算法，例如崔鑫等［14］對正類樣本聚類，只對到簇心距離小于負(fù)類樣本的正類樣本使用SMOTE。該方法雖然在一定程度上避免了生成噪聲點，卻沒有考慮到距離正類簇心太近的負(fù)類樣本也可能是噪聲的情況，從而沒有增強正類特征，分類效果下降。

2 TSMOTE 算法

在傳統(tǒng)方法SMOTE 的基礎(chǔ)上，將試探的思想融合到過采樣中去，提出了一種新的SMOTE 改進算法——TSMOTE，通過放出試探點來“探測”周圍樣本的分布情況，動態(tài)確定新樣本的生成區(qū)域，從而避免生成噪聲點，解決數(shù)據(jù)分布邊緣化、未增強足夠特征等問題。

2.1 安全水平

假設(shè)全部原始數(shù)據(jù)進行KNN 算法，找到每個正類樣本最近K 個樣本，最大安全水平為K，正類樣本經(jīng)過K-means 聚類，分為m 簇{C1，C2，…，Cm}，簇心為{c1，c2，…，cm}。為每個正類樣本定義個體安全水平slp，全體正類樣本定義正類安全水平slm，每個簇定義簇安全水平率slrc。

定義1(個體安全水平)正類樣本pi的個體安全水平定義為樣本pi最近K 個樣本中正類樣本的數(shù)量。正類樣本pi個體安全水平公式為:

K+表示K 個樣本中正類樣本的個數(shù)。個體安全水平越高，表明該樣本周圍正類樣本越多，越大可能為正類區(qū)域，生成新樣本越安全。

定義2(正類安全水平)正類安全水平定義為正類樣本個體安全水平的均值。正類安全水平公式為:

slp(·)表示全部正類樣本的個體安全水平。個體安全水平比正類安全水平高的樣本，說明其處在較為安全的位置。正類安全水平越高，說明正類和負(fù)類的界限越清晰，因此新樣本的生成需要提高過采樣后的正類安全水平。

定義3(簇安全水平率)簇Cj的簇安全水平率定義為簇Cj內(nèi)部所有正類樣本的個體安全水平的均值除以最大安全水平K。簇Cj的簇安全水平率公式為:

slp(Cj)表示簇Cj內(nèi)所有正類樣本的個體安全水平，可知0≤slrc≤1。簇安全水平率越高，整個簇所處的位置越安全，越有可能處在正類所屬區(qū)域，同時也有樣本點密集的可能;簇安全水平率越低，整個簇所處的位置越不安全，越可能處在非正類的區(qū)域中，新樣本點的生成需要更加謹(jǐn)慎，以上說明了簇安全水平率作為新樣本生成指標(biāo)的合理性。

2.2 警戒點

負(fù)類樣本數(shù)量多，卻沒有涉及的空間區(qū)域，并處在正類樣本簇附近，則有極大可能屬于正類的空間區(qū)域，同時位置安全的正類樣本過采樣生成的新樣本對分類器的學(xué)習(xí)過程沒有太大影響［15］，因此安全水平較高的正類在生成新樣本時向這些區(qū)域進行探索是有利的。當(dāng)數(shù)據(jù)極不平衡時，一些少數(shù)樣本可能被多次合成，導(dǎo)致樣本混疊，甚至過度擬合［16］，為了防止樣本點過于密集，警戒點需要距離簇心一定距離，距離和簇安全水平率相關(guān)。TSMOTE 用試探性的方法，為每個正類樣本找到對應(yīng)的警戒點，一個正類樣本點及其簇心對應(yīng)一個警戒點，詳細(xì)步驟如下:

1)以簇心cj為起點，向其所屬樣本點pi連線，并延伸L 倍到端點，將線段S 等分，從簇心cj到的S-1 個等分點即為探測點{ti1，ti2，…，ti(s-1)}，為探測點tis，一共S 個探測點，探測點{ti1，ti2，…，tis}的排列為距離簇心cj從近到遠(yuǎn)的順序，S 為探測標(biāo)度。

2)找出距離每個探測點最近的K 個原始樣本點，以這K 個原始樣本點中的正類樣本個數(shù)，為每個探測點分配個體安全水平。

3)選取正類樣本點pi，將pi對應(yīng)探測點{ti1，ti2，…，tis}的個體安全水平依次與正類安全水平slm比較。若tin(n≤s)滿足條件:tin和距離簇心cj比tin近的探測點{ti1，…，ti(n-1)}的個體安全水平都大于等于正類安全水平slm，則認(rèn)為探測點{ti1，…，tin}都為安全探測點。

4)警戒點tli只能設(shè)立在簇安全水平率slrc(Cj)對應(yīng)的近端點A 與距離簇心距離最遠(yuǎn)的探測點tis之間。若距離簇心最遠(yuǎn)的安全探測點在可設(shè)立范圍內(nèi)，則距離簇心最遠(yuǎn)的安全探測點為警戒點tli;若不在范圍內(nèi)，則近端點A 為警戒點tli，近端點A 坐標(biāo)為cj+slrc(Cj)(pi-cj)。

以二維數(shù)據(jù)為例，利用圖3 進一步說明警戒點的設(shè)立，黑三角形A 為簇安全水平率對應(yīng)的近端點，2 個黑三角形之間為警戒點的設(shè)立范圍，ti1、ti2、ti3、ti4、ti5為該樣本點pi對應(yīng)探測點，虛線段為探測范圍。若探測點ti1、ti2、ti3的個體安全水平slp都大于等于正類安全水平slm，探測點ti4的slp小于slm，則警戒點為ti3;若全部探測點的個體安全水平都大于等于slm，則警戒點為ti5;若探測點ti1的slp小于slm，則警戒點為近端點A。

求警戒點的偽算法見算法1，第1—7 行為生成探測點;第8 行為計算探測點個體安全水平;第9—14 行為尋找每個正類樣本點對應(yīng)的警戒點;第15—17 行為將警戒點限定到設(shè)立范圍中。

算法1警戒點

2.3 TSMOTE 算法具體步驟

TSMOTE 利用試探性的思想圍繞個體安全水平、正類安全水平、簇安全水平率3 個指標(biāo)進行展開，新樣本的生成促使正類安全水平、簇安全水平率提升，同時簇安全水平率越大的簇生成樣本越激進，簇安全水平率越小的簇生成樣本越保守，使各簇之間的簇安全水平率差距得以縮小，利于分類器學(xué)習(xí)到每個簇，設(shè)立警戒點即約束新樣本點的生成。TSMOTE 算法主要分為去噪、聚類、試探、過采樣4 個部分，詳細(xì)算法步驟如下:

步驟1使用原始數(shù)據(jù)集，進行KNN 算法，以式(3)給每一個正類樣本分配個體安全水平slp，個體安全水平與其所處的位置相關(guān)，剔除個體安全水平為0 的噪聲。

步驟2將剩余的正類樣本進行K-means 聚類，每個聚類簇的簇心為{c1，c2，…，cm}，根據(jù)式(4)和(5)分別計算出正類安全水平slm和每個簇的簇安全水平率slrc。

步驟3設(shè)定延伸倍數(shù)L，探測標(biāo)度S，根據(jù)算法1 計算出每個正類樣本的警戒點tli。

步驟4依次選取每個簇心ci作為根樣本，以該簇內(nèi)正類樣本pi對應(yīng)的警戒點tli作為輔助樣本，按照式(6)進行新樣本pnew的生成。

上述步驟的偽算法見算法2。第1—6 行剔除個體安全水平為0 的噪聲點;第7 行對正類樣本聚類，并找出每一簇的簇心;第8—10 行求出簇安全水平率、正類安全水平、每個正類樣本的對應(yīng)的警戒點;第11—15 行為進行新樣本點的生成與存儲。

算法2TSMOTE 算法

3 實驗

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

選取的數(shù)據(jù)集均源于公開數(shù)據(jù)庫KEEL［17］，從樣本量多少、不平衡度(imbalanced ratio，IR)高低2 個方面選取了12 個二分類數(shù)據(jù)集，不平衡度從2.06～72.69，覆蓋區(qū)域大，更好地體現(xiàn)出在不同和不平衡度的情況下各種算法的性能。數(shù)據(jù)集詳細(xì)信息如表2 所示。

表2 不平衡數(shù)據(jù)集

3.2 評價指標(biāo)

在不平衡數(shù)據(jù)分類問題中，對正類的判別尤為重要，選取的評價指標(biāo)需要同時兼顧正類和負(fù)類的判別精度。選取了3 個評價指標(biāo)，分別是AUC (area under curve)［18］、G-means［9］、Fscore［12］。AUC 值是ROC(receiver operating characteristic curve)［19］與坐標(biāo)軸之間的下半部分面積，ROC 曲線是由混淆矩陣中負(fù)類的誤判率和正類的召回率繪制而成，當(dāng)分類效果越好時，ROC 曲線越貼近邊框，AUC 值也越大。二分類混淆矩陣如表3 所示。

表3 混淆矩陣

G-means 的取值取決于分類器對正類和負(fù)類分類的準(zhǔn)確性，能夠反映整體分類能力，計算公式如下:

F-score 是一種綜合評價查準(zhǔn)率和查全率的評價指標(biāo)，能夠比較客觀地反映分類效果，計算公式如下:

查準(zhǔn)率表示在預(yù)測結(jié)果中，正確預(yù)測為正類樣本的概率，查全率表示在原始樣本中，被正確預(yù)測為正類樣本的概率［18］，計算公式如下:

3.3 實驗設(shè)計

本次實驗通過10 次五折交叉驗證的方法，確保實驗的效果，消除隨機性問題，即每個數(shù)據(jù)集每輪實驗會產(chǎn)生50 個實驗數(shù)據(jù)集，最后實驗結(jié)果的取值為50 次的平均值，通過對比不同過采樣算法結(jié)果中的3 個評價指標(biāo)，來判斷TSMOTE 算法的性能。

為保證算法不受特定分類器的限制，實驗結(jié)果具有普遍性，通過比較機器學(xué)習(xí)分類算法，發(fā)現(xiàn)隨機森林算法具有良好的泛化能力和較快的訓(xùn)練速度，同時支持向量機常用于兩類問題的研究，線性核支持向量機對大數(shù)據(jù)集的分類速度很快［20］。因此，選取默認(rèn)設(shè)置的線性核支持向量機(support vector machine，SVM)和100 顆決策樹的隨機森林(random forest，RF)作為分類器分別進行實驗，F(xiàn)score 指標(biāo)中的β=1，各算法中KNN 的K 固定為5，即最大安全水平為5，聚類簇數(shù)按最優(yōu)情況選取，TSMOTE 算法中延伸倍數(shù)L=1，探測標(biāo)度S=20。

3.4 實驗結(jié)果分析

對5 種情況下的數(shù)據(jù)集進行實驗，同時將SMOTE、Safe-level-SMOTE、KM-SMOTE、TSMOTE分別略寫為SMO、SLS、KMS、TSMO，得到實驗結(jié)果見表4。

表4 不同過采樣算法對比結(jié)果

續(xù)表(表4)

將表4 中5 種過采樣算法里指標(biāo)值最高的數(shù)加粗，可以看出，TSMOTE 算法下指標(biāo)值最高的數(shù)量最多，該算法在各種不平衡度的數(shù)據(jù)上都表現(xiàn)較好，并且在不平衡度大于10 的數(shù)據(jù)上指標(biāo)值全部最優(yōu)。為了進一步對比研究TSMOTE 在不同平衡度數(shù)據(jù)下相較于其他過采樣算法的性能，將同數(shù)據(jù)集同過采樣算法在2 種分類器下得到的同評價指標(biāo)進行平均劃分，橫軸為按照不平衡度升序排列的12 個數(shù)據(jù)集，縱軸為2 種分類器下評價指標(biāo)的平均數(shù)，畫出柱狀圖，從圖4—6 中可以看出，隨著橫軸往右移動，純黑柱形高于其他柱形，在3張圖中都越來越明顯，即數(shù)據(jù)不平衡度越高，TSMOTE 相較于SMOTE、Safe-level-SMOTE 和KMSMOTE 解決數(shù)據(jù)不平衡問題越有優(yōu)勢。

圖4 平均評價指標(biāo)AUC 值

圖5 平均評價指標(biāo)G-means 值

分別計算全部數(shù)據(jù)集、不平衡度大于10 的數(shù)據(jù)集，TSMOTE 算法在不同分類器不同評價指標(biāo)下，相對其他算法的提升效果見表5，評價指標(biāo)AUC、G-means、F-score 在上述實驗結(jié)果中平均值為0.85、0.74、0.55，這些結(jié)果本身就較高，因此提升較為困難，但是TSMOTE 在2 種分類器下依舊較其他算法有較大提升，說明TSMOTE 算法合成新樣本的質(zhì)量較高，能有效平衡不平衡數(shù)據(jù)。同時，通過對比全部數(shù)據(jù)、IR＞10 數(shù)據(jù)的指標(biāo)提升值，可以發(fā)現(xiàn)幾乎在所有情況下，TSMOTE 在IR＞10 數(shù)據(jù)上性能更佳，說明這種試探性的新算法更適合處理高度不平衡度數(shù)據(jù)。

圖6 平均評價指標(biāo)F-score 值

表5 TSMOTE 相對其他算法提升 %

4 結(jié)論

為解決非平衡數(shù)據(jù)分類問題，提出了新過采樣算法TSMOTE，公開數(shù)據(jù)集上的實驗表明:TSMOTE 優(yōu)于SMOTE、Safe-level-SMOTE、KM-SMOTE。TSMOTE 有效解決了SMOTE 合成樣本的質(zhì)量問題、模糊類邊界問題，同時獲取了更多的正類特征，更好地改善了數(shù)據(jù)集，新算法中正類安全水平的引入，衡量了正類與負(fù)類的界限是否清晰，有效防止了噪聲點參與新樣本的生成;簇安全水平率有效防止了過擬合問題;使用試探性的方法，根據(jù)空間區(qū)域特點，分配不同的生成范圍，獲取每個簇的警戒點，不局限于樣本點與簇心之間，防止新樣本點生成在負(fù)類附近模糊了類邊界，也在安全區(qū)域內(nèi)獲取更多的特征信息。