支持向量机-SVM

概念

将训练数据集非线性的映射到一个高维特征空间，这个非线性映射的目的是把输入空间中线性不可分数据集映射到高维特征空间后，变成线性可分的数据集，随后在特征空间建立一个具有最大间隔距离的最优分离超平面，这也相当于在输入空间产生一个最优非线性决策边界；

问题定义:找到最大化的平面间隔

举例

以2维平面为例，若需要找到一条直线y=wx+b，将物品很好的分为两个不同的类别，如下图：

即需要找到平面上不同类别的点距离y=wx+b都能很好的被分割在平面的两边；

让wx+b=0，则可以得到如下图：

那么平面上的点到wx+b的距离，可以表示为|WX+B|，并且，我们可以知道，当wx+b>0时，可以将有判定为1的类别，否则可以判定为-1的类别；

定义

几何间隔

以二维空间为例，几个间隔定义为点(xi,yi)到直线ax+by+c=0的距离：

                                                                      

 

函数间隔

几何间隔就是函数间隔除以||w||，而且函数间隔y*(wx+b) = y*f(x)实际上就是|f(x)|，而几何间隔|f(x)|/||w||才是直观上的点到超平面的距离。

说明

单个样本的几何间隔为：

将上式转换为带约束条件的式子，约束条件为函数间隔大于或等于1：

为了更好的解决问题，将上式转换为二次凸函数优化问题：

然后将上式带有约束条件的式子，使用拉格朗日乘子法进行转换，得下式：

然后分别对w和b求偏导，得：

代入原式，得：

 

上式中xixj可使用核函数进行代替；

由于单纯的xixj变换，会导致输入空间到特征空间的维度发生爆炸式的增长，所以将该转换方式变换为使用核函数进行代替，在低维上进行计算，实质结果表现在高维上；常见的核函数有LR、线性核、高斯核（RBF）或者sigmoid核；主要区别：

在特征数量大到和样本数量差不多时，选择LR或者线性核；

当特征数量小，样本量正常时，选择高斯核；

当特征数量小，样本两大时，可先手工添加一些特征转变为第一种情况；

 

上述式子求解完成后，SVM的问题并没有解决完，还需要解决拉格朗日乘子的问题，求解拉格朗日乘子可使用SMO（最小序列优化）方法进行求解，该方法是基于一种类似动态规划的启发式算法，简单的归纳为每次以两个乘子作为求解的变量，其他的乘子固定，依次动态求解；