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

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

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

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

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

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

7、題求解問題(5)(5)，得，得 。則參數對。則參數對(w,b)(w,b)可由下式計算：可由下式計算：nyiniiiixwb1*1*2線性可分的支持向量(分類)機0) 1)(*bxwyiii 支持向量：支持向量：稱訓練集稱訓練集D中的樣本中的樣本xi為支持向量，如為支持向量，如 果它對應的果它對應的 i*0。 根據原始最優化問題的根據原始最優化問題的KKTKKT條件，有條件，有 于是，支持向量正好在間隔邊界上于是，支持向量正好在間隔邊界上 于是，得到如下的決策函數：于是，得到如下的決策函數：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關鍵點關鍵點: 把把 xi 變換到高維的特征空間變換到高維的特征空間n為什么要變換？為什么要變換？通過加入一個新的特征通過加入一個新的特征xi，使得樣本變成線性可分的，使得樣本變成線性可分的，此時特征空間維數變高此時特征空間維數變高nTransform x (x) na x12+b x2

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

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

11、代()()ijXX (,)()()ijijK XXXX 111l1i1min ()()2. . 0 0,1,lllijijijjijjiiiy yxxstyC il n需要求解的最優化問題需要求解的最優化問題n最后得到決策函數最后得到決策函數*1( )sgn( )( )sgn( ( )( )liiiif xwxbf xyxxb 或或為此，引進函數為此，引進函數2( ,)( ( )()() 1)ijijijK x xxxx xn 給定訓練集后，決策函數僅依賴于給定訓練集后，決策函數僅依賴于而不需要再考慮非線性變換而不需要再考慮非線性變換2( ,)() 1)ijijK x xx x( )x111l

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

13、多項式內核( ,)()qiiK x xx xc得到得到q 階多項式分類器階多項式分類器( ,)tanh( ()iiK x xx xc包含一個隱層的多層感知器，隱層節點數是由算法自動確定包含一個隱層的多層感知器，隱層節點數是由算法自動確定nSigmoid內核內核22|( ,)expiixxK x x每個基函數中心對應一個支持向量，它們及輸出權值由算法自動確定每個基函數中心對應一個支持向量，它們及輸出權值由算法自動確定n高斯徑向基函數內核高斯徑向基函數內核RBF幾個典型的核函數n現有現有5個一維數據個一維數據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通過二次規劃求解，得到通過二次規劃求解，得到支持向量為支持向量為 x2