人工智能算法与实践-第5章 支持向量机

5.4算法总结5.1算法概述5.2算法原理5.3算法案例目录第五章支持向量机人工智能算法与实践—1

—

01算法概述PartTHREE—2

—

支持向量机线性可分支持向量机非线性支持向量机二分类模型线性支持向量机支持向量机（SupportVectorMachine，SVM）是一种二分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器。它分为线性可分支持向量机、线性支持向量机、非线性支持向量机。5.1算法概述算法概述—3

—

线性可分支持向量机线性支持向量机非线性支持向量机1线性可分支持向量机当训练数据线性可分时，通过硬间隔最大化。则需要对数据使用线性可分支持向量机。2线性支持向量机当训练数据线性近似可分时，通过软间隔最大化，则需要对数据使用线性支持向量机。3非线性支持向量机当训练数据线性不可分时，通过硬间隔最大化和核技巧，则需要对数据使用非线性支持向量机。5.1算法概述算法概述—4

—

02算法原理PartTHREE—5

—

算法原理246531线性可分支持向量机拉格朗日乘子法对偶问题和KKT条件。SMO算法原理非线性支持向量机线性支持向量机5.2算法原理算法原理—6

—

找出无数条线将两类分开如图所示，有很多个分离超平面可以将数据分为两类。究竟哪一个分离超平面的分类效果最好呢？在SVM中，假设拥有最大“间隔”的超平面效果最好。计算出最大间隔最终将如何计算出最佳分离超平面转换为如何计算最大间隔。随机找一条线将两类分开通俗来讲，为了将两类数据分开，最简单的办法就是求解一个分离超平面，该平面能够将实例分到不同的类别。寻找出三条直线为了找到最佳的一个分离超平面，需要假设三条直线，其中有两条直线会穿过K、U两点，这两个点叫做支持向量并且分别是这两类中的一个点。5.2.1线性可分支持向量机线性可分支持向量机—7

—

最大间隔d最终通过转换，即是求解：5.2.1线性可分支持向量机线性可分支持向量机—8

—

假设三条直线的方程为：求解:010203无约束条件这是最简单的情况，解决方法通常是函数对变量求导，令求导函数等于0的点可能是极值点。将结果带回原函数进行验证即可。等式约束条件有等式约束条件的：不等式约束条件5.2.2拉格朗日乘子法拉格朗日乘子法—9

—

如何求出

？这里，我们需要引入一种方法叫做拉格朗日乘子法（LagrangeMultiplier），这种方法的目的就是将有n个变量和一个或k约束条件的最优解问题转换为一个有n+k个变量的方程组的极值问题，其变量不受任何约束（n和k为自然数）需要通过消元求解，或拉格朗日法求解。最终能求出f(x)的最小值。有不等式约束条件的：最终将原问题转换为：对偶问题对偶问题就是实质相同但从不同角度提出不同提法的一对问题，通过这种方法来求得最终的答案

。定义对偶问题：KKT条件KKT条件就是满足：（1）5.2.3对偶问题和KKT条件对偶问题和KKT条件—10

—

强对偶定理：（1）原函数是凸函数（2）约束条件f(x),g(x)是线性式子

（3）满足KKT条件（3）最终将问题转换为：（2）（4）SMO算法原理为了解决等式5.2.4

SMO算法SMO算法原理—11

—

需要引入SMO原理，SMO算法是一个启发式避免了二次规划数值解法的复杂迭代过程。这不但大大节省了计算时间，而且不会牵涉到迭代法造成的误差积累（其它一些算法中这种误差积累带来了很大的麻烦）。理论上SMO的每一步最小优化都不会造成任何误差积累，而如果用双精度数计算，舍入误差几乎可以忽略，于是所有的误差只在于最后一遍检验时以多大的公差要求所有拉格朗日乘子满足KKT条件。可以说SMO算法在速度和精度两方面都得到了保证。算法。为了计算的最大值。需要先给它们一个初始值，然后固定其他n-1个值然后再求其中一通过对所有的求解，最终可以求得原问题的最优解：则求解出了一个最佳分离超平面。个。同理所有的都是这样求出来的。SMO的最大特色在于它可以采用解析的方法而完全非线性支持向量机非线性分类问题中，我们不能在二维空间上找到一条线去区分这两类数据集，而是需要对这些数据进行变换。将数据从低维向高维做映射，这样做的目的是将非线性问题转换为线性问题，但是做这样转换势必会增大处理问题的规模。为了避免这个问题的发生，可以使用一个叫做核函数的东西，它既不会使维度上升又可以使问题变为线性问题求解。求解非线性支持向量机的对偶问题为：5.2.5非线性支持向量机非线性支持向量机—12

—

非线性支持向量机常见的核函数有两种：5.2.5非线性支持向量机非线性支持向量机—13

—

（1）多项式核函数：（2）高斯核函数：每个核函数中的参数对于SVM都有着不同的影响，在这里仅拿高斯核函数中的

谈谈它对SVM的影响。当时，两类的区分度下降，会出现欠拟合现象。当时，两类的区分度会上升，但是如果选择不当也会出现过拟合现象。线性支持向量机

若数据集在线性可分且存在一些噪点，则需要使用线性支持向量机进行求解。在线性支持向量机中，通过加入松弛变量，让噪点也满足构建的方程。再进行方程的求解。5.2.6线性支持向量机线性支持向量机—14

—

线性支持向量机

需要说明的一点是称为损失函数。应满足的条件是：5.2.6线性支持向量机线性支持向量机—15

—

式中C为惩罚系数，当时，会出现过拟合现象。C越小则会出现欠拟合现象。所以C的合理选取是至关重要的。

对偶问题和KKT条件

线性可分支持向量机拉格朗日乘子法

非线性支持向量机5.2算法原理算法原理—16

—

SMO原理

线性支持向量机03算法案例-手写体数字识别PartTHREE—17

—

算法案例-手写体数字识别虽然数字的笔画简单，类别较少。但是由于不同的人写出来的数字总带有着个人特色，数字相较于文字来说没有一些上下文的关系更是少了一些相关性。最重要的是，由于数字总是与金融、财会挂钩，所以数字的准确性关系到事情的成败问题。所以正确识别手写体数字的重要性不言而喻。左图为未经处理的部分数据。5.3算法案例-手写体数字识别算法案例-手写体数字识别—18

—

算法案例-手写体数字识别

针对此次实验，前期我们收集了近1000张来自不同人手写的数字集。将该数据集作为此次实验的实验数据集。再通过降维、取特征值等预处理的方法将该数据集进行前期的处理，得到想要的数据集。将处理好的数据集进行分割，将80%的数据集作为训练集，再用剩余20%作为测试集。左图是该算法的流程图。由于收集到的数据都是一些大小不一的图片。所以第一步需要对图片进行一些预处理，通过二值化的操作将图片像素全部处理为0或1。使用0或1来描述图像中的信息。5.3算法案例-手写体数字识别算法案例-手写体数字识别—19

—

算法案例-手写体数字识别

本份数据集共有2000条数据，1600条数据会作为训练集，剩下的400条数据会作为测试集去评判该模型的准确率。接下来就是上述提到的将图片进行二值化处理。

二值化处理即为每个像素只有两个可能值得数字图像。简单来讲就是将图像中其将大于某个临界灰度值的像素灰度设为灰度极大值，小于这个值的为灰度极小值，从而实现二值化。这样做的目的就是减少不必要的信息量，提高后期对数据的处理速度。最后将处理过后的数据存成文本形式，以便于模型的使用，处理后的部分数据如左图所示。5.3算法案例-手写体数字识别算法案例-手写体数字识别—20

—

算法案例-手写体数字识别

在本次试验中选用的核函数为高斯核函数。对于模型准确率的影响最大的两个参数分别是前面所介绍的惩罚系数C和高斯核函数中的

。通过对两个参数的调整，确定最终的SVM模型。我们使用了控制变量法来对两个参数进行调整，惩罚系数C调整的结果图如左图所示（纵轴为模型的准确率，横轴分别表示两个参数）。不难发现，当C=2.4时，模型的准确率最高。5.3算法案例-手写体数字识别算法案例-手写体数字识别—21

—

算法案例-手写体数字识别在本次试验中选用的核函数为高斯核函数。对于模型准确率的影响最大的两个参数分别是前面所介绍的惩罚系数C和高斯核函数中的

。通过对两个参数的调整，确定最终的SVM模型。我们使用了控制变量法来对两个参数进行调整，惩罚系数C调整的结果图如左图所示（纵轴为模型的准确率，横轴分别表示两个参数）。不难发现，当=0.006时，模型的准确率最高。5.3算法案例-手写体数字识别算法案例-手写体数字识别—22

—

算法案例-手写体数字识别通过综合两个图中的信息，我们发现两个参数并不是取值越大越理想，两个参数都有各自的最优取值。最终得出当C=2.4，=0.006时，该模型的准确率最高。准确率在98.6%左右。因为手写体自身因为出自不同的人所以本身所带的噪点就会有很多，能训练出如此高的准确率是比较理想的状态