基于對(duì)偶隨機(jī)投影的線性核支持向量機(jī)

席 茜，張鳳琴，李小青，管 樺，陳桂茸，王夢(mèng)非

(空軍工程大學(xué) 信息與導(dǎo)航學(xué)院，西安710077)

基于對(duì)偶隨機(jī)投影的線性核支持向量機(jī)

席 茜*，張鳳琴，李小青，管 樺，陳桂茸，王夢(mèng)非

(空軍工程大學(xué) 信息與導(dǎo)航學(xué)院，西安710077)

(*通信作者電子郵箱245594320@qq.com)

針對(duì)大型支持向量機(jī)(SVM)經(jīng)隨機(jī)投影特征降維后分類精度下降的問題，結(jié)合對(duì)偶恢復(fù)理論，提出了面向大規(guī)模分類問題的基于對(duì)偶隨機(jī)投影的線性核支持向量機(jī)(drp-LSVM)。首先，分析論證了drp-LSVM相關(guān)幾何性質(zhì)，證明了在保持與基于隨機(jī)投影降維的支持向量機(jī)(rp-LSVM)相近幾何優(yōu)勢(shì)的同時(shí)，其劃分超平面更接近于用全部數(shù)據(jù)訓(xùn)練得到的原始分類器。然后，針對(duì)提出的drp-LSVM快速求解問題，改進(jìn)了傳統(tǒng)的序列最小優(yōu)化(SMO)算法，設(shè)計(jì)了基于改進(jìn)SMO算法的drp-LSVM分類器。最后實(shí)驗(yàn)結(jié)果表明，drp-LSVM在繼承rp-LSVM優(yōu)點(diǎn)的同時(shí)，減小了分類誤差，提高了訓(xùn)練精度，并且各項(xiàng)性能評(píng)價(jià)更接近于用原始數(shù)據(jù)訓(xùn)練得到的分類器；設(shè)計(jì)的基于改進(jìn)SMO算法的分類器不但可以減少內(nèi)存消耗，同時(shí)可以擁有較高的訓(xùn)練精度。

機(jī)器學(xué)習(xí)；支持向量機(jī)；隨機(jī)投影；序列最小優(yōu)化算法；降維

0 引言

支持向量機(jī)(Support Vector Machine, SVM)在1995年由Cortes等[1]首次提出，由于其擁有擅長(zhǎng)處理小樣本、非線性數(shù)據(jù)、高維模式識(shí)別的特點(diǎn)，并在一定程度下避免了“維數(shù)災(zāi)難”，所以基于SVM的分類器在文本分類領(lǐng)域中有著廣泛的應(yīng)用，在處理高維數(shù)據(jù)分類問題時(shí)也獨(dú)占優(yōu)勢(shì)。與此同時(shí)應(yīng)用于大型SVM的特征降維方法也成為研究熱點(diǎn)。近年來，隨機(jī)近似算法在大規(guī)模機(jī)器學(xué)習(xí)中應(yīng)用廣泛，其中隨機(jī)投影(Random Projections, RP)方法可以快速有效地解決高維數(shù)據(jù)的降維問題，用以減少相關(guān)優(yōu)化問題的計(jì)算代價(jià)。隨機(jī)投影是通過控制精度來減少維度的方法，保持兩個(gè)樣本之間成對(duì)的距離，因此屬于基于距離的方法。由于SVM也是基于距離的學(xué)習(xí)方法，故可以運(yùn)用隨機(jī)投影進(jìn)行特征降維。2007年到2009年期間,Kumar等[2]和Jethava等[3]證明了基于高斯隨機(jī)投影的SVM可以得到與原問題相近的相關(guān)誤差，訓(xùn)練時(shí)間與投影矩陣和輸入矩陣相關(guān)。2014年P(guān)aul等[4]證明了運(yùn)用隨機(jī)投影后的數(shù)據(jù)經(jīng)過SVM訓(xùn)練，可以在保持特征空間的幾何性質(zhì)的同時(shí)保持分類器的最大間隔和最小閉包球的幾何性質(zhì)，維持了原有的泛化性能，并實(shí)踐論證，同時(shí)從理論上證明了基于隨機(jī)投影的線性核SVM(Linear kernel SVM based on random projection, rp-LSVM)訓(xùn)練時(shí)間與輸入的非零數(shù)據(jù)的數(shù)量線性相關(guān)。

但隨機(jī)投影后得到的最優(yōu)解與原始問題的最優(yōu)解存在一定誤差，2012年Zhang等[5]將凸優(yōu)化中的Fenchel對(duì)偶理論與隨機(jī)投影相結(jié)合，得到一種基于對(duì)偶解恢復(fù)的隨機(jī)機(jī)器學(xué)習(xí)方法，能有效地恢復(fù)原始優(yōu)化問題的最優(yōu)解。大規(guī)模的SVM問題本質(zhì)也是大規(guī)模的優(yōu)化問題，隨即投影的降維方法在提升分類器訓(xùn)練效率的同時(shí)，也在一定程度下降低了對(duì)精度的要求。本文首先將對(duì)偶恢復(fù)思想應(yīng)用于rp-LSVM中，提出基于對(duì)偶隨機(jī)投影的線性核SVM(Linear kernel SVM based on dual random projection, drp-LSVM)，在保持了rp-LSVM優(yōu)點(diǎn)的同時(shí)，解決了其精度下降的問題。理論分析證明drp-LSVM在幾何上比rp-LSVM更接近于所有數(shù)據(jù)訓(xùn)練得到的原始分類器，證明了drp-LSVM的最大間隔超平面與最小閉包球保持了與rp-LSVM近似的幾何性質(zhì)，同樣確保了與原始空間相近的泛化能力。本文還針對(duì)提出的drp-LSVM快速求解問題，改進(jìn)了序列最小優(yōu)化(Sequential Minimal Optimization, SMO)算法，設(shè)計(jì)了基于改進(jìn)SMO算法的drp-LSVM分類器。最后的實(shí)驗(yàn)證明了drp-LSVM在繼承rp-LSVM優(yōu)點(diǎn)的同時(shí)，減小了訓(xùn)練誤差，提高了訓(xùn)練精度，訓(xùn)練結(jié)果的各項(xiàng)性能評(píng)價(jià)更接近于用原始數(shù)據(jù)訓(xùn)練得到的分類器?；诟倪M(jìn)SMO算法的drp-LSVM分類器在減少內(nèi)存消耗的同時(shí)有較高的訓(xùn)練精度。

1 相關(guān)概念

1.1 線性核支持向量機(jī)

設(shè)有訓(xùn)練集D={xi,yi}(i=1,2,…,n)，xi∈Rd，類標(biāo)簽yi∈{-1,+1}。對(duì)于線性可分的數(shù)據(jù)，SVM學(xué)習(xí)問題最基本的思想是基于訓(xùn)練集D在樣本空間中找到一個(gè)擁有最大間隔的劃分超平面[6]，轉(zhuǎn)化為凸二次規(guī)劃問題形式為：

(1)

s.t.yi〈w,xi〉≥1,?i∈{1,2,…,n}

(2)

這是SVM的基本形，其中w為劃分超平面的法向量。當(dāng)加入軟間隔與正則化思想并且核函數(shù)為線性核時(shí)，相應(yīng)的拉格朗日對(duì)偶問題為：

(3)

(4)

其中αi為拉格朗日算子，C≥αi≥0,i=1,2,…,n，C為常數(shù)。

設(shè)樣本數(shù)據(jù)集在半徑為R的球內(nèi)，支持向量到超平面的距離和(即SVM的間隔)為γ，則該假設(shè)集的VC維(Vapnik-Chervonenkis Dimension)是O(R2/γ2)，如此可以估計(jì)出泛化誤差界。

1.2 隨機(jī)投影

引理1 對(duì)任意的ε∈(0,1)及正整數(shù)n，m為正整數(shù)且滿足:m≥4(ε2/2-ε3/3)-1ln(n)

定義P為上述RP，對(duì)任意的含n個(gè)點(diǎn)的集合X，對(duì)于所有的u,v∈X，有不等式成立：

(1-ε)‖u-v‖2≤‖P(u)-P(v)‖2≤ (1+ε)‖u-v‖2

(5)

定理1 令α∈Rd是x∈Rn經(jīng)過標(biāo)準(zhǔn)高斯矩陣隨機(jī)投影得到的，則有如下概率成立：

(6)

引理2[5]令0<ε≤1/2，δ∈(0,1)，V∈Rm×n是任意的正定矩陣，高斯隨機(jī)矩陣A∈Rm×r，其中r=O(nε-2lg(n/δ))，則至少以1-σ的概率有如下不等式成立：‖VTV-VTAATV‖≤ε。

1.3SMO算法

SMO[10]是目前最快的求解二次規(guī)劃問題的算法，特別針對(duì)LSVM和數(shù)據(jù)稀疏時(shí)性能更優(yōu)。SVM訓(xùn)練中最核心的問題是求解二次規(guī)劃問題，傳統(tǒng)的方法利用Hessian矩陣求解最優(yōu)值需要很大的計(jì)算和存儲(chǔ)代價(jià)。SMO算法將大規(guī)模的優(yōu)化問題轉(zhuǎn)化為一系列包含兩個(gè)變量的子問題，從而避免了復(fù)雜的數(shù)值解法，有效地節(jié)省了時(shí)間成本并降低了內(nèi)存要求。SMO算法類似于坐標(biāo)上升，每次啟發(fā)式選擇兩個(gè)參數(shù)變量進(jìn)行優(yōu)化，不斷循環(huán)，直到達(dá)到函數(shù)最優(yōu)解。

SMO算法的關(guān)鍵步驟可以大概總結(jié)為：首先啟發(fā)式選擇兩個(gè)參數(shù)，固定其余參數(shù)，整體視為一個(gè)二元函數(shù)，由約束條件將一個(gè)參數(shù)用另一個(gè)參數(shù)表示，視為一個(gè)一元函數(shù)，并對(duì)一元函數(shù)求極值點(diǎn)，最后根據(jù)上下界和約束條件，對(duì)原始解進(jìn)行修剪，更新參數(shù)并取臨界特殊情況，進(jìn)行分析。

2 基于對(duì)偶隨機(jī)投影的線性核支持向量機(jī)

2.1 隨機(jī)投影的對(duì)偶恢復(fù)

設(shè)有如下目標(biāo)優(yōu)化問題：

(7)

則根據(jù)Fenchel對(duì)偶定理得到原優(yōu)化問題的對(duì)偶問題：

(8)

代入原問題有：

用梯度求解法可求得：

(9)

(10)

(11)

(12)

易知新解與原優(yōu)化問題最優(yōu)解存在較大誤差，即：

(13)

故將低維空間Fenchel對(duì)偶得到的最優(yōu)解代入到原優(yōu)化問題中，得到恢復(fù)后的最優(yōu)解。

根據(jù)上述推導(dǎo)，得到基于對(duì)偶解的隨機(jī)投影(drp)算法如下。

算法1 drp算法。

輸入 訓(xùn)練集D={xi,yi}，樣本維度m。

2)計(jì)算低維子空間下的最優(yōu)解z*。

3)計(jì)算對(duì)偶解qi=▽L(yiz*Tαi) 。

2.2drp-LSVM

由于支持向量機(jī)問題可以轉(zhuǎn)化為凸二次規(guī)劃問題，使用拉格朗日乘子法可得到其對(duì)偶問題，類比Zhang等[5]提出的對(duì)偶隨機(jī)投影算法中將低維優(yōu)化問題的共軛對(duì)偶變量代入到原問題中恢復(fù)最優(yōu)解的方法，將低維空間中解出的拉格朗日乘子代入到原始超平面的計(jì)算中去，得到恢復(fù)的最優(yōu)超平面。

(14)

(15)

2.3drp-LSVM的性質(zhì)分析

(16)

證明 令E=VTV-VTAATV

將上述式(14)、(15)問題經(jīng)過奇異值分解(Singular Value Decomposition, SVD)分解得到：

(17)

(18)

由式(17)、(18)有如下不等式成立：

(19)

又由拉格朗日對(duì)偶函數(shù)的凹性可知：

(20)

由式(19)、(20)兩個(gè)不等式得到：

(21)

即：

(22)

結(jié)合引理2可得：

(23)

將低位空間的最優(yōu)解轉(zhuǎn)換高維空間后有關(guān)系：

(24)

則易求得：

(25)

由式(23)、(25)可以看出，drp-LSVM求得的最優(yōu)解比直接經(jīng)過隨機(jī)投影降維的LSVM的最優(yōu)解更接近原始最優(yōu)解，即從幾何上更接近于原始分類器。

下面論證drp-LSVM最大間隔超平面的幾何性質(zhì)。

利用SVD有:

(26)

即有不等式(27)如下：

(27)

易得不等式(28)如下：

(28)

將(28)代入(27)則有：

(29)

(30)

由不等式(28)可知：

(31)

結(jié)合式(25)、(31)得到：

(32)

即：

由引理2可得：

(33)

同樣可以利用SVD和引理2證明最小閉包球(Minimum Enclosing Ball, MEB)的性質(zhì)如下。

由于LSVM的MEB的拉格朗日對(duì)偶問題為：

max{αT(diag(XXT))-αTXXTα}

(34)

s.t.αT1=1,α≥0

設(shè)閉包球半徑為R，球心向量為xc，則：

R2=αT(diag(XXT))-αTXXTα

(35)

(36)

經(jīng)隨機(jī)投影后：

(37)

對(duì)偶恢復(fù)后：

結(jié)合引理2易推得：

(38)

由上述理論分析可以得到，drp-LSVM的間隔和最小閉包球半徑與rp-LSVM相近，同樣保持了與原始空間的ε相關(guān)誤差，維持了與原空間相似的泛化性能。

3 基于改進(jìn)SMO算法的drp-LSVM分類器

雖然LSVM的訓(xùn)練和測(cè)試速度相對(duì)較快，但與KSVM相同，LSVM中最核心的問題還是求解二次規(guī)劃問題，本文為求解基于對(duì)偶隨機(jī)投影的LSVM設(shè)計(jì)了基于對(duì)偶隨機(jī)投影的SMO算法，主要思想如下：

第一步 計(jì)算上下界H和L：

(39)

第二步 計(jì)算Ws的二階導(dǎo)η，并更新Ws：

η=x1TAATx1+x2TAATx2-2x1TAATx2

(40)

(41)

ei=g(xi)-yi

(42)

(43)

(44)

第四步 在原空間下更新：

(45)

收斂條件為在界內(nèi)的樣例都能夠滿足卡羅需-庫恩-塔克(Karush-Kuhn-Tucker, KTT)條件，且其對(duì)應(yīng)的αi只在極小范圍內(nèi)變動(dòng)，設(shè)計(jì)流程如圖1所示。

圖1 分類器設(shè)計(jì)流程

4 實(shí)驗(yàn)驗(yàn)證與分析

實(shí)驗(yàn)環(huán)境為2.6GHzIntelCorei5處理器，8GB內(nèi)存，操作系統(tǒng)為L(zhǎng)inux，開發(fā)工具為Python、Java。實(shí)驗(yàn)數(shù)據(jù)來自lib-SVMData[11]，實(shí)驗(yàn)一基于Liblinear庫[12]進(jìn)行drp-SVM相關(guān)性能測(cè)試，參數(shù)設(shè)置為默認(rèn)參數(shù)。實(shí)驗(yàn)二測(cè)試基于改進(jìn)SMO算法的drp-SVM性能。數(shù)據(jù)集D1、D2分別為gisette_scale[13]、rcv1.binary[14]。D1含訓(xùn)練樣本6 000，測(cè)試樣本1 000，樣本維數(shù)為5 000，滿足中等規(guī)模數(shù)據(jù)量及維數(shù)的特征；D2含訓(xùn)練樣本202 421，測(cè)試樣本677 399，維數(shù)為47 236，滿足大規(guī)模高維度數(shù)據(jù)特征。為保證實(shí)驗(yàn)的準(zhǔn)確度和可信度，相關(guān)實(shí)驗(yàn)重復(fù)5次，最終實(shí)驗(yàn)數(shù)據(jù)取平均值。

4.1 實(shí)驗(yàn)一

針對(duì)中等規(guī)模數(shù)據(jù)集D1，為檢驗(yàn)分類器效果，考慮到數(shù)據(jù)集維數(shù)為5 000，則取四種不同投影維數(shù)512、1 024、2 048、4 096，在各種目標(biāo)維數(shù)下分別計(jì)算drp-SVM，rp-SVM和原分

類器(即用全部數(shù)據(jù)訓(xùn)練出來的支持向量機(jī)，圖中用full表示)的相關(guān)評(píng)估參數(shù)。圖2分別為三種分類器在不同維度下精度(Accuracy,ACC)、均方誤差(MeanSquareError,MSE)及平方相關(guān)系數(shù)(SquaredCorrelationCoefficient,SCC)的關(guān)系。

由圖2可看出，相比于rp-SVM，drp-SVM的各項(xiàng)訓(xùn)練指標(biāo)都更接近于所有訓(xùn)練數(shù)據(jù)得到的原始分類器。

針對(duì)較大規(guī)模數(shù)據(jù)集D2，結(jié)合數(shù)據(jù)集維數(shù)47 236，取四種不同投影維數(shù)1 024、2 048、4 096、8 192，在各種目標(biāo)維數(shù)下分別計(jì)算drp-SVM、rp-SVM和原分類器(即用全部數(shù)據(jù)訓(xùn)練出來的支持向量機(jī)，圖中用full表示)的相關(guān)評(píng)估參數(shù)。圖3分別為三種分類器在不同維度下精度(ACC)、均方誤差(MSE)及平方相關(guān)系數(shù)(SCC)的關(guān)系。

由圖3可看出，在大規(guī)模更高維度的數(shù)據(jù)集環(huán)境下，drp-SVM的各項(xiàng)訓(xùn)練指標(biāo)更優(yōu)于rp-SVM，同時(shí)更加接近原始分類器。

圖2 D1數(shù)據(jù)集下不同維數(shù)各分類器的性能指標(biāo)

圖3 D2數(shù)據(jù)集下不同維數(shù)各分類器的性能指標(biāo)

表1～2分別為針對(duì)數(shù)據(jù)集D1和D2訓(xùn)練不同分類器在最優(yōu)投影維數(shù)下訓(xùn)練時(shí)間(用time表示，單位為s)、最大間隔(γ)、5次交叉檢驗(yàn)(5-fold)后的精度以及分類錯(cuò)誤率(errorRate)的統(tǒng)計(jì)。

從表1～2可以看出，相比于rp-SVM，drp-SVM保留了其訓(xùn)練時(shí)間減少和保持最大間隔的優(yōu)點(diǎn)，并在此基礎(chǔ)上提高了訓(xùn)練精度，減小了誤差。

4.2 實(shí)驗(yàn)二

用數(shù)據(jù)集D1來測(cè)試基于改進(jìn)SMO算法的drp-SVM性能，為方便對(duì)比，將三種算法的訓(xùn)練時(shí)間(用time表示，單位為h)、訓(xùn)練中消耗內(nèi)存比(用memory表示)及分類錯(cuò)誤率(用errorRate表示)在一張圖中展現(xiàn)，如圖4所示。

表1 D1訓(xùn)練的三種分類器的各項(xiàng)參數(shù)

表2 D2訓(xùn)練的三種分類器的各項(xiàng)參數(shù)

圖4 基于SMO算法的三種分類器性能比較

由圖4可以看出，運(yùn)用改進(jìn)的算法(drp-SMO)的分類器比運(yùn)用所有數(shù)據(jù)訓(xùn)練的基于SMO算法的分類器(full-SMO)的分類器更高效、更節(jié)省內(nèi)存，且相比直接經(jīng)過隨機(jī)投影的SMO分類器(rp-SMO)準(zhǔn)確度更接近原始分類器。

5 結(jié)語

本文針對(duì)特征降維后的支持向量機(jī)精度下降等問題，設(shè)計(jì)了基于對(duì)偶隨機(jī)投影的線性核支持向量機(jī)(drp-LSVM)相關(guān)算法，并從理論分析的角度證明了求解drp-LSVM問題得到的最優(yōu)解比rp-LSVM的最優(yōu)解更接近于原始分類器得到的最優(yōu)解，保證了在特征降維后，訓(xùn)練得到的分類器能夠保持與原分類器相似的幾何性質(zhì)。文中還證明了drp-LSVM的最大間隔超平面與最小閉包球保持了與rp-LSVM近似的ε相關(guān)誤差，同樣確保了與原始空間相近的泛化能力。文中提出針對(duì)drp-LSVM的改進(jìn)SMO算法，設(shè)計(jì)了基于改進(jìn)SMO算法的分類器。大規(guī)模高維的數(shù)據(jù)集的實(shí)驗(yàn)證明了drp-LSVM在降維特征提高訓(xùn)練速度的同時(shí)，訓(xùn)練效果及性能評(píng)價(jià)更接近于原始分類器，改進(jìn)SMO算法在保持了算法穩(wěn)定性的同時(shí)擁有較高的訓(xùn)練速度和精度。本文僅圍繞特殊的線性核支持向量機(jī)以及高斯投影進(jìn)行了針對(duì)性研究，并沒有考慮非線性核及其他種類的隨機(jī)投影特征降維情況。大規(guī)模機(jī)器學(xué)習(xí)仍是目前主流的挑戰(zhàn)，有關(guān)隨機(jī)機(jī)器學(xué)習(xí)的技術(shù)方法有待進(jìn)一步深入研究。

)

[1]CORTESC,VAPNIKV.Support-vectornetworks[J].MachineLearning, 1995, 20(3): 273-297.

[2]KUMARK,BHATTACHARYYAC,HARIHARANR.Arandomizedalgorithmforlargescalesupportvectorlearning[EB/OL]. [2016- 10- 09].http://hariharan-ramesh.com/papers/krichiram_nips_07.pdf.

[3]JETHAVAV,SURESHK,BHATTACHARYYAC,etal.RandomizedalgorithmsforlargescaleSVMs[EB/OL]. [2016- 10- 09].https://www.researchgate.net/publication/45873558_Randomized_Algorithms_for_Large_scale_SVMs.

[4]PAULS,BOUTSIDISC,MAGDON-ISMAILM,etal.Randomprojectionsforlinearsupportvectormachines[J].ACMTransactionsonKnowledgeDiscoveryfromData, 2014, 8(4):ArticleNo. 22.

[5]ZHANGLJ,MAHDAVIM,JINR,etal.Recoveringtheoptimalsolutionbydualrandomprojection[J].JournalofMachineLearningResearch, 2012, 30: 135-157.

[6] 周志華.機(jī)器學(xué)習(xí)[M].北京:清華大學(xué)出版社,2016:121-145.(ZHOUZH.MachineLearning[M].Beijing:TsinghuaUniversityPress, 2016: 121-145.)

[7] 劉紅,劉蓉,李書玲.基于隨機(jī)投影的加速度手勢(shì)識(shí)別[J].計(jì)算機(jī)應(yīng)用,2015,35(1):189-193.(LIUH,LIUR,LISL.Accelerationgesturerecognitionbasedonrandomprojection[J].JournalofComputerApplications, 2015, 35(1): 189-193.)

[8] 王萍,蔡思佳,劉宇.基于隨機(jī)投影技術(shù)的矩陣填充算法的改進(jìn)[J].計(jì)算機(jī)應(yīng)用,2014,34(6):1587-1590.(WANGP,CAISJ,LIUY.Improvementofmatrixcompletionalgorithmbasedonrandomprojection[J].JournalofComputerApplications, 2014, 34(6): 1587-1590.)

[9]PLATTJC.Fasttrainingofsupportvectormachinesusingsequentialminimaloptimization[M].Cambridge,MA:MITPress, 1999: 185-208.

[10]CHANGCC,LINCJ.LIBSVM:alibraryforsupportvectormachines[J].ACMTransactionsonIntelligentSystems&Technology, 2011, 2(3):ArticleNo. 27.

[11]FANRE,CHANGKW,HSIEHCJ,etal.LIBLINEAR:alibraryforlargelinearclassification[J].JournalofMachineLearningResearch, 2008, 9: 1871-1874.

[12]GOLUBTR,SLONIMDK,TAMAYOP,etal.Molecularclassificationofcancer:classdiscoveryandclasspredictionbygeneexpressionmonitoring[J].Science, 1999, 286(5439): 531-537.

[13]LEWISDD,YANGY,ROSETG,etal.RCV1:anewbenchmarkcollectionfortextcategorizationresearch[J].JournalofMachineLearningResearch, 2004, 5: 361-397.

ThisworkispartiallysupportedbytheNationalNaturalScienceFoundationofChina(71503260),theNaturalScienceFoundationofShaanxiProvince(2014JM8345).

XI Xi, born in 1993, M. S. candidate. Her research interests include data mining, machine learning.

ZHANG Fengqin, born in 1964, M. S., associate professor. Her research interests include data mining, complex network, distributed database.

LI Xiaoqing, born in 1982, Ph. D., lecturer. Her research interests include intelligent data processing.

GUAN Hua, born in 1963, M. S., professor. His research interests include command automation.

CHEN Guirong, born in 1970, M. S., lecturer. Her research interests include complex network.

WANG Mengfei, born in 1992, M. S. candidate. His research interests include complex network, machine learning.

Linear kernel support vector machine based on dual random projection

XI Xi*, ZHANG Fengqin, LI Xiaoqing, GUAN Hua, CHEN Guirong, WANG Mengfei

(InformationandNavigationCollege,AirForceEngineeringUniversity,Xi’anShaanxi710077,China)

Aiming at the low classification accuracy problem of large-scale Support Vector Machine (SVM) after random-projection-based feature dimensionality reduction, Linear kernel SVM based on dual random projection (drp-LSVM) for large-scale classification problems was proposed with the introduction of the dual recovery theory. Firstly, the relevant geometric properties of drp-LSVM were analyzed and demonstrated. It’s proved that, with maintaining the similar geometric advantages of Linear kernel SVM based on dual random projection (rp-LSVM), the divided hyperplane of drp-LSVM was more close to the primitive classifier trained by complete data. Then, in view of the fast solution to drp-LSVM, the traditional Sequential Minimal Optimization (SMO) algorithm was improved and the drp-LSVM classifier based on improved SMO algorithm was completed. Finally, the experimental results show that, drp-LSVM inherits the advantages of rp-LSVM, reduces classification error, improves training accuracy, and all its performance indexes are more close to the classifier trained by primitive data; the classifier designed based on the improved SMO algorithm can reduce memory consumption and achieve higher training accuracy.

machine learning; Support Vector Machine (SVM); random projection; Sequential Minimal Optimization (SMO) algorithm; dimensionality reduction

2016- 11- 10;

2016- 12- 29。

國家自然科學(xué)基金資助項(xiàng)目(71503260)；陜西省自然科學(xué)基金資助項(xiàng)目(2014JM8345)。

席茜(1993—)，女，山西新絳人，碩士研究生， CCF會(huì)員，主要研究方向：數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)； 張鳳琴(1964—)，女，山西芮城人，副教授，碩士， CCF會(huì)員，主要研究方向：數(shù)據(jù)挖掘、復(fù)雜網(wǎng)絡(luò)、分布式數(shù)據(jù)庫； 李小青(1982—)，女，陜西涇陽人，講師，博士，主要研究方向：數(shù)據(jù)智能處理； 管樺(1963—)，男，湖北孝感人，教授，碩士，主要研究方向：指揮自動(dòng)化； 陳桂茸(1970—)，女，陜西合陽人，講師，碩士，主要研究方向：復(fù)雜網(wǎng)絡(luò)； 王夢(mèng)非(1992—)，男，山東濟(jì)南人，碩士研究生，主要研究方向：復(fù)雜網(wǎng)絡(luò)、機(jī)器學(xué)習(xí)。

1001- 9081(2017)06- 1680- 06

10.11772/j.issn.1001- 9081.2017.06.1680

TP181

A