基于混合采樣的非平衡數據分類算法*

吳藝凡，梁吉業+，王俊紅

1.山西大學 計算機與信息技術學院，太原 030006

2.山西大學 計算智能與中文信息處理教育部重點實驗室，太原 030006

1 引言

大數據時代的到來使得基于數據的知識獲取成為可能，促進了數據密集型科學的發展。分類是機器學習和數據挖掘中重要的信息獲取手段之一，但傳統的分類算法沒有考慮數據的平衡性，在非平衡分類問題上仍面臨著巨大挑戰。例如在醫療診斷[1]、網絡入侵檢測[2]等問題中，關注的事件在所有數據記錄中占比都極小，但是將其錯誤分類卻會帶來無法估量的代價。將數量占多數的類稱為多數類，占少數的類稱為少數類，在非平衡數據中對少數類的正確分類往往比多數類更有價值。例如在癌癥檢測領域中，健康人的數量遠大于患病人的數量，但更注重對真正患病人的識別率。因此如何對非平衡數據集進行正確分類，提高少數類的分類精度成為分類問題中的一個難點[3]。并且多類問題通?？梢院喕癁閮深悊栴}來解決，因此非平衡數據集分類問題的研究重點也就轉化為提高兩類問題中的少數類的分類性能[4]。

目前，國內外學者對非平衡數據分類問題的常用策略大致分為算法層面的方法和數據層面的方法。算法層面主要有代價敏感學習[5]、集成學習[6-7]、特征選擇[8]、單類別學習[9]等方法。數據層面最常用的方法是數據采樣技術，主要包括三種：過采樣、欠采樣和混合采樣。本文重點關注數據層面的研究進展。

過采樣中比較經典的算法是Chawla等人[10]提出的 SMOTE（synthetic minority over-sampling technique）算法，其基本思想是：距離較近的少數類之間的樣本仍然是少數類，在距離較近的兩個少數類樣本之間通過線性插值的方式產生一個新的少數類樣本，使得少數類樣本增加，達到平衡數據集的目的。實驗結果表明SMOTE算法顯著提高了少數類的分類精度，但是SMOTE算法是對所有少數類樣本盲目地進行過采樣，容易生成很多不重要的少數類樣本。Han等人提出的Borderline-SMOTE[11]算法，認為處在邊界上的少數類更容易被錯分，對分類器的性能起到更重要的作用，因此對樣本周圍多數類較多的少數類樣本用SMOTE過采樣。

欠采樣中較為簡單的方法是隨機欠采樣，指隨機刪掉一些多數類樣本以平衡數據集，該方法操作簡單，但容易刪去一些有用的多數類樣本造成信息丟失。Tomeklinks[12]方法認為能構成Tomeklinks對的樣本中，某個樣本可能為噪聲樣本或在兩類樣本的邊界上，將其中的多數類樣本刪去，從而達到欠采樣的目的。

使用單一的采樣算法如只使用過采樣容易造成分類器過擬合，只使用欠采樣容易導致樣本信息丟失?；旌喜蓸油瑫r采用過采樣和欠采樣技術，在解決上述問題的同時提高了少數類的分類精度。傳統的混合采樣中表現較為出色的有SMOTE+Tomek links方法[13]，在使用SMOTE對少數類樣本上采樣的同時，刪除多數類樣本中的Tomek links對，還有SMOTE+ENN（edit nearest neighbor）方法等。這些方法都是基于樣本之間的距離的，Song等人[14]提出基于聚類的混合采樣算法（bi-directional sampling based onK-means，BDSK），該算法將SMOTE過采樣算法與基于K-means的欠采樣算法相結合，在增加少數類樣本的同時有效地刪去噪聲樣本。上述混合采樣的方法都是基于距離或者聚類的，沒有考慮到決策邊界對樣本的影響。Veropoulos等人提出了代價敏感訓練算法[15]，通過賦予錯分的正負類樣本不同的懲罰系數來降低分類超平面的偏移度，此方法簡單易行并且具有一定效果。然而，當少數類樣本過分稀疏時，采用此方法會因分類超平面過分擬合少數類樣本而影響分類效果。Jian等人[16]提出的基于不同貢獻度的采樣算法（different contribution sampling，DCS），認為支持向量是更靠近決策邊界的樣本，貢獻度更高，因此針對支持向量和非支持向量采用混合采樣方法，即使用SMOTE和隨機欠采樣技術來分別對少數類樣本中的支持向量和多數類樣本中的非支持向量進行重新采樣。該方法雖然考慮到決策邊界的影響，但沒有考慮到被錯分的少數類樣本更靠近真實類邊界，對分類器的性能起到重要作用，并且對多數類樣本進行隨機欠采樣有可能會刪去一些重要的樣本。

為了克服采樣算法的盲目性以及支持向量機算法（support vector machine，SVM）在處理非平衡數據時分類超平面容易偏向少數類樣本的問題，本文提出了一種基于SVM分類超平面的混合采樣算法（hybrid sampling algorithm based on SVM，SVM_HS），旨在利用SVM分類超平面找出較為重要的少數類樣本和不重要的多數類樣本，對這些樣本進行過采樣和欠采樣，達到平衡數據集的目的。在UCI數據集上進行實驗并與其他重采樣算法進行比較，實驗結果顯示SVM_HS算法的F-value和G-mean值均有較大提高，在處理非平衡數據分類問題上具有一定優勢。

2 相關工作

本文算法是基于SVM分類超平面的混合采樣算法，因此首先將從SVM算法思想和超平面偏移問題以及混合采樣中用到的采樣算法兩方面進行介紹。

2.1 SVM算法

20世紀90年代Vapnik提出了SVM支持向量機算法[17]，以結構風險最小化為原則，同時考慮到置信范圍和經驗風險，克服了分類器過學習、高維數、非線性和局部極值點等一系列問題。目前在機器學習領域中成為一個新的研究熱點。

SVM的基本原理是尋找一個最優分類超平面，使得該超平面在保證分類精度的同時能夠使超平面兩側的空白區域最大化。設訓練樣本集為T={(xi，yi)，i=1，2，…，l}，xi∈Rm，yi∈{-1，1}，超平面記作ωT?φ(x)+b=0，求解最優分類超平面可轉化為二次優化問題：

約束條件為：

其中，ξi為松弛因子，C＞0為誤分樣本的懲罰系數。用Lagrange乘子法可獲得式（2）的對偶問題：

約束條件為：

其中，αi為Lagrange乘子。設k(xi，xj)為核函數，它對應非線性映射φ。那么SVM訓練出來的分類判別式為：

但在利用SVM算法進行分類時，是建立在正負類數據樣本數量大致持平的情況下，當樣本數量不平衡時，分類超平面會偏向少數類。下面分別通過兩組實驗數據進行分析驗證，兩組數據樣本正負比分別為1∶1和1∶10，其他參數包括高斯核寬度為10，懲罰系數C為100，實驗結果分別如圖1和圖2所示。

Fig.1 Hyperplane of balanced dataset圖1 平衡數據集的分類超平面

可以發現，當數據平衡時，SVM分類超平面完美地位于正負樣本中間，當正負樣本出現嚴重失衡時，分類器的分類性能就會下降，為了使超平面兩側的空白區域最大化且獲得較高的分類精度，分類超平面會偏向少數類。因此為了使超平面向真實類邊界靠近，需要改變非平衡數據集的分布情況。

Fig.2 Hyperplane of unbalanced dataset圖2 非平衡數據集的分類超平面

2.2 SMOTE算法

SMOTE算法基本思想是：在距離較近的兩個少數類樣本之間通過線性插值的方式產生一個新的少數類樣本，使得少數類樣本增加，達到平衡數據集的目的。整體算法如算法1所示。

算法1SMOTE算法

3 基于混合采樣的非平衡數據分類算法

從相關研究中可以知道[15-17]，傳統的SVM算法對非平衡數據集進行分類時，訓練所得的分類超平面會偏向少數類，被錯分的少數類比分對的更靠近真實類邊界，對分類器的性能起到更重要的作用，因此對這些樣本進行過采樣；而對于多數類來說，離分類超平面越遠，則對分類性能的影響越小，因此對離超平面較遠的多數類樣本進行欠采樣，進而使SVM分類超平面向著真實類邊界方向偏移。

3.1 SVM_HS算法基本思想

給定一個樣本集，使用該集合訓練出一個SVM分類器，被錯誤分類的少數類樣本更為重要，是要進行過采樣的集合對象；離分類超平面較遠的多數類樣本相較于離超平面近的多數類樣本更為不重要，是要進行欠采樣的集合對象。

設初始訓練樣本集合為T，T=P?Q，其中P表示少數類樣本集合，Q表示多數類樣本集合。利用SVM對集合T進行訓練得到分類器為：

分類超平面為：

利用分類超平面可將少數類集合分為分對的集合P1和分錯的集合P2。P2即為要進行過采樣的對象，即：

對于集合Q，根據公式：

計算出所有多數類樣本點到超平面的距離r，然后根據采樣率得到較遠的多數類樣本即為集合Q′。

在算法中，找到集合P2和集合Q′后，直接刪掉集合Q′，然后對集合P2使用SMOTE算法迭代進行合成，將每次合成的新樣本加入到訓練集中，在每次迭代后測試分類器的分類性能并使用G-mean值進行比較，當G-mean開始減小時，迭代結束，即得到優化后的分類器。根據算法思想可以看出，訓練集將逐漸趨于平衡，使得SVM分類超平面慢慢向真實類邊界方向偏移直至最靠近真實類邊界。

3.2 迭代停止準則

將一個原始數據集分為訓練集和測試集，測試集不進行任何操作，設訓練集為T，集合T將訓練SVM分類器并對T進行混合采樣，重復此步驟。假設第t次迭代后得到的訓練集合為X，使用集合X訓練出新的分類器h(x)后，再使用集合X測試分類器h(x)，并使用非平衡問題中常用的評價標準幾何平均正確率G-mean值評價分類器的性能，若G-mean值逐漸增加，則說明所訓練出的分類器性能變好，迭代繼續；若G-mean值減小，則結束迭代，選擇當前訓練出的分類器作為最優分類器。

3.3 SVM_HS算法描述

SVM_HS的整體算法如算法2所示。

算法2SVM_HS算法

4 實驗過程及結果分析

4.1 評價標準

對于分類問題，一般使用分類精度作為標準來評價一個分類器的性能。但對于非平衡數據來說，由于傳統的分類算法更傾向于多數類樣本，僅僅使用準確率評價非平衡數據分類算法是不合適的，反映不出對少數類樣本的分類性能。因此，非平衡數據的評價標準也是數據挖掘領域中一項重要的研究內容。目前常用的評價標準主要有F-value、G-mean等。

在二分類問題中，常用的混淆矩陣[18-19]如表1所示。其中，TP表示少數類樣本被正確分類的數量，FN表示少數類樣本被錯誤分類的數量，TN表示多數類樣本被正確分類的數量，FP表示多數類樣本被錯誤分類的數量[20]。

Table 1 Confusion matrix of 2-class problem表1 二分類問題中的混淆矩陣

由此可以得到：

（1）分類準確率

（2）查準率

（3）查全率

（4）少數類的F-value[21]

式中，β是調整查準率和查全率所占比重的參數，通常取β=1。

（5）幾何平均正確率G-mean[22]

本文選用accuracy、F-value、G-mean作為評價算法性能的標準。

4.2 數據集描述

為了評價本文提出的SVM_HS算法的有效性并與同類方法進行對比，選用標準數據庫UCI中的8組非平衡數據集進行實驗和分析，選擇了不同平衡程度、不同樣本數量、不同領域的數據集進行實驗，使得數據集更具代表性。由于UCI中二類不平衡數據集較少，這里可以將部分數據集中的某些類別合并，形成二類不平衡數據集，例如，Segment數據集包含2 310個樣本，共有7個類別，可以將其中的第五類“window”作為少數類，而其余的所有類別進行合并形成多數類，這樣就可以形成一個二類的不平衡數據集。通過此方式，對UCI中的部分其他數據集也進行類似的修改，從而形成了需要的數據集。修改后的數據集詳細信息描述如表2所示。

Table 2 Experimental datasets description表2 實驗數據集描述

4.3 實驗設計與結果分析

本實驗采用十折交叉驗證方法，使用Matlab作為仿真環境并將LIBSVM工具箱作為實現工具。

在SVM_HS算法中，需要輸入訓練樣本集合T和每次迭代的采樣率δ，即少數類增加的百分比和多數類減少的百分比。由于需要迭代使得分類超平面逐漸趨于真實類邊界，因此每次采樣的樣本個數不宜太多，但為了排除人工的方法，為實驗設置恰當的采樣率，本文選取了幾個采樣率的值即10%、20%、30%、40%進行了實驗，使用3個數據集進行測試，并利用非平衡分類問題中的一般性評價標準F-value、G-mean進行評估。如表3和表4所示，可以看出，當采樣率為20%時F-value和G-mean的值普遍較高，因此本文將選取20%作為每次迭代實驗中的采樣率。

Table 3 F-value at different sampling rates表3 不同采樣率下的F-value

Table 4 G-mean at different sampling rates表4 不同采樣率下的G-mean

采樣率確定后，將本文算法SVM_HS與SVM算法、SMOTE+SVM算法和Borderline_SMOTE+SVM算法進行比較，并對accuracy、F-value、G-mean等評價指標進行分析。算法參數設置如下：支持向量機分類器選擇高斯核函數，核寬度為10，懲罰因子C為1 000，算法中SMOTE最近鄰參數k選取為6，采樣率為20%。實驗結果如表5所示。

Table 5 Accuracy,F-value,G-mean表5 分類準確率、F-value、G-mean

在表5中，相比較傳統的SVM算法，本文算法的準確率在多數數據集上只有小幅度的提高，且在個別數據集上有所降低。這說明在提高少數類的分類準確率的同時多數類的分類準確率可能會減小，但與兩種改進的算法相比，本文的準確率都有明顯提高。相比于準確率，F-value和G-mean更能作為非平衡數據整體分類性能的評價指標，往往能夠指示一個方法在非平衡數據集的分類性能好壞。表5顯示出，SVM_HS算法明顯優于SMOTE+SVM算法和Borderline_SMOTE+SVM算法，在數據集上得到了較好的實驗結果，有效提高了少數類和多數類的分類精度，說明本文算法有一定的優勢和可行性。

為了對比算法的優勢，圖3～圖5分別繪制了4種算法在8個數據集上的測試結果趨勢曲線。其中，橫坐標為4種算法策略，縱坐標為實驗取值范圍。通過這3個圖可以看出，使用SVM_HS方法進行混合采樣，少數類的分類性能有所上升。

實驗結果表明本文算法在少數類的數量有明顯劣勢的情況下，分類效果有較大的提高，能夠顯著提高少數類的分類精度，并具有良好的適應性。

Fig.3 Variation curve of precision圖3 準確率變化曲線圖

Fig.4 Variation curve of F-value圖4 F-value變化曲線圖

Fig.5 Variation curve of G-mean圖5 G-mean變化曲線圖

5 結束語

本文針對SVM算法在處理非平衡數據時分類超平面容易偏向少數類樣本的問題進行研究。首先利用SVM算法得到分類超平面；然后迭代進行混合采樣，主要包括刪除離分類超平面較遠的多數類樣本和對靠近真實類邊界的少數類樣本用SMOTE算法過采樣兩部分；使分類超平面逐漸靠近真實類邊界。本文算法通過在數據層面的改進，少數類的分類精度得到顯著提高。然而，本文僅在數據層面進行了改進，如何在算法層面進行改進，將是未來重點研究方向。