靳啟帆，陳 麗，2，徐明亮，姜曉恒

1.鄭州大學(xué) 計(jì)算機(jī)與人工智能學(xué)院，鄭州450001

2.鄭州大學(xué) 體育學(xué)院（校本部），鄭州450001

支持向量機(jī)（support vector machine，SVM）[1]是一種基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化和最大間隔法原理的監(jiān)督學(xué)習(xí)方法。SVM通過(guò)求解一個(gè)凸二次規(guī)劃問(wèn)題得到劃分兩類(lèi)點(diǎn)的決策超平面，而凸二次規(guī)劃問(wèn)題的求解計(jì)算復(fù)雜度較高，導(dǎo)致SVM 訓(xùn)練速度較慢。為克服這一問(wèn)題，Jayadeva等[2]提出了孿生支持向量機(jī)（twin support vector machine，TSVM）。TSVM 旨在尋找兩個(gè)非平行的投影超平面，使每一個(gè)超平面盡可能靠近一類(lèi)樣本點(diǎn)并且遠(yuǎn)離另一類(lèi)樣本點(diǎn)。與SVM 相比，TSVM 只需求解兩個(gè)規(guī)模更小的二次規(guī)劃問(wèn)題。對(duì)于平衡數(shù)據(jù)集，采用線性核的TSVM 計(jì)算復(fù)雜度僅為SVM 的1/4。為進(jìn)一步提高TSVM的運(yùn)算速度，Kumar和Gopal[3]基于最小二乘損失函數(shù)提出了最小二乘孿生支持向量機(jī)（least squares twin support vector machine，LSTSVM），LSTSVM 將TSVM中的不等式約束用等式約束替代，通過(guò)求解兩個(gè)線性規(guī)劃來(lái)代替求解復(fù)雜的二次規(guī)劃問(wèn)題。與TSVM相比，LSTSVM具有計(jì)算簡(jiǎn)單和訓(xùn)練速度快的優(yōu)勢(shì)。然而，由于LSTSVM采用的是最小二乘損失函數(shù)，一方面其損失值隨誤差值的增大而無(wú)限增大，導(dǎo)致具有較大誤差值的異常點(diǎn)對(duì)投影超平面的構(gòu)造影響較大，因此LSTSVM對(duì)異常點(diǎn)較敏感。另一方面，已有求解LSTSVM的算法得到的解中幾乎所有的訓(xùn)練樣本都是支持向量，即解缺乏稀疏性，而對(duì)于大規(guī)模數(shù)據(jù)，并不是所有的樣本點(diǎn)都對(duì)模型的建立起到關(guān)鍵的決策作用。針對(duì)以上兩個(gè)問(wèn)題，本文提出了一種魯棒最小二乘孿生支持向量機(jī)模型，并得到了其稀疏解。

克服模型對(duì)異常點(diǎn)敏感的常用方法可分為三類(lèi)：一類(lèi)是在模型中加入權(quán)重，Chen等[4]提出了加權(quán)最小二乘孿生支持向量機(jī)（weighted LSTSVM，W-LSTSVM），通過(guò)對(duì)樣本增加不同的權(quán)重，以提高算法的魯棒性，但是W-LSTSVM 對(duì)于每一個(gè)模型，僅對(duì)其中一類(lèi)數(shù)據(jù)加權(quán)重，這使得W-LSTSVM 對(duì)于含有交叉噪聲的數(shù)據(jù)集分類(lèi)效果不好。針對(duì)這一問(wèn)題，儲(chǔ)茂祥等[5]提出了廣泛權(quán)重的最小二乘孿生支持向量機(jī)（widely weighted least squares twin support vector machine，WWL-STSVM），WWL-STSVM 對(duì)于每個(gè)模型，在正負(fù)兩類(lèi)樣本上都增加權(quán)重，很好地抑制了交叉噪聲對(duì)分類(lèi)效果的影響。另一類(lèi)方法是采用估計(jì)值代替異常點(diǎn)處的值，黃賢源等[6]利用局部樣本中心距離對(duì)訓(xùn)練樣本進(jìn)行異常點(diǎn)檢測(cè)，然后用異常點(diǎn)的平面坐標(biāo)推導(dǎo)的估計(jì)值來(lái)代替異常點(diǎn)處的值。郭戰(zhàn)坤等[7]提出了一種基于局部異常因子（local outlier factor，LOF）和奇異譜分析（singular spectrum analysis，SSA）的LOF-SSA-LSSVM預(yù)測(cè)模型，采用LOF算法進(jìn)行異常點(diǎn)檢測(cè)，確定異常數(shù)據(jù)的位置，最后通過(guò)插值法或應(yīng)用LSSVM中的預(yù)測(cè)值來(lái)修正原始序列中的異常點(diǎn)的值。第三類(lèi)方法是利用非凸損失函數(shù)來(lái)提高模型的魯棒性。Shen 等[8]和Wu 等[9]基于截?cái)郒inge 損失函數(shù)提出魯棒SVM 模型。Wang 等[10]和Yang 等[11]基于截?cái)嘧钚《藫p失函數(shù)提出魯棒LSSVM（robust LSSVM，R-LSSVM）模型。安亞利等[12]提出了一種推廣的指數(shù)魯棒最小二乘支持向量機(jī)模型。實(shí)驗(yàn)結(jié)果表明基于非凸損失函數(shù)的方法可有效抑制異常點(diǎn)對(duì)模型分類(lèi)精度的影響。

增強(qiáng)解的稀疏性方面，常用方法是減枝法。Suykens等[13]通過(guò)去除Lagrange乘子相對(duì)較小的支持向量來(lái)提升算法的稀疏性。Zeng 等[14]通過(guò)移除在對(duì)偶空間里對(duì)目標(biāo)函數(shù)作用較小的樣本點(diǎn)來(lái)提高算法的稀疏性。Li等[15]提出通過(guò)將yi f(xi)的值較大的樣本點(diǎn)移除來(lái)達(dá)到稀疏的目的。然而，這類(lèi)方法需要迭代地求解一組線性方程組，雖得到了稀疏解，但增加了算法復(fù)雜性，降低了訓(xùn)練速度。劉小茂等[16]基于中心距離比值及增量學(xué)習(xí)的思想提出了一種基于預(yù)選支持向量的稀疏最小二乘支持向量機(jī)，該方法預(yù)先選取訓(xùn)練樣本集的子集訓(xùn)練模型，加快了LSTSVM的訓(xùn)練速度，然而當(dāng)所選子集不能代表原始樣本集特性時(shí)，會(huì)影響學(xué)習(xí)的效果。Jiao等[17]提出快速稀疏近似LSSVM（fast sparse approximation LSSVM，F(xiàn)SA-LSSVM），該方法通過(guò)從基于核的字典中逐個(gè)添加基函數(shù)來(lái)迭代地構(gòu)造近似決策函數(shù)，直到滿足停止條件。De等[18]提出固定大小LSSVM（fixed-size LSSVM，F(xiàn)S-LSSVM），該算法先固定一些向量作為支持向量，然后計(jì)算訓(xùn)練樣本的Rényi二階熵，根據(jù)計(jì)算出來(lái)的Rényi二階熵的大小來(lái)選擇支持向量，然而該方法在迭代過(guò)程中，樣本的熵不是在整個(gè)數(shù)據(jù)集中選擇，而是僅在工作集中選擇，這可能導(dǎo)致次最優(yōu)解。Zhou 等[19]基于核矩陣不完全選主元Cholesky 分解提出了基于主元Cholesky的原空間LSSVM（pivoting cholesky of primal LSSVM，PCP-LSSVM）算法，該算法與已有LSSVM 算法相比，在保持分類(lèi)準(zhǔn)確率的同時(shí)提高了收斂速度。

針對(duì)LSTSVM 對(duì)異常點(diǎn)敏感和解缺乏稀疏性問(wèn)題，本文基于截?cái)嘧钚《藫p失函數(shù)提出魯棒最小二乘孿生支持向量機(jī)模型（robust LSTSVM，R-LSTSVM），并從加權(quán)的角度解釋了R-LSTSVM 具有魯棒性，為得到R-LSTSVM 的稀疏解，將R-LSTSVM 首先表示成兩個(gè)凸函數(shù)的差，然后利用表示定理、DCA（difference of convex algorithm）方法和不完全Cholesky 分解提出了稀疏R-LSTSVM算法（sparse R-LSTSVM，SR-LSTSVM）。新算法可抑制異常點(diǎn)對(duì)模型的影響，并選取對(duì)模型建立有效的數(shù)據(jù)樣本點(diǎn)，適合處理帶異常點(diǎn)的大規(guī)模數(shù)據(jù)。

1 相關(guān)算法

1.1 最小二乘孿生支持向量機(jī)及相關(guān)算法

記訓(xùn)練樣本集為T(mén)={(x1,y1),(x2,y2),…,(xm,ym)}，其中xi∈?d為訓(xùn)練樣本，yi∈{+1,-1} 為樣本的類(lèi)別標(biāo)簽。設(shè)A∈表示標(biāo)簽為+1 的樣本組成的矩陣，B∈表示標(biāo)簽為-1 的樣本組成的矩陣，?m×d表示所有樣本組成的矩陣，則線性LSTSVM 模型如下：

其中，e1∈，e2∈為元素全為1 的向量，ξ和η表示誤差，C1和C2為懲罰因子。模型（1）、（2）的第一項(xiàng)表示使一類(lèi)訓(xùn)練樣本點(diǎn)盡可能靠近一個(gè)超平面，第二項(xiàng)表示最小二乘損失函數(shù)。由Lagrange 乘數(shù)法可得到線性LSTSVM的解為：

其中，E=[A e1],F=[B e2] 。由求到的w1、b1和w2、b2可得到兩個(gè)非平行的投影超平面為xTw1+b1=0 和xTw2+b2=0。對(duì)于未知標(biāo)簽的樣本x，根據(jù)樣本點(diǎn)離超平面的距離來(lái)判斷樣本點(diǎn)的標(biāo)簽，即f(x)=

對(duì)于非線性情況，LSTSVM通過(guò)引入核函數(shù)K(xi,xj)=?(xi)T?(xj)，其中?(x)是將x投影到高維特征空間的映射，得到非線性LSTSVM模型為：

（非線性LSTSVM1）

（非線性LSTSVM2）

其中，KAM=K(xi,xj)(xi∈A,xj∈M)，KBM=K(xi,xj)(xi∈B,xj∈M)，KMM=K(xi,xj)(xi∈M,xj∈M) 。由Lagrange乘數(shù)法可得到非線性LSTSVM的解為：

其中，H=[KAM e1]，G=[KBM e2] 。與線性LSTSVM投影超平面的構(gòu)造類(lèi)似，非線性LSTSVM的兩個(gè)非平行的投影超平面為K(xT,MT)w1+b1=0 和K(xT,MT)w2+b2=0。對(duì)應(yīng)的判別函數(shù)為：

通過(guò)式（7）、（8）得到的非線性LSTSVM 的解是稠密的，其計(jì)算復(fù)雜度為O(m3)。

1.2 不完全Cholesky分解方法

不完全Cholesky分解算法的時(shí)間復(fù)雜度為O(mr2)，其只需要計(jì)算核矩陣的至多r列(r?m)及對(duì)角線上的所有元素就可以得到跡范數(shù)意義下核矩陣K的最優(yōu)Nystr?m低秩近似PPT[19]。

2 稀疏魯棒最小二乘孿生支持向量機(jī)

由于LSTSVM采用的是最小二乘損失函數(shù)Lsq(ξ)=ξ2，損失值隨誤差值ξ的增大而無(wú)限增大，因此LSTSVM對(duì)于誤差值較大的異常點(diǎn)較敏感。為解決這一問(wèn)題，本文采用截?cái)嘧钚《藫p失函數(shù)來(lái)降低異常點(diǎn)對(duì)超平面的影響，提出魯棒LSTSVM 模型（R-LSTSVM），并從加權(quán)的角度解釋了R-LSTSVM的魯棒性。為使R-LSTSVM可處理大規(guī)模數(shù)據(jù)，本文基于表示定理、DCA 方法及不完全Cholesky 分解得到稀疏R-LSTSVM 算法（SRLSTSVM）。

2.1 魯棒最小二乘孿生支持向量機(jī)模型

為克服LSTSVM 對(duì)異常點(diǎn)敏感的缺陷，本文基于截?cái)嘧钚《藫p失函數(shù)提出如下非線性魯棒LSTSVM模型：

其中，模型（9）中目標(biāo)函數(shù)的第一項(xiàng)為正則項(xiàng)，表示最大化投影超平面?(x)Tw1+b1=0 和單側(cè)邊界超平面?(x)Tw1+b1=-1 之間的距離，從而使模型式（9）的結(jié)構(gòu)風(fēng)險(xiǎn)最小。式（10）中的目標(biāo)函數(shù)的第一項(xiàng)也為正則項(xiàng)，其可使模型（10）的結(jié)構(gòu)風(fēng)險(xiǎn)最小，C3和C4為正則化參數(shù)。采用的截?cái)嘧钚《藫p失函數(shù)Lτ(ξ)為：

其中，τ>0 為截?cái)鄥?shù)，圖1給出了當(dāng)τ=1.8 時(shí)Lτ(ξ)的圖像，從圖中可以看出當(dāng) |ξ|>τ時(shí)，損失值為一常數(shù)τ2，這使得損失值不會(huì)隨誤差值的增大而無(wú)限增大。

圖1 截?cái)嘧钚《藫p失函數(shù)圖(τ=1.8,Lτ(ξ)=Lsq(ξ)-L2(ξ))Fig.1 Truncated least squares loss function plots(τ=1.8,Lτ(ξ)=Lsq(ξ)-L2(ξ))

與最小二乘損失函數(shù)Lsq(ξ)=ξ2相比，最小二乘損失函數(shù)的損失值Lsq(ξ) 隨誤差值ξ的增大而無(wú)限增大。當(dāng)訓(xùn)練樣本中存在異常點(diǎn)時(shí)，異常點(diǎn)處的誤差值ξ通常較大，這導(dǎo)致異常點(diǎn)處具有較大的損失值，因而LSTSVM 的投影超平面較易受異常點(diǎn)的影響。而截?cái)嘧钚《藫p失函數(shù)將具有較大誤差值的異常點(diǎn)處的損失值設(shè)置為某個(gè)固定常數(shù)，減少了異常點(diǎn)對(duì)R-LSTSVM的投影超平面的影響。此外，在3.4節(jié)中，將從R-LSTSVM與加權(quán)LSTSVM 等價(jià)的角度來(lái)進(jìn)一步闡釋R-LSTSVM對(duì)異常點(diǎn)具有魯棒性。

2.2 R-LSTSVM的稀疏解

為了求解非凸優(yōu)化問(wèn)題式（9）、（10），并得到適合處理大規(guī)模數(shù)據(jù)的算法，本節(jié)基于DCA方法、不完全Cholesky分解及表示定理來(lái)得到R-LSTSVM的稀疏解。

如果損失函數(shù)是凸函數(shù)，通過(guò)對(duì)偶理論，優(yōu)化模型的最優(yōu)解w可以表示為：

其中，αi∈?。如果損失函數(shù)是非凸函數(shù)，則強(qiáng)對(duì)偶理論不成立，因此無(wú)法通過(guò)對(duì)偶理論得到式（12）。但是，通過(guò)下面的表示定理，可證明式（12）也適用于R-LSTSVM模型。

定理1（表示定理）[20-21]給定非空集合X,?(?)為從X到希爾伯特空間的映射，設(shè)訓(xùn)練樣本集為{(x1,y1),(x2,y2),…,(xm,ym)}∈X×?,g:?+→? 為單調(diào)不減實(shí)值函數(shù)，f:?m→? 為任意的損失函數(shù)，問(wèn)題

的最優(yōu)值w滿足式（12）。

由定理1可知，R-LSTSVM的解滿足如下定理。

由于Lτ(ξ)為非凸函數(shù)，因此模型（13）為非凸優(yōu)化問(wèn)題，然而，Lτ(ξ)可表示為兩個(gè)凸函數(shù)相減的形式：

為凸函數(shù)。因此，可采用DCA方法[10-11，22]求解模型（15），即通過(guò)迭代求解以下凸二次規(guī)劃問(wèn)題直至收斂來(lái)獲得其最優(yōu)解：

圖2 L2(ξ)和(ξ)的圖像Fig.2 Plots of L2(ξ) and (ξ)

運(yùn)用KKT 條件對(duì)式（16）進(jìn)行求解，可得如下線性方程組：

2.3 稀疏R-LSTSVM算法

由3.2 節(jié)稀疏解求解過(guò)程，可得到如下稀疏RLSTSVM算法。

算法2 稀疏R-LSTSVM算法

SR-LSTSVM 算法中第2 步中?的確定及P的求解可通過(guò)算法1得到。

復(fù)雜度分析：第2 步和第3 步的計(jì)算復(fù)雜度均為O(mr2)，通常r?m，迭代計(jì)算第4 步的計(jì)算復(fù)雜度為O(tmr)，其中t為迭代次數(shù)。因此，該算法總的計(jì)算復(fù)雜度為O(mr2+tmr)。在非線性情況下LSTSVM 的計(jì)算復(fù)雜度為O(m3)，因此，在非線性情況下SR-LSTSVM比LSTSVM的計(jì)算復(fù)雜度低。

由于不完全Cholesky分解只需要O(mr2)的時(shí)間復(fù)雜度計(jì)算核矩陣的至多r列(r?m)及對(duì)角線上元素就可以得到跡范數(shù)意義下核矩陣K的最優(yōu)Nystr?m 低秩近似，其時(shí)間復(fù)雜度遠(yuǎn)低于計(jì)算全核矩陣的時(shí)間復(fù)雜度。并且稀疏R-LSTSVM 算法可得到模型的稀疏解，其時(shí)間復(fù)雜度O(mr2+tmr)遠(yuǎn)低于具有稠密解的LSTSVM算法的時(shí)間復(fù)雜度O(m3)。因此，稀疏R-LSTSVM具有更快的訓(xùn)練速度，更適合處理大規(guī)模數(shù)據(jù)。

2.4 R-LSTSVM的魯棒性

本節(jié)基于文獻(xiàn)[23-24]中的思想從加權(quán)角度來(lái)解釋R-LSTSVM具有魯棒性。

引理Lτ(ξ)=min(τ2,ξ2)可以表示成：

其中

此外：

命題1 R-LSTSVM 模型式（9）中任何穩(wěn)定點(diǎn)可以通過(guò)迭代地求解如下模型得到：

顯然，式（35）中的優(yōu)化問(wèn)題具有閉式解（31）。式（34）中的優(yōu)化問(wèn)題是加入正則項(xiàng)的加權(quán)LSTSVM（32）。證畢。

同理可證如下命題2。

命題2 R-LSTSVM 模型（10）中任何穩(wěn)定點(diǎn)可以通過(guò)迭代地求解如下模型得到：

由命題1 和命題2 可知R-LSTSVM 與加入正則項(xiàng)的加權(quán)LSTSVM 等價(jià)。在模型（32）和（36）中，誤差較大的異常點(diǎn)將獲得較小的權(quán)重，因此模型對(duì)異常點(diǎn)具有魯棒性，從而R-LSTSVM 對(duì)異常點(diǎn)也具有魯棒性。這從加權(quán)的角度解釋了R-LSTSVM的魯棒性。

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)設(shè)計(jì)

通過(guò)在模擬數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)來(lái)驗(yàn)證SR-LSTSVM 對(duì)異常點(diǎn)的魯棒性、解的稀疏性和處理大規(guī)模數(shù)據(jù)的能力。

為驗(yàn)證算法的性能，將SR-LSTSVM算法與以下算法進(jìn)行比較：

（1）LSTSVM：最小二乘孿生支持向量機(jī)[3]，損失函數(shù)為最小二乘損失，LSTSVM通過(guò)求解兩組線性方程組來(lái)確定兩個(gè)非平行的投影超平面。

（2）LSTBSVM：基于最小二乘的孿生有界支持向量機(jī)（least squares twin bounded support vector machines，LSTBSVM）[26]，該模型在LSTSVM中加入了正則項(xiàng)。

（3）W-LSTSVM：加權(quán)最小二乘孿生支持向量機(jī)[4]，通過(guò)對(duì)樣本損失增加不同權(quán)重，來(lái)提高算法魯棒性。

（4）WWL-STSVM：廣泛權(quán)重的最小二乘孿生支持向量機(jī)[5]，對(duì)于每個(gè)模型，在正負(fù)兩類(lèi)樣本上都增加權(quán)重。

（5）PCP-LSSVM：基于選主元Cholesky分解的原空間LSSVM[19]，該算法為一種稀疏最小二乘支持向量機(jī)算法。

（6）SR-LSSVM：一種稀疏魯棒最小二乘支持向量機(jī)算法（Sparse R-LSSVM，SR-LSSVM）[27]。

在模擬數(shù)據(jù)集和中小規(guī)模真實(shí)數(shù)據(jù)集上將新算法與LSTSVM、LSTBSVM、W-LSTSVM 和WWL-STSVM結(jié)果進(jìn)行對(duì)比。在大規(guī)模真實(shí)數(shù)據(jù)集上，由于上述算法占用內(nèi)存較大，消耗時(shí)間較長(zhǎng)，因此將新算法與兩種稀疏算法PCP-LSSVM和SR-LSSVM的結(jié)果進(jìn)行對(duì)比。

參數(shù)選取方法為首先采用網(wǎng)格搜索方式確定最優(yōu)參數(shù)所在區(qū)間，然后細(xì)化該搜索區(qū)間，得到最優(yōu)參數(shù)取值。核函數(shù)采用Gaussian核函數(shù)，即K(xi,xj)=exp(-‖xi-xj‖2/(2σ2))，其中σ為參數(shù)，取值范圍為[10-10,1010]。在WLSTSVM、WWL-STSVM 和LSTBSVM 中，C1和C2為懲罰因子，C3和C4為正則化參數(shù)。WWL-STSVM 中的R為權(quán)重參數(shù)，取值范圍為[0,10]。SR-LSSVM 和PCP-LSSVM 中的C為正則化參數(shù)。在SR-LSTSVM中，停止參數(shù)ρ=10-4，固定光滑參數(shù)p=105。C、C1、C2、C3、C4的取值范圍為[10-10,1010]。τ的取值范圍為[0,102]。

效果性能評(píng)估指標(biāo)：采用分類(lèi)準(zhǔn)確率評(píng)估模型分類(lèi)性能：

所有實(shí)驗(yàn)均在Intel i5（2.50 GHz）處理器和內(nèi)存為4.0 GB的平臺(tái)上實(shí)現(xiàn)，編程環(huán)境為Matlab R2014a。

3.2 模擬數(shù)據(jù)集實(shí)驗(yàn)

模擬數(shù)據(jù)點(diǎn)由位于兩條相交直線上的點(diǎn)擾動(dòng)產(chǎn)生，正類(lèi)和負(fù)類(lèi)數(shù)據(jù)均為200個(gè)。在數(shù)據(jù)集中隨機(jī)選取3/4樣本點(diǎn)作為訓(xùn)練樣本，剩余樣本點(diǎn)作為測(cè)試樣本，在訓(xùn)練樣本中隨機(jī)選取五個(gè)樣本點(diǎn)并改變其標(biāo)簽來(lái)模擬異常點(diǎn)。為了驗(yàn)證SR-LSTSVM的魯棒性，在無(wú)異常點(diǎn)和有異常點(diǎn)的模擬數(shù)據(jù)集上進(jìn)行對(duì)比實(shí)驗(yàn)。

圖3 所給出了五種對(duì)比算法在無(wú)異常點(diǎn)和取相同異常點(diǎn)時(shí)的投影超平面。在圖3 中正類(lèi)的異常點(diǎn)用紅色菱形表示，負(fù)類(lèi)異常點(diǎn)用藍(lán)色五角星表示，正類(lèi)樣本點(diǎn)的投影超平面用紅色實(shí)線表示，負(fù)類(lèi)樣本點(diǎn)的投影超平面用黑色實(shí)線表示。通過(guò)圖3可以看出：加異常點(diǎn)前后，SR-LSTSVM的投影超平面變化比其他四種算法小，說(shuō)明SR-LSTSVM 比其他四種算法具有更好的魯棒性。這是由于SR-LSTSVM 的損失函數(shù)是截?cái)嘧钚《藫p失函數(shù)，當(dāng)訓(xùn)練樣本中存在異常點(diǎn)時(shí)，截?cái)嘧钚《藫p失函數(shù)會(huì)將具有較大誤差值的異常點(diǎn)處的損失值設(shè)置為一個(gè)常數(shù)，從而減少異常點(diǎn)對(duì)投影超平面的影響。W-LSTSVM 對(duì)于每一個(gè)模型，僅對(duì)其中的一類(lèi)數(shù)據(jù)加權(quán)重，對(duì)于含有交叉噪聲的數(shù)據(jù)集投影超平面變化較大。WWL-STSVM 對(duì)于每個(gè)模型，在正負(fù)兩類(lèi)樣本上都增加權(quán)重，因此加異常點(diǎn)前后投影超平面的變化比W-LSTSVM 小，但仍比SR-LSTSVM 大。稀疏性方面，SR-LSTSVM采用不完全Cholesky分解選出的樣本作為支持向量，如圖3（i）、（j）所示。其中，正類(lèi)支持向量（SV）用粉色實(shí)心圓表示，負(fù)類(lèi)SV用綠色菱形表示。然而，其他算法的解不具有稀疏性，幾乎所有樣本都是SV。只在SR-LSTSVM 上標(biāo)記SV。圖3（i）、（j）表明SR-LSTSVM在有異常點(diǎn)和無(wú)異常點(diǎn)的模擬數(shù)據(jù)集上都只需要兩個(gè)SV，表明SR-LSTSVM算法具有稀疏性。

圖3 模擬數(shù)據(jù)集上加異常點(diǎn)前后投影超平面對(duì)比Fig.3 Comparison of projection hyperplane on simulated datasets before and after adding outliers

為了進(jìn)一步體現(xiàn)SR-LSTSVM 在模擬數(shù)據(jù)集上的分類(lèi)性能，表1給出了五種算法在模擬數(shù)據(jù)集上有異常點(diǎn)和無(wú)異常點(diǎn)情況下的參數(shù)設(shè)置、準(zhǔn)確率和方差，其中準(zhǔn)確率和方差是算法獨(dú)立運(yùn)行100 次取得的平均值。表1 表明在無(wú)異常點(diǎn)和有異常點(diǎn)的模擬數(shù)據(jù)集上SRLSTSVM 比其他算法具有更高的準(zhǔn)確率。在數(shù)據(jù)集加入異常點(diǎn)后LSTSVM、LSTBSVM 和W-LSTSVM 三種算法的準(zhǔn)確率明顯下降，而WWL-STSVM和SR-LSTSVM的準(zhǔn)確率下降較小，但是WWL-STSVM 的下降幅度仍比SR-LSTSVM大，因此，SR-LSTSVM比其他四種算法具有更好的魯棒性。

表1 模擬數(shù)據(jù)集上算法的參數(shù)設(shè)置和分類(lèi)準(zhǔn)確率Table 1 Parameter setting and classification accuracy of algorithms on simulation data sets

3.3 中小規(guī)模真實(shí)數(shù)據(jù)集實(shí)驗(yàn)

在五組中小規(guī)模真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，數(shù)據(jù)集均來(lái)自LIBSVM網(wǎng)站（https：//www.csie.ntu.edu.tw/～cjlin/libsvmtools/datasets/），其中Shuttle 包含七個(gè)類(lèi)別，選取第四類(lèi)和第五類(lèi)數(shù)據(jù)。Segment 包含七個(gè)類(lèi)別，選取第二類(lèi)和第三類(lèi)數(shù)據(jù)。Satimage包含六個(gè)類(lèi)別，選取第二類(lèi)和第三類(lèi)數(shù)據(jù)。Pendigits包含九個(gè)類(lèi)別，選取第三類(lèi)和第四類(lèi)數(shù)據(jù)。在每組數(shù)據(jù)集中隨機(jī)選取3/4樣本點(diǎn)作為訓(xùn)練樣本，剩余樣本點(diǎn)作為測(cè)試樣本，在訓(xùn)練樣本中隨機(jī)選取10%的樣本點(diǎn)并改變其標(biāo)簽來(lái)模擬異常點(diǎn)。為驗(yàn)證SR-LSTSVM的魯棒性，所有實(shí)驗(yàn)均在含異常點(diǎn)的數(shù)據(jù)集上進(jìn)行。

表2和表3分別給出了五種算法在中小規(guī)模數(shù)據(jù)集上實(shí)驗(yàn)的參數(shù)設(shè)置和實(shí)驗(yàn)結(jié)果，其中nSVs 表示支持向量的個(gè)數(shù)。所有實(shí)驗(yàn)結(jié)果均為算法獨(dú)立運(yùn)行100次取得的平均值。從表3中可以看出SR-LSTSVM在Segment、Satimage、SVMguide1 和Pendigits 這四組數(shù)據(jù)上的分類(lèi)效果均好于其他算法，在Shuttle 上的準(zhǔn)確率比WWLSTSVM 略差，但SR-LSTSVM 的訓(xùn)練速度比WWLSTSVM 快。圖4 給出了五種算法在五組數(shù)據(jù)集上準(zhǔn)確率排名的平均值。從圖4可以看出SR-LSTSVM是五種算法中分類(lèi)準(zhǔn)確率最高的模型，這是由于SR-LSTSVM采用的是截?cái)嘧钚《藫p失函數(shù)，當(dāng)訓(xùn)練數(shù)據(jù)中存在異常點(diǎn)時(shí)，截?cái)嘧钚《藫p失函數(shù)會(huì)將具有較大誤差值的異常點(diǎn)的損失值設(shè)置為一個(gè)常數(shù)，從而減少異常點(diǎn)對(duì)投影超平面的影響，得到更符合數(shù)據(jù)分布的投影超平面。這提高了SR-LSTSVM 的分類(lèi)準(zhǔn)確率。訓(xùn)練速度方面，SR-LSTSVM 采用了核矩陣的低秩近似矩陣，避免了計(jì)算全核矩陣，具有較低的計(jì)算復(fù)雜度。因此，SR-LSTSVM比其他四種算法具有更快的訓(xùn)練速度。稀疏性方面，SR-LSTSVM 的支持向量的個(gè)數(shù)比其他算法少，這是由于SR-LSTSVM采用不完全Cholesky分解選擇支持向量，得到了具有稀疏性的解，而其他算法得到的解中幾乎所有樣本均是支持向量，不具有稀疏性。因此，SR-LSTSVM比其他四種算法具有更少的支持向量。

表3 中小規(guī)模數(shù)據(jù)集上算法的實(shí)驗(yàn)結(jié)果Table 3 Experimental results of algorithms on small and medium-sized benchmark datasets

圖4 五種算法分類(lèi)準(zhǔn)確率排名的平均值對(duì)比Fig.4 Comparison of average value of classification accuracy ranking of five algorithms

表2 中小規(guī)模數(shù)據(jù)集上算法的參數(shù)設(shè)置Table 2 Parameter settings for algorithms on small and medium-sized benchmark datasets

3.4 大規(guī)模真實(shí)數(shù)據(jù)集實(shí)驗(yàn)

為了驗(yàn)證SR-LSTSVM處理大規(guī)模數(shù)據(jù)的能力，將SR-LSTSVM與兩種稀疏算法SR-LSSVM和PCP-LSSVM在大規(guī)模真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果進(jìn)行比較。數(shù)據(jù)集均來(lái)自LIBSVM 網(wǎng)站，其中SensIT_Vehicle 包含三個(gè)類(lèi)別，選取第二類(lèi)和第三類(lèi)數(shù)據(jù)實(shí)驗(yàn)。在每組數(shù)據(jù)集中隨機(jī)選取3/4 樣本點(diǎn)作為訓(xùn)練樣本，剩余樣本點(diǎn)作為測(cè)試樣本，在訓(xùn)練樣本中隨機(jī)選取10%的樣本點(diǎn)并改變其標(biāo)簽來(lái)模擬異常點(diǎn)。為驗(yàn)證SR-LSTSVM的魯棒性，所有實(shí)驗(yàn)均在含異常點(diǎn)的數(shù)據(jù)集上進(jìn)行。

表4和表5分別給出了在大規(guī)模數(shù)據(jù)上三種稀疏算法的參數(shù)設(shè)置和實(shí)驗(yàn)結(jié)果，所有結(jié)果均為算法獨(dú)立運(yùn)行10 次取得的平均值。從表5 中可以看出：準(zhǔn)確率方面，SR-LSSVM 和SR-LSTSVM 比PCP-LSSVM 準(zhǔn)確率更高，這是由于SR-LSTSVM和SR-LSSVM均采用了對(duì)異常點(diǎn)具有魯棒性的損失函數(shù)，而PCP-LSSVM采用的是易受異常點(diǎn)影響的最小二乘損失函數(shù)。SR-LSTSVM在W8a 和IJCNN 這兩組數(shù)據(jù)上的分類(lèi)效果比SR-LSSVM好。訓(xùn)練時(shí)間方面，SR-LSTSVM 的訓(xùn)練時(shí)間均少于SR-LSSVM。這是由于SR-LSTSVM通過(guò)計(jì)算兩個(gè)規(guī)模更小的線性規(guī)劃問(wèn)題得到最優(yōu)解，與SR-LSSVM相比具有更低的計(jì)算復(fù)雜度，因而具有更快的訓(xùn)練速度。稀疏性方面，SR-LSTSVM、SR-LSSVM 和PCP-LSSVM 三個(gè)算法均具有稀疏性，這是由于這三種算法均采用不完全Cholesky分解選出的樣本作為支持向量機(jī)。綜上所述，SR-LSTSVM 具有較高的分類(lèi)準(zhǔn)確率和較快的訓(xùn)練速度，更適合處理含異常點(diǎn)的大規(guī)模數(shù)據(jù)分類(lèi)問(wèn)題。

表4 大規(guī)模數(shù)據(jù)集上稀疏算法的參數(shù)設(shè)置Table 4 Parameter settings for sparse algorithms on large-scale data sets

表5 大規(guī)模數(shù)據(jù)集上稀疏算法的實(shí)驗(yàn)結(jié)果Table 5 Experimental results of sparse algorithms on large-scale data sets

4 總結(jié)

LSTSVM 模型易受異常點(diǎn)的影響且其解缺乏稀疏性。為克服這些缺陷，基于截?cái)嘧钚《藫p失提出了具有魯棒性的LSTSVM（R-LSTSVM），并得到了R-LSTSVM的稀疏解，提出了稀疏R-LSTSVM（SR-LSTSVM）算法。此外，從加權(quán)的角度解釋了R-LSTSVM 具有魯棒性。實(shí)驗(yàn)結(jié)果表明，SR-LSTSVM 比其他算法具有更好的分類(lèi)準(zhǔn)確率和更快的訓(xùn)練速度，是處理含異常點(diǎn)的大規(guī)模分類(lèi)問(wèn)題的合適選擇。