，

(北京科技大學(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)造中，以達(dá)到減少噪聲值影響的目的。同時還考慮樣本總的類內(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項是錯分項，最小化是為了降低另一類樣本的錯分程度。約束條件要求其中一類的樣本以一定的誤差盡可能遠(yuǎn)離另一類樣本的超平面。

為了求解模型(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ù)類樣本遠(yuǎn)離正類樣本的程度大于正類樣本遠(yuǎn)離負(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ù)集的詳細(xì)信息見表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分類正確率相等，且都達(dá)到最高；在Glass7數(shù)據(jù)集中，TWCD-RTSVM甚至與多個分類算法都達(dá)到最高分類正確率。另外，與FTSVM相比，TWCD-RTSVM分類正確率較高，即抗噪聲性能優(yōu)于FTSVM的?？傊?，TWCD-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值相等， 且都達(dá)到最大值。

表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ù)項合理取值后達(dá)到了減少噪聲影響的目的。同時將整體類分布信息引入到模型的正則項中，實現(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)用到多分類問題。