当前位置:首页 >> 数学 >>

模式识别结课论文


模式识别结课论文

题 学 专 姓 学

目:模式识别中基于支持向量机算法分析 院: 业: 名: 号: 电气工程与信息工程学院 电气工程

指导教师:

教授

1 支持向量机
支持向量机是从线性可分情况下的最优分类面发展而来的, 因此我们也从线 性可分情况下的支持向量机思想开始讨论支持向量机的理论

1.1 线性支持向量机
首先我们分析如下图的分类问题

y
x w?b ?1
T

xT w ? b ? 1
xT w ? b ? 0
2 w
2

xT w ? b ? ?1

xT w ? b ? ?1

O

x
图 1 线性可分分类问题

图 1 中包含两类共十个样本点,我们现在的目的是将其正确分开为两类,显 然有许多直线能将两类样本点正确分开, 所以我们需要讨论的是哪条分类直线更 好一些。 而最好的一条分类直线就是使分类间隔最大的直线,这条直线的求解方 式如下。 首先我们假定分类直线方程为
xT w ? b ? 0

(1.1)

我们定义过两类样本点中离分类线最近点平行分类线的直线为支持直线, 则 支持直线方程为

xT w ? b ? 1 xT w ? b ? ?1
则两条支持直线之间的距离为

(1.2)

2 w
2

,这样我们求最优分类线的问题就转化

为求使

2 w
2

取最大值的 w 的问题。而分类问题的最基本要求是能够正确分类,

因此样本点应该在如下区域中

xT w ? b ? 1 xT w ? b ? ?1
这样我们可以得到如下的最优化问题

(1.3)

min s.t.

1 2 w 2 yi ? xiT w ? b ? ? 1, i ? 1, 2,L ,10

(1.4)

此时引入 Lagrange 函数得到 10 1 2 L ? w, b, ? ? ? w ? ? ? i ? yi ? xiT w ? b ? ? 1? ? ? ? i ? 0, i ? 1, 2, L ,10 2 i ?1
10 ?L ? w, b, ? ? ? w ? ? ? i yi xi ? 0 ?w i ?1

(1.5)

?L ? w, b, ? ? 10 ? ? ? i yi ? 0 ?b i ?1

这样可以得到式(1.5)的对偶问题
max W ?? ? ? ? ? i ?
i ?1 10

1 10 ? yi y j? i? j ? xiT x j ? 2 i , j ?1

s.t.

? i ? 0 i ? 1, 2, L ,10

(1.6)

?? y
i ?1 i

10

i

?0

这是一个凸规划问题,我们根据 KKT 条件,假设得到该对偶问题的解为

?i , i ? 1, 2,L 10 ,那么 ?
?i yi xi ? ? ? ?i yi xi ? ? ?? w
i ?1 i ?1 10 p

(1.7)

?i , i ? 1, 2,L 10 中的一个正分量 ? ? j ,据此计算 选取 ?
?? y ? ? b ? ?i yi ? xi x j ? j
i ?1 10

(1.8)

? ? 0 ,由此求得决策函数 ? ?b 构造分类超平面 xT w

f ? x ? ? sgn ? g ? x ??
其中
? ? y? ? ? ?b g ? x ? ? xT w ? i ?i ? xiT x ? ? b
i ?1 10

(1.9)

(1.10)

这就是线性可分支持向量机的基本原理。

1.2 非线性支持向量机
上面讨论的是最优和广义线性分类函数, 要解决一个特征空间中的最优线性 分类问题, 我们只需知道这个空间中的内积运算即可。支持向量机的最主要特点 还是解决非线性问题的能力,我们假设如下 XOR 问题
z

x

x

y (a)

y (b)

图 2 非线性分类问题

我们首先观察图 2(a)中的分类问题,无法通过线性方法处理,因此我们需要 寻找其他方法。假定 x ? ? x1, x2 ? ,我们定义映射

? ? x ? ? ??1 ? x ? , ?2 ? x ? , ?3 ? x ? ? ? ? x1 ? , ? x2 ? , 2 x1 x2
2 2

?

?

(1.11)

这样我们可以得到四个样本点的如下映射

? 0, 0 ? ? ? 0, 0, 0 ? ?1,1? ? ?1,1, 2 ? ? 0,1? ? ? 0,1, 0 ? ?1, 0 ? ? ?1, 0, 0 ?

(1.12)

这样就形成了如图 2(b)所示的空间关系,在这个三维空间上,分类问题成为 了线性问题。 这就是支持向量机处理非线性问题思想的简单表示,将该非线性问 题通过函数映射到更高维的空间中,使其变为线性问题,继而在高维空间中进行 线性规划。具体算法如下 给定训练集

T ? ?? x1 , y1 ? ,L , ? xl , yl ?? ? ? R n ? y ? xi ? R n , yi ? y ? ?1, ?1? , i ? 1,L , l
构造并求解如下的凸二次规划问题

l

(1.13)

选取适当的从欧氏空间到 Hilbert 空间的变换 x ? ? ? x ? ,以及惩罚参数 C>0。
l 1 l y y ? ? ? x ? ? x ? ?j ? i j i j ? i? ? j? ? 2 i , j ?1 j ?1

min
?

?

?

s.t.

? y?
i ?1 i
T

l

i

?0

(1.14)

0 ? ? i ? C , i ? 1,L , l
得解 ? * ? ??1* ,L , ? l* ? ,选取 ? * j ? ? 0, C ? ,得到
b ? yi ? ? yi?i* ? ? xi ? ? ? ? x j ?
* i ?1 l

?

?
l i ?1

(1.15)

从而得到决策函数 f ? x ? ? sgn ? g ? x ?? ,其中 g ? x ? ? ? yi ai* ?? ? xi ? ? ? ? x ? ? ? b* 。

1.3 核函数
我们在分析非线性支持向量机思想时, 很容易发现变换 ? 在算法中的作用完 全是通过内积 ? ? xi ? ? ? ? x j ? 和 ?? ? xi ? ?? ? x ?? 实现的,换句话说,变换 ? 总是以内 积的形式出现, 因此函数 K ? x, x '? ? ?? ? x ? ?? ? x '?? 是很重要的, 只要选定了该函数, 则并不需要考虑变换 ? 而仍然可以得到决策函数。我们称这个函数为核函数。将 核函数引入支持向量机之后,可以将式(1.14)改为如下的最优化问题
l 1 l yi y j? i? j K ? xi , x j ? ? ?? j ? 2 i , j ?1 j ?1

?

?

min
?

s.t.

? y?
i ?1 i
l

l

i

?0

(1.16)

0 ? ? i ? C , i ? 1,L , l
得到的决策函数中 g ? x ? ? ? yi ai* K ? xi , x ? ? b*
i ?1

这就是标准支持向量机(SVM) ,我们所讨论的支持向量机就是这个模型。 核函数的选取是支持向量机算法中十分重要的内容,只要满足 mercer 条件 的函数均可以作为核函数使用,目前使用比较多的核函数有: 线性核函数:K(x,y) = x*y;

径向基核函数:K(x,y) = exp{?

| x ? y |2

?2

};

2 支持向量机分类算法的实现
支持向量机算法是在训练样本的特征空间求取能把两类样本没有错误分开的最 大间隔超平面, 在数学上表示为一个凸二次规划的问题。也可以说算法求解的主 要内容是通过求解二次规划(QP)问题, 这个优化问题的求解是支持向量机算法的 核心, 可以说支持向量机的算法就得到了实现。前面所述支持向量机算法可以表 示 为 在 式 (2.2) 和 式 (2.3) 的 约 束 下 求 式 (2.1) 取 最 小 值 时 的 拉 格 朗 日 乘 子

A ? (?1, ?2 ....., ?n )T 为训练样本的个数。
Q( A) ? ? AT I ? 1/ 2 AT DA
0? A?C

(2.1) (2.2) (2.3)

AT y ? 0
其中:

A ? (?1, ?2 ,...., ?n )T 为 n 元 列 向 量 , 是 要 求 的 拉 格 朗 日 乘 子 ;

Dij ? yi y j K ( xi , x j ) 是一个正定矩阵; y ? ( y1 , y2 ,... yn )T 是样本的所属类别,由 1
或一 1 组成的列向量;xi 为训练样本。可以看出,求解支持向量机就是求解上 述的一个二次规划问题,求解后得到拉格朗日乘子 A ? (?1 , ?2 ,...., ?n )T ,也就求 得了最大间隔超平面。 求解这个二次规划问题需要深厚的数学功底数值计算方面 的技能,在主流程序语言中实现算法又需要专业的计算机程序设计的知识。 在 MATLAB 环境下求解这一问题会变得非常简单, 这得益于 MATLAB 软件强大的优 化工具箱,提供了一个求解二次规划的函数,可以直接调用。二次规划问题 (quadratic programming)的标准形式为: 1 min f ' x ? x ' Hx 2 Ax ? b sub.to Aeqx=beq
lb ? x ? ub

其中,H、A、Aeq 为矩阵;f、b、beq、lb、ub、x 为向量,其它形式的二次规划 问题都可转化为标准形式。 函数 quadprog 格式如下: [x,fva1]=quadprog(H,f,A,b,Aeq,beq,lb,ub,x0) 其中 H、f、A、b、Aeq、beq、lb、ub 为标准形中的参数;x 为求解得到的最优

值,也就是二次规划的解析解;lb、ub 分别为 x 的下界与上界,满足不等式约
b ? x ? ub ;Aeq、beq 满足等约束条件 Aeq*x=beq;x0 为设置的初值,这个值是

人为赋予 x 的值,一般 x 为零;fval 为目标函数最小值,可以看出,支持向量 机算法是一个标准的二次规划问题; H ? Dij ? yi y j K ( xi , x j ) ,根据训练样本数据 求出;f = -1;支持向量机算法没形式的不等式约束条件,所以 A、b 为空矩阵;

Aeq ? AT y ,beq=Y,实现 A Y=0 等式约束;Lb=0、ub=C,实现 0 ? A ? C 不等
式约束;x0=0,赋予 A 的初始值为零。样本数据已知,c 是人工赋于的值。

3.实例说明及实验结果
3.1实验程序代码 %定义核函数及相关参数 nu = 0.2; % nu -> (0,1] 在支持向量数与错分样本数之间进行折 衷 ker = struct('type','linear'); % 构造两类训练样本 n = 50; randn('state',6); x1 = randn(2,n); y1 = ones(1,n); x2 = 5+randn(2,n); y2 = -ones(1,n); figure; plot(x1(1,:),x1(2,:),'bx',x2(1,:),x2(2,:),'k.'); axis([-3 8 -3 8]); title('C-SVC') hold on; X = [x1,x2]; %训练样本,d*n的矩阵,n为样本个数,d为样本维数 Y = [y1,y2]; % 训练目标,1*n的矩阵,n为样本个数,值为+1或-1 % ------------------------------------------------------------% % 训练支持向量机 tic svm = svmTrain('svc_nu',X,Y,ker,nu); t_train = toc %寻找支持向量? a = svm.a; epsilon = 1e-8; %如果小于此值则认为是0 i_sv = find(abs(a)>epsilon); %支持向量下标 plot(X(1,i_sv),X(2,i_sv),'ro');

% ------------------------------------------------------------% % 测试输出 [x1,x2] = meshgrid(-2:0.1:7,-2:0.1:7); [rows,cols] = size(x1); nt = rows*cols; % ?测试样本数 Xt = [reshape(x1,1,nt);reshape(x2,1,nt)]; tic Yd = svmSim(svm,Xt); t_sim = toc Yd = reshape(Yd,rows,cols); contour(x1,x2,Yd,[0 0],'m'); hold off; 3.2 实验结果

% 测试输出

%分类面


赞助商链接
相关文章:
模式识别结课论文
模式识别结课论文 题学专姓学 目:模式识别中基于支持向量机算法分析 院: 业: 名: 号: 电气工程与信息工程学院 电气工程 指导教师: 教授 1 支持向量机支持...
模式识别结课论文
模式识别结课论文_其它_高等教育_教育专区。大学课程 模式识别结课论文 模式识别论文 题目 基于 Matlab 的语音识别系统 Title: the voice recognition system based ...
模式识别课程论文
模式识别课程论文 - 模式识别中的贝叶斯决策 学专班 院业级 信息电子技术 电子信息工程 级1班 学籍号姓名 指导教师 信息电子技术学院 2016 年 10 月 25...
模式识别期末论文_图文
模式识别期末论文_理学_高等教育_教育专区。对模式识别应用领域的认识 摘要自 20...- 10 - 火电厂自动化专题结课作业对模式识别应用领域的认识 班级: 自动化 ...
模式识别与人工智能结课论文
模式识别与人工智能结课论文_教育学/心理学_人文社科_专业资料 暂无评价|0人阅读|0次下载|举报文档 模式识别与人工智能结课论文_教育学/心理学_人文社科_专业...
模式识别-课程论文模板
模式识别-课程论文模板_实习总结_总结/汇报_实用文档。模式识别课程论文模板,大家可以参考 基于神经网络的模拟电路故障诊断方法研究 XXX (xxx学院 信息与通信工程学院...
模式识别人工智能论文
模式识别人工智能论文_电脑基础知识_IT/计算机_专业资料。浅谈人工智能与模式识别...四、心得体会很荣幸能在本学期学习模式识别这门课程, 这是一门很实用并且有着...
模式识别论文
模式识别与智能系统结课论文 姓名:郑辉 班级:控制理论与控制工程4班 学号:S11081101017 基于模糊神经网络控制 的异步电动机软起动的探讨摘 要:软起动采用三相交流调...
模式识别论文
模式识别期末论文 7页 1下载券 模式识别课程论文 11页 免费 模式识别方面的论文...基于MATLAB 的 REF 神经网络的模式识别一. 神经网络介绍神经网络具有并行处理能力...
智能视频分析结课论文
智能视频分析技术课程论文 中国传媒大学 2014~2015 学年第 1 学期 课程 智能视频分析技术 题学班 目号级 人工智能和模式识别的结合运用 刘晶晶 201110013208 数字...
更多相关标签: