嚴曉明

(福建師范大學 數(shù)學與信息學院, 福州 350117)

傳統(tǒng)的SVM算法通過分類超平面來判斷樣本的類別, 在解決不平衡數(shù)據(jù)的分類問題時, 分類結(jié)果會偏向于多數(shù)類樣本點集合, 使得少數(shù)類樣本點的分類正確率低, 而多數(shù)類分類準確率高.

當前針對不平衡數(shù)據(jù)集SVM分類的改進, 一般集中在數(shù)據(jù)清洗和算法改進兩個方向上. 許多學者都提出了具有代表性的改進方法, 如對于樣本的欠采樣方法 SMOTE[1], 過采樣方法 Tomek links[2]以及它們相應(yīng)的改進算法[3,4], 都是通過不同方法增加少數(shù)類樣本或減少多數(shù)類樣本, 來達到使得不同類別中的樣本數(shù)量基本相當?shù)哪康? 在算法層面上, 代價敏感學習方法[5]對不平衡數(shù)據(jù)集中少數(shù)類和多數(shù)類分別設(shè)置不同的懲罰參數(shù), 通過調(diào)整不同類別的懲罰參數(shù), 提高不平衡數(shù)據(jù)集的分類效果, Huang[6]改進了代價敏感學習, 通過結(jié)合極限學習機來實現(xiàn)動態(tài)代價敏感學習; 集成學習方法[7]提出構(gòu)造不同的弱分類器, 對每個弱分類器設(shè)置一個權(quán)重并組合成一個強分類器對不平衡數(shù)據(jù)集進行分類, 在集成學習方法的基礎(chǔ)上, Zi?ba M 等人[8]還結(jié)合了主動學習策略對每個弱分類器的代價函數(shù)進行改進.

對樣本數(shù)量的增減, 都會改變使得原始樣本數(shù)據(jù)的分布, 使得分類超平面的位置產(chǎn)生偏差; 而設(shè)置不同類別懲罰參數(shù)的方法, 對于不同的不平衡數(shù)據(jù)集中每個類別樣本數(shù)量和分布情況, 較難對懲罰參數(shù)的值進行預(yù)設(shè). 本文提出了一個在保持原數(shù)據(jù)樣本不變的情況下, 應(yīng)用SMO算法解拉格朗日優(yōu)化方程參數(shù)的同時, 利用不同類別的樣本分布特點構(gòu)造出權(quán)重值, 并對超平面方程中的參數(shù)進行優(yōu)化的方法. 實驗結(jié)果表明,分類結(jié)果中不平衡數(shù)據(jù)集少數(shù)類的分類正確率更高,相應(yīng)的F1-Measure指標也得到了改善, 并且對于各種類別樣本分布情況的不平衡數(shù)據(jù)集, 有著較好的適應(yīng)能力.

1 樣本數(shù)量不平衡對分類超平面的影響

SVM算法要找的兩條間隔邊界是兩類別樣點中所有間距最小的樣本點之間的最大距離. 在不平衡數(shù)據(jù)集下生成分類超平面時, 之所以分類結(jié)果會偏向多數(shù)類樣本集, 本質(zhì)上是因為對所有類別的樣本點都使用相同的懲罰系數(shù).

在上文提到對不平衡數(shù)據(jù)集代價敏感的SVM算法中, 將懲罰參數(shù)設(shè)置為分別表示對于少數(shù)類樣本點和多數(shù)類樣本點松弛變量和的約束. 在應(yīng)用拉格朗日方法轉(zhuǎn)換成對偶問題時, 參數(shù)的求解變成了對的求解, 即實際上最后都變成了對值的約束:如公式(2)[5,9]:

用公式(2)的方式對不平衡數(shù)據(jù)集進行優(yōu)化時, 在算法運行前, 要人為設(shè)置兩個參數(shù)通過少數(shù)類樣本集設(shè)置的懲罰參數(shù)大于多數(shù)類樣本集的懲罰參數(shù), 即首先,要比預(yù)設(shè)值大多少, 是一個人工經(jīng)驗的問題, 由于樣本的分布和數(shù)量上的區(qū)別, 預(yù)設(shè)值的大小不容易確定; 其次, 這兩個參數(shù)最后轉(zhuǎn)換成條件又由于實際上是最后去判斷的大小, 公式可以合并成即用SMO算法求解時, 對不同類別的懲罰系數(shù)的作用被弱化成了對較小的那個懲罰系數(shù)的約束, 相應(yīng)地對分類效果的作用也弱化了.

2 參數(shù) b 與分類超平面的關(guān)系

圖1 不平衡數(shù)據(jù)集分類結(jié)果局部放大

對于圖1中的不平衡數(shù)據(jù)集而言, 生成的分類超平面如果能向多數(shù)類方向移動, 即圖1中實線向下移動, 在本例中相當于減小, 就會提高少數(shù)量樣本點的分類準確率.

3 參數(shù) b 針對少類樣本集的優(yōu)化

具體的優(yōu)化算法步驟如下:

在SMO算法的求解過程中, 迭代更新后, 會使得求得的分類超平面向多數(shù)類方向移動, 對不平衡數(shù)據(jù)集問題, 會使得少數(shù)類的分類正確率提高, F1-Measure指標得到改善, 并且由于僅在迭代過程中增加了若干條計算語句和一個分析是否為少數(shù)類樣本的判斷語句, 算法的時間復(fù)雜度沒有發(fā)生變化.

4 實驗與結(jié)果分析

下面設(shè)置了兩組數(shù)據(jù)在Matlab 2016a中來驗證本文算法(以下用SVM_Improved表示), 一組數(shù)據(jù)為上文中的人工數(shù)據(jù)集, 另一組為UCI[10]公共數(shù)據(jù)集中的6個不平衡數(shù)據(jù)集; 實驗環(huán)境的計算機配置為: CPU為core i5, 內(nèi)存 4 G, 操作系統(tǒng)為 Windows10.

4.1 人工數(shù)據(jù)集

圖2和本文第2節(jié)中的圖1分別是采用傳統(tǒng)SVM和SVM_Improved得到的分類超平面, 懲罰系數(shù)都為5.0.

圖2 本文算法生成的分類超平面放大圖

第2節(jié)圖1中的少數(shù)類分類正確率為50%, 多數(shù)類正確率為 100%, 即少數(shù)類分對 5 個, 分錯 5 個; 多數(shù)類分對210個, 沒有錯分樣本點; 支持向量一共16個,支持向量中少數(shù)類和多數(shù)類各一半, 少數(shù)類的F1-Measure為0.67. 圖2中的少數(shù)類正確率為90%, 多數(shù)類正確率為 97.14%, 少數(shù)類分對 9 個, 分錯 1 個, 多數(shù)類分對204個, 分錯6個. 支持向量的情況和圖1中相同, 而少數(shù)類F1-Measure為0.93. 圖1中的分類超平面方程為:而圖2的為兩個算法的實際分類面間隔都為0.48. 從該數(shù)據(jù)集的實驗上可以看到, 采用SVM_Improved算法, 參數(shù)的值變化后, 分類超平面更靠近多數(shù)類樣本集, 使得少數(shù)類樣本點的分類性能得到較大的提升.

4.2 UCI中的不平衡數(shù)據(jù)集

從UCI中抽取6個不同的不平衡數(shù)據(jù)集, 分別為heart disease, balance scale, yeast, abalone, haberman,ecoli. 如表1 所示.

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

在這6個UCI數(shù)據(jù)中, 不平衡數(shù)據(jù)集里有多個類別的, 將其中的一個或若干個類別合并設(shè)置為少數(shù)類,即表1中為目標類別列, 而將其余類別的樣本合并設(shè)置為多數(shù)類. 如數(shù)據(jù)集yeast中, 將類別標簽為ME1,ME2和ME3這三個類別的44,51,163個樣本合并成少數(shù)類, 而將剩余的標簽為CYT等7個類別共1226個樣本組成多數(shù)類. 每個數(shù)據(jù)集少數(shù)類和多數(shù)類樣本數(shù)的對比為表1中的最后一列. 這四個數(shù)據(jù)集中, heart disease選擇的是Cleveland數(shù)據(jù)庫; abalone數(shù)據(jù)集的多數(shù)類與少數(shù)類樣本數(shù)相差最大, 達到129倍, 其它五個數(shù)據(jù)集的多數(shù)類與少數(shù)類樣本數(shù)相差5至15倍之間.

對這6個數(shù)據(jù)集的實驗結(jié)果如表2所示, 其中Pr、Re 和 F1_M 分別表示 Precision(查準率), Recall(召回率)和F1-Measure. 算法SVM_1為對少數(shù)類和多數(shù)類分別設(shè)置不同的懲罰參數(shù)的代價敏感學習方法. 在實驗中, 懲罰參數(shù)都為5, 算法SVM_1中對少數(shù)的懲罰參數(shù)為5, 對多數(shù)類的懲罰參數(shù)為3.

從表2的數(shù)據(jù)中可以看出: 對于兩個類別樣本數(shù)量不同的多個不平衡數(shù)據(jù)集中, SVM_Improved算法的少數(shù)類樣本F1_measure的值都有不同程度的提升. 特別地對于haberman數(shù)據(jù)集, 由于屬性數(shù)只有4個, 并且這些屬性值為整數(shù)又較接近, 即兩類樣本點在分類超平面附近有較多的分布, 本文算法對于少數(shù)類的分類正確的樣本數(shù)較SVM_1算法多了11, 雖然此時的多數(shù)類樣本點的分類正確的數(shù)量有一定的下降, 但是最后少數(shù)類F1_measure的值提升較大; 對于ecoli數(shù)據(jù)集, 樣本屬性值的特點和haberman數(shù)據(jù)集類似, 屬性數(shù)增加到8個, 少數(shù)類分類正確的樣本較SVM_1增加了13%左右, 和haberman數(shù)據(jù)集的結(jié)果接近.

表2 實驗結(jié)果對比 (單位: %)

對于 abalone 數(shù)據(jù)集, 樣本相差 129 倍時, TP 增加從17個樣本增加到25個樣本, 少數(shù)類分類正確的數(shù)量提高的同時多數(shù)類識別錯誤的樣本數(shù)也較SVM算法增加了12個樣本, F1-Measure的值增加了近5%, 該數(shù)據(jù)集的F1-Measure指標的提升也與haberman,ecoli這樣的數(shù)據(jù)集接近. heart-disease, balance scale,yeast三個數(shù)集的TP分別較SVM算法增加了2,4,7個樣本, 即少數(shù)類樣本分類正確數(shù)量增加了2%至5%,多數(shù)類正確率基本不變.

5 結(jié)語

本文提出一種改進不平衡數(shù)據(jù)集少數(shù)類樣本分類精確度的SVM_Improved方法, 在求解的過程中, 結(jié)合了不平衡數(shù)據(jù)集中的每個類別的支持向量個數(shù)和樣本總數(shù)以及多數(shù)類和少數(shù)類樣本的正確率比生成一個參數(shù)對SVM的分類超平面參數(shù)進行優(yōu)化. 實驗結(jié)果表明, 該方法改善了不平衡數(shù)據(jù)集的少數(shù)類F1-Measure指標, 特別在分類超平面附近有較多的少數(shù)類支持向量的數(shù)據(jù)集, 少數(shù)類樣本點的正確率有較大改進.