• 《机器学习实战》6.支持向量机（SVM）

    目录

    1 基于最大间隔分隔数据

    2 寻找最大间隔

    2.1 分类器求解的优化问题

    2.2 SVM应用的一般流程

    3 SMO高效优化算法

    3.1 Platt的SMO算法

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

    4 利用完整Platt SMO算法加速优化

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

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

    5.2径向基核函数

    5.3 在测试中用到核函数

     6 手写识别问题回顾

     7 本章小结

    本章涉及到的向相关代码和数据

    SVM有很多种实现方法，但是这里学习最流行的一种，即序列最小化（SMO）算法。在此之后，将介绍如何使用一种称为核函数的方式奖SVM拓展到更多数据集上

    1 基于最大间隔分隔数据

    优点：泛化错误率低，计算开销不大，结果易解释  

    缺点：对参数调节喝核函数的选择敏感，原始分类器不加修饰仅适用于处理二类问题  

    适用数据类型：数值型数据与标称型数据  

    支持向量就是离分割超平面最近的那些点，然后找到最大化支持向量到分割面的距离，需要找到此问题的优化求解方法

    2 寻找最大间隔

    2.1 分类器求解的优化问题

    使用海维赛德阶跃函数来进行分类的计算

    为了找到分割最好的那一条线，我们在这里选择得到最大化支持向量的最大化间隔

    2.2 SVM应用的一般流程

    ①收集数据：可以使用任意方法  

    ②准备数据：需要数值型数据  

    ③分析数据：有助于可视化分隔超平面  

    ④训练算法：SVM的大部分时间都源于训练，该过程主要实现两个参数的调优  

    ⑤测试算法：十分简单的计算过程就可以实现  

    ⑥使用算法：几乎所有的分类问题都可以使用SVM，值得一提的是，SVM本身是一个二类分类器，对多类问题应用SVM需要对代码做出一些修改  

    3 SMO高效优化算法

    ①最小化的目标函数

    ②在优化过程中必须遵循约束条件

    3.1 Platt的SMO算法

    SMO表示序列最小化。PLatt的SMO算法是将大优化问题分解为多个小优化问题来求解。这些小优化问题往往很容易求解，并且对他们进行顺序求解的结果与将他们整体来求解的结果是完全一致的。在结果完全相同的条件下，SMO算法的求解时间就会短很多。  

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

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

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

    platt SMO的实现需要大量的代码。因此我们对算法进行简化处理，以便大致了解算法的基本工作思路，之后再基于简化版给出完整版。简化版虽然量少但执行速度慢。

    1. # SMO算法中的辅助函数
    2.  
    3. # 打开文件并对其进行逐行分析，从而得到每行的类标签和整个数据矩阵
    4. def loadDataSet(fileName):
    5.     dataMat=[]
    6.     labelMat=[]
    7.     fr=open(fileName)
    8.     # 读取文件
    9.     # 按行读取
    10.     for line in fr.readlines():
    11.         # 将每一行的数据进行分割
    12.         lineArr=line.strip().split('\t')
    13.         # 前两列为x，y值
    14.         dataMat.append([float(lineArr[0]),float(lineArr[1])])
    15.         # 第三列为标签值
    16.         labelMat.append(float(lineArr[2]))
    17.     # 返回数据集和标签集
    18.     return dataMat,labelMat
    19.  
    20. # 只要函数值不等于输入值i，函数就会进行随机选择
    21. import random
    22. #         i输入下标，m为总数
    23. def selectJrand(i,m):
    24.     j=i
    25.     while(j==i):
    26.         j=int(random.uniform(0,m))
    27.     return j
    28.  
    29. # 用于调整大于H或是小于L的alpha的值
    30. def clipAlpha(aj,H,L):
    31.     # 大于H的值取H
    32.     if aj>H:
    33.         aj=H
    34.     # 小于L的值取L
    35.     if L>aj:
    36.         aj=L
    37.     return aj

    运行上面函数读取数据

    1. dataArr,labelArr=loadDataSet('testSet.txt')
    2. # 可以看出这里的分类标签是1和-1，而不是1和0
    3. labelArr

    运行得到的结果为：

     先写出数据集中的二维点的分布函数

    1. # 画出待分类数据的二维分布
    2. import numpy as np
    3. def plotBestFit(dataMat,labelMat):
    4.     import matplotlib.pyplot as plt
    5.     # getA（）函数将矩阵转化为数组
    6.     # weights=wei.getA()
    7.     # 加载数据
    8.     dataArr=np.array(dataMat)
    9.  
    10.     n=np.shape(dataArr)[0]
    11.     xcord1=[]
    12.     ycord1=[]
    13.     xcord2=[]
    14.     ycord2=[]
    15.     # print(labelMat)
    16.     for i in range(n):
    17.         if int(labelMat[i])==1:
    18.             xcord1.append(dataArr[i][0])
    19.             ycord1.append(dataArr[i][1])
    20.         else:
    21.             xcord2.append(dataArr[i][0])
    22.             ycord2.append(dataArr[i][1])
    23.     fig=plt.figure()
    24.     ax=fig.add_subplot(111)
    25.     # print(xcord1)
    26.     # print(ycord1)
    27.     ax.scatter(xcord1,ycord1,s=30,c='red',marker='s')
    28.     ax.scatter(xcord2,ycord2,s=30,c='green')
    29.     # arange()函数用于创造等差数组
    30.             # 起始点 终止点 步长
    31.     # x=np.arange(-3.0,3.0,0.1)
    32.     # y=(-weights[0]-weights[1]*x)/weights[2]
    33.     # ax.plot(x,y)
    34.     # 添加xy轴标签
    35.     plt.xlabel('X1')
    36.     plt.ylabel('X2')
    37.     # 显示图像
    38.     plt.show()

    调用上述函数

    plotBestFit(dataArr,labelArr)

    得到二维点的分布结果：

    接下来写SMO函数的具体实现，他的伪代码大致如下：

     创建一个alpha向量并将其初始化为0向量  

    当迭代次数小于最大迭代次数时：（外循环）  

     对数据集中的每个数据向量：（内循环）  

      如果该数据向量可以被优化：  

        随机选择另外一个数据向量  

        同时优化这两个向量  

        如果两个向量都不能被优化，推出内循环  

     如果所有向量都没有被优化，增加迭代次数，继续下一次循环  

     简化版的代码如下：

    1. # 简化版的smo算法
    2. from numpy import *
    3. # 构建函数时，采用通用的接口，这样就可以对算法和数据源进行组合和配对处理
    4. #    输入参数：数据集，类别标签，常数C，容错率，取消最大的循环次数
    5. def smoSimple(dataMatIn, classLabels, C, toler, maxIter):
    6.     # 将数列转化为矩阵
    7.     dataMatrix = mat(dataMatIn)
    8.     # .transpose()函数映射坐标轴
    9.     labelMat = mat(classLabels).transpose()
    10.     b = 0; 
    11.     # 得到矩阵的长和宽
    12.     m,n = shape(dataMatrix)
    13.     # 得到一个m行1列全部是0的矩阵
    14.     alphas = mat(zeros((m,1)))
    15.     iter = 0
    16.     while (iter < maxIter):
    17.         alphaPairsChanged = 0
    18.         for i in range(m):
    19.             fXi = float(multiply(alphas,labelMat).T*(dataMatrix*dataMatrix[i,:].T)) + b
    20.             Ei = fXi - float(labelMat[i])#if checks if an example violates KKT conditions
    21.             # 如果alpha可以更改则进入优化过程
    22.             if ((labelMat[i]*Ei < -toler) and (alphas[i] < C)) or ((labelMat[i]*Ei > toler) and (alphas[i] > 0)):
    23.                 j = selectJrand(i,m)
    24.                 fXj = float(multiply(alphas,labelMat).T*(dataMatrix*dataMatrix[j,:].T)) + b
    25.                 Ej = fXj - float(labelMat[j])
    26.                 alphaIold = alphas[i].copy()
    27.                 alphaJold = alphas[j].copy()
    28.                 # 保证alpha在0和C之间
    29.                 if (labelMat[i] != labelMat[j]):
    30.                     L = max(0, alphas[j] - alphas[i])
    31.                     H = min(C, C + alphas[j] - alphas[i])
    32.                 else:
    33.                     L = max(0, alphas[j] + alphas[i] - C)
    34.                     H = min(C, alphas[j] + alphas[i])
    35.                 if L==H: print ("L==H"); continue
    36.                 eta = 2.0 * dataMatrix[i,:]*dataMatrix[j,:].T - dataMatrix[i,:]*dataMatrix[i,:].T - dataMatrix[j,:]*dataMatrix[j,:].T
    37.                 if eta >= 0: print ("eta>=0"); continue
    38.                 alphas[j] -= labelMat[j]*(Ei - Ej)/eta
    39.                 alphas[j] = clipAlpha(alphas[j],H,L)
    40.                 if (abs(alphas[j] - alphaJold) < 0.00001): print ("j not moving enough"); continue
    41.                 alphas[i] += labelMat[j]*labelMat[i]*(alphaJold - alphas[j])#update i by the same amount as j
    42.                                                                         #the update is in the oppostie direction
    43.                 b1 = b - Ei- labelMat[i]*(alphas[i]-alphaIold)*dataMatrix[i,:]*dataMatrix[i,:].T - labelMat[j]*(alphas[j]-alphaJold)*dataMatrix[i,:]*dataMatrix[j,:].T
    44.                 b2 = b - Ej- labelMat[i]*(alphas[i]-alphaIold)*dataMatrix[i,:]*dataMatrix[j,:].T - labelMat[j]*(alphas[j]-alphaJold)*dataMatrix[j,:]*dataMatrix[j,:].T
    45.                 if (0 < alphas[i]) and (C > alphas[i]): 
    46.                     b = b1
    47.                 elif (0 < alphas[j]) and (C > alphas[j]): 
    48.                     b = b2
    49.                 else: 
    50.                     b = (b1 + b2)/2.0
    51.                 alphaPairsChanged += 1
    52.                 print ("iter: %d i:%d, pairs changed %d" % (iter,i,alphaPairsChanged))
    53.         if (alphaPairsChanged == 0): 
    54.             iter += 1
    55.         else: 
    56.             iter = 0
    57.         print ("iteration number: %d" % iter)
    58.     return b,alphas

    调用简化版的代码：

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

    运行得到的结果为：

     分别查看b和支持向量的alpha的值如下

     并且写代码筛选出得到的支持向量：

    1. shape(alphas[alphas>0])
    2. for i in range(100):
    3.     if alphas[i]>0.0:
    4.         print(dataArr[i],labelArr[i])

    运行得到的支持向量为5个支持向量

    4 利用完整Platt SMO算法加速优化

    在几百个点组成的小规模数据集上，简化版SMO算法的运行是么样问题的，但是在更大的数据集上的运行速度就会变慢。在完整版中，实现alpha的更改和代数运算的优化环节一模一样。在优化过程中唯一不同的就是选择alpha的方式。完整版的Platt SMO算法应用了一些那个提速的启发方法。  

    Platt SMO算法时通过一个外循环来选择第一个alpha的值，并且其选择过程会在两种方式之间交替：一种方式是在所有数据集上进行单遍扫描，另一种方式则是在非边界alpha中实现单遍扫描。而那些所谓非边界alpha指的就是那些不等于边界0或C的alpha值。对整个数据集的扫描相当容易，而实现非边界alpha值的扫描时，首先需要建立这些alpha值的列表，然后子啊对这个表进行遍历。同时该步骤会跳过那些一职的不会改变的alpha值。  

    在选择第一个alpha值的时后，算法会通过一个内循环来选择第二个alpha的值，在优化过程中，会通过最大化步长的方式来获得第二个alpha值。再简化版SMO算法中，我们会选择j之后计算错误率Ej。但在这里，我们会建立一个全局的缓存用于保存误差值，并从中选择使得步长或者说是Ei-Ej最大的alpha值  

    1. # 建立一个数据结构来保存所有重要的数据
    2. class optStruct:
    3.     def __init__(self,dataMatIn,classLabels,C,toler):
    4.         self.X=dataMatIn                      #数据集
    5.         self.labelMat=classLabels             #标签集
    6.         self.C=C                              #常数C
    7.         self.tol=toler                        #容错率
    8.         self.m=shape(dataMatIn)[0]            #数据集的列
    9.         self.alphas=mat(zeros((self.m,1)))    #alpha矩阵
    10.         self.b=0                              #参数b
    11.         self.eCache=mat(zeros((self.m,2)))
    12.  
    13. # 对于给定的alpha值，计算E值并返回
    14. # 使用频繁，直接单独拎出来
    15. def calcEk(oS,k):
    16.     fXk=float(multiply(oS.alphas,oS.labelMat).T*(oS.X*oS.X[k,:].T))+oS.b
    17.     Ek=fXk-float(oS.labelMat[k])
    18.     return Ek
    19.  
    20. # 用于选择第二个alpha或者说内循环的alpha的值
    21. def selectJ(i,oS,Ei):
    22.     maxK=-1
    23.     maxDeltaE=0
    24.     Ej=0
    25.     oS.eCache[i]=[1,Ei]
    26.     validEcacheList=nonzero(oS.eCache[:,0].A)[0]
    27.     if(len(validEcacheList))>1:
    28.         for k in validEcacheList:
    29.             if k==i:
    30.                 continue
    31.             Ek=calcEk(oS,k)
    32.             deltaE=abs(Ei-Ek)
    33.             if(deltaE>maxDeltaE):
    34.                 maxK=k
    35.                 maxDeltaE=deltaE
    36.                 Ej=Ek
    37.         return maxK,Ej
    38.     else:
    39.         j=selectJrand(i,oS.m)
    40.         Ej=calcEk(oS,j)
    41.     return j,Ej
    42.  
    43. # 计算误差值并存入缓存
    44. def updateEk(oS,k):
    45.     Ek=calcEk(oS,k)
    46.     oS.eCache[k]=[1,Ek]
    47.  
    48.  
    49. # 用于寻找决策边界的优化例程
    50. def innerL(i,oS):
    51.     Ei=calcEk(oS,i)
    52.     # 是否进行优化
    53.     if((oS.labelMat[i]*Ei<-oS.tol)and(oS.alphas[i]or((oS.labelMat[i]*Ei>oS.tol)and(oS.alphas[i]>0)):
    54.         j,Ej=selectJ(i,oS,Ei)
    55.         alphaIold=oS.alphas[i].copy()
    56.         alphaJold=oS.alphas[j].copy()
    57.         if(oS.labelMat[i]!=oS.labelMat[j]):
    58.             L=max(0,oS.alphas[j]-oS.alphas[i])
    59.             H=min(oS.C,oS.C+oS.alphas[j]-oS.alphas[i])
    60.         else:
    61.             L=max(0,oS.alphas[j]+oS.alphas[i]-oS.C)
    62.             H=min(oS.C,oS.alphas[j]+oS.alphas[i])
    63.         if L==H: 
    64.             print ("L==H")
    65.             return 0
    66.         eta = 2.0 * oS.X[i,:]*oS.X[j,:].T - oS.X[i,:]*oS.X[i,:].T - oS.X[j,:]*oS.X[j,:].T
    67.         if eta >= 0: 
    68.             print ("eta>=0") 
    69.             return 0
    70.         oS.alphas[j] -= oS.labelMat[j]*(Ei - Ej)/eta
    71.         oS.alphas[j] = clipAlpha(oS.alphas[j],H,L)
    72.         updateEk(oS, j) #added this for the Ecache
    73.         if (abs(oS.alphas[j] - alphaJold) < 0.00001): 
    74.             print ("j not moving enough")
    75.             return 0
    76.         oS.alphas[i] += oS.labelMat[j]*oS.labelMat[i]*(alphaJold - oS.alphas[j])#update i by the same amount as j
    77.         updateEk(oS, i) #added this for the Ecache                    #the update is in the oppostie direction
    78.         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
    79.         b2 = oS.b - Ej- oS.labelMat[i]*(oS.alphas[i]-alphaIold)*oS.X[i,:]*oS.X[j,:].T - oS.labelMat[j]*(oS.alphas[j]-alphaJold)*oS.X[j,:]*oS.X[j,:].T
    80.         if (0 < oS.alphas[i]) and (oS.C > oS.alphas[i]): 
    81.             oS.b = b1
    82.         elif (0 < oS.alphas[j]) and (oS.C > oS.alphas[j]): 
    83.             oS.b = b2
    84.         else: 
    85.             oS.b = (b1 + b2)/2.0
    86.         return 1
    87.     else: 
    88.         return 0
    89.  
    90. # 外循环代码
    91. def smoP(dataMatIn,classLabels,C,toler,maxIter,kTup=('lin',0)):
    92.     # 初始化一个结构体
    93.     oS=optStruct(mat(dataMatIn),mat(classLabels).transpose(),C,toler)
    94.     iter=0     #记录循环次数
    95.     entireSet=True
    96.     alphaPairsChanged=0
    97.     # 进入循环
    98.     # 如果循环次数没有达到最大上限  and 
    99.     while(iterand ((alphaPairsChanged>0)or(entireSet)):
    100.         alphaPairsChanged=0
    101.         if entireSet:
    102.             # 对数据集中的每个数据向量
    103.             for i in range(oS.m):
    104.                 alphaPairsChanged+=innerL(i,oS)
    105.             print("fullSet,iter:%d i:%d,pairs changed %d" %(iter,i,alphaPairsChanged))
    106.             iter+=1
    107.         else:
    108.             nonBoundIs=nonzero((oS.alphas.A>0)*(oS.alphas.A0]
    109.             for i in nonBoundIs:
    110.                 alphaPairsChanged+=innerL(i,oS)
    111.                 print("non-bound,iter:%d i:%d,pairs changed %d" %(iter,i,alphaPairsChanged))
    112.             iter+=1
    113.         # 使下次能够进入循环
    114.         if entireSet:
    115.             entireSet=False
    116.         elif(alphaPairsChanged==0):
    117.             entireSet=True
    118.         print("iteration number:%d"%iter)
    119.     # 返回训练得到的b和alpha矩阵
    120.     return oS.b,oS.alphas
    121.             
    122.

    利用上述代码进行SMO的计算

    1. # 打开文件，读取数据
    2. dataArr,labelArr=loadDataSet('testSet.txt')
    3. # 将数据进行支持向量机训练
    4. b,alphas=smoP(dataArr,labelArr,0.6,0.001,40)

    运行得到的结果为：

     再次查看b和支持向量的值：

    计算最终起作用的（斜率）？

    1. def calcWs(alphas,dataArr,classLabels):
    2.     X=mat(dataArr)
    3.     labelMat=mat(classLabels).transpose()
    4.     m,n=shape(X)
    5.     w=zeros((n,1))
    6.     for i in range(m):
    7.         # 最终起作用的只有支持向量
    8.         w+=multiply(alphas[i]*labelMat[i],X[i,:].T)
    9.     return w

     调用上述函数并使用一个数据进行检验

    1. ws=calcWs(alphas,dataArr,labelArr)
    2. datMat=mat(dataArr)
    3. datMat[0]*mat(ws)+b

    得到的结果为

    结果是小于0 的

    因此查看该数据的分类：

    是-1，因此测试的结果正确。 

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

    前面我们用的数据就是讨论线性可分的情况。接下来，我们就要使用一种称为核函数的工具将数据转换为已于分类器理解的形式

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

    我们将数据从一个特征空间转换为另一个特征空间。再新空间下，我们可以很容易利用已有的工具对数据进行处理。在通常情况下，这种映射将为从低维特征空间映射到高维空间。  

    这种从某个特征空间到另一个特征空间的映射是通过核函数来实现的。他能够报数据从某个很难处理的形式转换为另一个较容易处理的形式。经过空间转换之后，我们可以在高维空间中解决线性问题，这也就等价于在地位空间中解决非线性问题。  

    SVM优化中一个特别好的地方就是，所有的运算都可以写成内积的形式，向量的内积指的是两个向量相乘，之后得到的单个标量或是数值。把内积替换成核函数，而不做简化处理，这种方式被称为核技巧。  

    核函数不仅仅应用于向量机，很多其他的机器学习算法也都有用到核函数。

    5.2径向基核函数

    径向基函数是SVM中常用到的一种核函数，他是一个采用向量作为自变量的函数，能够基于向量距离运算输出一个标量。  

    这里 我们应用径向基函数的高斯版本，将数据从特征空间映射到更高维的空间，具体来说是映射到一个更高维的空间

    1. # 转换核函数
    2. def kernelTrans(X,A,kTup):
    3.     m,n=shape(X)
    4.     K=mat(zeros((m,1)))
    5.     if kTup[0]=='lin':
    6.         K=X*A.T
    7.     elif kTup[0]=='rbf':
    8.         for j in range(m):
    9.             deltaRow=X[j,:]-A
    10.             K[j]=deltaRow*deltaRow.T
    11.         K=exp(K/(-1*kTup[1]**2))
    12.     else:
    13.         raise NameError('Houston We Have a Problem--That Kernel is not recognized')
    14.     return K
    15.  
    16. # 定义一个新的结构体，加入核函数
    17. class optStruct:
    18.     def __init__(self,dataMatIn,classLabels,C,toler,kTup):
    19.         self.X=dataMatIn
    20.         self.labelMat=classLabels
    21.         self.C=C
    22.         self.tol=toler
    23.         self.m=shape(dataMatIn)[0]
    24.         self.alphas=mat(zeros((self.m,1)))
    25.         self.b=0
    26.         self.eCache=mat(zeros((self.m,2)))
    27.         self.K=mat(zeros((self.m,self.m)))
    28.         # 计算核函数
    29.         # 引入一个新变量kTup
    30.         for i in range(self.m):
    31.             # 计算高斯函数的值
    32.             self.K[:,i]=kernelTrans(self.X,self.X[i,:],kTup)
    33.  
    34. # 重新更改上文中提到的innerL()和calcLEk()函数的部分代码
    35. # 用于寻找决策边界的优化例程
    36. def innerL(i,oS):
    37.     Ei=calcEk(oS,i)
    38.     # 是否进行优化
    39.     if((oS.labelMat[i]*Ei<-oS.tol)and(oS.alphas[i]or((oS.labelMat[i]*Ei>oS.tol)and(oS.alphas[i]>0)):
    40.         j,Ej=selectJ(i,oS,Ei)
    41.         alphaIold=oS.alphas[i].copy()
    42.         alphaJold=oS.alphas[j].copy()
    43.         if(oS.labelMat[i]!=oS.labelMat[j]):
    44.             L=max(0,oS.alphas[j]-oS.alphas[i])
    45.             H=min(oS.C,oS.C+oS.alphas[j]-oS.alphas[i])
    46.         else:
    47.             L=max(0,oS.alphas[j]+oS.alphas[i]-oS.C)
    48.             H=min(oS.C,oS.alphas[j]+oS.alphas[i])
    49.         if L==H: 
    50.             print ("L==H")
    51.             return 0
    52.         eta = 2.0 * oS.K[i,j]-oS.K[i,i]-oS.K[j,j]
    53.         if eta >= 0: 
    54.             print ("eta>=0") 
    55.             return 0
    56.         oS.alphas[j] -= oS.labelMat[j]*(Ei - Ej)/eta
    57.         oS.alphas[j] = clipAlpha(oS.alphas[j],H,L)
    58.         updateEk(oS, j) #added this for the Ecache
    59.         if (abs(oS.alphas[j] - alphaJold) < 0.00001): 
    60.             print ("j not moving enough")
    61.             return 0
    62.         oS.alphas[i] += oS.labelMat[j]*oS.labelMat[i]*(alphaJold - oS.alphas[j])#update i by the same amount as j
    63.         updateEk(oS, i) #added this for the Ecache                    #the update is in the oppostie direction
    64.         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]
    65.         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]
    66.         if (0 < oS.alphas[i]) and (oS.C > oS.alphas[i]): 
    67.             oS.b = b1
    68.         elif (0 < oS.alphas[j]) and (oS.C > oS.alphas[j]): 
    69.             oS.b = b2
    70.         else: 
    71.             oS.b = (b1 + b2)/2.0
    72.         return 1
    73.     else: 
    74.         return 0
    75.  
    76. # 外循环代码
    77. def smoP(dataMatIn,classLabels,C,toler,maxIter,kTup=('lin',0)):
    78.     # 初始化一个结构体
    79.     oS=optStruct(mat(dataMatIn),mat(classLabels).transpose(),C,toler,kTup)
    80.     iter=0     #记录循环次数
    81.     entireSet=True
    82.     alphaPairsChanged=0
    83.     # 进入循环
    84.     # 如果循环次数没有达到最大上限  and 
    85.     while(iterand ((alphaPairsChanged>0)or(entireSet)):
    86.         alphaPairsChanged=0
    87.         if entireSet:
    88.             # 对数据集中的每个数据向量
    89.             for i in range(oS.m):
    90.                 alphaPairsChanged+=innerL(i,oS)
    91.             print("fullSet,iter:%d i:%d,pairs changed %d" %(iter,i,alphaPairsChanged))
    92.             iter+=1
    93.         else:
    94.             nonBoundIs=nonzero((oS.alphas.A>0)*(oS.alphas.A0]
    95.             for i in nonBoundIs:
    96.                 alphaPairsChanged+=innerL(i,oS)
    97.                 print("non-bound,iter:%d i:%d,pairs changed %d" %(iter,i,alphaPairsChanged))
    98.             iter+=1
    99.         # 使下次能够进入循环
    100.         if entireSet:
    101.             entireSet=False
    102.         elif(alphaPairsChanged==0):
    103.             entireSet=True
    104.         print("iteration number:%d"%iter)
    105.     # 返回训练得到的b和alpha矩阵
    106.     return oS.b,oS.alphas
    107.  
    108. def calcEk(oS,k):
    109.     fXk=float(multiply(oS.alphas,oS.labelMat).T*oS.K[:,k]+oS.b)
    110.     Ek=fXk-float(oS.labelMat[k])
    111.     return Ek

    5.3 在测试中用到核函数

    1. def testRbf(k1=1.3):
    2.     dataArr,labelArr=loadDataSet('testSetRBF.txt')
    3.     plotBestFit(dataArr,labelArr)
    4.     b,alphas=smoP(dataArr,labelArr,200,0.0001,10000,('rbf',k1))
    5.     datMat=mat(dataArr)
    6.     labelMat=mat(labelArr).transpose()
    7.     svInd=nonzero(alphas.A>0)[0]
    8.     sVs=datMat[svInd]
    9.     labelSV=labelMat[svInd]
    10.     print('there are %d Support Vectors' % shape(sVs)[0])
    11.     m,n=shape(datMat)
    12.     errorCount=0
    13.     for i in range(m):
    14.         kernelEval=kernelTrans(sVs,datMat[i,:],('rbf',k1))
    15.         predict=kernelEval.T*multiply(labelSV,alphas[svInd])+b
    16.         if sign(predict)!=sign(labelArr[i]):
    17.             errorCount+=1
    18.         print('the training error rate is :%f' % (float(errorCount)/m))
    19.         dataArr,labelArr=loadDataSet('testSetRBF2.txt')
    20.         errorCount=0
    21.         datMat=mat(dataArr)
    22.         labelMat=mat(labelArr).transpose()
    23.         m,n=shape(datMat)
    24.         for i in range(m):
    25.             kernelEval=kernelTrans(sVs,datMat[i,:],('rbf',k1))
    26.             predict=kernelEval.T*multiply(labelSV,alphas[svInd])+b
    27.             if sign(predict)!=sign(labelArr[i]):
    28.                 errorCount+=1
    29.         print("the test error rate is :%f" %(float(errorCount)/m))

    调用上述函数：

    testRbf()

    得到的输出结果为：

     可以看出数据测试的错误率为0.27

     6 手写识别问题回顾

    基于SVM的数字识别  

    ①收集数据：提供的文本文件  

    ②准备数据：基于二值图像构建向量  

    ③分析数据：对图像向量进行目测  

    ④训练数据：采用两种不同的核函数，并对径向基核函数采用不同的设置来运行SMO算法  

    ⑤测试算法：编写一个函数来测试不同的核函数并计算错误率  

    ⑥使用算法：一个图像识别的完整应用还需要一些图像处理的知识  

    1. from random import triangular
    2.  
    3.  
    4. def img2vector(filename):
    5.     returnVect=zeros((1,1024))
    6.     fr=open(filename)
    7.     # 按行读取矩阵
    8.     for i in range(32):
    9.         lineStr=fr.readline()
    10.         for j in range(32):
    11.             returnVect[0,32*i+j]=int (lineStr[j])
    12.     return returnVect
    13.  
    14.  
    15. def loadImages(dirName):
    16.     from os import listdir
    17.     hwLabels = []
    18.     trainingFileList = listdir(dirName)           #load the training set
    19.     m = len(trainingFileList)
    20.     trainingMat = zeros((m,1024))
    21.     for i in range(m):
    22.         fileNameStr = trainingFileList[i]
    23.         fileStr = fileNameStr.split('.')[0]     #take off .txt
    24.         classNumStr = int(fileStr.split('_')[0])
    25.         if classNumStr == 9: hwLabels.append(-1)
    26.         else: hwLabels.append(1)
    27.         trainingMat[i,:] = img2vector('%s/%s' % (dirName, fileNameStr))
    28.     return trainingMat, hwLabels 
    29.  
    30. def testDigits(kTup=('rbf',10)):
    31.     dataArr,labelArr=loadImages('digits/trainingDigits')
    32.     b,alphas=smoP(dataArr,labelArr,100,0.001,10000,kTup)
    33.     datMat=mat(dataArr)
    34.     labelMat=mat(labelArr).transpose()
    35.     svInd=nonzero(alphas.A>0)[0]
    36.     sVs=datMat[svInd]
    37.     labelSV=labelMat[svInd]
    38.     print("there are %d Support Vectors"%shape(sVs)[0])
    39.     m,n=shape(datMat)
    40.     errorCount=0
    41.     for i in range(m):
    42.         kernelEval=kernelTrans(sVs,datMat[i,:],kTup)
    43.         predict=kernelEval.T*multiply(labelSV,alphas[svInd])+b
    44.         if sign(predict)!=sign(labelArr[i]):
    45.             errorCount+=1
    46.     print("the training error rate is:%f" % (float(errorCount)/m))
    47.     dataArr,labelArr=loadImages('digits/testDigits')
    48.     errorCount=0
    49.     datMat=mat(dataArr)
    50.     labelMat=mat(labelArr).transpose()
    51.     m,n=shape(datMat)
    52.     for i in range(m):
    53.         kernelEval=kernelTrans(sVs,datMat[i,:],kTup)
    54.         predict=kernelEval.T*multiply(labelSV,alphas[svInd])+b
    55.         if sign(predict)!=sign(labelArr[i]):
    56.             errorCount+=1
    57.     print("the test error rate is :%f" % (float(errorCount)/m))
    58.

    调用上述函数：

    testDigits(('rbf',20))

    得到的结果为为：

    因此一旦碰到数字9,则输出类别标签-1，否则输出+1。本质上，支持向量机是-个二类分类器，其分类结果不是+1就是-1。由于这里只做二类分类，因此除了1和9之外的数字都被去掉了。

     7 本章小结

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

    支持向量机试图通过求解一个二次元问题来最大化分类间隔，再过去，训练支持向量机常采用非常复杂并且低效的二次规划问题，john Platt引入了SMO算法，此算法可以通过每次只优化2个alpha值来加快SVM的训练速度。  

    核方法或者说是核技巧会将数据从一个低维空间映射到一个高维空间，可以将一个在低维空间中的非线性问题转换为高维空间的一个线性问题来研究

  • 相关阅读:
    一条爬虫抓取一个小网站所有数据
    OpenCV自学笔记十三：图像梯度
    【RPA实战】 中秋节月饼不知道买哪种？UiPath零代码2分钟获取1000种月饼商品信息告诉你答案
    【redis】Redis是AP架构还是CP架构？
    绕任意轴旋转矩阵推导
    SpringBoot保姆级教程（三）SpringBoot原理分析
    卷积神经网络基本概念
    多对多的创建方式与Ajax
    mysql无法访问故障排除步骤
    聊聊我们是如何做技术保障的
  • 原文地址：https://blog.csdn.net/weixin_46182244/article/details/127578438