SVM原理與應(yīng)用培訓(xùn)

SVM原理與應(yīng)用HITSCIR-TMGroupzkli-李澤魁大綱背景線性分類非線性分類松弛變量多元分類應(yīng)用工具包2大綱背景線性分類非線性分類松弛變量多元分類應(yīng)用工具包3SVM背景支持向量機(jī)supportvectormachineSVM4為什么要用SVM(個人觀點(diǎn))分類效果好上手快N種語言的N個Toolkit理論基礎(chǔ)完備婦孺皆知的好模型找工作需要它(利益相關(guān)：面試狗一只)應(yīng)用與原理5SVM發(fā)展歷史重要理論基礎(chǔ)160年代，Vapnik和Chervonenkis提出VC維理論重要理論基礎(chǔ)21982年，Vapnik提出結(jié)構(gòu)風(fēng)險(xiǎn)最小化理論支持向量機(jī)(SupportVectorMachine)是Cortes和Vapnik于1995年首先提出的它在解決小樣本、非線性及高維模式識別中表現(xiàn)出許多特有的優(yōu)勢，并能夠推廣應(yīng)用到函數(shù)擬合等其他機(jī)器學(xué)習(xí)問題中6作者之一簡介Vapnik《StatisticalLearningTheory》作者書中詳細(xì)的論證了統(tǒng)計(jì)機(jī)器學(xué)習(xí)之所以區(qū)別于傳統(tǒng)機(jī)器學(xué)習(xí)的本質(zhì)，就在于統(tǒng)計(jì)機(jī)器學(xué)習(xí)能夠精確的給出學(xué)習(xí)效果，能夠解答需要的樣本數(shù)等等一系列問題。7SVM理論基礎(chǔ)1（比較八股）統(tǒng)計(jì)學(xué)習(xí)理論的VC維理論(StatisticalLearningTheory或SLT)是研究有限樣本情況下機(jī)器學(xué)習(xí)規(guī)律的理論(Vapnik-ChervonenkisDimension)

反映了函數(shù)集的學(xué)習(xí)能力，VC維越大則學(xué)習(xí)機(jī)器越復(fù)雜8SVM理論基礎(chǔ)2（比較八股）結(jié)構(gòu)風(fēng)險(xiǎn)最小化機(jī)器學(xué)習(xí)本質(zhì)上就是一種對問題真實(shí)模型的逼近。這個與問題真實(shí)解之間的誤差，就叫做風(fēng)險(xiǎn)。結(jié)構(gòu)化風(fēng)險(xiǎn)=經(jīng)驗(yàn)風(fēng)險(xiǎn)+置信風(fēng)險(xiǎn)經(jīng)驗(yàn)風(fēng)險(xiǎn)=

分類器在給定樣本上的誤差置信風(fēng)險(xiǎn)=分類器在未知文本上分類的結(jié)果的誤差，代表了我們在多大程度上可以信任分類器在未知文本上分類的結(jié)果。（無法準(zhǔn)確估值，給出估計(jì)的區(qū)間）9SVM理論基礎(chǔ)2（比較八股）結(jié)構(gòu)化風(fēng)險(xiǎn)=經(jīng)驗(yàn)風(fēng)險(xiǎn)+置信風(fēng)險(xiǎn)置信風(fēng)險(xiǎn)因素：樣本數(shù)量，給定的樣本數(shù)量越大，學(xué)習(xí)結(jié)果越有可能正確，此時置信風(fēng)險(xiǎn)越??；分類函數(shù)的VC維，顯然VC維越大，推廣能力越差，置信風(fēng)險(xiǎn)會變大。泛化誤差界的公式*R(w)≤Remp(w)+Ф(n/h)公式中R(w)就是真實(shí)風(fēng)險(xiǎn)，Remp(w)就是經(jīng)驗(yàn)風(fēng)險(xiǎn)，Ф(n/h)就是置信風(fēng)險(xiǎn)。統(tǒng)計(jì)學(xué)習(xí)的目標(biāo)從經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化變?yōu)榱藢で蠼?jīng)驗(yàn)風(fēng)險(xiǎn)與置信風(fēng)險(xiǎn)的和最小，即結(jié)構(gòu)風(fēng)險(xiǎn)最小。10SVM理論基礎(chǔ)（小結(jié)）統(tǒng)計(jì)學(xué)習(xí)理論的VC維理論SVM關(guān)注的是VC維結(jié)構(gòu)風(fēng)險(xiǎn)最小化R(w)≤Remp(w)+Ф(n/h)11SVM特性小樣本與問題的復(fù)雜度比起來，SVM算法要求的樣本數(shù)是相對比較少的非線性SVM擅長應(yīng)付樣本數(shù)據(jù)線性不可分的情況，主要通過松弛變量和核函數(shù)技術(shù)來實(shí)現(xiàn)高維模式識別例如文本的向量表示，幾萬維，反例:KNN12大綱背景線性分類非線性分類松弛變量多元分類應(yīng)用工具包13線性分類器問題的引入X和O是兩類樣本中間的直線就是一個分類函數(shù)，它可以將兩類樣本完全分開。14線性函數(shù)？在一維空間里就是一個點(diǎn)在二維空間里就是一條直線在三維空間里就是一個平面……如果不關(guān)注空間的維數(shù)，這種線性函數(shù)還有一個統(tǒng)一的名稱——超平面(HyperPlane)15線性函數(shù)

分類問題例如我們有一個線性函數(shù)g(x)=wx+b我們可以取閾值為0，這樣當(dāng)有一個樣本xi需要判別的時候，我們就看g(xi)的值。若g(xi)>0，就判別為類別O若g(xi)<0，則判別為類別XTipsw、x、b均可以是向量中間那條直線的表達(dá)式是g(x)=0，即wx+b=0，我們也把這個函數(shù)叫做分類面16分類面的決定分離超平面不是唯一上面的N直線都可以對點(diǎn)正確分類分離超平面存在一個最好的17分類面的“好壞”量化一個很直觀的感受是，讓“離直線最近的點(diǎn)，距離直線盡可能地遠(yuǎn)”就是分割的間隙越大越好，把兩個類別的點(diǎn)分得越開越好18“分類間隔”的引入文本分類分類時樣本格式label（標(biāo)示出這個樣本屬于哪個類別）feature（文本特征所組成的向量）假設(shè)label=±1，我們就可以定義一個樣本點(diǎn)到某個超平面的間隔為(這是定義)δi=yi(wxi+b)19^分類間隔δi=yi(wxi+b)yi(wxi+b)總大于0的，而且它的值等于|wxi+b|如果某個樣本屬于該類別的話，wxi+b>0，而yi也大于0反之，wxi+b<0，而yi也小于0現(xiàn)在把w和b進(jìn)行一下歸一化，即用w/||w||和b/||w||分別代替原來的w和b，那么間隔就可以寫成20^分類間隔

幾何間隔解析幾何中點(diǎn)xi到直線g(x)=0的距離公式推廣一下，是到超平面g(x)=0的距離，g(x)=0就是上節(jié)中提到的分類超平面||w||是什么符號？||w||叫做向量w的范數(shù)，向量長度其實(shí)指的是它的2-范數(shù)用歸一化的w和b代替原值之后的間隔有一個專門的名稱，叫做幾何間隔21量化問題之“支持向量”被紅色和藍(lán)色的線圈出來的點(diǎn)就是所謂的支持向量(supportvector)22量化問題之“最大化間隔”MaximumMarginal原則ClassifierBoundary就是f(x)，紅色和藍(lán)色的線（plusplane與minusplane）就是supportvector所在的面，紅色、藍(lán)色線之間的間隔就是我們要最大化的分類間的間隔。23量化問題之“最大化間隔”MaximumMargin原則幾何間隔24幾何間隔的現(xiàn)實(shí)含義H是分類面，而H1和H2是平行于H，且過離H最近的兩類樣本的直線，H1與H，H2與H之間的距離就是幾何間隔25幾何間隔的存在意義幾何間隔與樣本的誤分次數(shù)間存在關(guān)系其中的δ是樣本集合到分類面的間隔，R=max||xi||

i=1,...,n，即R是所有樣本中向量長度最長的值（也就是說代表樣本的分布有多么廣）誤分次數(shù)一定程度上代表分類器的誤差。（證明略）誤分次數(shù)的上界由幾何間隔決定（樣本已知的時候）26MaximumMargin為了使分類面更合適為了減少誤分次數(shù)最大化幾何間隔27minimize||w||是否讓W(xué)=0，目標(biāo)函數(shù)就最小了呢？=。=式子有還有一些限制條件，完整的寫下來，應(yīng)該是這樣的求最小值的問題就是一個優(yōu)化問題，一個帶約束的二次規(guī)劃(quadraticprogramming,QP)問題，是一個凸問題凸二次規(guī)劃區(qū)別于一般意義上的規(guī)劃問題，它有解而且是全局最優(yōu)的解，而且可以找到28如何解二次規(guī)劃問題等式約束，是求極值、拉格朗日轉(zhuǎn)化等方法轉(zhuǎn)化為無約束問題不等式約束的問題怎么辦？方法一：用現(xiàn)成的QP(QuadraticProgramming)優(yōu)化包進(jìn)行求解(效率低)方法二：求解與原問題等價的對偶問題(dualproblem)得到原始問題的最優(yōu)解(更易求解、可以推廣到核函數(shù))拉格朗日乘子法拉格朗日對偶性KKT理論支撐29求解步驟轉(zhuǎn)化為對偶問題對偶轉(zhuǎn)化&KKT條件求解wb極小化拉格朗日乘子極值求解α極大化用SMO算法求解α乘子301、對偶問題的轉(zhuǎn)化給每一個約束條件加上一個拉格朗日乘子（Lagrangemultiplier），定義拉格朗日函數(shù)根據(jù)對偶算法與KKT條件約束，這個問題可以從轉(zhuǎn)化為其中p*和d*等價條件就是KKT條件*312、wb的極小化那么問題轉(zhuǎn)化為先固定α，求wb的最小值將以上結(jié)果代入之前的L，得到只含α的優(yōu)化結(jié)果323、α的極大化優(yōu)化問題接上一步處理結(jié)果如果求出了α*，那么w和b就可以隨之求解最終得出分離超平面和分類決策函數(shù)。那么有什么好方法求α呢？333、利用SMO算法求解對偶問題中的拉格朗日乘子α優(yōu)化問題接上一步處理結(jié)果上述式子要解決的是在參數(shù)αi上求最大值的問題，至于xy都是已知數(shù)SMO算法(略)34

表達(dá)式的感性分析(番外篇)線性函數(shù)表達(dá)式為g(x)=<w,x>+b樣本確定了w，用數(shù)學(xué)的語言描述，就是w可以表示為樣本的某種組合w=α1x1+α2x2+…+αnxn同時w不僅跟樣本點(diǎn)的位置有關(guān)，還跟樣本的類別有關(guān)（也就是和樣本的“標(biāo)簽”有關(guān)）。因此用下面這個式子表示才算完整：w=α1y1x1+α2y2x2+…+αnynxn

35分類函數(shù)的預(yù)測將w的表達(dá)式帶入分類函數(shù)后對于新點(diǎn)x的預(yù)測，只需要計(jì)算它與訓(xùn)練數(shù)據(jù)點(diǎn)的內(nèi)積即可（表示向量內(nèi)積）所有非SupportingVector所對應(yīng)的系數(shù)都αi是等于零的，因此對于新點(diǎn)的內(nèi)積計(jì)算實(shí)際上只要針對少量的“支持向量”而不是所有的訓(xùn)練數(shù)據(jù)即可。36大綱背景線性分類非線性分類松弛變量多元分類應(yīng)用工具包37非線性分類——問題的引入我們把橫軸上端點(diǎn)a和b之間紅色部分里的所有點(diǎn)定為正類，兩邊的黑色部分里的點(diǎn)定為負(fù)類。試問能找到一個線性函數(shù)把兩類正確分開么？不能，因?yàn)槎S空間里的線性函數(shù)就是指直線，顯然找不到符合條件的直線。38非線性分類——問題的引入顯然通過點(diǎn)在這條曲線的上方還是下方就可以判斷點(diǎn)所屬的類別39非線性分類——問題的引入這條曲線就是我們熟知的二次曲線，它的函數(shù)表達(dá)式可以寫為：它不是一個線性函數(shù)，但是，我們可以新建一個向量y和a：這樣g(x)就可以轉(zhuǎn)化為f(y)=<a,y>40非線性分類——問題的引入原先問題是：轉(zhuǎn)化后的問題：

在任意維度的空間中，這種形式的函數(shù)都是一個線性函數(shù)原來在二維空間中一個線性不可分的問題，映射到四維空間后，變成了線性可分的。解決線性不可分問題的基本思路——向高維空間轉(zhuǎn)化(這種特征變換稱作特征映射(featuremapping))，使其變得線性可分。41核函數(shù)——例子引入我們文本分類問題的原始空間是1000維的，在這個維度上問題是線性不可分的。現(xiàn)在我們有一個2000維空間里的線性函數(shù)式中的w’和x’都是2000維的向量，只不過w’是定值，而x’是變量現(xiàn)在我們的輸入，是一個1000維的向量x，分類的過程是先把x變換為2000維的向量x’，然后求這個變換后的向量x’與向量w’的內(nèi)積，再把這個內(nèi)積的值和b相加，就得到了結(jié)果，看結(jié)果大于閾值還是小于閾值就得到了分類結(jié)果。42核函數(shù)——例子引入我們其實(shí)只關(guān)心那個高維空間里內(nèi)積的值，那個值算出來了，分類結(jié)果就算出來了。是否能有這樣一種函數(shù)K(w,x),他接受低維空間的輸入值，卻能算出高維空間的內(nèi)積值<w’,x’>？如果有這樣的函數(shù)，那么當(dāng)給了一個低維空間的輸入x以后：這兩個函數(shù)的計(jì)算結(jié)果就完全一樣，我們也就用不著費(fèi)力找那個映射關(guān)系，直接拿低維的輸入往g(x)里面代就可以了43假設(shè)映射函數(shù)是我們要將映射為那么定義核函數(shù)（Kernel）為如果要實(shí)現(xiàn)該節(jié)開頭的效果，只需先計(jì)算，然后計(jì)算

即可，然而這種計(jì)算方式是非常低效的。比如最初的特征是n維的，我們將其映射到n^2維，然后再計(jì)算，這樣需要O(n^2)的時間。那么我們能不能想辦法減少計(jì)算時間呢?核函數(shù)——形式化定義44核函數(shù)這樣的K(w,x)確實(shí)存在。它被稱作核函數(shù)(kernel)，而且還不止一個事實(shí)上，只要是滿足了Mercer條件*的函數(shù)，都可以作為核函數(shù)。核函數(shù)的基本作用就是接受兩個低維空間里的向量，能夠計(jì)算出經(jīng)過某個變換后在高維空間里的向量內(nèi)積值。45核函數(shù)——例子1假設(shè)x和z都是n維的展開后，得我們可以只計(jì)算原始特征x和z內(nèi)積的平方，時間復(fù)雜度是O(n)，就等價與計(jì)算映射后特征的內(nèi)積。也就是說我們不需要花時間O(n^2)了46核函數(shù)——例子2核函數(shù)對應(yīng)的映射函數(shù)（n=3時）是47核函數(shù)舉例1——高斯核如果x和z很相近(

)，那么核函數(shù)值為1，如果x和z相差很大()，那么核函數(shù)值約等于0。由于這個函數(shù)類似于高斯分布，因此稱為高斯核函數(shù)，也叫做徑向基函數(shù)(RadialBasisFunction簡稱RBF)。它能夠把原始特征映射到無窮維。48核函數(shù)舉例1——高斯核49核函數(shù)舉例2——sigmoid核既然高斯核函數(shù)能夠比較x和z的相似度，并映射到0到1，回想logistic回歸，sigmoid函數(shù)可以，因此還有sigmoid核函數(shù)等等。50核函數(shù)舉例3——多項(xiàng)式核剛才我們舉的例子是這里多項(xiàng)式核的一個特例（R=0，d=2）。雖然比較麻煩，而且沒有必要，不過這個核所對應(yīng)的映射實(shí)際上是可以寫出來的。51核函數(shù)舉例4——線性核這實(shí)際上就是原始空間中的內(nèi)積。這個核存在的主要目的是使得“映射后空間中的問題”和“映射前空間中的問題”兩者在形式上統(tǒng)一起來52核函數(shù)小結(jié)我們會經(jīng)常遇到線性不可分的樣例，此時，我們的常用做法是把樣例特征映射到高維空間中去如果凡是遇到線性不可分的樣例，一律映射到高維空間，那么這個維度大小是會高到可怕的核函數(shù)就隆重登場了，核函數(shù)的價值在于它雖然也是講特征進(jìn)行從低維到高維的轉(zhuǎn)換，但核函數(shù)絕就絕在它事先在低維上進(jìn)行計(jì)算，而將實(shí)質(zhì)上的分類效果表現(xiàn)在了高維上，也就如上文所說的避免了直接在高維空間中的復(fù)雜計(jì)算53核函數(shù)分類效果圖籬笆部署問題54核函數(shù)還有什么值得我們注意的既然有很多的核函數(shù)，針對具體問題該怎么選擇？對核函數(shù)的選擇，現(xiàn)在還缺乏指導(dǎo)原則如果使用核函數(shù)向高維空間映射后，問題仍然是線性不可分的，那怎么辦？松弛變量55大綱背景線性分類非線性分類松弛變量多元分類應(yīng)用工具包56問題的引入現(xiàn)在我們已經(jīng)把一個本來線性不可分的文本分類問題，通過映射到高維空間而變成了線性可分的57問題的引入圓形和方形的點(diǎn)各有成千上萬個，現(xiàn)在想象我們有另一個樣本點(diǎn)，但是這個樣本的位置是這樣的：58近似線性可分問題就是圖中黃色那個點(diǎn)，它是方形的，因而它是負(fù)類的一個樣本，這單獨(dú)的一個樣本，使得原本線性可分的問題變成了線性不可分的。這樣類似的問題（僅有少數(shù)點(diǎn)線性不可分）叫做“近似線性可分”的問題。59Outlier的處理分析有一萬個點(diǎn)都符合某種規(guī)律（因而線性可分），有一個點(diǎn)不符合，那這一個點(diǎn)是否就代表了分類規(guī)則中我們沒有考慮到的方面呢更有可能的是，這個樣本點(diǎn)壓根就是錯誤，是噪聲，是提供訓(xùn)練集的同學(xué)人工分類時一打瞌睡錯放進(jìn)去的。所以我們會簡單的忽略這個樣本點(diǎn)，仍然使用原來的分類器，其效果絲毫不受影響。60硬間隔分類問題由于我們原本的優(yōu)化問題的表達(dá)式中，確實(shí)要考慮所有的樣本點(diǎn)（不能忽略某一個，因?yàn)槌绦蛩趺粗涝摵雎阅囊粋€呢？），在此基礎(chǔ)上尋找正負(fù)類之間的最大幾何間隔，而幾何間隔本身代表的是距離，是非負(fù)的，像上面這種有噪聲的情況會使得整個問題無解。這種解法其實(shí)也叫做“硬間隔”分類法，因?yàn)樗残缘囊笏袠颖军c(diǎn)都滿足和分類平面間的距離必須大于某個值。61如何評價硬間隔分類硬間隔的分類法其結(jié)果容易受少數(shù)點(diǎn)的控制，這是很危險(xiǎn)的解決方法：允許一些點(diǎn)到分類平面的距離不滿足原先的要求62松弛變量的引入意思是說離分類面最近的樣本點(diǎn)函數(shù)間隔也要比1大。如果要引入容錯性，就給1這個硬性的閾值加一個松弛變量，即允許因?yàn)樗沙谧兞渴欠秦?fù)的，因此最終的結(jié)果是要求間隔可以比1小63松弛變量值的確定當(dāng)某些點(diǎn)出現(xiàn)這種間隔比1小的情況時（這些點(diǎn)也叫離群點(diǎn)），意味著我們放棄了對這些點(diǎn)的精確分類，而這對我們的分類器來說是種損失但是放棄這些點(diǎn)也帶來了好處，那就是使分類面不必向這些點(diǎn)的方向移動，因而可以得到更大的幾何間隔（在低維空間看來，分類邊界也更平滑）64松弛變量vs優(yōu)化問題我們原始的硬間隔分類對應(yīng)的優(yōu)化問題我們要把松弛變量加入到優(yōu)化問題中，即將損失越小越好65軟間隔分類器如果是，則為二階軟間隔分類器如果是，則為一階軟間隔分類器66懲罰因子C懲罰因子C把損失加入到目標(biāo)函數(shù)里的時候，就需要一個懲罰因子（cost，也就是N中工具包中的參數(shù)C）67松弛變量&懲罰因子的幾點(diǎn)說明并非所有的樣本點(diǎn)都有一個松弛變量與其對應(yīng)。實(shí)際上只有“離群點(diǎn)”才有，沒離群的點(diǎn)松弛變量都等于0松弛變量的值實(shí)際上標(biāo)示出了對應(yīng)的點(diǎn)到底離群有多遠(yuǎn)，值越大，點(diǎn)就越遠(yuǎn)懲罰因子C決定了你有多重視離群點(diǎn)帶來的損失，顯然當(dāng)所有離群點(diǎn)的松弛變量的和一定時，你定的C越大，對目標(biāo)函數(shù)的損失也越大懲罰因子C不是一個變量，整個優(yōu)化問題在解的時候，C是一個事先指定的值68核函數(shù)vs松弛變量相同點(diǎn)：都是解決線性不可分問題的不同點(diǎn)：在原始的低維空間中，樣本相當(dāng)?shù)牟豢煞?，無論你怎么找分類平面，總會有大量的離群點(diǎn)，此時用核函數(shù)向高維空間映射一下，雖然結(jié)果仍然是不可分的，但比原始空間里的要更加接近線性可分的狀態(tài)達(dá)到了近似線性可分的狀態(tài)后，此時再用松弛變量處理那些少數(shù)“冥頑不化”的離群點(diǎn)69C的運(yùn)用：數(shù)據(jù)集偏斜(unbalanced)它指的是參與分類的兩個類別（也可以指多個類別）樣本數(shù)量差異很大。比如說正類有10000個樣本，而負(fù)類只給了100個70數(shù)據(jù)集偏斜(unbalanced)方形的點(diǎn)是負(fù)類。H，H1，H2是根據(jù)給的樣本算出來的分類面兩個灰色點(diǎn)有提供的話，那算出來的分類面應(yīng)該是H’，H2’和H1負(fù)類給的樣本點(diǎn)越多，就越容易出現(xiàn)在灰色點(diǎn)附近的點(diǎn)，我們算出的結(jié)果也就越接近于真實(shí)的分類面。71unbalanced問題的解決方法(1)懲罰因子，那就是給樣本數(shù)量少的負(fù)類更大的懲罰因子，表示我們重視這部分樣本72unbalanced問題的解決方法(2)不一定是樣本少，還可能是分布不夠廣“政治類”vs“體育類”文本分類，體育類集中在“籃球”領(lǐng)域比如可以算算他們在空間中占據(jù)了多大的體積，例如給負(fù)類找一個超球，它可以包含所有負(fù)類的樣本，再給正類找一個，比比兩個球的半徑，就可以大致確定分布的情況但是有些領(lǐng)域分布的確不夠廣，比如“高考作文”vs“C語言類”73unbalanced問題的解決方法簡單的就是美的Libsvm在解決偏斜問題的時候用的是方案一，樣本數(shù)量的比C的初始值根據(jù)參數(shù)調(diào)優(yōu)計(jì)算出來咱們先假定說C+是5這么大，C-就可以定為500這么大（10000：100=100：1）74大綱背景線性分類非線性分類松弛變量多元分類應(yīng)用工具包75多元分類SVM是一種典型的兩類分類器，即它只回答屬于正類還是負(fù)類的問題而現(xiàn)實(shí)中要解決的問題，往往是多類的問題如何由兩類分類器得到多類分類器，就是一個值得研究的問題76方案一：一次求解N個分類面一次性考慮所有樣本，并求解一個多目標(biāo)函數(shù)的優(yōu)化問題，一次性得到多個分類面可惜這種算法還基本停留在紙面上，因?yàn)橐淮涡郧蠼獾姆椒ㄓ?jì)算量實(shí)在太大，大到無法實(shí)用的地步77方案二：一類對其余一類對余類法(Oneversusrest，OVR)構(gòu)造類別數(shù)k個的二元分類器訓(xùn)練時第i個分類機(jī)取訓(xùn)練集中第i類為正類，其余類別點(diǎn)為負(fù)類判別時，輸入信號分別經(jīng)過k個分類器輸出優(yōu)點(diǎn)每個優(yōu)化問題的規(guī)模比較小，而且分類的時候速度很快缺點(diǎn)分類重疊&不可分類&人為的數(shù)據(jù)偏斜78方案三：一對一該方法在每兩類問訓(xùn)練一個分類器，因此對于一個k類問題，將有k(k-1)/2個分類器優(yōu)點(diǎn)避免了數(shù)據(jù)偏斜訓(xùn)練階段（也就是算出這些分類器的分類平面時）所用的總時間卻比“OVR”方法少很多投票時也會有分類重疊的現(xiàn)象，但不會有不可分類現(xiàn)象缺點(diǎn)類別數(shù)為5的時候，我們調(diào)用了10個分類器，類別數(shù)如果是1000，要調(diào)用的分類器數(shù)目會上升至約500,000個（但是時間上可能OVO還是比OVR少，因?yàn)榭紤]的樣本數(shù)少）79方案四：DAG方法(有向無環(huán)圖)DAG-SVMs是針對OVO存在誤分現(xiàn)象提出的這種方法的k(k-1)/2個分類器，構(gòu)成一個有向無環(huán)圖。該有向無環(huán)圖中含有k(k-1)/2個內(nèi)部節(jié)點(diǎn)和k個葉結(jié)點(diǎn)，每個節(jié)點(diǎn)對應(yīng)一個二類分類器80方案四：DAG方法(有向無環(huán)圖)優(yōu)點(diǎn)簡單易行，只需要使用k-1個決策函數(shù)即可得出結(jié)果，較“一對一"方法提高了測試速度，而且不存在誤分、拒分區(qū)域由于其特殊的結(jié)構(gòu)，故有一定的容錯性，分類精度較一般的二叉樹方法高缺點(diǎn)誤差積累81方案四：DAG方法(有向無環(huán)圖)DAG的錯誤累積錯誤累積在一對其余和一對一方法中也都存在，DAG方法好于它們的地方就在于，累積的上限，不管是大是小，總是有定論的，有理論證明而一對其余和一對一方法中，盡管每一個兩類分類器的泛化誤差限是知道的，但是合起來做多類分類的時候，誤差上界是多少DAG方法根節(jié)點(diǎn)的選取我們就總?cè)≡趦深惙诸愔姓_率最高的那個分類器作根節(jié)點(diǎn)置信度最大的路徑82其他方案：決策樹、ECOC決策樹方法糾錯輸出編碼法(ECOC)K*L維編碼矩陣類別判定用漢明距離83大綱背景線性分類非線性分類松弛變量多元分類應(yīng)用工具包84SVM的應(yīng)用文本分類(下頁詳談)圖像處理圖像過濾、圖片分類與檢索生物信息技術(shù)蛋白質(zhì)分類語音識別人臉檢測、指紋識別手寫字體識別網(wǎng)絡(luò)入侵檢測、口令認(rèn)證、網(wǎng)頁分類……85SVM的文本分類應(yīng)用例:Topic分類14萬條微信數(shù)據(jù)，33個類別。3000條測試數(shù)據(jù)，其余數(shù)據(jù)為訓(xùn)練數(shù)據(jù)。Emotion分類8000句微博，3個類別。2000句測試數(shù)據(jù)，其余數(shù)據(jù)訓(xùn)練。省略恢復(fù)“小明買了蘋果，很甜?！?6大綱背景線性分類非線性分類松弛變量多元分類應(yīng)用工具包87SVM工具包LibsvmLiblinear

Svm_perfLibShortText……88Libsvm簡介LibSVM是林智仁(Chih-JenLin)教授開發(fā)可以很方便的對數(shù)據(jù)做分類或回歸程序小，運(yùn)用靈活，輸入?yún)?shù)少，并且是開源的，易于擴(kuò)展，因此成為目前國內(nèi)應(yīng)用最多的SVM的庫Thecurrentrelease(Version3.20,November2014)

89Libsvm工具包工具包組成JavaMatlabPythonsvm-toy(一個可視化的工具,用來展示訓(xùn)練數(shù)據(jù)和分類界面,里面是源碼,其編譯后的程序在windows文件夾下)Tools(四個python文件,用來數(shù)據(jù)集抽樣(subset),參數(shù)優(yōu)選(grid),集成測試(easy),數(shù)據(jù)檢查(checkdata))Windows(包含libSVM四個exe程序包)其他.c.h源碼90Libsvm工具包常用命令Svmtrain

svmtrain[options]training_set_file[model_file]Svmpredictsvmpredict[options]test_filemodel_fileoutput_fileSvmscalesvmscale[options]filename91Libsvm模型文件X.model92Libsvm源碼數(shù)據(jù)結(jié)構(gòu)舉例SVMnodeSVMmodel93Libsvm源碼數(shù)據(jù)結(jié)構(gòu)舉例SVMproblemsvm_train調(diào)用的svm_group_class94LiblinearLiblinear線性分類器主要為大規(guī)模數(shù)據(jù)的線性模型設(shè)計(jì)由于采用線性核,所以不需要計(jì)算kernelvalue,速度更快缺點(diǎn)就是太吃內(nèi)存了。10G的數(shù)據(jù)量需要接近50G的內(nèi)存，數(shù)據(jù)量再大就沒法做了

95什么時候用Liblinear當(dāng)你面對海量的數(shù)據(jù)時，這里的海量通常是百萬級別以上海量數(shù)據(jù)分為兩個層次：樣本數(shù)量和特征的數(shù)量。使用線性和非線性映射訓(xùn)練模型得到相近的效果對模型訓(xùn)練的時間效率要