Python3：《机器学习实战》之支持向量机（2）简化版SMO

2024-06-09 08:58
文章标签 实战 学习 机器 支持 python3 向量 简化版 smo

本文主要是介绍Python3：《机器学习实战》之支持向量机（2）简化版SMO，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Python3：《机器学习实战》之支持向量机（2）简化版SMO

  • 转载请注明作者和出处：http://blog.csdn.net/u011475210
  • 代码地址：https://github.com/WordZzzz/ML/tree/master/Ch06
  • 操作系统：WINDOWS 10
  • 软件版本：python-3.6.2-amd64
  • 编  者：WordZzzz

  • Python3机器学习实战之支持向量机2简化版SMO
    • 前言
    • Platt的SMO算法
    • 应用简化版SMO算法处理小规模数据集

前言

  SVM有很多实现，但我们只关注其中最流行的一种实现，即序列最小优化（ Sequential MInimal Optimization，SMO ）算法。

  下面我们就开始讨论SMO算法，本篇博文先给出一个简化的版本，以便我们能够正确理解它的工作流程。

Platt的SMO算法

  1996年，伟大的John Platt发布了一个称为SMO的强大算法，用于训练SVM。Platt的SMO算法是将大优化问题分解为多个小优化问题来求解的。这些小优化问题往往很容易求解，并且对它们进行顺序来求解的结果与将他们作为整体来求解的结果是完全一致的，但是求解时间却大大缩短。

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

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

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

  Platt SMO算法中的外循环确定要优化的最佳alpha对。而简化版会跳过这一部分，首先在数据集上遍历每一个alpha，然后在剩下的alpha集合中随机选择另一个alpha来构成alpha对。这里有一点相当重要，就是我们要同时改变两个alpha，因为我们需要满足一个约束条件：

$$
\sum \alpha_i · label^{(i)} = 0
$$

  由于改变一个alpha可能会导致该约束条件失效，因为需要同时改变两个alpha，一增一减，改变的量相同。

  在实现简化版SMO之前，我们需要先构造几个辅助函数。打开文本编辑器，将下面的代码加入svmMLiA.py中。

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Date    : 2017-09-21 21:02:51
# @Author  : WordZzzz (wordzzzz@foxmail.com)
# @Link    : http://blog.csdn.net/u011475210from numpy import *
from time import sleepdef loadDataSet(fileName):"""Function：   加载数据集Input：      fileName：数据集Output： dataMat：数据矩阵labelMat：类别标签矩阵""" #初始化数据列表dataMat = []#初始化标签列表labelMat = []#打开文件fr = open(fileName)#遍历每一行数据，读取数据和标签for line in fr.readlines():#strip删除头尾空白字符，然后再进行分割lineArr = line.strip().split('\t')#填充数据集dataMat.append([float(lineArr[0]), float(lineArr[1])])#填充类别标签labelMat.append(float(lineArr[2]))#返回数据集和标签列表return dataMat, labelMatdef selectJrand(i, m):"""Function：   随机选择Input：      i：alpha下标m：alpha数目Output： j：随机选择的alpha下标""" #初始化下标jj = i#随机化产生j，直到不等于iwhile (j == i):j = int(random.uniform(0,m))#返回j的值return jdef clipAlpha(aj, H, L):"""Function：   设定alpha阈值Input：      aj：alpha的值H：alpha的最大值L：alpha的最小值Output： aj：处理后的alpha的值""" #如果输入alpha的值大于最大值，则令aj=Hif aj > H:aj = H#如果输入alpha的值小于最小值，则令aj=Lif L > aj:aj = L#返回处理后的alpha的值return aj

  首先是我们熟悉的老哥loadDataSet()，用来打开文件并对其进行解析，从而得到每行的类别标签和整个数据矩阵；然后是selectJrand()，用来随机选择第二个alpha的下标（只要和第一个alpha下标不一样就行）；最后一个是clipAlpha()函数，用于设定阈值，限制alpha的值。

>>> reload(svmMLiA)
<module 'svmMLiA' from 'E:\\机器学习实战\\mycode\\Ch06\\svmMLiA.py'>
>>> dataArr, labelArr = svmMLiA.loadDataSet('testSet.txt')
>>> labelArr
[-1.0, -1.0, 1.0, -1.0, 1.0, 1.0, 1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, 1.0, -1.0, 1.0, 1.0, -1.0, 1.0, -1.0, -1.0, -1.0, 1.0, -1.0, -1.0, 1.0, 1.0, -1.0, -1.0, -1.0, -1.0, 1.0, 1.0, 1.0, 1.0, -1.0, 1.0, -1.0, -1.0, 1.0, -1.0, -1.0, -1.0, -1.0, 1.0, 1.0, 1.0, 1.0, 1.0, -1.0, 1.0, 1.0, -1.0, -1.0, 1.0, 1.0, -1.0, 1.0, -1.0, -1.0, -1.0, -1.0, 1.0, -1.0, 1.0, -1.0, -1.0, 1.0, 1.0, 1.0, -1.0, 1.0, 1.0, -1.0, -1.0, 1.0, -1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, -1.0, -1.0, -1.0, -1.0, 1.0, -1.0, 1.0, 1.0, 1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0]
>>>

  简化版SMO伪代码：

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

  下述代码是SMO算法中的一个有效版本，如果看不懂，可以先找SVM的公式推导看看。打开文本编辑器，将下面的代码加入svmMLiA.py中。

def smoSimple(dataMatIn, classLabels, C, toler, maxIter):"""Function：   简化版SMO算法Input：      dataMatIn：数据集classLabels：类别标签C：常数Ctoler：容错率maxIter：最大的循环次数Output： b：常数项alphas：数据向量""" #将输入的数据集和类别标签转换为NumPy矩阵dataMatrix = mat(dataMatIn); labelMat = mat(classLabels).transpose()#初始化常数项b，初始化行列数m、nb = 0; m,n = shape(dataMatrix)#初始化alphas数据向量为0向量alphas = mat(zeros((m,1)))#初始化iter变量，存储的是在没有任何alpha改变的情况下遍历数据集的次数iter = 0#外循环，当迭代次数小于maxIter时执行while (iter < maxIter):#alpha改变标志位每次都要初始化为0alphaPairsChanged = 0#内循环，遍历所有数据集for i in range(m):#multiply将alphas和labelMat进行矩阵相乘，求出法向量w(m,1),w`(1,m)#dataMatrix * dataMatrix[i,:].T，求出输入向量x(m,1)#整个对应输出公式f(x)=w`x + bfXi = float(multiply(alphas, labelMat).T * (dataMatrix * dataMatrix[i,:].T)) + b#计算误差Ei = fXi - float(labelMat[i])#如果标签与误差相乘之后在容错范围之外，且超过各自对应的常数值，则进行优化if ((labelMat[i]*Ei < -toler) and (alphas[i] < C)) or ((labelMat[i] * Ei > toler) and (alphas[i] > 0)):#随机化选择另一个数据向量j = selectJrand(i, m)#对此向量进行同样的计算fXj = float(multiply(alphas, labelMat).T * (dataMatrix * dataMatrix[j,:].T)) + b#计算误差Ej = fXj - float(labelMat[j])#利用copy存储刚才的计算值，便于后期比较alphaIold = alphas[i].copy(); alpahJold = alphas[j].copy()#保证alpha在0和C之间if (labelMat[i] != labelMat[j]):L = max(0, alphas[j] - alphas[i])H = min(C, C + alphas[j] - alphas[i])else:L = max(0, alphas[j] + alphas[i] - C)H = min(C, alphas[j] + alphas[i])#如果界限值相同，则不做处理直接跳出本次循环if L == H: print("L == H"); continue#最优修改量，求两个向量的内积（核函数）eta = 2.0 * dataMatrix[i,:] * dataMatrix[j,:].T - dataMatrix[i,:] * dataMatrix[i,:].T - dataMatrix[j,:] * dataMatrix[j,:].T#如果最优修改量大于0，则不做处理直接跳出本次循环，这里对真实SMO做了简化处理if eta >= 0: print("eta >= 0"); continue#计算新的alphas[j]的值alphas[j] -= labelMat[j] * (Ei - Ej) / eta#对新的alphas[j]进行阈值处理alphas[j] = clipAlpha(alphas[j], H, L)#如果新旧值差很小，则不做处理跳出本次循环if (abs(alphas[j] - alpahJold) < 0.00001): print("j not moving enough"); continue#对i进行修改，修改量相同，但是方向相反alphas[i] += labelMat[j] * labelMat[i] * (alpahJold - alphas[j])#新的常数项b1 = b - Ei - labelMat[i] * (alphas[i] - alphaIold) * dataMatrix[i,:] * dataMatrix[i,:].T - labelMat[i] * (alphas[j] - alpahJold) * dataMatrix[i,:] * dataMatrix[j,:].Tb2 = b - Ej - labelMat[i] * (alphas[i] - alphaIold) * dataMatrix[i,:] * dataMatrix[j,:].T - labelMat[j] * (alphas[j] - alpahJold) * dataMatrix[j,:] * dataMatrix[j,:].T#谁在0到C之间，就听谁的，否则就取平均值if (0 < alphas[i]) and (C > alphas[i]): b = b1elif (0 < alphas[j]) and (C > alphas[j]): b = b2else: b = (b1 + b2) / 2.0#标志位加1alphaPairsChanged += 1#输出迭代次数，alphas的标号以及标志位的值print("iter: %d i: %d, pairs changed %d" % (iter, i, alphaPairsChanged))#如果标志位没变，即没有进行优化，那么迭代值加1if (alphaPairsChanged == 0): iter += 1#否则迭代值为0else: iter = 0#打印迭代次数print("iteration number: %d" % iter)#返回常数项和alphas的数据向量return b, alphas

  运行结果如下：

>>> reload(svmMLiA)
<module 'svmMLiA' from 'E:\\机器学习实战\\mycode\\Ch06\\svmMLiA.py'>
>>> b, alphas = svmMLiA.smoSimple(dataArr, labelArr, 0.6, 0.001, 40)
iter: 0 i: 0, pairs changed 1
j not moving enough
j not moving enough
iter: 0 i: 5, pairs changed 2
j not moving enough
j not moving enough
iter: 0 i: 17, pairs changed 3
j not moving enough
j not moving enough
j not moving enough
j not moving enough
j not moving enough
j not moving enough
j not moving enough
iter: 0 i: 54, pairs changed 4
j not moving enough
j not moving enough
L == H
j not moving enough
L == H
j not moving enough
iteration number: 0
j not moving enough
iter: 0 i: 5, pairs changed 1
···
···
iteration number: 0
j not moving enough
j not moving enough
j not moving enough
iteration number: 1
j not moving enough
j not moving enough
j not moving enough
···
···
j not moving enough
j not moving enough
j not moving enough
iteration number: 39
j not moving enough
j not moving enough
j not moving enough
iteration number: 40

  上述过程可能需要几分钟才会收敛，一旦运行结束，我们就可以对结果进行查看：

>>> b
matrix([[-3.87260031]])
>>> alphas[alphas > 0]
matrix([[ 0.10195497,  0.25933768,  0.0240785 ,  0.33721415]])
>>> from numpy import *
>>> shape(alphas[alphas > 0])
(1, 4)
>>> for i in range(100):
...     if alphas[i] > 0.0: print(dataArr[i], labelArr[i])
... 
[4.658191, 3.507396] -1.0
[3.457096, -0.082216] -1.0
[5.286862, -2.358286] 1.0
[6.080573, 0.418886] 1.0
>>>

  由于SMO算法的随机性，每次运行之后得到的结果不尽相同。alphas[alphas > 0]命令是数组过滤的一个实例，得到仅仅包含大于0的值的矩阵，而且它只对NumPy类型有用，却并不适用于Python中的正则表。

  我们在数据集上把这些支持向量画出来：

  希望通过本篇博文，大家对SMO的工作流程有了一定得了解，至于完成版的SMO，WordZzzz将会在下一篇博文介绍给大家。

系列教程持续发布中，欢迎订阅、关注、收藏、评论、点赞哦～～(￣▽￣～)～

完的汪(∪｡∪)｡｡｡zzz

这篇关于Python3：《机器学习实战》之支持向量机（2）简化版SMO的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1044740。

相关文章

Golang使用minio替代文件系统的实战教程

Golang使用minio替代文件系统的实战教程

《Golang使用minio替代文件系统的实战教程》本文讨论项目开发中直接文件系统的限制或不足,接着介绍Minio对象存储的优势,同时给出Golang的实际示例代码,包括初始化客户端、读取minio对... 目录文件系统 vs Minio文件系统不足：对象存储：miniogolang连接Minio配置Min
阅读更多...
Python3中Sanic中间件的使用

Python3中Sanic中间件的使用

《Python3中Sanic中间件的使用》Sanic框架中的中间件是一种强大的工具,本文就来介绍Python3中Sanic中间件的使用,具有一定的参考价值,感兴趣的可以了解一下... 目录Sanic 中间件的工作流程中间件的使用1. 全局中间件2. 路由中间件3. 异常处理中间件4. 异步中间件5. 优先级
阅读更多...
Node.js 中 http 模块的深度剖析与实战应用小结

Node.js 中 http 模块的深度剖析与实战应用小结

《Node.js中http模块的深度剖析与实战应用小结》本文详细介绍了Node.js中的http模块,从创建HTTP服务器、处理请求与响应,到获取请求参数,每个环节都通过代码示例进行解析,旨在帮... 目录Node.js 中 http 模块的深度剖析与实战应用一、引言二、创建 HTTP 服务器：基石搭建（一
阅读更多...
网页解析 lxml 库--实战

网页解析 lxml 库--实战

lxml库使用流程 lxml 是 Python 的第三方解析库，完全使用 Python 语言编写，它对 XPath表达式提供了良好的支 持，因此能够了高效地解析 HTML/XML 文档。本节讲解如何通过 lxml 库解析 HTML 文档。 pip install lxml lxm| 库提供了一个 etree 模块，该模块专门用来解析 HTML/XML 文档，下面来介绍一下 lxml 库
阅读更多...
HarmonyOS学习(七)——UI（五）常用布局总结

HarmonyOS学习(七)——UI（五）常用布局总结

自适应布局 1.1、线性布局（LinearLayout） 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列，Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距，达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式，且在各类尺寸屏幕上表现一致，其中交叉轴为垂直时，取值为Vert
阅读更多...
Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya（不是本人，claude AI）在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容： 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用
阅读更多...
【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【课程链接】 AntV G6：深入图形与图形分组、自定义节点、节点动画（下）_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中，应该怎样去计算和绘制图形，如何给一个图形制作不间断的动画，以及在鼠标事件之后产生动画。（有点难，需要好好理解） <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06
阅读更多...
学习hash总结

学习hash总结

2014/1/29/   最近刚开始学hash，名字很陌生，但是hash的思想却很熟悉，以前早就做过此类的题，但是不知道这就是hash思想而已，说白了hash就是一个映射，往往灵活利用数组的下标来实现算法，hash的作用：1、判重；2、统计次数；
阅读更多...
性能分析之MySQL索引实战案例

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题，本文将一起从代码层去分析为什么没有建立索引？ 开源ERP项目地址：https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2