一種基于FoBa算法思想的支持向量機(jī)稀疏SMO算法研究*

梁萬路

(解放軍炮兵學(xué)院5系43隊(duì) 合肥 230031)

1 引言

支持向量機(jī)[1～2](SVM)是由Vapnik所領(lǐng)導(dǎo)的貝爾實(shí)驗(yàn)室在1963年提出的一種非常有潛力的分類技術(shù),主要應(yīng)用于模式識(shí)別[3]領(lǐng)域。近年來,已取得了巨大的發(fā)展,成為機(jī)器學(xué)習(xí)領(lǐng)域一個(gè)標(biāo)準(zhǔn)的學(xué)習(xí)算法。當(dāng)前的研究主要集中在算法本身的改進(jìn)、拓展和算法實(shí)現(xiàn)上。隨著計(jì)算機(jī)技術(shù)的日益發(fā)展以及互聯(lián)網(wǎng)的日益普及,大規(guī)模,海量數(shù)據(jù)的處理能力成為分類器算法得以實(shí)現(xiàn)的現(xiàn)實(shí)要求。

傳統(tǒng)的實(shí)現(xiàn)方法由于算法復(fù)雜、存儲(chǔ)要求大、收斂速度慢等弊端無法滿足實(shí)際應(yīng)用的要求。支持向量機(jī)優(yōu)化問題具有對(duì)支持向量的分類等價(jià)于對(duì)整個(gè)樣本集的分類,優(yōu)化問題的解是樣本點(diǎn)的線性組合等特點(diǎn)。基于這些特點(diǎn)人們提出了解析方法,主要包括分塊算法、分解算法、SMO[5～6]算法,共同的思想是循環(huán)迭代:將原來較大的二次優(yōu)化問題分解為若干規(guī)模較小的子二次優(yōu)化問題,按照某種優(yōu)化策略,通過反復(fù)優(yōu)化子問題,最終使結(jié)果收斂到原問題的最優(yōu)解。SMO算法是將分解算法的思想推向極致,每次迭代僅優(yōu)化兩個(gè)樣本點(diǎn)的最小子集。但是這些方法對(duì)支持向量數(shù)目的約減并未過多關(guān)注,算法的稀疏性[9]有待進(jìn)一步提高。

支持向量機(jī)的分類速度與支持向量的數(shù)目成正比。因此對(duì)支持向量數(shù)目進(jìn)行約減可以提高算法的分類速度。本文將FoBa算法[10]對(duì)特征進(jìn)行約減的思想引入SMO算法中,對(duì)訓(xùn)練產(chǎn)生的作用甚微的支持向量進(jìn)行約減,提出了稀疏SMO算法,在海量數(shù)據(jù)的處理上取得了很好的效果。……