一種改進(jìn)的LSTSVM增量學(xué)習(xí)算法

周水生, 姚 丹

(西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 西安 710126)

支持向量機(jī)(support vector machines, SVM)[1]的主要思想是最大限度地分開(kāi)兩類訓(xùn)練樣本. 由于SVM能較好地克服維數(shù)災(zāi)難等問(wèn)題, 因而在模式分類、回歸分析、文本分類和生物信息學(xué)等領(lǐng)域應(yīng)用廣泛[2-4]. 為了研究交叉分類問(wèn)題, Jayadeva等[5]提出了非平行平面的分類器, 即孿生支持向量機(jī)(twin support vector machines, TWSVM), 其基本思想是構(gòu)造兩個(gè)非平行的超平面進(jìn)行分類, 其中每個(gè)超平面擬合一類樣本且盡量遠(yuǎn)離另一類樣本. TWSVM將傳統(tǒng)的一個(gè)規(guī)模較大的凸二次規(guī)劃問(wèn)題轉(zhuǎn)化為兩個(gè)規(guī)模較小的凸二次規(guī)劃問(wèn)題, 提高了訓(xùn)練速度[6]. 邵元海等[7]在TWSVM的基礎(chǔ)上提出了孿生邊界支持向量機(jī)(twin bound support vector machines, TBSVM), 其通過(guò)在目標(biāo)函數(shù)上增加正則化項(xiàng)實(shí)現(xiàn)結(jié)構(gòu)風(fēng)險(xiǎn)最小化. 目前, 對(duì)TWSVM的改進(jìn)已有許多[8-9], 使得TWSVM在魯棒性和泛化性能等方面均有提高. Kumar等[10]提出了最小二乘孿生支持向量機(jī)(least squares twin support vector machines, LSTSVM), 與LSSVM的不同點(diǎn)在于求解過(guò)程變成了求解兩個(gè)等式方程組, 因而提高了求解效率, 減少了存儲(chǔ)空間. 基于LSTSVM, 陳靜等[11]提出了加權(quán)的最小二乘孿生支持向量機(jī)(weighted least squares twin support vector machines, WLSTSVM), 其通過(guò)對(duì)樣本增加權(quán)重, 提高該算法的魯棒性, 但WLSTSVM分類效果的好壞取決于權(quán)重的選擇, 從而制約了其應(yīng)用范圍.

當(dāng)樣本數(shù)據(jù)規(guī)模較大時(shí), 文獻(xiàn)[10,12-13]給出的LSTSVM算法需要訓(xùn)練樣本較多, 使模型出現(xiàn)求逆過(guò)程計(jì)算量大、易產(chǎn)生過(guò)擬合、訓(xùn)練速度慢、計(jì)算復(fù)雜度高等缺點(diǎn). 針對(duì)LSTSVM算法的不足, 本文基于Sherman-Morrison定理[14]和迭代算法提出一種改進(jìn)的最小二乘孿生支持向量機(jī)(based on Sherman-Morrison theorem and iterative algorithm an improved least squares twin support vector machine, SMI-ILSTSVM)增量學(xué)習(xí)算法, 對(duì)最小二乘孿生支持向量機(jī)進(jìn)行改進(jìn)和優(yōu)化.

1 最小二乘孿生支持向量機(jī)

LSTSVM的基本思想是通過(guò)構(gòu)造兩個(gè)超平面進(jìn)行分類, 每個(gè)超平面回歸一類樣本且盡量遠(yuǎn)離另一類樣本[5]. 線性的LSTSVM就是求解下述問(wèn)題：

LSTSVM1：

(1)

LSTSVM2：

(2)

其中: A表示正類樣本; B表示負(fù)類樣本;c1,c2表示懲罰參數(shù); e1和e2表示全一向量. 根據(jù)式(1),(2), 可求得線性LSTSVM的解為

(3)

(4)

最后, 可使用所得到的超平面(4), 并應(yīng)用判別函數(shù), 即

(5)

非線性情況通過(guò)構(gòu)造核函數(shù)的方法獲得, 非線性的LSTSVM為

(6)

(7)

根據(jù)式(6),(7), 可求得非線性LSTSVM的解為

(8)

(9)

(10)

2 改進(jìn)的最小二乘孿生支持向量機(jī)

由于LSTSVM的求解難度在于求解規(guī)模為(m+1)×(m+1)矩陣的逆, 如果該矩陣為非滿秩矩陣, 則求解結(jié)果會(huì)出現(xiàn)病態(tài)解的現(xiàn)象[6]. 文獻(xiàn)[13,15]都是基于經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則對(duì)LSTSVM進(jìn)行不同的改進(jìn), 所以本文提出一種改進(jìn)的最小二乘孿生支持向量機(jī)(improved least squares twin support vector machine, ILSTSVM).

2.1 線性ILSTSVM

在線性LSTSVM的目標(biāo)問(wèn)題上加入經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則, 得到下述問(wèn)題：

ILSTSVM1：

(11)

ILSTSVM2：

(12)

可以求出式(11),(12)的解, 即

(13)

2.2 非線性ILSTSVM

對(duì)于非線性的情況, 采用核函數(shù)的方法, 即

類似于線性ILSTSVM的求解方法, 可求出式(14),(15)的解, 即

(16)

3 SMI-ILSTSVM增量學(xué)習(xí)算法

3.1 矩陣求逆分解定理

本文提出的SMI-ILSTSVM算法, 主要采用對(duì)矩陣的逆進(jìn)行分解, 然后重組矩陣的逆, 最終得到一種結(jié)構(gòu)相對(duì)簡(jiǎn)單、計(jì)算量較小的迭代求解算法, 其原理是通過(guò)迭代求解利用前一次的計(jì)算結(jié)果求逆, 不必直接求大樣本矩陣的逆.

定理1(Sherman-Morrison定理)[14]若矩陣A是一個(gè)可逆矩陣, u和v均為向量, 且

1+vTA-1u≠0,

則當(dāng)u=v時(shí),

(17)

3.2 線性SMI-ILSTSVM增量學(xué)習(xí)算法

增量學(xué)習(xí)(incremental learning)[16]算法降低了對(duì)時(shí)間和空間的需求, 更能滿足實(shí)際要求, 但每次迭代過(guò)程中只增加一個(gè)樣本, 會(huì)導(dǎo)致計(jì)算效率偏低. 本文采用隨機(jī)法選擇訓(xùn)練樣本, 在一定程度上降低了增量學(xué)習(xí)算法對(duì)分類精度的影響, 且每次隨機(jī)選擇一列訓(xùn)練樣本也提高了計(jì)算效率.

(18)

所以對(duì)于擴(kuò)展矩陣E計(jì)算更新后的ETE, 僅添加了一個(gè)小矩陣ssT, 更新后SMI-ILSTSVM模型的解可寫(xiě)為

(19)

由于式(19)中存在單位矩陣, 所以式(19)總是非奇異的, 此時(shí)可利用式(17)分解矩陣的逆. 令

(20)

則v1=-M-1FTe2, v2=N-1ETe1. 進(jìn)一步計(jì)算可得

根據(jù)上述推導(dǎo)過(guò)程, 線性SMI-ILSTSVM增量學(xué)習(xí)算法如下.

算法1線性SMI-ILSTSVM增量學(xué)習(xí)算法.

輸入: 訓(xùn)練集{X,L}, 罰參數(shù)ci>0(i=1,2,3,4);

1) (n,m)=size(X);

3) fori=1∶ndo

s=(Si)T和l=Li;

4) ifi==1 then

5) else

7) end if

8) end for.

觀察線性ILSTSVM的解式(13), 可知該模型的復(fù)雜度為O(((m+1)3+(m+1)2)n), 而線性SMI-ILSTSVM增量學(xué)習(xí)算法的復(fù)雜度為O(2(m+1)2n), 降低了復(fù)雜度, 因此, SMI-ILSTSVM增量學(xué)習(xí)算法計(jì)算效率更高.

3.3 非線性SMI-ILSTSVM增量學(xué)習(xí)算法

非線性SMI-ILSTSVM的擴(kuò)展向量為

由于非線性情形下計(jì)算高斯核矩陣需花費(fèi)大量的時(shí)間和內(nèi)存, 因此可先隨機(jī)選取樣本C的子集Z, 用核矩陣K(A,ZT)代替K(A,CT), 使SMI-ILSTSVM算法在訓(xùn)練時(shí)僅使用部分樣本數(shù)據(jù), 不但減少了算法的總計(jì)算量, 且降低了存儲(chǔ)空間, 在不影響分類性能的基礎(chǔ)上, 使算法具有稀疏性.

衡量稀疏性的一個(gè)指標(biāo)----稀疏水平[17]的計(jì)算公式為

(22)

其中:r為訓(xùn)練樣本中非零解數(shù)量的比例;m為訓(xùn)練樣本的大小. 先令

(23)

則

v1=-P-1HTe2, v2=Q-1GTe1.

進(jìn)一步計(jì)算可得

其中:

根據(jù)上述推導(dǎo)過(guò)程, 非線性SMI-ILSTSVM增量學(xué)習(xí)算法如下.

算法2非線性SMI-ILSTSVM增量學(xué)習(xí)算法.

輸入: 訓(xùn)練集{X,L}, 罰參數(shù)ci>0(i=1,2,3,4), 高斯核函數(shù)參數(shù)σ∈(2-11,23);

1) (n,m)=size(X);

3) fori=1∶ndo

4) ifi==1 then

5) else

7) end if

8) end for.

4 實(shí)驗(yàn)結(jié)果與分析

為了評(píng)價(jià)SMI-ILSTSVM算法的性能, 下面進(jìn)行人工數(shù)據(jù)和UCI數(shù)據(jù)集的仿真實(shí)驗(yàn). 實(shí)驗(yàn)條件為： Windows7系統(tǒng), 8 GB內(nèi)存, Intel(R)Core(TM)i7-4790 CPU@3.6 GHz, MATLAB R2014a, 核函數(shù)為

4.1 人工生成數(shù)據(jù)實(shí)驗(yàn)

先隨機(jī)生成200個(gè)交叉型樣本點(diǎn), 其中左類和右類各100個(gè), 分別用SVM和TWSVM構(gòu)造分類面. 實(shí)驗(yàn)結(jié)果表明, TWSVM的精度約為90%, 而線性SVM的精度約為60%. 對(duì)于交叉型數(shù)據(jù)集, TWSVM的分類效果比SVM的分類效果好. LSTSVM,WLSTSVM和SMI-ILSTSVM三種分類器針對(duì)含有噪聲的交叉樣本集的分類結(jié)果如圖1所示.

圖1 3種分類器的分類結(jié)果Fig.1 Classification results of three classifiers

由圖1可見(jiàn), LSTSVM和WLSTSVM分類器在交叉樣本點(diǎn)上受噪聲影響較大, 這是因?yàn)槲墨I(xiàn)[11]提出的權(quán)重算法對(duì)于交叉數(shù)據(jù)集缺乏魯棒性, 而本文提出的SMI-ILSTSVM增量學(xué)習(xí)算法的分類效果較好.

4.2 UCI數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果

為了驗(yàn)證SMI-ILSTSVM增量學(xué)習(xí)算法的分類性能, 本文選取列于表1中的6個(gè)標(biāo)準(zhǔn)UCI數(shù)據(jù)集, 并分別對(duì)線性和非線性兩種類型的SMI-ILSTSVM,WLSTSVM,LSTSVM,TWSVM進(jìn)行分類精度與訓(xùn)練時(shí)間的仿真實(shí)驗(yàn). 在實(shí)驗(yàn)中, 線性情形采用線性核函數(shù), 非線性情形采用高斯核函數(shù), 訓(xùn)練集隨機(jī)選取原有訓(xùn)練集的30%進(jìn)行訓(xùn)練, 核參數(shù)在區(qū)間[2-11,23]內(nèi)選取, 懲罰參數(shù)ci>0(i=1,2,3,4)在區(qū)間[0,2]內(nèi)選取, 所有參數(shù)的選取方法均采用十折交叉驗(yàn)證法[7,10]. 4種方法得到的分類結(jié)果列于表2～表5.

表1 標(biāo)準(zhǔn)UCI數(shù)據(jù)集屬性

表1可見(jiàn), 本文提出的線性SMI-ILSTSVM增量學(xué)習(xí)算法對(duì)于6種UCI數(shù)據(jù)集的分類精度和訓(xùn)練時(shí)間均好于TWSVM,LSTSVM和WLSTSVM. 對(duì)于同一個(gè)數(shù)據(jù)集, SMI-ILSTSVM的分類精度基本上最高, WLSTSVM的分類精度次之, 而TWSVM和LSTSVM的分類精度差別不大； SMI-ILSTSVM的訓(xùn)練時(shí)間最少, TWSVM的訓(xùn)練時(shí)間最多.

表2 線性核情形下4種方法的分類精度比較

表3 線性核情形下4種方法的訓(xùn)練時(shí)間比較

表4 非線性核情形下4種方法的分類精度比較

表5 非線性核情形下4種方法的訓(xùn)練時(shí)間比較

圖2 大規(guī)模數(shù)據(jù)集的稀疏水平Fig.2 Sparse level of large scale datasets

由表2～表5可見(jiàn), 本文提出的非線性SMI-ILSTSVM增量學(xué)習(xí)算法對(duì)于6種UCI數(shù)據(jù)集的分類精度和訓(xùn)練時(shí)間均好于TWSVM,LSTSVM和WLSTSVM. 對(duì)于同一個(gè)數(shù)據(jù)集, SMI-ILSTSVM的訓(xùn)練時(shí)間最少, 這是由于隨機(jī)選取訓(xùn)練樣本的子集進(jìn)行訓(xùn)練, 可確保較少的訓(xùn)練時(shí)間, 但犧牲了一定的分類精度； WLSTSVM的訓(xùn)練時(shí)間最多, 是由于計(jì)算樣本權(quán)重提高分類精度比較耗時(shí), 所以其分類精度較高. 因?yàn)榉蔷€性SMI-ILSTSVM增量學(xué)習(xí)算法在訓(xùn)練時(shí)僅使用部分樣本數(shù)據(jù), 所以在UCI數(shù)據(jù)集上并非一致地優(yōu)于其他3種已有算法, 這也是本文算法有待進(jìn)一步提高之處. 本文算法的優(yōu)勢(shì)在于不僅降低了存儲(chǔ)空間, 而且減少了算法的總計(jì)算量, 使算法具有稀疏性. 稀疏性是解向量的非零元素個(gè)數(shù), 本文使用其相對(duì)值, 即稀疏水平. 利用式(22)計(jì)算出不同訓(xùn)練樣本對(duì)應(yīng)的稀疏水平如圖2所示. 由圖2可見(jiàn), 本文提出的非線性SMI-ILSTSVM增量學(xué)習(xí)算法對(duì)于大規(guī)模數(shù)據(jù)集均具有一定的稀疏水平.

綜上可見(jiàn), 本文提出的SMI-ILSTSVM增量學(xué)習(xí)算法較LSTSVM算法具有更好的泛化性能, 避免了在求解該目標(biāo)函數(shù)時(shí)對(duì)病態(tài)矩陣求逆的處理, 算法的分類精度和訓(xùn)練時(shí)間有明顯提高； 采用隨機(jī)選擇法選取訓(xùn)練樣本的一列, 在一定程度上降低了增量學(xué)習(xí)算法對(duì)分類精度的影響, 也提高了計(jì)算效率； 引入隨機(jī)選擇訓(xùn)練樣本的一個(gè)子集代替全部訓(xùn)練樣本, 使核函數(shù)的計(jì)算量減小, 從而使算法具有稀疏性, 減少了運(yùn)算時(shí)間. 在UCI數(shù)據(jù)集上的實(shí)驗(yàn)表明, 本文算法能實(shí)現(xiàn)高精度和高效率的分類效果, 且適用于含有噪聲的交叉樣本集分類.