1. Toy模板网首页
  2. > Toy博客

机器学习（六）支持向量机（SVM）

9月前 作者：Ag11 分类：Toy博客 阅读(51) 违法举报

这篇具有很好参考价值的文章主要介绍了机器学习（六）支持向量机（SVM）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

目录

1.间隔与支持向量

1.1线性可分

1.2支持向量

1.3 最大间隔超平面

2.对偶问题

2.1拉格朗日乘子法

2.2 SMO算法

2.3SMO算法代码实现

3.核函数

4. SVM实例（手写体数字识别）

5.实验总结

支持向量机（SVM）是有监督学习中最有影响力的机器学习算法之一，一般用于解决二分类问题（也可以解决分类和回归问题）。与逻辑回归和神经网络相比，支持向量机，在学习复杂的非线性方程时提供了一种更为清晰，更加强大的方式。

1.间隔与支持向量

1.1线性可分

机器学习（六）支持向量机（SVM）

在二维空间上，两类点被一条直线完全分开叫做线性可分。

严格的数学定义是：

和是n维欧氏空间中的两个点集。如果存在 n 维向量 w 和实数 b，使得所有属于的点都有机器学习（六）支持向量机（SVM），而对于所有属于的点则有机器学习（六）支持向量机（SVM），则我们称和线性可分

1.2支持向量

从二维扩展到多维空间中时，将和  完全正确地划分开的机器学习（六）支持向量机（SVM）就成了一个超平面。

在样本空间中，划分超平面可通过如下线性方程来描述：

                                机器学习（六）支持向量机（SVM）

其中为法向量，决定了超平面的方向；b为位移项，决定了超平面与原点之间的距离。

给定训练样本集机器学习（六）支持向量机（SVM），分类学习最基本的想法
就是基于训练集D在样本空间中找到一个划分超平面，将不同类别的样本分开，但能将训练样本分
开的划分超平面可能有很多，如图所示，我们应努力去找到哪一个呢？

 机器学习（六）支持向量机（SVM）

直观上看，应该去找位于两类训练样本"正中间"的划分超平面，即上图中红色的那个，因为该划分
超平面对训练样本局部扰动的“容忍”性最好。例如，由于训练集的局限性或噪声的因素，训练集外
的样本可能比上图中的训练样本更接近两个类的分隔界，这将使许多划分超平面出现错误，而红色
的超平面受影响最小。
划分超平面可被法向量w和位移b确定，下面我们将其记为(w,b)。样本空间中任意点x到超平面(w,b)的距离可写为：
                                         机器学习（六）支持向量机（SVM）
假设超平面(w,b)能将训练样本正确分类，即对于 ，若 机器学习（六）支持向量机（SVM），则有 机器学习（六）支持向量机（SVM）；若 ，则有 机器学习（六）支持向量机（SVM）
                                         机器学习（六）支持向量机（SVM）

如下图所示， 距离超平面最近的这几个训练样本点使上述不等式中等号成立，被称为支持向量

                                        机器学习（六）支持向量机（SVM）

1.3 最大间隔超平面

间隔：
令 机器学习（六）支持向量机（SVM）和 位于决策边界上，标签分别为正、负的两个样本， 机器学习（六）支持向量机（SVM）到分类线的距离为
机器学习（六）支持向量机（SVM）， 到分类线的距离为 机器学习（六）支持向量机（SVM），则两个异类支持向量到超平面的距离之和为 

                                        

它被称为“间隔”

机器学习（六）支持向量机（SVM）

最大间隔平面：以最大间隔把两类样本分开的超平面
  • 两类样本分别分割在该超平面的两侧；
  • 两侧距离超平面最近的样本点到超平面的距离被最大化了。
SVM的最优化问题就是要找到各类样本点到超平面的距离最远，也就是找到最大间隔超平面 
训练数据： 
机器学习（六）支持向量机（SVM）

线性可分当且仅当: 

 机器学习（六）支持向量机（SVM）

 在数学上，我们可以得到以下式子等效：

机器学习（六）支持向量机（SVM）

所以，为了方便后续的计算，简化方程为：

机器学习（六）支持向量机（SVM）

最大化间隔：寻找参数w和b，使得间隔最大，即

 ​​​                           机器学习（六）支持向量机（SVM）

                           机器学习（六）支持向量机（SVM）

通过数学知识可知，求的最大值，就是求的最小值，求最大值我们利用求导获取极值来解题，为了简化计算，因此问题可以等价于求的最小值：

                             机器学习（六）支持向量机（SVM）

                             机器学习（六）支持向量机（SVM）（1.1）

这就是支持向量机(Support Vector Machine ，简称 SVM) 的基本型.

2.对偶问题

我们希望求解式（1.1）来得到大间隔划分超平面所对应的模型 

                        机器学习（六）支持向量机（SVM）

其中w和b是模型参数。式（1.1）本身是一个凸二次规划，能直接用现成的优化计算包求解，但我们可以有更高效的办法。

2.1拉格朗日乘子法

在求解最优化问题中，拉格朗日乘子法（Lagrange Multiplier）和KKT（Karush Kuhn Tucker）条件是两种最常用的方法。在有等式约束时使用拉格朗日乘子法，在有不等约束时使用KKT条件。

等式约束：

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

                                机器学习（六）支持向量机（SVM）

可建立拉格朗日函数：

                                机器学习（六）支持向量机（SVM）

其中 λ 称为拉格朗日乘数。因此，可将原本的约束优化问题转换成等价的无约束优化问题：机器学习（六）支持向量机（SVM）

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

                                机器学习（六）支持向量机（SVM）

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

 不等式约束的KKT条件：

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

                                机器学习（六）支持向量机（SVM）

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

                           机器学习（六）支持向量机（SVM）       

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

                                机器学习（六）支持向量机（SVM）

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

 最大间隔问题的拉格朗日乘法：

支持向量机的目标函数与约束函数：

                         机器学习（六）支持向量机（SVM）

                        机器学习（六）支持向量机（SVM）

 第一步：引入拉格朗日乘子 ≥0得到拉格朗日函数

                        机器学习（六）支持向量机（SVM）

第二步：令机器学习（六）支持向量机（SVM）对w和b的偏导为零：

                         机器学习（六）支持向量机（SVM）

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

第四步：从而得到对偶问题

                        机器学习（六）支持向量机（SVM）

等价形式（式2.1）：

 机器学习（六）支持向量机（SVM）

第五步：此式为关于机器学习（六）支持向量机（SVM）的极大值求解，当求出解机器学习（六）支持向量机（SVM）之后，求出机器学习（六）支持向量机（SVM），有

                        机器学习（六）支持向量机（SVM）

 根据多约束推广的KKT条件，推出支持向量机优化问题的KKT条件：

                      机器学习（六）支持向量机（SVM）

对于不在最大边缘边界上的点:机器学习（六）支持向量机（SVM）

支持向量机解的稀疏性: 训练完成后, 大部分的训练样本都不需保留, 最终模型仅与支持向量有关.

 机器学习（六）支持向量机（SVM）

2.2 SMO算法

式（2.1）是一个二次规划问题，可使用通用的二次规划算法来求解；然而，该问题的规模正比于训练样本数，这会在实际任务中造成很大的开销。为了避开这个障碍，人们通过利用问题本身的特性，提出了很多高效算法， SMO 是其中一个著名的代表。

SMO(Sequential Minimal Optimization)，序列最小优化算法，其核心思想非常简单：每次只优化一个参数，其他参数先固定住，仅求当前这个优化参数的极值

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


基本思路：不断执行如下两个步骤直至收敛.

  • 第一步：选取一对需更新的变量α_i和 α_j.
  • 第二步：固定α_i和 α_j以外的参数, 求解对偶问题更新α_i和 α_j.

仅考虑α_i和 α_j时, 对偶问题的约束变为:

                机器学习（六）支持向量机（SVM）

 偏移项b：通过支持向量来确定

算法流程：

机器学习（六）支持向量机（SVM）

假设最优解为 ：机器学习（六）支持向量机（SVM）

可得：

机器学习（六）支持向量机（SVM）

 得到分类平面： 机器学习（六）支持向量机（SVM）

2.3SMO算法代码实现

对小数据集（数据集来源《机器学习实战》）：

机器学习（六）支持向量机（SVM）

 绘制数据集：

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('\t')                     # 去除空格
        dataMat.append([float(lineArr[0]), float(lineArr[1])]) # 数据矩阵中添加数据
        labelMat.append(float(lineArr[2]))                     # 数据标签中添加标签
    return dataMat, labelMat


# 绘制数据集
def showData():
    dataMat, labelMat = loadDataSet('D:/syy/MachineLearning/machinelearninginaction/Ch06/testSet.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()

 运行结果如图：

机器学习（六）支持向量机（SVM）

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

简化版SMO算法

# 随机选择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('D:/syy/MachineLearning/machinelearninginaction/Ch06/testSet.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('D:/syy/MachineLearning/machinelearninginaction/Ch06/testSet.txt')
    b, alphas = smoSimple(dataMat, labelMat, 0.6, 0.001, 40)
    w = calcWs(alphas, array(dataMat), labelMat)
    showDataLine(w, b)

运行结果如图：

机器学习（六）支持向量机（SVM）

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

 上面我们实现了在100个点组成的小规模数据集上的简化版SMO算法，运行效果是可行的，但是在更大 的数据集上的运行速度就会变慢。完整版的Platt SMO算法应用了一些能够提速的启发方法。

算法原理：

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

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

代码实现：

# 读取数据
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
 
# 随机选择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('D:/syy/MachineLearning/machinelearninginaction/Ch06/testSet.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()

运行结果：

机器学习（六）支持向量机（SVM）

3.核函数

我们可能会碰到的一种情况是样本点不是线性可分的，比如：

 机器学习（六）支持向量机（SVM）

 这种情况的解决方法就是：将二维线性不可分样本映射到高维空间中，让样本点在高维空间线性可分

 对于在有限维度向量空间中线性不可分的样本，我们将其映射到更高维度的向量空间里，再通过间隔最大化的方式，学习得到支持向量机，就是非线性 SVM。

我们用 x 表示原来的样本点，用 表示 x 映射到特征新的特征空间后到新向量。那么分割超平面可以表示为：机器学习（六）支持向量机（SVM）

对于非线性 SVM 的对偶问题就变成了：

                        机器学习（六）支持向量机（SVM）

核函数的作用：

我们有这样的一核函数 k(x,y)=(ϕ(x),ϕ(y))，  与 在特征空间的内积等于它们在原始样本空间中通过函数 k(x,y) 计算的结果，我们就不需要计算高维甚至无穷维空间的内积了。

常见核函数：

机器学习（六）支持向量机（SVM）

4. SVM实例（手写体数字识别）

使用SVM实现手写体数字识别

数据集来源《机器学习实战》

机器学习（六）支持向量机（SVM）

代码如下：

from numpy import *
 
# 随机选择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)))                    # 第一列是有效标志
        self.K = mat(zeros((self.m,self.m)))                     # 初始化核K
        for i in range(self.m):                                  # 计算所有数据的核K
            self.K[:,i] = kernelTrans(self.X, self.X[i,:], kTup)
 
# 通过核函数将数据转换更高维的空间
def kernelTrans(X, A, kTup):
    m,n = shape(X)
    K = mat(zeros((m,1)))
    if kTup[0] == 'lin': K = X * A.T                       #线性核函数,只进行内积。
    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))                      #计算高斯核K
    else: raise NameError('核函数无法识别')
    return K
 
# 计算误差
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 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.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]
 
        # 步骤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
 
# 图像转换为向量
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)     # 加载训练集
    m = len(trainingFileList)
    trainingMat = zeros((m, 1024))
    for i in range(m):
        fileNameStr = trainingFileList[i]
        fileStr = fileNameStr.split('.')[0]
        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)):
    dataArr, labelArr = loadImages('D:/syy/MachineLearning/machinelearninginaction/Ch06/trainingDigits')
    b, alphas = smoP(dataArr, labelArr, 200, 0.0001, 10000, kTup)
    datMat = mat(dataArr);
    labelMat = mat(labelArr).transpose()
    svInd = nonzero(alphas.A > 0)[0]
    sVs = datMat[svInd]
    labelSV = labelMat[svInd];
    print("支持向量机是 %d " % 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
    print("训练集错误率: %f" % (float(errorCount) / m))
    dataArr, labelArr = loadImages('D:/syy/MachineLearning/machinelearninginaction/Ch06/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("测试错误率: %f" % (float(errorCount) / m))

运行结果如下：

机器学习（六）支持向量机（SVM）

5.实验总结

 SVM的优缺点

优点:

  • 有严格的数学理论支持，可解释性强，不依靠统计方法，从而简化了通常的分类和回归问题；
  • 能找出对任务至关重要的关键样本（即：支持向量）；
  • 采用核技巧之后，可以处理非线性分类/回归任务；
  • 最终决策函数只由少数的支持向量所确定，计算的复杂性取决于支持向量的数目，而不是样本空间的维数，这在某种意义上避免了“维数灾难”。

 缺点：

  • 训练时间长。当采用 SMO 算法时，由于每次都需要挑选一对参数，因此时间复杂度为 O(N2) ，其中 N 为训练样本的数量；
  • 当采用核技巧时，如果需要存储核矩阵，则空间复杂度为 O(N2) ；
  • 模型预测时，预测时间与支持向量的个数成正比。当支持向量的数量较大时，预测计算复杂度较高。

      SVM算法中有较多公式需要推导，理解起来有一定难度

代码：

链接：https://pan.baidu.com/s/1HiVpS6YV3ODkTho0FN_TAQ 
提取码：n9t9文章来源地址https://www.toymoban.com/news/detail-488601.html

到了这里，关于机器学习（六）支持向量机（SVM）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 机器学习-支持向量机SVM

    机器学习-支持向量机SVM

    在本练习中，我们将使用支持向量机（SVM）来构建垃圾邮件分类器。 我们将从一些简单的2D数据集开始使用SVM来查看它们的工作原理。 然后，我们将对一组原始电子邮件进行一些预处理工作，并使用SVM在处理的电子邮件上构建分类器，以确定它们是否为垃圾邮件。 我们要做

    2024年02月12日
    浏览(51)
  • 【机器学习】支持向量机SVM入门

    【机器学习】支持向量机SVM入门

    相较于之前学习的线性回归和神经网络，支持向量机（Supprot Vector Machine，简称SVM）在拟合复杂的非线性方程的时候拥有更出色的能力，该算法也是十分经典的算法之一。接下来我们需要学习这种算法 首先我们回顾逻辑回归中的经典假设函数，如下图： 对于任意一个实例 (

    2024年02月15日
    浏览(52)
  • 机器学习算法：支持向量机（SVM）

    机器学习算法：支持向量机（SVM）

    Solem《python计算机视觉编程》、李航《统计学习方法》、周志华《机器学习》 要理解好支持向量机需要较好的数学功底，且能不被公式以及文字绕晕，这里我们就理清楚支持向量机的大体过程。具体的数学计算推导其实已经封装好了，那么理解算法的原理也对我们将来的学习

    2024年02月03日
    浏览(49)
  • 机器学习（六）支持向量机（SVM）

    机器学习（六）支持向量机（SVM）

    目录 1.间隔与支持向量 1.1线性可分 1.2支持向量 1.3 最大间隔超平面 2.对偶问题 2.1拉格朗日乘子法 2.2 SMO算法 2.3SMO算法代码实现 3.核函数 4. SVM实例（手写体数字识别） 5.实验总结 支持向量机（SVM） 是有监督学习中最有影响力的机器学习算法之一，一般用于解决二分类问题（

    2024年02月09日
    浏览(51)
  • 【机器学习】SVM支持向量机模型

    【机器学习】SVM支持向量机模型

     本站原创文章，转载请说明来自 《老饼讲解-机器学习》 ml.bbbdata.com 目录 一. SVM的目标和思想    1.1 SVM硬间隔模型的原始目的 1.2 SVM的直接目标 1.3 什么是支持向量  二. SVM的支持平面的表示方式 2.1 支持面表示方式的初步思路 2.2 初步思路的缺陷与改进 2.3 支持面的最终表示

    2023年04月23日
    浏览(186)

  • 机器学习：基于支持向量机（SVM）进行人脸识别预测

    作者：i阿极 作者简介：Python领域新星作者、多项比赛获奖者：博主个人首页 😊😊😊如果觉得文章不错或能帮助到你学习，可以点赞👍收藏📁评论📒+关注哦！👍👍👍 📜📜📜如果有小伙伴需要数据集和学习交流，文章下方有交流学习区！一起学习进步！💪 专栏案例：

    2024年01月23日
    浏览(47)
  • 机器学习：Python中如何使用支持向量机(SVM)算法

    机器学习：Python中如何使用支持向量机(SVM)算法

    (简单介绍一下支持向量机，详细介绍尤其是算法过程可以查阅其他资) 在机器学习领域，支持向量机SVM(Support Vector Machine)是一个有监督的学习模型，通常用来进行模式识别、分类(异常值检测)以及回归分析。 其具有以下特征： (1)SVM可以表示为凸优化问题，因此可以利用已知的

    2024年02月04日
    浏览(53)
  • 第29步 机器学习分类实战：支持向量机（SVM）建模

    第29步 机器学习分类实战：支持向量机（SVM）建模

    支持向量机（SVM）建模。 先复习一下参数（传送门），需要调整的参数有： ① kernel：{‘linear’, ‘poly’, ‘rbf’, ‘sigmoid’, ‘precomputed’}，默认为’rbf’。使用的核函数，必须是“linear”，“poly”，“rbf”，“sigmoid”，“precomputed”或者“callable”中的一个。 ② c：浮点

    2024年02月02日
    浏览(64)
  • [学习笔记] [机器学习] 10. 支持向量机 SVM（SVM 算法原理、SVM API介绍、SVM 损失函数、SVM 回归、手写数字识别）

    [学习笔记] [机器学习] 10. 支持向量机 SVM（SVM 算法原理、SVM API介绍、SVM 损失函数、SVM 回归、手写数字识别）

    视频链接 数据集下载地址：无需下载 学习目标： 了解什么是 SVM 算法 掌握 SVM 算法的原理 知道 SVM 算法的损失函数 知道 SVM 算法的核函数 了解 SVM 算法在回归问题中的使用 应用 SVM 算法实现手写数字识别器 学习目标： 了解 SVM 算法的定义 知道软间隔和硬间隔 在很久以前的

    2024年02月09日
    浏览(88)
  • 机器学习实战：Python基于支持向量机SVM-RFE进行分类预测（三）

    机器学习实战：Python基于支持向量机SVM-RFE进行分类预测（三）

    1.1 支持向量机的介绍 支持向量机（ Support Vector Machine，SVM ）是一种监督学习的分类算法。它的基本思想是找到一个能够最好地将不同类别的数据分开的超平面，同时最大化分类器的边际（margin）。SVM的训练目标是最大化间隔（margin），即支持向量到超平面的距离。 具体地，

    2024年02月05日
    浏览(61)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包