基于總類內(nèi)分布的松弛約束雙支持向量機

，

(北京科技大學(xué) 數(shù)理學(xué)院， 北京 100083)

支持向量機(support vector machine, SVM)[1]是模式識別領(lǐng)域中的一種有效算法， 最初由Cortes等[2]提出， 以解決二分類問題， 此后經(jīng)過眾多學(xué)者不斷研究而迅速發(fā)展起來。 Mangasarian等[3]提出廣義特征值近端支持向量機(generalized eigenvaluepro-ximal SVM, GEPSVM)， 首次通過構(gòu)造2個非平行平面來處理二分類問題。 在此基礎(chǔ)上， Jayadeva等[4]于2007年提出了雙支持向量機(twin support vector machine, TWSVM)。與SVM相比，TWSVM求解的是2個小規(guī)模的二次規(guī)劃問題(QPPs)而不是一個大規(guī)模的QPPs，這使得TWSVM的訓(xùn)練速度比SVM的更快。 受Fisher判別分析[5]的啟發(fā)，將類分布信息引入SVM構(gòu)造中開始普及。例如最小類方差支持向量機(minimum class variance SVM, MCVSVM)[6]、結(jié)構(gòu)正則支持向量機(structural regularized SVM, SRSVM)[7]等。 同樣， 將類分布信息引入SVM構(gòu)造中在TWSVM領(lǐng)域也得到了發(fā)展。 例如， Peng等[8]提出了魯棒最小類方差雙支持向量機(robust minimumclass variance TWSVM, RMCV-TWSVM)，將正、負(fù)類樣本點的類方差矩陣分別引入2個超平面的構(gòu)造中。Qi等[9]提出了結(jié)構(gòu)雙支持向量機(structural TWSVM, S-TWSVM)，將正、負(fù)類樣本各自聚類簇的協(xié)方差矩陣求和得到正、負(fù)類樣本的協(xié)方差矩陣，分別參與構(gòu)造分類超平面。以上2種算法都加入了類內(nèi)結(jié)構(gòu)信息,但是并沒有將樣本總的類內(nèi)分布信息考慮到每個SVM的構(gòu)造中。本文中將樣本的總類內(nèi)離散度矩陣加到每個SVM的公式中，這樣構(gòu)造超平面考慮得更加全面。同時，還可以解決線性RMCV-TWSVM中類方差矩陣不可逆的問題。雖然TWSVM算法在不斷完善，但是在TWSVM領(lǐng)域，對于噪聲處理的算法還不是很成熟。其中最基本的做法是在目標(biāo)函數(shù)中引入樣本的模糊隸屬度來處理不同的樣本。例如，Khemchandani等[10]提出模糊雙支持向量機(fuzzy twin support vector machine, FTSVM)，根據(jù)距離理念來設(shè)計隸屬度函數(shù)。丁勝鋒等[11]提出基于混合模糊隸屬度的FTSVM，將距離與緊密度相結(jié)合來設(shè)計模糊隸屬度函數(shù)。由于目標(biāo)函數(shù)對變化比較敏感，因此傳統(tǒng)的算法可能會導(dǎo)致不理想的分類結(jié)果?；谝陨戏治?，本文中提出一種新的方法來處理噪聲樣本，即松弛約束條件，不僅提出松弛約束的隸屬度函數(shù)，而且將一對約束參數(shù)項引入到模型的構(gòu)造中，以達到減少噪聲值影響的目的。同時還考慮樣本總的類內(nèi)分布信息，最后提出一類基于總類內(nèi)分布的松弛約束雙支持向量機(TWCD-RTSVM)。

1　TWSVM模型

給定訓(xùn)練樣本集T={(xj,yj),j=1,2,…,m}，其中xj∈n,j=1 ,2 ,…,m為行向量，表示樣本的輸入，yj={1, -1}為相應(yīng)的類別， 當(dāng)yi=1時樣本屬于正類， 當(dāng)yj=-1時樣本屬于負(fù)類。 假設(shè)樣本集中正、 負(fù)類的樣本數(shù)分別為m1和m2，這里m=m1+m2。 不妨設(shè)xj(j=1, 2, …,m)為正類樣本，xj(j=m1+1, …,m1+m2)為負(fù)類樣本。 矩陣A∈m1×n和B∈m2×n分別為訓(xùn)練集正、負(fù)類樣本構(gòu)成的矩陣，CT=(ATBT)，C∈m×n為全體訓(xùn)練集樣本構(gòu)成的矩陣，且A和B的第i行Ai,Bi∈n分別為正、負(fù)類的樣本點。

對于線性的情形，標(biāo)準(zhǔn)的TWSVM旨在尋找一對分類超平面

xTω1+b1=0，
xTω2+b2=0，

其模型為

(1)

式中：x∈n為列向量；法向量ω1,ω2∈n;b1,b2∈;c1,c2>0為懲罰參數(shù)；ζ1∈m2,ζ2∈m1為松弛向量；e1∈m1,e2∈m2為分量全是1的列向量。

通過引入Lagrangian函數(shù)，得到問題(1)的對偶問題，即

(2)

式中：H=(Ae1);G=(Be2)；α∈m2,γ∈m1為Lagrangian乘子。求得原問題的解為

新樣本點x∈n的類別取決于決策函數(shù)

對于非線性的情形，需要利用核函數(shù)建立一對標(biāo)準(zhǔn)的TWSVM非線性分類超平面

K(xT,CT)u1+b1=0，
K(xT,CT)u2+b2=0，

式中：K為核函數(shù)，K(xT,y)=φ(xT)φ(y),x,y∈n為列向量，K(xT,CT)∈1×m的每個分量為實數(shù)，φ(·)為低維樣本空間n到高維Hilbert空間H的一個非線性映射；為CT的第i列；u1,u2∈n為列向量。

非線性模型為

(3)

非線性模型的求解過程與線性模型的求解過程類似，求得原問題的解為

式中：S=(K(A,CT)e1)；R=(K(B,CT)e2)。

新樣本點x∈n的類別決策函數(shù)為

2　TWCD-RTSVM的構(gòu)造與求解

Shao等[12]在TWSVM算法被提出來后，提出了正則雙支持向量機(twin bounded SVM, TBSVM)，其主要改進是在目標(biāo)函數(shù)中加入了正則項，實現(xiàn)了結(jié)構(gòu)風(fēng)險最小化原則。下面將總類內(nèi)分布因素(總類內(nèi)離散度矩陣)引入到正則項中，使得2類樣本在以最大限度分離的同時保證類內(nèi)結(jié)構(gòu)盡量緊密。

(4)

為了避免目標(biāo)函數(shù)對數(shù)據(jù)變化過度敏感，對約束條件進行模糊設(shè)置，以一對約束參數(shù)項的形式體現(xiàn)在模型的構(gòu)造中，以提高模型的抗噪聲能力。再結(jié)合式(4)中的總類內(nèi)離散度矩陣，提出新模型。

下面從線性和非線性2個方面提出TWCD-RTSVM模型。

2.1　TWCD-RTSVM線性模型

s.t.-(Bω1+e2b1)+ζ1≥E1,ζ1≥0

,

(5)

s.t.(Aω2+e1b2)+ζ2≥E2,ζ2≥0

,

(6)

其中E1∈m2、E2∈m1為各分量相等的約束參數(shù)向量(定義詳見第3節(jié))。

TWCD-RTSVM的第1項是結(jié)構(gòu)正則項，實現(xiàn)了結(jié)構(gòu)風(fēng)險最小化原則。同時引入類內(nèi)緊密性因素，使得TWCD-RTSVM的目標(biāo)函數(shù)在理論上比TBSVM的目標(biāo)函數(shù)更為理想。第2項是緊密項，最小化是為了保證超平面接近對應(yīng)類的樣本。第3項是錯分項，最小化是為了降低另一類樣本的錯分程度。約束條件要求其中一類的樣本以一定的誤差盡可能遠離另一類樣本的超平面。

為了求解模型(5)、(6)，給出如下引理1、2及定理1。

當(dāng)m-2≥n時，如果r(C)=n且CT的第2列到第n+1列線性無關(guān)，則r(CTD)=n。

證明略。

引理2設(shè)Sw為樣本的總類內(nèi)離散度矩陣，根據(jù)式(4)，當(dāng)m-2≥n時，如果r(C)=n且CT的第2列到第n+1列線性無關(guān)，則Sw為對稱正定矩陣。

r(D)=r(T1)+r(T2)=(m1-1)+(m2-1)=m-2。當(dāng)m-2≥n，r(C)=n且CT的第2列到第n+1列線性無關(guān)時，由引理1，r(CTD)=n，即Sw滿秩，因此Sw是對稱正定矩陣。

定理1在引理2的條件下，線性模型(5)、(6)的對偶問題分別為

s.t.0≤α≤c2e2

,

(7)

和

s.t.0≤γ≤c4e1

,

(8)

證明：優(yōu)化問題(5)的Lagrangian函數(shù)為

L(ω1,b1,ζ1,α,β)=

αT[-(Bω1+e2b1)+ζ1-E1]-βTζ1,

(9)

對上式變量ω1、b1、ζ1求偏導(dǎo)并令其等于0，根據(jù)Karush-Kuhn-Tucker(簡稱KKT)條件可得

(10)

(11)

，

(12)

-(Bω1+e2b2)+ζ1≥E1,ζ1≥0

，

(13)

αT[-(Bω1+e2b1)+ζ1-E1]=0,βTζ1=0 ，

(14)

α≥0,β≥0

。

(15)

由式(10)、(11)得

(16)

(17)

由式(17)得

(18)

將式(18)及KKT條件代入式(9)，可得問題(5)的對偶問題為

s.t.0≤α≤c2e2。

同理，得到問題(6)的對偶問題為

s.t.0≤γ≤c4e1,

以及

(19)

定理1得證。

由定理1，求解對偶問題可得到模型(5)、(6)的解z1和z2。對于新樣本點x∈n，類別標(biāo)簽取決于決策函數(shù)

2.2　TWCD-RTSVM非線性模型

s.t.-(K(B,CT)u1+e2b1)+ζ1≥E1,ζ1≥0,

(20)

s.t.(K(A,CT)u2+e1b2)+ζ2≥E2,ζ2≥0。

(21)

φ(A)φ(CT)-φ(CT)Tφ(A)Te1q1φ(CT)]u1=

為了求解模型(20)、(21)，給出定理2，證明過程與線性情形的證明過程類似。

定理2非線性模型(20)、(21)的對偶問題分別為

s.t.0≤α≤c2e2

,

(22)

和

s.t.0≤γ≤c4e1

,

(23)

證明：通過lagrangian函數(shù)及KKT條件得

原問題的對偶問題為模型(22)、(23)。

由定理2，求解對偶問題可得到模型(20)、(21)的解p1和p2。對于新樣本點x∈n，其類別決策函數(shù)為

3　約束參數(shù)項E1和E2的設(shè)置

在實際應(yīng)用中，針對一些樣本點(噪聲點或離群值)不能被準(zhǔn)確分類的情況，采取在約束條件中引入松弛約束的隸屬度函數(shù)來減少噪聲的影響。

對標(biāo)準(zhǔn)TWSVM模型(1)中的不等式約束進行如下處理，

(24)

(25)

基于文獻[14]，對上述松弛約束進行處理，提出TWSVM松弛約束條件的隸屬度函數(shù)。

定義1松弛約束的隸屬度函數(shù)設(shè)在論域U1=n+1+m2上給定映射μ1∶n+1+m2→[0, 1]， 在論域U2=n+1+m2上給定映射μ2∶n+1+m1→[0,1]，μ1和μ2分別定義為

μ1(ω1,b1,ζ1)=

μ2(ω2,b2,ζ2)=

則稱μ1和μ2分別為松弛約束條件(24)和(25)的隸屬度函數(shù)。其中d1和d2分別為模型(1)中2類不等式約束集允許違反的程度。

定義2松弛約束的α截集對?α∈[0,1]，稱集合

P1(α)={(ω1,b1,ζ1)∈n+1+m2|μ1(ω1,b1,ζ1)≥α},

P2(α)={(ω2,b2,ζ2)∈n+1+m1|μ2(ω2,b2,ζ2)≥α}

分別為松弛約束條件(24)、(25)的α截集。

由定義2，分別選取松弛約束條件(24)的α1截集和松弛約束條件(25)的α2截集，即有

-(Bω1+e2b1)+ζ1≥e2[1-d1(1-α1)]，

Aω2+e1b2+ζ2≥e1[1-d2(1-α2)]。

取約束參數(shù)向量E1=e2[1-d1(1-α1)]=e2v1，E2=e1[1-d2(1-α)]=e1v2，則得到TWCD-RTSVM模型的約束參數(shù)向量。

對于給定的(ω1,b1,ζ1)∈n+1+m2(或(ω2,b2,ζ2)∈n+1+m1)，d1(或d2)越大，負(fù)類樣本(或正類樣本)違反約束的程度越大，此時一些訓(xùn)練數(shù)據(jù)可視為噪聲值或者異常值。αi(i=1,2)為松弛約束條件(24)、 (25)隸屬度的下限，αi(i=1,2)越大， 則隸屬度取值越大， 樣本的確定性越高， 樣本是噪聲值的可能性越小。 當(dāng)對正、 負(fù)類樣本賦予相等的松弛程度(d1=d2)時， 如果α1>α2， 則v1>v2， 從而負(fù)類樣本遠離正類樣本的程度大于正類樣本遠離負(fù)類樣本的程度， 正類樣本的確定性高于負(fù)類樣本的，反之亦然。

綜上所述，di和αi(i=1, 2)的不同取值， 即vi(i=1,2)的不同取值， 會對分類噪聲值或者異常值產(chǎn)生一定的影響， 即對vi(i=1,2)合理取值能減少噪聲值或者異常值對分類結(jié)果的影響， 從而提高分類精度。 在第4節(jié)中將利用數(shù)值實驗來驗證該結(jié)論。

4　實驗與分析

4.1　評價標(biāo)準(zhǔn)

混淆矩陣[15]和受試者工作特征(receiver operating characteristic，ROC)曲線[16]是測量分類正確率的常用方法?；煜仃囃ㄟ^樣本的真實結(jié)果與分類器預(yù)測的結(jié)果來計算正確率，混淆矩陣的結(jié)構(gòu)見表1。

表1　混淆矩陣的結(jié)構(gòu)

注：nTP和nTN分別為正、負(fù)類樣本被分類器正確分類的樣本數(shù)；nFP為分類器將負(fù)類樣本誤分成正類樣本的樣本數(shù)；nFN為分類器將正類樣本誤分成負(fù)類樣本的樣本數(shù)。

分類正確率為所有樣本中被正確分類的樣本所占的比例，即

式中：a為分類正確率；nTP和nTN分別為正、負(fù)類樣本被分類器正確分類的樣本數(shù)；nFP為分類器將負(fù)類樣本誤分成正類樣本的樣本數(shù)；nFN為分類器將正類樣本誤分成負(fù)類樣本的樣本數(shù)。

從混淆矩陣中還可以計算出假正率(false positive rate，F(xiàn)PR)和真正率(true positive rate，TPR)，即

式中：fFPR為假正率；fTPR為真正率。

ROC曲線描述的是分類混淆矩陣中FPR和TPR這2個量之間的相對變化情況。在TPR隨著FPR不斷增大的情況下，如果TPR增長得比FPR快，那么曲線靠近圖形左上角的程度越大，曲線下的面積(area under the curve, AUC)越大，模型的分類性能也就越好，因此，可以通過計算AUC值來判斷分類器的性能。

4.2　TWCD-RTSVM模型實驗

選用UCI機器學(xué)習(xí)庫中的6個數(shù)據(jù)集進行數(shù)值實驗，即Hepatitis、Glass、Heart-statlog、Ecoli、BUPA和Monk_3，其中Glass和Ecoli為多分類數(shù)據(jù)集。由于本文中模型針對的是二分類問題，因此對多分類數(shù)據(jù)集Glass和Ecoli進行處理。取Glass集的類7為正類，其余各類歸并成負(fù)類；把Ecoli集的Cp類和Im類歸并成正類，其余各類歸并成負(fù)類。將以上2類重新命名為Glass7和Ecoli12。6個數(shù)據(jù)集的詳細信息見表2。

表2　數(shù)據(jù)集描述

通過混淆矩陣求解各分類器在上述6個數(shù)據(jù)集上的線性和非線性分類效果，實驗結(jié)果分別見表3、4，其中分類正確率的最大值用黑體標(biāo)出。由表3、4可知：1)在時間方面，TWSVM算法的耗時明顯少于SVM的。與其他4種TWSVM算法相比，本文中所提算法TWCD-RTSVM的運行時間不相上下，在個別數(shù)據(jù)集上甚至耗時最少。總之，TWCD-RTSVM分類算法具有較高的分類效率。2)在正確率方面，無論是線性模型還是非線性模型，與其他分類算法相比，TWCD-RTSVM在上述數(shù)據(jù)集中的表現(xiàn)較好，分類正確率最高。在某些數(shù)據(jù)集上，個別分類算法與TWCD-RTSVM具有同樣高的分類精度。例如，在Monk_3數(shù)據(jù)集中，RMCV-TWSVM與TWCD-RTSVM分類正確率相等，且都達到最高；在Glass7數(shù)據(jù)集中，TWCD-RTSVM甚至與多個分類算法都達到最高分類正確率。另外，與FTSVM相比，TWCD-RTSVM分類正確率較高，即抗噪聲性能優(yōu)于FTSVM的?？傊琓WCD-RTSVM有很高的分類正確率及減噪能力。

實驗過程中線性算法的最優(yōu)參數(shù)見表5，其中，TWCD-RTSVM算法給出了使得不同數(shù)據(jù)集取得較好分類性能的參數(shù)v1和v2。前4個數(shù)據(jù)集在v1和v2取值不斷變化時分類正確率的直觀變化示意圖見

表3　各分類器的線性分類效果

表4　各分類器的非線性分類效果

圖1。由圖可知，4個數(shù)據(jù)集取得的最大分類正確率與最優(yōu)參數(shù)值與表5中的數(shù)值相一致。對于Hepatitis和Heart-statlog數(shù)據(jù)集來說，當(dāng)v1和v2取值較大(接近1)時，TWCD-RTSVM算法表現(xiàn)出較好的分類性能；對于Glass7和Ecoli12數(shù)據(jù)集來說，當(dāng)v1和v2取值較小(小于0.5)時，TWCD-RTSVM算法已經(jīng)表現(xiàn)出較好的分類性能，且在v1和v2的大部分取值范圍內(nèi)TWCD-RTSVM算法保持了較高的分類正確率，即算法比較穩(wěn)定。

在ROC分析中， 通過求AUC值來測量分類算法的性能， AUC值越大， 說明分類算法越好。 為了實驗簡便， 模型中涉及的懲罰參數(shù)取值均為1。 求得上述各數(shù)據(jù)集在TWSVM、 FTSVM、 TBSVM、 RMCV-TWSVM和TWCD-RTSVM 5種線性TWSVM算法下的AUC值情況見表6，其中AUC最大值用黑體標(biāo)出。由表可知，TWCD-RTSVM在上述數(shù)據(jù)集中的表現(xiàn)較好， 代表分類性能的AUC值最大。 在Monk-3數(shù)據(jù)集中， TWCD-RTSVM與TWSVM模型的AUC值相等， 且都達到最大值。

表5　各分類器的最優(yōu)參數(shù)

(a) 數(shù)據(jù)集Hepatitis(b) 數(shù)據(jù)集Glass7(c) 數(shù)據(jù)集Heart-statlog(d) 數(shù)據(jù)集Ecoli12圖1 4個數(shù)據(jù)集條件下參數(shù)v1和v2對分類正確率的影響

表6　5種TWSVM算法在6個數(shù)據(jù)集上的AUC值

5　結(jié)論

本文中提出了一種TWCD-RTSVM模型。主要結(jié)論如下：

1)該模型從模糊集的思想出發(fā)，對部分約束不等式集進行松弛處理，提出松弛約束的隸屬度函數(shù)，進而構(gòu)造出一對約束參數(shù)項來松弛約束條件，使得參數(shù)項合理取值后達到了減少噪聲影響的目的。同時將整體類分布信息引入到模型的正則項中，實現(xiàn)了結(jié)構(gòu)風(fēng)險最小化原則。實驗結(jié)果表明，TWCD-RTSVM算法具有較好的分類性能。

2)TWCD-RTSVM與4種TWSVM算法的對比實驗結(jié)果表明，約束參數(shù)項和總類內(nèi)分布信息的引入使得TWCD-RTSVM算法不僅分類正確率最高，而且具有較強的魯棒性。在以后的研究中應(yīng)致力于進一步探索參數(shù)項的構(gòu)造與選擇，以及將其應(yīng)用到多分類問題。