支持向量機(jī)的算法及應(yīng)用綜述

張松蘭

摘要：支持向量機(jī)（SVM）是在統(tǒng)計(jì)學(xué)習(xí)的VC維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小化原理基礎(chǔ)上建立起來的機(jī)器學(xué)習(xí)方法，其訓(xùn)練算法本質(zhì)上是一個(gè)二次規(guī)劃的求解問題。首先簡(jiǎn)述了SVM的基本原理，然后對(duì)SVM算法進(jìn)行了概括，如塊算法、分解算法，序列最小優(yōu)化算法及最小二乘支持向量機(jī)、模糊支持向量機(jī)和粒度支持向量機(jī)等。接著介紹了支持向量機(jī)的應(yīng)用，最后對(duì)該領(lǐng)域存在的問題和發(fā)展趨勢(shì)進(jìn)行了展望。

關(guān)鍵詞：支持向量機(jī)；統(tǒng)計(jì)學(xué)習(xí)理論；訓(xùn)練算法

中圖分類號(hào)：O234 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-7394（2016）02-0014-04

支持向量機(jī)是在統(tǒng)計(jì)學(xué)習(xí)理論的基礎(chǔ)上，以結(jié)構(gòu)風(fēng)險(xiǎn)最小化為原則建立起來的機(jī)器學(xué)習(xí)算法，通過控制參數(shù)自動(dòng)調(diào)節(jié)模型結(jié)構(gòu)，實(shí)現(xiàn)經(jīng)驗(yàn)風(fēng)險(xiǎn)和結(jié)構(gòu)風(fēng)險(xiǎn)最小化。在解決小樣本、高維問題和非線性問題等方面表現(xiàn)出良好的泛化能力和預(yù)測(cè)性能，在人臉檢測(cè)、數(shù)據(jù)挖掘、圖像處理、語音識(shí)別、故障診斷、網(wǎng)頁分類、系統(tǒng)建模與辨識(shí)、模式識(shí)別等諸多領(lǐng)域有著廣泛的應(yīng)用。

1 支持向量機(jī)基本原理

對(duì)于線性可分問題，支持向量機(jī)運(yùn)用優(yōu)化算法實(shí)現(xiàn)最大化分類間隔；而對(duì)于非線性問題，支持向量機(jī)通過適當(dāng)?shù)暮撕瘮?shù)將輸入空間映射到高維空間，實(shí)現(xiàn)高維空間線性可分，將非線性問題轉(zhuǎn)化線性問題，然后在新空間中利用二次型尋優(yōu)算法求取最優(yōu)線性分類面，從而將兩類樣本區(qū)分開來，如圖1所示。圖中空心點(diǎn)和實(shí)心點(diǎn)分別表示兩種不同類型的數(shù)據(jù)，H、H₁、H₂是區(qū)分兩類數(shù)據(jù)的分類面。其中H₁，H₂是劃分兩類數(shù)據(jù)的邊緣分類面，它們之間的距離margin就是兩類之間的分類間隔，而圖中位于分類面H₁，H₂上的空心點(diǎn)和實(shí)心點(diǎn)即為支持向量。支持向量機(jī)實(shí)現(xiàn)非線性映射的目的就是尋求一個(gè)最優(yōu)的分類面使兩類之間的分類間隔最大，同時(shí)在映射的復(fù)雜性和樣本數(shù)據(jù)的學(xué)習(xí)泛化能力方面達(dá)到最佳。

對(duì)于由多個(gè)樣本對(duì)構(gòu)成的數(shù)據(jù)集{x_i，y_i}，X_i∈Rⁿ，Y_i∈{+1，-1}，SVM設(shè)計(jì)的目的是尋求一個(gè)具有最大間隔的超平面g（x）=ω^TX+b=0，將所有訓(xùn)練樣本正確分類，并使分類的誤差最小，因此實(shí)現(xiàn)最優(yōu)分類面變成求解下列問題。

其中，Φ（X_i）是Rⁿ→R^m，m>n是非線性映射方程，實(shí)現(xiàn)樣本數(shù)據(jù)從低維空間映射到高維空間的映射，在特征空間構(gòu)造最優(yōu)分類超平面實(shí)現(xiàn)最大化分類間隔。ε是松馳變量，表示數(shù)據(jù)點(diǎn)的誤差度量；C為可調(diào)的懲罰參數(shù)，表示對(duì)分類錯(cuò)誤的懲罰程度。

由于，L（ω）是二次型函數(shù)有唯一的極小點(diǎn)，利用拉格郎日優(yōu)化方法將最優(yōu)分類面問題轉(zhuǎn)化為其對(duì)偶形式：

2 支持向量機(jī)的基本算法

基本的支持向量機(jī)算法基本思想是在二次規(guī)劃的基礎(chǔ)上不斷迭代尋找支持向量，主要有塊算法、分解算法、序列最小優(yōu)化算法、增量算法等，下面介紹這幾種基本的支持向量機(jī)算法。

2.1 塊算法

塊算法是通過KKT條件逐步迭代刪除矩陣中Lagrange乘子為零的行和列，保留非零的支持向量部分，從圖1中可知對(duì)于給定的整個(gè)樣本數(shù)據(jù)而言，支持向量相對(duì)較少，這樣通過不斷迭代將一個(gè)大型二次規(guī)劃問題分解為小規(guī)模的二次規(guī)劃問題，將樣本空間降為支持向量空間，樣本數(shù)量減小，從而降低了訓(xùn)練過程對(duì)計(jì)算機(jī)的存儲(chǔ)容量要求，加快了訓(xùn)練速度，其訓(xùn)練速度最終受支持向量數(shù)目的影響。

2.2 分解算法

分解算法也是對(duì)大型二次規(guī)劃問題進(jìn)行分解，迭代過程與塊算法相似，但分解算法是將訓(xùn)練樣本分成工作集和非工作集，選取Lagrange乘子分量的一個(gè)子集為工作集，每次迭代時(shí)只對(duì)工作集進(jìn)行尋優(yōu)，而非工作集保持不變，不斷迭代找出最優(yōu)工作集，此算法的收斂速度取決于最優(yōu)工作集的選擇算法。

2.3 序列最小優(yōu)化算法

文獻(xiàn)提出的序列最小優(yōu)化（sequential mini-mal optimization，SMO）算法是在分解算法的基礎(chǔ)上發(fā)展起來的，它將工作集減少為只有2個(gè)樣本。通過兩個(gè)嵌套的循環(huán)尋找待優(yōu)化的兩個(gè)樣本，外層循環(huán)主要尋找工作集的第一個(gè)樣本；然后采用啟發(fā)式規(guī)則選擇第二個(gè)樣本，選擇的原則是使目標(biāo)函數(shù)靠近最優(yōu)點(diǎn)的速度達(dá)到最快；最后用解析的方法快速對(duì)選定的樣本進(jìn)行優(yōu)化。工作集的選擇采用啟發(fā)式選擇策略加快了算法的收斂速度，同時(shí)減小了矩陣存儲(chǔ)空間，適合于稀疏樣本。

2.4 增量算法

增量學(xué)習(xí)在處理新增樣本時(shí)，只對(duì)新樣本有關(guān)的部分進(jìn)行增加修改或刪除操作，拋棄與之無關(guān)的部分。增量訓(xùn)練算法的學(xué)習(xí)過程不是一次離線完成的，而是逐一加入數(shù)據(jù)不斷反復(fù)優(yōu)化的過程。Ralaivola提出的增量式學(xué)習(xí)方法只更新對(duì)學(xué)習(xí)結(jié)果影響最大的Lagrange系數(shù)，以減少計(jì)算復(fù)雜度。文獻(xiàn)提出了一種快速增量學(xué)習(xí)算法，先找出支持向量進(jìn)行支持向量機(jī)的增量學(xué)習(xí)，進(jìn)而求出最優(yōu)分類面，加快學(xué)習(xí)速度。

以上幾種基本算法本質(zhì)上都是將一個(gè)大規(guī)模的二次規(guī)劃問題分解為小的二次規(guī)劃問題，不同的是分解策略和工作集的選取方法，這也是導(dǎo)致算法收斂速度快慢的原因。

3 支持向量機(jī)的改進(jìn)算法

隨著研究的深入基本支持向量機(jī)的算法產(chǎn)生了各自的缺陷，根據(jù)實(shí)際研究問題的需要通過線性化方法、增加函數(shù)項(xiàng)、方法融合等進(jìn)行處理，因而SVM訓(xùn)練算法也不斷發(fā)展和改進(jìn)，減弱缺陷的影響程度。

3.1 最小二乘支持向量機(jī)

在求解大型QP問題時(shí)，基本支持向量機(jī)算法中的塊算法和分解算法會(huì)存在維數(shù)災(zāi)難和求解速度過慢等問題，在支持向量機(jī)的求解過程中約束條件為不等式約束，為簡(jiǎn)化尋優(yōu)過程并保證一定的學(xué)習(xí)速度，用等式約束來代替式（1）中的不等式約束，用最小二乘損失函數(shù)代替不敏感損失函數(shù)來簡(jiǎn)化求解過程，從而得到最小二乘支持向量機(jī)算法。

3.2 模糊支持向量機(jī)

由于實(shí)際樣本檢測(cè)時(shí)存在不同程度的噪聲，需要從樣本數(shù)據(jù)中將非正常數(shù)據(jù)篩以除降低其影響。具體實(shí)施方法為：通過在訓(xùn)練樣本數(shù)據(jù)集中增加每個(gè)樣本的隸屬度項(xiàng)，如對(duì)樣本中的噪聲數(shù)據(jù)和孤立點(diǎn)給予較小的隸屬度，正常的樣本賦予較大的隸屬度，從而對(duì)不同的樣本起到懲罰作用，降低噪聲數(shù)據(jù)對(duì)分類最優(yōu)平面的影響。模糊支持向量機(jī)算法結(jié)合模糊數(shù)學(xué)方法通過在基本支持向量機(jī)算法的基礎(chǔ)上增加隸屬度值對(duì)最優(yōu)平面起到調(diào)節(jié)作用，提高分類精度。但樣本數(shù)據(jù)中如果異常數(shù)據(jù)較多時(shí)，會(huì)影響支持向量機(jī)的泛化學(xué)習(xí)能力，另外由于增加了隸屬度項(xiàng)，使得核函數(shù)計(jì)算復(fù)雜，訓(xùn)練速度降低。

3.3 粒度支持向量機(jī)

粒度支持向量機(jī)在支持向量機(jī)學(xué)習(xí)算法中加入了粒度計(jì)算，通過關(guān)聯(lián)規(guī)則及聚類等方式來劃分粒度，構(gòu)建粒度空間的信息粒，再利用信息粒上的信息得到SVM目標(biāo)函數(shù)。目前，粒度劃分的主要研究有：基于關(guān)聯(lián)規(guī)則的粒度支持向量機(jī)，利用關(guān)聯(lián)規(guī)則挖掘樣本數(shù)據(jù)集的頻繁模式，分割樣本特征空間建立粒度空間，最后在粒度特征空間上進(jìn)行訓(xùn)練學(xué)習(xí)?；诰垲惖牧６戎С窒蛄繖C(jī)是對(duì)樣本空間的數(shù)據(jù)利用聚類方法進(jìn)行粒度劃分，然后從中選擇攜帶有較多信息的粒來學(xué)習(xí)樣本信息，從而實(shí)現(xiàn)分類或回歸問題。

3.4 多類訓(xùn)練算法

隨著研究問題的復(fù)雜化，現(xiàn)實(shí)的分類問題不單純是正反兩類，會(huì)存在多類的現(xiàn)象。對(duì)多分類問題需構(gòu)造多類SVM分類器，主要通過目標(biāo)函數(shù)和分類器來完成。對(duì)應(yīng)的實(shí)現(xiàn)途徑主要有兩種：一種是通過選取合適的目標(biāo)函數(shù)來實(shí)現(xiàn)k類分類支持向量機(jī)。由于實(shí)際問題存在多類，因而選擇的目標(biāo)函數(shù)變量多，求解過程復(fù)雜，一般只用于解決小型問題。另一種實(shí)現(xiàn)方法基于兩分類器的分類思想，將多個(gè)兩分類器進(jìn)行組合，主要方法有一對(duì)多算法、一對(duì)一算法、決策導(dǎo)向無環(huán)圖。一對(duì)多算法對(duì)k個(gè)類的樣本需構(gòu)造k個(gè)分類器，樣本對(duì)應(yīng)的決策函數(shù)最大即為所對(duì)應(yīng)的類。一對(duì)一算法對(duì)k類訓(xùn)練樣本中的任兩類構(gòu)造一個(gè)分類器，兩兩組合構(gòu)造多個(gè)分類器，然后在這些分類器中使用投票法累計(jì)各個(gè)類的投票數(shù)，其中得票數(shù)最多的類即為樣本點(diǎn)所屬的類。當(dāng)類別較大時(shí)組合分類器數(shù)量較多，影響分類預(yù)測(cè)速度。對(duì)此Platt等提出了一個(gè)新的學(xué)習(xí)架構(gòu)：決策導(dǎo)向無環(huán)圖。每個(gè)分類器有兩類，類似于二叉樹，在分類過程中由根部開始經(jīng)各層中間節(jié)點(diǎn)逐步向葉節(jié)點(diǎn)分類，這種分類方法能提高支持向量機(jī)的分類速度和性能。

4 支持向量機(jī)算法的應(yīng)用

4.1 模式識(shí)別

支持向量機(jī)在模式識(shí)別領(lǐng)域的應(yīng)用最廣泛，已成功地解決了諸如手寫體、圖像處理、語音識(shí)別等許多識(shí)別和分類問題。

在手寫字體識(shí)別方面，當(dāng)采用5層神經(jīng)網(wǎng)絡(luò)算法時(shí)，其識(shí)別的錯(cuò)誤率為5.1%；貝爾實(shí)驗(yàn)室最先將SVM應(yīng)用于手寫字體識(shí)別研究，選取三種不同的核函數(shù)時(shí)，得到的誤識(shí)率分別為4.0%，4.1%和4.2%，可看出支持向量機(jī)方法比神經(jīng)網(wǎng)絡(luò)算法具有更好的分類準(zhǔn)確性。柳回春等在SVM的基礎(chǔ)上結(jié)合與RBF神經(jīng)網(wǎng)絡(luò)將其用于UK心理測(cè)試自動(dòng)分析系統(tǒng)的手寫體數(shù)字識(shí)別問題。

在人臉識(shí)別方面，由于人臉圖像存儲(chǔ)和SVM訓(xùn)練需要大量的存儲(chǔ)空間，周志明等人將小波變換與支持向量機(jī)相結(jié)合，由小波變換提取人臉特征，減小特征向量維數(shù)并將其輸入到SVM中，并結(jié)合最近鄰分類器進(jìn)行分類，提高了分類器的魯棒性和分類精度。

在語音識(shí)別方面，由于背景環(huán)境中存在不同程度的噪雜聲，根據(jù)支持向量機(jī)和隱式馬爾可夫模型相結(jié)合的特點(diǎn)，忻棟等建立SVM和隱式馬爾可夫模型兩者相結(jié)合的混合模型，算法比較復(fù)雜，用來解決語音識(shí)別問題。

4.2 網(wǎng)頁分類

在中文網(wǎng)頁分類問題上，賀海軍等在網(wǎng)頁文本的特征表示和二分類問題的基礎(chǔ)上，把二叉決策樹和SVM算法相結(jié)合構(gòu)成多類分類器，實(shí)現(xiàn)網(wǎng)頁文本的分類，取得了較好的分類效果和訓(xùn)練速度。

在網(wǎng)絡(luò)入侵檢測(cè)分類方面，網(wǎng)絡(luò)入侵檢測(cè)其實(shí)也是一種網(wǎng)頁分類。徐文龍等提出了一種基于從特殊到特殊的直推式支持向量機(jī)，從獲取的網(wǎng)絡(luò)數(shù)據(jù)中進(jìn)行歸納式學(xué)習(xí)和標(biāo)記樣本，從中提出特征輸入到TSVM學(xué)習(xí)機(jī)中進(jìn)行學(xué)習(xí)，檢測(cè)其異常的網(wǎng)絡(luò)入侵，提高了測(cè)試樣本的分類準(zhǔn)確度。

4.3 系統(tǒng)建模與系統(tǒng)辨識(shí)

在未知非線性系統(tǒng)建模方面，張浩然等利用對(duì)象的輸入輸出數(shù)據(jù)集，在非線性系統(tǒng)的控制結(jié)構(gòu)設(shè)計(jì)中采用支持向量機(jī)建模來獲取對(duì)象的動(dòng)態(tài)特性，以SVM作為辨識(shí)器在控制器中采用指數(shù)梯度法實(shí)現(xiàn)控制作用。

在非線性系統(tǒng)的辨識(shí)方面，崔萬照等剛將最小二乘方法應(yīng)用于支持向量機(jī)算法中并選擇小波函數(shù)作為支持向量機(jī)的核函數(shù)，構(gòu)造最小二乘小波支持向量機(jī)來解決單輸入單輸出（SISO）非線性系統(tǒng)的辨識(shí)問題，仿真結(jié)果表明此方法能提高辨識(shí)效果，加快系統(tǒng)響應(yīng)時(shí)間。

5 結(jié)論與討論

SVM以統(tǒng)計(jì)學(xué)習(xí)理論為基礎(chǔ)，存在全局優(yōu)化、泛化性能好等優(yōu)點(diǎn)，同時(shí)也存在諸多缺陷，有很多問題需深入研究。

（1）支持向量機(jī)算法的核心是核函數(shù)及其參數(shù)，它們的正確選取對(duì)SVM的預(yù)測(cè)及泛化性能影響很大。對(duì)于具體的研究問題，究竟選擇哪種核函數(shù)并找到最優(yōu)的參數(shù)對(duì)求解問題至關(guān)重要。因此，如何快速準(zhǔn)確地選擇核函數(shù)及對(duì)應(yīng)的參數(shù)來滿足快速性和準(zhǔn)確性要求是迄待解決的問題。

（2）在大規(guī)模及實(shí)時(shí)性要求較高的系統(tǒng)中，SVM算法受制于求解問題的收斂速度和系統(tǒng)規(guī)模的復(fù)雜程度。在非線性系統(tǒng)的SVM訓(xùn)練算法中，尤其要處理大規(guī)模數(shù)據(jù)時(shí)，需要解決樣本規(guī)模和速度間的矛盾，提高訓(xùn)練算法的效率和精度。

（3）如何有效地將二類別分類器有效地?cái)U(kuò)展到多類別問題上，多類SVM的優(yōu)化設(shè)計(jì)也是今后研究的內(nèi)容。

（4）針對(duì)特定問題如何實(shí)現(xiàn)支持向量機(jī)與其他算法的融合，從而順利解決待求問題也是需要研究的方向。

（5）目前的SVM研究側(cè)重于理論研究，真正的實(shí)踐應(yīng)用還有一段距離。

目前，SVM仍然存在很多問題需進(jìn)一步的研究，可將SVM與離散余弦變換、小波包分解、主元分析、獨(dú)立分量分析、聚類、粗糙集理論等方法結(jié)合，提高應(yīng)用效果并不斷探索SVM新的應(yīng)用領(lǐng)域。

責(zé)任編輯 祁秀春