机器学习-支持向量机（SVM）-09-灵析社区

一、SVM简介

支持向量机（support vector machines, SVM）是一种二分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机；

SVM还包括核技巧，这使它成为实质上的非线性分类器。SVM的的学习策略就是间隔最大化，可形式化为一个求解凸二次规划的问题，也等价于正则化的合页损失函数的最小化问题。

SVM的的学习算法就是求解凸二次规划的最优化算法。

支持向量机学习方法，针对不同的情况，有由简至繁的不同模型：

线性可分支持向量机（linear support vector machine in linearly separable case）：训练数据线性可分的情况下，通过硬间隔最大化（hard margin maximization），学习一个线性的分类器，即线性可分支持向量机（亦称作硬间隔支持向量机）。
线性支持向量机（linear support vector machine）：训练数据近似线性可分的情况下，通过软间隔最大化（soft margin maximization），学习一个线性的分类器，称作线性支持向量机（又叫软间隔支持向量机）。
非线性支持向量机（non-linear support vector machine）：训练数据线性不可分的情况下，通过使用核技巧（kernel trick）及软间隔最大化，学习非线性分类器，称作非线性支持向量机。

支持向量机可以借助核技巧完成复杂场景下的非线性分类，当输入空间为欧式空间或离散集合、特征空间为希尔贝特空间时，核函数（kernel function）表示将输入从输入空间映射到特征空间得到的特征向量之间的内积

二、SVM的优化目标

2.1、线性可分 SVM 与硬间隔最大化

SVM 模型它不仅仅希望把两类样本点区分开，还希望找到鲁棒性最高、稳定性最好的决策边界（对应图中的黑色直线）

当向量 x 为二维向量时， f(x) 表示二维空间中的一条直线。
当向量 x 为三维向量时，f(x) 表示三维空间中的一个平面。
当向量x 的 n维向量（ fn>3）时，f(x) 表示 n 维空间中的 n-1 维超平面。
当有一个新的点 x 需要预测属于哪个分类的时候，我们用 sign(f(x)) 就可以预测了。 sign表示符号函数：

公式：

根据svm的设定，当样本点分类正确的时候，有：
y(xi)>0,yi=+1
y(xi)<0,yi=−1
根据上面两个公式可以推出： y·y(xi)>0

回到重点，我们怎样才能取得一个最优的划分直线 f(x)呢？下图的直线表示几条可能的f(x)：

我们希望这条直线满足「最大间隔」原则，也就是如下图的形态。图中位于红色和蓝色线上的图标就是所谓的支持向量（support vector）：

决策边界就是f(x)，红色和蓝色的线是支持向量（support vector）所在的面，红色、蓝色线之间的间隙就是我们要最大化的分类间的间隙M（Margin Width）

2.2、几何间隔（重要）

① 根据以上定义， SVM 模型的「求解最大分割超平面问题」可以表示为以下约束最优化问题：

上面公式中 s.t 是 subject to 的缩写，也就是限制条件的意思。

2.3、对偶算法

求解线性可分支持向量机的最优化问题，我们很多时候会将它转化为对偶问题（dual problem）来求解，也就是应用「拉格朗日对偶性」，通过求解「对偶问题（dual problem）」得到「原始问题（primal problem）」的最优解，即线性可分支持向量机的对偶算法（dual algorithm）。

这样做有一些优点：

对偶问题往往更容易求解。
引入自然核函数，进而可以推广到非线性分类问题。

① 我们首先构建拉格朗日函数（Lagrange function）。为此，对每一个不等式约束引进拉格朗日乘子（Lagrange multiplier）

也就是说，这里的决策函数只依赖于输入�x 和训练样本输入的内积。上式亦称作线性可分 SVM 的对偶形式。

2.4、线性 SVM 与软间隔最大化

我们前面提到的是线性可分的情况，但实际应用中完全线性可分的情况太少见了。如下图就是一个典型的线性不可分的分类图（我们没有办法找到一条直线，把空间划分为 2个区域，一个区域只有黑点，一个区域只有白点）。

要对其进行切分，有2种方案：

方案1：用曲线去将其完全分开，即非线性的决策边界，这会和之后谈到的核函数关联。

方案2：还是使用直线，不过不追求完全可分，会适当包容一些分错的情况，在这个过程中我们会在模型中加入惩罚函数，尽量让分错的点不要太多太离谱。对分错点的惩罚函数就是这个点到其正确位置的距离

图上黄色、蓝色的直线分别为支持向量所在的边界，黑色的线为决策函数，那些绿色的线表示分错的点到其相应的决策面的距离，这样我们可以在原函数上面加上一个惩罚函数，并且带上其限制条件为：

当C很大的时候，分错的点就会更少，但是过拟合的情况可能会比较严重。
当C很小的时候，分错的点可能会很多，不过可能由此得到的模型也会不太正确。

实际我们也会调整和选择合适的 C值。

经过这个变换之后，我们可以同样求解一个拉格朗日对偶问题，得到原问题的对偶问题的表达式：

在线性不可分情况下得到的对偶问题，不同的地方就是α的范围从 [0,+∞)[0,+∞)，变为了[0,C)，增加的惩罚ξ 没有为对偶问题增加太多复杂度。

2.5、非线性 SVM 与核函数

如果我们要处理的分类问题更加复杂，甚至不能像上面一样近似线性可分呢，这种情况下找到的超平面分错的程度太高不太可接受。

对于这样的问题，一种解决方案是将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分，然后再运用 SVM 求解，如下图所示：

上述两个核函数分别为多项式核和高斯核，高斯核甚至是将原始空间映射为无穷维空间,比较常用的核函数就是高斯核函数

3. SVM 总结

3.1、模型总结

支持向量机（Support vector machines, SVM）是一种二分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器，他的学习策略就是间隔最大化，同时该方法可以形式化为一个求解图二次规划。

SVM由简至繁可分为三类：线性可分支持向量机、硬间隔（hard-margin svm）；线性支持向量机、软间隔（soft-margin svm）；非线性支持向量机、Kernel SVM。

SVM中存在三宝：间隔、对偶、核技巧

3.2、模型优缺点

（1）SVM模型优点

SVM 是一个凸优化问题，求得的解一定是全局最优而不仅仅是局部最优。
不仅适用于线性问题，还适用于非线性问题（借助核技巧）。
模型鲁棒性好，决策边界只取决于支持向量而不是全部数据集。
中小样本量数据集上效果优异。
无需依赖整个数据。
泛化能力比较强。

（2）SVM模型缺点

二次规划问题求解将涉及n阶矩阵的计算（其中n为样本的个数），计算量随样本量上涨厉害，因此 SVM 不适用于超大数据集。
原始 SVM 仅适用于二分类问题。（当然， SVM 的推广SVR也适用于回归问题；我们也可以通过one-vs-one，one-vs-rest等思路组合 SVM 来解决多分类问题）。
对非线性问题没有通用解决方案，有时候很难找到一个合适的核函数。
对于核函数的高维映射解释力不强，尤其是径向基函数。
SVM 对缺失数据敏感。

4、代码演示-SVM

sklearn
data iris

import numpy as np
import matplotlib.pyplot as plt
from sklearn import svm, datasets
iris = datasets.load_iris()
X = iris.data[:, :2]  #只取前两维特征，方便可视化
y = iris.target
# 线性可分
svc = svm.SVC(kernel='linear', C=1).fit(X, y)
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
h = (x_max / x_min) / 100
xx, yy = np.meshgrid(np.arange(x_min, x_max, h), np.arange(y_min, y_max, h))
plt.subplot(1, 1, 1)
Z = svc.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)
plt.contourf(xx, yy, Z, cmap=plt.cm.Paired, alpha=0.8)
plt.scatter(X[:, 0], X[:, 1], c=y, cmap=plt.cm.Paired)
plt.xlabel('Sepal length')
plt.ylabel('Sepal width')
plt.xlim(xx.min(), xx.max())
plt.title('SVC with linear kernel')
plt.show()

#使用多项式核函数
#svc = svm.SVC(kernel='poly', degree=3).fit(X, y)

#使用rbf核函数（高斯核函数）
# svc = svm.SVC(kernel='rbf', C=1).fit(X, y)
PythonCopy

import numpy as np
import matplotlib.pyplot as plt
from sklearn import svm, datasets
iris = datasets.load_iris()
X = iris.data[:, :2]  #只取前两维特征，方便可视化
y = iris.target
#
#svc = svm.SVC(kernel='linear', C=1).fit(X, y)
#使用多项式核函数
svc = svm.SVC(kernel='poly', degree=3).fit(X, y)
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
h = (x_max / x_min) / 100
xx, yy = np.meshgrid(np.arange(x_min, x_max, h), np.arange(y_min, y_max, h))
plt.subplot(1, 1, 1)
Z = svc.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)
plt.contourf(xx, yy, Z, cmap=plt.cm.Paired, alpha=0.8)
plt.scatter(X[:, 0], X[:, 1], c=y, cmap=plt.cm.Paired)
plt.xlabel('Sepal length')
plt.ylabel('Sepal width')
plt.xlim(xx.min(), xx.max())
plt.title('SVC with poly kernel')
plt.show()

#使用多项式核函数
#svc = svm.SVC(kernel='poly', degree=3).fit(X, y)

#使用rbf核函数（高斯核函数）
# svc = svm.SVC(kernel='rbf', C=1).fit(X, y)
PythonCopy

import numpy as np
import matplotlib.pyplot as plt
from sklearn import svm, datasets
iris = datasets.load_iris()
X = iris.data[:, :2]  #只取前两维特征，方便可视化
y = iris.target
#
#svc = svm.SVC(kernel='linear', C=1).fit(X, y)
#使用rbf核函数（高斯核函数）
svc = svm.SVC(kernel='rbf', C=1).fit(X, y)
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
h = (x_max / x_min) / 100
xx, yy = np.meshgrid(np.arange(x_min, x_max, h), np.arange(y_min, y_max, h))
plt.subplot(1, 1, 1)
Z = svc.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)
plt.contourf(xx, yy, Z, cmap=plt.cm.Paired, alpha=0.8)
plt.scatter(X[:, 0], X[:, 1], c=y, cmap=plt.cm.Paired)
plt.xlabel('Sepal length')
plt.ylabel('Sepal width')
plt.xlim(xx.min(), xx.max())
plt.title('SVC with rbf kernel')
plt.show()

#使用多项式核函数
#svc = svm.SVC(kernel='poly', degree=3).fit(X, y)

#使用rbf核函数（高斯核函数）
# svc = svm.SVC(kernel='rbf', C=1).fit(X, y)
PythonCopy





gamma 值越大，SVM 就会倾向于越准确的划分每一个训练集里的数据，这会导致泛化误差较大和过拟合问题。


C：错误项的惩罚参数 C。它还控制平滑决策边界和正确分类训练点之间的权衡。