演示文稿支持向量機(jī)

支持向量機(jī)課件目前一頁(yè)\總數(shù)二十九頁(yè)\編于二點(diǎn)支持向量機(jī)，一種線性和非線性數(shù)據(jù)有前途的新劃分類(lèi)方法。巧妙利用向量?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)解。目前二頁(yè)\總數(shù)二十九頁(yè)\編于二點(diǎn)支持向量機(jī)定義所謂支持向量機(jī)，顧名思義，分為兩個(gè)部分了解：一，什么是支持向量（簡(jiǎn)單來(lái)說(shuō)，就是支持或支撐平面上把兩類(lèi)類(lèi)別劃分開(kāi)來(lái)的超平面的向量點(diǎn)）二，這里的“機(jī)（machine，機(jī)器）”便是一個(gè)算法。在機(jī)器學(xué)習(xí)領(lǐng)域，常把一些算法看做是一個(gè)機(jī)器，如分類(lèi)機(jī)（當(dāng)然，也叫做分類(lèi)器），而支持向量機(jī)本身便是一種監(jiān)督式學(xué)習(xí)的方法，它廣泛的應(yīng)用于統(tǒng)計(jì)分類(lèi)以及回歸分析中。目前三頁(yè)\總數(shù)二十九頁(yè)\編于二點(diǎn)SVM的描述目標(biāo)：找到一個(gè)超平面，使得它能夠盡可能多的將兩類(lèi)數(shù)據(jù)點(diǎn)正確的分開(kāi)，同時(shí)使分開(kāi)的兩類(lèi)數(shù)據(jù)點(diǎn)距離分類(lèi)面最遠(yuǎn)。解決方法：構(gòu)造一個(gè)在約束條件下的優(yōu)化問(wèn)題，具體的說(shuō)是一個(gè)約束二次規(guī)劃問(wèn)題(constrainedquadraticprograming),求解該問(wèn)題，得到分類(lèi)器。目前四頁(yè)\總數(shù)二十九頁(yè)\編于二點(diǎn)概述目前五頁(yè)\總數(shù)二十九頁(yè)\編于二點(diǎn)1.線性可分情形目前六頁(yè)\總數(shù)二十九頁(yè)\編于二點(diǎn)線性可分情形最大邊緣超平面(MMH)邊緣：從超平面到其邊緣的側(cè)面的最短距離等于到其邊緣的另一個(gè)側(cè)面的最短距離，邊緣側(cè)面平行于超平面目前七頁(yè)\總數(shù)二十九頁(yè)\編于二點(diǎn)分類(lèi)面與邊界距離(margin)的數(shù)學(xué)表示:分類(lèi)超平面表示為：Class1Class2m數(shù)學(xué)語(yǔ)言描述目前八頁(yè)\總數(shù)二十九頁(yè)\編于二點(diǎn)一、線性可分的支持向量(分類(lèi))機(jī)首先考慮線性可分情況。設(shè)有如下兩類(lèi)樣本的訓(xùn)練集：線性可分情況意味著存在超平面使訓(xùn)練點(diǎn)中的正類(lèi)和負(fù)類(lèi)樣本分別位于該超平面的兩側(cè)。如果能確定這樣的參數(shù)對(duì)（w,b）的話,就可以構(gòu)造決策函數(shù)來(lái)進(jìn)行識(shí)別新樣本。目前九頁(yè)\總數(shù)二十九頁(yè)\編于二點(diǎn)線性可分的支持向量(分類(lèi))機(jī)問(wèn)題是：這樣的參數(shù)對(duì)（w,b）有許多。解決的方法是采用最大間隔原則。最大間隔原則：選擇使得訓(xùn)練集D對(duì)于線性函數(shù)(w·x)+b的幾何間隔取最大值的參數(shù)對(duì)(w,b)，并由此構(gòu)造決策函數(shù)。在規(guī)范化下，超平面的幾何間隔為于是，找最大幾何間隔的超平面表述成如下的最優(yōu)化問(wèn)題：(1)目前十頁(yè)\總數(shù)二十九頁(yè)\編于二點(diǎn)線性可分的支持向量(分類(lèi))機(jī)

為求解問(wèn)題(1),使用Lagrange乘子法將其轉(zhuǎn)化為對(duì)偶問(wèn)題。于是引入Lagrange函數(shù)：其中，稱(chēng)為L(zhǎng)agrange乘子。首先求Lagrange函數(shù)關(guān)于w,b的極小值。由極值條件有：得到：(2)(3)(4)目前十一頁(yè)\總數(shù)二十九頁(yè)\編于二點(diǎn)線性可分的支持向量(分類(lèi))機(jī)將(3)式代入Lagrange函數(shù)，并利用(4)式，則原始的優(yōu)化問(wèn)題轉(zhuǎn)化為如下的對(duì)偶問(wèn)題(使用極小形式)：這是一個(gè)凸二次規(guī)劃問(wèn)題有唯一的最優(yōu)解(5)求解問(wèn)題(5)，得。則參數(shù)對(duì)(w,b)可由下式計(jì)算：目前十二頁(yè)\總數(shù)二十九頁(yè)\編于二點(diǎn)線性可分的支持向量(分類(lèi))機(jī)

支持向量：稱(chēng)訓(xùn)練集D中的樣本xi為支持向量，如果它對(duì)應(yīng)的i*>0。

根據(jù)原始最優(yōu)化問(wèn)題的KKT條件，有

于是，支持向量正好在間隔邊界上

于是，得到如下的決策函數(shù)：目前十三頁(yè)\總數(shù)二十九頁(yè)\編于二點(diǎn)幾何意義：超平面法向量是支持向量的線性組合。幾何意義a6=1.4Class1Class2a1=0.8a2=0a3=0a4=0a5=0a7=0a8=0.6a9=0a10=0目前十四頁(yè)\總數(shù)二十九頁(yè)\編于二點(diǎn)對(duì)于線性不可分的樣本怎么辦？非線性可分情形如何找到正確的分類(lèi)曲線和正確的超平面對(duì)此類(lèi)情況分類(lèi)?目前十五頁(yè)\總數(shù)二十九頁(yè)\編于二點(diǎn)非線性可分情形關(guān)鍵點(diǎn):把xi

變換到高維的特征空間為什么要變換？通過(guò)加入一個(gè)新的特征xi，使得樣本變成線性可分的，此時(shí)特征空間維數(shù)變高Transformx(x)目前十六頁(yè)\總數(shù)二十九頁(yè)\編于二點(diǎn)例子ax12+bx22=1[w]1z1+[w]2z2

+[w]3z3+b=0目前十七頁(yè)\總數(shù)二十九頁(yè)\編于二點(diǎn)設(shè)訓(xùn)練集，其中假定可以用平面上的二次曲線來(lái)劃分：現(xiàn)考慮把2維空間映射到6維空間的變換上式可將2維空間上二次曲線映射為6維空間上的一個(gè)超平面：非線性分類(lèi)目前十八頁(yè)\總數(shù)二十九頁(yè)\編于二點(diǎn)可見(jiàn)，只要利用變換，把x

所在的2維空間的兩類(lèi)輸入點(diǎn)映射x所在的6維空間，然后在這個(gè)6維空間中，使用線性學(xué)習(xí)機(jī)求出分劃超平面：最后得出原空間中的二次曲線：非線性分類(lèi)目前十九頁(yè)\總數(shù)二十九頁(yè)\編于二點(diǎn)如何選擇到較高維空間的非線性映射？給定的檢驗(yàn)元組，必須計(jì)算與每個(gè)支持向量的點(diǎn)積，出現(xiàn)形如可以引入核函數(shù)（內(nèi)積的回旋）來(lái)替代目前二十頁(yè)\總數(shù)二十九頁(yè)\編于二點(diǎn)需要求解的最優(yōu)化問(wèn)題非線性分類(lèi)最后得到?jīng)Q策函數(shù)或?yàn)榇耍M(jìn)函數(shù)目前二十一頁(yè)\總數(shù)二十九頁(yè)\編于二點(diǎn)實(shí)現(xiàn)非線性分類(lèi)的思想給定訓(xùn)練集后，決策函數(shù)僅依賴(lài)于而不需要再考慮非線性變換如果想用其它的非線性分劃辦法，則可以考慮選擇其它形式的函數(shù)，一旦選定了函數(shù)，就可以求解最優(yōu)化問(wèn)題目前二十二頁(yè)\總數(shù)二十九頁(yè)\編于二點(diǎn)實(shí)現(xiàn)非線性分類(lèi)的思想其中解得，而決策函數(shù)目前二十三頁(yè)\總數(shù)二十九頁(yè)\編于二點(diǎn)目前研究最多的核函數(shù)主要有三類(lèi)：核函數(shù)的選擇多項(xiàng)式內(nèi)核得到q階多項(xiàng)式分類(lèi)器包含一個(gè)隱層的多層感知器，隱層節(jié)點(diǎn)數(shù)是由算法自動(dòng)確定Sigmoid內(nèi)核每個(gè)基函數(shù)中心對(duì)應(yīng)一個(gè)支持向量，它們及輸出權(quán)值由算法自動(dòng)確定高斯徑向基函數(shù)內(nèi)核RBF目前二十四頁(yè)\總數(shù)二十九頁(yè)\編于二點(diǎn)幾個(gè)典型的核函數(shù)目前二十五頁(yè)\總數(shù)二十九頁(yè)\編于二點(diǎn)核的比較目前二十六頁(yè)\總數(shù)二十九頁(yè)\編于二點(diǎn)現(xiàn)有5個(gè)一維數(shù)據(jù)x1=1,x2=2,x3=4,x4=5,x5=6,其中1,2,6為class1，4,5為class2

y1=1,y2=1,y3=-1,y4=-1,y5=1選擇polynomialkernelofdegree2K(x,y)=(xy+1)2C=100求解ai(i=1,…,5)12456例子目前二十七頁(yè)\總數(shù)二十九頁(yè)\編于二點(diǎn)例子通過(guò)二次規(guī)劃求解，得到支