一種改進(jìn)的多分類孿生支持向量機(jī)

周開偉 錢雪忠 周世兵

(江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院 江蘇 無(wú)錫 214122)

0 引 言

支持向量機(jī)(Support Vector Machine，SVM)是Vapnik等在統(tǒng)計(jì)學(xué)習(xí)理論的基礎(chǔ)上提出的一種用于二分類的機(jī)器學(xué)習(xí)算法[1]。該算法在解決小規(guī)模樣本的分類問題上比一些其他算法有更好的性能，故對(duì)SVM的相關(guān)研究受到了極大的重視。為了進(jìn)一步提高SVM的性能，2007年Jayadeva等在廣義特征值近似支持向量機(jī)的基礎(chǔ)上提出了求解二分類問題的孿生支持向量機(jī)(Twin Support Vector Machine，TWSVM)[2-3]。TWSVM通過(guò)求解一組二次規(guī)劃(Quadratic Programming Problem，QPP)產(chǎn)生一對(duì)非平行的超平面，分別對(duì)應(yīng)于兩類相應(yīng)的樣本，使得某一類樣本盡可能距離相對(duì)應(yīng)的超平面近，同時(shí)盡可能遠(yuǎn)離另一類的超平面。理論上TWSVM每次求解一個(gè)QPP問題的規(guī)模是傳統(tǒng)SVM問題的一半，所以TWSVM求解問題的速度是SVM的四倍[4]。為了提高TWSVM的性能，國(guó)內(nèi)外眾多學(xué)者對(duì)其進(jìn)行改進(jìn)，進(jìn)而提出了不少改進(jìn)算法。例如，投影孿生支持向量機(jī)(Projection TWSVM)[5]和基于Chen-Harker-Kanzow-Smale(CHKS)函數(shù)的光滑孿生支持向量機(jī)(CHKS TWSVM)[6]。

現(xiàn)實(shí)中，多分類問題是普遍存在的，所以研究多分類具有重要意義。構(gòu)建多分類支持向量機(jī)使用最多的方法是間接構(gòu)建法，即通過(guò)不同的策略將多個(gè)二分類器組合成一個(gè)多分類器，該方法計(jì)算復(fù)雜度低，實(shí)現(xiàn)簡(jiǎn)單，且容易理解。目前，已經(jīng)有許多學(xué)者在多分類孿生支持向量機(jī)的研究上做出了一定貢獻(xiàn)。Xie等[7]結(jié)合一對(duì)多(one-versus-all，OVA)策略和TWSVM構(gòu)造出基于一對(duì)多策略的多分類孿生支持向量機(jī)(OVA-MTWSVM)，該算法將TWSVM運(yùn)算速度快與OVA策略原理簡(jiǎn)單且易實(shí)現(xiàn)等優(yōu)點(diǎn)相結(jié)合，從而提高了解決多分類問題的效率和速度。Shao等[8]將Knerr提出的一對(duì)一(one-versus-all，OVO)策略和TWSVM相結(jié)合得到基于一對(duì)一策略的多分類孿生支持向量機(jī)(OVO-MTWSVM)，此算法因?yàn)槭褂肙VO策略，每個(gè)子分類器只需兩類樣本參與訓(xùn)練，訓(xùn)練的速度較快，而且能很好地解決樣本不平衡問題。Gu等[9-10]結(jié)合TWSVM與圖論中的有向無(wú)環(huán)圖(directed acyclic graph，DAG)得到基于有向無(wú)環(huán)圖的多分類孿生支持向量機(jī)(DAG-MTWSVM)，該算法與其他策略相比在分類時(shí)需要的分類器數(shù)量較少，分類速度較快。Yang等[11]將多對(duì)一策略(all-versus-one,AVO)與TWSVM相結(jié)合得到基于多對(duì)一策略的多分類孿生支持向量機(jī)(AVO-MTWSVM)，又被稱為多生支持向量機(jī)(MBSVM)，此算法和OVA-MTWSVM一樣具有較低的算法復(fù)雜度，因此受到眾多學(xué)者的關(guān)注。除了這四種常用方法外，Xu等[12]將TWSVM與1-versus-1-versus-rest(1-1-R)策略相結(jié)合得到一種全新的多分類孿生支持向量機(jī)(Twin KSVC)[12]，此算法的每個(gè)子分類器既考慮到了待分類的兩類樣本，同時(shí)也將其他類樣本考慮在內(nèi)，具有更好的算法魯棒性。

本文在多對(duì)一的多分類組合策略的基礎(chǔ)上提出一種改進(jìn)的多分類算法。所謂多對(duì)一策略就是將訓(xùn)練樣本中某一類樣本設(shè)為負(fù)類樣本并與設(shè)為正類樣本的其余所有類樣本組合構(gòu)建多個(gè)二分類器。根據(jù)測(cè)試樣本與超平面的距離，若測(cè)試樣本距離某一類的超平面最遠(yuǎn)則判定測(cè)試樣本屬于該類。另外，此算法設(shè)定每個(gè)二分類器的參數(shù)都是相同的，以此來(lái)解決多分類問題。本文在此基礎(chǔ)上通過(guò)添加正則項(xiàng)[13]來(lái)貫徹SVM的最小結(jié)構(gòu)風(fēng)險(xiǎn)原則[14]，并結(jié)合最小二乘思想得到一種改進(jìn)的最小二乘多分類孿生支持向量機(jī)(Improved multiclass least squares TWSVM，IM AVO MLSTSVM)。

1 相關(guān)理論

1.1 孿生支持向量機(jī)

假設(shè)X1∈Rl1×n和X2∈Rl2×n分別表示n維空間Rn中的兩類樣本，其中X1為+1類樣本，樣本數(shù)為l1，X2為-1類樣本，樣本數(shù)為l2。TWSVM算法主要是在Rn中尋找到以下兩個(gè)非平行的超平面：

XTW1+b1=0和XTW2+b2=0

(1)

式中：W1和W2是兩個(gè)超平面的法向量；b1和b2是兩個(gè)超平面的偏移量。它們是通過(guò)求解下面兩個(gè)QPP得出：

(2)

s.t. -(X2W1+e2b1)+ξ≥e2,ξ≥0

(3)

s.t. (X1W2+e1b2)+η≥e2,η≥0

式中：c1和c2是兩個(gè)懲罰因子；e1和e2是兩個(gè)全為1的向量；ξ∈Rl1和η∈Rl2是兩個(gè)松弛變量。最后決策函數(shù)式(4)通過(guò)計(jì)算測(cè)試樣本與超平面之間的距離，比較測(cè)試樣本與各個(gè)超平面的距離，與測(cè)試樣本最近的超平面所對(duì)應(yīng)的那一類為該測(cè)試樣本所屬類別。

(4)

如圖1所示，對(duì)于兩個(gè)非平行的超平面，Class1所對(duì)應(yīng)的超平面盡可能與Class1所對(duì)應(yīng)的樣本點(diǎn)近而距離Class2所對(duì)應(yīng)的樣本盡可能遠(yuǎn)，同樣Class2所對(duì)應(yīng)的超平面距離Class2對(duì)應(yīng)的樣本盡可能近，而距離Class1的樣本盡可能遠(yuǎn)。

圖1 孿生支持向量機(jī)

1.2 基于多對(duì)一策略的最小二乘多分類孿生支持向量機(jī)

TWSVM最初是為了解決二分類問題而提出來(lái)的，但現(xiàn)實(shí)中大多數(shù)問題為多分類問題，這就需要結(jié)合TWSVM和多分類的組合策略構(gòu)成多分類孿生支持向量機(jī)來(lái)解決多分類問題。

多對(duì)一組合策略是構(gòu)建多分類器方法最常用方法之一，其原理就是將K類樣本中取某一類作為負(fù)類，其余K-1類作為正類，構(gòu)建一個(gè)分類器并得到該K-1類樣本的超平面，以此類推最后得到K個(gè)超平面。AVO策略在每次訓(xùn)練時(shí)需要所有的訓(xùn)練樣本參與訓(xùn)練，這就需要訓(xùn)練出K個(gè)分類器。本文所用算法是基于多對(duì)一策略的最小二乘多分類孿生支持向量機(jī)(AVO MLSTSVM)[15]，該算法在基于AVO策略的MTWSVM的基礎(chǔ)上引入最小二乘思想[16]，用等式約束代替原先QPP問題中的不等式約束，極大地降低了算法求解的復(fù)雜性。

基于多對(duì)一策略的最小二乘多分類孿生支持向量機(jī)(AVO MLSTSVM)算法需要求解以下QPP問題：

(5)

s.t. (XiWi+ei1bi)+ξi=ei1

式中：ci為懲罰因子；ei1∈Rli，ei2∈Rl-li是兩個(gè)全為1的向量；ξi是松弛變量。式(5)的目標(biāo)函數(shù)的第一項(xiàng)使得超平面盡可能遠(yuǎn)離第i類樣本；第二項(xiàng)為松弛變量，用來(lái)最小化來(lái)自其他樣本點(diǎn)的分類誤差。這樣使得超平面盡可能遠(yuǎn)離相應(yīng)的樣本點(diǎn)，而盡可能接近其他樣本點(diǎn)。求解式(5)一般使用拉格朗日乘子法[17]，則其對(duì)應(yīng)的拉格朗日函數(shù)為：

αi((XiWi+ei1bi)+ξi-ei1)

(6)

根據(jù)Karush-Kuhn-Tucker(KKT)條件，分別對(duì)Wi、bi、ξi、αi求其梯度并令其為0：

(7)

(8)

(9)

(10)

求解式(7)-式(10)得到分類超平面的法向量Wi和偏移量bi為：

(11)

(12)

最后通過(guò)計(jì)算測(cè)試樣本與各個(gè)超平面的距離，比較各個(gè)距離的大小，與測(cè)試樣本距離最遠(yuǎn)的超平面所對(duì)應(yīng)的樣本類別為該測(cè)試樣本所屬類。

圖2為AVO MLSTSVM在三類樣本中的分類示意圖，可以看出Plane 1為Class1類樣本所對(duì)應(yīng)的超平面，Plane 1盡可能遠(yuǎn)離Class1樣本，并離Class2和Class3樣本近，同理Plane 2和Plane 3與Plane 1一樣都是距離所對(duì)應(yīng)的樣本盡可能遠(yuǎn)，而距離其他樣本盡可能近。

圖2 線性AVO MLSTSVM示意圖

2 基于多對(duì)一策略的改進(jìn)的最小二乘多分類孿生支持向量機(jī)

結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則是通過(guò)最大化各類樣本之間的邊界來(lái)實(shí)現(xiàn)的。傳統(tǒng)多對(duì)一策略的最小二乘多分類孿生支持向量機(jī)只考慮了經(jīng)驗(yàn)風(fēng)險(xiǎn)的最小化，卻沒有將結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則考慮在內(nèi)。本文在多對(duì)一策略的最小二乘多分類孿生支持向量機(jī)的基礎(chǔ)上引入正則項(xiàng)式[13]來(lái)實(shí)現(xiàn)最小結(jié)構(gòu)風(fēng)險(xiǎn)原則[14]。

本文對(duì)基于一對(duì)多策略的改進(jìn)的最小二乘多分類孿生支持向量機(jī)從線性情況與非線性情況分析。在待分類的數(shù)據(jù)中能夠直接找到超平面將待分類的數(shù)據(jù)分開，稱為該情況為線性可分的，即為線性情況。在待分類的數(shù)據(jù)中無(wú)法直接找到相應(yīng)的超平面將待分類的數(shù)據(jù)分開，稱該情況為非線性情況。這種情況往往通過(guò)核函數(shù)將待分類的數(shù)據(jù)映射到高維空間，從而可以解決在低維空間無(wú)法直接分類的問題。

2.1 線性情況

假設(shè)2維空間R有L個(gè)樣本，這些訓(xùn)練樣本可以被分為K類。其中令Xi表示第i類樣本，Yi表示除第i類樣本之外其余的樣本。那么在線性情況下算法所需要解決的最優(yōu)化問題可以表示為：

(13)

s.t. (XiWi+ei1bi)+ξi=ei1

式中：Wi是第i類樣本的超平面的法向量，bi為偏移量，ci為懲罰因子，ξi為松弛變量，ei1、ei2是兩個(gè)全為1的向量，θi為添入的正則項(xiàng)式的權(quán)重。

用拉格朗日乘子法求解式(13)得：

(14)

最后得到超平面的參數(shù)為：

(15)

(16)

算法1線性情況下改進(jìn)的基于多對(duì)一策略的最小二乘多分類孿生支持向量機(jī)(IM AVO MLSTSVM)的步驟如下：

Step1初始化：訓(xùn)練數(shù)據(jù)的類數(shù)K，Xi為第i類樣本，Yi為其他類樣本，i為第i類樣本的類標(biāo)。

Step2fori=1:K

(1) 定義兩個(gè)矩陣Ai和Bi，其中Hi=[Xiei1]，Gi=[Yiei2]。

(2) 選擇合適的懲罰因子ci和正則化參數(shù)θi。

(3) 根據(jù)式(15)確定第i類樣本所對(duì)應(yīng)的分類超平面的參數(shù)，從而確定第i類樣本所對(duì)應(yīng)的超平面。

end

Step3根據(jù)式(16)計(jì)算測(cè)試樣本與超平面的距離，測(cè)試樣本與哪個(gè)超平面最遠(yuǎn)則判斷該樣本屬于哪一類。

2.2 非線性情況

現(xiàn)實(shí)情況下大多數(shù)需要解決的問題都是非線性的，所使用的算法必須在能解決線性問題的同時(shí)也能解決非線性問題。對(duì)于非線性的樣本需要使用核函數(shù)對(duì)樣本進(jìn)行處理，首先把樣本映射到高維空間中去，然后再利用分類器進(jìn)行分類。則樣本對(duì)應(yīng)的超平面可以表示為：

Ker(Y,DT)μi+γi=0i=1,2,…,K

(17)

式中：D=[XiYi]T，Ker表示選用的適合的核函數(shù)。則改進(jìn)的基于多對(duì)一策略的最小二乘多分類孿生支持向量機(jī)(IM AVO MLSTSVM)可以表示為：

(18)

s.t. (Ker(Xi,DT)μi+ei1γi)+ξi=ei1

用拉格朗日乘子法求解式(18)：

(19)

求解得到超平面：

(20)

(21)

與線性情況下一樣，通過(guò)計(jì)算測(cè)試樣本與各個(gè)超平面的距離，比較各個(gè)距離的大小，測(cè)試樣本與哪個(gè)超平面的距離大，則判定該樣本屬于該超平面所對(duì)應(yīng)的那一類。

非線性情況下改進(jìn)的基于多對(duì)一策略的最小二乘多分類孿生支持向量機(jī)(IM AVO MLSTSVM)步驟如下：

Step1初始化：訓(xùn)練數(shù)據(jù)的類數(shù)K，Xi為第i類樣本，Yi為其他類樣本，i為第i類樣本的類標(biāo)。

Step2fori=1:K

(1) 定義兩個(gè)矩陣Hi和Gi，其中Hi=[Ker(Xi,DT)ei1]，Gi=[Ker(Yi,DT)ei2]。

(2) 選擇合適的懲罰因子ci和正則化參數(shù)θi。

(3) 根據(jù)式(20)確定第i類樣本所對(duì)應(yīng)的分類超平面的參數(shù)，從而確定第i類樣本所對(duì)應(yīng)的超平面。

end

Step3根據(jù)式(21)計(jì)算測(cè)試樣本與超平面的距離，測(cè)試樣本與哪個(gè)超平面最遠(yuǎn)則判斷該樣本屬于哪一類。

2.3 復(fù)雜度分析

3 實(shí)驗(yàn)與結(jié)果分析

本節(jié)通過(guò)實(shí)驗(yàn)對(duì)本文所提出的算法進(jìn)行驗(yàn)證。所選用的數(shù)據(jù)均來(lái)自UCI數(shù)據(jù)庫(kù)，所有實(shí)驗(yàn)均用十次交叉驗(yàn)證。運(yùn)行環(huán)境為4 GB內(nèi)存，CPU為Intel CORE i3- 4170,3.7 GHz的主頻，Windows 10操作系統(tǒng)。所有實(shí)驗(yàn)室均在MATLAB R2016a環(huán)境上實(shí)現(xiàn)。實(shí)驗(yàn)所用的數(shù)據(jù)集具體信息如表1所示。

表1 實(shí)驗(yàn)所用數(shù)據(jù)集信息

在實(shí)驗(yàn)設(shè)置中，本文選取一對(duì)多策略多分類支持向量機(jī)(OVA SVM)，多對(duì)一策略最小二乘多分類孿生支持向量機(jī)(AVO MLSTSVM)和一對(duì)多策略最小二乘多分類孿生支持向量機(jī)(OVA MLSTWSVM)作為對(duì)比實(shí)驗(yàn)。并且分別對(duì)不同算法選用線性核時(shí)算法的表現(xiàn)和選用高斯核時(shí)算法的表現(xiàn)作出分析，實(shí)驗(yàn)結(jié)果均為10次交叉驗(yàn)證所得到的平均精度。實(shí)驗(yàn)中對(duì)比算法都只有一個(gè)懲罰參數(shù)c和一個(gè)核函數(shù)參數(shù)σ，本文提出的算法包含三個(gè)參數(shù)，懲罰參數(shù)c、核函數(shù)參數(shù)σ和一個(gè)正則化參數(shù)θ,懲罰參數(shù)和正則化參數(shù)均使用網(wǎng)格搜索選取參數(shù)，參數(shù)均初始化為之間，同時(shí)為了減少運(yùn)算的復(fù)雜度，默認(rèn)高斯核的核參數(shù)σ為2。各種算法在不同數(shù)據(jù)集上的性能如表2和表3所示。

表2 線性情況下各類算法的分類性能對(duì)比(%)

表3 非線性情況下各類算法的分類性能對(duì)比(%)

由表2可以看出新提出的算法在使用線性核情況下，在數(shù)據(jù)集glass、wine、thyroid、cmc和ecoli上面表現(xiàn)的結(jié)果較其他三個(gè)算法是性能更好。由表3可以得出，IM AVO MLSTSVM算法在非線性情況下使用rbf核函數(shù)并且核參數(shù)默認(rèn)為2的情況下在數(shù)據(jù)glass、wine、thyroid、cmc和ecoli上表現(xiàn)較其他三種算法分類性能更好。由此可看出在大多數(shù)情況下提出的算法在較其他三種算法在分類性能上是有改進(jìn)的。

從表4的分類時(shí)間上可以看出本文所提出的算法在線性核情況下時(shí)與算法AVO MLSTSVM和OVA MLSTSVM相差較小，同時(shí)比OVA SVM的分類時(shí)間更好。由表5可以看出在非線性核情況下本文所提出的算法與其他三個(gè)算法在數(shù)據(jù)集glass、wine、thyroid和ecoli上分類時(shí)間相差不大，在數(shù)據(jù)集cmc上與算法AVO MLSTSVM和算法OVA MLSTSVM相差不大，同OVA AVM相比較低。綜上所述本文的算法在分類時(shí)間上在大多數(shù)情況下是有改進(jìn)的。

表4 線性情況下各類算法的分類時(shí)間對(duì)比 單位：s

表5 非線性情況下各類算法的分類時(shí)間對(duì)比 單位：s

本文對(duì)比實(shí)驗(yàn)采用十次交叉驗(yàn)證，最后結(jié)果為十次的平均值，圖3-圖8為在線性核情況下數(shù)據(jù)集wine、cmc和ecoli以及在非線性使用RBF核函數(shù)的情況下在數(shù)據(jù)集glass、thyroid和wine上各算法在十次交叉驗(yàn)證中的對(duì)比情況。由圖3可以看出，本文的算法在線性核情況下在數(shù)據(jù)集wine上的有著更好的表現(xiàn)，而且總的來(lái)說(shuō)對(duì)比其他三種算法都有著更好的表現(xiàn)。由圖6可以看出非線性情況下在數(shù)據(jù)集glass上本文所提出的算法更優(yōu)于其他三種算法。另外，由圖4、圖5、圖7和圖8也可以看出與其他三種算法相比本文算法在分類性能上有較好的改進(jìn)。

圖3 線性情況下各算法在wine上的表現(xiàn)

圖4 線性情況下各算法在cmc上的表現(xiàn)

圖5 線性情況下各算法在ecoli上的表現(xiàn)

圖6 非線性情況下各算法在glass上的表現(xiàn)

圖7 非線性情況下各算法在thyroid上的表現(xiàn)

圖8 非線性核情況下各算法在wine上的表現(xiàn)

4 結(jié) 語(yǔ)

本文算法是在多對(duì)一策略的最小二乘多分類孿生支持向量機(jī)的基礎(chǔ)上引入正則項(xiàng)式來(lái)實(shí)現(xiàn)結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則，從而提高分類器的性能。和AVO MLSTSVM類似，本文算法也是將訓(xùn)練數(shù)據(jù)按照多對(duì)一的策略劃分。然而AVO MLSTSVM只考慮到算法的經(jīng)驗(yàn)風(fēng)險(xiǎn)，卻沒有考慮算法的結(jié)構(gòu)風(fēng)險(xiǎn)。本文提出的算法考慮到算法的經(jīng)驗(yàn)風(fēng)險(xiǎn)，而且通過(guò)引入正則項(xiàng)式來(lái)貫徹結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則，能夠極大地提高分類算法的性能。通過(guò)在UCI數(shù)據(jù)集上的實(shí)驗(yàn)驗(yàn)證，引入的正則化對(duì)提高分類器性能是有效的。另外，在面對(duì)數(shù)據(jù)不平衡時(shí)，各類樣本數(shù)相差較大時(shí)如何提升算法性能，解決數(shù)據(jù)不平衡問題還需進(jìn)一步研究。