【机器学习】支持向量机SVM及实例应用

【机器学习】支持向量机

1.分类超平面与最大间隔

2.对偶问题与拉格朗日乘子法

3.核函数

4.软间隔与正则化

5.实例应用：python使用支持向量机SVM

    准备：    

        数据集

        导入SVM模块

    步骤：

        1.读取数据集

        2.划分训练样本与测试样本

        4.计算分类准确率

        5.绘制图像

       上图是一个关于机器学习算法的时间线来自于Eren Golge。可以看出SVM旺盛的生命力。实际上，即使是深度学习非常火热的今天，SVM依然盛行。在一些小样本分类问题上，SVM表现非常好，用深度学习模型可能反而会使问题变得更复杂。

    下面开始介绍SVM--支持向量机。

1.分类超平面与最大间隔

    给定训练样本集 D ={ (X1 ,Yl)，（X2，Y2)..., (Xm,Ym)}, Yi ∈{-1,+1}，分类学习最基本的想法就是基于训练集D在样本空间中找到一个划分超平面、将不同类别的样本分开。

    但能将训练样本分开的划分超平面可能有很多，如图 6.1所示，我们应该努力去找到哪一个昵?

                

     原则上，是去找位于两类训练样本"正中间"的划分超平面，即图 6.1中黑色最粗的那个，因为该划分超平面对训练样本局部扰动的"容忍性“最好，鲁棒性最强，泛化能力最强。

    例如，由于训练集的局限性或噪声的因素，训练集外的样本可能比图6.1中的训练样本更接近两个类的分隔界，这将使许多划分超平面出现错误，而黑色最粗的那个超平面受影响最小。换言之，这个划分超平面所产生的分类结果是最鲁棒的，对未见示例的泛化能力最强。

    在样本空间中，划分超平面可通过如下线性方程来描述:

            

    其中：

    x=(x1,x2…xd)为输入数据，维度为d。

    为法向量，决定了超平面的方向。

     b为位移项，决定了超平面与原点之间的距离。

    显然，分类超平面可被法向量ω和位移b确定，下面我们将其记为(w,b)。样本空间中任意点 x到超平面(w,b)的距离可写为：

            

    点到超平面的距离，可参考点到直线的距离公式，见附录【1】。

     假设超平面(w,b)能将训练样本正确分类，即对于，  

                

    所以，令：

         

    如图6.2所示，距离超平面最近的这几个训练样本点使式(6.3)的等号成立，它们被称为"支持向量"，两个异类支持向量到超平面的距离之和为：

            

    其中，γ被称为"间隔"。

 

    那如何找到具有“最大间隔”的分类超平面呢？

    欲找到具有"最大间隔" (maximum margin) 的划分超平面，也就是要找到能满足式(6.3)中约束的参数w和b，使得γ最大，即

    

    显然，为了最大化间隔γ，仅需最小化||w||。于是，式(6.5)可重写为：

    

    上述（6.6）是支持向量机的基本型。

    支持向量机有何特点？

    支持向量满足：

    最大化间隔真的仅与ω有关吗？

    NO！事实上，最大化间隔不只与ω有关，偏置b通过约束隐性地影响着w的取值，进而对间隔产生影响。

    为什么目标函数要写成（6.6）中的凸函数形式呢？

    在表示最大化间隔的优化问题中，发现式（6.5）中的目标函数是非凸的，并没有现成的可用的软件来解决非凸函数的优化问题。所以改成了（6.6）中的凸函数形式。

    关于凸函数，可见附录【2】。

 2.对偶问题与拉格朗日乘子法

    我们希望求解式(6.6)来得到最大间隔分类超平面所对应的模型f(x):

    

    其中ω和b是模型参数。注意到式(6.6)本身是一个凸二次规划问题，能直接用现成的优化计算包求解，但我们可以有更高效的办法。
    对式(6.6)使用拉格朗日乘子法可得到其"对偶问题" 。具体来说，对式(6.6)的每条约束添加拉格朗日乘子，则该问题的拉格朗日函数可写为：

    从对偶问题(6.11)解出的是式(6.8)中的拉格朗日乘子，它恰对应着训练样本。注意到式(6.6)中有不等式约束，因此上述过程需满足KKT(Karush-Kuhn-Tucker)条件，即要求

        

    于是，对任意训练样本，总有。

        若，则该样本将不会在式(6.12) 的求和中出现，也就不会对f(x)有任何影响;

        若，则必有，所对应的样本点位于最大间隔边界上，是一个支持向量。
    这显示出支持向量机的一个重要性质：训练完成后，大部分的训练样本都不需保留，最终模型仅与支持向量有关。

    那么如何求解式(6.11) 呢?不难发现，这是一个二次规划问题?可使用通用的二次规划算法来求解，二次规划可见附录【3】。这里我还没搞懂，先留着坑。

 3.核函数

    在本章前面的讨论中，我们假设训练样本是线性可分的，即存在一个划分超平面能将训练样本正确分类。然而在现实任务中，原始样本空间内，也许并不存在一个能正确划分两类样本的超平面。例如图 6.3 中的" 异或 " 问题就不是线性可分的。

                

    那如何解决非线性可分问题呢？

    对于原空间中的非线性可分问题，可将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。例如在图6.3中，若将原始的二维空间映射到一个合适的三维空间 ，就能找到一个合适的划分超平面。幸运的是，如果原始空间是有限维，即属性数有限，那么一定存在一个高维特征空间使样本可分。

            

                

    这里的函数 κ(.,.)就是"核函数"。式(6.24)显示出模型最优解可通过训练样本的核函数展开，这一展式亦称"支持向量展式 "显然，若己知合适映射Ф的具体形式，则可写出核函数 κ(.，.)。但在现实任务中我们通常不知道Ф是什么形式，那么，合适的核函数是否一定存在呢?什么样的函数能做核函数呢?

    我们有下面的定理：

        

    那核函数的特点是什么？

    核函数：一个对称函数所对应的核矩阵半正定，它就可作为核函数使用。

    事实上，对于一个半正定核矩阵，总能找到一个与之对应的映射Ф。换言之，任何一个核函数都隐式地定义了一个称为"再生核希尔伯特空间"的特征空间。
    通过前面的讨论可知，我们希望样本在特征空间内线性可分，因此特征空间的好坏对支持向量机的性能至关重要。需注意的是，在不知道特征映射的形式时，我们并不知道什么样的核函数是合适的，而核函数也仅是隐式地定义了这个特征空间。于是，"核函数选择"成为支持向量机的最大变数。若核函数选择不合适，则意味着将样本映射到了一个不合适的特征空间，很可能导致性能不佳。

        

4.软间隔与正则化

    在前面的讨论中，我们一直假定训练样本在样本空间或特征空间中是线性可分的，即存在一个超平面能将不同类的样本完全划分开。然而，在现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性可分。

    退一步说，即使恰好找到了某个核函数使训练集在特征空间中线性可分，也很难断定这个貌似线性可分的结果不是由于过拟合所造成的。

    那么如何缓解该问题呢？

    缓解该问题的一个办法是：允许支持向量机在一些样本上出错。为此，引入"软间隔"的概念，如图 6.4所示：

        

    具体来说，前面介绍的支持向量机是要求所有样本均满足约束(6.3)，即所有样本都必须划分正确，这称为"硬间隔" ，而软间隔则是允许某些样本不满足约束：

    

        

5.实例应用：python使用支持向量机SVM

准备：    

    数据集

    导入SVM模块

步骤：

    1.读取数据集

    2.划分训练样本与测试样本

    4.计算分类准确率

    5.绘制图像

     因为Python中的sklearn库也集成了SVM算法，所以在Python中一样可以使用支持向量机做分类。

    【注意】本文的运行环境是windows+Pycharm+python3.6。

    Scikit-Learn库基本实现了所有的机器学习算法，具体使用详见官方文档说明：

    http://scikit-learn.org/stable/auto_examples/index.html#support-vector-machines

    因为本文是基于sklearn包，所以需先在python中下载sklearn包，网上有很多教程，在此不再叙述。

    数据集

    本文用的数据集为Iris.data可从UCI数据库中下载，http://archive.ics.uci.edu/ml/datasets/Iris

    Iris.data的数据格式如下：共5列，前4列为样本特征，第5列为类别，分别有三种类别Iris-setosa， Iris-versicolor， Iris-virginica。

    注意：因为在分类中类别标签必须为数字量，所以应将Iris.data中的第5列的类别（字符串）转换为num.

        

导入SVM模块

    首先在使用SVM时，需先从sklearn包中导入SVM模块。

1.读取数据集

    定义的转换函数为：可实现将类别Iris-setosa， Iris-versicolor， Iris-virginica映射成 0,1,2。

    读取文件用的是loadtxt函数，其声明如下：

    常用的参数有：

        fname: 文件路径，例 path='F:/Python_Project/SVM/data/Iris.data'

    dtype:样本的数据类型 例dtype=float

          delimiter：分隔符。例 delimiter=','

          converters：将数据列与转换函数进行映射的字典。例 converters={4:Iris_label}含义是将第5列的数据对应转换函数进行转换。

          usecols：选取数据的列。

2.划分训练样本与测试样本

       1. split(数据，分割位置，轴=1（水平分割） or 0（垂直分割）)。

　　2.  sklearn.model_selection.train_test_split随机划分训练集与测试集。train_test_split(train_data,train_label,test_size=数字, random_state=0)

　　参数解释：

　    　train_data：所要划分的样本特征集

　    　train_label：所要划分的样本类别

　    　test_size：样本占比，如果是整数的话就是样本的数量.(注意：)

                   --  test_size:测试样本占比。 默认情况下，该值设置为0.25。 默认值将在版本0.21中更改。 只有train_size没有指定时， 

                        它将保持0.25，否则它将补充指定的train_size，例如train_size=0.6,则test_size默认为0.4。

                   -- train_size:训练样本占比。

　    　random_state：是随机数的种子。

　　    随机数种子：其实就是该组随机数的编号，在需要重复试验的时候，保证得到一组一样的随机数。比如你每次都填1，其他参数一样的情况下你得到的随机数组是一样的。但填0或不填，每次都会不一样。随机数的产生取决于种子，随机数和种子之间的关系遵从以下两个规则：种子不同，产生不同的随机数；种子相同，即使实例不同也产生相同的随机数。

3.训练SVM分类器

    kernel='linear'时，为线性核，C越大分类效果越好，但有可能会过拟合（defaul C=1）。

　 kernel='rbf'时（default），为高斯核，gamma值越小，分类界面越连续；gamma值越大，分类界面越“散”，分类效果越好，但有可能会过拟合。

　 decision_function_shape='ovr'时，为one v rest（一对多），即一个类别与其他类别进行划分，

　 decision_function_shape='ovo'时，为one v one（一对一），即将类别两两之间进行划分，用二分类的方法模拟多分类的结果。

4.计算分类准确率

    结果：

        

    还有另一种计算准确率的方法:

    实际上，classifier.score（）内部也是先predict得到tes_label , 然后调用了accuracy_score(test_label,tes_label)方法来计算准确率的。

    可以查看一下内部决策函数，返回的是 样本到分类超平面的距离 ，

   （1） 若选用“ovr”(一对多)，则每个样本会产生3个距离值（3为类别种类数）。如下：

        

           

    （2）若选用“ovo”(一对一)，则每个样本会产生3*（3-1）/2=3 个距离值,即 ：距离值个数=类别数*（类别数-1）/2。结果如下：

        

        

5.绘制图像

    确定坐标轴范围、字体、背景颜色

    这里用到了mgrid()函数，该函数的作用这里简单介绍一下：

　　 假设假设目标函数F（x，y）=x+y。x轴范围1~3，y轴范围4~6，当绘制图像时主要分四步进行：

　　【step1：x扩展】(朝右扩展)：

       [1 1 1]

　　 [2 2 2]

　　 [3 3 3]

　　【step2：y扩展】(朝下扩展)：

　　 [4 5 6]

　　 [4 5 6]

　　 [4 5 6]

　　【step3：定位（xi，yi）】：

　　 [(1,4) (1,5) (1,6)]

　　 [(2,4) (2,5) (2,6)]

　　 [(3,4) (3,5) (3,6)]

　　【step4：将（xi，yi）代入F(x,y)=x+y】

　　因此这里x1, x2 = np.mgrid[x1_min:x1_max:200j, x2_min:x2_max:200j]后的结果为：

　　

　　再通过stack()函数，axis=1，生成测试点

　　

    绘图：

           pcolormesh(x,y,z,cmap)这里参数代入x1，x2，grid_hat，cmap=cm_light绘制的是背景。

　　    scatter中edgecolors是指描绘点的边缘色彩，s指描绘点的大小，cmap指点的颜色。

　    　xlim指图的边界。

     pcolormesh(x,y,z,cmap)绘制的背景如下：即将坐标系下的点都进行一个分类。

                

                所有样本点的分类结果：

                    

                将测试点从中圈出来：

                        

    完整代码如下：

 -------------------------------------------        ------------------------------------------------

-------------------------------------------------------   附录   ----------------------------------------------

附录【1】：

    

    注意:  ||w||是指欧几里得范数，例，w=（w1,w2,…wn）的转置,  ||w||的求解如下：

        所以，的表达式如下：

        

附录【2】

    凸函数：对区问 [α，b]上定义的函数 f，若它对区间[a,b]中任意两点X1，X2 均有

                   ,则称 f 为区间 [α ， b]上的凸函数 。

    在凸集中任取两个点连成一条直线，这条直线上的点仍然在这个集合内部，如下图的左图。

    优点：凸函数局部最优就是全局最优，而右边的非凸函数的局部最优就不是全局最优了。

        

    （左为凸函数，右为非凸函数）

附录【3】

    二次规划
    二次规划(Quadratic Programming，简称 QP)是一类典型的优化问题，包括凸二次优化和非凸二次优化。在此类问题中，目标函数是变量的二次函数，而约束条件是变量的线性不等式。

    假定变量个数为d，约束条件的个数为m，则标准的二次规划问题形如：

        

    其中m为d维向量，为实对称矩阵，为实矩阵，和为实向量，Ax≤b的每一行对应一个约束。

    可能的情况有：

    （1）若Q为半正定矩阵，则式(B.12)目标函数是凸函数，相应的二次规划是凸二次优化问题，此时若约束条件Ax≤b定义的可行域不为空，且目标函数在此可行域有下界，则该问题将有全局最小值。

    （2）若Q为正定矩阵，则该问题有唯一的全局最小值。

    （3）若Q为非正定矩阵，则式(B.12)是有多个平稳点和局部极小点的NP难问题。
    常用的二次规划解法有椭球法(ellipsoid method)、内点法(interior point)、增广拉格朗日法 (augmented Lagrangian) 、梯度投影法 (gradient projeetion) 等。若Q为正定矩阵，则相应的二次规划问题可由椭球法在多项式时间内求解。

    注意：

    非标准二次规划问题中可以包含等式约束，注意到等式约束能用两个不等式约束来代替;不等式约束可通过增加松弛变量的方式转化为等式约束。

 -------------------------------------------         END      -------------------------------------

参考：

周志华《机器学习》

SVM-支持向量机原理详解与实践 https://www.cnblogs.com/spoorer/p/6551220.html

Python中的支持向量机SVM的使用（有实例） http://www.cnblogs.com/luyaoblog/p/6775342.html（非常好）