SVM算法补充(一): 核函数

1.名词

分割超平面
支持向量：离分割超平面最近的点
间距:支持向量到分割超平面的距离的两倍

原理：找到一个分割超平面。将数据正确分类，并且间距最大。

2.计算间距

在二维空间既是点到直线的距离
在高维空间中，使用直线方程：距离相应的表示为：

由于支持向量在直线 W^Tx+b=-1和W^Tx+b=1 上，所以带入可得

为了使得距离最大，只需要找到合适的参数w和b,使得最大即可。 ||w|| 就是向量w的L2范数。使用分割超平面可以解决分类问题。求解SVM算法，就是在满足约束条件下求w的L2范数的最小值。

3.松弛系数

针对现行不可分的数据集，上面的方法就不能用了。解决这个问题的办法就是引入一个参数ϵ，称为松弛系数。然后把优化的目标函数变为,m是数据集的个数，R为算法参数，其约束条件变为:，可以把ε理解为样本x(i)违反一大间距规则的程度。针对大多数满足约束条件的样本ε=0。而对部分违反最大间距规则的样本ε>0。参数R则表示对违反约束的样本的”惩罚”。R越大对违反约束的点“惩罚力度”越大反之越小。这样模型就会倾向于允许部分点违反最大间距规则。可以纠正过拟合问题

核函数

核函数是特征转换函数。

（1）最基础的核函数

间距最大是我们的优化目标。真确地对数据分类是约束条件。即在满足约束条件y(i)(wTx(i)+b)≥1的前提下，求解||w||^2的最小值。
使用拉格朗日乘子法：

对w和b求骗到，用拉格朗日法解得:

对这个公式求解最小值，求出的ai大多数是0，因为只有支持向量所对应的样本才决定了间隙的大小，引入核函数：

L里的x(i)^Tx(j)部分，其中x(i)是一个特征向量，所以x(i)^Tx(j)是一个数值，就是两个输入特征向量的内积。预测函数为：预测函数中也包含x(i)^Tx(j),引入K(x^(i),x(j))=x(i)^Tx(j)作为核函数，白哦是两个向量的相似性，如向量垂直时，就表示两个向量线性无关，值为0，引入核函数后预测函数变为：

(2)相似性函数

对无法进行线性分割的样本集，可以使用一定的规则将样本映射到更高纬度的空间，然后找出超平面。核函数的引入就是为了实现这种映射，联想利用多项式解决线性回归欠拟合问题的方法。如果输入特征是一维的[x1]变量，我们把它变成二维的一个方法是把输入特征转化为[x1,2x1 ^2]，定义这种特征映射的函数就称之为相似性函数Φ(x)。这样在原来低维度计算相似性的运算x(i)^Tx(j)，就可以转换为高纬度空间里进行相似性运算Φ(x(i))^TΦ(x(i))。

(3)常用的核函数

一般有两种：多项式核函数和高斯核函数。

1.多项式核函数

2.高斯核函数

如果输入的特征是一维的标量，那么高斯核函数对应的形状就是一个反钟形的曲线，其参数σσ控制反钟形的宽度。由K(x(i),x(j))=Φ(x(i))TΦ(x(i))，经过合适的数学变换，可得高斯核函数对应的特征转换函数为：

前面无限多项的累加器，其物理意义就是把特征向量转换到无限多维向量空间里，即高斯函数可以吧输入特征扩展到无限多维空间里。公式的推导公式会用到泰勒公式。

其中K(x(i),x(j))是高斯核函数，ai只在支持向量对应的样本出不为0.由此可知，预测函数时中心点在支持向量机处的高斯函数的线性组合，其线性组合的系数为aiy(i)。因此，高斯核函数也称为RBF核函数，即反钟形函数的线性组合。

(4)核函数的对比(摘自网络)

1、线性核函数：这是最简单的核函数，它直接计算两个输入特征向量的内积。

优点：简单高效，结果易解释，总能生成一个最简洁的线性分割超平面
缺点：只适用线性可分的数据集

2、多项式核函数：通过多项式来作为特征映射函数

优点：可以拟合出复杂的分割超平面。
缺点：参数太多。有γ,c,nγ,c,n三个参数要选择，选择起来比较困难；另外多项式的阶数不宜太高否则会给模型求解带来困难。

3、高斯核函数：

优点：可以把特征映射到无限多维，并且没有多项式计算那么困难，参数也比较好选择。
缺点：不容易解释，计算速度比较慢，容易过拟合。

（5）核函数的选择

1、最一般的选择原则是针对数据量很大的时候，可以选择复杂一点的模型。虽然复杂模型容易过拟合，但由于数据量很大，可以有效弥补过拟合问题。如果数据集较小选择简单点的模型，否则很容易过拟合，此时特别要注意模型是否欠拟合，如果欠拟合可以增加多项式纠正欠拟合。

2、根据样本量mm和特征量nn进行选择：

特征相比样本较大（如m=10～1000，n=10000）：选逻辑回归或者线性函数SVM
特征较少，样本量中（如m=10～10000，n=1～1000）：选择高斯SVM
特征量少，样本多（如m=50000+，n=1~1000)：选多项式或高斯SVM