非均衡數(shù)據(jù)的支持向量機新方法

（1.西北工業(yè)大學 自動化學院 西安 710072； 2.西安電子科技大學 應用數(shù)學系 西安 710071）

摘 要：為了彌補支持向量機對非均衡樣本集分類時傾向于較大類的不足，提出一種平衡策略。基于Fisher判別思想，計算出兩類樣本在分類超平面法向量上投影后的均值和方差，再依據(jù)兩類錯分概率相等準則，給出新的閾值計算方法對超平面進行調(diào)整。該方法可補償非平衡數(shù)據(jù)分類的傾向性，提高預測分類精度。最后在非均衡的人工和真實數(shù)據(jù)集上的數(shù)值實驗表明了該方法的可行性與有效性。

關鍵詞：支持向量機; 非平衡數(shù)據(jù); 分類; 閾值

中圖分類號：TP181文獻標志碼：A

文章編號：1001-3695(2009)05-1654-02

New method for support vector machine based on imbalanced data

XIE Danrui1 HAN Jianxin1 XUE Huifeng1 DU Zhe2

(1.College of Automation Northwestern Polytechnical University Xi’an 710072 China; 2. Dept. of Applied Mathematics Xidian University，Xi’an 710071 China)

Abstract:Since support vector machine is unfair to the rare class for the classification of imbalanced data proposed an adjustment method of the separating hyperplane. Based on Fisher discrimination got the projected class mean and variance are by projecting two classes samples onto the normal vector of the separating hyperplane then adjustedthe threshold of the hyperplane according to the principle that error probability of two classes are equal. The proposed algorithm could compensate the illeffect of tendency and improved the accuracy. Simulations on imbalanced artificial and real data show that the feasibility and validity of the proposed method.

Key words：support vector machine(SVM); imbalanced data; classification; threshold

支持向量機(SVM)是一種基于統(tǒng)計學習理論的機器學習方法^[1]，由于其優(yōu)良的性能被廣泛應用，形成研究熱點。但SVM對非均衡數(shù)據(jù)分類時，對較少類不利，分類結果傾向于較大類^[2]，這限制了其在醫(yī)學診斷、金融分析、入侵檢測^[3]等典型非均衡問題方面的應用。為了解決不平衡問題，文獻[4]通過構造較少類樣本數(shù)量來補償與較大類的差距，達到平衡作用，但新樣本難以保證與原樣本同分布，且增加了訓練器負擔；文獻[5]提出減少較大類樣本數(shù)量來達到平衡，雖然會加快訓練速度，但這樣會減少樣本信息，且兩類樣本總錯誤率沒有得到下降；文獻[6]將上述兩種方法結合使用，但其結果未得到明顯改進；文獻[7]通過對兩類樣本實行不同的懲罰因子，以達到類別補償。傳統(tǒng)SVM的閾值是居于距兩超平面等距的中間值，這對于非均衡問題十分不利。不同于以上基于樣本數(shù)量的方法，本文從樣本統(tǒng)計分布角度出發(fā)，提出一種新的支持向量機閾值計算方法。而又由Fisher判別分析可知，投影點的均值和方差分別為樣本分布的均值和類內(nèi)散度的投影值^[8]，故本文充分利用非均衡數(shù)據(jù)的樣本統(tǒng)計信息，首先計算出兩類樣本在支持向量機分類超平面法向量上投影后的均值和方差，再依據(jù)兩類樣本錯分概率相等準則，求新的閾值。該方法平衡了錯誤率，彌補了對非均衡數(shù)據(jù)分類時的不足，最后通過數(shù)值實驗表明在平衡錯誤率的同時，總錯誤率也得到了下降。

1 支持向量機

SVM用兩個最大間隔的平行超平面將兩類樣本集{xi，yi}ni=1∈Rm×{+1，-1}盡可能地分開，核函數(shù)的匿名映射為φ(x)，則訓練樣本集變?yōu)?φ(xi)，yi)，分類超平面為ω#8226;φ(x)-b=0，從而轉(zhuǎn)換為求解問題：

min 1/2‖ω‖2+C∑ni=1ξi

s.t. yi[ω#8226;φ(xi)-b]-1+ξi≥0;

ξi≥0；i=1，2，…，n(1)

其中:C為常數(shù)。通過構造Lagrangian函數(shù)和鞍點條件，得到原問題式(1)的對偶規(guī)劃為

min 1/2∑ni=1∑nj=1αiαjyiyjK(xi，xj)-∑ni=1αi

s.t. ∑ni=1αiyi=0;0≤αi≤C

(2)

式（2）中K(xi，xj)=φ(xi)#8226;φ(xj)T為核函數(shù)。由此凸二次規(guī)劃可求得惟一最優(yōu)解α。0＜α＜C所對應的樣本點稱為支持向量，則分類超平面的法向量為

w=∑NSVi=1αiyiφ(xi)(3)

其中：NSV是支持向量的個數(shù)。選取某個支持向量xj，代入式(1)中約束條件，可得超平面的閾值為

b=∑NSVi=1yiαiK(xi#8226;xj)-yj

在實際計算中，為了防止累計誤差，使用式（4）計算閾值：

b=1/NSV∑NSVj=1

(∑NSVi=1yiαiK(xi#8226;xj)-yj)(4)

從而求得分類函數(shù)為

f(x)=sig n(∑ni=1αiyiK(xi#8226;x)-b)(5)

2 統(tǒng)計分析與閾值計算方法

支持向量機的分類超平面是按等距于兩平行超平面來確定的，而這對于不平衡數(shù)據(jù)顯然不合理，為此本文給出一種新閾值計算方法來平衡錯誤率。在SVM完成訓練得到分類超平面法向量w后，將所有樣本投影到w上，則根據(jù)這些一維數(shù)據(jù){wTxi}ni=1所提供的樣本統(tǒng)計信息來求得閾值b、平衡錯誤率以補償SVM的傾向性。

不失一般性，設較少類為正類，較大類為負類；假設兩類樣本的投影點y=wTx服從正態(tài)分布，即兩者概率密度函數(shù)為

p±(y)=1/（2πσ±） exp (-(y-μ±)2/（2σ2±)）

顯然對非均衡分類數(shù)據(jù)有μ+≠μ-，σ+≠σ-。按照正負類錯分類概率相等的準則有

∫+∞b p+(y)dy=∫b-∞ p(y)dy(6)

需求出使上式成立的b=b0即可。則b0應該滿足：

1-Φ((b0-μ+)/σ+)=Φ((b0-μ-)/σ-)或

Φ((μ+-b0)/σ+)=Φ((b0-μ-)/σ-)(7)

這里Φ(x)為一維標準正態(tài)分布函數(shù)，而(μ+-b0)/σ+及(b0-μ-)/σ-分別表示點b0到兩類中心μ+和μ-的一維馬氏距離。不同的正態(tài)分布下概率相等的點具有相等的馬氏距離，所以(μ+-b0)/σ+=(b0-μ-)/σ-，從而得出

b0=(σ-μ++σ+μ-)/(σ++σ-)(8)

則新的超平面為wTx=b0。樣本投影概率分布如圖1所示。

下面給出σ±和μ±的估計方法，設n+和n-分別為正負類樣本數(shù)，將線性與非線性情形統(tǒng)一描述，當映射φ(x)=x時即為線性分類。通過式(2)求得w=∑ni=1αiyiφ(xi)，則兩類樣本投影點的均值為

±=1/n± ∑n±i=1 wTφ(xi)=1/n± ∑n±i=1∑nj=1αjyjK(xj，xi)(9)

兩類樣本投影點方差為

2±=1/n± ∑n±i=1(wTφ(xi)-±)2=

1/n±∑n±i=1(∑nj=1αjyjK(xj，xi)-1/n±∑n±l=1∑nj=1αjyjK(xj，xl))2(10)

將式(9)和(10)代入式(8)則可求出：b0=(++-+-+)/(++-)。而在特征空間中兩類樣本均值和類內(nèi)散度矩陣分別為mφ±=1/n± ∑n±j=1φ(xj)和Sφ±=1/n± ∑n±i=1(φ(xi)-mφ±)(φ(xi)-mφ±)T，對于它們在w上投影顯然有^[8]wTmφ±=± 和wTSφ± w=2±。所以b0包含了樣本的一階二階統(tǒng)計信息。對于線性情形只需取核函數(shù)為線性核，即K(xi，xj)=xTixj；另外由于SVM的解具有稀疏性，即為非支持向量對應的αi=0，同樣只需使用支持向量進行閾值計算即可。

3 數(shù)值實驗

在CPU 2.6 GHz，RAM 512 MB的PC機上進行數(shù)值實驗，采用MATLAB 7.0.1軟件，SVM使用軟件包LibSVM 2.82^[9]。

首先在人工數(shù)據(jù)集上對SVM和本文的BSVM進行比較實驗。隨機產(chǎn)生兩類二維正態(tài)分布的樣本作為訓練集，正類為較小類，得到兩者的線性分類比較圖（圖2）。從圖2中可以看出，BSVM（虛線）降低了對正類的不公平；為了比較兩者的泛化能力，再完全按照上面正負類的分布隨機產(chǎn)生正負類樣本各100個作為測試集。分別取核函數(shù)為線性核和徑向基核(RBF:K(x，y)=exp(-γ‖x-y‖2) )，獨立運行10次取正確率平均值，得到圖3的線性和非線性情況的分類精度比較。其中：+/-train和+/-test分別表示正負類的訓練正確率和測試正確率；Atrain和Atest分別表示總的訓練和測試正確率。在圖3中可看出BSVM提高了正類的訓練正確率和測試正確率，但負類的正確率下降了，這是調(diào)整閾值的必然結果；但是BSVM的總測試正確率并未降低，這表明BSVM的總泛化能力并沒有下降。

再在UCI數(shù)據(jù)庫中幾個真實數(shù)據(jù)集上進行比較測試。表1為各個數(shù)據(jù)集的正負類訓練和測試的樣本數(shù)目，以及實驗時參數(shù)的選取值。選取核函數(shù)為RBF核，在相同的參數(shù)下進行10折交叉驗證得到SVM和BSVM的分類精度比較，如表2所示。

從表2中也可看出本文BSVM的優(yōu)勢：與傳統(tǒng)SVM相比，BSVM大大降低了正類分類錯誤率，且泛化能力也沒有下降；這也說明了本文從樣本統(tǒng)計分布角度出發(fā)的優(yōu)勢。

本文的理論分析雖是在假設樣本的投影滿足正態(tài)分布的條件下進行，但通過對真實數(shù)值實驗表明，本文方法的有效性并不僅僅局限于此。

4 結束語

本文提出一種用于非均衡數(shù)據(jù)的超平面