SVM方法在模式識別應(yīng)用領(lǐng)域中的發(fā)展與研究

朱亞輝，黃襄念

（西華大學(xué)數(shù)學(xué)與計算機學(xué)院，成都 610039）

SVM方法在模式識別應(yīng)用領(lǐng)域中的發(fā)展與研究

朱亞輝，黃襄念

（西華大學(xué)數(shù)學(xué)與計算機學(xué)院，成都 610039）

SVM是一種新型機器學(xué)習(xí)方法。對SVM訓(xùn)練算法的最新研究成果進行綜述，并且介紹目前研究的新進展，總結(jié)SVM在模式識別中的應(yīng)用現(xiàn)狀以及對其發(fā)展趨勢進行展望。

SVM；模式識別；機器學(xué)習(xí)；數(shù)據(jù)挖掘；模式分類

0 引言

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

1 SVM方法的發(fā)展與研究現(xiàn)狀

SVM方法是基于統(tǒng)計學(xué)理論VC維理論和結(jié)構(gòu)風(fēng)險最小原理基礎(chǔ)上的機器學(xué)習(xí)方法，SVM理論基礎(chǔ)決定了它最終求得的是全局最優(yōu)值而不是局部極小值，提高對未知樣本的良好泛化能力。其良好的優(yōu)化性能，普遍受到更多研究人員的重視。目前，在算法改進和理論研究取得了重大突破，現(xiàn)在已成為模式識別領(lǐng)域中研究的熱點。

1.1 SVM方法的原理

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

1.2 SVM訓(xùn)練算法

（1）塊算法和分解算法

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

（2）變形算法

變形算法主要是通過增加函數(shù)項、變量或系數(shù)等方法使公式變形，產(chǎn)生出各種有某一方面優(yōu)勢或者一定應(yīng)用范圍的算法。

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

（3）幾何方法

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

（4）增量算法

增量學(xué)習(xí)是處理機器學(xué)習(xí)中與新樣本有關(guān)的部分進行增加、修改或刪除等操作過程，增量訓(xùn)練算法的特點是一次反復(fù)優(yōu)化的過程。

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

（5）多類分類算法

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

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

（6）模糊SVM

模糊SVM是如何給訓(xùn)練樣本確定相應(yīng)權(quán)重，使不同的樣本對決策函數(shù)的學(xué)習(xí)做出不同的貢獻，可以減少對外部的影響。

（7）粒度SVM

粒度SVM主要的研究是內(nèi)在學(xué)習(xí)機制，在SVM學(xué)習(xí)框架下，引入粒與粒的內(nèi)積運算，建立粒度核函數(shù)并將之運用于粒度SVM的學(xué)習(xí)之中。

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

（8）孿生SVM

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

（9）排序SVM

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

2 SVM方法在模式識別中的應(yīng)用

SVM方法由于其在理論上具有全局最優(yōu)、良好的推廣能力，在很多問題上有其他統(tǒng)計學(xué)習(xí)技術(shù)難以比擬的優(yōu)越性，近幾年，許多關(guān)于SVM方法的改進與應(yīng)用的研究，對國內(nèi)外學(xué)術(shù)界產(chǎn)生了巨大影響。

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

3 SVM方法的發(fā)展趨勢與展望

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

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

（2）如何提高在SVM應(yīng)用中求解問題的速度和規(guī)模。線性SVM結(jié)合自身特點，將能夠設(shè)計出更好的訓(xùn)練算法，處理大規(guī)模數(shù)據(jù)的快速算法，將是今后重點關(guān)注的問題。

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

（4）如何提高特征提取的質(zhì)量，獲取好的分類基礎(chǔ)，完善SVM在實際應(yīng)用中的性能。不斷提高SVM訓(xùn)練速度，構(gòu)造高效的訓(xùn)練算法，加大對SVM理論與具體算法實現(xiàn)的研究。

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

[2] 丁世飛，齊丙娟，譚紅艷.支持向量機理論與算法研究綜述[J].電子科技大學(xué)學(xué)報，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，F(xiàn)renud 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] 周水生，詹海生，周利華.訓(xùn)練支持向量機的Huber近似算法[J].計算機學(xué)報，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幾何算法及其應(yīng)用[J].應(yīng)用數(shù)學(xué)與力學(xué)，2009，15（01）:90～100

[15] 常振華，陳伯成，李英杰，劉文煌，閆學(xué)為.SVM的幾何方法——SK類思路的研究[J].計算機工程與應(yīng)用，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條件與殼向量的增量學(xué)習(xí)算法研究[J].計算機科學(xué)，2013，40（3）:255～258

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[36] 劉鍇.基于排序支持向量機的目標(biāo)跟蹤算法研究[D]，廈門大學(xué)，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-），男，四川成都人，教授，博士，研究方向為圖像處理與模式識別、體感交互技術(shù)與虛擬現(xiàn)實

2014-09-23

2015-01-28