一種新的基于聚類的試探性SMOTE 算法

王 曜，鄭 列

(湖北工業大學 理學院，武漢 430068)

0 引言

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

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

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

1 相關算法述評

1.1 Safe-level-SMOTE 算法

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

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

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

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

表1 不同情況下的g 值

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

圖1 Safe-level-SMOTE 算法

1.2 KM-SMOTE 算法

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

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

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

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

圖2 KM-SMOTE 算法

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

2 TSMOTE 算法

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

2.1 安全水平

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

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

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

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

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

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

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

2.2 警戒點

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

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

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

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

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

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

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

算法1警戒點

2.3 TSMOTE 算法具體步驟

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

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

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

步驟3設定延伸倍數L，探測標度S，根據算法1 計算出每個正類樣本的警戒點tli。

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

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

算法2TSMOTE 算法

3 實驗

3.1 數據集

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

表2 不平衡數據集

3.2 評價指標

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

表3 混淆矩陣

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

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

查準率表示在預測結果中，正確預測為正類樣本的概率，查全率表示在原始樣本中，被正確預測為正類樣本的概率［18］，計算公式如下:

3.3 實驗設計

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

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

3.4 實驗結果分析

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

表4 不同過采樣算法對比結果

續表(表4)

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

圖4 平均評價指標AUC 值

圖5 平均評價指標G-means 值

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

圖6 平均評價指標F-score 值

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

4 結論

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