大數(shù)據(jù)十大經(jīng)典算法SVM 講解

數(shù)據(jù)挖掘十大算法之SVM小組成員：

楊凌云、徐小江、劉潔

劉家旺、呂佳艷、伍俊分類概念：通過構(gòu)造一個(gè)分類函數(shù)或分類器的方法，該方法能把數(shù)據(jù)庫中的數(shù)據(jù)項(xiàng)映射到給定類別中的某一個(gè)，從而可以用于預(yù)測(cè)未知數(shù)據(jù)。數(shù)據(jù)：線性可分線性不可分什么是SVM全名：SupportVectorMachine（支持向量機(jī)）支持向量：支持或支撐平面上把兩類類別劃分開來的超平面的向量點(diǎn)。機(jī)：一個(gè)算法基于統(tǒng)計(jì)學(xué)習(xí)理論的一種機(jī)器學(xué)習(xí)方法。簡單的說，就是將數(shù)據(jù)單元表示在多維空間中，然后對(duì)這個(gè)空間做劃分的算法。SVM的特點(diǎn)SVM是建立在統(tǒng)計(jì)學(xué)習(xí)理論的VC維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小原理基礎(chǔ)上的，根據(jù)有限的樣本信息在模型的復(fù)雜性之間尋求最佳折衷，以期獲得最好的推廣能力（或泛化能力）。

核函數(shù)松弛變量線性分類1線性分類1線性分類問題1.如何求得最優(yōu)的g(x)？2.最優(yōu)的標(biāo)準(zhǔn)是什么？3.g(x)=wx+b中的w和b如何確定？最優(yōu)標(biāo)準(zhǔn)：分類間隔數(shù)據(jù)表示Di=(xi,yi)分類間隔即兩分類之間的距離——越遠(yuǎn)越不易混淆定義δi=(1/||w||)|g(xi)|，稱為幾何間隔||w||叫做向量w的范數(shù),WX的p范數(shù)為||w||p=(X1^p+X2^p+...+Xn^p）^(1/p)最優(yōu)標(biāo)準(zhǔn)：分類間隔H2與H之間的間隔便是幾何間隔。其中H1：<w,x>+b=1；H2：<w,x>+b=-1；幾何間隔與樣本的誤分次數(shù)間的關(guān)系：誤分次數(shù)<=(2R/δ)^2，其中δ是樣本集合到分類面的間隔，R=max||xi||,i=1,...,n;所以問題轉(zhuǎn)化成為求最大δ值。因?yàn)閣是超平面的法向量，所以w實(shí)際上只由在H1平面上的樣本點(diǎn)確定；在H1上的向量則叫做SupportedVectors，因?yàn)樗鼈儭皳巍逼鹆朔纸缇€。求最大的δ于是問題便轉(zhuǎn)化成了求很容易看出當(dāng)||w||=0的時(shí)候就得到了目標(biāo)函數(shù)的最小值。反映在圖中，就是H1與H2兩條直線間的距離無限大，所有樣本點(diǎn)都進(jìn)入了無法分類的灰色地帶解決方法：加一個(gè)約束條件求最大的δ我們把所有樣本點(diǎn)中間隔最小的那一點(diǎn)的間隔定為1，也就意味著集合中的其他點(diǎn)間隔都不會(huì)小于1，于是不難得到有不等式：yi[<w,xi>+b]≥1(i=1,2,…,l)總成立。于是上面的問題便轉(zhuǎn)化成了求條件最優(yōu)化問題：約束條件這是一個(gè)凸二次規(guī)劃問題，所以一定會(huì)存在全局的最優(yōu)解，但實(shí)際求解較為麻煩。實(shí)際的做法：將不等式約束轉(zhuǎn)化為等式約束，從而將問題轉(zhuǎn)化為拉格朗日求極值的問題。最優(yōu)問題的求解引入拉格朗日對(duì)偶變量a，w可表示為：w=a1y1x1+a2y2x2+…+anynxn；利用Lagrange乘子法：凸二次規(guī)劃問題求解代入

L(w,b,a):問題轉(zhuǎn)換為：由凸二次規(guī)劃的性質(zhì)能保證這樣最優(yōu)的向量a是存在的凸二次規(guī)劃問題求解線性分類目標(biāo)函數(shù)：約束條件：目標(biāo)函數(shù)：約束條件：拉格朗日乘數(shù)法可將問題轉(zhuǎn)化為對(duì)偶問題：目標(biāo)函數(shù)：約束條件：線性分類巧妙之處：原問題=>二次凸優(yōu)化問題=>對(duì)偶問題對(duì)偶問題求解：更巧妙的地方：未知數(shù)據(jù)x的預(yù)測(cè)，只需要計(jì)算它與訓(xùn)練數(shù)據(jù)點(diǎn)的內(nèi)積即可非線性分類對(duì)于以上所述的SVM，處理能力還是很弱，僅僅能處理線性可分的數(shù)據(jù)。如果數(shù)據(jù)線性不可分的時(shí)候，我們就將低維的數(shù)據(jù)映射向更高的維次，以此使數(shù)據(jù)重新線性可分。這轉(zhuǎn)化的關(guān)鍵便是核函數(shù)。非線性分類找不到一個(gè)超平面（二維空間：直線）將其分割開來，而很自然的想到可以用一個(gè)橢圓將數(shù)據(jù)分為兩類Z1=X1,

Z2=X12,

Z3=X2,

Z4=X22,

Z5=X1X2(X1,X2)——>(Z1,Z2,Z3,Z4,Z5,)即將：R2空間映射到R5空間。此時(shí)，總能找到一個(gè)超平面wTZ+b=0wT={a1，a2，a3，a4，a5}T，b=a6使得數(shù)據(jù)很好的分類。映射過后的空間:非線性分類令：Z1=X1,

Z2=X12,

Z3=X2,

Z4=X22,

Z5=X1X2(X1,X2)—Φ—>(Z1,Z2,Z3,Z4,Z5,)則：對(duì)于樣本x1=(η1,η2),x2=(ξ1,ξ2)Φ(x1)=[η1,η12,η2,η22,η1η2]TΦ(x2)=[ξ1,ξ12,ξ2,ξ22,ξ1ξ2]T內(nèi)積:我們注意到：非線性分類我們注意到：若令Φ(x1)=[√2η1,η12,√2η2,η22,

√2η1η2,1]T則：那么區(qū)別在于什么地方呢？1.一個(gè)是將低維空間數(shù)據(jù)映射到高維空間中，然后再根據(jù)內(nèi)積的公式進(jìn)行計(jì)算；另一個(gè)則直接在原來的低維空間中進(jìn)行計(jì)算，而不需要顯式地寫出映射后的結(jié)果。當(dāng)樣本空間處于高維度時(shí)，第一種方法將引發(fā)維度災(zāi)難，第二種方法仍然能夠從容處理核函數(shù)核函數(shù)：概念：x,z∈X,X屬于Rn空間,非線性函數(shù)Φ實(shí)現(xiàn)輸入空間X到特征空間F的映射,其中F屬于Rm，n<<m。核函數(shù)技術(shù)接收2個(gè)低維空間的向量，能夠計(jì)算出經(jīng)某變換后高維空間里的向量內(nèi)積值。根據(jù)核函數(shù)技術(shù)有：K(x,z)=<Φ(x),Φ(z)>其中：<,>為內(nèi)積,K(x,z)為核函數(shù)。例如：加入核函數(shù)以后的分類函數(shù)為：核函數(shù)核函數(shù)應(yīng)用廣泛的原因：核函數(shù)的引入避免了“維數(shù)災(zāi)難”,大大減小了計(jì)算量。而輸入空間的維數(shù)n對(duì)核函數(shù)矩陣無影響，因此，核函數(shù)方法可以有效處理高維輸入。無需知道非線性變換函數(shù)Φ的形式和參數(shù)核函數(shù)的形式和參數(shù)的變化會(huì)隱式地改變從輸入空間到特征空間的映射，進(jìn)而對(duì)特征空間的性質(zhì)產(chǎn)生影響，最終改變各種核函數(shù)方法的性能。核函數(shù)方法可以和不同的算法相結(jié)合，形成多種不同的基于核函數(shù)技術(shù)的方法，且這兩部分的設(shè)計(jì)可以單獨(dú)進(jìn)行，并可以為不同的應(yīng)用選擇不同的核函數(shù)和算法。常用的核函數(shù)多項(xiàng)式核：線性核：高斯核：總結(jié)線性可分：求解使得超平面具有最大內(nèi)間間隔的wT，b參數(shù)。將問題轉(zhuǎn)化為對(duì)偶問題進(jìn)行快速求解。改進(jìn)：加入松弛變量和懲罰因子C的SVM

松弛變量允許實(shí)際分類中一定的不準(zhǔn)確性的存在，引入松弛變量后原先的約束條件變?yōu)椋簯土P因子C則是為了避免系統(tǒng)輕易放棄一些重要的數(shù)據(jù)，減小系統(tǒng)損失。引入C后目標(biāo)函數(shù)變?yōu)椋嚎偨Y(jié)線性不可分：將數(shù)據(jù)空間映射到高維空間，使原本線性不可分變?yōu)榫€性可分。引入核函數(shù)，簡化映射空間中的內(nèi)積運(yùn)算。它避開了直接在高維空間中進(jìn)行計(jì)算，而表現(xiàn)形式卻等價(jià)于高維空間。不同的樣本結(jié)構(gòu)與不同的核函數(shù)結(jié)合，達(dá)到很好的分割效果參考資料1.《支持向量機(jī)導(dǎo)論》，[美]NelloCristianini/JohnShawe-Taylor著；2.支持向量機(jī)導(dǎo)論一書的支持網(wǎng)站：/；3.《數(shù)據(jù)挖掘?qū)д摗罚琜美]Pang-NingTan/MichaelSteinbach/VipinKumar著；4.《數(shù)據(jù)挖掘：概念與技術(shù)》，(加)JiaweiHan;MichelineKamber著；5.《數(shù)據(jù)挖掘中的新方法：支持向量機(jī)》，鄧乃揚(yáng)田英杰著；6.《支持向量機(jī)--理論、算法和擴(kuò)展》，鄧乃揚(yáng)田英杰著；7.《模式識(shí)別支持向量機(jī)指南》，C.J.CBurges著；8.《統(tǒng)計(jì)自然語言處理》，宗成慶編著，第十二章、文本分類；9.SVM入門系列，Jasper：/zhenandaci/category/31868.html；10.數(shù)據(jù)挖掘掘中所需的概率論與數(shù)理統(tǒng)計(jì)知識(shí)、上；11.《數(shù)理統(tǒng)計(jì)學(xué)簡史》，陳希孺院士著；12.《最優(yōu)化理論與算法(第2版)》，陳寶林編著；13.AGentleIntroductiontoSupportVectorMachinesinBiomedicine：/downloads/supplements/SVM_Tutorial_2010/Final_WB.pdf14.卡梅隆大學(xué)的講解SVM的PPT：/tutorials/svm15.pdf；pOXLp7v0djZKylHSJr3WxBmHK6NJ2GhiBeFZ7R4I30kA1DkaGhn3XtKknBYCUDxqA7FHYi2CHhI92tgKQcWA3PtGZ7R4I30kA1DkaGhn3XtKknBYCUDxqA7FHYi2CHhI92tgKQcWA3PtGshLs50cLmTWN60eo8Wgqv7XAv2OHUm32WGeaUwYDIAWGMeR4I30kA1DkaGhn3XtKknBYCUDxqA7FHYi2CHhI92tgKQcWA3PtGZ7R4I30kA1DkaGtgKQcWA3PtGZ7R4I30kA1DkaGhn3XtKknBYCUDxqA7FHYi2CHhI92tgKQcWA3PtGshLs50cLmTWN60eo8Wgqv7XAv2OHUm32WGeaUwYDIAWGMeR4I30kA1DkaGhn3XtKknBYCUDxqA7FHYi2CHhI92t