基于pinball損失的一對一加權孿生支持向量機

李凱，李潔

(河北大學 網絡空間安全與計算機學院，河北 保定 071002)

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

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

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

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

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

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

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

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

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

1 相關工作

1.1 OVO-TWSVM

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

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

1.2 損失函數

對于傳統的SVM以及TWSVM，在建立相應模型時，主要使用了鉸鏈損失函數，即

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

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

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

2 基于pinball損失的一對一加權孿生支持向量機

將pinball損失函數和權重引入到一對一策略的多分類孿生支持向量機中,用pinball損失代替傳統的鉸鏈損失，并針對不同樣本的重要程度，為每一個樣本賦予一個權重，從而得到基于pinball損失的一對一加權孿生支持向量機算法Pin-OVO-STWSVM.下面將分為2種情況進行介紹.

2.1 線性情況

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

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

(1)

則獲得2個超平面的第i類和第j類的優化問題為

(2)

(3)

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

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

下面以式(2)為例，使用拉格朗日方法對其求解，為此，構造拉格朗日函數

(4)

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

根據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)

進一步化簡得到

(12)

令H=[Aiei]，G=[Ajej]，vi=[wibi]T，則式(12)變為

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

(13)

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

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

(14)

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

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

(15)

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

(16)

其中γ=(α-β).

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

(17)

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

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

(18)

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

(19)

2.2 非線性情況

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

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

(20)

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

(21)

(22)

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

(23)

(24)

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

(25)

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

(26)

3 實驗及結果分析

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

3.1 樣本權重的確定方法

為了研究不同樣本賦予不同權重時對分類結果的影響，使用3種確定權重值方法進行了實驗，分別為類中心距離法、模糊C均值法和S型方法.

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

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

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

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

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

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

3.2 人工數據集

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

為了檢測算法Pin-OVO-STWSVM的抗噪性，對每個數據集加入5%和10%的噪聲，獲得的數據集分別為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算法進行了對比，實驗結果如圖2所示.

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

圖1 人工數據集Fig.1 Artificial data sets

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

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

3.3 UCI數據集

為了進一步評價提出算法的性能，選用UCI數據庫中的12個數據集，分別為Iris、Wine、Glass、Balance、Seeds、Vowel、Ecoli、Hayes-roth、Vehicle、Thyroid、CMC和Car，使用OVO-TWSVM、OVA-TWSVM、Pin-OVO-TWSVM和Pin-OVO-STWSVM 4種算法對數據集進行分類，并使用3種確定權重的方法進行實驗，實驗結果如表1所示.

表1 不同算法在標準數據集上的準確率和標準差

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

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

表2 不同算法在加入噪聲的標準數據集上的準確率和標準差

4 結論

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