6.支持向量机
第6章 支持向量机
1 支持向量机 概述
支持向量机(Support Vector Machines, SVM): 是一种监督学习算法。
- 支持向量(Support Vector)就是离分隔超平面最近的那些点。
- 机(Machine)就是表示一种算法，而不是表示机器。
2 支持向量机 场景
- 要给左右两边的点进行分类
- 明显发现: 选择D会比B、C分隔的效果要好很多。
3 支持向量机 原理
SVM 工作原理
对于上述的苹果和香蕉，我们想象为2种水果类型的炸弹。（保证距离最近的炸弹，距离它们最远）
- 寻找最大分类间距
- 转而通过拉格朗日函数求优化的问题
- 数据可以通过画一条直线就可以将它们完全分开，这组数据叫
线性可分(linearly separable)数据，而这条分隔直线称为分隔超平面(separating hyperplane)。 - 如果数据集上升到1024维呢？那么需要1023维来分隔数据集，也就说需要N-1维的对象来分隔，这个对象叫做
超平面(hyperlane)，也就是分类的决策边界。
寻找最大间隔
点到超平面的距离
分隔超平面
函数间距:
$$y(x)=w^Tx+b$$分类的结果 (sign表示>0为1，<0为-1，=0为0) :
$$f(x)=sign(w^Tx+b)$$点到超平面的
几何间距（||w||表示w矩阵的二范数$\sqrt{w^T*w}$, 点到超平面的距离也是类似的）:
$$d(x)=(w^Tx+b)/||w||$$点到直线的距离公式
$$
d=\left|\frac{Ax_0+By_0+C}{\sqrt{A^2+B^2}}\right|
$$
拉格朗日乘子法
- 类别标签用-1、1，是为了后期方便 $label*(w^Tx+b)$ 的标识和距离计算；如果 $label*(w^Tx+b)>0$ 表示预测正确，否则预测错误。
- 现在目标很明确，就是要找到
w和b，因此我们必须要找到最小间隔的数据点，也就是前面所说的支持向量。也就说，让最小的距离取最大.(最小的距离: 就是最小间隔的数据点；最大: 就是最大间距，为了找出最优超平面–最终就是支持向量) - 目标函数:
$$arg: max_{w, b} \left( min[label*(w^Tx+b)]*\frac{1}{||w||} \right) $$ - 如果 $label*(w^Tx+b)>0$ 表示预测正确，也称
函数间隔，$||w||$ 可以理解为归一化，也称几何间隔。 - 令 $label*(w^Tx+b)>=1$， 因为0～1之间，得到的点是存在误判的可能性，所以要保障 $min[label*(w^Tx+b)]=1$，才能更好降低噪音数据影响。
- 所以本质上是求 $arg: max_{w, b}\frac{1}{||w||}$；也就说，我们约束(前提)条件是: $label*(w^Tx+b)=1$
- 如果 $label*(w^Tx+b)>0$ 表示预测正确，也称
- 新的目标函数求解:
- $arg: max_{w, b} \frac{1}{||w||}$
- => 就是求: $arg: min_{w, b} ||w||$ (求矩阵会比较麻烦，如果x只是 $\frac{1}{2}*x^2$ 的偏导数，那么。。同样是求最小值)
- => 就是求: $arg: min_{w, b} (\frac{1}{2}*||w||^2)$ (二次函数求导，求极值，平方也方便计算)
- 本质上就是求线性不等式的二次优化问题(求分隔超平面，等价于求解相应的凸二次规划问题)
- 通过拉格朗日乘子法，求二次优化问题。假设需要求极值的目标函数 (objective function) 为 f(x,y)，限制条件为 φ(x,y)=M # M=1。设g(x,y)=M-φ(x,y) # 临时φ(x,y)表示下文中
$$label*(w^Tx+b)$$
- 定义一个新函数: F(x,y,λ)=f(x,y)+λg(x,y)a为λ（a>=0），代表要引入的拉格朗日乘子(Lagrange multiplier)那么:
$$L(w,b,\alpha)=\frac{1}{2} * ||w||^2 + \sum_{i=1}^{n} \alpha_i * [1 - label * (w^Tx+b)]$$
- 因为:
$$label*(w^Tx+b)>=1, \alpha>=0$$
- 所以
$$\alpha*[1-label*(w^Tx+b)]<=0$$
$$\sum_{i=1}^{n} \alpha_i * [1-label*(w^Tx+b)]<=0$$ - 当
$$label*(w^Tx+b)>1$$ - 则
$$\alpha=0$$ - 表示该点为非支持向量相当于求解:
$$max_{\alpha} L(w,b,\alpha) = \frac{1}{2} *||w||^2$$ - 如果求:
$$min_{w, b} \frac{1}{2} *||w||^2$$ - 也就是要求:
$$min_{w, b} \left( max_{\alpha} L(w,b,\alpha)\right)$$ - 现在转化到对偶问题的求解
$$min_{w, b} \left(max_{\alpha} L(w,b,\alpha) \right)>= max_{\alpha} \left(min_{w, b}\ L(w,b,\alpha) \right)$$ - 现在分2步先求:
$$min_{w, b} L(w,b,\alpha)=\frac{1}{2} * ||w||^2 + \sum_{i=1}^{n} \alpha_i * [1 - label * (w^Tx+b)]$$ - 就是求
L(w,b,a)关于[w, b]的偏导数, 得到w和b的值，并化简为:L和a的方程。参考: 如果公式推导还是不懂，也可以参考《统计学习方法》李航-P103<学习的对偶算法>
- 终于得到课本上的公式:
$$max_{\alpha} \left( \sum_{i=1}^{m} \alpha_i - \frac{1}{2} \sum_{i, j=1}^{m} label_i \ast label_j \ast \alpha_i \ast \alpha_j \ast <x_i, x_j> \right) $$ - 约束条件:
$$a>=0$$
$$\sum_{i=1}^{m} a_i \ast label_i=0$$
松弛变量(slack variable)
参考地址: http://blog.csdn.net/wusecaiyun/article/details/49659183
- 我们知道几乎所有的数据都不那么干净, 通过引入松弛变量来
允许数据点可以处于分隔面错误的一侧。 - 约束条件: $$C>=a>=0$$ 并且 $$\sum_{i=1}^{m} a_i \ast label_i=0$$
- 总的来说:
表示 松弛变量- 常量C是
惩罚因子, 表示离群点的权重（用于控制“最大化间隔”和“保证大部分点的函数间隔小于1.0” ）- $$label*(w^Tx+b) > 1$$ and alpha = 0 (在边界外，就是非支持向量)
- $$label*(w^Tx+b) = 1$$ and 0< alpha < C (在分割超平面上，就支持向量)
- $$label*(w^Tx+b) < 1$$ and alpha = C (在分割超平面内，是误差点 -> C表示它该受到的惩罚因子程度)
- 参考地址: https://www.zhihu.com/question/48351234/answer/110486455
- C值越大，表示离群点影响越大，就越容易过度拟合；反之有可能欠拟合。
- 我们看到，目标函数控制了离群点的数目和程度，使大部分样本点仍然遵守限制条件。
- 例如: 正类有10000个样本，而负类只给了100个（C越大表示100个负样本的影响越大，就会出现过度拟合，所以C决定了负样本对模型拟合程度的影响！，C就是一个非常关键的优化点！）
- 这一结论十分直接，SVM中的主要工作就是要求解 alpha.
SMO 高效优化算法
- SVM有很多种实现，最流行的一种实现是:
序列最小优化(Sequential Minimal Optimization, SMO)算法。 - 下面还会介绍一种称为
核函数(kernel)的方式将SVM扩展到更多数据集上。 - 注意:
SVM几何含义比较直观，但其算法实现较复杂，牵扯大量数学公式的推导。
序列最小优化(Sequential Minimal Optimization, SMO)
- 创建作者: John Platt
- 创建时间: 1996年
- SMO用途: 用于训练 SVM
- SMO目标: 求出一系列 alpha 和 b,一旦求出 alpha，就很容易计算出权重向量 w 并得到分隔超平面。
- SMO思想: 是将大优化问题分解为多个小优化问题来求解的。
- SMO原理: 每次循环选择两个 alpha 进行优化处理，一旦找出一对合适的 alpha，那么就增大一个同时减少一个。
- 这里指的合适必须要符合一定的条件
- 这两个 alpha 必须要在间隔边界之外
- 这两个 alpha 还没有进行过区间化处理或者不在边界上。
- 之所以要同时改变2个 alpha；原因是我们有一个约束条件: $$\sum_{i=1}^{m} a_i \ast label_i=0$$；如果只是修改一个 alpha，很可能导致约束条件失效。
- 这里指的合适必须要符合一定的条件
SMO 伪代码大致如下:
1 | 创建一个 alpha 向量并将其初始化为0向量 |
SVM 开发流程
1 | 收集数据: 可以使用任意方法。 |
SVM 算法特点
1 | 优点: 泛化（由具体的、个别的扩大为一般的，就是说: 模型训练完后的新样本）错误率低，计算开销不大，结果易理解。 |
4 课本案例（无核函数）
项目概述
对小规模数据点进行分类
开发流程
收集数据
文本文件格式:
1 | 3.542485 1.977398 -1 |
准备数据
1 | def loadDataSet(fileName): |
分析数据: 无
训练算法
1 | def smoSimple(dataMatIn, classLabels, C, toler, maxIter): |
5 核函数(kernel) 使用
- 对于线性可分的情况，效果明显
- 对于非线性的情况也一样，此时需要用到一种叫
核函数(kernel)的工具将数据转化为分类器易于理解的形式。
利用核函数将数据映射到高维空间
- 使用核函数: 可以将数据从某个特征空间到另一个特征空间的映射。（通常情况下: 这种映射会将低维特征空间映射到高维空间。）
- 如果觉得特征空间很装逼、很难理解。
- 可以把核函数想象成一个包装器(wrapper)或者是接口(interface)，它能将数据从某个很难处理的形式转换成为另一个较容易处理的形式。
- 经过空间转换后: 低维需要解决的非线性问题，就变成了高维需要解决的线性问题。
- SVM 优化特别好的地方，在于所有的运算都可以写成内积(inner product: 是指2个向量相乘，得到单个标量 或者 数值)；内积替换成核函数的方式被称为
核技巧(kernel trick)或者核"变电"(kernel substation) - 核函数并不仅仅应用于支持向量机，很多其他的机器学习算法也都用到核函数。最流行的核函数: 径向基函数(radial basis function)
- 径向基函数的高斯版本，其具体的公式为:
6 项目案例: 手写数字识别的优化（有核函数）
项目概述
1 | 你的老板要求: 你写的那个手写识别程序非常好，但是它占用内存太大。顾客无法通过无线的方式下载我们的应用。 |
开发流程
收集数据: 提供的文本文件
1 | 00000000000000001111000000000000 |
准备数据: 基于二值图像构造向量
将 32*32的文本转化为 1*1024的矩阵
1 | def img2vector(filename): |
分析数据: 对图像向量进行目测
训练算法: 采用两种不同的核函数，并对径向基核函数采用不同的设置来运行SMO算法
1 | def kernelTrans(X, A, kTup): # calc the kernel or transform data to a higher dimensional space |
测试算法: 便携一个函数来测试不同的和函数并计算错误率
1 | def testDigits(kTup=('rbf', 10)): |
使用算法: 一个图像识别的完整应用还需要一些图像处理的知识，这里并不打算深入介绍
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 Estom的博客！
相关推荐
2022-10-14
05 Spring5日志&测试
框架新功能 基于java8，兼容jdk9 本质上，Spring容器的管理有三种主要的方式 xml配置方式，能够通过xml声明bean，并且注入bean的属性 注解方式，通过@Bean@Component创建bean，通过@Autowire注入bean 函数方式，同构register函数讲普通的java对象注册为bean，通过context.getBean获取 日志功能自带了通用的日志封装。可以整合第三方日志工具log4j&slf4j slf4j是中间层 log4j是日志引擎，实现了slf4j提供的接口。可以配合使用 12345678910111213141516<?xml version="1.0" encoding="UTF-8"?><configuration> <appenders> <console name="Console" target="SYSTEM_OUT"> <Pa...
2021-09-02
filepath
概述filepath包的功能和path包类似，但是对于不同操作系统提供了更好的支持。filepath包能够自动的根据不同的操作系统文件路径进行转换，所以如果你有跨平台的需求，你需要使用filepath。 与path包相同的函数filepath包中的函数和path包很类似，其中对应函数的功能相同，只是一个可以跨平台，一个不能，所以这里不详细展开，可以从 path 中获取这些函数的详细说明。主要函数如下： func Base(path string) string func Dir(path string) string func Ext(path string) string func Join(elem …string) string func Split(path string) (dir, file string) 其他函数剩下的还有两个函数值得一说，一个是Abs函数，可以将一个文件路径转换为绝对路径。函数声明如下： 1func Abs(path string) (string, error) 另一个是Walk函数，和filepath包中的其他函数不同，它并不对文件路径...
2020-09-27
4.朴素贝叶斯
第4章 基于概率论的分类方法: 朴素贝叶斯1 朴素贝叶斯 概述贝叶斯分类是一类分类算法的总称，这类算法均以贝叶斯定理为基础，故统称为贝叶斯分类。本章首先介绍贝叶斯分类算法的基础——贝叶斯定理。最后，我们通过实例来讨论贝叶斯分类的中最简单的一种: 朴素贝叶斯分类。 2 贝叶斯理论 & 条件概率贝叶斯理论 我们现在有一个数据集，它由两类数据组成，数据分布如下图所示: 我们现在用 p1(x,y) 表示数据点 (x,y) 属于类别 1（图中用圆点表示的类别）的概率，用 p2(x,y) 表示数据点 (x,y) 属于类别 2（图中三角形表示的类别）的概率，那么对于一个新数据点 (x,y)，可以用下面的规则来判断它的类别: 如果 p1(x,y) > p2(x,y) ，那么类别为1 如果 p2(x,y) > p1(x,y) ，那么类别为2 也就是说，我们会选择高概率对应的类别。这就是贝叶斯决策理论的核心思想，即选择具有最高概率的决策。 条件概率 有一个装了 7 块石头的罐子，其中 3 块是白色的，4 块是黑色的。如果从罐子中随机取出一块石头，那么是白色石头的...
2020-09-29
083D与动画
3D与动画基本方法本章知识点归纳如下: 创建3D图：ax = Axes3D(fig) 画出3D图：ax.plot_surface() 投影：ax.contourf() 动画：animation.FuncAnimation() 3D作图首先在进行 3D Plot 时除了导入 matplotlib ，还要额外添加一个模块，即 Axes 3D 3D 坐标轴显示,并且之后要先定义一个图像窗口，在窗口上添加3D坐标轴，显示成下图： 123456import numpy as npimport matplotlib.pyplot as pltfrom mpl_toolkits.mplot3d import Axes3Dfig = plt.figure()ax = Axes3D(fig) 接下来给进 X 和 Y 值，并将 X 和 Y 编织成栅格。每一个（X, Y）点对应的高度值我们用下面这个函数来计算: 1234567# X, Y valueX = np.arange(-4, 4, 0.25)Y = np.arange(-4, 4, 0.25)X, Y = np.mesh...
2021-03-09
14 注册表文件修改
数据库注册表修改心得 几个月前跟随导员用xampp做的集成开发环境进行Apache服务器上的php网站开发项目 近几日大作业老师要求使用深喉咙的php继承开发环境，结果现在的mysql不听话，各种出错！！！ 端口冲突： 由于xampp，深喉咙加上我自己的电脑，总共装了三个版本的mysql，导致端口占用等问题时有发生，所以吧xampp和深喉咙的mysql直接删掉，反而不能启动了！ 注册表修改： 后来发现，深喉咙自动修改了注册表，原来一直启动的并不是电脑上的mysql，而是深喉咙自带的mysql，修改注册表。 （http://jingyan.baidu.com/article/91f5db1bd298ed1c7f05e315.html） 但是登录的时候报了一个奇怪的错误， mysqlnd cannot connect to MySQL 4.1+ using the old insecure authentication后来查证，是因为前不久不小心更新了xampp，导致数据库中原来密码出现问题，密码格式不能被新版的phpmyadmin解析，于是看教程，经过PASSWORD()函数...
2021-03-20
a_demo_of_the_spectral_co-clustering_algorithm
频谱共聚算法演示 翻译者：@N!no校验者：待校验 这个例子演示了如何使用谱协聚类算法生成数据集并对其进行双聚类处理。 数据集是使用 make_biclusters 函数生成的，该函数创建一个小值矩阵，并将大值植入双聚类。然后将行和列打乱并传递给光谱协聚算法。通过重新排列变换后的矩阵可以使双聚类连续，这展示出该算法找到双聚类的准确性。 1consensus score: 1.0 123456789101112131415161718192021222324252627282930313233343536373839404142print(__doc__)# Author: Kemal Eren <kemal@kemaleren.com># License: BSD 3 clauseimport numpy as npfrom matplotlib import pyplot as pltfrom sklearn.datasets import make_biclustersfrom sklearn.cluster import SpectralCoclus...
