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

吳立勝 皮珣珣

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

1 引言

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

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

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

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

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

2 相關理論

2.1 經典支持向量機在不平衡數據分類的不足

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

在經典的支持向量機算法中，目標是找到一個決策邊界，將正類樣本和負類樣本盡可能地分開。然而，在不平衡數據集中，正類樣本的數量明顯多于負類樣本，這導致支持向量機更傾向于將決策邊界偏向多數類別。這種偏向會導致分類器對少數類別的識別能力下降，容易將少數類別誤分類為多數類別，影響了分類的準確性。

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

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

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

圖1 SVM分類的結果

2.2 SMOTE算法

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

根據歐幾里德距離，將樣本空間中最近的樣本點分為一組。然后，將距離較近的樣本點劃分為負類樣本。接著，在每組樣本中，使用SMOTE算法構造新的負類樣本。

其中i=1,2,…,m，X表示負類樣本點，Yi為X的第i個近鄰樣本，rand(0,1)表示0到1一個隨機數。Xnew表示新合成的樣本。

3 基于不平衡算法的改進

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

CRSMOTE算法：

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

（1）從負類樣本集中隨機選擇一個樣本點yi，i,j∈(1,m)，以參數φ為半徑，其計算公式為：

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

（2）將負類樣本點yi與剩下任意一個負類樣本點yj采用公式3得到數值Mi。

（3）以負類樣本點yi為圓心，以Mi為半徑的圓Oi，計算其中包含樣本點數目Ni，其中負類樣本數目Ai，其負類樣本密度計算公式MinPtsi：

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

（5）以負類樣本點yj為圓心，以Mj為半徑的圓Oj采用公式計算其密度MinPtsj。

（6）計算圓Oi和Oj之間交叉空間負類樣本點比重I，其計算公式如下：

其中，MinPtsi∩j表示圓Oi和Oj之間相交部分負類樣本點密度。

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

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

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

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

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

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

4 實驗與結果分析

4.1 不平衡數據評價指標

對二分類問題采用混淆矩陣來對其進行評價。混淆矩陣將樣本分為四種組合：真正類（True Positive）：樣本的真正類別屬于正類，模型預測的結果也是正類。假負類（False Negative）：樣本的真正類別屬于正類，模型預測的結果屬于負類。假正類（True Negative）：樣本的真正類別屬于負類，但是模型將其預測成為正類。真負類（True Negative）：樣本的真正類別是負類，模型預測成為負類。分類混淆矩陣如表3所示[11]。

表3 混淆矩陣

分類器進行分類以準確率（Precision）和召回率（Recall）為最基礎兩個指標[12]。準確率：測試數據中，分類器正確分類的樣本數量占總樣本的比重。召回率：樣本數據中，表示樣本數據集中存在多少正例樣本被正確預測。其計算公式為[13]：

F-value是對準確率和召回率進行平均，本次實驗中β調和因子設置為1。F-value定義如下：

在對于非平衡數據的處理中，對于分類器中兩類樣本性能一般采用G-mean值評價。G-mean其定義如下：

4.2 實驗過程和結果

本文為了測試CRSMOTE算法對非平衡數據的處理，文中采用了8個UCI數據集進行分析和實驗。非平衡比是指正類樣本和負類樣本的數量比。表4同時給出負類樣本、正類樣本以及非平衡比。

表4 實驗中UCI數據集

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

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

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

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

實驗表明在圖3～5和表5～7采用四種算法分別是：SVM、SMOTE、TSMOTE、CRSMOTE仿真得出F-value、G-mean、Precision指標進行比較。結果表明數據集中采用CRSMOTE算法在SMOTE基礎上進行改進使其指標均得到提升。本文提出的算法在處理不平衡樣本中，生成負類樣本點分布更加均勻，最終使得分類準確性得到提升。

表5 數據集中Precision值

表6 數據集中F-value值

表7 數據集中G-mean值

5 結語

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