机器学习简明教程-基于Python语言实现 课件 第7章支持向量机

支持向量机《机器学习简明教程》高延增侯跃恩罗志坚机械工业出版社07本章目标•理解线性可分、间隔最大化的概念•理解对偶问题•掌握线性支持向量机•了解非线性支持向量机支持向量机（SupportVectorMachine,SVM）是一种非常优雅的算法，具有完善的数学理论支撑，早在1963年就由Vapnik提出了，直到20世纪末才被广泛使用。在深度学习算法流行之前，SVM一直是传统机器学习算法的典型代表，在模式识别、回归、分类等领域得到广泛应用，一度被业界称为最成功的机器学习算法。SVM是一种有监督的二分类模型，目前在小样本、非线性、高维场景下依然表现亮眼，并且该算法数学理论完备，是数据挖掘从业者必须掌握的算法之一。SVM的核心思想是在对样本空间分类的时候使用间隔最大化的分类器，而最让人称奇的问题解决思路是将低维度上线性不可分的样本扩展到多维空间中，然后就可以在多维空间中构建一个线性分类器将这些样本分开，同时使用核技巧降低这一过程的计算复杂度。SVM实现样本分类过程中涉及到线性可分、间隔最大化、核技巧等知识，本章将分别介绍。目录/Contents7.17.2SVM相关概念线性SVM7.3非线性SVM7.4软间隔7.5应用案例7.1SVM的相关概念

7.1SVM的相关概念——线性可分

若找不到这样的超平面，数据集就是线性不可分的线性可分线性不可分7.1SVM的相关概念——间隔最大化点到面的距离

7.1SVM的相关概念——间隔最大化

但仅满足上式的参数构成的分隔超平面鲁棒性较弱，我们希望能找到类似下图中两条虚线中间的实线作为分隔线，这样的分割线具有较好的鲁棒性。上面的公式变成：支持向量（SupportVector）就是左图落在虚线上的正负实例点。而正负支持向量与分隔平面的距离之和被称为间隔，如公式

（7.7）7.1SVM的相关概念——间隔最大化上页图中，改变ω,b的值即改变分隔平面的法向量和相对坐标原点的平移量，会使得间隔的大小也发生变化，我们希望能找到可以使间隔取得最大值的ω确定的那个分隔平面。间隔的最大值，被称为最大间隔，正因如此SVM又常被称为大间隔分类器（largemarginclassifier）。对应的两条包含支持向量的两条虚线被称为间隔边界，由上页图可知分隔超平面、分割边界由支持向量决定。

（7.9）

目录/Contents7.17.2SVM相关概念线性SVM7.3非线性SVM7.4软间隔7.5应用案例7.2线性SVM式（7.9）的解ω*,b*确定一个样本集的分隔超平面

（7.10）式（7.9）是一个凸二次规划问题，可以用拉格朗日乘子法得到其对偶问题，通过求解对偶问题得到原始问题的最优解。引进拉格朗日乘子后会使对偶问题相对原始问题更容易求解，而且可以推广到非线性分类问题。7.2线性SVM——对偶问题

（7.11）定义广义拉格朗日函数为：

（7.12）7.2线性SVM——对偶问题

7.2线性SVM——学习算法

（7.19）

7.2线性SVM——学习算法利用对偶性转换，得到对偶问题（7.20）（7.20）

（7.21）（7.22）可得式（7.23）、（7.24）。

（7.23）（7.24）7.2线性SVM——学习算法

（7.25）（7.26）由此得到式（7.9）的对偶问题

若对偶问题（7.26）的解恰好对应（7.9）的解，需满足KKT条件，此处的KKT条件是（7.27）7.2线性SVM——学习算法

（7.28）

（7.29）

（7.30）7.2线性SVM——学习算法

（7.31）

（7.32）至此，就完成了线性支持向量机的求解，由支持向量得到了一个线性分类器（7.33）

目录/Contents7.17.2SVM相关概念线性SVM7.3非线性SVM7.4软间隔7.5应用案例7.3非线性SVM——核心思想对于线性不可分集合，SVM算法将它们从原始空间映射到更高维度的空间中，使得它们在高维的空间中变成线性可分的

（7.34）（7.35）

7.3非线性SVM——核心思想对偶问题也由（7.26）转变为式（7.36）（7.36）

如果有办法在原始特征空间计算映射后的高维空间的内积，就可以直接在原始特征空间上构建一个分类器了，这种直接在原始空间上计算内积的方法称为核函数方法。7.3非线性SVM——核心思想

（7.37）7.3非线性SVM——核函数的应用

（7.38）对于一个新的样本，式（7.38）给出了高维空间上的线性分类器的计算方法,但是有了核函数，我们不需要计算内积，使用式（7.39）进行分类，这样就避免了高维空间中计算量大增的“维数灾难”问题。（7.39）

7.3非线性SVM——核函数的应用例7.3.1：假设二维空间上的向量x到三维空间上的映射如式（7.40），求这个映射的核函数。（7.40）（7.41）（7.42）已知映射公式（7.40）假设二维空间上的两个向量x,y，映射到三维空间后的向量内积如式（7.41）。而在映射之前的二维空间中，向量x,y的内积如式（7.42）

7.3非线性SVM——核函数的应用（7.43）若将例7.3.1中的映射变得更复杂一点，将二维空间的向量映射到四维空间中，如式（7.43）。你会发现映射（7.43）与（7.40）具有相同的核函数。显然，核函数的计算复杂度要比在映射后的高维空间中直接计算向量内积的复杂度更低。

从式（7.36）、（7.39）知，高维空间中对偶问题求解、最后分隔超平面的解析式都只需要计算映射后的向量内积，不需要知道映射的具体形式。我们直接在原始空间中找到一些函数，判断这些函数是否可以作为有效的核函数，然后将核函数直接代入（7.36）、（7.39）就可以得到高维的线性分隔超平面，这样就节省了高维映射、高维空间向量内积运算等操作，降低了复杂度。Mercer定理给出了一个判断某个函数是否可以作为核函数的方法。7.3非线性SVM——核函数的应用

（7.44）定理第一句是说核函数是原始空间上两个向量到一个实数的映射，后半句中训练样例的核函数矩阵如式Mercer定理说明任何一个使矩阵（7.44）为半正定矩阵的函数k∙,∙都可以使一个有效的核函数，而每个有效的核函数又可以隐式地定义了一个特征空间，这个特征空间被称为再生核希尔伯特空间（ReproducingKernelHilbertSpaces,RKHS）。

7.3非线性SVM——核函数的应用

有了核函数就可以隐式的生成一个高维空间，但是样本集在这个隐式的高维空间中是否具有一个良好的线性分隔超平面呢？这就要看核函数的选择了，所以现在原始空间上线性不可分样本集的分类问题就变成了寻找合适的核函数问题了。7.3非线性SVM——常用核函数核函数的选取直接关系到对样本集的分类效果，因此通常需要根据应用场景选择合适的核函数。具体的应用场景中，有专用核函数和通用核函数两类，专用核函数需要根据具体应用场景去构造，而常见的通用核函数包括：线性核、多项式核、高斯核、拉普拉斯核、Sigmoid核。线性核函数如式（7.46）,

线性核主要用于线性可分的场景，原始空间和映射空间的维度并没有发生变化。线性核的优点是参数少、速度快，缺点是不能解决线性不可分的样本集分类问题。（7.46）多项式核函数如式（7.47），式中γ=1,n=1时就变成了线性核。通过升维使原本线性不可分的样本集变得线性可分。（7.47）7.3非线性SVM——常用核函数高斯核函数如式（7.48），式中σ为高斯核的带宽。高斯核函数是一种局部性强的核函数，其可以将一个样本映射到一个更高维的空间内，该核函数是应用最广的一个，无论大样本还是小样本都有比较好的性能，相对于多项式核函数参数要少，在不确定合适的核函数的场景下可以优先尝试高斯核函数的分类效果。Sigmoid核函数如式（7.49），式中tanh∙为双曲正切函数。Sigmoid函数经常用在神经网络的映射中。

（7.48）（7.49）

7.3非线性SVM——学习算法有了核函数后，就是对公式（7.37）的求解，求解方法与线性SVM类似，假设最优解为α*,b*，则对应的非线性SVM如式（7.50）。（7.50）

（7.51）与线性SVM的算法相比，非线性SVM的学习算法步骤多了选取适当核函数的工作，其算法步骤包括：（1）选择适当的核函数；（2）求解对偶问题α*；（3）求解偏移量b*；（4）构造分类决策函数（7.50）。步骤一：选择核函数。具体哪种核函数更适合，要看待分类的训练集。如果训练集的特征数量多，样本数量不太多可以考虑使用线性核；如果特征数量少、样本数量比较多的时候考虑使用高斯核。在不确定哪种核函数更合适的时候，可以采用交叉验证的方式比较各种不同核函数的分类效果，然后选择一个最优的。步骤二：求解最优化问题。选定了核函数后，就是解对偶问题（7.37），与线性SVM求解类似也可以使用SMO算法求解。步骤三：计算偏移量。选择α*的正分量αi*计算b*，如式（7.52）。

步骤四：构造非线性SVM的决策函数（7.50）。7.3非线性SVM——学习算法（7.52）目录/Contents7.17.2SVM相关概念线性SVM7.3非线性SVM7.4软间隔7.5应用案例7.4软间隔——定义前面SVM求解的假设是样本集都是严格可分的，原始空间上线性可分或映射空间上线性可分。但是，现实应用中由于噪声点一类的影响导致训练集可能并不是完美可分的，而且严格完美的分隔超平面很有可能是过拟合的结果。为了解决这些问题，在SVM算法的间隔最大化时使用软间隔对公式（7.9）进行优化。为使SVM更具通用性、防止过拟合，引入软间隔如下图，软间隔允许某些样本不满足约束条件，即软间隔支持向量并不一定是离分隔超平面最近的点。这样就可以过滤掉在分隔超平面附近由于噪声而被错误归类的点。7.4软间隔——定义

（7.54）

（7.55）

7.4软间隔——采用软间隔的SVM与硬间隔线性SVM算法类似，采用软间隔的SVM求解也经过拉格朗日函数构建、对偶问题、问题求解、利用求解得到的分隔超平面构建分类模型四个步骤。式（7.55）引入拉格朗日乘子，得到拉格朗日函数如式（7.56）。（7.56）式（7.56）中，αi,γi为拉格朗日乘子。与7.2.2的方法类似，Lω,b,α,ε,μ分别对ω,b,ε求偏导,令其为0，得：（7.57）（7.58）（7.59）7.4软间隔——采用软间隔的SVM

（7.60）由于采用的是软间隔，相对应的KKT条件也变为（7.61）7.4软间隔——采用软间隔的SVM

（7.62）（7.63）

目录/Contents7.17.2SVM相关概念线性SVM7.3非线性SVM7.4软间隔7.5应用案例7.5应用案例使用SVM算法制作一个鸢尾花的分类器。尾花，它是一种较常见的单子叶百合目花卉。早在上世纪30年代，就有科学家采集了鸢尾花的萼长、萼宽、瓣长、瓣宽与具体种类之间的对应数据作为线性分类器的验证集。鸢尾花数据集非常经典，是各种机器学习算法常用的验证数据源。Sklearn包的数据集中就包含了鸢尾花数据，可以通过load_iris来加载。数据集包含三种鸢尾花（setosa,versicolor,virginica）合计150条记录，每个种类50条记录。每条记录都包含了花的萼长、萼宽、瓣长、瓣宽（单位：cm），以及对应的鸢尾花种类。7.5应用案例使用SVM算法制作一个鸢尾花的分类器。

以萼长（sepallength）和萼宽（sepalwidth）为横、纵坐标，然后根据鸢尾花类别不同使用不同大小和颜色的点绘制成散点图如右图以花萼尺寸构建二维平面上鸢尾花不是线性可分的。7.5应用案例构建并求解SVM分类器，python的sklearn包提供了很好的SVM分类器实现，使用时只需通过设置合适的接口参数即可得到适用于所处理数据的SVM分类器。Sklearn.svm.SVC使用时常被调整参数包括：核函数（kernel）、正则化参数（C）、多项式核函数的次数（degree，poly核时有效）、核系数（gamma，rbf,poly,sigmoid核有效）、核函数中的常数项（coef0，poly,sigmoid核有效）等。核函数的选取对分类效果影响较大，可选的包括线性核（linear）、多项式核（poly）、径向基函数核（rbf）、S