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

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

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

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

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

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

  • 線性支持向量機

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

  • 近似線性支持向量機

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

• SMO算法

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

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

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

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

  • 簡化版SMO算法

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

• 核函數(shù)

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

• 例子:手寫識別

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

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

• 小節(jié)

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

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

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

代碼托管見Github