分类——支持向量机分类

上篇博客讲到感知机是支持向量机(SVM)的基础。支持向量机同样采用分离超平面(或超曲面)来分离正负样本，故支持向量机是二分类分类器。支持向量机是一个非常广泛的领域，不是一两篇博客就能说清楚的，本文简单说下支持向量机的分类原理。支持向量机按简单到复杂分为线性可分支持向量机、线性支持向量机以及非线性支持向量机。

核心思想

找到分离超平面(超曲面)，使得距离超平面最近的点到超平面距离最大。

与感知机的区别

两者同样是采用训练数据集训练模型，获取分离超平面。但感知机仅仅是分离而已，至于分离效果好不好无法保证，因此存在多个分离超平面来分离正负实例，而当样本无法线性分离时，该分离超平面不存在。
支持向量机不仅仅能分离，而且能使分离效果最好，那么分离效果最好如何衡量呢？即距离分离超平面最近的点到分离超平面距离最大。

线性可分支持向量机

同感知机模型，线性可分支持向量机只能处理线性可分的数据集，是最基础的支持向量机。

模型

基本概念

函数间隔：γi^=yi(wxi+b)$\widehat{{\gamma }_i}=y_i(w{x}_i+b)$
几何间隔：γi=yi||w||(wxi+b)${\gamma }_i=\frac{y_i}{||w||}(w{x}_i+b)$
支持向量：与分离超平面距离最近的两个样本点(一正一负)
间隔边界：两个支持向量所在的平行的两个超平面
分离超平面：平行且位于两个间隔边界*的超平面
线性可分支持向量机的模型就是基于分离超平面的决策函数f(x)=sign(wx+b)$f(x)=sign(wx+b)$。

策略

找到分离超平面是一个含有不等式约束的最优化问题：

maxγ^||w||s.t.yi(wxi+b)⩾γ^$$\begin{gathered} max\frac{\hat{\gamma }}{||w||} \\ s.t.y_i(w{x}_i+b)⩾\hat{\gamma } \end{gathered}$$

γ^$\hat{\gamma }$的取值不影响最优化问题，取做1即可(这里可以这么理解：优化的目的就是为了找到最合适的w和b，γ^$\hat{\gamma }$相当于是类标记y$y$的缩放因子，而y$y$仅仅是一个类的标记值，不影响w,b)。转化为最小化问题如下：

min12||w||2s.t.yi(wxi+b)−1⩾0$$\begin{gathered} min\frac{1}{2}{||w||}^2 \\ s.t.y_i(w{x}_i+b)-1⩾0 \end{gathered}$$

求解上面的凸二次最优化问题，通常采用拉格朗日乘子法：

L(w,b,α)=12||w||2−∑i=1Nαiyi(wxi+b)+∑i=1Nαi$$L(w,b,\alpha )=\frac{1}{2}||w|{|}^2-\sum _{i=1}^N{\alpha }_i{y}_i(w{x}_i+b)+\sum _{i=1}^N{\alpha }_i$$

这个问题仍然不容易直接求解，故应用拉格朗日对偶性，求解其对偶问题：

min12∑i=1N∑j=1Nαiαjyiyj(xi⋅xj)−∑i=1Nαis.t.∑i=1Nαiyi=0s.t.αi⩾0,i=0,1,2,⋅⋅⋅,N$$\begin{gathered} min\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i·x_j)-\sum _{i=1}^N{\alpha }_i \\ s.t.\sum _{i=1}^N{\alpha }_i{y}_i=0 \\ s.t.{\alpha }_i⩾0,i=0,1,2,···,N \end{gathered}$$

可以将其视为损失函数，故模型的策略即损失函数最小的模型就是最优模型。而损失函数最小时，应当满足KKT条件(参考李航《统计学习方法》)，最终w和b的计算如下：

w=∑i=1Nαiyixib=yj−∑i=1Nαiyi(xi⋅xj)$$\begin{gathered} w=\sum _{i=1}^N{\alpha }_i{y}_i{x}_i \\ b=y_j-\sum _{i=1}^N{\alpha }_i{y}_i(x_i·x_j) \end{gathered}$$

可见仅当α>0$\alpha >0$的样本点对最终的结果有影响，称之为支持向量，线性可分支持向量机的支持向量就是分离超平面两侧最近的样本点。其他样本点距离分离超平面比较远，分类正确确信度十分高。

学习

求解上面的拉格朗日对偶问题的方法有很多，最常用的是序列最小最优化(SMO)算法，后面的博客会讲到。

线性支持向量机

线性支持向量机是考虑到数据集是线性不可分的，也就是说找不到分离超平面将正负实例完全分离开。这反映到上面的最优化问题上就是某些样本点不满足条件 yi(wxi+b)−1⩾0$y_i(w{x}_i+b)-1⩾0$。解决方法就是引入软间隔，即允许样本点跨越间隔边界。反映到约束条件上就是：

yi(wxi+b)⩾1−ξi$$y_i(w{x}_i+b)⩾1-{\xi }_i$$

ξi${\xi }_i$就是该样本点为了跨越间隔边界而支付的代价，称为松弛因子。当然，绝大多数的样本代价是0。为了保证模型的准确率，引入惩罚因子C,即C越大，惩罚越大，即允许跨越间隔边界的样本点越少。优化问题变为：

min12||w||2+C∑i=1Nξi$$min\frac{1}{2}{||w||}^2+C\sum _{i=1}^N{\xi }_i$$

同样采用拉格朗日乘子法，并求其对偶问题，令人惊奇的是ξ$\xi$被消除了(反映了支持向量机在已知惩罚力度情况下，会自动分配松弛因子)，约束条件没有变，仅仅是约束条件2变成

s.t.0⩽αi⩽Ci=0,1,2,⋅⋅⋅,N$$s.t.0⩽{\alpha }_i⩽Ci=0,1,2,···,N$$

线性支持向量机w、b的计算和线性可分支持向量机的计算基本一致。唯一的区别是选取不同的支持向量，b的计算结果不一致，通常取所有支持向量计算结果的平均值。
线性支持向量机的支持向量没有线性可分情况下好理解，可以将支持向量分为间隔边界上的支持向量、间隔边界与分离超平面间的支持向量、分离超平面上的支持向量和误分一侧的支持向量。KKT条件中有如下两个条件

μiξi=0C−αi−μi=0$$\begin{gathered} {\mu }_i{\xi }_i=0 \\ C-{\alpha }_i-{\mu }_i=0 \end{gathered}$$

函数样本点到间隔边界的距离为ξi||w||$\frac{{\xi }_i}{||w||}$，则可得出以下结论：
1.当0<α<C$0<\alpha <C$时，μi${\mu }_i$不等于0，那么ξi${\xi }_i$一定等于0，即该支持向量位于间隔边界上。
2.当α=C$\alpha =C$时，是分离比较糟糕的样本，支持向量不在正确一侧的间隔边界上。此时当ξi<1${\xi }_i<1$，支持向量位于间隔边界与分离超平面间；当ξi=1${\xi }_i=1$，支持向量位于分离超平面上；当ξi>1${\xi }_i>1$支持向量位于误分一侧。

非线性支持向量机

由于实际生活中绝大多数数据是不能简单地用超平面分离的，这时考虑建立超曲面。即首先将数据从当前空间非线性映射到另一个高维空间，在映射后的空间中，数据是能用超平面分离的，那么在这个空间中建立超平面方程后，再非线性变换回去即可(类似于拉普拉斯变换解决问题的思路)。但是这种方法，存在明显的缺点，首先映射函数的选择很困难，无法保证映射后是能用超平面分离的，其次计算量巨大。这就需要用到核技巧。
核技巧说白了就是偷个懒，无论在当前空间还是映射空间，我们都仅需要求解两个样本的内积，那么直接将变换来变换去的两个非线性变换的过程省略即可，即隐式地变换。具体实现就要引入核函数。例如核函数K(xi,xj)=(xi⋅xj)2$K(x_i,x_j)=(x_i·x_j{)}^2$，xi和yi$x_i和y_i$在映射后空间的内积就是(xi⋅xj)2$(x_i·x_j{)}^2$，至于隐藏在其中的非线性变换有很多种，具体是啥？权当是黑箱。
问题简单了，只需要将线性支持向量机优化问题中的内积xi⋅xj$x_i·x_j$改成K(xi,xj)$K(x_i,x_j)$就可以了！

ν$\nu$ -支持向量机

上文讲到的支持向量机分类中涉及惩罚因子C，因此称为C-支持向量机，ν$\nu$-支持向量机是在C-支持向量机基础上添加了另外一个参数ν$\nu$来调节模型。ν$\nu$的含义就是训练错误样本占比上限，也即支持向量个数占比下限。由于ν$\nu$有明确的含义，调节起来比较方便。优化问题如下：可以看出，ν$\nu$-支持向量机是在C-支持向量机的基础上添加了一个参数ρ$\rho$来调节支持向量的个数而已。默认的惩罚因子是1l$\frac{1}{l}$，是可以另外设置的。（由于支持向量机是尺度可变的，故C的尺度依赖于输入数据的尺度，一般情况下可以将输入X的每个维度都归一化处理，sklearn和LIBSVM等支持向量包中C默认是1.0
我的GitHub
注：如有不当之处，请指正。