支持向量机SVM

作者:Irving_zhang

1、简介

理解SVM,咱们必须先弄清楚一个概念:线性分类器。

    给定一些数据点,它们分别属于两个不同的类,现在要找到一个线性分类器把这些数据分成两类。如果用x表示数据点,用y表示类别(y可以取1或者-1,分别代表两个不同的类),一个线性分类器的学习目标便是要在n维的数据空间中找到一个超平面(hyper plane),这个超平面的方程可以表示为( wT中的T代表转置):

                                                           

    可能有读者对类别取1-1有疑问,事实上,这个1-1的分类标准起源于logistic回归

    Logistic回归目的是从特征学习出一个0/1分类模型,而这个模型是将特性的线性组合作为自变量,由于自变量的取值范围是负无穷到正无穷。因此,使用logistic函数(或称作sigmoid函数)将自变量映射到(0,1)上,映射后的值被认为是属于y=1的概率。

    假设函数

    其中x是n维特征向量,函数g就是logistic函数。
    而的图像是


    可以看到,将无穷映射到了(0,1)。
    而假设函数就是特征属于y=1的概率。

    从而,当我们要判别一个新来的特征属于哪个类时,只需求即可,若大于0.5就是y=1的类,反之属于y=0类。

    此外,只和有关,>0,那么而g(z)只是用来映射,真实的类别决定权还是在于。再者,当时,=1,反之=0。如果我们只从出发,希望模型达到的目标就是让训练数据中y=1的特征,而是y=0的特征Logistic回归就是要学习得到,使得正例的特征远大于0,负例的特征远小于0而且要在全部训练实例上达到这个目标。

    接下来,尝试把logistic回归做个变形。首先,将使用的结果标签y = 0y = 1替换为y = -1,y = 1,然后将)中的替换为b,最后将后面的替换为(即)。如此,则有了。也就是说除了yy=0变为y=-1外,线性分类函数跟logistic回归的形式化表示没区别。

2、一个例子

下面举个简单的例子,如下图所示,现在有一个二维平面,平面上有两种不同的数据,分别用圈和叉表示。由于这些数据是线性可分的,所以可以用一条直线将这两类数据分开,这条直线就相当于一个超平面,超平面一边的数据点所对应的y全是 -1 ,另一边所对应的y全是1

    这个超平面可以用分类函数表示,当f(x) 等于0的时候,x便是位于超平面上的点,而f(x)大于0的点对应 y=1 的数据点,f(x)小于0的点对应y=-1的点,如下图所示:

    注:有的资料上定义特征到结果的输出函数与这里定义的实质是一样的。为什么?因为无论是,还是,不影响最终优化结果。下文你将看到,当我们转化到优化的时候,为了求解方便,会把yf(x)令为1,即yf(x)是y(w^x + b),还是y(w^x - b),对我们要优化的式子max1/||w||已无影响。

    (有一朋友飞狗来自Mare_Desiderii,看了上面的定义之后,问道:请教一下SVM functional margin 为=y(wTx+b)=yf(x)中的Y是只取1和-1 吗?y的唯一作用就是确保functional margin的非负性?真是这样的么?当然不是,详情请见本文评论下第43楼

    当然,有些时候,或者说大部分时候数据并不是线性可分的,这个时候满足这样条件的超平面就根本不存在(不过关于如何处理这样的问题我们后面会讲),这里先从最简单的情形开始推导,就假设数据都是线性可分的,亦即这样的超平面是存在的

    换言之,在进行分类的时候,遇到一个新的数据点x将x代入f(x) 中,如果f(x)小于0x类别赋为-1,如果f(x)大于0x的类别赋为1。

    接下来的问题是,如何确定这个超平面呢?从直观上而言,这个超平面应该是最适合分开两类数据的直线。而判定“最适合”的标准就是这条直线离直线两边的数据的间隔最大。所以,得寻找有着最大间隔的超平面。

3、最大间隔

对一个数据点进行分类,当超平面离数据点的“间隔”越大,分类的确信度(confidence)也越大。所以,为了使得分类的确信度尽量高,需要让所选择的超平面能够最大化这个“间隔”值。这个间隔就是下图中的Gap的一半

    通过由前面的分析可知:函数间隔不适合用来最大化间隔值,因为在超平面固定以后,可以等比例地缩放w的长度和b的值,这样可以使得的值任意大,亦即函数间隔可以在超平面保持不变的情况下被取得任意大。但几何间隔因为除上了,使得在缩放wb的时候几何间隔的值是不会改变的,它只随着超平面的变动而变动,因此,这是更加合适的一个间隔。那么,  换言之,这里要找的最大间隔分类超平面中的“间隔”指的是几何间隔。

   于是最大间隔分类器(maximum margin classifier)的目标函数可以定义为:

    同时需满足一些条件,根据间隔的定义,有

    其中,s.t.,即subject to的意思,它导出的是约束条件

    回顾下几何间隔的定义可知:如果令函数间隔等于1(之所以令等于1,是为了方便推导和优化,且这样做对目标函数的优化没有影响,至于为什么,请见本文评论下第42楼回复,则有 = 1 / ||w||且,从而上述目标函数转化成了

    这个目标函数便是在相应的约束条件下,最大化这个1/||w||,而1/||w||便是几何间隔。   

    如下图所示,中间的实线便是寻找到的最优超平面(Optimal Hyper Plane),其到两条虚线边界的距离相等,这个距离便是几何间隔,两条虚线间隔边界之间的距离等于2,而虚线间隔边界上的点则是支持向量。由于这些支持向量刚好在虚线间隔边界上,所以它们满足还记得我们把 functional margin 定为 1 了吗?上节中:处于方便推导和优化的目的,我们可以令=1),而对于所有不是支持向量的点,则显然有

    OK,到此为止,算是了解到了SVM的第一层,对于那些只关心怎么用SVM的朋友便已足够,不必再更进一层深究其更深的原理。

4、python实例

# -*- coding: utf-8 -*-
"""
Created on Wed Jul 13 16:31:19 2016

@author: irvingzhang
"""
import numpy as np
import pylab as pl
from sklearn import svm
#创建实例
np.random.seed(1)
X = np.r_[np.random.randn(20,2) - [2,2] ,np.random.randn(20,2) + [2,2]]
Y = [0] * 20 + [1] * 20
#分类器fit
clf = svm.SVC(kernel='linear')
clf.fit(X,Y)
#得到点和向量机的坐标
w = clf.coef_[0]
a = -w[0] / w[1]
xx = np.linspace(-5 , 5)
yy = a * xx - (clf.intercept_[0]) / w[1]
#画出经过支持向量机的超平面
b = clf.support_vectors_[0]
yy_down = a * xx + (b[1] - a * b[0])
b = clf.support_vectors_[-1]
yy_up = a * xx + (b[1] - a * b[0])

pl.plot(xx,yy,'k-')
pl.plot(xx,yy_down,'k--')
pl.plot(xx,yy_up,'k--')

pl.scatter(clf.support_vectors_[:,0],clf.support_vectors_[:,1],s=80,facecolors='none')
pl.scatter(X[:,0],X[:,1],c=Y,cmap=pl.cm.Paired)

pl.axis('tight')
pl.show()

结果展示:


发表评论

0个评论

我要留言×

技术领域:

我要留言×

留言成功,我们将在审核后加至投票列表中!

提示x

人工智能机器学习知识库已成功保存至我的图谱现在你可以用它来管理自己的知识内容了

删除图谱提示×

你保存在该图谱下的知识内容也会被删除,建议你先将内容移到其他图谱中。你确定要删除知识图谱及其内容吗?

删除节点提示×

无法删除该知识节点,因该节点下仍保存有相关知识内容!

删除节点提示×

你确定要删除该知识节点吗?