基于交叉區(qū)域SMOTE算法的非平衡數(shù)據(jù)分類

吳立勝 皮珣珣

（江西科技學(xué)院信息工程學(xué)院，江西 南昌 330098）

1 引言

不平衡數(shù)據(jù)分類問題指的是在二分類任務(wù)中，某一類樣本的數(shù)量遠(yuǎn)遠(yuǎn)小于另一類樣本，導(dǎo)致數(shù)據(jù)分布不平衡[1]。這種情況在現(xiàn)實(shí)生活中的許多場(chǎng)景中都普遍存在，例如信用卡欺詐檢測(cè)、信息檢索和過濾、市場(chǎng)行為分析等。傳統(tǒng)分類算法通常假設(shè)待分類的兩類樣本數(shù)量大致相等，因此在處理不平衡數(shù)據(jù)時(shí)容易受到多數(shù)類樣本的影響，導(dǎo)致分類邊界偏移和分類錯(cuò)誤的問題。

為了解決不平衡數(shù)據(jù)分類問題，學(xué)者們提出了許多解決方案，主要從數(shù)據(jù)集和算法兩個(gè)方面入手。在數(shù)據(jù)集方面，處理不平衡數(shù)據(jù)的方法通常涉及兩個(gè)方面：過采樣增加負(fù)類樣本或者下采樣減少正類樣本，以實(shí)現(xiàn)數(shù)據(jù)樣本的平衡，并提高分類準(zhǔn)確率。其中，過采樣增加負(fù)類樣本的方法之一是SMOTE（Synthetic Minority Over-sampling Technique）[2]，它通過從負(fù)類樣本中選取K近鄰樣本，并生成新的合成負(fù)類樣本，從而增加負(fù)類樣本的數(shù)量。

但是，SMOTE算法對(duì)負(fù)類樣本合成未考慮負(fù)類樣本點(diǎn)分布。Han等人針對(duì)生成負(fù)類樣本點(diǎn)分布不平衡提出了Borderline-SMOTE方法[3]，其在最近鄰正類樣本點(diǎn)構(gòu)成n維球體內(nèi)進(jìn)行隨機(jī)插值，擴(kuò)大生成負(fù)類樣本點(diǎn)的區(qū)域，將數(shù)據(jù)集中到分類邊界。宋艷等人針對(duì)數(shù)據(jù)不平衡提出E-SMOTE算法[4]，SMOTE算法在進(jìn)行插值時(shí)，不僅考慮了鄰域樣本點(diǎn)，還考慮了附近鄰域樣本點(diǎn)的分布特征。它通過控制近鄰樣本點(diǎn)的分布特征，來生成合成的負(fù)類樣本點(diǎn)，以實(shí)現(xiàn)對(duì)負(fù)類樣本點(diǎn)分布區(qū)域的調(diào)控。

Francisco等使用了二值化分解正類樣本并結(jié)合SMOTE算法來生成負(fù)類樣本，以平衡數(shù)據(jù)集[5]。Matwin等通過邊界、冗余和去重等方法減少正類樣本的數(shù)量。Mani等采用KNN算法刪除正類樣本點(diǎn)，并提出了NearMiss-1、NearMiss-2、NearMiss-3和“最遠(yuǎn)距離”四種方法，根據(jù)負(fù)類樣本點(diǎn)的距離選擇正類樣本點(diǎn)[6]。在算法層面，Patel等采用混合加權(quán)的KNN方法對(duì)不平衡數(shù)據(jù)進(jìn)行分類，通過動(dòng)態(tài)設(shè)置權(quán)值，給予負(fù)類樣本較大的權(quán)值，以減小分類邊界對(duì)正類樣本的影響[7]。袁興梅等提出了一種新型的集成分類算法AdaStASVM，首先利用聚類算法獲取樣本的結(jié)構(gòu)信息，然后通過Ada-Boost動(dòng)態(tài)調(diào)整樣本權(quán)重，以減少數(shù)據(jù)不平衡帶來的影響[8]。

綜上所述，現(xiàn)在對(duì)不平衡數(shù)據(jù)研究關(guān)注重點(diǎn)是對(duì)負(fù)類樣本合成過程、分類算法權(quán)重等方面。本文通過限制負(fù)類樣本的合成區(qū)域提出CRSMOTE算法。CRNSMOTE算法確定負(fù)類樣本點(diǎn)合成最佳閾值區(qū)間。將CRSMOTE與SVM相結(jié)合進(jìn)行大量仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明該算法提升了在不平衡數(shù)據(jù)集上的G-mean，F(xiàn)-value以及Precision值。

2 相關(guān)理論

2.1 經(jīng)典支持向量機(jī)在不平衡數(shù)據(jù)分類的不足

支持向量機(jī)（Support Vector Machine,SVM）是一種常用的監(jiān)督學(xué)習(xí)算法[9]，被廣泛應(yīng)用于二分類和多分類問題。然而，在處理不平衡數(shù)據(jù)分類時(shí)，經(jīng)典的支持向量機(jī)算法存在一些不足之處。

在經(jīng)典的支持向量機(jī)算法中，目標(biāo)是找到一個(gè)決策邊界，將正類樣本和負(fù)類樣本盡可能地分開。然而，在不平衡數(shù)據(jù)集中，正類樣本的數(shù)量明顯多于負(fù)類樣本，這導(dǎo)致支持向量機(jī)更傾向于將決策邊界偏向多數(shù)類別。這種偏向會(huì)導(dǎo)致分類器對(duì)少數(shù)類別的識(shí)別能力下降，容易將少數(shù)類別誤分類為多數(shù)類別，影響了分類的準(zhǔn)確性。

此外，支持向量機(jī)的學(xué)習(xí)過程中，對(duì)每個(gè)樣本的處理是均等的，沒有對(duì)不平衡數(shù)據(jù)集進(jìn)行針對(duì)性的處理。這意味著在模型訓(xùn)練中，每個(gè)樣本對(duì)分類器的影響相同，無論其屬于多數(shù)類還是少數(shù)類。對(duì)于少數(shù)類樣本而言，可能受到多數(shù)類樣本的干擾，導(dǎo)致分類器難以捕捉到少數(shù)類樣本的特征和模式。

因此，針對(duì)不平衡數(shù)據(jù)分類問題，僅使用經(jīng)典的支持向量機(jī)算法可能無法達(dá)到理想的分類效果。為了改進(jìn)不平衡數(shù)據(jù)分類的性能，需要采用一些特殊的方法或算法來處理不平衡數(shù)據(jù)集，以提高對(duì)少數(shù)類別的識(shí)別能力和分類準(zhǔn)確性。

圖1中表明分類邊界向負(fù)樣本方向移動(dòng)，產(chǎn)生上述情況是由于優(yōu)化函數(shù)中對(duì)正類樣本和負(fù)類樣本采用相同懲罰系數(shù)，造成負(fù)類樣本分類存在較大的誤差。負(fù)類樣本其懲罰系數(shù)應(yīng)遠(yuǎn)遠(yuǎn)小于正類樣本的懲罰系數(shù)。因此，要提高SVM在不平衡數(shù)據(jù)分類中的準(zhǔn)確性，需要解決SVM偏向負(fù)類樣本的問題[7]。

圖1 SVM分類的結(jié)果

2.2 SMOTE算法

SMOTE算法是采用人工合成增加負(fù)類樣本點(diǎn)降低數(shù)據(jù)不平衡性。SMOTE算法根據(jù)歐幾里德距離計(jì)算一個(gè)樣本X={x1,x2…,xn}和樣本Y={y1,y2…,yn}之間距離。那么樣本X和樣本Y之間的歐幾里德距離D：

根據(jù)歐幾里德距離，將樣本空間中最近的樣本點(diǎn)分為一組。然后，將距離較近的樣本點(diǎn)劃分為負(fù)類樣本。接著，在每組樣本中，使用SMOTE算法構(gòu)造新的負(fù)類樣本。

其中i=1,2,…,m，X表示負(fù)類樣本點(diǎn)，Yi為X的第i個(gè)近鄰樣本，rand(0,1)表示0到1一個(gè)隨機(jī)數(shù)。Xnew表示新合成的樣本。

3 基于不平衡算法的改進(jìn)

SMOTE算法在進(jìn)行負(fù)類樣本合成時(shí)候，無法解決負(fù)類樣本點(diǎn)分布不均衡的問題[10]，同時(shí)計(jì)算過于復(fù)雜。本文針對(duì)SMOTE算法負(fù)類樣本分布不均勻提出了CRSMOTE算法。CRSMOTE算法重點(diǎn)關(guān)注樣本點(diǎn)產(chǎn)生的區(qū)域和合成數(shù)量，避免樣本數(shù)據(jù)分布的邊緣化。

CRSMOTE算法：

輸入：訓(xùn)練集I,原始樣本點(diǎn)正類樣本集合為S1={x1,x2…xn}、負(fù)類樣本集合為S2={y1,y2…ym}。

（1）從負(fù)類樣本集中隨機(jī)選擇一個(gè)樣本點(diǎn)yi，i,j∈(1,m)，以參數(shù)φ為半徑，其計(jì)算公式為：

其中，D(yi,yj)表示采用歐式距離來計(jì)算負(fù)類樣本點(diǎn)yi和yj之間的距離。

（2）將負(fù)類樣本點(diǎn)yi與剩下任意一個(gè)負(fù)類樣本點(diǎn)yj采用公式3得到數(shù)值Mi。

（3）以負(fù)類樣本點(diǎn)yi為圓心，以Mi為半徑的圓Oi，計(jì)算其中包含樣本點(diǎn)數(shù)目Ni，其中負(fù)類樣本數(shù)目Ai，其負(fù)類樣本密度計(jì)算公式MinPtsi：

（4）負(fù)類樣本點(diǎn)yj與剩下任意一個(gè)負(fù)類樣本點(diǎn)ya，a∈(1,m)，采用公式3得到數(shù)值Mj。

（5）以負(fù)類樣本點(diǎn)yj為圓心，以Mj為半徑的圓Oj采用公式計(jì)算其密度MinPtsj。

（6）計(jì)算圓Oi和Oj之間交叉空間負(fù)類樣本點(diǎn)比重I，其計(jì)算公式如下：

其中，MinPtsi∩j表示圓Oi和Oj之間相交部分負(fù)類樣本點(diǎn)密度。

（7）若I小于相應(yīng)閾值區(qū)間,則在yi和yj之間進(jìn)行負(fù)類樣本點(diǎn)合成數(shù)目為N'，使得I最終處于最佳閾值區(qū)間。若I值大于1，則忽略交叉區(qū)間不對(duì)負(fù)類樣本點(diǎn)yi和yj進(jìn)行合成。

（8）如果合成負(fù)類樣本點(diǎn)數(shù)目不足，則繼續(xù)轉(zhuǎn)步驟4。當(dāng)步驟4中負(fù)類樣本點(diǎn)全部隨機(jī)完成，但是合成負(fù)類樣本點(diǎn)還未達(dá)到和正類樣本點(diǎn)數(shù)量1:1，則再轉(zhuǎn)步驟1選擇不重復(fù)負(fù)類樣本點(diǎn)：繼續(xù)步驟2～7，直到生成負(fù)類樣本點(diǎn)和正類樣本點(diǎn)數(shù)量達(dá)到1:1。

如何獲得高效的閾值區(qū)間，從而進(jìn)行負(fù)類樣本點(diǎn)合成是本實(shí)驗(yàn)需要解決問題的關(guān)鍵。本文采用在非平衡數(shù)據(jù)中分類的一般性的評(píng)價(jià)標(biāo)準(zhǔn)：F-value和G-mean計(jì)算的值進(jìn)行評(píng)估。采用I來確定合成的負(fù)類樣本點(diǎn)分布。在表1和表2分別隨機(jī)選擇3個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，劃分區(qū)間為[0.0,0.2)，[0.2，0.4)，[0.4，0.6)，[0.6，0.8)，[0.8，1.0]這5個(gè)區(qū)間，分別將下面數(shù)據(jù)集中包含負(fù)類樣本點(diǎn)按照CRSMOT算法合成對(duì)其進(jìn)行測(cè)試。經(jīng)過測(cè)試，圖1和圖2表明，不同數(shù)據(jù)集在I處于[0.2，0.4)之間F-value和G-mean值更為高效。說明交叉區(qū)域內(nèi)負(fù)類樣本合成具有一定的普適性，除了改變負(fù)類樣本點(diǎn)分布區(qū)域之外，還可以提高分類器的分類效率。

表1 不同區(qū)間下的G-mean值

表2 不同區(qū)間下的F-value值

圖2 不同區(qū)間下G-mean值和F-value

4 實(shí)驗(yàn)與結(jié)果分析

4.1 不平衡數(shù)據(jù)評(píng)價(jià)指標(biāo)

對(duì)二分類問題采用混淆矩陣來對(duì)其進(jìn)行評(píng)價(jià)?；煜仃噷颖痉譃樗姆N組合：真正類（True Positive）：樣本的真正類別屬于正類，模型預(yù)測(cè)的結(jié)果也是正類。假負(fù)類（False Negative）：樣本的真正類別屬于正類，模型預(yù)測(cè)的結(jié)果屬于負(fù)類。假正類（True Negative）：樣本的真正類別屬于負(fù)類，但是模型將其預(yù)測(cè)成為正類。真負(fù)類（True Negative）：樣本的真正類別是負(fù)類，模型預(yù)測(cè)成為負(fù)類。分類混淆矩陣如表3所示[11]。

表3 混淆矩陣

分類器進(jìn)行分類以準(zhǔn)確率（Precision）和召回率（Recall）為最基礎(chǔ)兩個(gè)指標(biāo)[12]。準(zhǔn)確率：測(cè)試數(shù)據(jù)中，分類器正確分類的樣本數(shù)量占總樣本的比重。召回率：樣本數(shù)據(jù)中，表示樣本數(shù)據(jù)集中存在多少正例樣本被正確預(yù)測(cè)。其計(jì)算公式為[13]：

F-value是對(duì)準(zhǔn)確率和召回率進(jìn)行平均，本次實(shí)驗(yàn)中β調(diào)和因子設(shè)置為1。F-value定義如下：

在對(duì)于非平衡數(shù)據(jù)的處理中，對(duì)于分類器中兩類樣本性能一般采用G-mean值評(píng)價(jià)。G-mean其定義如下：

4.2 實(shí)驗(yàn)過程和結(jié)果

本文為了測(cè)試CRSMOTE算法對(duì)非平衡數(shù)據(jù)的處理，文中采用了8個(gè)UCI數(shù)據(jù)集進(jìn)行分析和實(shí)驗(yàn)。非平衡比是指正類樣本和負(fù)類樣本的數(shù)量比。表4同時(shí)給出負(fù)類樣本、正類樣本以及非平衡比。

表4 實(shí)驗(yàn)中UCI數(shù)據(jù)集

每次實(shí)驗(yàn)采取隨機(jī)方法將樣本數(shù)據(jù)中80%劃分為訓(xùn)練集，剩余20%劃分為測(cè)試集。本文對(duì)測(cè)試數(shù)據(jù)取10次數(shù)據(jù)的均值，同時(shí)采用F-value、G-mean、Precision評(píng)價(jià)指標(biāo)進(jìn)行評(píng)價(jià)。實(shí)驗(yàn)中將CRSMOTE算法與SMOTE算法、TSMOTE算法[14]和單純SVM算法進(jìn)行對(duì)比，以顯示該算法的優(yōu)勢(shì)。從圖3～5中分別采用了4種策略算法在8個(gè)數(shù)據(jù)集來表示其趨勢(shì)。從圖可以看出采用CRSMOTE算法進(jìn)行過采樣，使得負(fù)類樣本的性能得到提升。

圖3 不同策略算法Precision值變化圖

圖4 不同策略算法F-value值變化圖

圖5 不同策略算法G-mean值變化圖

實(shí)驗(yàn)表明在圖3～5和表5～7采用四種算法分別是：SVM、SMOTE、TSMOTE、CRSMOTE仿真得出F-value、G-mean、Precision指標(biāo)進(jìn)行比較。結(jié)果表明數(shù)據(jù)集中采用CRSMOTE算法在SMOTE基礎(chǔ)上進(jìn)行改進(jìn)使其指標(biāo)均得到提升。本文提出的算法在處理不平衡樣本中，生成負(fù)類樣本點(diǎn)分布更加均勻，最終使得分類準(zhǔn)確性得到提升。

表5 數(shù)據(jù)集中Precision值

表6 數(shù)據(jù)集中F-value值

表7 數(shù)據(jù)集中G-mean值

5 結(jié)語

本文針對(duì)SMOTE算法進(jìn)行改進(jìn)提出CRSMOTE算法。改進(jìn)算法考慮到數(shù)據(jù)生成區(qū)域和數(shù)量分布，使得對(duì)樣本點(diǎn)生成準(zhǔn)確率得到提升，有效改善SMOTE算法樣本點(diǎn)分布不均勻的問題。實(shí)驗(yàn)結(jié)果表明，CRSMOTE與SMOTE和TSMOTE相對(duì)比得到了比較高的F-value、G-mean和Precision值，提高了對(duì)于不平衡數(shù)據(jù)分類的準(zhǔn)確性。本文算法改進(jìn)還存在合成負(fù)類樣本點(diǎn)計(jì)算量過大、未考慮異常點(diǎn)剔除等缺陷，未來將對(duì)模型做進(jìn)一步優(yōu)化。