第六章 支持向量機(jī)(代碼)

• SVM算法優(yōu)缺點(diǎn)

  • 優(yōu)點(diǎn):泛化錯(cuò)誤率低，計(jì)算開銷不大，結(jié)果易解釋。

  • 缺點(diǎn):對(duì)參數(shù)調(diào)節(jié)和和核函數(shù)的選擇敏感，原始分類器不加修改僅適用于處理二分類問題。

  • 范圍:數(shù)值型和標(biāo)稱型數(shù)據(jù)。

• SVM分類(Tip:不講非線性支持向量機(jī))

  • 線性支持向量機(jī)

    • 求解線性支持向量機(jī)的過程是凸二次規(guī)劃問題，所謂凸二次規(guī)劃問題，就是目標(biāo)函數(shù)是凸的二次可微函數(shù)，約束函數(shù)為仿射函數(shù)（滿足f(x)=a*x+b,a,x均為n為向量）。而我們說求解凸二次規(guī)劃問題可以利用對(duì)偶算法--即引入拉格朗日算子，利用拉格朗日對(duì)偶性將原始問題的最優(yōu)解問題轉(zhuǎn)化為拉格朗日對(duì)偶問題，這樣就將求w，b的原始問題的極小問題轉(zhuǎn)化為求alpha（alpha>=0）的對(duì)偶問題的極大問題，即求出alpha，在通過KKT條件求出對(duì)應(yīng)的參數(shù)w，b，從而找到這樣的間隔最大化超平面，進(jìn)而利用該平面完成樣本分類

  • 近似線性支持向量機(jī)

- 當(dāng)數(shù)據(jù)集并不是嚴(yán)格線性可分時(shí)，即滿足絕不部分樣本點(diǎn)是線性可分，存在極少部分異常點(diǎn)；這里也就是說存在部分樣本不能滿足約束條件，此時(shí)我們可以引入松弛因子，這樣這些樣本點(diǎn)到超平面的函數(shù)距離加上松弛因子，就能保證被超平面分隔開來；當(dāng)然，添加了松弛因子sigma，我們也會(huì)添加對(duì)應(yīng)的代價(jià)項(xiàng)，使得alpha滿足0=<alpha<=C

• SMO算法

  • SMO是一種用于訓(xùn)練SVM的強(qiáng)大算法，它將大的優(yōu)化問題分解為多個(gè)小的優(yōu)化問題來進(jìn)行求解。而這些小優(yōu)化問題往往很容易求解，并且對(duì)它們進(jìn)行順序求解和對(duì)整體求解結(jié)果是一致的。在結(jié)果一致的情況下，顯然SMO算法的求解時(shí)間要短很多，這樣當(dāng)數(shù)據(jù)集容量很大時(shí)，SMO就是一致十分高效的算法

  • SMO算法的目標(biāo)是找到一系列alpha和b，而求出這些alpha，我們就能求出權(quán)重w，這樣就能得到分隔超平面，從而完成分類任務(wù)

  • SMO算法的工作原理是：每次循環(huán)中選擇兩個(gè)alpha進(jìn)行優(yōu)化處理。一旦找到一對(duì)合適的alpha，那么就增大其中一個(gè)而減少另外一個(gè)。這里的"合適",意味著在選擇alpha對(duì)時(shí)必須滿足一定的條件，條件之一是這兩個(gè)alpha不滿足最優(yōu)化問題的kkt條件，另外一個(gè)條件是這兩個(gè)alpha還沒有進(jìn)行區(qū)間化處理

  • 對(duì)于SMO算法編寫，我們采用由簡單到復(fù)雜的方法，層層遞進(jìn)，完成最終的SMO算法實(shí)現(xiàn)，最后通過實(shí)際的用例對(duì)SVM模型進(jìn)行訓(xùn)練，并驗(yàn)證準(zhǔn)確性

  • 簡化版SMO算法

    簡化版SMO算法，省略了確定要優(yōu)化的最佳a(bǔ)lpha對(duì)的步驟，而是首先在數(shù)據(jù)集上進(jìn)行遍歷每一個(gè)alpha，再在剩余的數(shù)據(jù)集中找到另外一個(gè)alpha，構(gòu)成要優(yōu)化的alpha對(duì)，同時(shí)對(duì)其進(jìn)行優(yōu)化，這里的同時(shí)是要確保公式：Σαilabel(i)=0。所以改變一個(gè)alpha顯然會(huì)導(dǎo)致等式失效，所以這里需要同時(shí)改變兩個(gè)alpha。*

• 核函數(shù)

  核函數(shù)的目的主要是為了解決非線性分類問題，通過核技巧將低維的非線性特征轉(zhuǎn)化為高維的線性特征，從而可以通過線性模型來解決非線性的分類問題。

• 例子:手寫識(shí)別

  相較于KNN算法，盡管KNN也能取得不錯(cuò)的效果；但是從節(jié)省內(nèi)存的角度出發(fā)，顯然SVM算法更勝一籌，因?yàn)槠洳恍枰４嬲鎮(zhèn)€數(shù)據(jù)集，而只需要其作用的支持向量點(diǎn)，而取得不錯(cuò)的分類效果

由上圖可以看出，σ值在取10時(shí)取得了最好的分類效果，這也印證了我們上面的敘述。即對(duì)于固定的數(shù)據(jù)集，存在最優(yōu)的支持向量個(gè)數(shù)，使得分類錯(cuò)誤率最低。支持向量的個(gè)數(shù)會(huì)隨著σ值的增大而逐漸減少，但是分類錯(cuò)誤率確實(shí)一個(gè)先降低后升高的過程。即最小的分類錯(cuò)誤率并不意味著最少的支持向量個(gè)數(shù)。

• 小節(jié)

  支持向量機(jī)是一種分類器，它具有良好的學(xué)習(xí)能力，并且學(xué)到的東西具有很好的拓展性，SMO解決了SVM訓(xùn)練速度慢的原因。

  核函數(shù)會(huì)將數(shù)據(jù)從一個(gè)低維空間映射到一個(gè)高維空間，可以將一個(gè)在低維空間中的非線性問題轉(zhuǎn)化成為高維空間下的線性問題來求解

  支持向量機(jī)在解決多類問題的時(shí)候，需要額外的方法來對(duì)其進(jìn)行擴(kuò)展，SVM效果也對(duì)優(yōu)化參數(shù)和所用核參數(shù)中的參數(shù)敏感。

代碼托管見Github