魯棒雙參數化間隔支持向量機

馬婷婷，楊志霞，葉俊佑

新疆大學 數學與系統科學學院，烏魯木齊830046

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

上述所提及的方法，均是在訓練集中的樣本點是精確的假設前提下而提出的。然而，在實際應用中，訓練集中的樣本點，通常會受到測量誤差和統計誤差的干擾，導致無法得到完全精確的數據。Goldfarb等人在文獻[18]中指出，輸入空間中的誤差會在決策時被放大導致錯誤決策。因此，探索能夠對這種擾動數據具有魯棒性的學習算法是很有意義的。

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

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

1 研究背景

本章將簡要介紹雙參數化間隔支持向量機[14]。考慮以下二分類訓練集：

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

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

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

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

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

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

2 魯棒雙參數化間隔支持向量機

2.1 建立優化模型

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

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

現在，任務是分別針對正類樣本和負類樣本尋找如下兩個參數化間隔超平面：

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

為此，構造如下一對優化問題：

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

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

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

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

2.2 優化模型的求解

現將優化問題（12）的目標函數寫作：

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

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

為了求解優化問題式（12），將使用隨機梯度下降（SGD）算法。現在分別給出目標函數式（14）中的第二項和第三項的封閉形式。具體地，式（15）和式（16）分別可轉化為：

借用以下[26]定理：

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

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

則有：

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

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

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

現分別對J+關于w+和b+求偏導數，可得：

類似地，優化問題式（13）的目標函數可以表示為：

其中

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

現對目標函數式（25）分別關于w-和b-求偏導數，可得：

2.3 算法實施步驟

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

迭代更新步驟：

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

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

3 數值實驗

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

3.1 人工數據集

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

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

3.2 基準數據集

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

表1 六個基準數據集簡介Table 1 Introduction to six benchmark datasets

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

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

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

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

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

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

第一種構造協方差矩陣的方式：

其中對角線元素為：

第二種構造協方差矩陣的方式：

其中對角線元素為：

第三種構造協方差矩陣的方式：

其中對角線元素為：

第四種構造協方差矩陣的方式：

其中，對角線元素為：

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

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

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

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

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

3.3 威斯康辛乳腺癌數據集

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

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

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

4 結論

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