適用于不平衡數(shù)據(jù)集分類的改進SVM算法*

劉東啟， 陳志堅， 徐 銀， 李飛騰

(浙江大學 超大規(guī)模集成電路設(shè)計研究所,浙江 杭州 310027)

0 引 言

現(xiàn)實生活的很多分類問題，如故障診斷[1]、疾病檢測[2]等均涉及不平衡數(shù)據(jù)的分析與處理。傳統(tǒng)的分類算法均基于數(shù)據(jù)平衡的理論，當數(shù)據(jù)集不平衡時，傳統(tǒng)的分類器不能得到理想的分類結(jié)果。支持向量機[3，4](support vector machine,SVM)算法作為一種通用性的學習方法已被廣泛應用于各個領(lǐng)域[5,6]。盡管如此，對于不平衡數(shù)據(jù)，SVM通常也只能得到次優(yōu)的分類結(jié)果[7～8]。

針對不平衡數(shù)據(jù)，為了獲得更好的預測結(jié)果，現(xiàn)有的SVM算法通常從數(shù)據(jù)和算法2個方面進行改進：

1)數(shù)據(jù)層面解決策略：通過對訓練樣本進行重采樣，平衡多類樣本和少類樣本的數(shù)量。現(xiàn)有的數(shù)據(jù)重采樣方法主要有過采樣和降采樣2種方法。傳統(tǒng)的隨機過采樣(random oversampling,RAMO)技術(shù)常常導致過擬合；隨機降采樣(random undersampling,RAMU)技術(shù)可能會刪除有用的信息[9]。因此，出現(xiàn)了合成少類過采樣技術(shù)[10](synthetic minority oversampling technique,SMOTE)、自適應合成采樣[11](adaptive synthetic sampling,ADASYN)等多種過采樣方法和GSVM-RU[12]等降采樣方法。

2)算法層面解決策略：主要針對少類和多類樣本數(shù)量存在的差異，改進SVM訓練算法，增強算法本身對不平衡數(shù)據(jù)的學習效果。常見的方法有基于代價敏感的SVM算法、集成SVM算法、以及修改核函數(shù)等方法。

本文結(jié)合上述2種方法的優(yōu)點，提出了改進的SVM算法，在對不平衡數(shù)據(jù)進行測試中取得了滿意的效果。

1 不平衡數(shù)據(jù)集對SVM的影響

考慮SVM算法的優(yōu)化問題

s.t.yi(wTφ(xi)+b)≥1-ξi

ξi≥0,i=1,2,…,l

(1)

式中ξ為松弛變量；C為懲罰因子；w為權(quán)矢量；φ(x)為核空間映射函數(shù)；yi為特征向量xi對應的樣本標簽。式(1)的第一部分試圖最大化分類間隔，第二部分試圖最小化錯誤代價。對于平衡數(shù)據(jù)集，少類樣本和多類樣本的數(shù)量相同，使用相同的懲罰因子并不會引起超平面的偏移。對于不平衡數(shù)據(jù)集，少類樣本的數(shù)量遠少于多類樣本，若使用同樣的懲罰因子，則為了降低分類的整體的錯誤代價，超平面會偏向少類。分類算法上不支持或者未考慮不平衡數(shù)據(jù)是造成傳統(tǒng)SVM分類效果差的一個重要因素。

2 改進的SVM算法

選擇基于代價敏感的不同錯誤代價(different error cost,DEC)算法作為訓練算法。文獻[13]指出，DEC算法對少類樣本非常敏感，如果不平衡數(shù)據(jù)中少類樣本分布稀疏，通過DEC算法訓練得到的超平面形狀也會跟隨少類樣本的分布而在理想的超平面附近有較大波動，因此，選擇ADASYN作為重采樣技術(shù)在訓練前增加少類樣本的數(shù)目。此外，由于樣本中可能包含噪聲點，需要減少噪聲對SVM訓練結(jié)果的影響。因此，在SVM算法中引入權(quán)重因子，對每個樣本賦予不同的權(quán)值，正常樣本的權(quán)值高，而噪聲點的權(quán)值小，從而有效降低噪聲點的干擾。其算法流程如圖1所示。

圖1 改進的SVM算法框架

2.1 ADASYN過采樣

改進的SVM算法中選擇ADASYN作為過采樣算法，ADAYSN算法主要分為4個步驟：

1)計算少類樣本需要合成的樣本點的數(shù)量G

G=(|Smaj|-|Smin|)×β

(2)

式中Smaj為多類樣本數(shù)量;Smin為少類樣本數(shù)量;β∈(0,1]為修正比例。

2)對于每個少類樣本，使用KNN算法計算其合成樣本占合成樣本點總數(shù)量G的比例Γi

(3)

式中K為KNN算法的參數(shù)；Δi為距離xi最近的K個點中多類樣本的數(shù)目;Z為歸一化參數(shù)，其值為

(4)

3)決定每個少類樣本需要合成樣本的數(shù)目gi

gi=Γi×G

(5)

4)對于每個少類樣本，在距離其最近的K個樣本中隨機抽取一個樣本，合成新的少類樣本xnew

(6)

2.2 權(quán)值計算

噪聲點為距離自己所屬類別較遠甚至混入其他類別中的點，可以根據(jù)樣本距離類中心點的遠近確定噪聲點并賦予相應的權(quán)值。

對于少類樣本和多類樣本，假設(shè)其中心點的值為該類所有樣本點的平均值，并假設(shè)每個類別的半徑為中心點到屬于該類的距離最遠點的歐氏距離，即

(7)

(8)

式中δ>0，用于防止權(quán)值為0?？梢钥闯觯弘x中心點越遠，權(quán)值越接近0，而離中心點越近，權(quán)值越接近1，從而有效抑制了噪聲的影響。

2.3 DEC算法訓練

對于式(1)，規(guī)定多類的懲罰因子為C+，少類的懲罰因子為C-，得到DEC的優(yōu)化方程

s.t.yi(wTφ(xi)+b)≥1-ξi,ξi≥0,i=1,2,…,l

(9)

式中C+/C-=Smaj/Smin。同時，將權(quán)值計算的結(jié)果融合進DEC算法的參數(shù)C中，即可削弱噪聲的干擾。所以，DEC算法和權(quán)值計算相結(jié)合后，少類和多類的懲罰因子分別為

(10)

3 實驗與分析

3.1 測試指標

在機器學習中，其算法的性能通常可以由混淆矩陣概括。如表1所示，其中TP為預測正確的少類樣本數(shù)目，TN為預測正確的多類樣本數(shù)目，F(xiàn)P為預測錯誤的多類樣本數(shù)目，F(xiàn)N為預測錯誤的少類樣本數(shù)目。

表1 混淆矩陣

考慮到不平衡的情況下，少類樣本占據(jù)的比例非常小，當預測器對所有樣本的預測結(jié)果均為負時，預測準確率依然非常高。如果使用靈敏度(sensitivity,SE)和特異度(specificity,SP)作為少類和多類樣本的準確率，為了使二者均能獲得較高的準確率，在不平衡數(shù)據(jù)集中，使用G-mean作為性能測試標準

(11)

(12)

(13)

3.2 數(shù)據(jù)集

針對提出的模型，使用來自UCI的6個現(xiàn)實世界不平衡數(shù)據(jù)作為性能測試數(shù)據(jù)，數(shù)據(jù)集的詳細信息如表2所示。其包含少類樣本個數(shù)、樣本總數(shù)、數(shù)據(jù)集的特征數(shù)量以及少類與多類樣本比例。

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

3.3 測試方法

為了評估分類器的性能，使用五折交叉驗證的方法對數(shù)據(jù)集進行測試。其具體過程如下：

1)在MATLAB軟件中對數(shù)據(jù)進行預處理，將數(shù)據(jù)集隨機分為樣本數(shù)目相同的5份，并且每份擁有與原樣本相同的不平衡比例。

2)每折驗證中，將4份作為訓練集，1份作為預測集。

3)進行SVM算法的訓練:在訓練過程中，為了獲得最好的預測模型，使用LIBSVM[14]軟件包中的grid函數(shù)搜索最優(yōu)參數(shù)C和γ，并使用該參數(shù)對訓練集進行訓練，得到最優(yōu)預測模型。

4)采用預測模型對預測集進行預測，使用G-mean評估性能評估的標準。

在進行訓練中需要使用的參數(shù)，選取范圍如下：在ADASYN算法中的參數(shù)β，其范圍是{0.1,0.2,…,0.9}；對于權(quán)值計算中的參數(shù)δ，使用10-5；對于DEC算法，其使用RBF核函數(shù)

K(x,y)=e-γ(‖x-y‖2)

(14)

4 實驗結(jié)果

為了評估改進的SVM算法對不平衡數(shù)據(jù)的分類結(jié)果，使用DEC，SMOTE，ADASYN以及標準SVM作為實驗對比。對于每種算法，均使用與改進SVM算法相同的訓練預測方法，即基于LIBSVM使用五折交叉驗證。所有算法均使用5次結(jié)果的平均值作為最終結(jié)果。

改進SVM算法在不同數(shù)據(jù)集上的結(jié)果如表3所示?？梢钥闯?使用G-mean作為參數(shù)選擇標準時，少類樣本的準確率SE和多類樣本的準確率SP相差較小，能夠取得較為平衡的分類結(jié)果。

表3 改進SVM算法結(jié)果 %

表4給出了不同算法對6個數(shù)據(jù)集進行訓練預測的G-mean結(jié)果比較。對比改進SVM算法與其他SVM算法，結(jié)果顯示：在所有數(shù)據(jù)集中，復合SVM算法中有5個數(shù)據(jù)集具有最高的G-mean，余下1個接近最好算法的G-mean，G-mean值較其他算法平均高出了3.7 %～23.6 %。

表4 不同分類算法的G-mean比較 %

5 結(jié) 論

提出和實現(xiàn)了一種改進SVM算法，通過使用重采樣、權(quán)值計算、DEC算法訓練相結(jié)合的方法，消除不平衡數(shù)據(jù)對分類器訓練造成的影響。通過在6組數(shù)據(jù)集上與現(xiàn)有的常見算法比較，證明了改進SVM算法的可行性。實驗結(jié)果表明：在大多數(shù)情況下，改進SVM算法具有最高的G-mean值。將改進SVM算法應用到現(xiàn)實生活的不平衡分類中，尤其在疾病檢測或故障監(jiān)測等方面，將會有廣闊的應用前景。

[1] 王長坤,袁慎芳,邱 雷,等.基于支持向量機的加筋板健康監(jiān)測[J].傳感器與微系統(tǒng),2008,27(5):49-51.

[2] 陶泳任,陳冠雄,沈海斌.便攜心電傳感器的心房肥大診斷研究[J].傳感器與微系統(tǒng),2014,33(9):55-57.

[3] Vapnik V N,Vapnik V.Statistical learning theory[M].New York:Wiley,1998.

[4] Cortes C,Vapnik V.Support-vector networks[J].Machine Lear-ning,1995,20(3):273-297.

[5] 卞桂龍,丁 毅,沈海斌.適用于智能傳感器系統(tǒng)的SVM集成研究[J].傳感器與微系統(tǒng),2014,33(8):44-47.

[6] 王 成,郝順義,翁大慶,等.基于混沌PSO算法優(yōu)化LS-SVM的慣導系統(tǒng)測試[J].傳感器與微系統(tǒng),2011,30(2):125-128.

[7] He H,Garcia E A.Learning from imbalanced data[J].IEEE Transactions on Knowledge and Data Engineering,2009,21(9):1263-1284.

[8] 陶新民,郝思媛,張冬雪,等.不均衡數(shù)據(jù)分類算法的綜述[J].重慶郵電大學學報:自然科學版,2013,25(1):101-110.

[9] Branco P,Torgo L,Ribeiro R P.A survey of predictive modeling on imbalanced domains[J].ACM Computing Surveys,2016,49(2):1-50.

[10] Chawla N V,Bowyer K W,Hall L O,et al.SMOTE:Synthetic minority over-sampling technique[J].Journal of Artificial Intelligence Research,2002,16:321-357.

[11] He H,Bai Y,Garcia E A,et al.ADASYN:Adaptive synthetic sampling approach for imbalanced learning[C]∥2008 IEEE International Joint Conference on Neural Networks(IEEE World Congress on Computational Intelligence)，IEEE,2008:1322-1328.

[12] Tang Y,Zhang Y Q,Chawla N V,et al.SVMs modeling for highly imbalanced classification[J].IEEE Transactions on Systems,Man,and Cybernetics,Part B:Cybernetics,2009,39(1):281-288.

[13] Akbani R,Kwek S,Japkowicz N.Applying support vectormachines to imbalanced datasets[C]∥European Conference on Machine Learning，Berlin/Heidelberg:Springer,2004:39-50.

[14] Chang C C,Lin C J.LIBSVM:A library for support vectormachines[J].ACM Transactions on Intelligent Systems and Technology(TIST),2011,2(3):1-27.