寫在前面

支持向量機(jī)是比較不容易理解的，網(wǎng)上有很多很詳盡的技術(shù)文檔，包括數(shù)學(xué)推導(dǎo)也寫得頗為全面否淤，奈何我就是怎么看也看不懂。經(jīng)過多方面學(xué)習(xí)棠隐，雖然我現(xiàn)在也還是不很懂叹括，特別是數(shù)學(xué)推導(dǎo)沒有理解，但是我意識(shí)到其實(shí)根本沒有關(guān)系宵荒，你只要能看懂結(jié)論里的公式就可以了汁雷。我用盡量簡單的語言把基本過程說清楚。假設(shè)你和最早的我一樣报咳，什么也不懂侠讯，我們開始：

不過等等，為了幫助你理解暑刃，我還是推薦一個(gè)很詳細(xì)的文檔給你們：支持向量機(jī)通俗導(dǎo)論（理解SVM的三層境界)

還有一個(gè)視頻：支持向量機(jī)在SPSS中

支持向量機(jī)

今天只說最簡單的厢漩。你就將其理解為現(xiàn)在有很多點(diǎn)，一部分的標(biāo)簽是+1岩臣，一部分的標(biāo)簽是-1溜嗜，而且這些點(diǎn)一定能被一條直線劃分成兩部分宵膨，我們的任務(wù)是“畫一條線”把不同標(biāo)簽的數(shù)據(jù)分開。如下圖所示：

中間那條關(guān)鍵的線我們叫它超平面炸宵。是的沒錯(cuò)辟躏，雖然它是一條直線，但我們還是叫它“超平面”土全。我們現(xiàn)在處理的是二維平面數(shù)據(jù)捎琐，此時(shí)超平面為一條直線。當(dāng)我們處理的是三維空間數(shù)據(jù)時(shí)裹匙，超平面就是一個(gè)平面瑞凑。而當(dāng)我們處理的是100維數(shù)據(jù)時(shí)，超平面就是一個(gè)99維的對(duì)象概页。

所有資料都將這個(gè)超平面描述為：

千萬不要認(rèn)為他就是這條直線的方程式籽御！不是這樣的。wTx+b的結(jié)果其實(shí)是個(gè)分類標(biāo)簽惰匙，我們稱 wTx+b 為分類器技掏。假設(shè)右邊橘紅色的點(diǎn)標(biāo)簽都是+1，左邊藍(lán)色的點(diǎn)都是-1徽曲，那么當(dāng)我們把具體的數(shù)據(jù)點(diǎn)零截，也就是這個(gè)具體數(shù)據(jù)點(diǎn)的(x, y)坐標(biāo)帶入wTx+b以后，輸出的結(jié)果大于+1標(biāo)簽就是+1秃臣，小于-1標(biāo)簽就是-1涧衙。比如你輸入（5, 5）這個(gè)點(diǎn)，帶入 wTx+b 可能得出+2.5奥此，那他的標(biāo)簽就是+1弧哎。（為什么是大于+1、小于-1而不是大于0稚虎、小于0我們之后講撤嫩。）從這里你也看到，本文wTx+b 中的 “x” 并不是一個(gè)數(shù)蠢终，而是一對(duì)數(shù)序攘，是(5, 5)。所以 wTx+b 中的 wT 就是一個(gè)向量寻拂，計(jì)算的時(shí)候應(yīng)該是這樣的：

所以程奠，只要我們找到向量wT和常數(shù)b，分類器就找到了祭钉，就能預(yù)測其他的數(shù)據(jù)點(diǎn)了瞄沙。不過這里有個(gè)問題，那就是我們可以畫出許多“超平面”，比如：

再比如：

那么那一個(gè)“超平面”更好呢距境？我們認(rèn)為第一個(gè)最好申尼，因?yàn)樗摹白畲箝g隔”是最大的。

中間的超平面是wTx+b=0垫桂。這個(gè)很好理解师幕，就是標(biāo)簽既不是+1，也不是-1伪货。邊界兩條直線们衙，右邊是wTx+b=+1钾怔，左邊是wTx+b=-1碱呼。這樣有一個(gè)好處，就是如果你的數(shù)據(jù)點(diǎn)帶入wTx+b算出來等于+1或者-1宗侦，那么說明這個(gè)數(shù)據(jù)點(diǎn)剛好在邊界上愚臀，我們叫這樣的點(diǎn)為“支持向量”。這里回答我們之前的那個(gè)問題矾利，為什么輸出結(jié)果是大于+1姑裂、小于-1而不是大于0、小于0男旗，因?yàn)楫?dāng)?shù)扔?1或-1時(shí)可判斷為支持向量舶斧，當(dāng)大于-1小于1時(shí)，我們認(rèn)為這個(gè)點(diǎn)處于間隔之內(nèi)察皇。這個(gè)值的絕對(duì)值越大茴厉，就越遠(yuǎn)離支持向量。

所以現(xiàn)在什荣，換句話說矾缓，我們要找到“最大間隔”下的 wT 和 b。這個(gè)“間隔”如何求呢稻爬？我給你一個(gè)公式：

分母是w的二階范數(shù)嗜闻。

不要問我這個(gè)公式怎么來的，因?yàn)槲乙膊恢牢ΤＮ铱梢越o你再貼一張圖琉雳，是我從《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》這本書上截下來的，也許你能看懂（順手強(qiáng)烈推薦這本書友瘤，真的非常好）：

想要這個(gè)間距最大翠肘，那就要讓分母最小。這里做了個(gè)等量代換商佑，把求||x||的最小值轉(zhuǎn)變?yōu)榍?.5||x||^2的最小值锯茄。（也不要問我為什么是等價(jià)的。）當(dāng)然這里是有約束條件的，就是所有你訓(xùn)練的點(diǎn)都必須在邊界以外肌幽，用數(shù)學(xué)來表示是這樣的：

所以現(xiàn)在我們是要在約束條件下求解晚碾，這個(gè)叫凸優(yōu)化問題，因?yàn)楝F(xiàn)在的目標(biāo)函數(shù)是二次的喂急，約束條件是線性的格嘁，所以它是一個(gè)凸二次規(guī)劃問題。這個(gè)在數(shù)學(xué)上有自己的方法求解廊移，是這樣的：

這是一個(gè)可編程的式子糕簿。

每一個(gè)數(shù)據(jù)點(diǎn)都對(duì)應(yīng)一個(gè) alpha ，alpha_i 和 alpha_j 表明狡孔，求最值需要alpha結(jié)對(duì)計(jì)算懂诗。話不多說，上代碼苗膝。先給3個(gè)輔助函數(shù)：

# coding=utf-8
from numpy import *

# 載入數(shù)據(jù)殃恒，對(duì)txt文件解析
def loadDataSet(fileName):
    dataMat = []
    labelMat = []
    fr = open(fileName)
    for line in fr.readlines():
        lineArr = line.strip().split('\t')
        dataMat.append([float(lineArr[0]), float(lineArr[1])])
        labelMat.append(float(lineArr[2]))
    return dataMat, labelMat

# i是alpha的下標(biāo)，m是所有alpha的數(shù)目
# 只要函數(shù)值不等于輸入值i辱揭，函數(shù)就會(huì)進(jìn)行隨機(jī)選擇
def selectJrand(i, m):
    j = i  # we want to select any J not equal to i
    while (j == i):
        j = int(random.uniform(0, m))
    return j

# 用于調(diào)整大于H或小于L的alpha值
def clipAlpha(aj, H, L):
    if aj > H:
        aj = H
    if L > aj:
        aj = L
    return aj

我給的數(shù)據(jù)是這樣的离唐，文件名叫 testSet_qiu3.txt

0.0 5.0 1
5.0 0.0 1
5.0 5.0 1
1.0 0.0 -1
0.0 1.0 -1
0.0 0.0 -1

這些數(shù)據(jù)如果畫圖出來是這樣的：

我們用肉眼可以看出超平面應(yīng)該是這樣的：

載入數(shù)據(jù)：

dataArr, labelArr = loadDataSet('ch06_Data\\testSet_qiu3.txt')

之后是關(guān)鍵，這是簡化版SMO算法：

def smoSimple(dataMatIn, classLabels, C, toler, maxIter):
    dataMatrix = mat(dataMatIn)
    labelMat = mat(classLabels).transpose()  # 轉(zhuǎn)置為列向量
    # print 'labelMat:', labelMat
    b = 0
    m, n = shape(dataMatrix)  # m行问窃，n列
    alphas = mat(zeros((m, 1)))
    iter = 0
    while (iter < maxIter):
        alphaPairsChanged = 0  # pair 一對(duì)亥鬓，成雙的
        for i in range(m):
            fXi = float(multiply(alphas, labelMat).T * (dataMatrix * dataMatrix[i, :].T)) + b
            # multiply()相當(dāng)于點(diǎn)乘
            # print 'dataMatrix:', dataMatrix
            Ei = fXi - float(labelMat[i])  # if checks if an example violates KKT conditions
            if ((labelMat[i] * Ei < -toler) and (alphas[i] < C)) or ((labelMat[i] * Ei > toler) and (alphas[i] > 0)):
                # 如果alpha可以更改，進(jìn)入優(yōu)化程序
                j = selectJrand(i, m)
                fXj = float(multiply(alphas, labelMat).T * (dataMatrix * dataMatrix[j, :].T)) + b
                Ej = fXj - float(labelMat[j])
                alphaIold = alphas[i].copy()
                alphaJold = alphas[j].copy()
                if (labelMat[i] != labelMat[j]):
                    L = max(0, alphas[j] - alphas[i])
                    H = min(C, C + alphas[j] - alphas[i])
                else:
                    L = max(0, alphas[j] + alphas[i] - C)
                    H = min(C, alphas[j] + alphas[i])
                if L == H:
                    # print "L==H"
                    continue
                eta = 2.0 * dataMatrix[i, :] * dataMatrix[j, :].T - dataMatrix[i, :] * dataMatrix[i, :].T - \
                      dataMatrix[j, :] * dataMatrix[j, :].T
                if eta >= 0:
                    # print "eta>=0"
                    continue
                alphas[j] -= labelMat[j] * (Ei - Ej) / eta
                alphas[j] = clipAlpha(alphas[j], H, L)
                # if (abs(alphas[j] - alphaJold) < 0.00001): print "j not moving enough"; continue
                alphas[i] += labelMat[j] * labelMat[i] * (alphaJold - alphas[j])  # update i by the same amount as j
                # the update is in the oppostie direction
                b1 = b - Ei - labelMat[i] * (alphas[i] - alphaIold) * dataMatrix[i, :] * dataMatrix[i, :].T \
                     - labelMat[j] * (alphas[j] - alphaJold) * dataMatrix[i, :] * dataMatrix[j, :].T
                b2 = b - Ej - labelMat[i] * (alphas[i] - alphaIold) * dataMatrix[i, :] * dataMatrix[j, :].T \
                     - labelMat[j] * (alphas[j] - alphaJold) * dataMatrix[j, :] * dataMatrix[j, :].T
                if (0 < alphas[i]) and (C > alphas[i]):
                    b = b1
                elif (0 < alphas[j]) and (C > alphas[j]):
                    b = b2
                else:
                    b = (b1 + b2) / 2.0
                alphaPairsChanged += 1
                # print "iter: %d i:%d, pairs changed %d" % (iter, i, alphaPairsChanged)
        if (alphaPairsChanged == 0):
            iter += 1
        else:
            iter = 0
            # print "iteration number: %d" % iter
    return b, alphas

smoSimple函數(shù)返回的兩個(gè)值域庇，一個(gè)b嵌戈，就是wTx+b中的b，而alphas是一個(gè)n*1的矩陣较剃，矩陣中的每一個(gè)值代表一個(gè)數(shù)據(jù)點(diǎn)對(duì)應(yīng)的alpha咕别。正常情況下這些值大部分都等于0，那些不為0的點(diǎn)就是支持向量写穴。我們這個(gè)例子因?yàn)閿?shù)據(jù)點(diǎn)比較少惰拱，所以非零值比較多。

我們輸出看一下b和alphas：

b, alphas = smoSimple(dataArr, labelArr, 0.6, 0.001, 40)
print 'b:', b
print 'alphas:', alphas

輸出結(jié)果：

b: [[-1.49897588]]
alphas: [[ 0.10818116]
 [ 0.14171643]
 [ 0.        ]
 [ 0.20878698]
 [ 0.04111061]
 [ 0.        ]]

找到alphas不是我們的目的啊送，我們的目標(biāo)是找到wT偿短。我們這樣通過alphas求wT：

# 此函數(shù)所返回的，就是 WT*X + b 中的WT
def calcWs(alphas, dataArr, classLabels):
    X = mat(dataArr)
    labelMat = mat(classLabels).transpose()
    m, n = shape(X)
    w = zeros((n, 1))
    for i in range(m):
        w += multiply(alphas[i] * labelMat[i], X[i, :].T)
    return w

看一看wT張什么樣：

>> ws = calcWs(alphas, dataArr, labelArr)
>> print ws
[[ 0.49979518]
 [ 0.49979518]]

其實(shí)就是：

[[ 0.5]
 [ 0.5]]

而b=-1.49897588馋没，其實(shí)就是-1.5嘛昔逗，所以分類器我們就可以這樣寫：

我們帶入幾個(gè)已知點(diǎn)試一下，比如篷朵，帶入(5, 0)應(yīng)該得+1勾怒，帶入(5, 5)應(yīng)該得一個(gè)大于+1的數(shù)婆排，帶入(0, 1)應(yīng)該得-1：

這樣，我們的任務(wù)就完成了笔链。（好吧段只，是最基本的任務(wù)。）

我們的822鉴扫，我們的青春
歡迎所有熱愛知識(shí)熱愛生活的朋友和822實(shí)驗(yàn)室一起成長赞枕，吃喝玩樂，享受知識(shí)坪创。