SVM方法在模式識別應用領域中的發展與研究

朱亞輝，黃襄念

（西華大學數學與計算機學院，成都 610039）

SVM方法在模式識別應用領域中的發展與研究

朱亞輝，黃襄念

（西華大學數學與計算機學院，成都 610039）

SVM是一種新型機器學習方法。對SVM訓練算法的最新研究成果進行綜述，并且介紹目前研究的新進展，總結SVM在模式識別中的應用現狀以及對其發展趨勢進行展望。

SVM；模式識別；機器學習；數據挖掘；模式分類

0 引言

SVM方法是學習的泛化能力的體現，SVM借助最優化方法，解決小樣本、高維數、非線性和局部最小點等實際問題上表現非常出色，并有效解決了模式分類、維數災難和過學習等問題。它具有較好的推廣能力、泛化能力和全局最優性能，以及出色學習能力，成功地解決了模式識別中很多問題，并得到了廣泛的應用。學術界普遍認為它是繼神經網絡之后，在大數據時代一個新的研究方向，使機器學習進入了一個新的時期。

1 SVM方法的發展與研究現狀

SVM方法是基于統計學理論VC維理論和結構風險最小原理基礎上的機器學習方法，SVM理論基礎決定了它最終求得的是全局最優值而不是局部極小值，提高對未知樣本的良好泛化能力。其良好的優化性能，普遍受到更多研究人員的重視。目前，在算法改進和理論研究取得了重大突破，現在已成為模式識別領域中研究的熱點。

1.1 SVM方法的原理

近年來，對SVM的研究主要集中在其本身性質的研究和以及加大SVM應用研究的深度和廣度。

1.2 SVM訓練算法

（1）塊算法和分解算法

從最早1995年Cortes和Vapnik提出了塊算法（Chunking Algorithm）[3]，在1997年由Osuan等人提出并應用于人臉檢測的分解算法[4]。Joachims基于分解算法做出了重要改進，提出了Shrinking方法。為了提高運算和收斂速度，1998年，Platt提出了順序最小優化算法[5]。Joachim從工作集角度提出了SVMlight算法[6]，它是Osuan分解算法的一種推廣，實現了基于此算法的軟件包SVMlight。

（2）變形算法

變形算法主要是通過增加函數項、變量或系數等方法使公式變形，產生出各種有某一方面優勢或者一定應用范圍的算法。

Suykens等人提出了最小二乘SVM[7]（Least Squares SVM，LS-SVM），使SVM的訓練等價于一組線性方程組的求解。對支持向量稀疏性進行了改進，提出了回歸問題的稀疏近似策略。在LS-SVM的基礎上，又提出了如動態加權LS-SVM等改進算法。針對二次規劃無約束對偶問題，提出了Huber近似算法[8]、多拉格朗日乘子協同優化算法。

（3）幾何方法

SVM方法的幾何意義主要體現在訓練樣本的結構和空間距離的重定義。文獻[12]提出了一種直觀的幾何方法來選擇大數據的SVM訓練，時間復雜度是線性的訓練集大小為n的特征空間凸包樣本。文獻[13]為SVM分類問題的幾何框架提供了一個直觀地用于理解和幾何優化算法的應用。文獻[14]提出了基于壓縮凸包的SVM分類問題的幾何算法，保持了數據的幾何體形狀，并且易于得到確定其極點的充要條件。文獻[15]提出了一種SK類思路SVM的幾何方法，該類算法迭代過程中，其最優點多在頂點和邊界上，并在第一次迭代就可能達到邊界。

（4）增量算法

增量學習是處理機器學習中與新樣本有關的部分進行增加、修改或刪除等操作過程，增量訓練算法的特點是一次反復優化的過程。

Ahmed.S.N最早提出了SVM增量訓練算法[16]，選擇一小批常規二次規劃算法作為增量，使支持向量和新增樣本進行混合訓練。文獻[17]針對經典SVM難以快速有效地進行增量學習的缺點，提出了基于KKT條件與殼向量的增量學習算法，該算法選擇包含所有支持向量的殼向量，利用KKT條件淘汰新增樣本中無用樣本，減少參與訓練的樣本數目，在新的訓練集中快速訓練SVM進行增量學習。文獻[18]針對支持向量回歸因時空復雜度較高而無法處理大規模數據的問題，提出了一個新的回歸增量學習法。文獻[19]為了解決SVM在增量學習時，由于支持向量選擇不完全，導致增量學習過程無法持久進行的問題，提出了最大似然邊界SVM增量學習算法。

（5）多類分類算法

SVM兩類分類器擴展到多類分類問題上，需要構造多類SVM分類器，其構造方法有多種，其中典型的是組合多個兩類分類器，包括：一對多算法、一對一算法和決策導向無環圖，其次是SVM決策樹方法。

文獻[20]提出了一種改進的基于二叉樹結構的SVM多類分類算法，有效地解決現有SVM多類分類算法的不可分區域問題及提高了泛化能力。文獻[21]提出了一種基于樣本的類劃分方案，采用平衡決策樹的結構，得到一種新的決策樹SVM多類分類算法，有效地減少了樣本訓練時間，提高了多類分類器的識別率。文獻[22]提出了一種基于對SVM的多類分類算法，有效地處理大規模數據時訓練速度上存在的弱勢。

（6）模糊SVM

模糊SVM是如何給訓練樣本確定相應權重，使不同的樣本對決策函數的學習做出不同的貢獻，可以減少對外部的影響。

（7）粒度SVM

粒度SVM主要的研究是內在學習機制，在SVM學習框架下，引入粒與粒的內積運算，建立粒度核函數并將之運用于粒度SVM的學習之中。

文獻[27]通過引入動態層次粒度的方法，設計了動態粒度SVM回歸模型。文獻[28]針對數據規模和分布密度不平衡的數據集，提出了一種基于粒度偏移因子的粒度SVM學習方法，是將原始樣本用Mercer核映射到高維空間，對數據進行有效的粒劃分，重新構造SVM的凸二次優化問題，以得到一個泛化能力更好的分類超平面。文獻[29]提出一種動態粒度SVM學習算法，根據粒的不同分布自動粒劃分，使SVM可在不同層次的粒上訓練，結果具有更好的分類性能。

（8）孿生SVM

孿生SVM是一種二值數據的分類器，求解兩個二次規劃問題的一種快速分類方法，具有很強的數據處理能力。文獻[30]提出了模糊加權孿生支持向量機，通過為每個訓練樣本賦予不同的樣本重要性，以及減少樣本點對非平行超平面的影響。文獻[31]是對文獻[30]的改進，提出了加權光滑CHKS孿生SVM。文獻[32]提出了一種廣泛權重的最小二乘孿生SVM新型模式分類器，該SVM在正、負兩類樣本上廣泛地增加權重，很好地抑制了交叉噪聲樣本對數據分類的影響。文獻[33]提出了基于孿生SVM的特征選擇與分類算法研究，從流形學習和聚類技術兩方面對孿生SVM進行改進，求解兩個SVM的二次規劃問題來獲得分類模型，從而縮短了訓練時間。

（9）排序SVM

排序學習是當前機器學習研究的熱點，現有排序學習算法把訓練樣本廣泛應用于回歸和分類的學習。文獻[34]提出了一種基于有監督學習的融合多個與查詢相關排序子模型的方法，使用子排序模型的輸出進行向量化表示，將多個查詢相關的排序模型轉化為特征數據，實現多排序模型的集成。文獻[35]提出了一種基于距離排序的快速SVM分類算法，計算兩類樣本點的樣本中心距離，選擇比例的小距離樣本作為邊界樣本。文獻[36]將視覺目標跟蹤問題視為一個排序學習問題，利用排序SVM進行目標跟蹤，提出了兩種新的目標跟蹤算法，并且應用于日益受到重視的紅外視頻下的目標跟蹤問題，實現對紅外視頻目標的魯棒性跟蹤。

2 SVM方法在模式識別中的應用

SVM方法由于其在理論上具有全局最優、良好的推廣能力，在很多問題上有其他統計學習技術難以比擬的優越性，近幾年，許多關于SVM方法的改進與應用的研究，對國內外學術界產生了巨大影響。

隨著對SVM研究的不斷深入，并且SVM方法有著突出的優勢，它能夠保證找到極值解，即全局最優解而非局部最小值，這也就決定了SVM方法對未知樣本有較好的泛化能力。正由于這些優點，SVM的一些模型和方法在各種應用領域表現出較好的推廣能力，得到了廣泛的應用，在模式識別領域的應用最為普遍，如人臉檢測與人臉識別、手寫數字識別、文本分類、說話人語音識別、圖像識別、圖像分類與檢索等，已成功解決了許多模式識別問題。

3 SVM方法的發展趨勢與展望

SVM理論研究與實際應用研究之間還存在較大差距，許多問題的研究需要更一步的擴展和學習，需要不斷深入統計學理論的研究，加快SVM算法發展。目前，下述幾個方面的問題值得進行深入研究：

（1）如何擴展SVM算法本身推廣性能的核函數及其參數，選擇簡單、高效、實用的核參數將是未來研究的關鍵。

（2）如何提高在SVM應用中求解問題的速度和規模。線性SVM結合自身特點，將能夠設計出更好的訓練算法，處理大規模數據的快速算法，將是今后重點關注的問題。

（3）如何有效地將二類別分類器擴展到多類別問題上，仍是今后研究的重點。還將擴大對回歸問題、對聚類和時間序列分析問題的研究。

（4）如何提高特征提取的質量，獲取好的分類基礎，完善SVM在實際應用中的性能。不斷提高SVM訓練速度，構造高效的訓練算法，加大對SVM理論與具體算法實現的研究。

[1] 崔和，龍玉峰.支持向量機學習算法的研究現狀與展望[J].信息與電子工程，2008，09（1）：328～331

[2] 丁世飛，齊丙娟，譚紅艷.支持向量機理論與算法研究綜述[J].電子科技大學學報，2011，40（1）：3～10

[3] Baser B，Guyton I，Vapnik V.A Training Algorithm for Optimal Margin Classifiers[C].M Proceedings of the 5th Annual ACMWorkshop on Computational Learning Theory.New York:ACM Press，1992：144～152

[4] Osuna E，Frenud R，Girosi F.An Improved Training Algorithm for Support Vector Machines[C].M Proceedings of IEEEWorkshop on Neural Networks for Signal Processing.New York，USA，1997：276～285

[5] Platt J.Fast Training of Support Vector Machines Using SequentialMinimal Optimization[M].MA.J.Smola，B.Scholkopf，C.Burges，eds.Advances in Kernel Methods:Support Vector Machines，Cambridge，MA:MIT Press，1999：185～208

[6] Joachim T.Making Large-Scale SVM Learning Practical[A].Burges C，Scholkopf B.Advances in KernelMethods:Support Vector Learning[C].Cambridge，MA:MIT Press，1998：169～184

[7] Suykens JAK，Vandewalle J.Least Squares Support Vector Machine Classifiers[J].Neural Processing Letters，1999，9（3）：293～300

[8] 周水生，詹海生，周利華.訓練支持向量機的Huber近似算法[J].計算機學報，2005，28（10）:1664～1670

[9] Keerthi SS，Shevade SK，Bhattacharyya C，etal.A Fast Iterative Nearest Point Algorithm for Support Vector Machine Classifier Design[J].IEEE Transactions on Neural Networks，2000，11（1）:124～136

[10] Scholkopf B，Smola A，Williamson R C，et al.New Support Vector Algorithms[J].Neural Computation，2000，12（5）:1207～1245

[11] Chang Chih-Chung，Lin Chih-Jen.Training V–Support Vector Classifiers:Theory and Algorithms[J].Neural Computation，2001，13（9）:2119-2147.

[12] Zhi-Qiang Zeng.A Geometric Approach to Train SVM on Very Large Data Sets[C].Intelligent System and Knowledge Engineering，2008.ISKE 2008.3rd International Conference on Xiamen，2008，17～19（8）：991～996

[13] Mavroforakis，M.E.A Geometric Approach to Support Vector Machine（SVM）Classification[J].IEEE Computational Intelligence Society IEEE Computational Intelligence Society，2006，08（5）：671～682

[14] 彭新俊，王翼飛.基于CCH的SVM幾何算法及其應用[J].應用數學與力學，2009，15（01）:90～100

[15] 常振華，陳伯成，李英杰，劉文煌，閆學為.SVM的幾何方法——SK類思路的研究[J].計算機工程與應用，2011，11（03）:149～153

[16] Liefeng Bo，LingWang，Licheng Jiao，Training Hard Margin Support Vector Machine Using Greedy StageWise A lgorithm，Lecture Notes in Computer Science（PAK DD2005），2005，3518：632～638，2005

[17] 文波，單甘霖，段修生.基于KKT條件與殼向量的增量學習算法研究[J].計算機科學，2013，40（3）:255～258

[18] 張一凡，馮愛民，張正林.支持向量回歸增量學習[J].計算機科學，2014，41（6）:166～170

[19] 曹健，孫世宇，段修生，張澤建.基于KKT條件的SVM增量學習算法[J].火力與指揮控制，2014，15（7）:139～143

[20] 劉健，劉忠，熊鷹.改進的二叉樹支持向量機多類分類算法研究[J].計算機工程與應用，2010，33（11）:117～120

[21] 刁智華，趙春江，郭新宇，陸聲鏈.一種新的基于平衡決策樹的SVM多類分類算法[J].控制與決策，2011，26（01）:149～152

[22] 聶盼盼，臧洌，劉雷雷.基于對支持向量機的多類分類算法在入侵檢測中的應用[J].計算機應用，2013，33（2）:426～429

[23] 丁勝鋒，孫勁光.基于混合模糊隸屬度的模糊雙支持向量機研究[J].計算機應用研究，2012，10（10）:432～435

[24] 徐國浪，魏延.基于多核函數的模糊支持向量機學習算法[J].重慶師范大學學報，2012，29（6）:50`53

[25] 李凱，盧霄霞.種基于粗糙間隔的模糊支持向量機[J].電子學報，2013，41（6）:1183～1187

[26] 曹建芳，焦莉娟.基于模糊支持向量機的圖像分類方法[J].計算機與數字工程，2013，41（4）:638～641

[27] 郭虎升，王文劍.動態粒度支持向量回歸機[J].軟件學報，2013，15（11）:2535～2547

[28] 郭虎升，王文劍.基于粒度偏移因子的支持向量機學習方法[J].計算機研究與發展，2013，15（11）:2315～2324

[29]程鳳偉，王文劍，郭虎升.動態粒度SVM學習算法[J].模式識別與人工智能，2014，15（4）:372～377

[30] 李凱，李娜，盧霄霞.一種模糊加權的孿生支持向量機算法[J].計算機工程與應用，2011，14（11）:162～165

[31] 丁世飛，黃華娟，史忠植.加權光滑CHKS孿生支持向量機[J].軟件學報，2013，15（11）:2548～2557

[32] 儲茂祥，王安娜，鞏榮芬.一種改進的最小二乘孿生支持向量機分類算法[J].電子學報，2014，26（05）：998～1003

[33] 封瑞.基于孿生支持向量機的特征選擇與分類算法研究[D].西安電子科技大學，2013，10（1）：1～29

[34] 王揚，黃亞樓，謝茂強，劉杰，盧敏，廖振.多查詢相關的排序支持向量機融合算法[J].計算機研究與發展，2011，48（4）:558～566

[35] 胡志軍，王鴻斌，張惠斌.基于距離排序的快速支持向量機分類算法[J].計算機應用與軟件，2013，30（4）:593～597

[36] 劉鍇.基于排序支持向量機的目標跟蹤算法研究[D]，廈門大學，2014，01（4）:5～19

Development and Research on the SVM Methods in the Field of Pattern Recognition App lications

ZHU Ya-hui，HUANG Xiang-nian
（School ofMathematics and Computer Engineering，Xihua University，Chengdu 610039）

Support Vector Machines is a new typemachine learningmethod in recent years.Reviews the latest research results on the training algorithms of SVM，and introduces new progress of the present study，summarizes the SVM application status in pattern recognition aswell as the prospects for its development trend.

SVM;PatternRecognition;Machine Learning;Data Mining;Pattern Classification

1007-1423（2015）06-0020-05

10.3969/j.issn.1007-1423.2015.06.005

朱亞輝（1989-），男，河南商丘人，碩士，研究方向為圖像處理與模式識別

黃襄念（1965-），男，四川成都人，教授，博士，研究方向為圖像處理與模式識別、體感交互技術與虛擬現實

2014-09-23

2015-01-28