1 介紹
SVM（Support Vector Machines）——支持向量機(jī)是在所有知名的數(shù)據(jù)挖掘算法中最健壯毫别，最準(zhǔn)確的方法之一组贺，它屬于二分類算法泡躯，可以支持線性和非線性的分類儿普。
支持向量與超平面
在了解svm算法之前崎逃，我們首先需要了解一下線性分類器這個(gè)概念。比如給定一系列的數(shù)據(jù)樣本眉孩，每個(gè)樣本都有對(duì)應(yīng)的一個(gè)標(biāo)簽个绍。為了使得描述更加直觀，我們采用二維平面進(jìn)行解釋浪汪，高維空間原理也是一樣巴柿。
舉個(gè)例子，假設(shè)在一個(gè)二維線性可分的數(shù)據(jù)集中吟宦，圖一A所示篮洁，我們要找到一個(gè)超平面把兩組數(shù)據(jù)分開，這時(shí)殃姓，我們認(rèn)為線性回歸的直線或邏輯回歸的直線也能夠做這個(gè)分類袁波，這條直線可以是圖一B中的直線，也可以是圖一C中的直線蜗侈，或者圖一D中的直線篷牌，但哪條直線才最好呢，也就是說(shuō)哪條直線能夠達(dá)到最好的泛化能力呢踏幻？那就是一個(gè)能使兩類之間的空間大小最大的一個(gè)超平面枷颊。
這個(gè)超平面在二維平面上看到的就是一條直線，在三維空間中就是一個(gè)平面...该面，因此夭苗，我們把這個(gè)劃分?jǐn)?shù)據(jù)的決策邊界統(tǒng)稱為超平面。離這個(gè)超平面最近的點(diǎn)就叫做支持向量隔缀，點(diǎn)到超平面的距離叫間隔题造。支持向量機(jī)就是要使超平面和支持向量之間的間隔盡可能的大，這樣超平面才可以將兩類樣本準(zhǔn)確的分開猾瘸，而保證間隔盡可能的大就是保證我們的分類器誤差盡可能的小界赔，盡可能的健壯丢习。
2 工作原理
2.1 點(diǎn)到超平面的距離公式
既然這樣的直線是存在的，那么我們?cè)鯓訉ふ页鲞@樣的直線呢淮悼？與二維空間類似咐低，超平面的方程也可以寫成一下形式：
有了超平面的表達(dá)式之后之后，我們就可以計(jì)算樣本點(diǎn)到平面的距離了袜腥。假設(shè)
為樣本的中的一個(gè)點(diǎn)见擦，其中xi表示為第個(gè)特征變量。那么該點(diǎn)到超平面的距離d就可以用如下公式進(jìn)行計(jì)算：
其中||W||為超平面的范數(shù)羹令，常數(shù)b類似于直線方程中的截距锡宋。
2.2 最大間隔的優(yōu)化模型
現(xiàn)在我們已經(jīng)知道了如何去求數(shù)據(jù)點(diǎn)到超平面的距離，在超平面確定的情況下特恬，我們就能夠找出所有支持向量，然后計(jì)算出間隔margin徐钠。每一個(gè)超平面都對(duì)應(yīng)著一個(gè)margin癌刽，我們的目標(biāo)就是找出所有margin中最大的那個(gè)值對(duì)應(yīng)的超平面。因此用數(shù)學(xué)語(yǔ)言描述就是確定w尝丐、b使得margin最大显拜。這是一個(gè)優(yōu)化問(wèn)題其目標(biāo)函數(shù)可以寫成：
其中y表示數(shù)據(jù)點(diǎn)的標(biāo)簽，且其為-1或1爹袁。距離用計(jì)算y(wx+b)远荠，這是就能體會(huì)出-1和1的好處了。如果數(shù)據(jù)點(diǎn)在平面的正方向(即+1類)那么y(wx+b)是一個(gè)正數(shù)失息，而當(dāng)數(shù)據(jù)點(diǎn)在平面的負(fù)方向時(shí)(即-1類)譬淳，y(wx+b)依然是一個(gè)正數(shù)，這樣就能夠保證始終大于零了盹兢。注意到當(dāng)w和b等比例放大時(shí)邻梆，d的結(jié)果是不會(huì)改變的。因此我們可以令所有支持向量的u為1绎秒，而其他點(diǎn)的u大1這是可以辦通過(guò)調(diào)節(jié)w和b求到的浦妄。因此上面的問(wèn)題可以簡(jiǎn)化為：
為了后面計(jì)算的方便，我們將目標(biāo)函數(shù)等價(jià)替換為：
這是一個(gè)有約束條件的優(yōu)化問(wèn)題见芹，通常我們可以用拉格朗日乘子法來(lái)求解剂娄。應(yīng)用拉格朗日乘子法如下：
求L關(guān)于求偏導(dǎo)數(shù)得：
帶入計(jì)算得：
原問(wèn)題的對(duì)偶問(wèn)題為：
該對(duì)偶問(wèn)題的KKT條件為：
到此，似乎問(wèn)題就能夠完美地解決了玄呛。但是這里有個(gè)假設(shè)：數(shù)據(jù)必須是百分之百可分的阅懦。但是實(shí)際中的數(shù)據(jù)幾乎都不那么“干凈”，或多或少都會(huì)存在一些噪點(diǎn)把鉴。為此下面我們將引入了松弛變量來(lái)解決這種問(wèn)題故黑。
2.3 松弛變量
由上一節(jié)的分析我們知道實(shí)際中很多樣本數(shù)據(jù)都不能夠用一個(gè)超平面把數(shù)據(jù)完全分開儿咱。如果數(shù)據(jù)集中存在噪點(diǎn)的話，那么在求超平的時(shí)候就會(huì)出現(xiàn)很大問(wèn)題场晶。從圖三中課看出其中一個(gè)藍(lán)點(diǎn)偏差太大混埠，如果把它作為支持向量的話所求出來(lái)的margin就會(huì)比不算入它時(shí)要小得多。更糟糕的情況是如果這個(gè)藍(lán)點(diǎn)落在了紅點(diǎn)之間那么就找不出超平面了诗轻。
因此引入一個(gè)松弛變量ξ來(lái)允許一些數(shù)據(jù)可以處于分隔面錯(cuò)誤的一側(cè)钳宪。這時(shí)新的約束條件變?yōu)?
式中ξi的含義為允許第i個(gè)數(shù)據(jù)點(diǎn)允許偏離的間隔。如果讓?duì)稳我獯蟮脑挵饩妫敲慈我獾某矫娑际欠蠗l件的了吏颖。所以在原有目標(biāo)的基礎(chǔ)之上，我們也盡可能的讓?duì)蔚目偭恳脖M可能地小恨樟。所以新的目標(biāo)函數(shù)變?yōu)椋?br>
其中的C是用于控制“最大化間隔”和“保證大部分的點(diǎn)的函數(shù)間隔都小于1”這兩個(gè)目標(biāo)的權(quán)重半醉。將上述模型完整的寫下來(lái)就是：
新的拉格朗日函數(shù)變?yōu)椋?br>
接下來(lái)將拉格朗日函數(shù)轉(zhuǎn)化為其對(duì)偶函數(shù)，首先對(duì)L
分別求偏導(dǎo)劝术，并令其為0,結(jié)果如下：
代入原式化簡(jiǎn)之后得到和原來(lái)一樣的目標(biāo)函數(shù)：
經(jīng)過(guò)添加松弛變量的方法缩多，我們現(xiàn)在能夠解決數(shù)據(jù)更加混亂的問(wèn)題。通過(guò)修改參數(shù)C养晋，我們可以得到不同的結(jié)果而C的大小到底取多少比較合適衬吆，需要根據(jù)實(shí)際問(wèn)題進(jìn)行調(diào)節(jié)。
2.4 核函數(shù)
以上討論的都是在線性可分情況進(jìn)行討論的绳泉，但是實(shí)際問(wèn)題中給出的數(shù)據(jù)并不是都是線性可分的逊抡，比如有些數(shù)據(jù)可能是如圖樣子。
而對(duì)于非線性的情況零酪，SVM 的處理方法是選擇一個(gè)核函數(shù) κ(?,?) 冒嫡，通過(guò)將數(shù)據(jù)映射到高維空間，來(lái)解決在原始空間中線性不可分的問(wèn)題四苇。
在線性不可分的情況下灯谣，支持向量機(jī)首先在低維空間中完成計(jì)算，然后通過(guò)核函數(shù)將輸入空間映射到高維特征空間蛔琅，最終在高維特征空間中構(gòu)造出最優(yōu)分離超平面胎许，從而把平面上本身不好分的非線性數(shù)據(jù)分開。
事實(shí)上罗售，上圖所述的這個(gè)數(shù)據(jù)集辜窑，是用兩個(gè)半徑不同的圓圈加上了少量的噪音生成得到的，所以寨躁，一個(gè)理想的分界應(yīng)該是一個(gè)“圓圈”而不是一條線（超平面）穆碎。
因此我只需要把它映射到 , , 這樣一個(gè)三維空間中即可，下圖即是映射之后的結(jié)果职恳，將坐標(biāo)軸經(jīng)過(guò)適當(dāng)?shù)男D(zhuǎn)所禀，就可以很明顯地看出方面，數(shù)據(jù)是可以通過(guò)一個(gè)平面來(lái)分開的：
上面說(shuō)了這么一大堆，讀者可能還是沒明白核函數(shù)到底是個(gè)什么東西色徘？我再簡(jiǎn)要概括下恭金，即以下三點(diǎn)：
實(shí)際中，我們會(huì)經(jīng)常遇到線性不可分的樣例褂策，此時(shí)横腿，我們的常用做法是把樣例特征映射到高維空間中去(如上文2.2節(jié)最開始的那幅圖所示，映射到高維空間后斤寂，相關(guān)特征便被分開了耿焊，也就達(dá)到了分類的目的)；
但進(jìn)一步遍搞，如果凡是遇到線性不可分的樣例罗侯，一律映射到高維空間，那么這個(gè)維度大小是會(huì)高到可怕的(如上文中19維乃至無(wú)窮維的例子)溪猿。那咋辦呢歇父？
此時(shí)，核函數(shù)就隆重登場(chǎng)了再愈，核函數(shù)的價(jià)值在于它雖然也是講特征進(jìn)行從低維到高維的轉(zhuǎn)換，但核函數(shù)絕就絕在它事先在低維上進(jìn)行計(jì)算护戳，而將實(shí)質(zhì)上的分類效果表現(xiàn)在了高維上翎冲，也就如上文所說(shuō)的避免了直接在高維空間中的復(fù)雜計(jì)算。
轉(zhuǎn)自：https://blog.csdn.net/v_july_v/article/details/7624837
