机器学习之SVM支持向量机笔记

 

数学理论部分

1.svm支持向量机是什么?

如下图所示,SVM的目标就是寻找一条图中的黑线,使得这条线到两个分类的距离最大,即寻找最大间隔

机器学习之SVM支持向量机笔记

 2.超平面:我们定义那条黑线为超平面,函数公式为 ƒ(x)=wTx+b ,当ƒ(x)=wTx+b=0时为黑线处,大于或者小于分别表示一个类别。

3.分类:根据超平面我们可以进行如下定义,完成分类

机器学习之SVM支持向量机笔记

【注】我们将类别 yi 定义为正负一是为了方便计算边界条件 ,就拿1分类举例,因为yi 为1,所以 yi(wTx+b)>=1仍然成立,这个分类的边界为 yi(wTx+b)=1,我们顺利的将标签y与特征x均放入了一个公式当中。

4.距离计算:

样本点到超平面距离为机器学习之SVM支持向量机笔记,样本之间的间隔为机器学习之SVM支持向量机笔记

4.1推导样本点到平面距离:

方法一:

机器学习之SVM支持向量机笔记

机器学习之SVM支持向量机笔记机器学习之SVM支持向量机笔记,两个公式联立可得机器学习之SVM支持向量机笔记,||w||为范数,是所有元素平方和再开方,w是一个方向向量

 

 方法二:利用中学的距离公式,点到直线的距离公式机器学习之SVM支持向量机笔记,现在已知直线是ƒ(x)=wTx+b,所以机器学习之SVM支持向量机笔记

 

 

4.2推导:从3中可以知道分类的边界是 yi(wTx+b)=1,而 yi=1,所以wTx+b=1,于是单边间距为机器学习之SVM支持向量机笔记,总间距为机器学习之SVM支持向量机笔记

 5.拉格朗日乘数法:对于多元函数 ƒ(x,y)在约束条件φ(x,y)情况下求极值可以使用拉格朗日乘数法,首先加入一个拉格朗日乘数λ,构造出拉格朗日函数机器学习之SVM支持向量机笔记,对 x、y、λ分别偏导为0,求得极值点。

6.KTT条件:

机器学习之SVM支持向量机笔记

6.1 互补松弛条件:上面约束条件g(x)<=0,拉格朗日乘数υ >=0,机器学习之SVM支持向量机笔记(约束条件内部可视作无约束,约束条件边界上才起约束作用)

 

7.对偶问题:

 在满足KTT条件下,可以实现下述公式转换机器学习之SVM支持向量机笔记,从而达到简化计算,下图右式红框中的是多元求极值,可以用拉格朗日求,于是就简化了计算。机器学习之SVM支持向量机笔记

8.整理逻辑顺序

求最大间隔 机器学习之SVM支持向量机笔记--> 等价于求w即 机器学习之SVM支持向量机笔记-->当存在约束条件时转化为拉格朗日函数--> 机器学习之SVM支持向量机笔记(不方便计算)

 

当满足KTT条件时简化计算-->机器学习之SVM支持向量机笔记 

 9.拉格朗日的对偶问题计算

9.1:超平面的模型机器学习之SVM支持向量机笔记

9.2:构建拉格朗日函数机器学习之SVM支持向量机笔记(边界约束条件的由来在上述2的【注】中已经说明)

需要使用到KTT条件进行对偶简化,所以这边α>=0.

9.3:对w,b求偏导,并置为0,可得:

机器学习之SVM支持向量机笔记机器学习之SVM支持向量机笔记因此机器学习之SVM支持向量机笔记

9.4:将9.3结果带入9.2可得

机器学习之SVM支持向量机笔记

 

 于是我们就求得了7中对偶公式的右侧结果

机器学习之SVM支持向量机笔记

 同时根据偏导结果超平面模型也可以写成:机器学习之SVM支持向量机笔记

  SMO算法(序列最小优化算法)

简单线性SMO算法

 SMO算法的主要目的是迭代获得α,b两个参数。

SMO算法的思路是这样的:

 1.SMO算法优化的是以下函数:在这个目标函数中可以看到有两个α,分别为αi、αj,因此是选择一对 拉格朗日乘数进行更新

机器学习之SVM支持向量机笔记

 

 2松弛变量与惩罚参数

由于真实数据并不是百分百线性可分的,所以我们引入松弛变量ς 与惩罚参数 C ,于是上面的约束条件就发生了变化(如下图所示)、同时原目标函数、原始问题拉格朗日函数均发生了改变

机器学习之SVM支持向量机笔记

 目标函数变为:

机器学习之SVM支持向量机笔记

 

 原问题的拉格朗日函数变为:

机器学习之SVM支持向量机笔记

 3.定义拉格朗日乘数α取值的上下限H、L

3.1:由于有一个约束条件是机器学习之SVM支持向量机笔记,所以机器学习之SVM支持向量机笔记

3.2:于是当这一对的α所对应的标签异号(即一个为1,另一个为-1),可以得到如图所示的两种情况机器学习之SVM支持向量机笔记

 

        同时因为需要满足 机器学习之SVM支持向量机笔记这个约束条件,于是可以绘制出下图中的两条边界线。(两条平行的黑线是上面两个公式、坐标轴上的框是约束条件0-C)

 

机器学习之SVM支持向量机笔记

3.3 对于这个图中的两条直线该如何用数学公式表达出来呢?

 

在上图中,我们可以看出来,两种类别中 α2的取值范围分别是 机器学习之SVM支持向量机笔记,但因为我们并不清楚两个标签异号的时候,谁对应谁,于是我们对这两组的 max(下限),min(上限)

 

于是可以这么定义机器学习之SVM支持向量机笔记,同时也可以将 ς 用 α 替换掉,得到 机器学习之SVM支持向量机笔记

 

同理,当标签不是异号的时候,我们可以推断出机器学习之SVM支持向量机笔记,绘制出下图

 

机器学习之SVM支持向量机笔记于是可以给出上下限的数学定义为机器学习之SVM支持向量机笔记

 

总之,综上可以给出上下限的数学定义公式为:

机器学习之SVM支持向量机笔记

 

 4.关于α值得迭代

机器学习之SVM支持向量机笔记

    机器学习之SVM支持向量机笔记

 机器学习之SVM支持向量机笔记

 【注】constant代表的是原公式最后2项,因为最后两项是α3及以后的项,对于α1、α2来讲是无关项,求导之后均为0,所以直接这样替换掉了

 继续简化,由于机器学习之SVM支持向量机笔记,我们可以将 ς 看成一个常数项,然后两边同乘y1 于是可得 机器学习之SVM支持向量机笔记

 

其中γ代表常数 ς*y1,s代表y1y2 

将α2代换掉α1,于是可得:机器学习之SVM支持向量机笔记

 

 

接下来求导:

 机器学习之SVM支持向量机笔记

 

 然后可以得到:机器学习之SVM支持向量机笔记

定义误差与最优修改量:

机器学习之SVM支持向量机笔记

同时根据已知的机器学习之SVM支持向量机笔记机器学习之SVM支持向量机笔记

 

 可简化迭代公式为机器学习之SVM支持向量机笔记

 

而对于α1需要根据α2进行推导,由于这边的α2还不确定是否满足要求,所以稍后推导

 5.由于α是受到约束的,所以需要考虑约束 0< α < C(惩罚参数),于是就需要把之前推导的α上下限放进来考虑了

机器学习之SVM支持向量机笔记

经过这一步就可以推导α1

机器学习之SVM支持向量机笔记

 

 

6.确定参数b(根据α的值去修改b,使得间隔最大)

smo中采用求平均值得方法跟新

机器学习之SVM支持向量机笔记

但是b1、b2怎么求呢?

机器学习之SVM支持向量机笔记

 

 

总结一下SMO过程:

步骤1:计算误差(先定义f(x)表达式、在定义误差表达式E(x)。)

步骤2:计算α允许的上下限L/H

步骤3:计算η

步骤4:更新迭代α

步骤5:修剪α(让其满足上下限的要求)

步骤6:更新另一个α

步骤7:更新b1、b2

步骤8:更新b

 完整版的SMO算法(应用启发方法优化)

为了加快迭代速度。在完整版本的SMO算法中应用了启发方法

1.最外层循环,首先在样本中选择违反KKT条件的一个乘子作为最外层循环,然后用"启发式选择"选择另外一个乘子并进行这两个乘子的优化

 2.在非边界乘子中寻找使得 |Ei - Ej| 最大的样本

 3.如果没有找到,则从整个样本中随机选择一个样本

 

非线性SVM

 

代码部分

 SMO算法部分

 1 def smoSimple(dataMatIn, classLabels, C, toler, maxIter):#数据集、标签集、惩罚参数C、容错率、最大迭代次数
 2   # 转换为numpy的mat存储
 3   dataMatrix = np.mat(dataMatIn);
 4   labelMat = np.mat(classLabels).transpose()
 5   # 初始化b参数,统计dataMatrix的维度
 6   b = 0;
 7   m, n = np.shape(dataMatrix)
 8   # 初始化alpha参数,设为0
 9   alphas = np.mat(np.zeros((m, 1)))
10   # 初始化迭代次数
11   iter_num = 0
12   # 最多迭代matIter次
13   while (iter_num < maxIter):
14     alphaPairsChanged = 0
15     for i in range(m):
16       # 步骤1:计算误差Ei
17       fXi = float(np.multiply(alphas, labelMat).T * (dataMatrix * dataMatrix[i, :].T)) + b #实际是f(x)=αyx^Tx+b公式,计算类别
18       Ei = fXi - float(labelMat[i]) #计算误差
19       # 优化alpha,更设定一定的容错率,若能满足分类要求,就随机匹配另一个α
20       if ((labelMat[i] * Ei < -toler) and (alphas[i] < C)) or ((labelMat[i] * Ei > toler) and (alphas[i] > 0)):
21         # 随机选择另一个与alpha_i成对优化的alpha_j
22         j = selectJrand(i, m)
23         # 步骤1:计算误差Ej
24         fXj = float(np.multiply(alphas, labelMat).T * (dataMatrix * dataMatrix[j, :].T)) + b
25         Ej = fXj - float(labelMat[j])
26         # 保存更新前的aplpha值
27         alphaIold = alphas[i].copy();
28         alphaJold = alphas[j].copy();
29         # 步骤2:计算上下界L和H
30         if (labelMat[i] != labelMat[j]):
31           L = max(0, alphas[j] - alphas[i])
32           H = min(C, C + alphas[j] - alphas[i])
33         else:
34           L = max(0, alphas[j] + alphas[i] - C)
35           H = min(C, alphas[j] + alphas[i])
36         if L == H: print("L==H"); continue#continue表示如果L=H就跳出本次for循环,直接进入下一次for循环
37         # 步骤3:计算η
38         eta = 2.0 * dataMatrix[i,:]*dataMatrix[j,:].T - dataMatrix[i,:]*dataMatrix[i,:].T - dataMatrix[j,:]*dataMatrix[j,:].T                                                                                                                                   :].T
39         if eta >= 0: print("eta>=0"); continue
40         # 步骤4:更新alpha_j,公式中的alpha_2
41         alphas[j] -= labelMat[j] * (Ei - Ej) / eta
42         # 步骤5:修剪alpha_j
43         alphas[j] = clipAlpha(alphas[j], H, L)
44         if (abs(alphas[j] - alphaJold) < 0.00001): print("alpha_j变化太小"); continue
45         # 步骤6:更新alpha_i,公式中的alpha_1
46         alphas[i] += labelMat[j] * labelMat[i] * (alphaJold - alphas[j])
47         # 步骤7:更新b_1和b_2
48         b1 = b - Ei - labelMat[i] * (alphas[i] - alphaIold) * dataMatrix[i, :] * dataMatrix[i, :].T - labelMat[j] * (
49             alphas[j] - alphaJold) * dataMatrix[i, :] * dataMatrix[j, :].T
50         b2 = b - Ej - labelMat[i] * (alphas[i] - alphaIold) * dataMatrix[i, :] * dataMatrix[j, :].T - labelMat[j] * (
51             alphas[j] - alphaJold) * dataMatrix[j, :] * dataMatrix[j, :].T
52         # 步骤8:根据b_1和b_2更新b
53         if (0 < alphas[i]) and (C > alphas[i]):
54           b = b1
55         elif (0 < alphas[j]) and (C > alphas[j]):
56           b = b2
57         else:
58           b = (b1 + b2) / 2.0
59         # 统计优化次数
60         alphaPairsChanged += 1
61         # 打印统计信息
62         print("第%d次迭代 样本:%d, alpha优化次数:%d" % (iter_num, i, alphaPairsChanged))
63     # 更新迭代次数
64     if (alphaPairsChanged == 0):
65       iter_num += 1
66     else:
67       iter_num = 0
68     print("迭代次数: %d" % iter_num)
69   return b, alphas

 

 simpleSMO算法及其辅助函数实现的整个过程

机器学习之SVM支持向量机笔记
# -*- coding:UTF-8 -*-
from time import sleep
import matplotlib.pyplot as plt
import numpy as np
import random
import types


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


def selectJrand(i, m):# 选择一个1-m之间的随机数
    j = i
    while (j == i):
        j = int(random.uniform(0, m))
    return j

def clipAlpha(aj,H,L):#限制aj在H-L之间,用于修剪
    if aj > H:
        aj = H
    if L > aj:
        aj = L
    return aj

def smoSimple(dataMatIn, classLabels, C, toler, maxIter):#数据集、标签集、惩罚参数C、容错率、最大迭代次数
    #转换为numpy的mat存储
    dataMatrix = np.mat(dataMatIn); labelMat = np.mat(classLabels).transpose()
    #初始化b参数,统计dataMatrix的维度
    b = 0; m,n = np.shape(dataMatrix)
    #初始化alpha参数,设为0
    alphas = np.mat(np.zeros((m,1)))
    #初始化迭代次数
    iter_num = 0
    #最多迭代matIter次
    while (iter_num < maxIter):
        alphaPairsChanged = 0
        for i in range(m):
            #步骤1:计算误差Ei
            fXi = float(np.multiply(alphas,labelMat).T*(dataMatrix*dataMatrix[i,:].T)) + b
            Ei = fXi - float(labelMat[i])
            #优化alpha,更设定一定的容错率。
            if ((labelMat[i]*Ei < -toler) and (alphas[i] < C)) or ((labelMat[i]*Ei > toler) and (alphas[i] > 0)):
                #随机选择另一个与alpha_i成对优化的alpha_j
                j = selectJrand(i,m)
                #步骤1:计算误差Ej
                fXj = float(np.multiply(alphas,labelMat).T*(dataMatrix*dataMatrix[j,:].T)) + b
                Ej = fXj - float(labelMat[j])
                #保存更新前的aplpha值
                alphaIold = alphas[i].copy(); alphaJold = alphas[j].copy();
                #步骤2:计算上下界L和H
                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
                #步骤3:计算eta,η
                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
                #步骤4:更新alpha_j
                alphas[j] -= labelMat[j]*(Ei - Ej)/eta
                #步骤5:修剪alpha_j
                alphas[j] = clipAlpha(alphas[j],H,L)
                #if (abs(alphas[j] - alphaJold) < 0.00001): print("alpha_j变化太小"); continue
                #步骤6:更新alpha_i
                alphas[i] += labelMat[j]*labelMat[i]*(alphaJold - alphas[j])
                #步骤7:更新b_1和b_2
                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
                #步骤8:根据b_1和b_2更新b
                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("第%d次迭代 样本:%d, alpha优化次数:%d" % (iter_num,i,alphaPairsChanged))
        #更新迭代次数
        if (alphaPairsChanged == 0): iter_num += 1
        else: iter_num = 0
        print("迭代次数: %d" % iter_num)
    return b,alphas

def showClassifer(dataMat, w, b):
    #绘制样本点
    data_plus = []                                  #正样本
    data_minus = []                                 #负样本
    for i in range(len(dataMat)):
        if labelMat[i] > 0:
            data_plus.append(dataMat[i])
        else:
            data_minus.append(dataMat[i])
    data_plus_np = np.array(data_plus)              #转换为numpy矩阵
    data_minus_np = np.array(data_minus)            #转换为numpy矩阵
    plt.scatter(np.transpose(data_plus_np)[0], np.transpose(data_plus_np)[1], s=30, alpha=0.7)   #正样本散点图,转置作用是转置后同一列的会变同一行,相同意义的放在同一列表中,也就是X是一个列表,Y是一个列表
    plt.scatter(np.transpose(data_minus_np)[0], np.transpose(data_minus_np)[1], s=30, alpha=0.7) #负样本散点图
    #绘制直线(使用两点法画直线)
    x1 = max(dataMat)[0] #取整个数据集中最大最小的两个x值
    x2 = min(dataMat)[0]
    a1, a2 = w
    print(a1,a2)
    b = float(b)
    a1 = float(a1[0])
    a2 = float(a2[0])
    y1, y2 = (-b- a1*x1)/a2, (-b - a1*x2)/a2#利用a、x、b求取x对应的那个y,求完就可以画直线了
    plt.plot([x1, x2], [y1, y2])
    #找出支持向量点
    for i, alpha in enumerate(alphas):#enumerate将遍历的对象组合称一个索引,同时列出下标和数据
        if alpha > 0:
            x, y = dataMat[i]
            plt.scatter([x], [y], s=150, c='none', alpha=0.7, linewidth=1.5, edgecolor='red')
    plt.show()

def get_w(dataMat, labelMat, alphas):
    alphas, dataMat, labelMat = np.array(alphas), np.array(dataMat), np.array(labelMat)
    #print('打印alphas\n', alphas,'\nalpha的阶数',alphas.shape)
    w = np.dot((np.tile(labelMat.reshape(1, -1).T, (1, 2)) * dataMat).T, alphas)#yi与xi对应位置相乘,然后在矩阵点成alphas,生成一个2x1的矩阵
    #print('w为:\n',w)
    return w.tolist()# .tolist将矩阵转换为列表


if __name__ == '__main__':
    dataMat, labelMat = loadDataSet('testSet.txt')
    #print('\n打印label',labelMat,'\n打印datamat',dataMat)
    b,alphas = smoSimple(dataMat, labelMat, 0.6, 0.001, 40)
    w = get_w(dataMat, labelMat, alphas)
    showClassifer(dataMat, w, b)
View Code

 完整版本SMO算法的实现过程

# _*_ coding:UTF-8 _*_

import matplotlib.pyplot as plt
import numpy as np
import random



class optStruct: #首先定义一个结构体类,用于缓存

    def __init__(self, dataMatIn, classLabels, C, toler):
        self.X = dataMatIn                                #数据矩阵
        self.labelMat = classLabels                        #数据标签
        self.C = C                                         #松弛变量
        self.tol = toler                                 #容错率
        self.m = np.shape(dataMatIn)[0]                 #数据矩阵行数
        self.alphas = np.mat(np.zeros((self.m,1)))         #根据矩阵行数初始化alpha参数为0
        self.b = 0                                         #初始化b参数为0
        self.eCache = np.mat(np.zeros((self.m,2)))         #根据矩阵行数初始化虎误差缓存,第一列为是否有效的标志位,第二列为实际的误差E的值。

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

def calcEk(oS, k): #计算误差率

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


def selectJrand(i, m):

  j = i  # 选择一个不等于i的j
  while (j == i):
    j = int(random.uniform(0, m))
  return j

def selectJ(i, oS, Ei): #用于内循环时选择alpha值

    maxK = -1; maxDeltaE = 0; Ej = 0                         #初始化
    oS.eCache[i] = [1,Ei]                                      #根据Ei更新误差缓存
    validEcacheList = np.nonzero(oS.eCache[:,0].A)[0]        #返回误差不为0的数据的索引值
    if (len(validEcacheList)) > 1:                            #有不为0的误差
        for k in validEcacheList:                           #遍历,找到最大的Ek
            if k == i: continue                             #不计算i,浪费时间
            Ek = calcEk(oS, k)                                #计算Ek
            deltaE = abs(Ei - Ek)                            #计算|Ei-Ek|
            if (deltaE > maxDeltaE):                        #找到maxDeltaE
                maxK = k; maxDeltaE = deltaE; Ej = Ek
        return maxK, Ej                                        #返回maxK,Ej
    else:                                                   #没有不为0的误差
        j = selectJrand(i, oS.m)                            #随机选择alpha_j的索引值
        Ej = calcEk(oS, j)                                    #计算Ej
    return j, Ej                                             #j,Ej

def updateEk(oS, k):

    Ek = calcEk(oS, k)                                        #计算Ek
    oS.eCache[k] = [1,Ek]                                    #更新误差缓存


def clipAlpha(aj,H,L):

    if aj > H:
        aj = H
    if L > aj:
        aj = L
    return aj

def innerL(i, oS):

    #步骤1:计算误差Ei
    Ei = calcEk(oS, i)
    #优化alpha,设定一定的容错率。
    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)): #内层循环,simplesmo算法中是先外在内,这边把外部条件单独领出去了
        #使用内循环启发方式2选择alpha_j,并计算Ej
        j,Ej = selectJ(i, oS, Ei)
        #保存更新前的aplpha值,使用深拷贝
        alphaIold = oS.alphas[i].copy(); alphaJold = oS.alphas[j].copy();
        #步骤2:计算上下界L和H
        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:
            print("L==H")
            return 0
        #步骤3:计算eta
        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:
            print("eta>=0")
            return 0
        #步骤4:更新alpha_j
        oS.alphas[j] -= oS.labelMat[j] * (Ei - Ej)/eta
        #步骤5:修剪alpha_j
        oS.alphas[j] = clipAlpha(oS.alphas[j],H,L)
        #更新Ej至误差缓存
        updateEk(oS, j)
        if (abs(oS.alphas[j] - alphaJold) < 0.00001):
            print("alpha_j变化太小")
            return 0
        #步骤6:更新alpha_i
        oS.alphas[i] += oS.labelMat[j]*oS.labelMat[i]*(alphaJold - oS.alphas[j])
        #更新Ei至误差缓存
        updateEk(oS, i)
        #步骤7:更新b_1和b_2
        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 - 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
        #步骤8:根据b_1和b_2更新b
        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): #外循环条件

    oS = optStruct(np.mat(dataMatIn), np.mat(classLabels).transpose(), C, toler)                    #初始化数据结构
    iter = 0                                                                                         #初始化当前迭代次数
    entireSet = True; alphaPairsChanged = 0
    while (iter < maxIter) and ((alphaPairsChanged > 0) or (entireSet)):                            #遍历整个数据集都alpha也没有更新或者超过最大迭代次数,则退出循环
        alphaPairsChanged = 0
        if entireSet:                                                                                #遍历整个数据集
            for i in range(oS.m):
                alphaPairsChanged += innerL(i,oS)                                                    #使用优化的SMO算法
                print("全样本遍历:第%d次迭代 样本:%d, alpha优化次数:%d" % (iter,i,alphaPairsChanged))
            iter += 1
        else:                                                                                         #遍历非边界值
            nonBoundIs = np.nonzero((oS.alphas.A > 0) * (oS.alphas.A < C))[0]                        #遍历不在边界0和C的alpha
            for i in nonBoundIs:
                alphaPairsChanged += innerL(i,oS)
                print("非边界遍历:第%d次迭代 样本:%d, alpha优化次数:%d" % (iter,i,alphaPairsChanged))
            iter += 1
        if entireSet:                                                                                #遍历一次后改为非边界遍历
            entireSet = False
        elif (alphaPairsChanged == 0):                                                                #如果alpha没有更新,计算全样本遍历
            entireSet = True
        print("迭代次数: %d" % iter)
    return oS.b,oS.alphas                                                                             #返回SMO算法计算的b和alphas


def showClassifer(dataMat, classLabels, w, b):

    #绘制样本点
    data_plus = []                                  #正样本
    data_minus = []                                 #负样本
    for i in range(len(dataMat)):
        if classLabels[i] > 0:
            data_plus.append(dataMat[i])
        else:
            data_minus.append(dataMat[i])
    data_plus_np = np.array(data_plus)              #转换为numpy矩阵
    data_minus_np = np.array(data_minus)            #转换为numpy矩阵
    plt.scatter(np.transpose(data_plus_np)[0], np.transpose(data_plus_np)[1], s=30, alpha=0.7)   #正样本散点图
    plt.scatter(np.transpose(data_minus_np)[0], np.transpose(data_minus_np)[1], s=30, alpha=0.7) #负样本散点图
    #绘制直线
    x1 = max(dataMat)[0]
    x2 = min(dataMat)[0]
    a1, a2 = w
    b = float(b)
    a1 = float(a1[0])
    a2 = float(a2[0])
    y1, y2 = (-b- a1*x1)/a2, (-b - a1*x2)/a2
    plt.plot([x1, x2], [y1, y2])
    #找出支持向量点
    for i, alpha in enumerate(alphas):
        if abs(alpha) > 0:
            x, y = dataMat[i]
            plt.scatter([x], [y], s=150, c='none', alpha=0.7, linewidth=1.5, edgecolor='red')
    plt.show()


def calcWs(alphas,dataArr,classLabels):

    X = np.mat(dataArr); labelMat = np.mat(classLabels).transpose()
    m,n = np.shape(X)
    w = np.zeros((n,1))
    for i in range(m):
        w += np.multiply(alphas[i]*labelMat[i],X[i,:].T)
    return w

if __name__ == '__main__':
    dataArr, classLabels = loadDataSet('testSet.txt')
    b, alphas = smoP(dataArr, classLabels, 0.6, 0.001, 40)
    w = calcWs(alphas,dataArr, classLabels)
    showClassifer(dataArr, classLabels, w, b)

 

 

参考Reference

周志华《机器学习》

Peter Harrington《机器学习实战》

博文:https://blog.csdn.net/b285795298/article/details/81977271

博文:https://www.cnblogs.com/massquantity/p/10807311.html

博文:https://cuijiahua.com/blog/2017/11/ml_8_svm_1.html

以上内容仅为个人理解笔记,理解不当之处还请大佬指出来

上一篇:【线性回归】读取txt


下一篇:机器学习笔记8-Logistic回归基础