教程目录
阅读:
支持向量机(SVM)算法详解
与感知机算法不同,在支持向量机(Support Vector Machines,SVM)中,求解出的分隔超平面不仅能够正确划分训练数据集,而且几何间隔最大。

同时,对于每一个样本,需要满足:

考虑到几何间隔和函数间隔之间的关系,则上述的几何间隔最大的分隔超平面可以等价为:

同时需要满足:

在函数间隔中,函数间隔的取值并不影响到最优问题的解,如上所述,当参数 W 和 b 同时扩大为原来的 2 倍,函数间隔也会同时扩大为原来的 2 倍,这对于上述的优化问题和约束条件并没有影响,因此,可以取值为 1,则上述的优化问题变成:

图 1
对于如图 1 所示的线性可分的二分类问题,在 m 个训练样本中,与分隔超平面距离最近的样本称为支持向量(Support Vector)。支持向量 X(i) 对应着约束条件为:
当 y(i)=+1 时,支持向量所在的超平面为:
当 y(i)=-1 时,支持向量所在的超平面为:
对于支持向量所在的超平面 H1 和 H2 ,如图 2 所示。

图 2 支持向量以及支持向量所在的超平面
在图 2 中,超平面 H1 和超平面 H2 之间的距离成为间隔,超平面 H1 和超平面 H2 又称为间隔边界。在确定最终的分隔超平面时,只有支持向量起作用,其他的样本点并不起作用,由于支持向量在确定分割超平面中起着重要的作用,因此,这种分类模型被称为支持向量机。
对于线性不可分的某些样本点 (X(i),y(i)) 意味着其不能满足函数间隔大于或等于 1 的约束条件,为了解决这个问题,可以对每个样本点 (X(i),y(i)) 引进一个松弛变量 ξi≥0,使得函数间隔加上松弛变量大于或等于 1,这样,约束条件变为:
同时,对每个松弛变量 ξi,支付一个代价 C,此时,目标函数变为:
此时的优化目标为:
间隔最大化
对于几何间隔最大的分隔超平面:




支持向量和间隔边界

图 1

当 y(i)=+1 时,支持向量所在的超平面为:

当 y(i)=-1 时,支持向量所在的超平面为:

对于支持向量所在的超平面 H1 和 H2 ,如图 2 所示。

图 2 支持向量以及支持向量所在的超平面
在图 2 中,超平面 H1 和超平面 H2 之间的距离成为间隔,超平面 H1 和超平面 H2 又称为间隔边界。在确定最终的分隔超平面时,只有支持向量起作用,其他的样本点并不起作用,由于支持向量在确定分割超平面中起着重要的作用,因此,这种分类模型被称为支持向量机。
线性支持向量机
对于如图 1 所示的数据集,其条件极为苛刻,要求所有的样本都是线性可分的,即存在分隔超平面,能够将所有的正样本和负样本正确区分开,但是在实际情况中,数据集很难满足这样的条件,对于一个数据集,其中存在部分的特异点,但是将这些特异点除去后,剩下的大部分的样本点组成的集合是线性可分的。对于线性不可分的某些样本点 (X(i),y(i)) 意味着其不能满足函数间隔大于或等于 1 的约束条件,为了解决这个问题,可以对每个样本点 (X(i),y(i)) 引进一个松弛变量 ξi≥0,使得函数间隔加上松弛变量大于或等于 1,这样,约束条件变为:

同时,对每个松弛变量 ξi,支付一个代价 C,此时,目标函数变为:

此时的优化目标为:
