支持向量机(Suport Vector Machine)

1.线性可分支持向量机

如下图A给定训练数据集，两个类别分隔足够清晰，因此很容易在图中画一条直线将两组数据分隔开，这种情况下数据称为线性可分(linearly separable )数据 。

由于数据在二维平面上，所以分隔超平面是一条直线；如果数据集是三维的，则分隔超平面是二维的；以此类推，如果数据集是N维的，那么分隔超平面就是N-1维的。我们把分隔数据的N-1维对象称为超平面(hyperplane)。 分布在超平面一侧的属于某一类，分布在另一侧的属于另一个类别。对于任意线性可分数据集我们就像找到一个超平面来构建分类器对样本分类。

分类学习的基本思想是：基于训练集在样本空间找到一个超平面将不同类别的样本分隔开，但是能将训练样本分割开的超平面可能有很多，如下图所示有很多直线可以将两类样本分开，应该选择哪条直线最好？

从直观上看，位于两个样本正中间的超平面是最好的，即下图红色的那条直线，因为该直线对样本局部扰动的容忍性最好。比如由于训练样本集的局限性和噪声干扰，训练集以外的样本可能比训练集中的任何样本都更接近分隔超平面，如下图中的几个绿色的样本点使得许多超平面出现划分错误。也就是说红色的超平面分类结果是最鲁棒的，对新样本泛化能力强。

我们希望找到距离分隔超平面最近的点，确保它们离超平面的距离尽可能的远

距离超平面最近的几个训练样本点成称为支持向量(support vector)

假设给定训练样本集 D = { (x₁, y₁), (x₂, y₂), ... , (xm, ym) }, y₁∈{-1，+1}

划分样本集的超平面有如下线性方程描述：

任意样本点到超平面的距离r：

将样本分为两类，正类为+1，负类为-1。假设超平面能将样本正确的分类，对于任意样本(xi,yi)，如果样本在超平面的正方向(+1类)，wx+b>0;如果样本在处于超平面的负方向(即-1类)，wx+b<0。距离超平面的样本点(支持向量)是公式(3)的等号成立。

两个异类支持向量到超平面的距离之和为式(4),它被称为**“间隔(margin)”**。

如果想要找到具有最大间隔的超平面，就要找到满足式(3)中约束的参数w和b，是的间隔r最大，即式（5）

为了最大化间隔，只需要最大化||w||-¹，等价于最小化 ||w||²，如式(6)

对式(6)拉格朗日乘子法得到其“对偶问题”，该问题的拉格朗日函数可写为：

对w和b分别求偏导并使其等于0，得到下式：

将式(8)带入式(7)，消去w和b就得到式(6)的对偶问题：

解出w和b得到分类超平面的模型：

从式(9)中解出的αi是拉格朗日乘子，对应着训练样本(xi,yi),式(6)有不等式条件，上述过程满足KKT条件，即满足：

由上述条件分析得到，对于任意样本(xi,yi),若αi=0，则该样本不会出现在式(10)的求和中，则样本不会对f(x)有任何影响；若αi≠0，则y₁f(x₁)-1=0，所对应的的样本点是一个支持向量。这时支持向量机的一个重要的性质，训练得到模型后，大部分样本都不需要保留，最终模型仅和支持向量有关。支持向量这个名字强调了这个分类器是如何从支持向量中构建模型的，模型的复杂度只和支持向量的数目有关。