支持向量機(jī) Support Vector Machine

支持向量機(jī)（SVM）是90年代中期發(fā)展起來的基于統(tǒng)計(jì)學(xué)習(xí)理論的一種機(jī)器學(xué)習(xí)方法柄粹，通過尋求結(jié)構(gòu)化風(fēng)險(xiǎn)最小來提高學(xué)習(xí)機(jī)泛化能力屎篱，實(shí)現(xiàn)經(jīng)驗(yàn)風(fēng)險(xiǎn)和置信范圍的最小化芋绸，從而達(dá)到在統(tǒng)計(jì)樣本量較少的情況下，亦能獲得良好統(tǒng)計(jì)規(guī)律的目的迁客。

通俗來講郭宝，它是一種二類分類模型，其基本模型定義為特征空間上的間隔最大的線性分類器掷漱，即支持向量機(jī)的學(xué)習(xí)策略便是間隔最大化粘室，最終可轉(zhuǎn)化為一個(gè)凸二次規(guī)劃問題的求解。

線性分割
kernel trick 核技巧卜范，多特征衔统，將x,y映射到多維空間進(jìn)行特征分割，之后再返回二維空間形成非線性分割線海雪。核函數(shù)表示將輸入從輸入空間映射到特征空間得到的特征向量之間的內(nèi)積锦爵。

image

什么是支持向量

訓(xùn)練數(shù)據(jù)集中與分離超平面距離最近的樣本點(diǎn)的實(shí)例稱為支持向量。支持向量在分離超平面時(shí)起決定作用奥裸，所以叫支持向量機(jī)险掀。
更通俗的解釋：
- 數(shù)據(jù)集中的某些點(diǎn)，位置比較特殊湾宙。比如 x+y-2=0 這條直線樟氢，假設(shè)出現(xiàn)在直線上方的樣本記為 A 類，下方的記為 B 類创倔。
- 在尋找找這條直線的時(shí)候嗡害，一般只需看兩類數(shù)據(jù)，它們各自最靠近劃分直線的那些點(diǎn)畦攘，而其他的點(diǎn)起不了決定作用。
- 這些點(diǎn)就是所謂的“支持點(diǎn)”十电，在數(shù)學(xué)中知押，這些點(diǎn)稱為向量，所以更正式的名稱為“支持向量”鹃骂。

支持向量機(jī)的分類

線性可分支持向量機(jī)
- 當(dāng)訓(xùn)練數(shù)據(jù)線性可分時(shí)台盯，通過硬間隔最大化，學(xué)習(xí)一個(gè)線性分類器畏线，即線性可分支持向量機(jī)静盅，又稱硬間隔支持向量機(jī)。
線性支持向量機(jī)
- 當(dāng)訓(xùn)練數(shù)據(jù)接近線性可分時(shí)，通過軟間隔最大化蒿叠，學(xué)習(xí)一個(gè)線性分類器明垢，即線性支持向量機(jī)，又稱軟間隔支持向量機(jī)市咽。
非線性支持向量機(jī)
- 當(dāng)訓(xùn)練數(shù)據(jù)線性不可分時(shí)痊银，通過使用核技巧及軟間隔最大化，學(xué)習(xí)非線性支持向量機(jī)施绎。

線性可分支持向量機(jī)

線性可分 ：存在一個(gè)超平面使得數(shù)據(jù)集中的正負(fù)樣本正確劃分到超平面的兩側(cè)溯革。
當(dāng)訓(xùn)練數(shù)據(jù)線性可分時(shí)，通過硬間隔最大化谷醉，學(xué)習(xí)一個(gè)線性分類器致稀，即線性可分支持向量機(jī)，又稱硬間隔支持向量機(jī)俱尼。感知機(jī)模型抖单，即誤差最小化的模型來求分離超平面的解有無窮多個(gè)。利用間隔最大化求解最優(yōu)分離超平面号显，這時(shí)臭猜，解是唯一的。

image

線性 SVM 的推導(dǎo)分為兩部分
1. 如何根據(jù)間隔最大化的目標(biāo)導(dǎo)出 SVM 的標(biāo)準(zhǔn)問題押蚤；
2. 拉格朗日乘子法對(duì)偶問題的求解過程.

定義

訓(xùn)練集 T

y 為 1 或者 -1蔑歌，正負(fù)樣本
分離超平面 (w,b)

如果使用映射函數(shù)，那么分離超平面為

映射函數(shù) Φ(x) 定義了從輸入空間到特征空間的變換揽碘，特征空間通常是更高維的次屠，甚至無窮維；方便起見雳刺，這里假設(shè) Φ(x) 做的是恒等變換劫灶。

分類決策函數(shù) f(x)

公式推導(dǎo)

從“函數(shù)間隔”到“幾何間隔”

給定訓(xùn)練集T和超平面(w,b)，定義函數(shù)間隔γ^：

對(duì) w 作規(guī)范化掖桦，使函數(shù)間隔成為幾何間隔γ

最大化幾何間隔

對(duì)訓(xùn)練數(shù)據(jù)集找到幾何間隔最大的超平面意味著以充分大的確信度對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行分類本昏。即，不僅將正負(fù)實(shí)例點(diǎn)分開枪汪，而且對(duì)于最難分的點(diǎn)也有足夠大的確信度將它們分開涌穆。這樣對(duì)未知的新實(shí)例有很好的分類預(yù)測(cè)能力。

由函數(shù)間隔與幾何間隔的關(guān)系雀久，等價(jià)于

函數(shù)間隔γ^的取值不會(huì)影響最終的超平面(w,b)：取γ^=1宿稀；又最大化 1/||w|| 等價(jià)于最小化1/2*||w||^2，于是有

為什么令γ^=1赖捌？——比例改變(ω,b)祝沸，超平面不會(huì)改變，但函數(shù)間隔γ^會(huì)成比例改變，因此可以通過等比例改變(ω,b)使函數(shù)間隔γ^=1

該約束最優(yōu)化問題即為線性支持向量機(jī)的標(biāo)準(zhǔn)問題——這是一個(gè)凸二次優(yōu)化問題罩锐，可以使用商業(yè) QP 代碼完成奉狈。

理論上，線性 SVM 的問題已經(jīng)解決了唯欣；但在高等數(shù)學(xué)中嘹吨，帶約束的最優(yōu)化問題還可以用另一種方法求解——拉格朗日乘子法。該方法的優(yōu)點(diǎn)一是更容易求解境氢，而是自然引入核函數(shù)蟀拷，進(jìn)而推廣到非線性的情況。

構(gòu)建拉格朗日函數(shù)

標(biāo)準(zhǔn)問題是求極小極大問題：

其對(duì)偶問題為：

求 L 對(duì) (w,b) 的極小

結(jié)果代入L萍聊，有：

求 L 對(duì) α 的極大问芬，即

該問題的對(duì)偶問題為：

于是，標(biāo)準(zhǔn)問題最后等價(jià)于求解該對(duì)偶問題

繼續(xù)求解該優(yōu)化問題寿桨，有 SMO 方法此衅；因?yàn)椤督y(tǒng)計(jì)學(xué)習(xí)方法》也只討論到這里，故推導(dǎo)也止于此

設(shè) α 的解為 α*亭螟，則存在下標(biāo)j使α_j > 0挡鞍，可得標(biāo)準(zhǔn)問題的解為：

可得分離超平面及分類決策函數(shù)為：

線性支持向量機(jī)

即在線性可分向量機(jī)的基礎(chǔ)上，增加懲罰參數(shù)和松弛變量预烙，使模型可以排除一些特異點(diǎn)之后線性可分墨微，使軟間隔最大化。

非線性支持向量機(jī)

非線性問題所采用的方法是進(jìn)行非線性變換扁掸，將非線性問題轉(zhuǎn)化為線性問題翘县。

多項(xiàng)式和函數(shù)
高斯核函數(shù)
字符串核函數(shù)

使用 sklearn 實(shí)戰(zhàn)

調(diào)參

在 rbf 核下，分別使用10谴分、100锈麸、1000、10000的C參數(shù)進(jìn)行調(diào)整輸出準(zhǔn)確率牺蹄。
使用1%的數(shù)據(jù)集忘伞。

C參數(shù)：低C使決策表面平滑，而高C旨在通過給予模型自由選擇更多樣本作為支持向量來正確地分類所有訓(xùn)練樣本沙兰。

features_train = features_train[:len(features_train)/100]
labels_train = labels_train[:len(labels_train)/100]

結(jié)果如下

C=10.0 accuracy=0.616040955631
C=100.0 accuracy=0.616040955631
C=1000. accuracy=0.821387940842
C=10000. accuracy=0.892491467577

結(jié)果計(jì)算

在全數(shù)據(jù)集下虑省，進(jìn)行準(zhǔn)確度計(jì)算，并計(jì)算預(yù)測(cè)為Chris郵件的個(gè)數(shù)

#!/usr/bin/python

""" 
    This is the code to accompany the Lesson 2 (SVM) mini-project.

    Use a SVM to identify emails from the Enron corpus by their authors:    
    Sara has label 0
    Chris has label 1
"""
    
import sys
from time import time
sys.path.append("../tools/")
from email_preprocess import preprocess


### features_train and features_test are the features for the training
### and testing datasets, respectively
### labels_train and labels_test are the corresponding item labels
features_train, features_test, labels_train, labels_test = preprocess()

# reduce training data
#features_train = features_train[:len(features_train)/100]
#labels_train = labels_train[:len(labels_train)/100]


#########################################################
### your code goes here ###
from sklearn.svm import SVC
clf = SVC(kernel='rbf',C=10000.)


#### now your job is to fit the classifier
#### using the training features/labels, and to
#### make a set of predictions on the test data
t0 = time()
clf.fit(features_train,labels_train)
print "training time : " ,round(time()-t0,3),"s"

#### store your predictions in a list named pred
t1 = time()
pred = clf.predict(features_test)
print "predicting time : " ,round(time()-t1,3),"s"

from sklearn.metrics import accuracy_score
acc = accuracy_score(pred, labels_test)
print "accuracy: ", acc

# answer1=pred[10]
# answer2=pred[26]
# answer3=pred[50]

num = 0
for n in pred:
    if n == 1:
        num = num + 1

print "total Chris(1): ", num
#########################################################