支持向量机

作者: Zaker_cook | 来源:发表于2019-12-12 15:15 被阅读0次

【转载】pluskid的SVM系列博文
【机器学习实战】第6章支持向量机（Support Vector
SVM支持向量机
编程作业（六）
支持向量机-QA
支持向量机
机器学习——libSVM（一）
支持向量机&&聚类
支持向量机
【9%】100小时机器学习——支持向量机SVM

问题

1. 支持向量机是如何进行数据分类？

2. 支持向量机求解过程

3. 支持向量机是怎么对线性不可分和非线性可分的数据进行分类？

4. 支持向量机主要有哪些优缺点？

5. 怎么对支持向量机进行优化？

1. 支持向量机是如何进行数据分类

支持向量机是在空间中寻找一个超平面，能够让最近的点离这个超平面越远越好，如下图所示，能够让分类间隔越大越好

支持向量机

只关注最近的点，主要是因为远离超平面的点，基本上是分对的点。

2. 支持向量机求解过程

图示

因为 $wx_i + b = \pm 1$ ， $y_i \in \{+1,-1\}$ ，所以 $y_i(wx_i+b)\geq 1$

因为 $d = \frac{\vert w^T x + b \vert }{\vert\vert w \vert\vert }$ ，其中 $\vert \vert w\vert \vert = \sqrt{w^2 } =\sqrt{w^T w}$

所以 $d = \frac{1}{\vert \vert w \vert\vert}$ ，支持向量到超平面的函数距离一般设置为1

因为要寻找能够让支持向量离超平面的最大间隔，所以数学表达式如下表示

$d = MAX _{w,b} \frac{1}{\vert \vert w \vert \vert }$

S.T $y_i(w_ix+b)\geq 1$ ，i=1,2,....,m

上式可等价于

$d = MIN_{w,b} \frac{1}{2} \vert \vert w \vert \vert ^2$

S.T $1- y_i(wx_i+b)\leq 0$

求解约束不等式最小值，可依据拉格朗日乘子法和 KKT条件

根据拉格朗日乘子法，则

$L_{w,b,\alpha} = \frac{1}{2} \vert \vert w \vert \vert ^2 + \sum_{i=1}^n \alpha_i[1-y_i(wx_i+b)]$

则优化目标通过 KKT条件变为

$min_{w,b}max_{\alpha} L_{w,b,\alpha} = max_\alpha min_{w,b} L_{w,b,\alpha}$

分别对 w，b 求导，可得

$\frac{\sigma L_{w,b,\alpha}}{\sigma w} = w + 0 -\sum_{i=1}^n \alpha_ix_iy_i -0 =0$ ，则 $w=\sum_{i=1}^n \alpha_ix_iy_i$

$\frac{\sigma L_{w,b,\alpha}}{\sigma b} = 0+0-0-\sum_{i=1}^n \alpha_iy_i = 0$ ，则 $\sum_{i=1}^n \alpha_iy_i = 0$

将 w, b 求导后的结果代入 $L_{w,b,\alpha}$ ，可得

$min_{w,b}L_{w,b,\alpha} = \sum_{i=1}^n \alpha_i - \frac{1}{2} \sum_{i=1,j=1}^n \alpha_i\alpha_jy_iy_jx_i^Tx_j$

S.T $\sum_{i=1}^n \alpha_iy_i = 0$ ， $\alpha_i \geq 0$

则 $max_\alpha L_{w,b,\alpha} = min_{\alpha}-L_{w,b,\alpha}$ ,所以

$min_\alpha - L_{w,b,\alpha} = \sum_{i=1,j=1}^n \alpha_i\alpha_jy_iy_jx_i^Tx_j - \sum_{i=1}^n \alpha_i$

S.T $\sum_{i=1}^n \alpha_iy_i = 0 , \alpha \geq 0$

通过SMO算法，求解 $\alpha$ 的值

3. 支持向量机对线性不可分数据以及非线性可分数据分类

对于线性不可分数据，即在线性可分数据中含有异常数据导致的。可通过软间隔进行处理

软间隔

目标函数如下：

$min_{w,b} \frac{1}{2} \vert \vert w\vert \vert ^2 + C\sum_{i=1}^n\xi _i$

S.T $y_i(wx_i+b) \geq 1-\xi$

$\xi$ 是松弛因子， $C$ 是惩罚系数。 $\xi$ 越大，距离超平面越近，当大于1时，则允许样本有错分的情况。当 $C$ 越小，则容许多数样本分错，即使 $\xi$ 越大，都可以控制在较小的范围内， $C$ 越大，要求样本少分错，使得 $\xi$ 越小

对于非线性可分的数据，将它从低维空间映射到高维空间，可让其变为线性可分，从而可以使用线性可分或软间隔模型。虽然非线性可分数据是从低维空间映射到高维空间，但它却是在低维空间进行计算，再将分类效果表现在高维。

目标函数如下：

$min_\alpha \frac{1}{2} \sum_{i=1,j=1}^n \alpha_i\alpha_jy_iy_j\phi (x_i)\phi(x_j) - \sum_{i=1}^n\alpha_i$

S.T $\sum_{i=1}^n \alpha_iy_i = 0$ , $0\leq \alpha_i\leq C, i=1,2,3,...,n$

为了避免从低维特征空间映射到高维特征空间所引起的向量内积的恐怖计算量，为解决这一问题，可以使用 核函数

核函数，指的是如果存在函数K(x, z)，对于任意的低维特征向量x，z，都有 $K(x,z) = \phi (x)\phi(z)$

核函数

核函数主要有以下几种

a. 线性核函数 $K(x,z) = x\bullet z$

b. 多项式核函数 $K(x,z) = (\gamma x\bullet z+r)^d , 其中 \gamma 、r、d都是参数$

c. 高斯核函数(常用) $K(x,z) = e^{-\gamma \vert\vert x-z\vert \vert ^2 },其中超参数\gamma >0$

d. sigmoid 核函数 $K(x,y)=tanh(\gamma x\bullet z+r),其中\gamma 、r是超参数$

4. 支持向量机的优缺点

优点

a. 支持向量机计算复杂性由支持向量的数量决定，而不是样本空间的维度决定，避免了维数灾难

b. 少数支持向量决定最终结果，对异常值不敏感，且具有较好的鲁棒性。鲁棒性主要体现在对非支持向量的增删，不会对模型产生影响。

c. 支持向量机的学习问题是一个凸优化问题，可以发现目标函数的全局最优解

d. 支持向量机适合于中小量样本规模的数据

缺点

a. 对大规模数据难以实施，这是因为支持向量机使用的是二次规划来求解支持向量，这将涉及到m(样本个数)阶矩阵的计算，使得大量的内存被消耗及运算时间更长

b. 解决多分类问题比较困难

c. 对参数和核函数的选择比较敏感

d. 对缺失数据敏感

5. 优化支持向量机

a. 对于大规模数据的分类问题，建议使用朴素贝叶斯或逻辑回归

b. 解决多分类问题，可以使用一对剩余(OVR)组合模型或一对一(OVO)组合模型

参考：理解 OVR 与 OVO

参考资料：CSDN1 CSDN2

【转载】pluskid的SVM系列博文
基本篇：支持向量机: Maximum Margin Classifier —— 支持向量机简介。支持向量机: Su...
【机器学习实战】第6章支持向量机（Support Vector
第6章支持向量机支持向量机概述支持向量机(Support Vector Machines, SVM)：是一...
SVM支持向量机
线性支持向量机# 径向支持向量机# 最优参数##
编程作业（六）
支持向量机支持向量机本部分练习，我们将在2D示例数据集上使用支持向量机。通过在这些数据集上使用支持向量机，将帮...
支持向量机-QA
Q1：SVM的类型有哪些？三类：线性可分支持向量机、线性支持向量机、非线性支持向量机线性可分支持向量机：当训练数...
支持向量机
支持向量机线性可分支持向量机与硬间隔最大化线性支持向量机与软间隔最大化非线性支持向量机与核函数序列最小最优...
机器学习——libSVM（一）
一、什么是支持向量机支持向量机（Support Vector Machine,SVM）也称为支持向量网络。是一类...
支持向量机&&聚类
支持向量机SVM（Support Vector Machine）一、支持向量机的原理 Support Vecto...
支持向量机
问题 1. 支持向量机是如何进行数据分类？ 2. 支持向量机求解过程 3. 支持向量机是怎么对线性不...
【9%】100小时机器学习——支持向量机SVM
支持向量机

支持向量机

问题

1. 支持向量机是如何进行数据分类

2. 支持向量机求解过程

3. 支持向量机对线性不可分数据以及非线性可分数据分类

4. 支持向量机的优缺点

5. 优化支持向量机

相关文章

【转载】pluskid的SVM系列博文

【机器学习实战】第6章支持向量机（Support Vector

SVM支持向量机

编程作业（六）