SVM+松弛变量实验报告(附matlab源码).pdfVIP

1 实实 验验 报报 告告 实验名称： SVM 算法实现 学 员： 何浩辰 学 号： 17060*4 专 业： 软件工程 所属学院： 2 一、实验目的和要求 Homework 2：实现线性支持向量机算法 二、实验内容和原理 1.SVM 算法原理 核心思想：对于线性可分的数据，找到一个划分超平面，将两类样本分开，使 得两类样本距离划分超平面的距离尽可能大。 样本集到超平面的距离定义为： 因此优化目标为： 其中，w 必须满足约束条件是将所有样本分类正确。为了简化上式， ，得到下式： 3 注意到，化简并不影响结果，因为分类器最终是取符号， 而。 取优化目标的倒数，得到 SVM 问题的原始形式： 其中，优化目标是严格正定的，所有的约束都是线性的，因此本优化问题是具 有线性约束的二次规划典型的凸优化问题，则最优解存在且唯一。 可以直接对上面问题进行求解，也可对其进行进一步化简。 为解上式，使用拉格朗日乘子法： 得到需满足的 KTT 条件 将 KTT 条件中的等式带入拉格朗日函数，得到原始问题的对偶问题： 该问题也是一个标准的带约束二次规划问题。未知数为，求解出后，需要 在求解 w、b：。注意到， 4 支持向量的点为对应 i 0 (i)的样本。 上述方法对线性可分数据有效，对于非线性可分数据： 超平面 x + b = 0: i)错误地分类 x i ; ii)正确地分类 x j ，但间隔小于 1。可以 假设，此时需要在间距最大化和训练误差最小化之间找到一个平衡点。则考虑允许 训练过程中有误差： 其中，C 为正则化参数是调节模型复杂度与训练误差的。但此时多了未知变量 ，直接对原始问题求解变得困难，所以要转换为其对偶形式。此时的拉格朗日函数 和 KTT 条件为： 将 KTT 条件带入拉格朗日函数： 5 相比于线性可分的情况，仅仅多出一个约束条件，且和均未出现，可以容易 的求解。得到后，按线性可分的情况求解 w 和 b 即可。 2.数据集 IRIS花的萼片的长度、宽度和花瓣的长度宽度数据，标签为画的种类： 。 。 。 。 。 。 上图为 iris 数据集， 分别选取线性可分数据 （第 1-100 行） 和非线性可分数据 （第 51-150 行） ，用于训练原始的 SVM 和引入松弛变量后的 SVM。考虑到 2 维和 4 维 在实现上无本质区别，为方便展示结果和可视化，选取两维（线性可分： sepal.lengthline150 和 sepal.width150 非线性可分：sepal.lengthline51150 和 petal.widthline51150）数据进行实验。 三、操作方法与实验细节 6 实验环境：Windows 10 编程语言：Matlab 1. 数据预处理 首先进行数据中心化处理，对于 SVM 算法而言，是否进行数据中心化，对训练 速度影响没有感知机那么大。 2. 线性可分-算法过程 对于线性可分数据， 本实验对原问题使用二次规划求解， 使用的函数为 quadprog 函数（） 。要使用这个函数，就要先将 化成标准的二次规划的形式： 具体演算为本人手写，如下图所示： 7 3. 非线性可分-算法过程 8 对于非线性可分数据，本实验使用原问题的对偶问题进行求解： 因为约束中出现了等式约束，所以 quadprog 函数需要更多的参数： 。同样，需要将对偶问题化成标准的二 次规划的形式，过程如下所示： 9 求出后，再用公式和求 出 w 和 b： 四、实验结果与分析 1.时间开销 原始 SVM 算法运行时间： 引入松弛变量的 SVM 算法运行时间： 第二个模型比第一个模型要复杂，所用时间约为 10 倍 2.对于数据线性可分的情况 10 完全划分 一共四个支持向量点（=0 对应的样本点） ，如图所示。显然，超平面距离支 持向量样本距离足够远。 3.对于数据非线性可分的情况 11 非线性可分的情况 共有 31 个支持向量点，其中参数 C 取 2.3。参数 C 取值超过某个值就不会再对 训练结果产生影响，这个阈值在 4 左