SVM基本原理及其發(fā)展概述

1、精選優(yōu)質(zhì)文檔-傾情為你奉上SVM基本原理及其發(fā)展概述摘要：支持向量機(jī)（Support Vector Machine，SVM）是一種基于統(tǒng)計(jì)學(xué)習(xí)理論的新型機(jī)器學(xué)習(xí)方法，它采用了結(jié)構(gòu)風(fēng)險最小化原則來代替了經(jīng)驗(yàn)風(fēng)險最小化能較好地解決小樣本學(xué)習(xí)的問題；還采用核函數(shù)思想，把非線性空間的問題轉(zhuǎn)換到線性空間，降低了算法的復(fù)雜度。正因?yàn)镾VM有較完備的理論基礎(chǔ)和較好的學(xué)習(xí)性能，在解決有限樣本、非線性及高維模式識別問題中表現(xiàn)出許多特有的優(yōu)勢，成為當(dāng)前機(jī)器學(xué)習(xí)領(lǐng)域的研究熱點(diǎn)問題之一，并在很多領(lǐng)域都得到了成功的應(yīng)用。關(guān)鍵詞：數(shù)據(jù)挖掘；統(tǒng)計(jì)理論；支持向量機(jī)中圖分類號：TP301 文獻(xiàn)標(biāo)識碼：A 文章編號：1統(tǒng)計(jì)學(xué)習(xí)理

2、論統(tǒng)計(jì)學(xué)習(xí)理論是SVM的理論基礎(chǔ)?；跀?shù)據(jù)的機(jī)器學(xué)習(xí)是現(xiàn)代智能技術(shù)中的重要方面，研究從觀測樣本出發(fā)尋找規(guī)律，利用這些規(guī)律對未來數(shù)據(jù)或無法觀測的數(shù)據(jù)進(jìn)行預(yù)測。包括模式識別、神經(jīng)網(wǎng)絡(luò)等在內(nèi)，現(xiàn)有機(jī)器學(xué)習(xí)方法共同的重要理論基礎(chǔ)之一是統(tǒng)計(jì)學(xué)。傳統(tǒng)統(tǒng)計(jì)學(xué)研究的是樣本數(shù)目趨于無窮大時的漸近理論，現(xiàn)有學(xué)習(xí)方法也多是基于此假設(shè)。但在實(shí)際問題中，樣本數(shù)往往是有限的，因此一些理論上很優(yōu)秀的學(xué)習(xí)方法實(shí)際中表現(xiàn)卻可能不盡人意。與傳統(tǒng)統(tǒng)計(jì)學(xué)相比，統(tǒng)計(jì)學(xué)習(xí)理論(Statistical Learning Theory，SLT)是一種專門研究小樣本情況下機(jī)器學(xué)習(xí)規(guī)律的理論。Vapnik Vapnik V N.The natu

3、re of statistical learning theoryM.New York:Spring,1995.等人從六、七十年代開始致力于此方面研究，到九十年代中期，隨著其理論的不斷發(fā)展和成熟，也由于神經(jīng)網(wǎng)絡(luò)等學(xué)習(xí)方法在理論上缺乏實(shí)質(zhì)性進(jìn)展，統(tǒng)計(jì)學(xué)習(xí)理論開始受到越來越廣泛的重視。統(tǒng)計(jì)學(xué)習(xí)理論是建立在一套較堅(jiān)實(shí)的理論基礎(chǔ)之上的，為解決有限樣本學(xué)習(xí)問題提供了一個統(tǒng)一的框架。它能將很多現(xiàn)有方法納入其中，有望幫助解決許多原來難以解決的問題(比如神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)選擇問題、局部極小點(diǎn)問題等)，同時，在這一理論基礎(chǔ)上發(fā)展了一種新的通用學(xué)習(xí)方法支持向量機(jī)(Support Vector Machine，SVM)。

4、一些學(xué)者認(rèn)為，SLT和SVM正在成為繼神經(jīng)網(wǎng)絡(luò)研究之后新的研究熱點(diǎn)，并將有力地推動機(jī)器學(xué)習(xí)理論和技術(shù)的發(fā)展。統(tǒng)計(jì)學(xué)習(xí)理論的一個核心概念就是VC維，它是描述函數(shù)集或?qū)W習(xí)機(jī)器的復(fù)雜性或者說學(xué)習(xí)能力的一個重要指標(biāo)，在此概念基礎(chǔ)上發(fā)展出了一系列關(guān)于統(tǒng)計(jì)學(xué)習(xí)的一致性、收斂速度、推廣性能等的重要結(jié)論。在統(tǒng)計(jì)學(xué)習(xí)理論基礎(chǔ)之上發(fā)展起來的支持向量機(jī)是統(tǒng)計(jì)學(xué)習(xí)理論中最年輕的內(nèi)容，它已表現(xiàn)出很多優(yōu)于己有方法的性能。2支持向量機(jī)2.1介紹及其特點(diǎn)支持向量機(jī)的重要理論基礎(chǔ)是統(tǒng)計(jì)學(xué)習(xí)理論的VC維理論和結(jié)構(gòu)風(fēng)險最小化原理。根據(jù)統(tǒng)計(jì)學(xué)習(xí)理論，學(xué)習(xí)機(jī)器的實(shí)際風(fēng)險由經(jīng)驗(yàn)風(fēng)險值和置信范圍值兩部分組成。傳統(tǒng)的統(tǒng)計(jì)模式識別方法在進(jìn)行機(jī)

5、器學(xué)習(xí)時，強(qiáng)調(diào)經(jīng)驗(yàn)風(fēng)險最小化。而基于經(jīng)驗(yàn)風(fēng)險最小化準(zhǔn)則的學(xué)習(xí)方法只強(qiáng)調(diào)了訓(xùn)練樣本的經(jīng)驗(yàn)風(fēng)險最小誤差，沒有最小化置信范圍值，會產(chǎn)生“過學(xué)習(xí)問題”，其推廣能力較差。SVM根據(jù)有限的樣本信息在模型的復(fù)雜性和學(xué)習(xí)能力之間尋求最佳折衷以期獲得最好的推廣能力，從而使其學(xué)習(xí)機(jī)獲得了更好的推廣性能，這恰恰是統(tǒng)計(jì)學(xué)習(xí)理論最重要的目標(biāo)之一。SVM可以自動尋找對分類有較好區(qū)分能力的支持向量，由此構(gòu)成的分類器可以最大化類與類之間的間隔。支持向量機(jī)主要優(yōu)點(diǎn)包括：（1）它是專門針對有限樣本情況的其目標(biāo)是得到現(xiàn)有信息下的最優(yōu)解，而不僅僅是樣本數(shù)目趨于無窮大時的最優(yōu)值。（2）算法最終轉(zhuǎn)化為一個二次型尋優(yōu)問題。從理論上說得到的

6、將是全局最優(yōu)點(diǎn)，解決了在神經(jīng)網(wǎng)絡(luò)方法中無法避免的局部極值問題。（3）算法將實(shí)際問題通過非線性變換到高維的特征空間，在高維空間中構(gòu)造線性判別函數(shù)以替換原空間中的非線性判別函數(shù)，這樣能保證機(jī)器有較好的推廣能力同時它巧妙地解決了維數(shù)問題，算法復(fù)雜度與樣本維數(shù)無關(guān)。SVM算法有很多成功的應(yīng)用領(lǐng)域，如人臉識別、手寫體識別、指紋識別等。SVM算法在精度上已經(jīng)超過傳統(tǒng)的學(xué)習(xí)算法或與之不相上下，這些應(yīng)用都說明了基于VC維理論和結(jié)構(gòu)風(fēng)險最小化原理而發(fā)展起來的結(jié)構(gòu)化學(xué)習(xí)方法的潛在優(yōu)勢。2.2算法及其發(fā)展2.2.1支持向量機(jī)算法V.Vapnik等人首先提出來的是chunking算法：從訓(xùn)練樣本中任意選擇一個小的子集

7、，求此子集的最優(yōu)解，保留此子集的支持向量，從剩余的樣本中啟發(fā)式地加入新的子集，再求解新子集的最優(yōu)，反復(fù)迭代直至收斂，但chunking算法需求的內(nèi)存空間受所解決問題的支持向量數(shù)目的限制，當(dāng)問題的支持向量數(shù)過大時子問題的求解也很困難。2.2.2支持向量機(jī)的幾個發(fā)展為了進(jìn)一步提高支持向量機(jī)算法的運(yùn)行效率和收斂速度，研究人員對此做出了巨大的努力，提出了很多改進(jìn)辦法，不斷推動支持向量機(jī)研究向前發(fā)展。（1）模糊支持向量機(jī)，引入樣本對類別的隸屬度函數(shù)，這樣每個樣本對于類別的影響是不同的。這種理論的應(yīng)用提高了SVM的抗噪聲的能力，尤其適合在未能完全揭示輸入樣本特性的情況下。（2）最小二乘支持向量機(jī)。這種方法

8、是在1999年提出，經(jīng)過這幾年的發(fā)展，已經(jīng)應(yīng)用要很多相關(guān)的領(lǐng)域。研究的問題已經(jīng)推廣到：對于大規(guī)模數(shù)據(jù)集的處理，處理數(shù)據(jù)的魯棒性，參數(shù)調(diào)節(jié)和選擇問題，訓(xùn)練和仿真等。（3）加權(quán)支持向量機(jī)（有偏樣本的加權(quán)，有偏風(fēng)險加權(quán)）。（4）主動學(xué)習(xí)的支持向量機(jī)。主動學(xué)習(xí)在學(xué)習(xí)過程中可以根據(jù)學(xué)習(xí)進(jìn)程，選擇最有利于分類器性能的樣本來進(jìn)一步訓(xùn)練分類器，特能有效地減少評價樣本的數(shù)量。（5）粗糙集與支持向量機(jī)的結(jié)合。首先利用粗糙集理論對數(shù)據(jù)的屬性進(jìn)行約簡,能在某種程度上減少支持向量機(jī)求解計(jì)算量。（6）基于決策樹的支持向量機(jī)。對于多類問題,采用二岔樹將藥分類的樣本集構(gòu)造出一系列的兩類問題,每個兩類構(gòu)造一個SVM。（7）分級

9、聚類的支持向量機(jī)?；诜旨壘垲惡蜎Q策樹思想構(gòu)建多類svm,使用分級聚類的方法,可以先把n-1個距離較近的類別結(jié)合起來,暫時看作一類,把剩下的一類作為單獨(dú)的一類,用svm分類,分類后的下一步不再考慮這單獨(dú)的一類,而只研究所合并的n-1類,再依次下去。（8）算法上的提高。Vapnik在1995年提出了一種稱為chunking的塊算法,即如果刪除矩陣中對應(yīng)Lagrange乘數(shù)為0的行和列,將不會影響最終結(jié)果。Osuna提出了一種分解算法固定工作樣本集方法：選擇一個固定大小的工作集B求解B上的quadraticproblemQP問題考察所有不滿足KKT條件的樣本啟發(fā)式地選擇一些樣本與集B中對應(yīng)優(yōu)化變量

10、的樣本交換反復(fù)迭代直到所有的樣本都滿足KKT條件每一個QP子問題仍然使用迭代數(shù)值優(yōu)化算法求解Osuna證明每次迭代使目標(biāo)函數(shù)單調(diào)遞增因?yàn)槟繕?biāo)函數(shù)有上界所以經(jīng)過有限次迭代后算法將收斂并得到最優(yōu)解但最優(yōu)解在一般情況下并不唯一。Joachims在1998年將Osuna提出的分解策略推廣到解決大型SVM學(xué)習(xí)的算法。Platt于1998年提出了序貫最小優(yōu)化每次的工作集中只有2個樣本。（9）核函數(shù)的構(gòu)造和參數(shù)的選擇理論研究?；诟鱾€不同的應(yīng)用領(lǐng)域,可以構(gòu)造不同的核函數(shù),能夠或多或少的引入領(lǐng)域知識。現(xiàn)在核函數(shù)廣泛應(yīng)用的類型有：多項(xiàng)式逼近、貝葉斯分類器、徑向機(jī)函數(shù)、多層感知器。參數(shù)的選擇現(xiàn)在利用交叉驗(yàn)證的方法

11、來確認(rèn)。（10）支持向量機(jī)從兩類問題向多類問題的推廣。Weston在1998年提出的多類算法為代表。在經(jīng)典svm理論的基礎(chǔ)上,直接在目標(biāo)函數(shù)上進(jìn)行改進(jìn),重新構(gòu)造多值分類模型,建立k分類支持向量機(jī)。通過sv方法對新模型的目標(biāo)函數(shù)進(jìn)行優(yōu)化,實(shí)現(xiàn)多值分類。一對多(one-against-rest)Vapnik提出的,k類k個分類器,第m個分類器將第m類與其余的類分開,也就是說將第m類重新標(biāo)號為1,其他類標(biāo)號為-1。完成這個過程需要計(jì)算k個二次規(guī)劃,根據(jù)標(biāo)號將每個樣本分開,最后輸出的是兩類分類器輸出為最大的那一類。不足:容易產(chǎn)生屬于多類別的點(diǎn)(多個1)和沒有被分類的點(diǎn)(標(biāo)號均為-1不對,訓(xùn)練樣本數(shù)據(jù)大

12、,訓(xùn)練困難,推廣誤差無界。層(數(shù)分類方法),是對一對一方法的改進(jìn),將k個分類合并為兩個大類,每個大類里面再分成兩個子類,如此下去,直到最基本的k個分類,這樣形成不同的層次,每個層次都用svm來進(jìn)行分類1對r-1法,構(gòu)建k-1個分類器,不存在拒絕分類區(qū)。3基于支持向量機(jī)的數(shù)據(jù)挖掘及其研究現(xiàn)狀3.1支持向量機(jī)在數(shù)據(jù)挖掘中的應(yīng)用現(xiàn)狀統(tǒng)計(jì)學(xué)習(xí)理論和支持向量機(jī)建立了一套較好的有限樣本下機(jī)器學(xué)習(xí)的理論框架和通用方法，有嚴(yán)格的理論基礎(chǔ)，其核心思想就是學(xué)習(xí)機(jī)器的復(fù)雜性要與有限的訓(xùn)練樣本相適應(yīng)，能較好地解決有限樣本、非線性、高維數(shù)和局部極小點(diǎn)等實(shí)際問題，能建立穩(wěn)定的預(yù)測準(zhǔn)確率高的分類器，所以很適合應(yīng)用于分類規(guī)則

13、挖掘。但是任何一種方法要成功應(yīng)用于分類規(guī)則挖掘，都必須解決幾個問題。首先數(shù)據(jù)挖掘的算法必須能處理海量數(shù)據(jù)，即數(shù)十萬、上百萬甚至更多的數(shù)據(jù)量?，F(xiàn)有訓(xùn)練算法一般都基于 SMO或其改進(jìn)算法，已經(jīng)基本解決了這個問題。其次數(shù)據(jù)挖掘在處理海量數(shù)據(jù)的同時還要有較快的運(yùn)算速度，這樣才能有較高的實(shí)用價值。Jianxiong Dong開發(fā)的HeroSVM（單線程版）經(jīng)過特別的優(yōu)化，在Pentium41.7Ghz的CPU上對一百多萬樣本的漢王手寫數(shù)字?jǐn)?shù)據(jù)庫作訓(xùn)練，只需45分鐘即可完成（Windows 2000 Professional，1.5G SDRAM）。這樣訓(xùn)練速度的問題也基本解決。最后是預(yù)測的問題。當(dāng)訓(xùn)練得

14、到的支持向量比較多時（特別是在訓(xùn)練海量數(shù)據(jù)時），預(yù)測的速度會比較慢。C.J.C.Burges提出了一種簡化的支持向量機(jī)（Simplified Support Vector Machine），可以大大壓縮支持向量的數(shù)目，而對預(yù)測準(zhǔn)確率影響很小，從而可以加快預(yù)測速度。由此我們可以說，支持向量機(jī)完全可以成為一種很好的分類規(guī)則挖掘方法。3.2支持向量機(jī)在數(shù)據(jù)挖掘應(yīng)用中存在的問題由于統(tǒng)計(jì)學(xué)習(xí)理論和支持向量機(jī)建立了一套較好的有限樣本下機(jī)器學(xué)習(xí)的理論框架和通用方法，既有嚴(yán)格的理論基礎(chǔ)，又能較好地解決小樣本、非線性、高維數(shù)和局部極小點(diǎn)等實(shí)際問題，因此成為20世紀(jì)90年代末發(fā)展最快的研究方向之一。其核心思想就是學(xué)習(xí)機(jī)器要與有限的訓(xùn)練樣本相適應(yīng)。目前SVM研究中仍需要解決的一些難點(diǎn)包括如下的一些方面：（1）核函數(shù)和參數(shù)的構(gòu)造和選擇缺乏理論指導(dǎo)。核函數(shù)的選擇影響著分類器的性能，如何根據(jù)待解決問題的先驗(yàn)