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

dinghj 2013-10-12

展開全文

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

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

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

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

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

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


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

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

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

本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購(gòu)買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊一鍵舉報(bào)。

轉(zhuǎn)藏 分享

QQ空間 QQ好友新浪微博微信

獻(xiàn)花（0） +1

來自： dinghj > 《算法編程》

舉報(bào)/認(rèn)領(lǐng)