數(shù)據(jù)挖掘十大經(jīng)典算法(3)：SVM支持向量機

dinghj 2013-10-12

展開全文

支持向量機（SVM，Support Vector Machine）是具有深厚數(shù)學原理支持的分類算法，本文只討論0/1分類問題。SVM的基本概念如下圖所示。將觀測的每一個特征看做一個維度，n個特征就組成n個維度空間。示意圖中n=2。在這個n維空間中，如果我們能夠找到一個線性分割平面，將觀測分離開來，稱樣本線性可分。我們先討論線性可分的情況，然后再討論如何處理線性不可分的情況。

線性可分情況
對于一個分割平面，我們定義正例或負例與平面的最小距離為間隔（我們要求平面位于正例和負例的中央，是的正例到平面的最小距離等于負例到平面的最小距離）。一個好的分割平面，應(yīng)該使間隔越大越好。上圖中，右邊的分割平面就比左邊的好。落在途中虛線上的樣本點稱為支持向量。
正例屬于類別1，標示為+1，負例屬于類別0，標示為-1。則分割平面的表達式可以獲得，具體式子見下圖中的紅實線。為了能夠獲得唯一的w和b，我們需要設(shè)定一個約束條件，這里的假設(shè)是支持向量滿足如圖中紅色虛線所示的方程。在此約束下，間隔可以用下圖的右下角式子表示。

現(xiàn)在我們可以用數(shù)學規(guī)劃的語言描述支持向量機的分類問題。我們的目標是最大化margin，約束是上圖兩條虛線內(nèi)部沒有觀測。具體的模型如下圖所示。

    這樣一來，SVM分類問題轉(zhuǎn)化為二次規(guī)劃。該問題的最優(yōu)解需要滿足K-T條件（庫恩-塔克條件，參看運籌學的非線性規(guī)劃）。K-T條件的內(nèi)容大致如下：目標函數(shù)關(guān)于w和b的梯度需要是支持向量約束梯度的線性組合。通過K-T條件，可以發(fā)現(xiàn)w可以用向量的內(nèi)積表示。原來的思路是：新來的觀測要分類，首先根據(jù)w和b做一次線性運算，然后看求解結(jié)果，若大于0，屬于類別1，若小于0，屬于類別0.現(xiàn)在的思路變?yōu)椋焊鶕?jù)支持向量約束梯度的線性組合系數(shù)，只要將新觀測和訓練數(shù)據(jù)中的支持向量做內(nèi)積即可。

線性不可分情況
    線性不可分情況有兩種做法。第一種是把原來的低維空間向高維空間映射，使得數(shù)據(jù)在高維空間中變?yōu)榫€性可分。這時候可以給予上面說的內(nèi)積性質(zhì)，利用核函數(shù)，仍然在低維空間做運算，達到高維空間做運算的效果，降低算法復(fù)雜度。
    然而，這種向高維映射的方法不能保證百分百成功，因此還引入了軟間隔的概念，即允許在margin內(nèi)部出現(xiàn)離群點，但在目標函數(shù)中加入懲罰函數(shù)，離群點越多程度越高，懲罰越厲害。


關(guān)于應(yīng)用K-T條件得到內(nèi)積性質(zhì)、核函數(shù)、軟間隔，可以參考網(wǎng)站：http://www.cnblogs.com/jerrylead/

本文所采用圖片均來自清華大學計算機系王建勇老師的課程《數(shù)據(jù)挖掘：原理與算法》

http://dbgroup.cs./wangjy/DM/DataMining.html