數(shù)據(jù)分析入門系列教程-SVM原理
SVM 的英文全稱是 Support Vector Machines，我們叫它支持向量機，支持向量機是用于分類的一種算法，當(dāng)然也有人用它來做回歸。
SVM 原理
我們先通過一個分類的例子來看一下 SVM 的定義
在一個二維平面上，有實心和空心兩組圓點，如果我們想用一條線分開它們，那么其實可以畫出無數(shù)條這種區(qū)分線。
而 SVM 就是試圖把線放在最佳位置，好讓在線的兩邊到兩組圓點邊界點的距離盡可能大。體現(xiàn)在圖上就是：
線 A 正好緊挨實心點的最邊界點，線 C 正好緊挨空心點的最邊界點，而線 A，B，C是三條平行線且線 B 處于線 A 和 C 距離的中心處，且圖中的綠線和黃線為最大距離，則此時的線 B 即為支持向量機算法下的最優(yōu)解。而點1，2，3就稱為支持向量，即 support vector。
當(dāng)然，還可以擴展到三維空間中，那么就是使用平面進行分割
此時我們也稱線 B 或者三維中的綠色平面為“決策面”。
決策面和分類間隔
在保證決策面方向不變且不會出現(xiàn)錯分樣本的情況下移動決策面，會在原來的決策面兩側(cè)找到兩個極限位置（越過該位置就會產(chǎn)生錯分現(xiàn)象），如圖中的兩條藍線。藍線的位置由決策面的方向和距離原決策面最近的幾個樣本的位置決定（即黃線和綠線）。而這兩條平行藍線正中間的分界線就是在保持當(dāng)前決策面方向不變的前提下的最優(yōu)決策面。兩條藍線之間的垂直距離就是這個最優(yōu)決策面對應(yīng)的分類間隔。這個具有“最大間隔”的決策面就是 SVM 要尋找的最優(yōu)解。而這個真正的最優(yōu)解對應(yīng)的兩側(cè)藍線所穿過的樣本點，就是 SVM 中的支持樣本點，稱為“支持向量”，這個概念我們上面也提到了。
由上面的圖示可以看出，要想找到最優(yōu)的決策面，其實就是一個求解最優(yōu)的問題，即最優(yōu)化問題。
當(dāng)然以上我們討論的都屬于線性的 SVM，對于非線性問題，在后面再做討論
線性 SVM 數(shù)學(xué)建模
下面我們就來看看如何使用數(shù)學(xué)公式來表示 SVM
在一個最優(yōu)化問題中，一般有兩個最基本的因素需要解決：
目標函數(shù)，就是我們希望什么東西的什么達到最好。
優(yōu)化對象，就是我們希望通過改變哪些因素來使目標函數(shù)達到最優(yōu)
在 SVM 算法中，目標函數(shù)對應(yīng)的應(yīng)該是“分類間隔”，因為我們希望根據(jù) SVM 的定義，我們需要找到這個最大的距離，才是 SVM 的最優(yōu)解。而優(yōu)化對象就是決策面，我們需要移動決策面的位置和方向，來使得分類間隔達到最大。
決策面方程
這里我們考慮的是一個兩類的分類問題，數(shù)據(jù)點用 x 來表示，這是一個 n 維向量，而類別用 y 來表示，可以取 1 或者 -1 ，分別代表兩個不同的類（這里類別用1和-1就是為了 SVM 公式的推導(dǎo)）。一個線性分類器就是要在 n 維的數(shù)據(jù)空間中找到一個超平面，其方程可以表示為
一個超平面，在二維空間中的例子就是一條直線。我們希望的是，通過這個超平面可以把兩類數(shù)據(jù)分隔開來，比如，在超平面一邊的數(shù)據(jù)點所對應(yīng)的 y 全是 -1 ，而在另一邊全是 1 。
這里的 w 和 x 都是向量，因為向量默認都是列向量，所以把 w 轉(zhuǎn)置一下就變成行向量了，然后它們的乘積就是一個標量，這樣就可以達到加一個標量 y 使得結(jié)果為0。
分類間隔
分類間隔說白了，就是點到直線的距離，公式為：
||w|| 就是向量 w 的模，即向量的長度；x 就是支持向量樣本點的坐標；y 等同于決策面方程中的 y。
SVM 約束條件
我們假設(shè)超平面（w, b）可以將訓(xùn)練樣本完全正確的分類，所以如果類別 y = 1，則有 wx + b > 0，如果 y = -1，則有 wx + b < 0。此時再根據(jù) SVM 的定義，要想正確分類，我們需要有如下約束：
記為約束條件1
由因為兩條邊界線（藍線）之間的距離 y 等于 2r，而此時 wx + b 是等于1的，所以可以得到 γ 的距離為
此時求解最優(yōu) SVM 就變成了求解在約束條件1下的 γ 的最大值，
注意因為類別 y 和 wx + b 是同號的，所以它們的乘積永遠為正數(shù)
也即是求 ||w|| 的最小化，即：
這個就是支持向量機的基本數(shù)學(xué)描述。
最后就是對上面的公式進行求解了，這中間會用到拉格朗日乘子和 KKT 等條件，就不再繼續(xù)擴展了，有興趣的同學(xué)可以查看周志華老師的《機器學(xué)習(xí)》支持向量機一篇，里面有非常詳細的推導(dǎo)過程。
SVM 擴展
我們現(xiàn)在假設(shè)樣本數(shù)據(jù)是完全線性可分的，那么學(xué)習(xí)到的模型就可以稱之為硬間隔支持向量機，即硬間隔就是指完全正確的分類，不存在錯誤的情況。
但是在真實的世界中，數(shù)據(jù)往往都不是那么“干凈”的，存在異常數(shù)據(jù)是再正常不過了，此時就需要軟間隔。軟間隔就是指允許一部分數(shù)據(jù)樣本分類錯誤，從而使得訓(xùn)練的模型可以滿足絕大部分其他樣本。
還存在另外一種情況，就是非線性的數(shù)據(jù)集。我們前面討論的都是線性情況下的分類，那么對于非線性的情況，SVM 也是支持的，就是非線性支持向量機。
比如該類數(shù)據(jù)集，任何線性模型都沒有辦法處理，SVM 也是不可用的。此時，我們就需要引入一個新的概念：核函數(shù)。它可以將樣本從原始的空間映射到一個更高緯度的空間中，從而使得在新的空間中樣本是線性可分的，這樣就可以繼續(xù)使用 SVM 來做分類了。
在非線性 SVM 中，核函數(shù)的選擇是影響 SVM 的最大因素。常用的核函數(shù)有線性核、多項式核、高斯核、拉普拉斯核，sigmoid 核等，或者是使用它們的組合核函數(shù)。通過這些核函數(shù)的轉(zhuǎn)換，我們就可以把樣本空間投射到新的高維度空間中。
SVM 實現(xiàn)多分類
SVM 本身是一個二值分類器，但是我們可以很方便的把它擴展到多分類的情況，這樣就可以很好的應(yīng)用到文本分類，圖像識別等場景中。
擴展 SVM 支持多分類，一般有兩種方法，OVR（one versus rest），一對多法；OVO（one versus one），一對一法。
OVR：對于 k 個類別發(fā)情況，訓(xùn)練 k 個SVM，第 j 個 SVM 用于判斷任意一條數(shù)據(jù)是屬于類別 j 還是非 j。
舉個栗子：一組數(shù)據(jù) A，B，C，我們先把其中的一類分為1，其他兩類分為2，則可以構(gòu)造 SVM 如下：
樣本 A 為正集，B，C 為負集；
樣本 B 為正集，A，C 為負集；
樣本 C 為正集，A，B 為負集。
這種方法需要針對 k 個分類訓(xùn)練 k 個分類器，分類的速度比較快，但是訓(xùn)練的速度較慢。當(dāng)新增一個分類時，需要重新對分類進行構(gòu)造。
OVO：對于 k 個類別的情況，訓(xùn)練 k * (k-1)/2 個 SVM，每一個 SVM 用來判斷任意一條數(shù)據(jù)是屬于 k 中的特定兩個類別中的哪一個。
相同的栗子：一組數(shù)據(jù) A，B，C，我們把任意兩類樣本之間構(gòu)造一個 SVM，那么可以構(gòu)造如下：
分類器1，A，B；
分類器2，B，C；
分類器3，A，C。
對于一個未知的樣本，每一個分類器都會有一個分類結(jié)果，記票為1，最終得票最多的類別就是未知樣本的類別。這樣當(dāng)新增類別時，不需要重新構(gòu)造 SVM 模型，訓(xùn)練速度快。但是當(dāng) k 較大時，訓(xùn)練和測試時間都會比較慢。
SVM 優(yōu)缺點
優(yōu)點
SVM 既可以用于分類，也可以用于回歸，學(xué)習(xí)能力強，學(xué)習(xí)到的結(jié)果具有很好的推廣性。
SVM 是深度學(xué)習(xí)網(wǎng)絡(luò)出現(xiàn)之前，機器學(xué)習(xí)領(lǐng)域的絕對王者
SVM 可以很好的解決小樣本，高緯度問題
缺點
對于參數(shù)調(diào)節(jié)和核函數(shù)的選擇很敏感
當(dāng)數(shù)據(jù)量特別大時，訓(xùn)練很慢
總結(jié)
今天我們一起學(xué)習(xí)了 SVM 算法，可以說它是機器學(xué)習(xí)領(lǐng)域必備的算法，沒有之一。
它本身是處理二值分類問題的，但是同樣可以通過構(gòu)造多個 SVM 分類器來靈活的處理多分類問題。
我們還簡單的推導(dǎo)了在線性可分的情況下 SVM 的數(shù)學(xué)公式，而對于非線性可分的數(shù)據(jù)，我們需要引入核函數(shù)，來映射原始數(shù)據(jù)到一個新的高緯度空間中，再進行 SVM 構(gòu)建。
