適用于不平衡數據集分類的改進SVM算法*

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

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

0 引 言

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

針對不平衡數據，為了獲得更好的預測結果，現有的SVM算法通常從數據和算法2個方面進行改進：

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

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

本文結合上述2種方法的優點，提出了改進的SVM算法，在對不平衡數據進行測試中取得了滿意的效果。

1 不平衡數據集對SVM的影響

考慮SVM算法的優化問題

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

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

(1)

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

2 改進的SVM算法

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

圖1 改進的SVM算法框架

2.1 ADASYN過采樣

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

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

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

(2)

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

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

(3)

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

(4)

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

gi=Γi×G

(5)

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

(6)

2.2 權值計算

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

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

(7)

(8)

式中δ>0，用于防止權值為0。可以看出：離中心點越遠，權值越接近0，而離中心點越近，權值越接近1，從而有效抑制了噪聲的影響。

2.3 DEC算法訓練

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

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

(9)

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

(10)

3 實驗與分析

3.1 測試指標

在機器學習中，其算法的性能通常可以由混淆矩陣概括。如表1所示，其中TP為預測正確的少類樣本數目，TN為預測正確的多類樣本數目，FP為預測錯誤的多類樣本數目，FN為預測錯誤的少類樣本數目。

表1 混淆矩陣

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

(11)

(12)

(13)

3.2 數據集

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

表2 不平衡數據集

3.3 測試方法

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

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

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

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

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

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

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

(14)

4 實驗結果

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

改進SVM算法在不同數據集上的結果如表3所示。可以看出:使用G-mean作為參數選擇標準時，少類樣本的準確率SE和多類樣本的準確率SP相差較小，能夠取得較為平衡的分類結果。

表3 改進SVM算法結果 %

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

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

5 結 論

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

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

[2] 陶泳任,陳冠雄,沈海斌.便攜心電傳感器的心房肥大診斷研究[J].傳感器與微系統,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] 卞桂龍,丁 毅,沈海斌.適用于智能傳感器系統的SVM集成研究[J].傳感器與微系統,2014,33(8):44-47.

[6] 王 成,郝順義,翁大慶,等.基于混沌PSO算法優化LS-SVM的慣導系統測試[J].傳感器與微系統,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] 陶新民,郝思媛,張冬雪,等.不均衡數據分類算法的綜述[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.