支持向量機的研究與應用

李卓文 宋金朋

新鄉職業技術學院 河南新鄉 473000

摘要：支持向量機是一種新的機器學習方法，由于其出色的學習性能，該技術已成為當前國際機器學習界的研究熱點。對SVM訓練算法的最新研究成果進行了綜述，著重說明了各種的算法的思路和優缺點?？偨Y了支持向量機理論及其應用的現狀，對支持向量機的未來發展方向進行了展望。

關鍵詞：支持向量機；訓練算法；分類

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；

支持向量機（Support Vector Machine，SVM）是Vapnik等1995年提出的一種基于統計學習理論[1]的模式識別方法。它在解決小樣本、非線性和高維模式識別問題中具有特有的優勢，且在某種程度上克服了維數災難和過度學習等傳統難題，另其具有堅實的理論基礎、簡明的數學模型，使得支持向量機自提出以來受到廣泛的關注，并取得了長足的發展。

1 支持向量機的訓練算法

（1）塊算法與分解算法

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

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

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

（2）序貫最小優化算法

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

（3）模糊支持向量機

模糊支持向量機（Fuzzy SVM，FSVM）算法將模糊邏輯的方法與支持向量機的學習方法相結合，該算法給每個訓練樣本都賦與相應的模糊隸屬度，這樣不同的樣本對決策函數的學習有不同的貢獻，可以降低噪聲對最優超平面的影響。

（4）粒度支持向量機[ 5]

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

（5）多分類支持向量機

SVM起初主要是針對兩類問題的分類，為了滿足現實生活應用中多分類問題，需要構造多類 SVM 分類器，目前多分類支持向量機算法的思路主要有兩種：

（1）在經典 SVM 的基礎上對其目標函數進行優化，構造多分類模型，進而實現多分類問題。這種方法為一次性求解法，由于其計算復雜度比較高，在實際應用中效率低，所以并不常用。

（2）將多分類問題歸結為多個兩分類問題，常用的算法主要有一對多[6-7]、一對一[8-9]、導向無環圖[10]、二叉樹[11]四種。文獻[12]對這四種算法分別進行了詳細的描述，在訓練復雜度、測試復雜度和分類準確率方面作了理論分析，并利用數據對分析結果進行了驗證。分析得出，導向無環圖的分類性能最優，一對一的分類性能次之，二叉樹的分類性能較差，一對多的分類性能最差；在訓練和測試耗時方面，二叉樹耗時最短，導向無環圖次之，一對一和一對多的耗時相對較長。

2 支持向量機的應用及發展方向

支持向量機理論自提出以來，在各種應用領域得到了廣泛應用，并在模式識別領域已經得到成功應用。在模式識別領域，SVM 方法主要應用于手寫數字識別、語音識別、人臉檢測與識別、文本分類等方面。

支持向量機在生物信息領域，如蛋白質的分類和 DNA 分析等，取得了較好結果。此外，支持向量機還應用于時間序列分析、回歸分析、聚類分析、動態圖像的人臉跟蹤、信號處理、語音識別、圖像分類和控制系統等諸多領域。

盡管國內外學者對支持向量機的理論與算法開展了許多有效的研究工作，但是其算法研究中還有很多尚未解決的問題。

（1）如何徹底解決大樣本時訓練算法速度慢、算法復雜、運算量大等缺點；

（2）SVM 自選參數目前尚缺乏結構化方法來實現參數的最優選擇，

（3）訓練樣本中數據含有不確定性以及噪聲時的 SVM 理論性能，即 SVM 理論的魯棒性問題是值得研究的重點課題。

結束語

本文主要介紹了現有的SVM 訓練算法，著重說明了各種的算法的思路和優缺點.當前對SVM的研究方興未艾，訓練算法的研究方向主要是確定不同的優化目標，根據KKT 約束優化條件尋找大規模訓練樣本下的實用算法；應用方向主要是為模式識別時的多類問題尋找好的算法和解決訓練樣本規模和訓練速度之間的矛盾、解決支持向量樹木和分類速度之間的矛盾。在此基礎上進行進一步的機理分析和試驗分析，探索和拓寬SVM新的應用領域，使其成為更有發展前途的新技術。

參考文獻：

[1] Vapnik V N.統計學習理論[ M ].許建華，張學工，譯.北京：電子工業出版社，2009.

[2] 吳德會.基于多分類支持向量機的智能輔助質量診斷研究[J].系統仿真學報，2009，21（6）：1689-1693.