李凱，李潔

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

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

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

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

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

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

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

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

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

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

1 相關(guān)工作

1.1 OVO-TWSVM

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

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

1.2 損失函數(shù)

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

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

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

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

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

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

2.1 線性情況

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

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

(1)

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

(2)

(3)

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

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

下面以式(2)為例，使用拉格朗日方法對其求解，為此，構(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)一步化簡得到

(12)

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

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

(13)

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

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

(14)

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

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

(15)

從而獲得原問題的對偶問題如下：

(16)

其中γ=(α-β).

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

(17)

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

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

(18)

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

(19)

2.2 非線性情況

通過引入核函數(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類和第j類對應(yīng)的優(yōu)化問題

(21)

(22)

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

(23)

(24)

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

(25)

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

(26)

3 實驗及結(jié)果分析

為了驗證提出算法的性能，將OVO-TWSVM、OVA-TWSVM、 Pin-OVO-TWSVM與提出的算法Pin-OVO-STWSVM在UCI數(shù)據(jù)庫中的12個標(biāo)準(zhǔn)數(shù)據(jù)集和4個人工生成數(shù)據(jù)集上進(jìn)行實驗.同時，為了檢測提出算法的抗噪性，在數(shù)據(jù)集中分別添加了5%和10%的特征噪聲，并檢測其準(zhǔn)確率.實驗中高斯核函數(shù)為K(i，j)=exp(-p‖x-y‖2)，使用了10重交叉驗證，并將10次測試的平均值及標(biāo)準(zhǔn)差作為最終的評價結(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)重時對分類結(jié)果的影響，使用3種確定權(quán)重值方法進(jìn)行了實驗，分別為類中心距離法、模糊C均值法和S型方法.

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

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

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

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

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

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

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

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

為了檢測算法Pin-OVO-STWSVM的抗噪性，對每個數(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.同時與OVO-TWSVM和Pin-OVO-TWSVM算法進(jìn)行了對比，實驗結(jié)果如圖2所示.

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

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

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

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

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

為了進(jìn)一步評價提出算法的性能，選用UCI數(shù)據(jù)庫中的12個數(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種算法對數(shù)據(jù)集進(jìn)行分類，并使用3種確定權(quán)重的方法進(jìn)行實驗，實驗結(jié)果如表1所示.

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

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

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

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

4 結(jié)論

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