支持向量機課件

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

2、一種監(jiān)督式學(xué)習(xí)的方法，它廣泛的應(yīng)用于統(tǒng)計分 類以及回歸分析中。 SVM的描述 n目標(biāo)：找到一個超平面，使得它能夠盡可能多 的將兩類數(shù)據(jù)點正確的分開，同時使分開的兩 類數(shù)據(jù)點距離分類面最遠(yuǎn)。 n解決方法：構(gòu)造一個在約束條件下的優(yōu)化問題， 具體的說是一個約束二次規(guī)劃問題(constrained quadratic programing),求解該問題，得到分類器。 最大邊緣超平面最大邊緣超平面(MMH) 邊緣：從超平面到其邊緣的側(cè)面的最短距離等于到邊緣：從超平面到其邊緣的側(cè)面的最短距離等于到 其邊緣的另一個側(cè)面的最短距離，邊緣側(cè)面平行于其邊緣的另一個側(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 一、線性可分的支持向量(分類)機 ),( ,),(),( 2211nn yxyxyxD， niyRXx i m i , 1,1, 1, 0)(bxw 首先考慮線性可分情況。設(shè)有如下兩類樣本的訓(xùn)練集：首先考慮線性可分情況。設(shè)有如下兩類樣本的訓(xùn)練集： 線性

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

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

6、),使用使用Lagrange乘子法乘子法將其轉(zhuǎn)化為對將其轉(zhuǎn)化為對 偶問題。于是引入偶問題。于是引入Lagrange函數(shù)函數(shù)： 其中，其中， 稱為稱為Lagrange乘子。乘子。 首先求首先求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) 線性可分的支持向量(分類)機 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)化問題轉(zhuǎn)化為如下的的優(yōu)化問題轉(zhuǎn)化為如下的對偶問題對偶問題( (使用極小形式使用極小形式) )： 這是一個凸二這是一個凸二 次規(guī)劃問題次規(guī)劃問題 有唯一的最優(yōu)有唯一的最優(yōu) 解解 (5)(5) 求解問題求解問題(5)(5)，得，得 。則參數(shù)對。則參數(shù)對(w,b(w,b) )可由下式計算：可由下式計算： n y i n i ii i xwb 1 * 1 * 2 線性可分的支持向量(分類)機 0) 1)( * bxwy iii 支持向量：支持向量：稱訓(xùn)練集稱訓(xùn)練集D中

8、的樣本中的樣本xi為支持向量，如為支持向量，如 果它對應(yīng)的果它對應(yīng)的 i*0。 根據(jù)原始最優(yōu)化問題的根據(jù)原始最優(yōu)化問題的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 對于線性不可分的樣本怎么辦？對于線性不可分的樣本怎么辦？ n

9、 如何找到正確的分類曲線和正確的超平面對此類情況分類如何找到正確的分類曲線和正確的超平面對此類情況分類? n關(guān)鍵點關(guān)鍵點: 把把 xi 變換到高維的特征空間變換到高維的特征空間 n為什么要變換？為什么要變換？ 通過加入一個新的特征通過加入一個新的特征xi，使得樣本變成線性可分的，使得樣本變成線性可分的， 此時特征空間維數(shù)變高此時特征空間維數(shù)變高 nTransform x (x) na x12+b x22=1 w1 z1+ w2z2 + w3 z3+ b =0 設(shè)訓(xùn)練集設(shè)訓(xùn)練集 ，其中，其中 假定可以用假定可以用 平面上的二次曲線來劃分：平面上的二次曲線來劃分： ( ,),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維空間上的一個超平面：維空間上的一個超平面： 112233445566 2 2 2 0wXwXwXwXwXwXb 可見，只要利用變換，把可見，只要利用變換，把 x 所在的所在的2維空間的兩類輸入點映射維空間的

11、兩類輸入點映射x 所在的所在的6維空間，然后在這個維空間，然后在這個6維空間中，使用維空間中，使用線性學(xué)習(xí)機求出線性學(xué)習(xí)機求出 分劃超平面：分劃超平面： 2 *2*2 12132412516 2 2 2 0wwxwxwxxwxwxb * 16 ()0 ( , ) T wxbwww ，其中 最后得出原空間中的二次曲線：最后得出原空間中的二次曲線： n如何選擇到較高維空間的非線性映射？給定的檢 驗元組，必須計算與每個支持向量的點積，出現(xiàn) 形如 可以引入核函數(shù)（內(nè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)化問題需要求解的最優(yōu)化問題 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)化問題，一旦選定了函數(shù)，就可以求解最優(yōu)化問題 * 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多項式內(nèi)核多項式內(nèi)核 ( ,)()q ii K x xx xc得到得到q 階多項式分類器階多項式分類器 ( ,)tanh( () ii K x xx xc 包含一個隱層的多層感知器，隱層節(jié)點數(shù)是由算法自動確定包含一個隱層的多層感知器，隱層節(jié)點數(shù)是由算法自動確定 nSigmoid內(nèi)核內(nèi)核 2 2 | ( ,)exp i i xx K 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=1 n選擇選擇 polynomial kernel of degree 2 K(x,y) = (xy+1)2 C = 100 n求解求解 i (i=1, , 5) 12456 n通過二次規(guī)劃求解，得到通過二次規(guī)劃求解，得到 支持向量為支持向量為