李卓文 宋金朋

新鄉(xiāng)職業(yè)技術(shù)學(xué)院 河南新鄉(xiāng) 473000

摘要：支持向量機(jī)是一種新的機(jī)器學(xué)習(xí)方法，由于其出色的學(xué)習(xí)性能，該技術(shù)已成為當(dāng)前國(guó)際機(jī)器學(xué)習(xí)界的研究熱點(diǎn)。對(duì)SVM訓(xùn)練算法的最新研究成果進(jìn)行了綜述，著重說(shuō)明了各種的算法的思路和優(yōu)缺點(diǎn)?？偨Y(jié)了支持向量機(jī)理論及其應(yīng)用的現(xiàn)狀，對(duì)支持向量機(jī)的未來(lái)發(fā)展方向進(jìn)行了展望。

關(guān)鍵詞：支持向量機(jī)；訓(xùn)練算法；分類(lèi)

Abstract：Support Vector Machines are a kind of novel machine learning methods，which have become the hotspot of machine learning because of their excellent learning performance.This paper made a summarize of the new pro gress in the SVM training of algorithm，focused on the ideas of various algorithms，pointed out the advantages and disadvantages of them.The status quo of SVM theory and its applications are summarized and the future development direction of SVM theory is expected.

Keywords：Support vector machine；raining algrithm；categorizing；

支持向量機(jī)（Support Vector Machine，SVM）是Vapnik等1995年提出的一種基于統(tǒng)計(jì)學(xué)習(xí)理論[1]的模式識(shí)別方法。它在解決小樣本、非線性和高維模式識(shí)別問(wèn)題中具有特有的優(yōu)勢(shì)，且在某種程度上克服了維數(shù)災(zāi)難和過(guò)度學(xué)習(xí)等傳統(tǒng)難題，另其具有堅(jiān)實(shí)的理論基礎(chǔ)、簡(jiǎn)明的數(shù)學(xué)模型，使得支持向量機(jī)自提出以來(lái)受到廣泛的關(guān)注，并取得了長(zhǎng)足的發(fā)展。

1 支持向量機(jī)的訓(xùn)練算法

（1）塊算法與分解算法

塊算法（chunking algorithm）[2]最早是由Boser等人提出來(lái)的。它的出發(fā)點(diǎn)是刪除矩陣中對(duì)應(yīng)于Lagrange乘子為零的行和列不會(huì)對(duì)最終結(jié)果產(chǎn)生影響。對(duì)于給定的樣本，塊算法的目標(biāo)就是通過(guò)某種迭代方式逐步排除非支持向量。塊算法將矩陣的規(guī)模從訓(xùn)練樣本數(shù)的平方減少到具有非零Lagrange乘子的樣本數(shù)的平方，從而降低了訓(xùn)練過(guò)程對(duì)存儲(chǔ)容量的要求。這種方法只要支持向量遠(yuǎn)遠(yuǎn)小于訓(xùn)練樣本。但是，隨著算法迭代次數(shù)的增多，訓(xùn)練樣本集規(guī)模也會(huì)越來(lái)越大，算法依舊會(huì)變得十分復(fù)雜。

Osuna等人提出的分解算法（decomposition a1.gorithm）[3]，是目前有效解決大規(guī)模問(wèn)題的主要方法。主要思想是將訓(xùn)練樣本分成工作集 B 和非工作集 N，并保持大小不變。該算法的關(guān)鍵是如何最優(yōu)的選取工作集B。Joachims利用SVMlight提高算法收斂速度，是目前設(shè)計(jì)SVM分類(lèi)器的重要軟件。

除了分解算法，還有Huber近似算法、多拉格朗日乘子協(xié)同優(yōu)化算法|、剪枝算法等SVM的求解方法。

（2）序貫最小優(yōu)化算法

由Platt提出的序列最小優(yōu)化（sequential mini—real optimization，SMO）[4]算法是分解算法是針對(duì)工作集的個(gè)數(shù)為2的特殊情形，即SMO把一個(gè)大的優(yōu)化問(wèn)題分解成一系列只含兩個(gè)變量的優(yōu)化問(wèn)題。兩個(gè)變量的最優(yōu)化問(wèn)題可以解析求解，因而不需要迭代地求解二次規(guī)劃問(wèn)題。對(duì)分類(lèi)SMO算法，Keerthi等人修正了優(yōu)化條件，并針對(duì)經(jīng)驗(yàn)方法提出兩個(gè)改進(jìn)措施，以保證算法收斂和減少迭代次數(shù)。隨后Keerthi等人引提出了廣義SMO（generalized SMO，GSMO）算法，利用違反對(duì)的概念確定工作集，指出前面兩種改進(jìn)都是GSMO的特例，并證明，對(duì)任意的t﹥0以τ違反對(duì)為工作集，則GSMO算法有限終止，得到優(yōu)化問(wèn)題的τ近似優(yōu)化解.Lin對(duì)SMO算法的漸進(jìn)收斂性進(jìn)行了證明。

（3）模糊支持向量機(jī)

模糊支持向量機(jī)（Fuzzy SVM，F(xiàn)SVM）算法將模糊邏輯的方法與支持向量機(jī)的學(xué)習(xí)方法相結(jié)合，該算法給每個(gè)訓(xùn)練樣本都賦與相應(yīng)的模糊隸屬度，這樣不同的樣本對(duì)決策函數(shù)的學(xué)習(xí)有不同的貢獻(xiàn)，可以降低噪聲對(duì)最優(yōu)超平面的影響。

（4）粒度支持向量機(jī)[ 5]

粒度支持向量機(jī)是Y.C.Tang提出的一種新的訓(xùn)練算法，其主要思想是通過(guò)粒劃分來(lái)構(gòu)建?？臻g獲得一系列信息粒，然后在每個(gè)信息粒上進(jìn)行學(xué)習(xí)，最后通過(guò)聚合信息粒上的信息（如數(shù)據(jù)、規(guī)則、知識(shí)、屬性等）獲得最終的SVM 決策函數(shù)。如何進(jìn)行粒度劃分是粒度支持向量機(jī)研究的主要問(wèn)題。目前，主要有基于關(guān)聯(lián)規(guī)則的粒度支持向量機(jī)，利用聚類(lèi)方法對(duì)訓(xùn)練樣本集進(jìn)行粒度劃分的基于聚類(lèi)的粒度支持向量機(jī)，基于商空間的粒度支持向量機(jī)的基本思想是首先對(duì)訓(xùn)練樣本集進(jìn)行粗粒度的選擇SV，去除一部分對(duì)構(gòu)造最優(yōu)分類(lèi)超平面無(wú)用的樣本點(diǎn)，然后再對(duì)粗選后的樣本進(jìn)行細(xì)粒度的 SV 訓(xùn)練。此外還有基于樹(shù)形層次結(jié)構(gòu)的粒度支持向量機(jī)等。

（5）多分類(lèi)支持向量機(jī)

SVM起初主要是針對(duì)兩類(lèi)問(wèn)題的分類(lèi)，為了滿足現(xiàn)實(shí)生活應(yīng)用中多分類(lèi)問(wèn)題，需要構(gòu)造多類(lèi) SVM 分類(lèi)器，目前多分類(lèi)支持向量機(jī)算法的思路主要有兩種：

（1）在經(jīng)典 SVM 的基礎(chǔ)上對(duì)其目標(biāo)函數(shù)進(jìn)行優(yōu)化，構(gòu)造多分類(lèi)模型，進(jìn)而實(shí)現(xiàn)多分類(lèi)問(wèn)題。這種方法為一次性求解法，由于其計(jì)算復(fù)雜度比較高，在實(shí)際應(yīng)用中效率低，所以并不常用。

（2）將多分類(lèi)問(wèn)題歸結(jié)為多個(gè)兩分類(lèi)問(wèn)題，常用的算法主要有一對(duì)多[6-7]、一對(duì)一[8-9]、導(dǎo)向無(wú)環(huán)圖[10]、二叉樹(shù)[11]四種。文獻(xiàn)[12]對(duì)這四種算法分別進(jìn)行了詳細(xì)的描述，在訓(xùn)練復(fù)雜度、測(cè)試復(fù)雜度和分類(lèi)準(zhǔn)確率方面作了理論分析，并利用數(shù)據(jù)對(duì)分析結(jié)果進(jìn)行了驗(yàn)證。分析得出，導(dǎo)向無(wú)環(huán)圖的分類(lèi)性能最優(yōu)，一對(duì)一的分類(lèi)性能次之，二叉樹(shù)的分類(lèi)性能較差，一對(duì)多的分類(lèi)性能最差；在訓(xùn)練和測(cè)試耗時(shí)方面，二叉樹(shù)耗時(shí)最短，導(dǎo)向無(wú)環(huán)圖次之，一對(duì)一和一對(duì)多的耗時(shí)相對(duì)較長(zhǎng)。

2 支持向量機(jī)的應(yīng)用及發(fā)展方向

支持向量機(jī)理論自提出以來(lái)，在各種應(yīng)用領(lǐng)域得到了廣泛應(yīng)用，并在模式識(shí)別領(lǐng)域已經(jīng)得到成功應(yīng)用。在模式識(shí)別領(lǐng)域，SVM 方法主要應(yīng)用于手寫(xiě)數(shù)字識(shí)別、語(yǔ)音識(shí)別、人臉檢測(cè)與識(shí)別、文本分類(lèi)等方面。

支持向量機(jī)在生物信息領(lǐng)域，如蛋白質(zhì)的分類(lèi)和 DNA 分析等，取得了較好結(jié)果。此外，支持向量機(jī)還應(yīng)用于時(shí)間序列分析、回歸分析、聚類(lèi)分析、動(dòng)態(tài)圖像的人臉跟蹤、信號(hào)處理、語(yǔ)音識(shí)別、圖像分類(lèi)和控制系統(tǒng)等諸多領(lǐng)域。

盡管?chē)?guó)內(nèi)外學(xué)者對(duì)支持向量機(jī)的理論與算法開(kāi)展了許多有效的研究工作，但是其算法研究中還有很多尚未解決的問(wèn)題。

（1）如何徹底解決大樣本時(shí)訓(xùn)練算法速度慢、算法復(fù)雜、運(yùn)算量大等缺點(diǎn)；

（2）SVM 自選參數(shù)目前尚缺乏結(jié)構(gòu)化方法來(lái)實(shí)現(xiàn)參數(shù)的最優(yōu)選擇，

（3）訓(xùn)練樣本中數(shù)據(jù)含有不確定性以及噪聲時(shí)的 SVM 理論性能，即 SVM 理論的魯棒性問(wèn)題是值得研究的重點(diǎn)課題。

結(jié)束語(yǔ)

本文主要介紹了現(xiàn)有的SVM 訓(xùn)練算法，著重說(shuō)明了各種的算法的思路和優(yōu)缺點(diǎn).當(dāng)前對(duì)SVM的研究方興未艾，訓(xùn)練算法的研究方向主要是確定不同的優(yōu)化目標(biāo)，根據(jù)KKT 約束優(yōu)化條件尋找大規(guī)模訓(xùn)練樣本下的實(shí)用算法；應(yīng)用方向主要是為模式識(shí)別時(shí)的多類(lèi)問(wèn)題尋找好的算法和解決訓(xùn)練樣本規(guī)模和訓(xùn)練速度之間的矛盾、解決支持向量樹(shù)木和分類(lèi)速度之間的矛盾。在此基礎(chǔ)上進(jìn)行進(jìn)一步的機(jī)理分析和試驗(yàn)分析，探索和拓寬SVM新的應(yīng)用領(lǐng)域，使其成為更有發(fā)展前途的新技術(shù)。

參考文獻(xiàn)：

[1] Vapnik V N.統(tǒng)計(jì)學(xué)習(xí)理論[ M ].許建華，張學(xué)工，譯.北京：電子工業(yè)出版社，2009.

[2] 吳德會(huì).基于多分類(lèi)支持向量機(jī)的智能輔助質(zhì)量診斷研究[J].系統(tǒng)仿真學(xué)報(bào)，2009，21（6）：1689-1693.