0
0

机器学习——支持向量机

一、基本概念

1.1支持向量机

支持向量：距超平面（c）距离最近的点

支持向量平面：恰好过这些点的平面（a、b）

支持向量机（support vector machines，SVM）是一种二分类模型，它的目的是寻找一个超平面来对样本进行分割，分割的原则是间隔最大化，最终转化为一个凸二次规划问题来求解。

1.2超平面

    由于数据点都在二维平面上，所以此时分隔超平面就只是一条直线。但是，如果所给的数据集是三维的，那么此时用来分隔数据的就是一个平面。显而易见，更高维的情况可以依此类推。当数据集是N维时，需要一个N-1维的某某对象来对数据进行分隔。N-1维的该对象被称为超平面（hyperplane），也就是分类的决策边界。 分布在超平面一侧的所有数据都属于某个类别，而分布在另一侧的所有数据则属于另一个类别。** **

1.3支持向量机分类

二、最大间隔与分类

2.1一个线性相关的例子

下面举个简单的例子，如下图所示，现在有一个二维平面，平面上有两种不同的数据，分别用圈和叉表示。由于这些数据是线性可分的，所以可以用一条直线将这两类数据分开，这条直线就相当于一个超平面，超平面一边的数据点所对应的y全是 -1 ，另一边所对应的y全是1。

这个超平面可以用分类函数表示，当f(x) 等于0的时候，x便是位于超平面上的点，而f(x)大于0的点对应 y=1 的数据点，f(x)小于0的点对应y=-1的点。 接下来的问题是，如何确定这个超平面呢？从直观上而言，这个超平面应该是最适合分开两类数据的直线。而判定“最适合”的标准就是这条直线离直线两边的数据的间隔最大（容忍性好，鲁棒性高，泛化能力最强）。所以，得寻找有着最大间隔的超平面。

2.2最大间隔

SVM中，分隔超平面是一个能够将正负样本恰好隔开的超平面，并且使得正样本在分隔超平面“上方”，负样本在分隔超平面”下方“。这就意味着w^{T}x+b=0，分隔超平面中的w,b需要满足以下条件：

w^{T}x_{i}+b>0,if y_{i}=+1

w^{T}x_{i}+b<0,if y_{i}=-1

即：\exists w,b y_{i}(w^{T}x_{i}+b)>0 \Rightarrow \exists w,b,c y_{i}(w^{T}x_{i}+b)\geqslant c and c>0

\Rightarrow \exists w,b y_{i}(w^{T}x_{i}+b)\geqslant 1

于是对于训练数据D={x}D=\left \{ x_{i},y_{i} \right \}_{i=1}^{m} x\epsilon \mathbb{R}^{n},y\epsilon \left \{ -1,+1 \right \}，当且仅当

\exists w,b s.t. y_{i}(w^{T}x_{i}+b)\geqslant 1时线性可分

间隔d=\frac{2}{\left \| w \right \|}

解释一下这个间隔的由来：上图中的x1点代入得到式1：w^{T}x_{1}+b=1,x2代入得到式2：w^{T}x_{2}+b =-1，将式1-式2得到：w^{T}(\vec{x}_{1}-\vec{x}_{2})=2，根据向量相乘的性质

\left \| w \right \|\cdot \left \| \vec{x}_{1}-\vec{x}_{2} \right \|\cdot cos\theta =2，由上图可以看出​​​​​​​\left \| \vec{x}_{1}-\vec{x}_{2} \right \|\cdot cos\theta =d，即\left \| w \right \|\cdot d=2，

所以d=\frac{2}{\left \| w \right \|}

最大化间隔也就是寻找参数w和b , 使得d最大，即：

\underset{w,b}{arg max}\frac{2}{\left \| w \right \|}

s.t. y_{i}(w^{T}x_{i}+b)\geq 1,i=1,2,\cdots ,m

求\frac{2}{\left \| w \right \|}的最大值，就是求其倒数的最小值，求最大值我们利用求导获取极值来解题，为了简化计算，因此问题可以等价于求\frac{\left \| w \right \|^{2}}{2}的最小值：

\underset{w,b}{arg min}\frac{1}{2}\left \| w \right \|^{2}

s.t. y_{i}(w^{T}x_{i}+b)\geq 1,i=1,2,\cdots ,m

上式就是求解最大间隔超平面的表达式。

三、对偶问题

3.1不等式约束的KKT条件

给定一个目标函数 f : Rn→R，希望找到x∈Rn ，在满足约束条件g(x)=0的前提下，使得f(x)有最小值。该约束优化问题记为：

min f(x)

s.t. g(x)=0

可建立拉格朗日函数：L(x,\lambda )=f(x)+\lambda g(x)

其中 λ 称为拉格朗日乘数。因此，可将原本的约束优化问题转换成等价的无约束优化问题：

\underset{x,\lambda }{min}L(x,\lambda )​​​​​​​

分别对待求解参数求偏导，可得：

\triangledown _{x}^{}\textrm{L}=\frac{\partial L}{\partial x}=\bigtriangledown f+\lambda \bigtriangledown g(x)=0

\bigtriangledown _{\lambda }L=\frac{\partial L}{\partial \lambda }=g(x)=0

一般联立方程组可以得到相应的解。

将约束等式 g(x)=0 推广为不等式 g(x)≤0。这个约束优化问题可改为：

min f(x)

s.t. g(x)\leq 0

同理，其拉格朗日函数为：

L(x,\lambda )=f(x)+\lambda g(x)

拉格朗日乘子法的几何意义即在等式g(x)=0或在不等式约束g(x)≤0下最小化目标函数f(x)，如下图：

​​​​​​​

其约束范围为不等式，因此可等价转换为Karush-Kuhn-Tucker (KKT)条件

\bigtriangledown _{x}L=\bigtriangledown f+\lambda \bigtriangledown g=0

g(x)\leq 0

\lambda \geq 0

\lambda g(x)=0

在此基础上，通过优化方式（如二次规划或SMO）求解其最优解。

3.2拉格朗日乘法

我们先看一下支持向量机的目标函数与约束函数：

\underset{w,b}{arg min}\frac{1}{2}\left \| w \right \|^{2}

s.t. y_{i}(w^{T}x_{i}+b)\geq 1,i=1,2,\cdots ,m

第一步：引入拉格朗日乘子a_{i}\geq 0得到拉格朗日函数

L(w,b,\alpha )=\frac{1}{2}\left \| w \right \|^{2}-\sum_{i=1}^{m}\alpha_{i}(y_{i}(w^{T}x_{i}+b)-1)

第二步：令L(w,b,\alpha )对w和b的偏导为零

w=\sum_{i=1}^{m}\alpha _{i}y_{i}x_{i},\sum_{i=1}^{m}\alpha _{i}y_{i}=0

第三步：w,b回代到第一步

\underset{\alpha }{min}\frac{1}{2}\sum_{i=1}^{j=1}\alpha _{i}\alpha _{j}y_{i}y_{j}x_{i}^{T}x_{j}-\sum_{i=1}^{m}\alpha _{i}

s.t. \sum_{i=1}^{m}\alpha _{i}y_{i}=0,\alpha _{i}\geq 0,i=1,2,\cdots ,m

第四步：转换为对偶形式

\underset{\alpha }{max}\sum_{i=1}^{m}\alpha _{i}-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha _{i}\alpha _{j}y_{i}y_{j}x_{i}^{T}x_{j}

s.t. \sum_{i=1}^{m}\alpha _{i}y_{i}=0

第五步：最终模型

f(x)=w^{T}x+b=\sum_{i=1}^{m}\alpha _{i}y_{i}x_{i}^{T}x+b，未知数为\alpha _{i}

四、SMO算法

4.1SMO算法的基本思路：

1.如果所有的变量的解都满足最优化问题的KKT条件 那么这个最优化问题的解就得到了
2.否则选择两个变量 固定其他变量(任意选择两个拉格朗日乘子) 针对这两个变量构建一个二次规划问题
这个二次规划问题关于这两个变量的解应该更加接近二次规划问题的解 使得二次规划问题的目标函数值变得更小
3.此时: 子问题有两个变量 一个是违反KKT条件最严重的一个 一个是由约束条件自动确定的

注意: 选择两个变量实质上只有一个自由变量
因为等式约束:\sum_{i=1}^{m}\alpha _{i}y_{i}=0​​​​​​​
重点:SMO算法实质上包含两个部分

  1. 求解两个变量二次规划的解析方法

2.选择变量的启发式方法

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

数据集：

from numpy import *
import matplotlib.pyplot as plt
 
# 读取数据
def loadDataSet(fileName):
    dataMat = []                                               # 数据矩阵
    labelMat = []                                              # 数据标签
    fr = open(fileName)                                        # 打开文件
    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

# 绘制数据集
def showData():
    dataMat, labelMat = loadDataSet('SVMdata.txt')         # 加载数据集，标签
    dataArr = array(dataMat)                               # 转换成numPy的数组
    n = shape(dataArr)[0]                                  # 获取数据总数
    xcord1 = []; ycord1 = []                               # 存放正样本
    xcord2 = []; ycord2 = []                               # 存放负样本
    for i in range(n):                                     # 依据数据集的标签来对数据进行分类
        if int(labelMat[i]) == 1:                          # 数据的标签为1，表示为正样本
            xcord1.append(dataArr[i, 0]); ycord1.append(dataArr[i, 1])
        else:                                              # 否则，若数据的标签不为1，表示为负样本
            xcord2.append(dataArr[i, 0]); ycord2.append(dataArr[i, 1])
    fig = plt.figure()
    ax = fig.add_subplot(111)
    ax.scatter(xcord1, ycord1, s=15, c='blue')             # 绘制正样本
    ax.scatter(xcord2, ycord2, s=15, c='red', marker='s')  # 绘制负样本
    plt.title('DateSet')                                   # 标题
    plt.xlabel('X1'); plt.ylabel('X2')                     # x，y轴的标签
    plt.show()

showData()

运行结果

这就是我们使用的二维数据集，显然线性可分。现在我们使用简化版的SMO算法进行求解。

from numpy import *
import matplotlib.pyplot as plt
 
# 读取数据
def loadDataSet(fileName):
    dataMat = []                                               # 数据矩阵
    labelMat = []                                              # 数据标签
    fr = open(fileName)                                        # 打开文件
    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

# 随机选择alpha
def selectJrand(i, m):
    j = i                               # 选择一个不等于i的j
    while (j == i):                     # 只要函数值不等于输入值i，函数就会进行随机选择
        j = int(random.uniform(0, m))
    return j
 
# 修剪alpha
def clipAlpha(aj, H, L):                # 用于调整大于H或小于L的alpha值
    if aj > H:
        aj = H
    if L > aj:
        aj = L
    return aj

# 简化版SMO算法
def smoSimple(dataMatIn, classLabels, C, toler, maxIter):
    dataMatrix = mat(dataMatIn)              # 数据矩阵dataMatIn转换为numpy的mat存储
    labelMat = mat(classLabels).transpose()  # 数据标签classLabels转换为numpy的mat存储
    b = 0; m, n = shape(dataMatrix)          # 初始化b参数，统计dataMatrix的维度m*n
    alphas = mat(zeros((m, 1)))              # 初始化alpha参数为0
    iter = 0                                 # 初始化迭代次数0
    while (iter < maxIter):                  # matIter表示最多迭代次数，iter变量达到输入值maxIter时，函数结束运行并退出
        alphaPairsChanged = 0                # 变量alphaPairsChanged用于记录alpha是否已经进行优化
        for i in range(m):
            # 步骤1：计算误差Ei
            fXi = float(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)):
                j = selectJrand(i, m)        # 随机选择另一个与alpha_i成对优化的alpha_j
 
                # 步骤1：计算误差Ej
                fXj = float(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("j not moving enough")
                    continue
 
                # 步骤6：更新alpha_i
                alphas[i] += labelMat[j] * labelMat[i] * (alphaJold - alphas[j])  # 按与alpha_j相同的方法更新alpha_i
 
                # 步骤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, i, alphaPairsChanged))
 
        # 更新迭代次数
        if (alphaPairsChanged == 0):
            iter += 1
        else:
            iter = 0
        print("迭代次数: %d" % iter)
    return b, alphas

# 计算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

# 绘制数据集以及划分直线
def showDataLine(w, b):
    x, y = loadDataSet('SVMdata.txt')
    xarr = array(x)
    n = shape(x)[0]
    x1 = []; y1 = []
    x2 = []; y2 = []
    for i in arange(n):
        if int(y[i]) == 1:
            x1.append(xarr[i, 0]);
            y1.append(xarr[i, 1])
        else:
            x2.append(xarr[i, 0]);
            y2.append(xarr[i, 1])
 
    plt.scatter(x1, y1, s=30, c='r', marker='s')
    plt.scatter(x2, y2, s=30, c='g')
 
    # 画出 SVM 分类直线
    xx = arange(0, 10, 0.1)
    # 由分类直线 weights[0] * xx + weights[1] * yy1 + b = 0 易得下式
    yy1 = (-w[0] * xx - b) / w[1]
    # 由分类直线 weights[0] * xx + weights[1] * yy2 + b + 1 = 0 易得下式
    yy2 = (-w[0] * xx - b - 1) / w[1]
    # 由分类直线 weights[0] * xx + weights[1] * yy3 + b - 1 = 0 易得下式
    yy3 = (-w[0] * xx - b + 1) / w[1]
    plt.plot(xx, yy1.T)
    plt.plot(xx, yy2.T)
    plt.plot(xx, yy3.T)
 
    # 画出支持向量点
    for i in range(n):
        if alphas[i] > 0.0:
            plt.scatter(xarr[i, 0], xarr[i, 1], s=150, c='none', alpha=0.7, linewidth=1.5, edgecolor='red')
 
    plt.xlim((-2, 12))
    plt.ylim((-8, 6))
    plt.show()

# 主函数
if __name__ == '__main__':
    dataMat, labelMat = loadDataSet('SVMdata.txt')
    b, alphas = smoSimple(dataMat, labelMat, 0.6, 0.001, 40)
    w = calcWs(alphas, array(dataMat), labelMat)
    showDataLine(w, b)

运行结果：

中间的蓝线为求出来的分类器，用红圈和橙圈圈出的点为支持向量点。

运行结果看起来并不是太差，但是这只是一个仅有100个点的小规模数据集。在更大的数据集上，收敛时间会变得更长。接下来，我们通过构建完整SMO算法来加快其运行速度。

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

# 读取数据
def loadDataSet(fileName):
    dataMat = []                                               # 数据矩阵
    labelMat = []                                              # 数据标签
    fr = open(fileName)                                        # 打开文件
    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
 
# 随机选择alpha
def selectJrand(i, m):
    j = i                               # 选择一个不等于i的j
    while (j == i):                     # 只要函数值不等于输入值i，函数就会进行随机选择
        j = int(random.uniform(0, m))
    return j
 
# 修剪alpha
def clipAlpha(aj, H, L):                # 用于调整大于H或小于L的alpha值
    if aj > H:
        aj = H
    if L > aj:
        aj = L
    return aj

# 类
class optStruct:
    def __init__(self, dataMatIn, classLabels, C, toler, kTup):  # 使用参数初始化结构
        self.X = dataMatIn                                       # 数据矩阵
        self.labelMat = classLabels                              # 数据标签
        self.C = C                                               # 松弛变量
        self.tol = toler                                         # 容错率
        self.m = shape(dataMatIn)[0]                             # 数据矩阵行数m
        self.alphas = mat(zeros((self.m, 1)))                    # 根据矩阵行数初始化alpha参数为0
        self.b = 0                                               # 初始化b参数为0
        self.eCache = mat(zeros((self.m, 2))) 

# 计算误差
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):
    maxK = -1; maxDeltaE = 0; Ej = 0     # 初始化
    oS.eCache[i] = [1, Ei]               # 选择给出最大增量E的alpha
    validEcacheList = nonzero(oS.eCache[:, 0].A)[0]
    if (len(validEcacheList)) > 1:
        for k in validEcacheList:        # 循环使用有效的Ecache值并找到使delta E最大化的值
            if k == i: continue          # 如果k对于i，不计算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
    else:                                # 在这种情况下（第一次），没有任何有效的eCache值
        j = selectJrand(i, oS.m)         # 随机选择alpha_j的索引值
        Ej = calcEk(oS, j)
    return j, Ej

#  计算Ek并更新误差缓存
def updateEk(oS, k):                     # 任何alpha更改后，更新缓存中的新值
    Ek = calcEk(oS, k)
    oS.eCache[k] = [1, Ek]

# 优化的SMO算法
def innerL(i, oS):
    Ei = calcEk(oS, i)                   # 计算误差Ei
    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)):
        # 使用内循环启发方式选择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("j not moving enough"); 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

# 完整的线性SMO算法
def smoP(dataMatIn, classLabels, C, toler, maxIter,kTup=('lin', 0)):
    oS = optStruct(mat(dataMatIn),mat(classLabels).transpose(), C, toler, kTup)# 初始化
    iter = 0                                                                   # 初始化迭代次数为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 = 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):
            entireSet = True
        print("迭代次数: %d" % iter)
    return oS.b, oS.alphas

# 计算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

# 绘制数据集以及划分直线
def showData(w, b):
    x, y = loadDataSet('SVMdata.txt')
    xarr = array(x)
    n = shape(x)[0]
    x1 = []; y1 = []
    x2 = []; y2 = []
    for i in arange(n):
        if int(y[i]) == 1:
            x1.append(xarr[i, 0]);
            y1.append(xarr[i, 1])
        else:
            x2.append(xarr[i, 0]);
            y2.append(xarr[i, 1])
 
    plt.scatter(x1, y1, s=30, c='r', marker='s')
    plt.scatter(x2, y2, s=30, c='g')
 
    # 画出 SVM 分类直线
    xx = arange(0, 10, 0.1)
    # 由分类直线 weights[0] * xx + weights[1] * yy1 + b = 0 易得下式
    yy1 = (-w[0] * xx - b) / w[1]
    # 由分类直线 weights[0] * xx + weights[1] * yy2 + b + 1 = 0 易得下式
    yy2 = (-w[0] * xx - b - 1) / w[1]
    # 由分类直线 weights[0] * xx + weights[1] * yy3 + b - 1 = 0 易得下式
    yy3 = (-w[0] * xx - b + 1) / w[1]
    plt.plot(xx, yy1.T)
    plt.plot(xx, yy2.T)
    plt.plot(xx, yy3.T)
 
    # 画出支持向量点
    for i in range(n):
        if alphas[i] > 0.0:
            plt.scatter(xarr[i, 0], xarr[i, 1], s=150, c='none', alpha=0.7, linewidth=1.5, edgecolor='red')
 
    plt.xlim((-2, 12))
    plt.ylim((-8, 6))
    plt.show()

if __name__ == '__main__':
    dataMat, labelMat = loadDataSet('SVMdata.txt')
    b, alphas = smoP(dataMat, labelMat, 0.6, 0.001, 40)
    w = calcWs(alphas, array(dataMat), labelMat)
    showData(w, b)

运行结果

在数据集上运行完整版SMO算法之后得到的支持向量，其结果与简单SMO稍有不同。

五、总结

优点:

  • 可用于线性/非线性分类，也可以用于回归，泛化错误率低，也就是说具有良好的学习能力，且学到的结果具有很好的推广性。
  • 可以解决小样本情况下的机器学习问题，可以解决高维问题，可以避免神经网络结构选择和局部极小点问题。
  • SVM是最好的现成的分类器，现成是指不加修改可直接使用。并且能够得到较低的错误率，SVM可以对训练集之外的数据点做很好的分类决策。

缺点：

  • 对参数调节和和函数的选择敏感。

适用的数据类型：

  • 数值型和标称型数据

标签： 人工智能
本文转载自: https://blog.csdn.net/m0_54703897/article/details/128282898
版权归原作者 装进了牛奶箱中 所有， 如有侵权，请联系我们删除。
登录后发布评论

“机器学习——支持向量机”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

网络安全法-网络运行安全

使用selenium/drissionpage时如何阻止chrome自动跳转http到https

docker desktop 里部署的Open WebUI 管理员密码忘记了的处理方法

在ubuntu20.04中搭建onsite比赛运行环境

利用开源的低代码表单设计器FcDesigner高效管理和渲染复杂表单结构

Kafka学习笔记

【前端】浏览器输入url到页面呈现发生了什么？

文章导航