SVM+松弛变量实验报告(附matlab源码)
- 格式：pdf
- 大小：1.35 MB
- 文档页数：13
实验报告
实验名称：SVM算法实现
学员：何浩辰学号： 17060**4 专业：软件工程所属学院：
一、实验目的和要求
Homework 2：实现线性支持向量机算法
二、实验内容和原理
1.SVM算法原理
核心思想：对于线性可分的数据，找到一个划分超平面，将两类样本分开，使得两类样本距离划分超平面的距离尽可能大。
样本集到超平面的距离ρ定义为：
因此优化目标为：
其中，w必须满足约束条件是将所有样本分类正确。
为了简化上式，
，得到下式：
注意到，化简并不影响结果，因为分类器最终是取符号，
而。
取优化目标的倒数，得到SVM问题的原始形式：
其中，优化目标是严格正定的，所有的约束都是线性的，因此本优化问题是具有线性约束的二次规划—典型的凸优化问题，则最优解存在且唯一。
可以直接对上面问题进行求解，也可对其进行进一步化简。
为解上式，使用拉格朗日乘子法：
得到需满足的KTT条件
将KTT条件中的等式带入拉格朗日函数，得到原始问题的对偶问题：
该问题也是一个标准的带约束二次规划问题。
未知数为α，求解出α后，需要在求解w、b：。
注意到，
支持向量的点为对应α i ≥0 (∀i)的样本。
上述方法对线性可分数据有效，对于非线性可分数据：
超平面ω⊤ x + b = 0: i)错误地分类x i ; ii)正确地分类x j ，但间隔小于1。
可以假设，此时需要在间距最大化和训练误差最小化之间找到一个平衡点。
则考虑允许训练过程中有误差：
其中，C为正则化参数是调节模型复杂度与训练误差的。
但此时多了未知变量ξ，直接对原始问题求解变得困难，所以要转换为其对偶形式。
此时的拉格朗日函数和KTT条件为：
将KTT条件带入拉格朗日函数：
相比于线性可分的情况，仅仅多出一个约束条件，且ξ和β均未出现，可以容易的求解。
得到α后，按线性可分的情况求解w和b即可。
2.数据集
IRIS—花的萼片的长度、宽度和花瓣的长度宽度数据，标签为画的种类：。
上图为iris数据集，分别选取线性可分数据（第1-100行）和非线性可分数据（第51-150行），用于训练原始的SVM和引入松弛变量后的SVM。
考虑到2维和4维在实现上无本质区别，为方便展示结果和可视化，选取两维（线性可分：sepal.length@line1~50和sepal.width@1~50 非线性可分：sepal.length@line51~150和petal.width@line51~150）数据进行实验。
三、操作方法与实验细节
实验环境：Windows 10
编程语言：Matlab
1.数据预处理
首先进行数据中心化处理，对于SVM算法而言，是否进行数据中心化，对训练速度影响没有感知机那么大。
2.线性可分-算法过程
对于线性可分数据，本实验对原问题使用二次规划求解，使用的函数为quadprog 函数（）。
要使用这个函数，就要先将
化成标准的二次规划的形式：
具体演算为本人手写，如下图所示：
3.非线性可分-算法过程
对于非线性可分数据，本实验使用原问题的对偶问题进行求解：
因为约束中出现了等式约束，所以quadprog函数需要更多的参数：。
同样，需要将对偶问题化成标准的二次规划的形式，过程如下所示：
求出α后，再用公式和求出w和b：
四、实验结果与分析
1.时间开销
原始SVM算法运行时间：
引入松弛变量的SVM算法运行时间：
第二个模型比第一个模型要复杂，所用时间约为10倍
2.对于数据线性可分的情况
完全划分
一共四个支持向量点（α>=0对应的样本点），如图所示。
显然，超平面距离支持向量样本距离足够远。
3.对于数据非线性可分的情况
非线性可分的情况
共有31个支持向量点，其中参数C取2.3。
参数C取值超过某个值就不会再对训练结果产生影响，这个阈值在4左右（这与0<=α<=C的约束相符）。
若C取值过小则分类效果不好，经调参得出C=2.3时取得当前的最优解。
五、问题
原始问题的对偶问题中，二次项对应矩阵H是否为半正定（已解决）。
首先X’×X是一个半正定的对称矩阵，Y×Y’也是半正定的对称矩阵，根据Schur乘积定理，两个半正定矩阵的乘积还是半正定矩阵。
因此矩阵H为半正定矩阵。
一开始没有注意到这个数有多小，只关注了负号，其实这个就是0。
六、源码
线性可分（原始问题）：
[attrib1, attrib2] = textread('C:\Users\hhc\Documents\iris-2D.data', '%f%f', 'delimiter', ','); X = [(attrib1-mean(attrib1))'; (attrib2-mean(attrib2))'];
Y = [ones(50, 1); -ones(50,1)];
plot(X(1,1:50),X(2,1:50),'r.');
hold on;
plot(X(1,51:100),X(2,51:100),'b.');
tic
u = svm(X,Y);
toc
x = linspace(-1,1);
y=-u(2)*x/u(3) - u(1)/u(3);
plot(x,y);
hold off;
function u = svm( X,Y )
[K,N] = size(X);% K=2, N=100
A = -repmat(Y,1,K+1).*[ones(N,1) X'];
b = -ones(N,1);
H = eye(K);
H = [zeros(1,K);H];
H = [zeros(K+1,1) H];
p = zeros(K+1,1);
[u,fval,exitflag,output,lambda]=quadprog(H,p,A,b,[],[]);
% 标注支持向量样本点
非线性可分（对偶问题）：。
