魯棒最小二乘孿生支持向量機及其稀疏算法

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

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

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

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

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

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

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

1 相關(guān)算法

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

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

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

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

對于非線性情況，LSTSVM通過引入核函數(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)造類似，非線性LSTSVM的兩個非平行的投影超平面為K(xT,MT)w1+b1=0 和K(xT,MT)w2+b2=0。對應(yīng)的判別函數(shù)為：

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

1.2 不完全Cholesky分解方法

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

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

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

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

為克服LSTSVM 對異常點敏感的缺陷，本文基于截斷最小二乘損失函數(shù)提出如下非線性魯棒LSTSVM模型：

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

其中，τ>0 為截斷參數(shù)，圖1給出了當τ=1.8 時Lτ(ξ)的圖像，從圖中可以看出當 |ξ|>τ時，損失值為一常數(shù)τ2，這使得損失值不會隨誤差值的增大而無限增大。

圖1 截斷最小二乘損失函數(shù)圖(τ=1.8,Lτ(ξ)=Lsq(ξ)-L2(ξ))Fig.1 Truncated least squares loss function plots(τ=1.8,Lτ(ξ)=Lsq(ξ)-L2(ξ))

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

2.2 R-LSTSVM的稀疏解

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

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

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

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

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

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

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

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

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

運用KKT 條件對式（16）進行求解，可得如下線性方程組：

2.3 稀疏R-LSTSVM算法

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

算法2 稀疏R-LSTSVM算法

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

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

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

2.4 R-LSTSVM的魯棒性

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

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

其中

此外：

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

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

同理可證如下命題2。

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

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

3 實驗

3.1 實驗設(shè)計

通過在模擬數(shù)據(jù)集和真實數(shù)據(jù)集上的實驗來驗證SR-LSTSVM 對異常點的魯棒性、解的稀疏性和處理大規(guī)模數(shù)據(jù)的能力。

為驗證算法的性能，將SR-LSTSVM算法與以下算法進行比較：

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

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

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

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

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

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

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

參數(shù)選取方法為首先采用網(wǎng)格搜索方式確定最優(yōu)參數(shù)所在區(qū)間，然后細化該搜索區(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]。

效果性能評估指標：采用分類準確率評估模型分類性能：

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

3.2 模擬數(shù)據(jù)集實驗

模擬數(shù)據(jù)點由位于兩條相交直線上的點擾動產(chǎn)生，正類和負類數(shù)據(jù)均為200個。在數(shù)據(jù)集中隨機選取3/4樣本點作為訓(xùn)練樣本，剩余樣本點作為測試樣本，在訓(xùn)練樣本中隨機選取五個樣本點并改變其標簽來模擬異常點。為了驗證SR-LSTSVM的魯棒性，在無異常點和有異常點的模擬數(shù)據(jù)集上進行對比實驗。

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

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

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

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

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

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

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

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

圖4 五種算法分類準確率排名的平均值對比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ù)據(jù)集實驗

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

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

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

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

4 總結(jié)

LSTSVM 模型易受異常點的影響且其解缺乏稀疏性。為克服這些缺陷，基于截斷最小二乘損失提出了具有魯棒性的LSTSVM（R-LSTSVM），并得到了R-LSTSVM的稀疏解，提出了稀疏R-LSTSVM（SR-LSTSVM）算法。此外，從加權(quán)的角度解釋了R-LSTSVM 具有魯棒性。實驗結(jié)果表明，SR-LSTSVM 比其他算法具有更好的分類準確率和更快的訓(xùn)練速度，是處理含異常點的大規(guī)模分類問題的合適選擇。