摘要：本篇內(nèi)容為機(jī)器學(xué)習(xí)實(shí)戰(zhàn)第章支持向量機(jī)部分程序清單。支持向量機(jī)優(yōu)點(diǎn)泛化錯(cuò)誤率低，計(jì)算開銷不大，結(jié)果易解釋。注以上給出的僅是簡(jiǎn)化版算法的實(shí)現(xiàn)，關(guān)于完整的算法加速優(yōu)化并應(yīng)用核函數(shù)，請(qǐng)參照機(jī)器學(xué)習(xí)實(shí)戰(zhàn)第頁(yè)。

本篇內(nèi)容為《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》第 6 章 支持向量機(jī)部分程序清單。所用代碼為 python3。

支持向量機(jī)
優(yōu)點(diǎn)：泛化錯(cuò)誤率低，計(jì)算開銷不大，結(jié)果易解釋。 
缺點(diǎn)：對(duì)參數(shù)調(diào)節(jié)和核函數(shù)的選擇敏感，原始分類器不加修改僅適用于處理二分類問題。
適用數(shù)據(jù)類型：數(shù)值型和標(biāo)稱型數(shù)據(jù)。

1996 年，John Platt 發(fā)布了一個(gè)稱為SMO的強(qiáng)大算法，用于訓(xùn)練 SVM。SMO表示序列最小優(yōu)化 (Sequential Minimal Optimization)。

SMO算法的工作原理是：每次循環(huán)中選擇兩個(gè)alpha進(jìn)行優(yōu)化處理。一旦找到一對(duì)合適的alpha，那么就增大其中一個(gè)同時(shí)減小另一個(gè)。這里的“合適”是指兩個(gè)alpha必須要符合一定的條件，第一個(gè)條件是這兩個(gè)alpha必須要在間隔邊界之外，第二個(gè)條件是這兩個(gè)alpha還沒有進(jìn)行過區(qū)間化處理或者不在邊界上。

下面給出簡(jiǎn)化版的SMO算法程序清單。

該SMO函數(shù)的偽代碼如下：
創(chuàng)建一個(gè)alpha向量并將其初始化為 0 向量
當(dāng)?shù)螖?shù)小于最大迭代次數(shù)時(shí)（外循環(huán)）
···對(duì)數(shù)據(jù)集中的每個(gè)數(shù)據(jù)向量（內(nèi)循環(huán)）：
······如果該數(shù)據(jù)向量可以被優(yōu)化：
·········隨機(jī)選擇另外一個(gè)數(shù)據(jù)向量
·········同時(shí)優(yōu)化這兩個(gè)向量
·········如果兩個(gè)向量都不能被優(yōu)化，退出內(nèi)循環(huán)
···如果所有向量都沒被優(yōu)化，增加迭代數(shù)目，繼續(xù)下一次循環(huán)

# coding=utf-8
# import sys
from numpy import *

def loadDataSet():
    dataMat = []
    labelMat = []
    fr = open("testSet.txt")

    for line in fr.readlines():
        lineArr = line.strip().split("	")
        dataMat.append([float(lineArr[0]), float(lineArr[1])])
        labelMat.append(float(lineArr[2]))
    return dataMat, labelMat


# i 是第一個(gè) alpha 的下標(biāo)， m 是所有 alpha 的數(shù)目
# 只要函數(shù)值不等于輸入值 i，函數(shù)就會(huì)進(jìn)行隨機(jī)選擇
def selectJrand(i, m):
    j = 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

在 python 提示符下，執(zhí)行代碼并得到結(jié)果：

>>> import svmMLiA
>>> dataArr, labelArr = svmMLiA.loadDataSet()
>>> labelArr
[-1.0, -1.0, 1.0, -1.0, 1.0, 1.0, 1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, 1.0, -1.0, 1.0, 1.0, -1.0, 1.0, -1.0, -1.0, -1.0, 1.0, -1.0, -1.0, 1.0, 1.0, -1.0, -1.0, -1.0, -1.0, 1.0, 1.0, 1.0, 1.0, -1.0, 1.0, -1.0, -1.0, 1.0, -1.0, -1.0, -1.0, -1.0, 1.0, 1.0, 1.0, 1.0, 1.0, -1.0, 1.0, 1.0, -1.0, -1.0, 1.0, 1.0, -1.0, 1.0, -1.0, -1.0, -1.0, -1.0, 1.0, -1.0, 1.0, -1.0, -1.0, 1.0, 1.0, 1.0, -1.0, 1.0, 1.0, -1.0, -1.0, 1.0, -1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, -1.0, -1.0, -1.0, -1.0, 1.0, -1.0, 1.0, 1.0, 1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0]

可以看出，這里采用的類別標(biāo)簽是 -1 和 1。

# 參數(shù)：數(shù)據(jù)集，類別標(biāo)簽，常數(shù)C，容錯(cuò)率，退出前最大的循環(huán)次數(shù)
def smoSimple(dataMatIn, classLabels, C, toler, maxIter):
    dataMatrix = mat(dataMatIn)
    # 由于轉(zhuǎn)置了類別標(biāo)簽，我們得到的是一個(gè)列向量而不是列表
    labelMat = mat(classLabels).transpose()
    b = 0
    m,n = shape(dataMatrix)
    # 構(gòu)建一個(gè) alpha 列矩陣，矩陣中元素都初始化為0
    alphas = mat(zeros((m, 1)))
    # iter 變量存儲(chǔ)的是在沒有任何 alpha 改變的情況下便利數(shù)據(jù)集的次數(shù)
    # 當(dāng)這個(gè)變量達(dá)到輸入值 maxIter 時(shí)，函數(shù)結(jié)束運(yùn)行并退出
    iter = 0

    while(iter < maxIter):

        # 每次循環(huán)當(dāng)中，將 alphaPairsChanged 先設(shè)為0，在對(duì)整個(gè)集合順序遍歷
        # 變量 alphaPairsChanged 用于記錄 alpha 是否已經(jīng)進(jìn)行優(yōu)化
        alphaPairsChanged = 0
        for i in range(m):
            # 計(jì)算 fXi，即我們預(yù)測(cè)的類別
            fXi = float(multiply(alphas, labelMat).T * (dataMatrix*dataMatrix[i,:].T) + b)
            # 與真實(shí)值比對(duì)，計(jì)算誤差 Ei
            Ei = fXi - float(labelMat[i])
            # 如果誤差很大，可以對(duì)該數(shù)據(jù)實(shí)例所對(duì)應(yīng)的 alpha 值進(jìn)行優(yōu)化

            # 不論正間隔還是負(fù)間隔都會(huì)被測(cè)試
            # 檢查 alpha 值，保證其不能等于 0 或 C
            if((labelMat[i]*Ei < -toler) and (alphas[i] < C)
               or (labelMat[i]*Ei > toler) and (alphas[i] > 0)):

                # 用輔助函數(shù) selectJrand 隨機(jī)選擇第二個(gè) alpha 值，即 alpha[j]
                j = selectJrand(i,m)
                # 同樣計(jì)算誤差
                fXj = float(multiply(alphas, labelMat).T * (dataMatrix*dataMatrix[j,:].T)) + b
                Ej = fXj - float(labelMat[j])
                alphaIold = alphas[i].copy()
                alphaJold = alphas[j].copy()

                # 計(jì)算 L 和 H，調(diào)整 alpha 到 0 與 C 之間
                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 是 alpha[j] 的最優(yōu)修改量
                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

                # 計(jì)算出一個(gè)新的 alpha[j]，并進(jìn)行調(diào)整
                alphas[j] -= labelMat[j] * (Ei - Ej) / eta
                alphas[j] = clipAlpha(alphas[j], H, L)

                # 檢查 alpha[j] 是否有輕微改變，是的話則退出 for 循環(huán)
                if(abs(alphas[j] - alphaJold) < 0.00001):
                    print("j not moving enough")
                    continue

                # 對(duì) alpha[i] 進(jìn)行和 alpha[j] 同樣的改變
                # 改變的大小一樣，方向正好相反
                alphas[i] += labelMat[j] * labelMat[i] * (alphaJold - alphas[j])

                # 對(duì) alpha[i] 和 alpha[j] 進(jìn)行優(yōu)化之后，給它們?cè)O(shè)置一個(gè)常數(shù)項(xiàng) b
                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(alphaPairsChanged == 0):
            iter += 1
        else:
            iter = 0
        print("iteration number: %d" % iter)
    return b, alphas

在 python 提示符下，執(zhí)行代碼并得到結(jié)果：

b, alphas = svmMLiA.smoSimple(dataArr, labelArr, 0.6, 0.001, 40)

再執(zhí)行：

>>> for i in range(100):
...     if alphas[i] > 0.0:
...             print(dataArr[i], labelArr[i])
... 
[3.542485, 1.977398] -1.0
[7.108772, -0.986906] 1.0
[4.658191, 3.507396] -1.0
[7.40786, -0.121961] 1.0
[3.457096, -0.082216] -1.0
[5.286862, -2.358286] 1.0
[6.080573, 0.418886] 1.0
[6.543888, 0.433164] 1.0
[1.966279, -1.840439] -1.0

所輸出的數(shù)據(jù)點(diǎn)即為支持向量。

注：以上給出的僅是簡(jiǎn)化版SMO算法的實(shí)現(xiàn)，關(guān)于完整的SMO算法加速優(yōu)化并應(yīng)用核函數(shù)，請(qǐng)參照《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》第 99 頁(yè)。

不足之處，歡迎指正。