这一章的内容非常多，在神经网络大火前，SVM是最优秀的机器学习算法，尽管现在已经很少用了，但作为一本七年前的书还是很详细的讲解了，所以这里简单的记录下。

基于最大间隔分隔数据

支持向量机

优点：泛化错误率低，计算开销不大，结果易理解
缺点：对参数调节和核函数选择敏感，原始分类器不加修改仅适用于处理二分类问题
适用数据类型：数值型和标称型数据

线性不可分的数据集

观察上图图发现我们不能画出一条线或者圆把圆形和方形的数据分割开，而下图可以画出一条直线将两组数据分开。所以下图的数据称为线性可分（linearly separable）。

线性可分的数据集

将数据集分开的直线称为分割超平面（separating hyperplane）。上面给出的例子数据都在二维平面上，所以分割超平面是一条直线，如果所给的数据是三维的，那么分割数据的就是一个平面。如果数据集是一个1024维的，那就需要一个1023维的对象对数据分割。如果一个数据集是N维的，需要一个N-1维的超平面分割。

支持向量（support vector）就是离分割超平面最近的那些点。

寻找最大间隔

How can we measure the line that best separates the data? To start with, look at figure 6.3. Our separating hyperplane has the form wTx+b. If we want to find the distance from A to the separating plane, we must measure normal or perpendicular to the line. This is given by |wTA+b|/||w||. The constant b is just an offset like w0 in logistic regression. All this w and b stuff describes the separating line, or hyperplane, for our data. Now, let’s talk about the classifier.

线性可分的数据集

分类器求解的优化问题

SVM应用的一般框架

SVM的一般流程

收集数据
准备数据：需要数值型数据
分析数据：有助于可视化分割超平面
训练算法：SVM大大部分时间都源自训练，该过程主要实现两个参数的调优
测试算法：十分简单的计算过程就可以实现
适用算法：几乎所有分类问题都可以适用SVM，值得一提的是，SVM本身是一个二分类分类器，对多分类问题SVM需要对代码修改

SMO高效优化算法

SMO表示序列最小优化（Sequential Minimal Optimization）

SMO算法的目标是求出一系列alpha和b，一旦求出了这些alpha，就很容易计算处权重向量w并得到分割超平面。

SMO算法的工作原理是：每次循环中选择两个alpha进行优化处理。一旦找到一
对合适的alpha，那么就增大其中一个同时减小另一个。这里所谓的合适们就是指两个alpha必须要符合两个条件，一，两个alpha必须要在间隔边界之外，二，两个alpha还没有进行过区间化处理或者不在边界上。

应用简化版SMO算法处理小规模数据集

$$\Sigma\alpha*label^{i} = 0$$

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]))
    fr.close()
    return dataMat, labelMat

def selectJrand(i, m):
    j = i
    while (j == i):
        j = int(random.uniform(0, m))
    return j

def clipAlpha(aj, H, L):
    if aj > H:
        aj = H
    if L > aj:
        aj = L
    return aj

1 2	dataArr, labelArr = loadDataSet('MLiA_SourceCode/machinelearninginaction/Ch06/testSet.txt') labelArr[:10]

[-1.0, -1.0, 1.0, -1.0, 1.0, 1.0, 1.0, -1.0, -1.0, -1.0]

selectJrand()有两个参数，i是第一个alpha的下表，m是所有alpha的数目，只要函数值不等于输入值i，函数就会随机选择

clipAlpha()的作用是调整alpha的值在H和L之间。

SMO伪代码大致如下：

创建一个alpha向量并将其初始化为0向量
当迭代次数小于最大迭代次数时（外循环）
    对数据集中的每个数据向量（内循环）：
        如果给数据向量可以被优化：
            随机选择另外一个数据向量
            如果优化这两个向量
            如果两个向量都不能被优化，退出内循环
    如果所有向量都没被优化，增加迭代数目，继续下一次循环

from numpy import *
def smoSimple(dataMatIn, classLabels, C, toler, maxIter):
    dataMatrix = mat(dataMatIn)
    labelMat = mat(classLabels).transpose()
    b = 0
    m,n = shape(dataMatrix)
    alphas = mat(zeros((m,1)))
    iter = 0
    
    while (iter < maxIter):
        alphaPairsChanged = 0
        for i in range(m):
            fXi = float(multiply(alphas,labelMat).T*(dataMatrix*dataMatrix[i,:].T)) + b
            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)):
                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

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

L==H
L==H
iter: 0 i:2, pairs changed 1
iter: 0 i:3, pairs changed 2
L==H
...
...
iteration number: 39
j not moving enough
j not moving enough
j not moving enough
iteration number: 40

matrix([[-3.79661253]])

1	alphas[alphas>0]

matrix([[0.12629181, 0.24169497, 0.36797683]])

1	shape(alphas[alphas>0])

(1, 3)

supportVectors = []
for i in range(100):
    if alphas[i] > 0.0:
        supportVectors.append(dataArr[i])
        print(dataArr[i], labelArr[i])

[4.658191, 3.507396] -1.0
[3.457096, -0.082216] -1.0
[6.080573, 0.418886] 1.0

import matplotlib
import matplotlib.pyplot as plt
from matplotlib.patches import Circle
plt.rcParams['axes.unicode_minus']=False # 用来正常显示负号

def plotSupportVectors(supportVectors):
    xcord0 = []
    ycord0 = []
    xcord1 = []
    ycord1 = []
    markers =[]
    colors =[]
    fr = open('MLiA_SourceCode/machinelearninginaction/Ch06/testSet.txt')
    for line in fr.readlines():
        lineSplit = line.strip().split('\t')
        xPt = float(lineSplit[0])
        yPt = float(lineSplit[1])
        label = int(lineSplit[2])
        if (label == -1):
            xcord0.append(xPt)
            ycord0.append(yPt)
        else:
            xcord1.append(xPt)
            ycord1.append(yPt)

    fr.close()
    fig = plt.figure()
    ax = fig.add_subplot(111)
    ax.scatter(xcord0,ycord0, marker='s', s=90)
    ax.scatter(xcord1,ycord1, marker='o', s=50, c='red')
    plt.title('Support Vectors Circled')
    for vector in supportVectors:
        circle = Circle(vector, 0.5, facecolor='none', edgecolor=(0,0.8,0.8), linewidth=2, alpha=0.5)
        ax.add_patch(circle)

    #plt.plot([2.3,8.5], [-6,6]) #seperating hyperplane
    b = -3.75567; w0=0.8065; w1=-0.2761
    x = arange(-2.0, 12.0, 0.1)
    y = (-w0*x - b)/w1
    ax.plot(x,y)
    ax.axis([-2,12,-8,6])
    plt.show()

圈出支持向量

1	plotSupportVectors(supportVectors)

png

利用完整的SMO算法加速优化

class optStruct:
    def __init__(self,dataMatIn, classLabels, C, toler, kTup):  # Initialize the structure with the parameters 
        self.X = dataMatIn
        self.labelMat = classLabels
        self.C = C
        self.tol = toler
        self.m = shape(dataMatIn)[0]
        self.alphas = mat(zeros((self.m,1)))
        self.b = 0
        self.eCache = mat(zeros((self.m,2))) #first column is valid flag
        
def calcEk(oS, k):
    fXk = float(multiply(oS.alphas, oS.labelMat).T*(oS.X*oS.X[k, :].T)) + oS.b
    Ek = fXk - float(oS.labelMat[k])
    return Ek
        
def selectJ(i, oS, Ei):         #this is the second choice -heurstic, and calcs Ej
    maxK = -1; maxDeltaE = 0; Ej = 0
    oS.eCache[i] = [1,Ei]  #set valid #choose the alpha that gives the maximum delta E
    validEcacheList = nonzero(oS.eCache[:,0].A)[0]
    if (len(validEcacheList)) > 1:
        for k in validEcacheList:   #loop through valid Ecache values and find the one that maximizes delta E
            if k == i: continue #don't calc for i, waste of time
            Ek = calcEk(oS, k)
            deltaE = abs(Ei - Ek)
            if (deltaE > maxDeltaE):
                maxK = k; maxDeltaE = deltaE; Ej = Ek
        return maxK, Ej
    else:   #in this case (first time around) we don't have any valid eCache values
        j = selectJrand(i, oS.m)
        Ej = calcEk(oS, j)
    return j, Ej

def updateEk(oS, k):#after any alpha has changed update the new value in the cache
    Ek = calcEk(oS, k)
    oS.eCache[k] = [1,Ek]

def innerL(i, oS, istraces=True):
    Ei = calcEk(oS, i)
    if ((oS.labelMat[i]*Ei < -oS.tol) and (oS.alphas[i] < oS.C)) or ((oS.labelMat[i]*Ei > oS.tol) and (oS.alphas[i] > 0)):
        j,Ej = selectJ(i, oS, Ei) #this has been changed from selectJrand
        alphaIold = oS.alphas[i].copy(); alphaJold = oS.alphas[j].copy();
        if (oS.labelMat[i] != oS.labelMat[j]):
            L = max(0, oS.alphas[j] - oS.alphas[i])
            H = min(oS.C, oS.C + oS.alphas[j] - oS.alphas[i])
        else:
            L = max(0, oS.alphas[j] + oS.alphas[i] - oS.C)
            H = min(oS.C, oS.alphas[j] + oS.alphas[i])

        if L==H:
            if istraces: 
                print("L==H")
            return 0

        eta = 2.0 * oS.X[i,:]*oS.X[j,:].T - oS.X[i,:]*oS.X[i,:].T - oS.X[j,:]*oS.X[j,:].T
        if eta >= 0:
            if istraces: 
                print("eta>=0")
            return 0

        oS.alphas[j] -= oS.labelMat[j]*(Ei - Ej)/eta
        oS.alphas[j] = clipAlpha(oS.alphas[j],H,L)
        updateEk(oS, j) # added this for the Ecache
        
        if (abs(oS.alphas[j] - alphaJold) < 0.00001):
            if istraces: 
                print("j not moving enough")
            return 0

        oS.alphas[i] += oS.labelMat[j]*oS.labelMat[i]*(alphaJold - oS.alphas[j])#update i by the same amount as j
        updateEk(oS, i) #added this for the Ecache                    #the update is in the oppostie direction
        b1 = oS.b - Ei - oS.labelMat[i] * (oS.alphas[i]-alphaIold)*oS.X[i,:]*oS.X[i,:].T - oS.labelMat[j]*(oS.alphas[j] - alphaJold)*oS.X[i,:]*oS.X[j,:].T
        b2 = oS.b - Ei - oS.labelMat[i] * (oS.alphas[i]-alphaIold)*oS.X[i,:]*oS.X[i,:].T - oS.labelMat[j]*(oS.alphas[j] - alphaJold)*oS.X[j,:]*oS.X[j,:].T
        
        
        if (0 < oS.alphas[i]) and (oS.C > oS.alphas[i]):
            oS.b = b1
        elif (0 < oS.alphas[j]) and (oS.C > oS.alphas[j]):
            oS.b = b2
        else:
            oS.b = (b1 + b2)/2.0
        return 1
    
    else: 
        return 0

def smoP(dataMatIn, classLabels, C, toler, maxIter, kTup=('lin', 0), istraces=True):    #full Platt SMO
    oS = optStruct(mat(dataMatIn),mat(classLabels).transpose(),C,toler, kTup)
    iter = 0
    entireSet = True; alphaPairsChanged = 0
    while (iter < maxIter) and ((alphaPairsChanged > 0) or (entireSet)):
        alphaPairsChanged = 0
        if entireSet:   # go over all
            for i in range(oS.m):        
                alphaPairsChanged += innerL(i, oS)
                if istraces:
                    print("fullSet, iter: %d i:%d, pairs changed %d" % (iter,i,alphaPairsChanged))
            iter += 1
        else: # go over non-bound (railed) alphas
            nonBoundIs = nonzero((oS.alphas.A > 0) * (oS.alphas.A < C))[0]
            for i in nonBoundIs:
                alphaPairsChanged += innerL(i, oS, istraces)
                if istraces:
                    print("non-bound, iter: %d i:%d, pairs changed %d" % (iter,i,alphaPairsChanged))
            iter += 1
        if entireSet:
            entireSet = False #toggle entire set loop
        elif (alphaPairsChanged == 0):
            entireSet = True  
        print("iteration number: %d" % iter)
    return oS.b, oS.alphas

1 2	dataArr, labelArr = loadDataSet('MLiA_SourceCode/machinelearninginaction/Ch06/testSet.txt') b, alphas = smoP(dataArr, labelArr, 0.6, 0.001, 40)

fullSet, iter: 0 i:0, pairs changed 1
fullSet, iter: 0 i:1, pairs changed 1
fullSet, iter: 0 i:2, pairs changed 2
j not moving enough
...
...
fullSet, iter: 2 i:97, pairs changed 0
fullSet, iter: 2 i:98, pairs changed 0
fullSet, iter: 2 i:99, pairs changed 0
iteration number: 3

supportVectors = []
for i in range(100):
    if alphas[i] > 0.0:
        supportVectors.append(dataArr[i])
        print(dataArr[i], labelArr[i])

[3.542485, 1.977398] -1.0
[7.55151, -1.58003] 1.0
[8.127113, 1.274372] 1.0
[7.108772, -0.986906] 1.0
[6.080573, 0.418886] 1.0
[3.107511, 0.758367] -1.0

1	plotSupportVectors(supportVectors)

png

如何用上面得到的alpha值来进行分类？首先必须基于alpha值得到超平面，计算w。

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

1 2	ws = calcWs(alphas, dataArr, labelArr) ws

array([[ 0.65139219],
       [-0.18666913]])

1 2	datMat = mat(dataArr) datMat[0]*mat(ws)+b

matrix([[-0.94421679]])

如果该值大于0那么其属于1类，小于0则属于-1类。对于dataMat[0]点应该时类别-1，验证检查：

1	labelArr[0]

-1.0

写个函数全部检查一遍看看

def checkResult(alphas, b, dataArr, labelArr):
    ws = calcWs(alphas, dataArr, labelArr)
    datMat = mat(dataArr)
    n = len(datMat)
    errorCount = 0.0
    for i in range(n):
        result = datMat[i]*mat(ws)+b
        result = 1.0 if float(result) > 0 else -1.0
        if result != labelArr[i]:
            errorCount += 1.0
    print("the error tate of this test is %f" % float(errorCount/n))

1	checkResult(alphas, b, dataArr, labelArr)

the error tate of this test is 0.000000

测试结果全部都分类正确

在复杂的数据上应用核函数

利用核函数将数据映射到高维空间

径向基核函数

1	%run MLiA_SourceCode/machinelearninginaction/Ch06/plotRBF.py

png

def kernelTrans(X, A, kTup): #calc the kernel or transform data to a higher dimensional space
    m,n = shape(X)
    K = mat(zeros((m,1)))
    if kTup[0]=='lin':
        K = X * A.T   #linear kernel
    elif kTup[0]=='rbf':
        for j in range(m):
            deltaRow = X[j,:] - A
            K[j] = deltaRow*deltaRow.T
        K = exp(K/(-1*kTup[1]**2)) #divide in NumPy is element-wise not matrix like Matlab
    else: raise NameError('Houston We Have a Problem -- \
    That Kernel is not recognized')
    return K

class optStruct:
    def __init__(self,dataMatIn, classLabels, C, toler, kTup):  # Initialize the structure with the parameters 
        self.X = dataMatIn
        self.labelMat = classLabels
        self.C = C
        self.tol = toler
        self.m = shape(dataMatIn)[0]
        self.alphas = mat(zeros((self.m,1)))
        self.b = 0
        self.eCache = mat(zeros((self.m,2))) #first column is valid flag
        self.K = mat(zeros((self.m,self.m)))
        for i in range(self.m):
            self.K[:,i] = kernelTrans(self.X, self.X[i,:], kTup)

def innerL(i, oS, istraces=False):
    Ei = calcEk(oS, i)
    if ((oS.labelMat[i]*Ei < -oS.tol) and (oS.alphas[i] < oS.C)) or ((oS.labelMat[i]*Ei > oS.tol) and (oS.alphas[i] > 0)):
        j,Ej = selectJ(i, oS, Ei) #this has been changed from selectJrand
        alphaIold = oS.alphas[i].copy(); alphaJold = oS.alphas[j].copy();
        if (oS.labelMat[i] != oS.labelMat[j]):
            L = max(0, oS.alphas[j] - oS.alphas[i])
            H = min(oS.C, oS.C + oS.alphas[j] - oS.alphas[i])
        else:
            L = max(0, oS.alphas[j] + oS.alphas[i] - oS.C)
            H = min(oS.C, oS.alphas[j] + oS.alphas[i])

        if L==H:
            if istraces: 
                print("L==H")
            return 0

        eta = 2.0 * oS.K[i,j] - oS.K[i,i] - oS.K[j,j] #changed for kernel
        if eta >= 0:
            if istraces: 
                print("eta>=0")
            return 0

        oS.alphas[j] -= oS.labelMat[j]*(Ei - Ej)/eta
        oS.alphas[j] = clipAlpha(oS.alphas[j],H,L)
        updateEk(oS, j) # added this for the Ecache
        
        if (abs(oS.alphas[j] - alphaJold) < 0.00001):
            if istraces: 
                print("j not moving enough")
            return 0

        oS.alphas[i] += oS.labelMat[j]*oS.labelMat[i]*(alphaJold - oS.alphas[j])#update i by the same amount as j
        updateEk(oS, i) #added this for the Ecache                    #the update is in the oppostie direction
        b1 = oS.b - Ei- oS.labelMat[i]*(oS.alphas[i]-alphaIold)*oS.K[i,i] - oS.labelMat[j]*(oS.alphas[j]-alphaJold)*oS.K[i,j]
        b2 = oS.b - Ej- oS.labelMat[i]*(oS.alphas[i]-alphaIold)*oS.K[i,j]- oS.labelMat[j]*(oS.alphas[j]-alphaJold)*oS.K[j,j]
        
        if (0 < oS.alphas[i]) and (oS.C > oS.alphas[i]):
            oS.b = b1
        elif (0 < oS.alphas[j]) and (oS.C > oS.alphas[j]):
            oS.b = b2
        else:
            oS.b = (b1 + b2)/2.0
        return 1
    
    else: 
        return 0

def calcEk(oS, k):
    fXk = float(multiply(oS.alphas,oS.labelMat).T*oS.K[:,k] + oS.b)
    Ek = fXk - float(oS.labelMat[k])
    return Ek

def testRbf(k1=1.3):
    dataArr,labelArr = loadDataSet('MLiA_SourceCode/machinelearninginaction/Ch06/testSetRBF.txt')
    b,alphas = smoP(dataArr, labelArr, 200, 0.0001, 10000, ('rbf', k1)) #C=200 important
    datMat=mat(dataArr); labelMat = mat(labelArr).transpose()
    svInd=nonzero(alphas.A>0)[0]
    sVs=datMat[svInd] #get matrix of only support vectors
    labelSV = labelMat[svInd];
    print("there are %d Support Vectors" % shape(sVs)[0])
    m,n = shape(datMat)
    errorCount = 0
    for i in range(m):
        kernelEval = kernelTrans(sVs,datMat[i,:],('rbf', k1))
        predict=kernelEval.T * multiply(labelSV,alphas[svInd]) + b
        if sign(predict)!=sign(labelArr[i]): errorCount += 1
    print("the training error rate is: %f" % (float(errorCount)/m))
    dataArr,labelArr = loadDataSet('MLiA_SourceCode/machinelearninginaction/Ch06/testSetRBF2.txt')
    errorCount = 0
    datMat=mat(dataArr); labelMat = mat(labelArr).transpose()
    m,n = shape(datMat)
    for i in range(m):
        kernelEval = kernelTrans(sVs,datMat[i,:],('rbf', k1))
        predict=kernelEval.T * multiply(labelSV,alphas[svInd]) + b
        if sign(predict)!=sign(labelArr[i]): errorCount += 1    
    print("the test error rate is: %f" % (float(errorCount)/m))

在测试中使用核函数

用加入了核函数的算法再次训练

testRbf()

fullSet, iter: 0 i:0, pairs changed 1
fullSet, iter: 0 i:1, pairs changed 1
...
...
fullSet, iter: 6 i:99, pairs changed 0
iteration number: 7
there are 29 Support Vectors
the training error rate is: 0.070000
the test error rate is: 0.050000

1	testRbf(0.1)

fullSet, iter: 0 i:0, pairs changed 1
fullSet, iter: 0 i:1, pairs changed 2
...
...
iteration number: 7
there are 89 Support Vectors
the training error rate is: 0.000000
the test error rate is: 0.070000

当k1=0.1时候，支持向量为89个，k1=1.3的时候时29个，当减小σ，训练错误率就会降低，但测试错误率就会上升。

支持向量的数目存在一个最优值。SVM的优点在于它能对数据进行高效分类。如果支持向量太少，就可能会得到一个很差的决策边界；如果支持向量太多，也就相当于每次都利用整个数据集进行分类，这种分类法发称为K近邻。

实例：手写识别问题回顾

基于SVM的数字识别

收集数据
准备数据：基于二值图像构造向量
分析数据：对图像向量进行目测
训练算法：采用两种不同的核函数，并对径向（radial direction）基核函数采用不同的设置来运行SMO算法
测试算法：编写一个函数来测试不同的核函数并计算错误率
使用算法

首先把第二章的img2vector()函数复制过来。

def img2vector(filename):
    returnVect = zeros((1,1024))
    fr = open(filename)
    for i in range(32):
        lineStr = fr.readline()
        for j in range(32):
            returnVect[0,32*i+j] = int(lineStr[j])
    return returnVect

def loadImages(dirName):
    from os import listdir
    hwLabels = []
    trainingFileList = listdir(dirName)         # load the training set
    m = len(trainingFileList)
    trainingMat = zeros((m,1024))
    for i in range(m):
        fileNameStr = trainingFileList[i]
        fileStr = fileNameStr.split('.')[0]     # take off .txt
        classNumStr = int(fileStr.split('_')[0])
        if classNumStr == 9:
            hwLabels.append(-1)
        else:
            hwLabels.append(1)
        trainingMat[i,:] = img2vector('%s/%s' % (dirName, fileNameStr))
    return trainingMat, hwLabels

def testDigits(kTup=('rbf', 10), istrances=False):
    dataArr,labelArr = loadImages('MLiA_SourceCode/machinelearninginaction/Ch06/digits/trainingDigits')
    b,alphas = smoP(dataArr, labelArr, 200, 0.0001, 10000, kTup, istrances)
    datMat=mat(dataArr)
    labelMat = mat(labelArr).transpose()
    svInd=nonzero(alphas.A>0)[0]
    sVs=datMat[svInd] 
    labelSV = labelMat[svInd];
    
    print("there are %d Support Vectors" % shape(sVs)[0])
    supportVectors = shape(sVs)[0]
    m,n = shape(datMat)
    errorCount = 0
    
    for i in range(m):
        kernelEval = kernelTrans(sVs,datMat[i,:],kTup)
        predict = kernelEval.T * multiply(labelSV,alphas[svInd]) + b
        if sign(predict) != sign(labelArr[i]):
            errorCount += 1
    trainErrorRate = float(errorCount)/m        
    print("the training error rate is: %f" % (float(errorCount)/m))
    dataArr,labelArr = loadImages('MLiA_SourceCode/machinelearninginaction/Ch06/digits/testDigits')
    errorCount = 0
    datMat=mat(dataArr) 
    labelMat = mat(labelArr).transpose()
    m,n = shape(datMat)
    
    for i in range(m):
        kernelEval = kernelTrans(sVs,datMat[i,:],kTup)
        predict=kernelEval.T * multiply(labelSV,alphas[svInd]) + b
        if sign(predict) != sign(labelArr[i]):
            errorCount += 1

    print("the test error rate is: %f" % (float(errorCount)/m))
    testErrorTate = float(errorCount)/m
    return trainErrorRate, testErrorTate, supportVectors

尝试不同的参数和线性核函数来学习：

parameters = [['rbf', 0.1],
             ['rbf', 5],
             ['rbf', 10],
             ['rbf', 50],
             ['rbf', 100],
             ['lin', 0]]
trainErrorRate = []
testErrorTate = []
supportVectors = []

for i, j in parameters:
    result = testDigits(kTup=(i, j))
    trainErrorRate.append(result[0])
    testErrorTate.append(result[1])
    supportVectors.append(result[2])

iteration number: 1
iteration number: 2
iteration number: 3
...
...
iteration number: 9
there are 39 Support Vectors
the training error rate is: 0.000000
the test error rate is: 0.021505

1
2
3

print("内核,设置\t训练错误率\t测试错误率\t支持向量数")
for i in range(len(parameters)):
    print("%s,%.1f \t%.4f \t\t%.4f \t\t%d" %(parameters[i][0], parameters[i][1], trainErrorRate[i], testErrorTate[i], supportVectors[i]))

内核,设置    训练错误率    测试错误率    支持向量数
rbf,0.1     0.0000         0.5215         402
rbf,5.0     0.0000         0.0323         402
rbf,10.0     0.0000         0.0054         132
rbf,50.0     0.0149         0.0269         31
rbf,100.0     0.0050         0.0108         34
lin,0.0     0.0000         0.0215         39

观察发现，最小的训练错误率并不对应最小的支持向量数，线性核函数的效果并不是特别糟糕。可以牺牲线性核函数的错误率来换取分类速度的提高。

总结

支持向量机时一种分类器，之所以称为“机”时因为它会产生一个二值决策结果，即它是一种决策“机”，支持向量机的泛化错误率较低，也就是说它具有良好的学习能力，并且学到的结果具有很好的推广性。

核函数从一个低纬空间映射到一个高纬空间，可以将一个低维空间中的非线性问题转换为高纬度空间下的线性问题来求解。

支持向量机是一个二分类器。当解决多分类问题时，则需要额外的方法对其进行扩展，SVM的效果也对优化参数和所用核函数中的参数敏感。