支持向量機(jī)ppt課件

1、9.3 支持向量機(jī)支持向量機(jī)支持向量機(jī)，一種線性和非線性數(shù)據(jù)有前途的新劃分類方法。巧妙利用向量內(nèi)積的回旋，通過將非線性核函數(shù)將問題變?yōu)楦呔S特征空間與低維輸入空間的相互轉(zhuǎn)換，解決了數(shù)據(jù)挖掘中的維數(shù)災(zāi)難。由于計算問題最終轉(zhuǎn)化為凸二次規(guī)劃問題，因此挖掘算法是無解或有全局最優(yōu)解。支持向量機(jī)定義n所謂支持向量機(jī)，顧名思義，分為兩個部分了解：n一，什么是支持向量（簡單來說，就是支持或支撐平面上把兩類類別劃分開來的超平面的向量點(diǎn)）n二，這里的“機(jī)（machine，機(jī)器）”便是一個算法。在機(jī)器學(xué)習(xí)領(lǐng)域，常把一些算法看做是一個機(jī)器，如分類機(jī)（當(dāng)然，也叫做分類器），而支持向量機(jī)本身便是一種監(jiān)督式學(xué)習(xí)的方法，它廣泛

2、的應(yīng)用于統(tǒng)計分類以及回歸分析中。SVM的描述n目標(biāo)：找到一個超平面，使得它能夠盡可能多的將兩類數(shù)據(jù)點(diǎn)正確的分開，同時使分開的兩類數(shù)據(jù)點(diǎn)距離分類面最遠(yuǎn)。n解決方法：構(gòu)造一個在約束條件下的優(yōu)化問題，具體的說是一個約束二次規(guī)劃問題(constrained quadratic programing),求解該問題，得到分類器。最大邊緣超平面最大邊緣超平面(MMH)邊緣：從超平面到其邊緣的側(cè)面的最短距離等于到邊緣：從超平面到其邊緣的側(cè)面的最短距離等于到其邊緣的另一個側(cè)面的最短距離，邊緣側(cè)面平行于其邊緣的另一個側(cè)面的最短距離，邊緣側(cè)面平行于超平面超平面1122( ,),(,),(,)nnx yxyxy, 1

3、,1diixy 1211 iiiiyxyx 表表示示；表表示示分類面與邊界距離分類面與邊界距離(margin)的數(shù)學(xué)表示的數(shù)學(xué)表示:分類超平面表示為：分類超平面表示為：0 x wTb2wm Class 1Class 2m1x wTb 1x wTb.一、線性可分的支持向量(分類)機(jī)),( ,),(),(2211nnyxyxyxD，niyRXximi, 1,1, 1,0)(bxw首先考慮線性可分情況。設(shè)有如下兩類樣本的訓(xùn)練集：首先考慮線性可分情況。設(shè)有如下兩類樣本的訓(xùn)練集： 線性可分情況意味著存在線性可分情況意味著存在超平面超平面使訓(xùn)練點(diǎn)中的正類和使訓(xùn)練點(diǎn)中的正類和負(fù)類樣本分別位于該超平面的兩側(cè)。

4、負(fù)類樣本分別位于該超平面的兩側(cè)。如果能確定這樣的參數(shù)對（如果能確定這樣的參數(shù)對（w,bw,b）的話的話, ,就可以構(gòu)造就可以構(gòu)造決策函數(shù)決策函數(shù)來進(jìn)行來進(jìn)行識別新樣本。識別新樣本。)sgn()(bxwxf線性可分的支持向量(分類)機(jī)nibxwytswiibw, 1, 1)(. .21min2,問題是問題是：這樣的參數(shù)對（：這樣的參數(shù)對（w,bw,b）有許多。）有許多。 解決的方法是采用最大間隔原則。解決的方法是采用最大間隔原則。最大間隔原則最大間隔原則：選擇使得訓(xùn)練集：選擇使得訓(xùn)練集D D對于線性函數(shù)對于線性函數(shù)(wx)+b的幾何間隔取最大值的的幾何間隔取最大值的參數(shù)對參數(shù)對(w,b)(w,b

5、)，并，并由此構(gòu)造決策函數(shù)。由此構(gòu)造決策函數(shù)。在規(guī)范化下，超平面的幾何間隔為在規(guī)范化下，超平面的幾何間隔為于是，找最大于是，找最大幾何間隔的超平面幾何間隔的超平面表述成如下的最優(yōu)化問題：表述成如下的最優(yōu)化問題：w1(1)(1).線性可分的支持向量(分類)機(jī)niiiibxwywbwL12) 1)(21),(nTnR),(210),(, 0),(bwLbwLwb 為求解問題為求解問題(1),(1),使用使用Lagrange乘子法乘子法將其轉(zhuǎn)化為對將其轉(zhuǎn)化為對偶問題。于是引入偶問題。于是引入Lagrange函數(shù)函數(shù)：其中，其中， 稱為稱為Lagrange乘子。乘子。首先求首先求Lagrange函數(shù)關(guān)

6、于函數(shù)關(guān)于w,bw,b的極小值。由的極小值。由極值條件有：極值條件有：niiiy10niiiixyw1得到：得到：(2)(2)(3)(3)(4)(4).線性可分的支持向量(分類)機(jī)niytsxxyyiniiininjjnjjijiji, 1, 0, 0. .)(21min1111niiiixyw1niiiixyw1*將將(3)(3)式代入式代入Lagrange函數(shù)，并利用函數(shù)，并利用(4)(4)式，則原始式，則原始的優(yōu)化問題轉(zhuǎn)化為如下的的優(yōu)化問題轉(zhuǎn)化為如下的對偶問題對偶問題( (使用極小形式使用極小形式) )：這是一個凸二這是一個凸二次規(guī)劃問題次規(guī)劃問題有唯一的最優(yōu)有唯一的最優(yōu)解解(5)(5)

7、求解問題求解問題(5)(5)，得，得 。則參數(shù)對。則參數(shù)對(w,b)(w,b)可由下式計算：可由下式計算：nyiniiiixwb1*1*2線性可分的支持向量(分類)機(jī)0) 1)(*bxwyiii 支持向量：支持向量：稱訓(xùn)練集稱訓(xùn)練集D中的樣本中的樣本xi為支持向量，如為支持向量，如 果它對應(yīng)的果它對應(yīng)的 i*0。 根據(jù)原始最優(yōu)化問題的根據(jù)原始最優(yōu)化問題的KKTKKT條件，有條件，有 于是，支持向量正好在間隔邊界上于是，支持向量正好在間隔邊界上 于是，得到如下的決策函數(shù)：于是，得到如下的決策函數(shù)：niiiibxxyxf1*)(sgn)(幾何意義：超平面法向量是支持向量的線性組合。幾何意義：超平面

8、法向量是支持向量的線性組合。 6=1.4Class 1Class 2 1=0.8 2=0 3=0 4=0 5=0 7=0 8=0.6 9=0 10=0n 對于線性不可分的樣本怎么辦？對于線性不可分的樣本怎么辦？n 如何找到正確的分類曲線和正確的超平面對此類情況分類如何找到正確的分類曲線和正確的超平面對此類情況分類?n關(guān)鍵點(diǎn)關(guān)鍵點(diǎn): 把把 xi 變換到高維的特征空間變換到高維的特征空間n為什么要變換？為什么要變換？通過加入一個新的特征通過加入一個新的特征xi，使得樣本變成線性可分的，使得樣本變成線性可分的，此時特征空間維數(shù)變高此時特征空間維數(shù)變高nTransform x (x) na x12+b

9、 x22=1 w1 z1+ w2z2 + w3 z3+ b =0設(shè)訓(xùn)練集設(shè)訓(xùn)練集 ，其中，其中假定可以用假定可以用 平面上的二次曲線來劃分：平面上的二次曲線來劃分： ( ,),1,iiTx yil 12( , ) ,1, 1Tiiiixxxy12( , )xx22212132412516 2 2 2 0wwxwxwxxwxwxb現(xiàn)考慮把現(xiàn)考慮把2維空間維空間 映射到映射到6維空間的變換維空間的變換12( )Txxx,22121212( )(1,2 ,2 ,2 , , )Txxxxxxx上式可將上式可將2維空間上二次曲線映射為維空間上二次曲線映射為6維空間上的一個超平面：維空間上的一個超平面：1

10、12233445566 2 2 2 0wXwXwXwXwXwXb可見，只要利用變換，把可見，只要利用變換，把 x 所在的所在的2維空間的兩類輸入點(diǎn)映射維空間的兩類輸入點(diǎn)映射x 所在的所在的6維空間，然后在這個維空間，然后在這個6維空間中，使用維空間中，使用線性學(xué)習(xí)機(jī)求出線性學(xué)習(xí)機(jī)求出分劃超平面：分劃超平面：2*2*2121324125162 2 2 0wwxwxwxxwxwxb*16()0 ( , )Twxbwww ，其中最后得出原空間中的二次曲線：最后得出原空間中的二次曲線：n如何選擇到較高維空間的非線性映射？給定的檢驗(yàn)元組，必須計算與每個支持向量的點(diǎn)積，出現(xiàn)形如 可以引入核函數(shù)（內(nèi)積的回旋

11、）來替代()()ijXX (,)()()ijijK XXXX111l1i1min ()()2. . 0 0,1,lllijijijjijjiiiy yxxs tyC il n需要求解的最優(yōu)化問題需要求解的最優(yōu)化問題n最后得到?jīng)Q策函數(shù)最后得到?jīng)Q策函數(shù)*1( )sgn( )( )sgn( ( )( )liiiif xwxbf xyxxb 或或?yàn)榇耍M(jìn)函數(shù)為此，引進(jìn)函數(shù)2( ,)( ( )()()1)ijijijK x xxxxxn 給定訓(xùn)練集后，決策函數(shù)僅依賴于給定訓(xùn)練集后，決策函數(shù)僅依賴于而不需要再考慮非線性變換而不需要再考慮非線性變換2( ,)() 1)ijijK x xx x( )x111

12、l1i1min ,2. . 0 0,1,lllijijijjijjiiiy yK x xstyC il ( ,)ijK x xn 如果想用其它的非線性分劃辦法，則可以考慮選擇其它形式如果想用其它的非線性分劃辦法，則可以考慮選擇其它形式的函數(shù)的函數(shù) ，一旦選定了函數(shù)，就可以求解最優(yōu)化問題，一旦選定了函數(shù)，就可以求解最優(yōu)化問題*1( )sgn( ,)liiijif xyK x xb其中其中*1( ,) |0ljiiijjibyyK x xjjC ( ,) ijK x x 核函數(shù)*1(,)Tl解得解得 ，而決策函數(shù)，而決策函數(shù)目前研究最多的核函數(shù)主要有三類：目前研究最多的核函數(shù)主要有三類：n多項(xiàng)式內(nèi)

13、核多項(xiàng)式內(nèi)核( ,)()qiiK x xx xc得到得到q 階多項(xiàng)式分類器階多項(xiàng)式分類器( ,)tanh( ()iiK x xx xc包含一個隱層的多層感知器，隱層節(jié)點(diǎn)數(shù)是由算法自動確定包含一個隱層的多層感知器，隱層節(jié)點(diǎn)數(shù)是由算法自動確定nSigmoid內(nèi)核內(nèi)核22|( ,)expiixxK x x每個基函數(shù)中心對應(yīng)一個支持向量，它們及輸出權(quán)值由算法自動確定每個基函數(shù)中心對應(yīng)一個支持向量，它們及輸出權(quán)值由算法自動確定n高斯徑向基函數(shù)內(nèi)核高斯徑向基函數(shù)內(nèi)核RBF幾個典型的核函數(shù)n現(xiàn)有現(xiàn)有5個一維數(shù)據(jù)個一維數(shù)據(jù)x1=1, x2=2, x3=4, x4=5, x5=6, 其中其中 1, 2, 6 為為 class 1，4, 5 為為class 2 y1=1, y2=1, y3=-1, y4=-1, y5=1n選擇選擇 polynomial kernel of degree 2K(x,y) = (xy+1)2C = 100n求解求解 i (i=1, , 5)12456n通過二次規(guī)劃求解，得到通過二次規(guī)劃求解，得到支持向量為支持向量為 x2