人工智能中文网
  • 主页
  • 线代考研视频
  • 线性代数
  • Python机器学习与算法
  • 大数据与机器学习
  • Python基础入门教程
  • 人工智能中文网
    教程目录
    阅读:

    支持向量机(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 又称为间隔边界。在确定最终的分隔超平面时,只有支持向量起作用,其他的样本点并不起作用,由于支持向量在确定分割超平面中起着重要的作用,因此,这种分类模型被称为支持向量机

    线性支持向量机

    对于如图 1 所示的数据集,其条件极为苛刻,要求所有的样本都是线性可分的,即存在分隔超平面,能够将所有的正样本和负样本正确区分开,但是在实际情况中,数据集很难满足这样的条件,对于一个数据集,其中存在部分的特异点,但是将这些特异点除去后,剩下的大部分的样本点组成的集合是线性可分的。

    对于线性不可分的某些样本点 (X(i),y(i)) 意味着其不能满足函数间隔大于或等于 1 的约束条件,为了解决这个问题,可以对每个样本点 (X(i),y(i)) 引进一个松弛变量 ξi≥0,使得函数间隔加上松弛变量大于或等于 1,这样,约束条件变为:


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


    此时的优化目标为:

    < 上一篇:函数间隔和几何间隔 下一篇:决策树算法 >