支持向量機的算法及應用綜述

張松蘭

摘要：支持向量機（SVM）是在統計學習的VC維理論和結構風險最小化原理基礎上建立起來的機器學習方法，其訓練算法本質上是一個二次規劃的求解問題。首先簡述了SVM的基本原理，然后對SVM算法進行了概括，如塊算法、分解算法，序列最小優化算法及最小二乘支持向量機、模糊支持向量機和粒度支持向量機等。接著介紹了支持向量機的應用，最后對該領域存在的問題和發展趨勢進行了展望。

關鍵詞：支持向量機；統計學習理論；訓練算法

中圖分類號：O234 文獻標識碼：A 文章編號：2095-7394（2016）02-0014-04

支持向量機是在統計學習理論的基礎上，以結構風險最小化為原則建立起來的機器學習算法，通過控制參數自動調節模型結構，實現經驗風險和結構風險最小化。在解決小樣本、高維問題和非線性問題等方面表現出良好的泛化能力和預測性能，在人臉檢測、數據挖掘、圖像處理、語音識別、故障診斷、網頁分類、系統建模與辨識、模式識別等諸多領域有著廣泛的應用。

1 支持向量機基本原理

對于線性可分問題，支持向量機運用優化算法實現最大化分類間隔；而對于非線性問題，支持向量機通過適當的核函數將輸入空間映射到高維空間，實現高維空間線性可分，將非線性問題轉化線性問題，然后在新空間中利用二次型尋優算法求取最優線性分類面，從而將兩類樣本區分開來，如圖1所示。圖中空心點和實心點分別表示兩種不同類型的數據，H、H₁、H₂是區分兩類數據的分類面。其中H₁，H₂是劃分兩類數據的邊緣分類面，它們之間的距離margin就是兩類之間的分類間隔，而圖中位于分類面H₁，H₂上的空心點和實心點即為支持向量。支持向量機實現非線性映射的目的就是尋求一個最優的分類面使兩類之間的分類間隔最大，同時在映射的復雜性和樣本數據的學習泛化能力方面達到最佳。

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

其中，Φ（X_i）是Rⁿ→R^m，m>n是非線性映射方程，實現樣本數據從低維空間映射到高維空間的映射，在特征空間構造最優分類超平面實現最大化分類間隔。ε是松馳變量，表示數據點的誤差度量；C為可調的懲罰參數，表示對分類錯誤的懲罰程度。

由于，L（ω）是二次型函數有唯一的極小點，利用拉格郎日優化方法將最優分類面問題轉化為其對偶形式：

2 支持向量機的基本算法

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

2.1 塊算法

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

2.2 分解算法

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

2.3 序列最小優化算法

文獻提出的序列最小優化（sequential mini-mal optimization，SMO）算法是在分解算法的基礎上發展起來的，它將工作集減少為只有2個樣本。通過兩個嵌套的循環尋找待優化的兩個樣本，外層循環主要尋找工作集的第一個樣本；然后采用啟發式規則選擇第二個樣本，選擇的原則是使目標函數靠近最優點的速度達到最快；最后用解析的方法快速對選定的樣本進行優化。工作集的選擇采用啟發式選擇策略加快了算法的收斂速度，同時減小了矩陣存儲空間，適合于稀疏樣本。

2.4 增量算法

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

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

3 支持向量機的改進算法

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

3.1 最小二乘支持向量機

在求解大型QP問題時，基本支持向量機算法中的塊算法和分解算法會存在維數災難和求解速度過慢等問題，在支持向量機的求解過程中約束條件為不等式約束，為簡化尋優過程并保證一定的學習速度，用等式約束來代替式（1）中的不等式約束，用最小二乘損失函數代替不敏感損失函數來簡化求解過程，從而得到最小二乘支持向量機算法。

3.2 模糊支持向量機

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

3.3 粒度支持向量機

粒度支持向量機在支持向量機學習算法中加入了粒度計算，通過關聯規則及聚類等方式來劃分粒度，構建粒度空間的信息粒，再利用信息粒上的信息得到SVM目標函數。目前，粒度劃分的主要研究有：基于關聯規則的粒度支持向量機，利用關聯規則挖掘樣本數據集的頻繁模式，分割樣本特征空間建立粒度空間，最后在粒度特征空間上進行訓練學習。基于聚類的粒度支持向量機是對樣本空間的數據利用聚類方法進行粒度劃分，然后從中選擇攜帶有較多信息的粒來學習樣本信息，從而實現分類或回歸問題。

3.4 多類訓練算法

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

4 支持向量機算法的應用

4.1 模式識別

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

在手寫字體識別方面，當采用5層神經網絡算法時，其識別的錯誤率為5.1%；貝爾實驗室最先將SVM應用于手寫字體識別研究，選取三種不同的核函數時，得到的誤識率分別為4.0%，4.1%和4.2%，可看出支持向量機方法比神經網絡算法具有更好的分類準確性。柳回春等在SVM的基礎上結合與RBF神經網絡將其用于UK心理測試自動分析系統的手寫體數字識別問題。

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

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

4.2 網頁分類

在中文網頁分類問題上，賀海軍等在網頁文本的特征表示和二分類問題的基礎上，把二叉決策樹和SVM算法相結合構成多類分類器，實現網頁文本的分類，取得了較好的分類效果和訓練速度。

在網絡入侵檢測分類方面，網絡入侵檢測其實也是一種網頁分類。徐文龍等提出了一種基于從特殊到特殊的直推式支持向量機，從獲取的網絡數據中進行歸納式學習和標記樣本，從中提出特征輸入到TSVM學習機中進行學習，檢測其異常的網絡入侵，提高了測試樣本的分類準確度。

4.3 系統建模與系統辨識

在未知非線性系統建模方面，張浩然等利用對象的輸入輸出數據集，在非線性系統的控制結構設計中采用支持向量機建模來獲取對象的動態特性，以SVM作為辨識器在控制器中采用指數梯度法實現控制作用。

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

5 結論與討論

SVM以統計學習理論為基礎，存在全局優化、泛化性能好等優點，同時也存在諸多缺陷，有很多問題需深入研究。

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

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

（3）如何有效地將二類別分類器有效地擴展到多類別問題上，多類SVM的優化設計也是今后研究的內容。

（4）針對特定問題如何實現支持向量機與其他算法的融合，從而順利解決待求問題也是需要研究的方向。

（5）目前的SVM研究側重于理論研究，真正的實踐應用還有一段距離。

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

責任編輯 祁秀春