支持向量机(SVM)

一.支持向量机

支持向量机模型用于二分类问题，一般分为3种：
线性可分支持向量机：用于数据线性可分的情况
线性支持向量机：用于数据总体线性可分，但是有个别点例外
非线性支持向量机：用于数据线性不可分的情况

二.线性可分支持向量机

1.线性可分支持向量机

对于线性可分的数据二分类就是要找一个合适的分离超平面将不同类别的数据分成两部分，使不同类别的数据处于超平面的两侧。然而能对数据进行二分类的超平面一般有无数个，如下图：图中红色点和蓝色点代表两种不同类型的数据， $l_{1},l_{2},l_{3}...$ 等直线（超平面）都能对其进行有效的划分

$\"这里写图片描述\"$

那么如何能找到一条最优的最合适的超平面，使其不仅能很好的对已知的数据（训练集）进行分类，对未知的数据（测试集）也能准确的分类？

为了解决这个问题我们引出函数间隔和几何间隔的概念：
已知数据集 $T=\\{(x_{1},y{1}),(x_{2},y_{2}),...,(x_{i},y_{i}),...,(x_{n},y_{n})\\}$ ,和超平面 $wx+b=0$
函数间隔：样本点 $(x_{i},y_{i})$ 与超平面 $(w,b)$ 的函数间隔为 $\\overline{l}_{i}=y_{i}(w\\cdot x+b)$
数据集T与超平面 $(w,b)$ 的函数间隔为 $\\overline{l}=min(\\overline{l}_{i})$ , $i=1,2,...,n$
几何间隔：样本点 $(x_{i},y_{i})$ 与超平面 $(w,b)$ 的几何间隔为 $l_{i}=y_{i}(\\frac{w}{||w||}\\cdot x+\\frac{b}{||w||})$
数据集T与超平面 $(w,b)$ 的函数间隔为 $l=min(l_{i})$ , $i=1,2,...,n$
几何距离是对超平面法向量 $w$ 做了约束规范化， $l=\\frac{\\overline{l}}{||W||}$
其实点到超平面的几何距离就是在坐标系中点到超平面的带符号实际距离，若点被分类正确就等于点到超平面的距离，数据集到超平面的几何距离就是离超平面距离最近的点到超平面的距离。

线性可分支持向量机认为能够正确划分训练数据集且到数据集几何间隔最大的分离超平面是最好的，所以线性可分支持向量机学习的基本思想就是：求解能够正确划分数据集且与数据集几何间隔最大的分离超平面,加上几何间隔最大（数据集上距离超平面最近的点与超平面的距离最大）这个条件，超平面就唯一确定了。

下面给出线性可分支持向量机的推导，假设分离超平面为 $wx+b=0$ ：
$\\max \\limits_{w,b}$ $l$
$s.t.$     $y_{i}(\\frac{w}{||w||}\\cdot x_{i}+\\frac{b}{||w||})\\ge l$ ,   $i=1,2,...,n$
$\\Downarrow$
$\\max \\limits_{w,b}$ $\\frac{\\overline l}{||w||}$
$s.t.$     $y_{i}(wx_{i}+b)\\ge\\overline l$ ,   $i=1,2,...,n$
$\\Downarrow$
$\\max \\limits_{w,b}$ $\\frac{1}{||w||}$
$s.t.$     $y_{i}(wx_{i}+b)\\ge 1$