魯棒雙參數(shù)化間隔支持向量機

馬婷婷，楊志霞，葉俊佑

新疆大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，烏魯木齊830046

支持向量機（support vector machine，SVM）是一種有監(jiān)督的學(xué)習(xí)算法，通常用于分類或回歸問題[1-5]。眾所周知，起初支持向量機是由Vapnik 提出[4-5]，基于結(jié)構(gòu)風(fēng)險最小化原理和最大間隔思想構(gòu)造的優(yōu)化模型，具有良好的泛化性能，在文本分類[6]、模式識別[7]、金融回歸[8]、計算生物學(xué)[9]等領(lǐng)域都有廣泛的應(yīng)用。當(dāng)前，研究者們發(fā)展了許多支持向量機的擴展版本，如文獻[10-11]。特別地，受廣義特征值中心支持向量機（generalized eigenvalue proximal support vector machine，GEPSVM）[12]的啟發(fā)，Jayadeva 等人提出了一種基于非平行邊界超平面思想的雙支持向量機（twin support vector machine，TWSVM）[13]。雙支持向量機是通過求解一對較小規(guī)模的二次規(guī)劃問題來尋找兩個非平行超平面，從而使雙支持向量機的學(xué)習(xí)效率大約比標準支持向量機快4倍。最近，雙支持向量機也出現(xiàn)了許多變形版本，如文獻[14-17]。尤其，文獻[14]提出的雙參數(shù)化間隔支持向量機（twinparametric-margin support vector machine，TPMSVM）。利用了參數(shù)化間隔思想，使得該方法具有一定的抗噪聲能力。

上述所提及的方法，均是在訓(xùn)練集中的樣本點是精確的假設(shè)前提下而提出的。然而，在實際應(yīng)用中，訓(xùn)練集中的樣本點，通常會受到測量誤差和統(tǒng)計誤差的干擾，導(dǎo)致無法得到完全精確的數(shù)據(jù)。Goldfarb等人在文獻[18]中指出，輸入空間中的誤差會在決策時被放大導(dǎo)致錯誤決策。因此，探索能夠?qū)@種擾動數(shù)據(jù)具有魯棒性的學(xué)習(xí)算法是很有意義的。

近年來，針對擾動數(shù)據(jù)提出了不同類型的魯棒支持向量機。文獻[18-22]主要采用二階錐規(guī)劃（SOCP）構(gòu)建了魯棒模型。Xu 等人[23-24]提出了一類非盒型不確定性集的魯棒分類方法。Bi等人[25]考慮了一個統(tǒng)計框架，其中不確定數(shù)據(jù)被假設(shè)為一個隱藏的混合成分。此外，Tzelepis等人[26]認為訓(xùn)練集是服從已知的均值和協(xié)方差矩陣的多元高斯分布，其中每個樣本對應(yīng)一個不同的協(xié)方差矩陣來表示數(shù)據(jù)的不確定性。其他相關(guān)研究也可在文獻[27-29]中找到。

在本文中，受雙參數(shù)化間隔支持向量機[14]和具有高斯樣本不確定性的支持向量機（SVM with Gaussian sample uncertainty，SVM-GSU）[26]的啟發(fā)。提出了一個新的不確定數(shù)據(jù)的雙參數(shù)化間隔支持向量機模型，稱為魯棒雙參數(shù)化間隔支持向量機（robust twin parametricmargin support vector machine，R-TPMSVM）。該方法的任務(wù)是針對正類樣本點和負類樣本點分別尋找一個相應(yīng)的參數(shù)化間隔超平面，并不要求這兩個超平面平行。由于魯棒雙參數(shù)化間隔支持向量機通過求解兩個較小規(guī)模的優(yōu)化問題，使得它具有更好的訓(xùn)練效率。此外，在魯棒雙參數(shù)化間隔支持向量機中，假設(shè)每個樣本點都服從多元高斯分布，從而得到的不確定區(qū)域比固定超球或超橢球形式的不確定區(qū)域[21-22]更加靈活。最后，針對優(yōu)化問題，提出了有效的隨機梯度下降（stochastic gradient descent，SGD）算法。分別考慮了人工數(shù)據(jù)集、六個基準數(shù)據(jù)集和威斯康辛乳腺癌數(shù)據(jù)集等，實驗數(shù)據(jù)數(shù)值結(jié)果表明，魯棒雙參數(shù)化間隔支持向量機具有較好的泛化能力。

1 研究背景

本章將簡要介紹雙參數(shù)化間隔支持向量機[14]?？紤]以下二分類訓(xùn)練集：

其中，(xi,yi)是第i個樣本點，xi∈Rn是輸入，yi∈{+1,-1}是輸出，i=1,2,…,l，l是樣本點的個數(shù)。為了方便起見，記向量,i=1,2,…,l1和,j=1,2,…,l2分別表示正類樣本點和負類樣本點的輸入，并且令l1和l2分別為正類樣本和負類樣本的個數(shù)，顯然有l(wèi)=l1+l2。

對于線性情形，雙參數(shù)化間隔支持向量機的任務(wù)是尋找如下兩個非平行超平面：

事實上，式（2）和（3）分別確定了正類參數(shù)化間隔超平面和負類參數(shù)化間隔超平面。

為了得到參數(shù)化間隔超平面（2）和（3），考慮如下一對無約束優(yōu)化問題：

其中，λ1,λ2,v1,v2是非負參數(shù)，并且和是損失項。

若得到優(yōu)化問題（4）和（5）的解w+,b+,w-,b-，對一個新的樣本點x∈Rn，可由以下決策函數(shù)進行判別：

2 魯棒雙參數(shù)化間隔支持向量機

2.1 建立優(yōu)化模型

在本節(jié)中，針對帶不確定區(qū)域的二分類問題，提出了魯棒雙參數(shù)化間隔支持向量機。對于帶服從多元高斯分布不確定區(qū)域的訓(xùn)練集如下所示：

其中，第i個樣本點(xi,Σi,yi)服從多元高斯分布，xi∈Rn表示輸入的均值向量，為輸入的協(xié)方差矩陣，yi∈{±1}是類標簽，i=1,2,…,l。為了方便起見，用=1,2,…,l1表示正類樣本點的輸入，j=1,2,…,l2表示負類樣本點的輸入，且l=l1+l2。假設(shè)隨機向量。

現(xiàn)在，任務(wù)是分別針對正類樣本和負類樣本尋找如下兩個參數(shù)化間隔超平面：

分別稱式（8）為正類參數(shù)化間隔超平面，式（9）為負類參數(shù)化間隔超平面。事實上，假設(shè)正負類參數(shù)化間隔超平面將訓(xùn)練集式（7）中的樣本點正確分離當(dāng)且僅當(dāng)：

為此，構(gòu)造如下一對優(yōu)化問題：

其中，λ1，λ2＞0 是正則化參數(shù)，v1,v2＞0 是懲罰參數(shù)。并且

是第i個隨機向量的高斯概率密度函數(shù)（PDF）。

值得一提的是，在優(yōu)化問題（12）中，第一項是正則項，控制優(yōu)化問題的復(fù)雜度；第二項是使負類樣本盡可能遠離正參數(shù)化間隔超平面；第三項是正例類樣本點被正類參數(shù)超平面錯誤分類的損失。對于優(yōu)化問題（13），有類似的解釋。圖1 顯示了雙參數(shù)化間隔支持向量機和魯棒雙參數(shù)化間隔支持向量機的幾何直觀圖。

圖1 雙參數(shù)化間隔支持向量機和魯棒雙參數(shù)化間隔支持向量機的幾何直觀圖Fig.1 Geometric intuitions of twin parametric-margin support vector machine and robust twin parametric-margin support vector machine

2.2 優(yōu)化模型的求解

現(xiàn)將優(yōu)化問題（12）的目標函數(shù)寫作：

其中，針對第j個負類樣本（即第j個高斯函數(shù)）投影函數(shù)為：

針對第i個正類樣本（即第i個高斯函數(shù)）損失函數(shù)為：

為了求解優(yōu)化問題式（12），將使用隨機梯度下降（SGD）算法?，F(xiàn)在分別給出目標函數(shù)式（14）中的第二項和第三項的封閉形式。具體地，式（15）和式（16）分別可轉(zhuǎn)化為：

借用以下[26]定理：

定理假設(shè)隨機向量x∈Rn服從多維高斯分布，其中均值為μ∈Rn，協(xié)方差矩陣為，其概率密度函數(shù)為：

超平面H:aTx+b=0 將Rn空間分為兩個半空間，即Ω±={x∈Rn:aTx+b＞或＜0},Ω+∪Ω-=Rn且Ω+∩Ω-=φ且積分I±:Rn×R→R，定義為：

則有：

其中，dμ=aTμ+b和。

由定理可知，對于半空間：

Ω-={x∈≤0},積分式（15）可轉(zhuǎn)化為如下的閉式：

現(xiàn)分別對J+關(guān)于w+和b+求偏導(dǎo)數(shù)，可得：

類似地，優(yōu)化問題式（13）的目標函數(shù)可以表示為：

其中

同理，上兩式所示的積分可表示為：

現(xiàn)對目標函數(shù)式（25）分別關(guān)于w-和b-求偏導(dǎo)數(shù)，可得：

2.3 算法實施步驟

接下來，給出優(yōu)化問題式（11）和（12）的求解算法。受Pegasos 算法[30]的啟發(fā)，提出了一種求解魯棒雙參數(shù)化間隔支持向量機的隨機梯度下降算法。為了方便表示，對于訓(xùn)練集T（式（7）），令T=T++T-，其中集合T+包含所有正類樣本點，集合T-包含所有負類樣本點。該算法的輸入?yún)?shù)如下：（1）迭代次數(shù)Γ，（2）用于計算次梯度的正樣本個數(shù)和負樣本個數(shù)為k1和k2。對于初始值，設(shè)置任意的向量。第t次迭代，隨機地選取T+和T-的子集，它們的勢分別為k1和k2，即，其中=k1，。與此同時，設(shè)置迭代速率。可得優(yōu)化問題式（14）和（25）的近似表達式：

迭代更新步驟：

其中，一階偏導(dǎo)數(shù)由式（23）、（24）和式（32）、（33）給出，并要求分別投影到半徑為和[31]的超球中，即

算法1隨機梯度下降求解方法

3 數(shù)值實驗

在這一章中，為了說明提出的魯棒雙參數(shù)化間隔支持向量機的性能，將其在二維人工數(shù)據(jù)集、六個基準數(shù)據(jù)集和威斯康辛乳腺癌數(shù)據(jù)集進行了數(shù)值實驗。所有的代碼都是在MATLAB2015b 環(huán)境下完成的。硬件設(shè)備指標：Intel Core I5 CPU，4 GB內(nèi)存。為了簡化參數(shù)選擇的復(fù)雜性，令λ1=λ2，v1=v2，并分別在集合{2i|i=-8,-7,…,2}和集合{1，2，3，4，5，6}中選擇最優(yōu)參數(shù)，并使用10折交叉驗證的方式搜尋最優(yōu)參數(shù)。

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

為了展示魯棒雙參數(shù)化間隔支持向量機的幾何直觀，構(gòu)造了一個二維數(shù)據(jù)集，如圖2所示，三個負類樣本點用紅色的“×”表示，三個正類樣本點用綠色的“+”表示。假設(shè)每一個訓(xùn)練樣本的不確定性由協(xié)方差矩陣給出，即每個樣本點服從二維高斯分布。圖2（a）和圖2（b）直觀地顯示了傳統(tǒng)雙參數(shù)化間隔支持向量機（TPMSVM）和魯棒雙參數(shù)化間隔支持向量機（RTPMSVM）的分劃超平面。從圖2（a）不難發(fā)現(xiàn)，傳統(tǒng)雙參數(shù)化間隔支持向量機只能將六個點正確分類，而圖2（b）顯示魯棒雙參數(shù)化間隔支持向量機不僅能將六個點正確分類，而且還可以將相應(yīng)的不確定區(qū)域也正確地分類。這是因為傳統(tǒng)的雙參數(shù)化間隔支持向量機忽略了數(shù)據(jù)的不確定區(qū)域。

圖2 兩種方法的幾何直觀Fig.2 Geometric intuition of two methods

3.2 基準數(shù)據(jù)集

在本節(jié)中，將在以下六個基準數(shù)據(jù)集[32]上評估魯棒雙參數(shù)化間隔支持向量機，分別是Hepatitis、WPBC、HStatlog、Heart-c、Bupa Liver 和Votes。六個數(shù)據(jù)集的詳細信息展示在表1，包括樣本個數(shù)、屬性個數(shù)和所占類別比例。這些數(shù)據(jù)集都是二分類問題。對于有缺失值的數(shù)據(jù)集，用零填補。與文獻[22]中使用的數(shù)據(jù)集相同，并且采用了與文獻[22]相同的數(shù)據(jù)預(yù)處理方法。

表1 六個基準數(shù)據(jù)集簡介Table 1 Introduction to six benchmark datasets

將魯棒雙參數(shù)化間隔支持向量機與如下五種方法進行了對比：魯棒支持向量機（R-SVM）[18]、魯棒雙支持向量機（R-TWSVM）[22]、高斯樣本不確定支持向量機（SVM-GSU）、雙支持向量機（TWSVM）[13]、雙參數(shù)化間隔支持向量機（TPMSVM）[14]。首先，考慮簡化后的不確定區(qū)域，即每個樣本的不確定區(qū)域固定為一個半徑為r的超球體。對于魯棒雙參數(shù)化間隔支持向量機，只需要為每個樣本xi∈Rn，構(gòu)造各向同性協(xié)方差矩陣Σi=(r,r,…,r)n，假設(shè)其在95%的置信度水平。表2中的前三個方法的數(shù)值結(jié)果來自于文獻[22]。在這六個基準數(shù)據(jù)集上執(zhí)行了雙參數(shù)化間隔支持向量機（TPMSVM），高斯樣本不確定支持向量機（SVM-GSU）和魯棒雙參數(shù)化間隔支持向量機（R-TPMSVM），結(jié)果見表2。表現(xiàn)較好的結(jié)果用黑體表示。從表2可以看出，魯棒雙參數(shù)化間隔支持向量機在四個數(shù)據(jù)集具有較好的性能。值得注意的是，本文提出的方法是線性分類器，并不需要使用核函數(shù)。

此外，圖3 對比了魯棒雙參數(shù)化間隔支持向量機（R-TPMSVM）和高斯樣本不確定支持向量機（SVMGSU）在六個基準數(shù)據(jù)集上的訓(xùn)練時間。顯然地，除了威斯康辛（WPBC）數(shù)據(jù)集之外，魯棒雙參數(shù)化間隔支持向量機所花費的時間小于高斯樣本不確定支持向量機所花費的時間。也可以注意到對于較大的數(shù)據(jù)集，本文的方法在時間上有更多的優(yōu)勢。

圖3 兩種方法訓(xùn)練時間的對比Fig.3 Comparison of training time between two methods

不難發(fā)現(xiàn)，表2 中的結(jié)果只考慮了一種特殊情況，具有各向同性協(xié)方差矩陣的不確定區(qū)域。但魯棒雙參數(shù)化間隔支持向量機可應(yīng)用于更一般的情況。借用文獻[33]中三種方法和文獻[34]中的方法構(gòu)造協(xié)方差矩陣。由于六個基準數(shù)據(jù)集中數(shù)據(jù)并沒有重復(fù)采樣，需要構(gòu)建均值向量和協(xié)方差矩陣，從而得到形如訓(xùn)練集式（7）所示的樣本點。具體地，假設(shè)數(shù)據(jù)集中的觀測數(shù)據(jù)點xi為均值向量。接下來，需要構(gòu)造協(xié)方差矩陣。假設(shè)協(xié)方差矩陣是對角陣，即。對每一個屬性之間相互獨立的數(shù)據(jù)集來說，對角元素,p=1,2,…,n是各不相同的。

表2 六種方法在基準數(shù)據(jù)集上的準確率對比Table 2 Accuracy comparison of six methods on benchmark datasets

具體地說，用l個數(shù)據(jù)點的屬性觀測范圍計算協(xié)方差矩陣。用以下四種方法構(gòu)造協(xié)方差矩陣，將這四種協(xié)方差矩陣分別記作Σ1、Σ2、Σ3、Σ4。

第一種構(gòu)造協(xié)方差矩陣的方式：

其中對角線元素為：

第二種構(gòu)造協(xié)方差矩陣的方式：

其中對角線元素為：

第三種構(gòu)造協(xié)方差矩陣的方式：

其中對角線元素為：

第四種構(gòu)造協(xié)方差矩陣的方式：

其中，對角線元素為：

其中，xi*取自于與xi不同類的樣本點中距離xi最近的樣本點。需要說明的是，前三種構(gòu)造方式使得每個樣本點具有相同的協(xié)方差矩陣，只是協(xié)方差矩陣的對角線元素各不相同。而第四種方式，使得每個樣本具有不同的協(xié)方差矩陣。

表3給出魯棒雙參數(shù)化間隔支持向量機（R-TPMSVM）和高斯樣本不確定支持向量機（SVM-GSU）對應(yīng)于四種協(xié)方差矩陣的結(jié)果，包括準確率和訓(xùn)練時間，表現(xiàn)較好的結(jié)果用黑體表示。從表3可以看出，雖然魯棒雙參數(shù)化間隔支持向量機使用前三種構(gòu)造協(xié)方差矩陣的準確率不高于高斯樣本不確定支持向量機，但是本文方法的訓(xùn)練時間小于高斯樣本不確定支持向量機。值得注意的是，本文方法使用第四種構(gòu)造協(xié)方差矩陣的準確率都高于高斯樣本不確定支持向量機，訓(xùn)練時間也較有優(yōu)勢。四種協(xié)方差的構(gòu)造方式，可根據(jù)不同需要來進行靈活選擇。

表3 四種協(xié)方差矩陣的訓(xùn)練時間及準確率對比Table 3 Comparison of training time and accuracy of four covariance matrices

為了考慮參數(shù)對算法的影響，圖4展示了不同參數(shù)下魯棒雙參數(shù)化間隔支持向量機的準確率的變化情況。令正則化參數(shù)λ=λ1=λ2，懲罰參數(shù)v=v1=v2，當(dāng)固定其中一個參數(shù)，調(diào)節(jié)另一個參數(shù)，這樣可以觀察出魯棒雙參數(shù)化間隔支持向量機的準確率與參數(shù)的依賴關(guān)系。圖4（a）給出了當(dāng)懲罰參數(shù)v固定，正則化參數(shù)λ在集合{2i|i=-8,-7,…,2}中取不同的值時準確率的變化。圖4（b）給出了當(dāng)正則化參數(shù)λ固定，懲罰參數(shù)v在集合{1，2，3，4，5，6}中取不同的值時準確率的變化。可以看出，魯棒雙參數(shù)化間隔支持向量機在六個基準數(shù)據(jù)集上隨著參數(shù)的變化，準確率變化緩慢。即參數(shù)的選取對準確率影響不大。

圖4 不同參數(shù)下的準確率變化情況Fig.4 Accuracy changes under different parameters

3.3 威斯康辛乳腺癌數(shù)據(jù)集

威斯康辛乳腺癌數(shù)據(jù)集（WDBC）[32]采集了患者乳腺腫塊，得到了經(jīng)過細針穿刺（FNA）后的數(shù)字化圖像，并對這些數(shù)字圖像進行了特征提取，這些特征描述的是圖像中的細胞核，腫瘤分為良性和惡性。即該數(shù)據(jù)集569 個樣本中，包含惡性（212 個樣本）和良性（357 個樣本）兩類樣本。對于威斯康辛乳腺癌數(shù)據(jù)集，使用與文獻[26]相同的預(yù)處理方式。即對每一幅圖像進行相應(yīng)的特征計算，得到30 個特征值。（包括10 個特征的三個維度：平均值、標準差和最大值）。每個特征值保留4位數(shù)字，數(shù)據(jù)中沒有缺失值。每個樣本均值x=(x1,…,x10,s1,…,s10,w1,…,w10)T∈R30，其中xj表示均值，sj表示標準誤差，wj表示第j個特征的最大值，j=1,2,…,10。由于標準誤差si和方差有關(guān)系式，其中的樣本大小N是未知的。記每個輸入的協(xié)方差矩陣為，其中被設(shè)置為很小的常數(shù)（比如，10-6），表示此特征對于這個方向的不確定性非常小，而其余的方差通過位于標準差范圍內(nèi)并控制在均值的80%內(nèi)縮放得到。

表4給出了魯棒雙參數(shù)化間隔支持向量機與幾個方法的準確率，包括線性支持向量機（LSVM）[4]、功率支持向量機（PSVM）[35]、各向同性支持向量機（LSVM-iso）[22，25]、高斯樣本不確定支持向量機（SVM-GSU）[26]、雙參數(shù)化間隔支持向量機（TPMSVM）[14]。前四種方法的結(jié)果來自文獻[35]。這里隨機地將數(shù)據(jù)集分為10份，其中90%作為訓(xùn)練集，10%作為測試集，最優(yōu)參數(shù)由十折交叉驗證確定。本文方法的準確率結(jié)果是10次實驗結(jié)果的平均值。從表4明顯可以看出，魯棒雙參數(shù)化間隔支持向量機表現(xiàn)最好。

表4 幾種方法在威斯康辛乳腺癌數(shù)據(jù)集上的準確率比較Table 4 Comparison of accuracy of several methods on Wisconsin breast cancer dataset

4 結(jié)論

本文提出了魯棒雙參數(shù)化間隔支持向量機，為此設(shè)計隨機梯度下降（SGD）算法來求解相應(yīng)的優(yōu)化問題。通過引入非平行邊界超平面的思想，提出的魯棒雙參數(shù)化間隔支持向量機比高斯樣本不確定支持向量機更穩(wěn)定。魯棒雙參數(shù)化間隔支持向量機通過求解一對較小規(guī)模的優(yōu)化問題，因此具有較快的訓(xùn)練速度。在魯棒雙參數(shù)化間隔支持向量機中，由于不同的點對應(yīng)不同的協(xié)方差矩陣，考慮了更靈活的不確定區(qū)域。在人工數(shù)據(jù)集、基準數(shù)據(jù)集和威斯康辛乳腺癌數(shù)據(jù)集上的數(shù)值實驗表明，該方法具有較好的泛化性能。