李 卉，楊志霞

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

（?通信作者電子郵箱yangzhx@xju.edu.cn）

0 引言

分類問題是機器學習中研究的熱點問題之一，針對此問題Vapink 在VC（Vapnik-Chervonenkis）維和統(tǒng)計學習理論的基礎上提出支持向量機（Support Vector Machine，SVM）［1］。與其他機器學習方法（例如人工神經(jīng)網(wǎng)絡［2］）相比，支持向量機具有許多優(yōu)勢。首先，支持向量機解決一個凸二次規(guī)劃問題，確保一旦獲得最佳解，它就是唯一解。其次，支持向量機通過最大化兩個類之間的間隔來得出模型，并基于結(jié)構(gòu)風險最小化原則，而不是經(jīng)驗風險最小化原則。目前，支持向量機已應用于不同領域，例如疾病診斷［3-4］、文本分類［5］和企業(yè)信用等級［6］等。

鑒于支持向量機優(yōu)越的性能，迄今為止它的擴展版本得到了長足發(fā)展。2007 年，Jayadeva 等［7］提出一種基于非平行分劃超平面思想的雙支持向量機（TWin Support Vector Machine，TWSVM）。雙支持向量機與廣義特征值中心支持向量機［8］的想法相似，都針對給定訓練集生成兩個非平行超平面解決二分類問題，但優(yōu)化問題的構(gòu)造不同。由于這兩個方法都是基于非平行超平面的思想構(gòu)造最終的決策函數(shù)，從而使得學習機具有更好的靈活性和泛化能力。最近，雙支持向量機的一些擴展算法也被不斷提出，如文獻［9-10］。然而，在現(xiàn)實生活中有許多需要解決的問題為多分類問題，如圖像分類［11］、疾病分類［12］、蛋白質(zhì)折疊識別［13］等。以雙支持向量機為基礎，文獻［14］提出多子支持向量機（Multiple Birth Support Vector Machine，MBSVM）解決多分類問題。多子支持向量機通過求解K 個小規(guī)模二次規(guī)劃問題來得到?jīng)Q策函數(shù)，從而有較低的計算復雜度，針對多分類問題具有一定的優(yōu)越性。

另一方面，在現(xiàn)實生活中，收集到的數(shù)據(jù)往往帶有噪聲，或者標簽記錯，這樣的數(shù)據(jù)稱之為異常值。多分類算法在遇到異常值的情況下，算法的性能會有所下降。有很多研究處理異常值都是通過對數(shù)據(jù)進行預處理，直接剔除異常值；然而直接剔除異常值會出現(xiàn)信息丟失等問題。因此，在不刪除異常值的前提下，提出魯棒的分類方法成為熱門的研究。例如，文獻［15］提出求解有噪聲數(shù)據(jù)的二分類方法，稱作基于Rescaled Hinge損失函數(shù)的魯棒支持向量機（Robust Support Vector Machines based on Rescaled Hinge loss function，RSVM-RHHQ）。

為了提高多分類方法對異常值的魯棒性，本文提出基于Rescaled Hinge 損失函數(shù)的多子支持向量機（Multiple Birth Support Vector Machine based on Rescaled Hinge loss function，RHMBSVM）。該方法通過將有界、非凸的Rescaled Hinge 損失函數(shù)引入多子支持向量機的優(yōu)化問題中，從而得到魯棒的優(yōu)化問題。事實上，該方法是一個加權(quán)多子支持向量機。給每個點不同的懲罰，從而可識別異常值，提高魯棒性。其次，針對K 個非凸優(yōu)化問題，通過共軛函數(shù)理論將問題進行等價轉(zhuǎn)換，利用變量交替策略構(gòu)造迭代算法，使問題得到了有效求解。本文方法主要的優(yōu)勢和特點可總結(jié)為如下3個方面：

1）針對多類分類問題，本文方法使用了非平行分劃超平面的思想，所構(gòu)建的優(yōu)化模型只需求解K 個小規(guī)模的二次規(guī)劃問題，主要求解對偶問題的未知量個數(shù)只與第k 類樣本點的個數(shù)有關(guān)，有效降低了計算復雜度。

2）針對帶異常值的多類分類問題，本文方法通過將Rescaled Hinge 損失函數(shù)引入到多子支持向量機中，給每個樣本點不同的懲罰，從而減弱異常值對模型性能的影響。

3）針對線性情形和非線性情形的多類分類問題，本文方法分別給出了具體的優(yōu)化模型和求解算法。具體地，當多類分類問題只需超平面就可分劃時，使用線性情形的算法；否則，就使用引入核函數(shù)的非線性情形的算法。值得注意的是，當非線性情形選擇的是線性核時，算法即可退化為線性情形。

數(shù)值實驗結(jié)果表明，在無異常值的UCI數(shù)據(jù)集中，本文方法的正確率比現(xiàn)有的多分類方法高。在有異常值的UCI數(shù)據(jù)集中，本文方法的魯棒性優(yōu)于現(xiàn)有的多分類方法。

1 準備知識

本章介紹了多子支持向量機和Rescaled Hinge損失函數(shù)。給定訓練集：

1.1 多子支持向量機

多子支持向量機的思想是針對訓練集T（1）尋找K個超平面，第k個超平面具體形式如下：

多子支持向量機通過求解K個小規(guī)模二次規(guī)劃問題來得到式（2）所示的超平面。其原理是第k類樣本點離第k個超平面盡可能遠，其余K -1 類樣本點離第k 個超平面盡可能近，從而可構(gòu)造多子支持向量機的第k個小規(guī)模二次規(guī)劃問題：

1.2 Rescaled Hinge損失函數(shù)

在本節(jié)中，簡單介紹一下Rescaled Hinge損失函數(shù)［15］。在文獻［16］中，用Correntropy［17］得到的損失函數(shù)C-loss為：

其中σ 是窗寬，常數(shù)當z=0 時，lC(0)=1。若定義最小二乘損失函數(shù)lls(z)=(1-z)2［18］，損失函數(shù)C-loss可寫為：

其中l(wèi)hinge(z)=max(0，1-z)，當z=0時，lrhinge(0)=1。

圖1［15］展示了Hinge 損失函數(shù)和不同η 的Rescaled Hinge損失函數(shù)的直觀幾何圖像。

圖1 Hinge損失函數(shù)和不同η值Rescaled Hinge 損失函數(shù)Fig.1 Hinge loss function and Rescaled Hinge loss function with different η

從圖像可看出Hinge 損失函數(shù)和Rescaled Hinge 損失函數(shù)都是單調(diào)函數(shù)，而Hinge損失函數(shù)是凸函數(shù)，Rescaled Hinge損失函數(shù)是非凸函數(shù)。從圖中也可看出，η 的值越接近0，Rescaled Hinge損失函數(shù)就越接近Hinge損失函數(shù)。

2 模型的提出

針對帶有異常值的多分類問題，本文提出基于Rescaled Hinge 損失函數(shù)的多子支持向量機（RHMBSVM）。該方法包括線性情形和非線性情形：線性情形針對超平面能夠分劃的多類分類問題提出，最終的決策函數(shù)由K 個超平面構(gòu)成；否則，本文通過引入核函數(shù)，構(gòu)造非線性情形的優(yōu)化模型，從而可得到K 個超曲面來構(gòu)造最終的決策函數(shù)。值得注意的是，當非線性情形時，如果選擇線性核函數(shù)，模型可退化為線性情形。

2.1 線性情形

現(xiàn)給出直觀的線性情形的優(yōu)化模型和求解過程。給定訓練集T（1），構(gòu)造如下K個超平面：

為了得到上述超平面，構(gòu)造如下原始優(yōu)化問題：

其中ck≥0 是懲罰參數(shù)。優(yōu)化問題（9）中，目標函數(shù)的第一項表示除了第k類樣本以外的K -1類樣本離第k個超平面盡可能近，第二項表示第k類樣本離第k個超平面盡可能地遠。為了使不同的樣本賦予不同的權(quán)重，這里使用了有界、非凸的Rescaled Hinge損失函數(shù)。

現(xiàn)在給出求解優(yōu)化問題（9）的求解過程，由于β 是常數(shù)，對優(yōu)化問題（9））沒有影響，因此優(yōu)化問題（9）等價于下面的優(yōu)化問題：

由于引入非凸的Rescaled Hinge 損失函數(shù)，導致優(yōu)化問題（10）為一個非凸的優(yōu)化問題，不方便求解，因此，通過共軛函數(shù)理論對優(yōu)化問題（10）進行等價轉(zhuǎn)換，再采用變量交替策略得到優(yōu)化問題（10）解(wk，bk)。具體地，引入輔助函數(shù)h(v)=-v ln(-v)+v(v ＜0)，根據(jù)共軛函數(shù)理論［19］，h(v)的共軛函數(shù)為：

接下來，將共軛函數(shù)理論應用到需要求解的非凸優(yōu)化問題（10）中。

由于求解式（18）的上界，等價于求解式（18）的最大值。因此，優(yōu)化問題（10）等價為如下形式：

此時，式（20）第二項中損失函數(shù)的系數(shù)可統(tǒng)一寫成一個關(guān)于的函數(shù)的形式因此，優(yōu)化問題（20）可寫成：

從優(yōu)化問題（21）看出，與多子支持向量機的優(yōu)化問題不同之處是懲罰參數(shù)是關(guān)于的函數(shù)，從而給予每個樣本不同的懲罰，由此可降低異常值的影響。優(yōu)化問題（21）的解可通過求解其對偶問題得到。通過引入拉格朗日乘子向量αk，構(gòu)造拉格朗日函數(shù)，利用KKT（Karush-Kuhn-Tucker）條件，可得優(yōu)化問題（21）的對偶問題［14］：

采用變量交替策略求解優(yōu)化問題（19）的第二步，當?shù)玫絻?yōu)化問題（21）的解(wk，bk)時，則優(yōu)化問題（19）的目標函數(shù)第一項為常數(shù)，不影響優(yōu)化問題的解。因此，優(yōu)化問題（19）等價于：

根據(jù)共軛函數(shù)理論中的式（17）和v 與r的關(guān)系式，得到解的關(guān)系式由解的關(guān)系知式（24）的解析解為：

將預測點x代入決策函數(shù)，可得相應的類別標簽。

綜上，歸納線性基于Rescaled Hinge 損失函數(shù)的多子支持向量機算法步驟如下：

1）初始化參數(shù)。選擇合適的參數(shù)η ＞0和懲罰參數(shù)ck，迭代收斂精度δ。設置s=0和=-1(i=1，2，…，lk)。

2.2 非線性情形

不難想象，很多情況下多類分類問題不能用K 個超平面來構(gòu)造決策函數(shù)，此時可使用核映射將樣本點映射到Hilbert空間中，在Hilbert 空間中可實現(xiàn)線性分劃，此時在原空間中即是非線性分劃。將針對非線性情形，尋找如下帶有核函數(shù)的K個超曲面：

其中E 是由所有樣本點構(gòu)成的矩陣，ET=[A1，A2，…，AK]T，K(?，?)是核函數(shù)。注意到，當核函數(shù)被選取為線性核函數(shù)時，上述超曲面可退化為超平面。為得到式（27）所示的超曲面，構(gòu)造如下的優(yōu)化問題：

其中ck≥0是懲罰參數(shù)。

現(xiàn)在，給出優(yōu)化問題（28）的求解過程。與線性情形的求解過程相似，用共軛函數(shù)理論將優(yōu)化問題（28）作等價變換。令代入共軛函數(shù)理論得到式

（14），則優(yōu)化問題（28）可用下面的形式表示：

采用變量交替策略求解優(yōu)化問題（29）的第二步，將(uk，bk)代入優(yōu)化問題（29）中，可得：

同理，根據(jù)共軛函數(shù)理論，可知式（33）的解析解為：

綜上，歸納非線性基于Rescaled Hinge 損失函數(shù)的多子支持向量機算法步驟如下：

1）初始化參數(shù)。選擇合適的核函數(shù)K(?，?)，參數(shù)η ＞0，核參數(shù)p 和懲罰參數(shù)ck，迭代收斂精度δ。設置s=0 和

3 數(shù)值實驗

本章用基于Rescaled Hinge 損失函數(shù)的多子支持向量機（RHMBSVM）與多子支持向量機（MBSVM）［14］、基于Rescaled Hinge 損失函數(shù)的魯棒支持向量機（RSVM-RHHQ）［15］進行比較。其中，由于基于Rescaled Hinge損失函數(shù)的魯棒支持向量機只能求解二分類問題，所以本文使用該方法時利用了“一對余”策略解決多分類問題，并在Matlab中編輯其代碼。按照多子支持向量機和基于Rescaled Hinge損失函數(shù)的多子支持向量機的算法，在Matlab軟件中編輯相應的代碼。為了方便計算，設參數(shù)η ∈{0.2，0.5，1，2，3，4}，懲罰參數(shù)c=c1=c2=…=ck選自集合{2-8，2-4，2-1，21，24，28}。選用高斯核函數(shù)K(x，x')=其中的參數(shù)p 選自集合{1，3，5，7，9}。用五折交叉驗證［20］選擇參數(shù)，并計算各種方法的正確率。實驗環(huán)境：內(nèi)存為4.00 GB，64 位的Windows 7 操作系統(tǒng)中用軟件Matlab R2016b運行得到。

為了檢驗本文提出的方法的有效性，在UCI 數(shù)據(jù)庫中選取了6 組數(shù)據(jù)集，它們分別是：iris、wine、glass、vowel、vehicle、svmguide2。表1給出了6組數(shù)據(jù)集的詳細信息。

表1 實驗中使用的UCI數(shù)據(jù)集Tab.1 UCI datasets used in the experiment

本文采用正確率（Accuracy，AC）來衡量分類性能。為了表明本文方法性能，針對6 個UCI 數(shù)據(jù)集進行了實驗，并與多子支持向量機和基于Rescaled Hinge 損失函數(shù)的魯棒支持向量機進行了比較，實驗結(jié)果如表2所示。

表2 各方法在無噪聲數(shù)據(jù)集上的正確率和標準差 單位：%Tab.2 Accuracy and standard deviation of different methods on noise-free datasets unit：%

表2中對最高正確率進行加粗，由表2可看出本文方法在6個數(shù)據(jù)集中有4個數(shù)據(jù)集的正確率都比對比方法高，并且本文的方法對于數(shù)據(jù)集glass 和vehicle 計算的正確率也和對比方法的結(jié)果差不多。從表2 的最后一行可以看出，在對不加噪聲的UCI數(shù)據(jù)集的數(shù)值實驗中，本文方法正確率比MBSVM平均提升1.11個百分點，比RSVM-RHHQ 平均提升0.74個百分點。因此，表明本文方法比現(xiàn)有的兩種多分類方法具有更高的正確率。

為了表明基于Rescaled Hinge 損失函數(shù)的多子支持向量機的魯棒性，分別選取6 個UCI 數(shù)據(jù)集25%或50%的特征，加入均值為0，方差為0.01 或0.05 的高斯白噪聲，并與多子支持向量機和基于Rescaled Hinge 損失函數(shù)的魯棒支持向量機進行比較，實驗結(jié)果如表3所示。

由表3 可看出，加入不同的噪聲，本文方法的性能優(yōu)于多子支持向量機和基于Rescaled Hinge 損失函數(shù)的魯棒支持向量機，且噪聲對算法的影響較小。從標準差可知，本文方法的結(jié)果更穩(wěn)定。從表3 中各方法計算的平均值可看出，在對加噪聲UCI數(shù)據(jù)集的數(shù)值實驗中，本文方法正確率比MBSVM 提升2.10 個百分點，比RSVM-RHHQ 提升1.47 個百分點，體現(xiàn)出本文方法與其他兩種多分類方法相比，對有噪聲的數(shù)據(jù)集具有更好的魯棒性。

分類的結(jié)果與參數(shù)的選擇有很大的關(guān)系，圖2 展示了本文 方法 在 參數(shù)c ∈{2-8，2-4，2-1，21，24，28}和p ∈{1，3，5，7，9}時，分別繪制正確率的三維柱狀圖，柱狀圖中的每一個都是由一對參數(shù)c和p確定。

如圖2 所示，在所有數(shù)據(jù)集中，對參數(shù)c 和p 的變化敏感度最低的是wine數(shù)據(jù)集，敏感度較高的有vehicle和svmguide2數(shù)據(jù)集。在選擇參數(shù)時，可看出這六個數(shù)據(jù)集中的大部分數(shù)據(jù)集選擇的參數(shù)在p=1，c=21。

表3 各方法在有噪聲數(shù)據(jù)集上的正確率和標準差 單位：%Tab.3 Accuracy and standard deviation of different methods on datasets with noise unit：%

圖2 在參數(shù)c和p不同值時，RHMBSVM在UCI數(shù)據(jù)集上的正確率Fig.2 Accuracy of RHMBSVM on UCI datasets with different values of parameters c and p

4 結(jié)語

在本文中，對多分類問題中存在異常值這一現(xiàn)象，本文將Rescaled Hinge 損失函數(shù)引入傳統(tǒng)的多子支持向量機中，提出了基于Rescaled Hinge 損失函數(shù)的多子支持向量機。在求解過程中發(fā)現(xiàn)，本文方法實際上是一個加權(quán)的多子支持向量機，給每個點不同的懲罰，使異常值對決策函數(shù)產(chǎn)生更小的影響。本文方法只需求解K 個小規(guī)模的二次規(guī)劃問題，有相對低的計算復雜度。對UCI 數(shù)據(jù)集進行了實驗，并與多子支持向量機和基于Rescaled Hinge損失函數(shù)的魯棒支持向量機的“一對余”策略進行了實驗比較，表明了在多子支持向量機中，引入Rescaled Hinge 損失函數(shù)，進一步提高了算法的準確性和魯棒性。接下來可以探索如何降低異常值對支持向量機推廣到多分類算法的影響，并且文中參數(shù)較多，也可對參數(shù)的分析和選擇進行更深入探究。