前言:支持向量機SVM算法,以前用的不多,但是以後肯定會用得到,但是真想搞明白還是有點難度的,參考了許多大牛的文章,總算是把基本的數學原理理解的差不多,公式比較多,通過圖文的方式,總算是做了簡單的探究
支持向量機是一種分類算法,特別是針對數據集較小的的情況下,往往分類效果比神經網絡好
原理:最大特點是構造出最大間距的決策邊界,從而提高分類算法的魯棒性
使用SVM算法的思路:
一:簡單情況,線性可分情況,把問題轉化為一個凸優化問題,可以用拉格朗日乘子法簡化,然後用既有的算法解決
二:複雜情況,線性不可分,用核函數將樣本投射到高維空間,使其變成線性可分的情形,利用核函數來減少高緯度計算量。
1,線性可分的情況:
(1)分割超平面與間距
對一個數據集進行分類,構造一個分隔線把圓點和五角星分開,這個分隔線稱為分割超平面
從上圖可以看出,紅線就是最好的分割線,那些離分割超平面最近的點,稱之為支持向量,離分隔線最近的點到分隔線的距離就是間距,其中Gap就是兩倍的間距
(2)怎麼計算間距?
在二維空間中,可以使用方程
來表示一個超平面
針對高緯度空間,可以轉化成一般化的向量形式,即
我們畫出與分割超平面平行的兩條直線,分別穿過兩個類別的支持向量,如下圖:
根據點到直線的距離,可以容易地算出支持向量到分隔超平面的距離:
我們目的是為了找出一個分類效果好的超平面作為分類器。分類器的好壞的評定依據是分類間隔W=2d的大小,即分類間隔w越大,我們認為這個超平面的分類效果越好。此時,求解超平面的問題就變成了求解分類間隔W最大化的問題,W的最大化也就是d最大化的。
(3)約束條件
問題來了,我們如何判斷超平面是否將樣本點正確分類?
這個二維平面上有兩種點,我們分別對它們進行標記:
紅顏色的圓點標記為1,我們人為規定其為正樣本;
藍顏色的五角星標記為-1,我們人為規定其為負樣本。
針對上圖,我們可以看出,對於紅點x,必定滿足
對於五角星x,必定滿足
因此,針對數據集中所有的樣本x,y,如果我們的超平面方程能夠完全正確地對樣本點進行分類,就會滿足下面的方程:
標籤為1和-1,我們將約束條件變成一個約束方程
(4)目標函數:
我們的優化目標是是d最大化。我們已經說過,我們是用支持向量上的樣本點求解d的最大化的問題的。那麼支持向量上的樣本點有什麼特點呢?
支持樣本點分佈在超平面
這樣,支持向量到達我們要優化的超平面 距離就是1/∥ω∥,間距就是2/∥ω∥現在我們可以將目標函數進一步優化:
我們只關心支持向量上的點。隨後我們求解d的最大化問題變成了||w||的最小化問題。進而||w||的最小化問題等效於(加上約束條件):
這裡n是樣本點的總個數,縮寫s.t.表示"Subject to",是"服從某某條件"的意思。上述公式描述的是一個典型的不等式約束條件下的二次型函數優化問題,同時也是支持向量機的基本數學模型。
注:在邏輯迴歸中使用0和1座位類別標籤,而在支持向量機中,我們使用1和-1作為類別標籤,其目的都是為了讓數學表達式儘量簡潔
一句話總結:求解SVM算法,就是在滿足約束條件的前提下,求解
的最小值
2,線性不可分
(1)鬆弛係數
如果針對不可分的數據集,針對可分數據集的方法就失效了,因為無法找到最大間距的分割超平面,
解決辦法:引入一個參數,稱為鬆弛係數ξi,然後可以把目標函數變成:
其中N為數據集個數,C為算法參數,約束條件相應地變成:
怎樣理解鬆弛係數?我們可以把ξi理解為數據樣本X違反最大間距規則的程度,針對大部分正常的樣本,即滿足約束條件的樣本ξ=0,而對部分違反最大間距規則的樣本ξ>0,參數C表示對違反最大間距規則樣本的'懲罰'力度,當C比較大的時候,對於違反規則的點的懲罰力度將變得很大,C比較小的時候,對於違反規則的點,其付出的代價不是特別大,一般模型會傾向於允許部分樣本違反最大間距規則
其實鬆弛係數類似邏輯迴歸中的正則項,目的都是為了糾正過擬合問題,讓支持向量機對噪聲數據有更強的適應性。
(2)拉格朗日乘子法
拉格朗日乘子法是解決在約束條件下,求函數極值的理想方法,其方法是引入非負係數α作為權重作為約束條件的權重:
針對每一個樣本集X,y都有一個αi與之對應,極值處偏導數為0,求L對w,b的偏導數,並等於0:
得到:
怎樣求最小值,廣泛的應用是SMO(序列最小化算法)
注:最好求解處理的α有個明顯特點,即大部分都是0,因為只有那些支持向量所對應的樣本直接決定了間距的大小,其他的樣本離分隔超平面太遠,對間距沒什麼影響。
(2)核函數
最簡單的核函數:我們注意到,L中有
其實它是一個數值,是兩個輸入特徵向量的內積,我們把它稱之為核函數,他的物理意義是衡量兩個向量的相似性。
為什麼要引入核函數?
假設有一個數據集,只有一個特徵,是線性不可分,要對這個數據集分類,這時候很難找一個超平面來分隔這個數據集。
為了解決這個問題,我們可以用一定規則把這些無法進行線性分隔的樣本映射到更高維度的空間裡,在高緯度空間找出分隔超平面,SVM的核函數就是為了實現這種相似性映射。假如我們一個[x]變量,把他變成二維的,就是變成[x,2x**2],此時就變成二維的向量,進行這種特徵映射的函數為
這樣原來在低緯度運算的,就可以轉化為高緯度空間的相似性運算
核函數和相似性函數有什麼關係?
相似性函數是映射函數,而核函數定義為特徵向量的內積,即
在實際運算中我們不會計算相似性函數及其映射值,因為這樣計算量很大
從二維空間擴展到多維,可以使用某種非線性的方法,讓空間從原本的線性空間映射到另一個維度更高的空間,在這個高維的線性空間中,再用一個超平面對樣本進行劃分,這種情況下,相當於增加了不同樣本間的區分度和區分條件。在這個過程中,核函數發揮了至關重要的作用,就是為了實現這種相似性映射,核函數的作用就是在保證不增加算法複雜度的情況下將完全不可分問題轉化為可分或達到近似可分的狀態。
如下圖:
閱讀更多 愛數據的小司機 的文章