基于總類內分布的松弛約束雙支持向量機

，

(北京科技大學 數理學院， 北京 100083)

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

1　TWSVM模型

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

對于線性的情形，標準的TWSVM旨在尋找一對分類超平面

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

其模型為

(1)

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

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

(2)

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

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

對于非線性的情形，需要利用核函數建立一對標準的TWSVM非線性分類超平面

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

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

非線性模型為

(3)

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

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

新樣本點x∈n的類別決策函數為

2　TWCD-RTSVM的構造與求解

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

(4)

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

下面從線性和非線性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為各分量相等的約束參數向量(定義詳見第3節)。

TWCD-RTSVM的第1項是結構正則項，實現了結構風險最小化原則。同時引入類內緊密性因素，使得TWCD-RTSVM的目標函數在理論上比TBSVM的目標函數更為理想。第2項是緊密項，最小化是為了保證超平面接近對應類的樣本。第3項是錯分項，最小化是為了降低另一類樣本的錯分程度。約束條件要求其中一類的樣本以一定的誤差盡可能遠離另一類樣本的超平面。

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

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

證明略。

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

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

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

s.t.0≤α≤c2e2

,

(7)

和

s.t.0≤γ≤c4e1

,

(8)

證明：優化問題(5)的Lagrangian函數為

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

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

(9)

對上式變量ω1、b1、ζ1求偏導并令其等于0，根據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，類別標簽取決于決策函數

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函數及KKT條件得

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

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

3　約束參數項E1和E2的設置

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

對標準TWSVM模型(1)中的不等式約束進行如下處理，

(24)

(25)

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

定義1松弛約束的隸屬度函數設在論域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)的隸屬度函數。其中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)]。

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

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

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

4　實驗與分析

4.1　評價標準

混淆矩陣[15]和受試者工作特征(receiver operating characteristic，ROC)曲線[16]是測量分類正確率的常用方法。混淆矩陣通過樣本的真實結果與分類器預測的結果來計算正確率，混淆矩陣的結構見表1。

表1　混淆矩陣的結構

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

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

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

從混淆矩陣中還可以計算出假正率(false positive rate，FPR)和真正率(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機器學習庫中的6個數據集進行數值實驗，即Hepatitis、Glass、Heart-statlog、Ecoli、BUPA和Monk_3，其中Glass和Ecoli為多分類數據集。由于本文中模型針對的是二分類問題，因此對多分類數據集Glass和Ecoli進行處理。取Glass集的類7為正類，其余各類歸并成負類；把Ecoli集的Cp類和Im類歸并成正類，其余各類歸并成負類。將以上2類重新命名為Glass7和Ecoli12。6個數據集的詳細信息見表2。

表2　數據集描述

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

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

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

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

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

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

表5　各分類器的最優參數

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

表6　5種TWSVM算法在6個數據集上的AUC值

5　結論

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

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

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