李凱，李潔

(河北大學(xué) 網(wǎng)絡(luò)空間安全與計(jì)算機(jī)學(xué)院，河北 保定 071002)

支持向量機(jī)(support vector machine，SVM)是由Vapnik等[1]提出的一種機(jī)器學(xué)習(xí)方法，一種基于統(tǒng)計(jì)學(xué)習(xí)理論的結(jié)構(gòu)風(fēng)險(xiǎn)最小化準(zhǔn)則和間隔最大化的思想，通過(guò)求解一個(gè)二次規(guī)劃問(wèn)題，以此獲得一個(gè)最優(yōu)分類(lèi)超平面.為了解決SVM中計(jì)算復(fù)雜度過(guò)高的問(wèn)題，Jayadeva等[2]提出了孿生支持向量機(jī)(Twin SVM，TWSVM)，通過(guò)求解2個(gè)較小的二次規(guī)劃問(wèn)題，確定2個(gè)非平行超平面，使得每個(gè)超平面都更接近一類(lèi)而遠(yuǎn)離另一類(lèi)，該方法進(jìn)一步提高了計(jì)算速度.此后，人們?cè)赥WSVM的基礎(chǔ)上提出了多種算法及其應(yīng)用[3-9].

為了解決SVM和TWSVM中采用鉸鏈損失函數(shù)的缺陷，研究人員采用pinball損失，提出了基于pinball損失的支持向量機(jī)和孿生支持向量機(jī)[10-12]，較好地解決了算法對(duì)噪聲敏感的問(wèn)題.另外，不論是SVM還是TWSVM，將所有樣本視為同等重要，實(shí)際上，不同樣本對(duì)分類(lèi)超平面具有不同程度的影響，為此，人們將模糊理論引入到SVM和TWSVM中，提出了模糊支持向量機(jī)[13](Fuzzy SVM，F(xiàn)SVM)、模糊孿生支持向量機(jī)[14-15](Fuzzy TWSVM，F(xiàn)TWSVM)及其一些改進(jìn)算法[16-17].通過(guò)對(duì)樣本賦予不同權(quán)重的方法，提高了算法的噪聲不敏感性.

可以看到，上述算法均適用于二類(lèi)問(wèn)題，然而，在實(shí)際應(yīng)用中，多分類(lèi)問(wèn)題更加普遍.目前，用于多分類(lèi)的孿生支持向量機(jī)主要分為如下幾種[18-20]：

1)一對(duì)多孿生支持向量機(jī).該方法在k個(gè)類(lèi)中任意挑選一類(lèi)作為正類(lèi)，其余k-1類(lèi)作為負(fù)類(lèi)，并構(gòu)造k個(gè)二分類(lèi)器進(jìn)行分類(lèi).

2)一對(duì)一孿生支持向量機(jī).將一個(gè)多分類(lèi)問(wèn)題轉(zhuǎn)化為一系列的2類(lèi)問(wèn)題進(jìn)行求解.該算法在訓(xùn)練階段對(duì)任意2類(lèi)樣本構(gòu)造一個(gè)TWSVM，共構(gòu)造k(k-1)/2個(gè)分類(lèi)器進(jìn)行分類(lèi)，使用投票法對(duì)測(cè)試樣本進(jìn)行分類(lèi).

3)有向無(wú)環(huán)圖支持向量機(jī).在訓(xùn)練階段類(lèi)似于一對(duì)一孿生支持向量機(jī)，而在測(cè)試階段，需要建立一個(gè)有向無(wú)環(huán)圖，其中k個(gè)葉子結(jié)點(diǎn)對(duì)應(yīng)k個(gè)類(lèi)，每個(gè)內(nèi)部節(jié)點(diǎn)對(duì)應(yīng)一個(gè)二分類(lèi)器，共k(k-1)/2個(gè)，待分類(lèi)樣本從根節(jié)點(diǎn)開(kāi)始根據(jù)每個(gè)分類(lèi)器的分類(lèi)結(jié)果進(jìn)行決策，直至葉結(jié)點(diǎn)得到對(duì)應(yīng)的類(lèi)別.

4)一對(duì)一對(duì)多孿生支持向量機(jī)[21].在一對(duì)一的思想上，將其余的k-2個(gè)類(lèi)作為第3類(lèi)與前2類(lèi)分隔開(kāi)，其最終分類(lèi)結(jié)果為三元輸出{-1，0，+1}.

5)其他解決方法[22].該方法在訓(xùn)練時(shí)使k類(lèi)中的任意一類(lèi)距離超平面最遠(yuǎn)，而其他k-1類(lèi)距離超平面最近，對(duì)于待分類(lèi)樣本，需要決策該樣本離超平面的距離來(lái)確定，即離哪個(gè)超平面最遠(yuǎn)則將此樣本歸為該類(lèi).

為了進(jìn)一步提高孿生支持向量機(jī)的性能，將pinball損失函數(shù)與樣本權(quán)重引入到多分類(lèi)算法中，提出了一種基于pinball損失的一對(duì)一加權(quán)孿生支持向量機(jī)(Pin-OVO-STWSVM).用pinball損失函數(shù)代替一對(duì)一孿生支持向量機(jī)中的鉸鏈損失函數(shù)，并通過(guò)引入權(quán)重方法，使得較重要的樣本賦予較大的權(quán)值，而對(duì)噪聲及異常值賦予較小的權(quán)重，以此區(qū)分不同樣本的重要程度，該算法對(duì)噪聲不敏感且訓(xùn)練時(shí)間短.實(shí)驗(yàn)中使用不同方法對(duì)樣本賦予權(quán)值，并在具有不同噪聲的人工數(shù)據(jù)集和UCI標(biāo)準(zhǔn)數(shù)據(jù)集[23]上進(jìn)行了實(shí)驗(yàn)，結(jié)果表明，與一對(duì)一孿生支持向量機(jī)OVO-TWSVM、一對(duì)多孿生支持向量機(jī)OVA-TWSVM以及基于pinball損失的一對(duì)一孿生支持向量機(jī)Pin-OVO-TWSVM等方法對(duì)比，提出的Pin-OVO-STWSVM算法具有較好的性能.

1 相關(guān)工作

1.1 OVO-TWSVM

“一對(duì)一”(one-verus-one，OVO)是由Knerr將二類(lèi)推廣到多類(lèi)問(wèn)題提出的一種方法.對(duì)于k分類(lèi)問(wèn)題，需要2個(gè)階段完成分類(lèi)任務(wù).在分解階段，需要在k個(gè)類(lèi)中任意選擇2類(lèi)樣本，并使用SVM分類(lèi)方法對(duì)其進(jìn)行分類(lèi)，通過(guò)此種方法需要構(gòu)建k(k-1)/2個(gè)分類(lèi)器，而每個(gè)分類(lèi)器只需對(duì)2類(lèi)樣本進(jìn)行分類(lèi)；在重構(gòu)階段，根據(jù)每個(gè)分類(lèi)器的分類(lèi)結(jié)果投票給不同的類(lèi)，并按照每一類(lèi)所得票數(shù)確定待分類(lèi)樣本的類(lèi)別.

為了克服SVM存在的缺陷，研究人員將TWSVM引入到OVO中，提出了OVO-TWSVM[20]，該方法不僅提高了分類(lèi)準(zhǔn)確率，同時(shí)使得訓(xùn)練時(shí)間減少到之前的1/4.假設(shè)A矩陣由m個(gè)樣本點(diǎn)構(gòu)成，其中A∈Rm×n.對(duì)于k分類(lèi)問(wèn)題，任意選取第i類(lèi)和第j類(lèi)，其優(yōu)化問(wèn)題如下：

1.2 損失函數(shù)

對(duì)于傳統(tǒng)的SVM以及TWSVM，在建立相應(yīng)模型時(shí)，主要使用了鉸鏈損失函數(shù)，即

Lhinge(x,y,f(x))=max(0,1-yf(x))，

其中y和f(x)分別為理想值和預(yù)測(cè)值.由于鉸鏈損失函數(shù)使用了最短距離，因此，易導(dǎo)致噪聲敏感性和重采樣的不穩(wěn)定性.為此，人們對(duì)不同損失函數(shù)的SVM及TWSVM進(jìn)行研究，其中pinball損失函數(shù)研究較為廣泛.pinball損失函數(shù)定義如下：

其中τ∈[0，1].可以看到，pinball損失函數(shù)不僅對(duì)分類(lèi)錯(cuò)誤的樣本進(jìn)行懲罰，而且對(duì)分類(lèi)正確的樣本給出一個(gè)額外懲罰；另外，該函數(shù)使用了分位數(shù)距離，因此，對(duì)噪聲不敏感，數(shù)據(jù)重采樣更穩(wěn)定，且不會(huì)增加計(jì)算成本.當(dāng)pinball損失的參數(shù)趨于零時(shí)，損失函數(shù)成為鉸鏈損失.

2 基于pinball損失的一對(duì)一加權(quán)孿生支持向量機(jī)

將pinball損失函數(shù)和權(quán)重引入到一對(duì)一策略的多分類(lèi)孿生支持向量機(jī)中,用pinball損失代替?zhèn)鹘y(tǒng)的鉸鏈損失，并針對(duì)不同樣本的重要程度，為每一個(gè)樣本賦予一個(gè)權(quán)重，從而得到基于pinball損失的一對(duì)一加權(quán)孿生支持向量機(jī)算法Pin-OVO-STWSVM.下面將分為2種情況進(jìn)行介紹.

2.1 線性情況

給定一個(gè)k類(lèi)訓(xùn)練數(shù)據(jù)集T={(xi，yi，Si)|i=1，2，…，m}，共包含m個(gè)樣本，其中，xi∈Rn為訓(xùn)練樣本數(shù)據(jù)，yi∈{1，2，…，k}為樣本標(biāo)簽，Ai和Aj分別表示第i類(lèi)和第j類(lèi)的樣本.線性Pin-OVO-STWSVM算法的目標(biāo)是為k類(lèi)中的任意2類(lèi)樣本找到一對(duì)非平行超平面.假設(shè)將第i類(lèi)和第j類(lèi)分開(kāi)的超平面為

xTwi+bi=0 和xTwj+bj=0，

(1)

則獲得2個(gè)超平面的第i類(lèi)和第j類(lèi)的優(yōu)化問(wèn)題為

(2)

(3)

其中c1>0和c2>0是平衡因子，ξi和ξj是松弛變量，ei和ej為全由1組成的列向量.

對(duì)于式(2)與(3)，與OVO-TWSVM的不同主要體現(xiàn)在目標(biāo)函數(shù)的第2項(xiàng)和約束條件中，其中目標(biāo)函數(shù)的第1項(xiàng)是第i類(lèi)點(diǎn)到該類(lèi)對(duì)應(yīng)超平面距離的平方和；第2項(xiàng)是求誤差變量的和，而Si和Sj分別是由第i類(lèi)和第j類(lèi)中樣本的權(quán)重值所組成的向量，樣本點(diǎn)的權(quán)重值越小，則該樣本點(diǎn)的重要程度越低，反之，權(quán)重值越大則較為重要，因此，為每個(gè)誤差變量乘上相應(yīng)的權(quán)重值可以使誤差對(duì)于分類(lèi)問(wèn)題的影響更準(zhǔn)確；而約束條件使用了pinball損失，τ1，τ2∈[0，1]為參數(shù).

下面以式(2)為例，使用拉格朗日方法對(duì)其求解，為此，構(gòu)造拉格朗日函數(shù)

(4)

其中α≥0，β≥0是由拉格朗日乘子所組成的向量.

根據(jù)KKT(Karush-Kuhn-Tucker)條件可得

(5)

(6)

(7)

-(Ajwi+ejbi)≥ej-ξi,ξi≥0，

(8)

αT(-(Ajwi+ejbi)+ξi-ej)=0，

(9)

(10)

α≥0,β≥0.

(11)

進(jìn)一步化簡(jiǎn)得到

(12)

令H=[Aiei]，G=[Ajej]，vi=[wibi]T，則式(12)變?yōu)?/p>

νi=-(HTH)-1GT(α-β).

(13)

為了防止HTH可能不適用的情況，引入一個(gè)正則化項(xiàng)δI，則式(13)變?yōu)?/p>

νi=-(HTH+δI)-1GT(α-β)，

(14)

其中δ是一個(gè)很小的正數(shù)，I是一個(gè)單位矩陣.

將式(14)帶入到式(4)中得到

(15)

從而獲得原問(wèn)題的對(duì)偶問(wèn)題如下：

(16)

其中γ=(α-β).

按照同樣的方法，可以得到式(3)的對(duì)偶問(wèn)題為

(17)

其中ρ=(σ-ε)，σ和ε為拉格朗日乘子，νj=[wjbj]T.

通過(guò)求解式(16)與(17)，從而獲得 [wibi]T與[wjbj]T，即

(18)

當(dāng)對(duì)新樣本x分類(lèi)時(shí)，需遍歷k(k-1)/2個(gè)分類(lèi)器，并對(duì)每個(gè)分類(lèi)器的分類(lèi)結(jié)果投票，則票數(shù)最高的類(lèi)即為樣本x所屬類(lèi)別.式(19)給出了使用第i類(lèi)和第j類(lèi)樣本訓(xùn)練得到的分類(lèi)器的決策函數(shù)，其中r為類(lèi)標(biāo)簽，r=i或j

(19)

2.2 非線性情況

通過(guò)引入核函數(shù)，將線性情況推廣到非線性情況中.利用核矩陣將輸入樣本映射到高維特征空間，使其在高維空間中實(shí)現(xiàn)線性可分，因此，決策面方程為

K(xT,CT)ui+bi=0和K(xT，CT)uj+bj=0,

(20)

其中CT=[AB]T，K(x1,x2)=φ(x1)φ(x2)，且φ是原空間到特征空間的映射.則非線性情況中第i類(lèi)和第j類(lèi)對(duì)應(yīng)的優(yōu)化問(wèn)題

(21)

(22)

按照求解式(2)與(3)方法，得到式(21)與(22)的對(duì)偶問(wèn)題如下：

(23)

(24)

其中γ=(α-β)，ρ=(σ-ε)，α、β、σ和ε為拉格朗日乘子，zi=[uibi]T，zj=[ujbj]T，通過(guò)求解對(duì)偶問(wèn)題，進(jìn)一步得到[uibi]T和[ujbj]T，即

(25)

當(dāng)對(duì)新樣本x分類(lèi)時(shí)，與線性情況類(lèi)似，只是決策函數(shù)有所不同，式(26)給出了使用第i類(lèi)和第j類(lèi)樣本訓(xùn)練得到的分類(lèi)器的決策函數(shù)，其中r為類(lèi)標(biāo)簽，r=i或j

(26)

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

為了驗(yàn)證提出算法的性能，將OVO-TWSVM、OVA-TWSVM、 Pin-OVO-TWSVM與提出的算法Pin-OVO-STWSVM在UCI數(shù)據(jù)庫(kù)中的12個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集和4個(gè)人工生成數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn).同時(shí)，為了檢測(cè)提出算法的抗噪性，在數(shù)據(jù)集中分別添加了5%和10%的特征噪聲，并檢測(cè)其準(zhǔn)確率.實(shí)驗(yàn)中高斯核函數(shù)為K(i，j)=exp(-p‖x-y‖2)，使用了10重交叉驗(yàn)證，并將10次測(cè)試的平均值及標(biāo)準(zhǔn)差作為最終的評(píng)價(jià)結(jié)果.采用網(wǎng)格搜索方法確定最優(yōu)參數(shù)，參數(shù)c1和c2的搜索范圍為{2i|i∈[-4，10]}；高斯核參數(shù)p的搜索范圍為{2i|i∈[-4，10]}；pinball損失參數(shù)的τ1=τ2，其取值范圍為{0.05，0.1，0.5}.

3.1 樣本權(quán)重的確定方法

為了研究不同樣本賦予不同權(quán)重時(shí)對(duì)分類(lèi)結(jié)果的影響，使用3種確定權(quán)重值方法進(jìn)行了實(shí)驗(yàn)，分別為類(lèi)中心距離法、模糊C均值法和S型方法.

1)類(lèi)中心距離法.根據(jù)每類(lèi)中的樣本距離該類(lèi)中心的距離遠(yuǎn)近來(lái)定義其權(quán)重，距離類(lèi)中心點(diǎn)越近的樣本權(quán)重越大，距離越遠(yuǎn)權(quán)重越小.計(jì)算樣本權(quán)重Si的方法如下：

其中di表示樣本到該類(lèi)類(lèi)中心的距離，ri表示該類(lèi)的半徑，即距離類(lèi)中心最遠(yuǎn)的樣本到中心的距離.

2)模糊C均值法.利用模糊C均值聚類(lèi)方法，獲得每個(gè)樣本的隸屬度，并計(jì)算樣本隸屬每個(gè)簇程度的最大值，以此作為樣本的權(quán)重.具體計(jì)算方法如下：

其中vj為聚類(lèi)中心，sij為第i個(gè)樣本在第j個(gè)簇中的權(quán)重，m為模糊加權(quán)指數(shù).在聚類(lèi)時(shí)，需要使用迭代方法獲得sij和vj.

3)S型方法.根據(jù)樣本距離該類(lèi)中心的距離遠(yuǎn)近來(lái)確定權(quán)重，對(duì)類(lèi)中心距離法中使用的線性函數(shù)用非線性函數(shù)替換，即

其中a和b為確定的參數(shù)并滿足b=(a+c)/2，當(dāng)di=b時(shí)，Si=0.5.

3.2 人工數(shù)據(jù)集

首先，隨機(jī)生成了4個(gè)服從高斯分布的人工數(shù)據(jù)集，分別稱為data_1、data_2、data_3和data_4，樣本數(shù)分別為300、400、300和400，類(lèi)別分別為3類(lèi)、3類(lèi)、4類(lèi)和5類(lèi)，其中data_1中的3類(lèi)數(shù)據(jù)分別由兩簇、三簇和三簇構(gòu)成，data_2和data_4中每類(lèi)均為一簇，data_3中的3類(lèi)數(shù)據(jù)均為兩簇，并且data_1、data_2和data_3中每類(lèi)樣本數(shù)量均相同，data_4中每類(lèi)含有不同數(shù)量樣本，如圖1所示.實(shí)驗(yàn)中使用OVO-TWSVM，Pin-OVO-TWSVM和Pin-OVO-STWSVM 3種算法進(jìn)行分類(lèi)，實(shí)驗(yàn)結(jié)果如圖2a所示，其中Pin-OVO-STWSVM算法采用模糊C均值法確定權(quán)重.

為了檢測(cè)算法Pin-OVO-STWSVM的抗噪性，對(duì)每個(gè)數(shù)據(jù)集加入5%和10%的噪聲，獲得的數(shù)據(jù)集分別為data_1_n5、data_2_n5、data_3_n5、data_4_n5和data_1_n10、data_2_n10、data_3_n10、data_4_n10.同時(shí)與OVO-TWSVM和Pin-OVO-TWSVM算法進(jìn)行了對(duì)比，實(shí)驗(yàn)結(jié)果如圖2所示.

由圖2a可以看出，提出的算法Pin-OVO-STWSVM在無(wú)噪聲的人工生成數(shù)據(jù)集上具有較好的性能，其分類(lèi)準(zhǔn)確率均優(yōu)于OVO-TWSVM和Pin-OVO-TWSVM 2種方法，而在圖2b和圖2c中，在加入不同比例的噪聲后，其性能優(yōu)于另2種分類(lèi)算法.同時(shí)，使用3種不同確定權(quán)重的方法對(duì)提出的算法進(jìn)行了測(cè)試，實(shí)驗(yàn)結(jié)果如圖3所示.由圖3可知，在3種確定權(quán)重的方法中，模糊C均值法較其他2種方法較為穩(wěn)定，準(zhǔn)確率也較高.

圖1 人工數(shù)據(jù)集Fig.1 Artificial data sets

a.無(wú)噪聲；b.5%噪聲；c.10%噪聲.圖2 3種算法在含有噪聲的人工數(shù)據(jù)集的準(zhǔn)確率Fig.2 Accuracy of three algorithms for artificial data sets with noises

a.無(wú)噪聲；b.5%噪聲；c.10%噪聲.圖3 不同權(quán)重方法對(duì)算法準(zhǔn)確率的影響Fig.3 Influence of different weighting methods on accuracy of algorithm

3.3 UCI數(shù)據(jù)集

為了進(jìn)一步評(píng)價(jià)提出算法的性能，選用UCI數(shù)據(jù)庫(kù)中的12個(gè)數(shù)據(jù)集，分別為Iris、Wine、Glass、Balance、Seeds、Vowel、Ecoli、Hayes-roth、Vehicle、Thyroid、CMC和Car，使用OVO-TWSVM、OVA-TWSVM、Pin-OVO-TWSVM和Pin-OVO-STWSVM 4種算法對(duì)數(shù)據(jù)集進(jìn)行分類(lèi)，并使用3種確定權(quán)重的方法進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表1所示.

表1 不同算法在標(biāo)準(zhǔn)數(shù)據(jù)集上的準(zhǔn)確率和標(biāo)準(zhǔn)差

可以看出，提出的算法Pin-OVO-STWSVM在11個(gè)數(shù)據(jù)集上準(zhǔn)確率優(yōu)于OVO-TWSVM、OVA-TWSVM和Pin-OVO-TWSVM算法，對(duì)于Car數(shù)據(jù)集，測(cè)試結(jié)果也高于OVO-TWSVM算法.另外，由3種獲取樣本權(quán)值方法的實(shí)驗(yàn)結(jié)果可知，對(duì)于不同的數(shù)據(jù)集，使用不同確定樣本權(quán)值的方法其效果是不同的，但這些方法較好地提高了分類(lèi)準(zhǔn)確率，且在12個(gè)數(shù)據(jù)集中，使用模糊C均值法確定權(quán)重，大多數(shù)數(shù)據(jù)集上均獲得了較高的分類(lèi)準(zhǔn)確率.

同時(shí)，針對(duì)UCI中的數(shù)據(jù)集分別加入5%和10%的特征噪聲，并與OVO-TWSVM、Pin-OVO-TWSVM和提出的算法Pin-OVO-STWSVM進(jìn)行比較，實(shí)驗(yàn)結(jié)果如表2所示，其中樣本的權(quán)重采用模糊C均值法確定，噪聲采用均值為0且方差為1的高斯分布.可以看到，在12個(gè)數(shù)據(jù)集中，僅在Balance數(shù)據(jù)集添加5%的噪聲和為T(mén)hyroid數(shù)據(jù)集添加10%噪聲的情況下，準(zhǔn)確率與OVO-TWSVM算法相當(dāng)，而在其他數(shù)據(jù)集的分類(lèi)結(jié)果均高于OVO-TWSVM算法.

表2 不同算法在加入噪聲的標(biāo)準(zhǔn)數(shù)據(jù)集上的準(zhǔn)確率和標(biāo)準(zhǔn)差

4 結(jié)論

通過(guò)對(duì)多分類(lèi)中一對(duì)一策略的孿生支持向量機(jī)算法的研究，將pinball損失替換鉸鏈損失且對(duì)樣本賦予權(quán)重的方法，提出了基于pinball損失的一對(duì)一加權(quán)孿生支持向量機(jī)，較好地解決了多分類(lèi)算法OVO-TWSVM中噪聲敏感性與重取樣不穩(wěn)定問(wèn)題，使用多種求取樣本權(quán)重的方法，驗(yàn)證了提出方法的有效性.同時(shí)，與OVO-TWSVM、OVA-TWSVM和Pin-TWSVM等算法進(jìn)行了比較，表明了Pin-OVO-STWSVM算法有效提高了多分類(lèi)算法的性能.