支持向量機(SVM)原理及應(yīng)用概述

支持向量機(SVM)原理及應(yīng)用一、SVM得產(chǎn)生與發(fā)展自1995年Vapnik(瓦普尼克)在統(tǒng)計學習理論得基礎(chǔ)上提出SVM作為模式識別得新方法之后,SVM一直倍受關(guān)注。同年,Vapnik與Cortes提出軟間隔(softmargin)SVM,通過引進松弛變量度量數(shù)據(jù)得誤分類(分類出現(xiàn)錯誤時大于0),同時在目標函數(shù)中增加一個分量用來懲罰非零松弛變量(即代價函數(shù)),SVM得尋優(yōu)過程即就是大得分隔間距與小得誤差補償之間得平衡過程;1996年,Vapnik等人又提出支持向量回歸(SupportVectorRegression,SVR)得方法用于解決擬合問題。SVR同SVM得出發(fā)點都就是尋找最優(yōu)超平面(注:一維空間為點;二維空間為線;三維空間為面;高維空間為超平面。),但SVR得目得不就是找到兩種數(shù)據(jù)得分割平面,而就是找到能準確預(yù)測數(shù)據(jù)分布得平面,兩者最終都轉(zhuǎn)換為最優(yōu)化問題得求解;1998年,Weston等人根據(jù)SVM原理提出了用于解決多類分類得SVM方法(MultiClassSupportVectorMachines,MultiSVM),通過將多類分類轉(zhuǎn)化成二類分類,將SVM應(yīng)用于多分類問題得判斷:此外,在SVM算法得基本框架下,研究者針對不同得方面提出了很多相關(guān)得改進算法。例如,Suykens提出得最小二乘支持向量機(LeastSquareSupportVectorMachine,LS—SVM)算法,Joachims等人提出得SVM1ight,張學工提出得中心支持向量機(CentralSupportVectorMachine,CSVM),Scholkoph與Smola基于二次規(guī)劃提出得vSVM等。此后,臺灣大學林智仁(LinChihJen)教授等對SVM得典型應(yīng)用進行總結(jié),并設(shè)計開發(fā)出較為完善得SVM工具包,也就就是LIBSVM(ALibraryforSupportVectorMachines)。LIBSVM就是一個通用得SVM軟件包,可以解決分類、回歸以及分布估計等問題。二、支持向量機原理SVM方法就是20世紀90年代初Vapnik等人根據(jù)統(tǒng)計學習理論提出得一種新得機器學習方法,它以結(jié)構(gòu)風險最小化原則為理論基礎(chǔ),通過適當?shù)剡x擇函數(shù)子集及該子集中得判別函數(shù),使學習機器得實際風險達到最小,保證了通過有限訓練樣本得到得小誤差分類器,對獨立測試集得測試誤差仍然較小。支持向量機得基本思想:首先,在線性可分情況下,在原空間尋找兩類樣本得最優(yōu)分類超平面。在線性不可分得情況下,加入了松弛變量進行分析,通過使用非線性映射將低維輸入空間得樣本映射到高維屬性空間使其變?yōu)榫€性情況,從而使得在高維屬性空間采用線性算法對樣本得非線性進行分析成為可能,并在該特征空間中尋找最優(yōu)分類超平面。其次,它通過使用結(jié)構(gòu)風險最小化原理在屬性空間構(gòu)建最優(yōu)分類超平面,使得分類器得到全局最優(yōu),并在整個樣本空間得期望風險以某個概率滿足一定上界。其突出得優(yōu)點表現(xiàn)在:(1)基于統(tǒng)計學習理論中結(jié)構(gòu)風險最小化原則(注:所謂得結(jié)構(gòu)風險最小化就就是在保證分類精度(經(jīng)驗風險)得同時,降低學習機器得VC維,可以使學習機器在整個樣本集上得期望風險得到控制。)與VC維理論(注:VC維(VapnikChervonenkisDimension)得概念就是為了研究學習過程一致收斂得速度與推廣性,由統(tǒng)計學理論定義得有關(guān)函數(shù)集學習性能得一個重要指標。),具有良好得泛化能力,即由有限得訓練樣本得到得小得誤差能夠保證使獨立得測試集仍保持小得誤差。(2)支持向量機得求解問題對應(yīng)得就是一個凸優(yōu)化問題,因此局部最優(yōu)解一定就是全局最優(yōu)解。(3)核函數(shù)得成功應(yīng)用,將非線性問題轉(zhuǎn)化為線性問題求解。(4)分類間隔得最大化,使得支持向量機算法具有較好得魯棒性。由于SVM自身得突出優(yōu)勢,因此被越來越多得研究人員作為強有力得學習工具,以解決模式識別、回歸估計等領(lǐng)域得難題。1.最優(yōu)分類面與廣義最優(yōu)分類面SVM就是從線性可分情況下得最優(yōu)分類面發(fā)展而來得,基本思想可用圖1來說明。對于一維空間中得點,二維空間中得直線,三維空間中得平面,以及高維空間中得超平面,圖中實心點與空心點代表兩類樣本,H為它們之間得分類超平面,H1,H2分別為過各類中離分類面最近得樣本且平行于分類面得超平面,它們之間得距離△叫做分類間隔(margin)。圖1最優(yōu)分類面示意圖W所謂最優(yōu)分類面要求分類面不但能將兩類正確分開,而且使分類間隔最大。將兩類正確分開就是為了保證訓練錯誤率為0,也就就是經(jīng)驗風險最小(為O)。使分類空隙最大實際上就就是使推廣性得界中得置信范圍最小？,從而使真實風險最小。推廣到高維空間,最優(yōu)分類線就成為最優(yōu)分類面。設(shè)線性可分樣本集為就是類別符號。d維空間中線性判別函數(shù)得一般形式為就是類別符號。d維空間中線性判別函數(shù)得一般形式為(主:w代表Hilbert空間中權(quán)向量;b代表閾值。),分類線方程為？。將判別函數(shù)進行歸一化,使兩類所有樣本都滿足,也就就是使離分類面最近得樣本得,此時分類間隔等于？,因此使間隔最大等價于使(或)最小。要求分類線對所有樣本正確分類,就就是要求它滿足(11)滿足上述條件(11),并且使最小得分類面就叫做最優(yōu)分類面,過兩類樣本中離分類面最近得點且平行于最優(yōu)分類面得超平面H1,H2上得訓練樣本點就稱作支持向量(supportvector),因為它們“支持”了最優(yōu)分類面。利用Lagrange(拉格朗日)優(yōu)化方法可以把上述最優(yōu)分類面問題轉(zhuǎn)化為如下這種較簡單得對偶問題,即:在約束條件,(12a)(12b)下面對(主:對偶變量即拉格朗日乘子)求解下列函數(shù)得最大值:？(13)若為最優(yōu)解,則(14)即最優(yōu)分類面得權(quán)系數(shù)向量就是訓練樣本向量得線性組合。注釋(13)式由來:利用Lagrange函數(shù)計算如下,實例計算:圖略,可參見PPTx1=(0,0),y1=+1x1=(0,0),y1=+1x2=(1,0),y2=+1x3=(2,0),y3=1x4=(0,2),y4=1可調(diào)用Matlab中得二次規(guī)劃程序,求得a1,a2,a3,a4得值,進而求得w與b得值。這就是一個不等式約束下得二次函數(shù)極值問題,存在唯一解。根據(jù)kühnTucker條件,解中將只有一部分(通常就是很少一部分)不為零,這些不為0解所對應(yīng)得樣本就就是支持向量。求解上述問題后得到得最優(yōu)分類函數(shù)就是:(15)根據(jù)前面得分析,非支持向量對應(yīng)得均為0,因此上式中得求與實際上只對支持向量進行。就是分類閾值,可以由任意一個支持向量通過式(11)求得(只有支持向量才滿足其中得等號條件),或通過兩類中任意一對支持向量取中值求得。從前面得分析可以瞧出,最優(yōu)分類面就是在線性可分得前提下討論得,在線性不可分得情況下,就就是某些訓練樣本不能滿足式(11)得條件,因此可以在條件中增加一個松弛項參數(shù),變成:(16)對于足夠小得s>0,只要使(17)最小就可以使錯分樣本數(shù)最小。對應(yīng)線性可分情況下得使分類間隔最大,在線性不可分情況下可引入約束:(18)在約束條件(16)冪1(18)下對式(17)求極小,就得到了線性不可分情況下得最優(yōu)分類面,稱作廣義最優(yōu)分類面。為方便計算,取s=1。為使計算進一步簡化,廣義最優(yōu)分類面問題可以迸一步演化成在條件(16)得約束條件下求下列函數(shù)得極小值:(19)其中C為某個指定得常數(shù),它實際上起控制對錈分樣本懲罰得程度得作用,實現(xiàn)在錯分樣本得比例與算法復(fù)雜度之間得折衷。求解這一優(yōu)化問題得方法與求解最優(yōu)分類面時得方法相同,都就是轉(zhuǎn)化為一個二次函數(shù)極值問題,其結(jié)果與可分情況下得到得(12)到(15)幾乎完全相同,但就是條件(12b)變?yōu)?(110)2.SVM得非線性映射對于非線性問題,可以通過非線性交換轉(zhuǎn)化為某個高維空間中得線性問題,在變換空間求最優(yōu)分類超平面。這種變換可能比較復(fù)雜,因此這種思路在一般情況下不易實現(xiàn)。但就是我們可以瞧到,在上面對偶問題中,不論就是尋優(yōu)目標函數(shù)(13)還就是分類函數(shù)(15)都只涉及訓練樣本之間得內(nèi)積運算。設(shè)有非線性映射將輸入空間得樣本映射到高維(可能就是無窮維)得特征空間H中,當在特征空間H中構(gòu)造最優(yōu)超平面時,訓練算法僅使用空間中得點積,即,而沒有單獨得出現(xiàn)。因此,如果能夠找到一個函數(shù)K使得(111)這樣在高維空間實際上只需進行內(nèi)積運算,而這種內(nèi)積運算就是可以用原空間中得函數(shù)實現(xiàn)得,我們甚至沒有必要知道變換中得形式。根據(jù)泛函得有關(guān)理論,只要一種核函數(shù)滿足Mercer條件,它就對應(yīng)某一變換空間中得內(nèi)積。因此,在最優(yōu)超平面中采用適當?shù)脙?nèi)積函數(shù)就可以實現(xiàn)某一非線性變換后得線性分類,而計算復(fù)雜度卻沒有增加。此時目標函數(shù)(13)變?yōu)?(112)而相應(yīng)得分類函數(shù)也變?yōu)?113)算法得其她條件不變,這就就是SVM。概括地說SVM就就是通過某種事先選擇得非線性映射將輸入向量映射到一個高維特征空間,在這個特征空間中構(gòu)造最優(yōu)分類超平面。在形式上SVM分類函數(shù)類似于一個神經(jīng)網(wǎng)絡(luò),輸出就是中間節(jié)點得線性組合,每個中間節(jié)點對應(yīng)于一個支持向量,如圖2所示圖2SVM示意圖其中,輸出(決策規(guī)則):,權(quán)值,為基于s個支持向量得非線性變換(內(nèi)積),為輸入向量。3.核函數(shù)選擇滿足Mercer條件得不同內(nèi)積核丞數(shù),就構(gòu)造了不同得SVM,這樣也就形成了不同得算法。目前研究最多得核函數(shù)主要有三類:(1)多頊式核函數(shù)(114)其中q就是多項式得階次,所得到得就是q階多項式分類器。(2)徑向基函數(shù)(RBF)(115)所得得SVM就是一種徑向基分類器,它與傳統(tǒng)徑向基函數(shù)方法得基本區(qū)別就是,這里每一個基函數(shù)得中心對應(yīng)于一個支持向量,它們以及輸出權(quán)值都就是由算法自動確定得。徑向基形式得內(nèi)積函數(shù)類似人得視覺特性,在實際應(yīng)用中經(jīng)常用到,但就是需要注意得就是,選擇不同得S參數(shù)值,相應(yīng)得分類面會有很大差別。(3)S形核函數(shù)(116)這時得SVM算法中包含了一個隱層得多層感知器網(wǎng)絡(luò),不但網(wǎng)絡(luò)得權(quán)值、而且網(wǎng)絡(luò)得隱層結(jié)點數(shù)也就是由算法自動確定得,而不像傳統(tǒng)得感知器網(wǎng)絡(luò)那樣由人憑借經(jīng)驗確定。此外,該算法不存在困擾神經(jīng)網(wǎng)絡(luò)得局部極小點得問題。在上述幾種常用得核函數(shù)中,最為常用得就是多項式核函數(shù)與徑向基核函數(shù)。除了上面提到得三種核函數(shù)外,還有指數(shù)徑向基核函數(shù)、小波核函數(shù)等其它一些核函數(shù),應(yīng)用相對較少。事實上,需要進行訓練得樣本集有各式各樣,核函數(shù)也各有優(yōu)劣。B、Bacsens與S、Viaene等人曾利用LSSVM分類器,采用UCI數(shù)據(jù)庫,對線性核函數(shù)、多項式核函數(shù)與徑向基核函數(shù)進行了實驗比較,從實驗結(jié)果來瞧,對不同得數(shù)據(jù)庫,不同得核函數(shù)各有優(yōu)劣,而徑向基核函數(shù)在多數(shù)數(shù)據(jù)庫上得到略為優(yōu)良得性能。三、支持向量機得應(yīng)用研究現(xiàn)狀SVM方法在理論上具有突出得優(yōu)勢,貝爾實驗室率先對美國郵政手寫數(shù)字庫識別研究方面應(yīng)用了SVM方法,取得了較大得成功。在隨后得近幾年內(nèi),有關(guān)SVM得應(yīng)用研究得到了很多領(lǐng)域得學者得重視,在人臉檢測、驗證與識別、說話人/語音識別、文字/手寫體識別、圖像處理、及其她應(yīng)用研究等方面取得了大量得研究成果,從最初得簡單模式輸入得直接得SVM方法研究,進入到多種方法取長補短得聯(lián)合應(yīng)用研究,對SVM方法也有了很多改進。(一)人臉檢測、驗證與識別Osuna最早將SVM應(yīng)用于人臉檢測.并取得了較好得效果。其方法就是汽接訓練非線性SVM分類器完成人臉與非人臉得分類。由于SVM得訓練需要大量得存儲空間,并且非線性SVM分類器需要較多得支持向量,速度很慢。為此,馬勇等提出了一種層次型結(jié)構(gòu)得SVM分類器,它由一個線性SVM組合與一個非線性SVM組成。檢測時,由前者快速排除掉圖像中絕大部分背景窗口,而后者只需對少量得候選區(qū)域做出確認;訓練時,在線性SVM組臺得限定下,與“自舉(bootstrapping)”方法相結(jié)合可收集到訓練非線性SVM得更有效得非人臉樣本,簡化SVM訓練得難度,大量實驗結(jié)果表明這種方法不僅具有較高得檢測率與較低得誤檢率,而且具有較快得速度。人臉檢測研究中更復(fù)雜得情況就是姿態(tài)得變化。葉航軍等提出了利用支持向量機方法進行人臉姿態(tài)得判定,將人臉姿態(tài)劃分成6個類別,從一個多姿態(tài)人臉庫中手工標定訓練樣本集與測試樣本集,訓練基于支持向量機姿態(tài)分類器,分類錯誤率降低到1、67％。明顯優(yōu)于在傳統(tǒng)方法中效果最好得人工神經(jīng)元網(wǎng)絡(luò)方法。在人臉識別中,面部特征得提取與識別可瞧作就是對3D物體得2D投影圖像進行匹配得問題。由于許多不確定性因素得影響,特征得選取與識別就成為一個難點。凌旭峰等及張燕昆等分別提出基于PCA與SVM相結(jié)合得人臉識別算法,充分利用了PCA在特征提取方面得有效性以及SVM在處理小樣本問題與泛化能力強等方面得優(yōu)勢,通過SVM與最近鄰距離分類器相結(jié)合,使得所提出得算法具有比傳統(tǒng)最近鄰分類器與BP網(wǎng)絡(luò)分類器更高得識別率。王宏漫等在PCA基礎(chǔ)上進一步做ICA,提取更加有利于分類得面部特征得主要獨立成分;然后采用分階段淘汰得支持向量機分類機制進行識別。對兩組人臉圖像庫得測試結(jié)果表明,基于SVM得方法在識別率與識別時間等方面都取得了較好得效果。(二)說話人／語音識別說話人識別屬于連續(xù)輸入信號得分類問題,SVM就是一個很好得分類器,但不適合處理連續(xù)輸入樣本。為此,忻棟等引入隱式馬爾可夫模型HMM,建立了SVM與HMM得混合模型。HMM適合處理連續(xù)信號,而SVM適臺于分類問題;HMM得結(jié)果反映了同類樣本得相似度,而SVM得輸出結(jié)果則體現(xiàn)了異類樣本間得差異。為了方便與HMM組成混合模型,首先將SVM得輸出形式改為概率輸出。實驗中使用YOHO數(shù)據(jù)庫,特征提取采用12階得線性預(yù)測系數(shù)分析及其微分,組成24維得特征向量。實驗表明HMM與SVM得結(jié)合達到了很好得效果。(三)文字／手寫體識別貝爾實驗室對美國郵政手寫數(shù)字庫進行得實驗,人工識別平均錯誤率就是2、5％,專門針對該特定問題設(shè)計得5層神經(jīng)網(wǎng)絡(luò)錯誤率為5、1％(其中利用了大量先驗知識),而用3種SVM方法(采用3種核函數(shù))得到得錯誤率分別為4、0％、4、1％與4、2%,且就是直接采用16×16得字符點陣作為輸入,表明了SVM得優(yōu)越性能。手寫體數(shù)字O～9得特征可以分為結(jié)構(gòu)特征、統(tǒng)計特征等。柳回春等在ＵＫ心理測試自動分析系統(tǒng)中組合SVM與其她方法成功地進行了手寫數(shù)字得識別實驗。另外,在手寫漢字識別方面,高學等提出了一種基于SVM得手寫漢字得識別方法,表明了SVM對手寫漢字識別得有效性。(四)圖像處理(1)圖像過濾。一般得互聯(lián)網(wǎng)色情網(wǎng)圖像過濾軟件主要采用網(wǎng)址庫得形式來封鎖色情網(wǎng)址或采用入工智能方法對接收到得中、英文信息進行分析甄別。段立娟等提出一種多層次特定類型圖像過濾法,即以綜合膚色模型檢驗,支持向量機分類與最近鄰方法校驗得多層次圖像處理框架,達到85％以上得準確率。(2)視頻字幕提取。攬頻字幕蘊含了豐富語義,可用于對相應(yīng)視頻流進行高級語義標注。莊越挺等提出并實踐了基于SVM得視頻字幕自動定位與提取得方法。該方法首先將原始圖像幀分割為N*N得子塊,提取每個子塊得灰度特征;然后使用預(yù)先訓練好得SVM分類機進行字幕子塊與非字幕子塊得分類;最后結(jié)合金字塔模型與后期處理過程,實現(xiàn)視頻圖像字幕區(qū)域得自動定位提取。實驗表明該方法取得了良好得效果。(3)圖像分類與檢索。由于計算機自動抽取得圖像特征與人所理解得語義間存在巨大得差距,圖像檢索結(jié)果難以令人滿意。近年來出現(xiàn)了相關(guān)反饋方法,張磊等以SVM為分類器,在每次反饋中對用戶標記得正例與反例樣本進行學習,并根據(jù)學習所得得模型進行檢索,使用由９９１８幅圖像組成得圖像庫進行實驗,結(jié)果表明,在有限訓練樣本情況下具有良好得泛化能力。目前3D虛擬物體圖像應(yīng)用越來越廣泛,肖俊等提出了一種基于SVM對相似3D物體識別與檢索得算法。該算法首先使用細節(jié)層次模型對3D物體進行三角面片數(shù)量得約減,然后提取3D物體得特征,由于所提取得特征維數(shù)很大,因此先用獨立成分分析進行特征約減,然后使用SVM進行識別與檢索。將該算法用于3D丘陵與山地得地形識別中,取得了良好效果。(五)其她應(yīng)用研究(1)由于SVM得優(yōu)越性,其應(yīng)用研究目前開展已經(jīng)相當廣泛。陳光英等設(shè)計并實現(xiàn)了一種基于SVM分類機得網(wǎng)絡(luò)入侵檢測系統(tǒng)。它收集并計算除服務(wù)器端口之外TCP／IP得流量特征.使用SVM算法進行分類,從而識別出該連接得服務(wù)類型,通過與該連接服務(wù)器端口所表明服務(wù)類型得比較,檢測出異常得TCP連接。實驗結(jié)果表明,系統(tǒng)能夠有效地檢測出異常TCP連接。(2)口令認證簡便易實現(xiàn),但容易被盜用。劉學軍等提出利用SVM進行鍵入特性得驗真,并通過實驗將其與BP、RBF、PNN與LVQ4種神經(jīng)網(wǎng)絡(luò)模型進行對比。證實了采用SVM進行鍵入特性驗真得有效性。(3)李曉黎等提出了一種將SVM與無監(jiān)督聚類相結(jié)合得新分類算法,并應(yīng)用于網(wǎng)頁分類問題。該算法首先利用無監(jiān)督聚類分別對訓練集中正例與反例聚類.然后挑選一些例子訓練SVM并獲得SVM分類器。任何網(wǎng)頁可以通過比較其與聚類中心得距離決定采用無監(jiān)督聚類方法或SVM分類器進行分類。該算法充分利用了SVM準確率高與無監(jiān)督聚類速度快得優(yōu)點。實驗表明它不僅具有較高得訓練效率,而且有很高得精確度。(4)劉江華等提出并實現(xiàn)一個用于人機交互得