支持向量機(jī)課件

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

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

3、22 ( ,),(,),(,) nn x yxyxy , 1,1 d ii xy 12 11 iiii yxyx 表表示示；表表示示 分類面與邊界距離分類面與邊界距離(margin)的數(shù)學(xué)表示的數(shù)學(xué)表示: 分類超平面表示為：分類超平面表示為： 0 x w T b 2 w m Class 1 Class 2 m 1x w T b 1x w T b 一、線性可分的支持向量(分類)機(jī) ),( ,),(),( 2211nn yxyxyxD， niyRXx i m i , 1,1, 1, 0)(bxw 首先考慮線性可分情況。設(shè)有如下兩類樣本的訓(xùn)練集：首先考慮線性可分情況。設(shè)有如下兩類樣本的訓(xùn)練集： 線性

4、可分情況意味著存在線性可分情況意味著存在超平面超平面使訓(xùn)練點(diǎn)中的正類和使訓(xùn)練點(diǎn)中的正類和 負(fù)類樣本分別位于該超平面的兩側(cè)。負(fù)類樣本分別位于該超平面的兩側(cè)。 如果能確定這樣的參數(shù)對(duì)（如果能確定這樣的參數(shù)對(duì)（w,bw,b） 的話的話, ,就可以構(gòu)造就可以構(gòu)造決策函數(shù)決策函數(shù)來(lái)進(jìn)行來(lái)進(jìn)行 識(shí)別新樣本。識(shí)別新樣本。 )sgn()(bxwxf 線性可分的支持向量(分類)機(jī) nibxwyts w ii bw , 1, 1)(. . 2 1 min 2 , 問(wèn)題是問(wèn)題是：這樣的參數(shù)對(duì)（：這樣的參數(shù)對(duì)（w,bw,b）有許多。）有許多。 解決的方法是采用最大間隔原則。解決的方法是采用最大間隔原則。 最大間隔原則

5、最大間隔原則：選擇使得訓(xùn)練集：選擇使得訓(xùn)練集D D對(duì)于線性函數(shù)對(duì)于線性函數(shù) (wx)+b的幾何間隔取最大值的的幾何間隔取最大值的參數(shù)對(duì)參數(shù)對(duì)(w,b(w,b) )，并，并 由此構(gòu)造決策函數(shù)。由此構(gòu)造決策函數(shù)。 在規(guī)范化下，超平面的幾何間隔為在規(guī)范化下，超平面的幾何間隔為 于是，找最大于是，找最大幾何間隔的超平面幾何間隔的超平面 表述成如下的最優(yōu)化問(wèn)題：表述成如下的最優(yōu)化問(wèn)題： w 1 (1)(1) 線性可分的支持向量(分類)機(jī) n i iii bxwywbwL 1 2 ) 1)( 2 1 ),( nT n R),( 21 0),(, 0),(bwLbwL wb 為求解問(wèn)題為求解問(wèn)題(1),(1

6、),使用使用Lagrange乘子法乘子法將其轉(zhuǎn)化為對(duì)將其轉(zhuǎn)化為對(duì) 偶問(wèn)題。于是引入偶問(wèn)題。于是引入Lagrange函數(shù)函數(shù)： 其中，其中， 稱為稱為L(zhǎng)agrange乘子。乘子。 首先求首先求Lagrange函數(shù)關(guān)于函數(shù)關(guān)于w,bw,b的極小值。由的極小值。由極值條件有：極值條件有： n i ii y 1 0 n i iii xyw 1 得到：得到： (2)(2) (3)(3) (4)(4) 線性可分的支持向量(分類)機(jī) ni yts xxyy i n i ii n i n j j n j jijiji , 1, 0 , 0. . )( 2 1 min 1 111 n i iii xyw 1 n

7、 i iii xyw 1 * 將將(3)(3)式代入式代入Lagrange函數(shù)，并利用函數(shù)，并利用(4)(4)式，則原始式，則原始 的優(yōu)化問(wèn)題轉(zhuǎn)化為如下的的優(yōu)化問(wèn)題轉(zhuǎn)化為如下的對(duì)偶問(wèn)題對(duì)偶問(wèn)題( (使用極小形式使用極小形式) )： 這是一個(gè)凸二這是一個(gè)凸二 次規(guī)劃問(wèn)題次規(guī)劃問(wèn)題 有唯一的最優(yōu)有唯一的最優(yōu) 解解 (5)(5) 求解問(wèn)題求解問(wèn)題(5)(5)，得，得 。則參數(shù)對(duì)。則參數(shù)對(duì)(w,b(w,b) )可由下式計(jì)算：可由下式計(jì)算： n y i n i ii i xwb 1 * 1 * 2 線性可分的支持向量(分類)機(jī) 0) 1)( * bxwy iii 支持向量：支持向量：稱訓(xùn)練集稱訓(xùn)練集D中

8、的樣本中的樣本xi為支持向量，如為支持向量，如 果它對(duì)應(yīng)的果它對(duì)應(yīng)的 i*0。 根據(jù)原始最優(yōu)化問(wèn)題的根據(jù)原始最優(yōu)化問(wèn)題的KKTKKT條件，有條件，有 于是，支持向量正好在間隔邊界上于是，支持向量正好在間隔邊界上 于是，得到如下的決策函數(shù)：于是，得到如下的決策函數(shù)： n i iii bxxyxf 1 * )(sgn)( 幾何意義：超平面法向量是支持向量的線性組合。幾何意義：超平面法向量是支持向量的線性組合。 6=1.4 Class 1 Class 2 1=0.8 2=0 3=0 4=0 5=0 7=0 8=0.6 9=0 10=0 n 對(duì)于線性不可分的樣本怎么辦？對(duì)于線性不可分的樣本怎么辦？ n

9、 如何找到正確的分類曲線和正確的超平面對(duì)此類情況分類如何找到正確的分類曲線和正確的超平面對(duì)此類情況分類? n關(guān)鍵點(diǎn)關(guān)鍵點(diǎn): 把把 xi 變換到高維的特征空間變換到高維的特征空間 n為什么要變換？為什么要變換？ 通過(guò)加入一個(gè)新的特征通過(guò)加入一個(gè)新的特征xi，使得樣本變成線性可分的，使得樣本變成線性可分的， 此時(shí)特征空間維數(shù)變高此時(shí)特征空間維數(shù)變高 nTransform x (x) na x12+b x22=1 w1 z1+ w2z2 + w3 z3+ b =0 設(shè)訓(xùn)練集設(shè)訓(xùn)練集 ，其中，其中 假定可以用假定可以用 平面上的二次曲線來(lái)劃分：平面上的二次曲線來(lái)劃分： ( ,),1, ii Tx yi

10、l 12 ( , ) ,1, 1 T iiii xxxy 12 ( , )xx 2 22 12132412516 2 2 2 0wwxwxwxxwxwxb 現(xiàn)考慮把現(xiàn)考慮把2維空間維空間 映射到映射到6維空間的變換維空間的變換 12 ( )Txxx, 22 121212 ( )(1,2 ,2 ,2 , , )Txxxxxxx 上式可將上式可將2維空間上二次曲線映射為維空間上二次曲線映射為6維空間上的一個(gè)超平面：維空間上的一個(gè)超平面： 112233445566 2 2 2 0wXwXwXwXwXwXb 可見(jiàn)，只要利用變換，把可見(jiàn)，只要利用變換，把 x 所在的所在的2維空間的兩類輸入點(diǎn)映射維空間的

11、兩類輸入點(diǎn)映射x 所在的所在的6維空間，然后在這個(gè)維空間，然后在這個(gè)6維空間中，使用維空間中，使用線性學(xué)習(xí)機(jī)求出線性學(xué)習(xí)機(jī)求出 分劃超平面：分劃超平面： 2 *2*2 12132412516 2 2 2 0wwxwxwxxwxwxb * 16 ()0 ( , ) T wxbwww ，其中 最后得出原空間中的二次曲線：最后得出原空間中的二次曲線： n如何選擇到較高維空間的非線性映射？給定的檢 驗(yàn)元組，必須計(jì)算與每個(gè)支持向量的點(diǎn)積，出現(xiàn) 形如 可以引入核函數(shù)（內(nèi)積的回旋）來(lái)替 代 ()() ij XX (,)()() ijij K XXXX 111 l 1 i 1 min ()() 2 . . 0

12、 0,1, lll ijijijj ijj ii i y yxx s ty C il n需要求解的最優(yōu)化問(wèn)題需要求解的最優(yōu)化問(wèn)題 n最后得到?jīng)Q策函數(shù)最后得到?jīng)Q策函數(shù) * * 1 ( )sgn( ) ( )sgn( ( )( ) l iii i f xwxb f xyxxb 或或 為此，引進(jìn)函數(shù)為此，引進(jìn)函數(shù) 2 ( ,)( ( )()() 1) ijijij K x xxxx x n 給定訓(xùn)練集后，決策函數(shù)僅依賴于給定訓(xùn)練集后，決策函數(shù)僅依賴于 而不需要再考慮非線性變換而不需要再考慮非線性變換 2 ( ,)() 1) ijij K x xxx ( )x 111 l 1 i 1 min , 2

13、. . 0 0,1, lll ijijijj ijj ii i y yK x x sty C il ( ,) ij K x x n 如果想用其它的非線性分劃辦法，則可以考慮選擇其它形式如果想用其它的非線性分劃辦法，則可以考慮選擇其它形式 的函數(shù)的函數(shù) ，一旦選定了函數(shù)，就可以求解最優(yōu)化問(wèn)題，一旦選定了函數(shù)，就可以求解最優(yōu)化問(wèn)題 * 1 ( )sgn( ,) l iiij i f xyK x xb 其中其中 * 1 ( ,) |0 l jiiijj i byyK x xjjC ( ,) ij K x x 核函數(shù) * 1 (,)T l 解得解得 ，而決策函數(shù)，而決策函數(shù) 目前研究最多的核函數(shù)主要有

14、三類：目前研究最多的核函數(shù)主要有三類： n多項(xiàng)式內(nèi)核多項(xiàng)式內(nèi)核 ( ,)()q ii K x xx xc得到得到q 階多項(xiàng)式分類器階多項(xiàng)式分類器 ( ,)tanh( () ii K x xx xc 包含一個(gè)隱層的多層感知器，隱層節(jié)點(diǎn)數(shù)是由算法自動(dòng)確定包含一個(gè)隱層的多層感知器，隱層節(jié)點(diǎn)數(shù)是由算法自動(dòng)確定 nSigmoid內(nèi)核內(nèi)核 2 2 | ( ,)exp i i xx K x x 每個(gè)基函數(shù)中心對(duì)應(yīng)一個(gè)支持向量，它們及輸出權(quán)值由算法自動(dòng)確定每個(gè)基函數(shù)中心對(duì)應(yīng)一個(gè)支持向量，它們及輸出權(quán)值由算法自動(dòng)確定 n高斯徑向基函數(shù)內(nèi)核高斯徑向基函數(shù)內(nèi)核RBF 幾個(gè)典型的核函數(shù) n現(xiàn)有現(xiàn)有5個(gè)一維數(shù)據(jù)個(gè)一維數(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=1 n選擇選擇 polynomial kernel of degree 2 K(x,y) = (xy+1)2 C = 100 n求解求解 i (i=1, , 5) 12456 n通過(guò)二次規(guī)劃求解，得到通過(guò)二次規(guī)劃求解，得到 支持向量為支持向量為