一、支持向量机介绍

支持向量机是一种分类方法，它适用于二分类，但是实际使用时可以通过多个支持向量机的组合实现多分类。

在下图中的二分类问题中，我们可以看到，有效划分两个类别的分解线（二维为分界面，多维为超平面）有很多，我们需要评估哪一种分界线的效果更好。

1.1 最大间隔

衡量分界线（超平面）的有效性，需要同时衡量分界线（超平面）距离分类样本的距离，即被划分不同种类样本之间的间隔，间隔越大效果越好。

线性代数知识是处理大量数据的有效工具，在线性代数思想中数据分布在多维空间中，空间中的每个样本有且只有一个坐标与之相对应，由此，我们可以将支持样本空间中的每个样本点用向量表示，这也是支持向量机中向量的由来。

在二分类问题划分界限时，只有a、b、c、d、e决定着最有分界线（超平面），所以被称之为支持向量，由此得到的二分类器被称作为支持向量机。

综上所述，支持向量机通俗来讲就是针对二分类问题给定可分类样本，寻找最优分界线（超平面）的算法，而这个最优分界面应该是间隔最大化的。

训练集T：

T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}

其中，样本 $x_i=(x_{i}^{1},x_{i}^{2},...,x_{i}^{n})$ 是n维的向量，表示一个样本由n个特征组成，整个数据集中含有N个样本；标记 $y_i{\in}(-1,+1)$ 表示二分类，只有两种结果。

最优分界面（超平面方程）：

w^*·x+b^*=0

其中， $w^\*,x$ 是向量， $b^\*$ 是标量，加 $\*$ 表示最优。 $w^\*=(w_{1}^{\*},w_{2}^{\*},...,w_{n}^{\*},)$ , $x=(x^{(1)},x^{(2)},...,x^{(n)})$

决策函数：

f(x)=sign(w^*·x+b^*)

f(x)=\begin{cases} +1 & 正类 \\ -1 & 负类 \\ \end{cases}

样本到超平面(w,b)的函数间隔：

函数间隔 $\gamma^-(x_i)$ 定义为：

\gamma^-(x_i)=y_i·(w·x_i+b)

其中 $y_i\in(-1, +1)$ ，则 $M(x_{i})\geq0$ 。

函数间隔的特点：同一个超平面可以对应不同的函数间隔（乘以常数C）。

几何间隔：

几何间隔实际上就是点到平面的欧氏距离

归一化的函数间隔：

\gamma(x_i)=y_i·(\frac{w}{||w||}·x_i+\frac{b}{||w||})

其中 $||w||$ 表示 $w$ 范数：

||w||=\sqrt{w_{1}^{2}+w_{2}^{2}+...+w_{n}^{2}}

归一化的函数间隔不会再因为同一个超平面（乘以常数C）再变得可大可小。

几何间隔和函数间隔的关系：

\gamma^{-}(x_i)=\frac{\gamma(x_i)}{||w||}

训练集T到超平面(w,b)的函数间隔：

\gamma=min_{i}(\gamma^-(x_i))

训练集T到超平面(w,b)的几何间隔：

\gamma=min_{i}(\gamma(x_i))