数字图像处理与分析课程设计

《数字图像处理与分析课程设计》由会员分享，可在线阅读，更多相关《数字图像处理与分析课程设计（12页珍藏版）》请在金锄头文库上搜索。

1、沈阳理工大学数字图像处理与分析课程设计11 设计目的Vapnik 等人在多年研究统计学习理论基础上对线性分类器提出了另一种设计最佳准则。其原理也从线性可分说起，然后扩展到线性不可分的情况。甚至扩展 到使用非线性函数中去，这种分类器被称为支持向量机（Support Vector Machine，简称 SVM） 。支持向量机的提出有很深的理论背景。 支持向量机方法是在近年来提出的一种新方法。 SVM 的主要思想可以概括为两点：它是针对线性可分情况进行分析，对于线性不可分的情况，通过使用非线性映射算法将低维输入空间线性不可分的样本 转化为高维特征空间使其线性可分，从而 使得高维特征空间采用线性算法对

2、样 本的非线性特征进行线性分析成为可能；2 设计方案2.1 SVM 简介SVM 方法是通过一个非线性映射 p，把样本空间映射到一个高维乃至无穷维的特 征空间中（Hilbert 空间） ，使得在原来的样本空间中非线性可分的问题转化为 在特征空间中的线性可分的问题简单地说，就是升维和线性化升维，就是 把样本向高维空间做映射，一般情况下这会增加计算的复杂性，甚至会引起 “维数灾难” ，因而人们很少问津但是作为分类、回归等问题来说，很可能在 低维样本空间无法线性处理的样本集，在高维特征空间中却可以通过一个线性 超平面实现线性划分（或回归） 一般的升维都会带来计算的复杂化，SVM 方法 巧妙地解决了这个

3、难题：应用核函数的展开定理，就不需要知道非线性映射的 显式表达式；由于是在高维特征空间中建立线性学习机，所以与线性模型相比， 不但几乎不增加计算的复杂性，而且在某种程度上避免了“维数灾难” 这一切 要归功于核函数的展开和计算理论 选择不同的核函数，可以生成不同的 SVM，常用的核函数有以下 4 种： 线性核函数 K(x,y)=xy； 多项式核函数 K(x,y)=(xy)+1d； 径向基函数 K(x,y)=exp(-|x-y|2/d2） 二层神经网络核函数 K(x,y)=tanh(a(xy)+b） 2.2 SVM 的基本原理与过程SVM 的主要思想可以概括为两点：它是针对线性可分情况进行分析，对

4、于线 性不可分的情况，通过使用非线性映射算法将低维输入空间线性不可分的样本 转化为高维特征空间使其线性可分，从而 使得高维特征空间采用线性算法对样 本的非线性特征进行线性分析成为可能； 举例来说：沈阳理工大学数字图像处理与分析课程设计2如右图：图 2.1将 1 维的“线性不可分”上升到 2 维后就成为线性可分了。 它基于结构风险最小化理论之上在特征空间中建构最优分割超平面， 图 2.2使得学习器得到全局最优化，并且在整个样本空间的期望风险以某个概率满足 一定上界。 在学习这种方法时，首先要弄清楚这种方法考虑问题的特点，这就要从线性可 分的最简单情况讨论起，在没有弄懂其原理之前，不要急于学习线性

5、不可分等 较复杂的情况，支持向量机在设计时，需要用到条件极值问题的求解，因此需 用拉格朗日乘子理论，但对多数人来说，以前学到的或常用的是约束条件为等 式表示的方式，但在此要用到以不等式作为必须满足的条件，此时只要了解拉 格朗日理论的有关结论就行。 SVM 学习问题可以表示为凸优化问题，因此可以利用已知的有效算法发现目 标函数的全局最小值。而其他分类方法（如基于规则的分类器和人工神经网络） 都采用一种基于贪心学习的策略来搜索假设空间，这种方法一般只能获得局部 最优解。 SVM 通过最大化决策边界的边缘来控制模型的能力。尽管如此，用户必须提 供其他参数，如使用核函数类型和引入松弛变量等。 通过对数

6、据中每个分类属性引入一个哑变量，SVM 可以应用于分类数据。 SVM 一般只能用在二类问题，对于多类问题效果不好。3 具体设计内容3.1 支持向量机分类的基本原理支持向量机是基于线性划分的。但是可以想象，并非所有数据都可以线性划分。 如二维空间中的两个类别的点可能需要一条曲线来划分它们的边界。在高维空 间中，它是一种线性划分，而在原有的数据空间中，它是一种非线性划分。沈阳理工大学数字图像处理与分析课程设计3但是讨论支持向量机的算法时，并不是讨论如何定义低维到高维空间的映射算 法（该算法隐含在其“核函数”中） ，而是从最优化问题（寻找某个目标的最 优解）的角度来考虑的。3.1.1 问题分析我们解

7、决一个问题时，如果将该问题表示为一个函数 f(x)，最优化问题就 是求该函数的极小值。通过高等数学知识可以知道，如果该函数连续可导， 就可以通过求导，计算导数0 的点，来求出其极值。但现实问题中，如果 f(x)不是连续可导的，就不能用这种方法了。最优化问题就是讨论这种情况。求最优解的问题可以分为两种：（1）无约束最优问题；（2）有约束最优问 题。无约束最优算法可以表达为：。可以用数值计算方法中的牛顿法、min( ) xf x最速梯度下降法等，通过多次循环，求得一次近似的最优解。 有约束问题，一般表达为：min( ). .( )01,2, nxif xxEstximL线性可分的二分类问题是指：原

8、数据可以用一条直线（如果数据只有二维） 或一个超平面划分开。用一个多维空间中的超平面将数据分隔为两个类有三 种基本方法： 1）平方最近点法：用两类点中最近的两点连线的平分线作为分类线（面）2）最大间隔法：求分类面，使分类边界的间隔最大。分类边界是值从分 类面分别向两个类的点平移，直到遇到第一个数据点。两个类的分类边 界的距离就是分类间隔。分类平面表示为：。注意，x 是多维向量。分类间隔的()0w xb倒数为：。所以该最优化问题表达为：21 2w2,1min,2 . .() 1)1,1,w biiwstyw xbil L其中的约束是指：要求各数据点到分类面的距离大于等于( ,)iix y1。其中

9、，为数据的分类。iy3.1.2 线性支持向量分类机2,1min| , (1.2.1)2 s.t.()1,1, (1.2.2)w biiwyw xbil L沈阳理工大学数字图像处理与分析课程设计41111()0.1min(),2. .00lllijijijj ijjlii iiw xby yx xsty分类面：要求：据此求出（最优解，算法另述）后：*，*1liii iwy a x*1()ljiiij ibyyx x说明：线性支持向量机是基于最大间隔法的。该问题是一个二次规划问 题得到上述的分类优化问题。需要注意的是，该问题仍然是一个有约束的最 优化问题。 （1）线性不可分问题 基本思路：由于样本

10、线性不可分，原来对间隔的要求不能达到。引入松弛变量 i，使约束条件弱化为：。但是，我们仍然希望() 1)1iiiyw xb 该松弛变量 i最小化（如果 i0，则就是原线性硬间隔分类机） 。于是， 在优化目标函数中使用惩罚参数 C 来引入对 i最小化的目标。这样，该分 类机的模型为：2,1()0.1min,2 . .() 1)1,1,liw biiiiw xbwCstyw xbil L分类面：要求：以此为原问题，其对偶问题为：1111*111min(),2. .00,()lllijijijj ijjlii iilliiijiiij iiy yx xstyCwy a xbyyx x (2)非线性硬

11、间隔分类机 基本思路是：可以将低维空间中的曲线（曲面）映射为高维空间中的直线或 平面。数据经这种映射后，在高维空间中是线性可分的。设映射为：，则高维空间中的线性支持向量机模型为：( )xx 沈阳理工大学数字图像处理与分析课程设计51111()0.1min( ( )(),2. .00lllijijijj ijjlii iiw xby yxxstyC 分类面：要求：需要注意的是，由于数据被映射到高维空间，的计算量比( )()ijxx大得多。此时引入了所谓“核函数”：ijx x( ,)( )()ijijK x xxx由上式可见，核函数的作用是，在将 x 映射到高维空间的同时，也计算了两个数据的在高维

12、空间的内积，使计算量回归到的量级。ijx x（3）非线性软间隔分类机（C-支持向量分类机） 非线性硬间隔分类机虽然将训练数据映射到高维空间中，但核函数的选择只 有几种，它们并不能保证在任何情况下都可以将训练数据映射到足够高的维 度，以使它们成为线性可分的。因此，有理由在此基础上引入线性软间隔分 类机中的松弛变量。这样，原问题为：，112,1( ,),( ,)( )()0. 1min,2. .() 1)1,1,lliili w biiiiTx yx yxxw xbwCstyw xbil %L% %L映射： 其中：分类面：其对偶问题为：1111*1*1min( ,),2. .00(,)( )sgn

13、( ,)lllijijijj ijjlii iiljiiij iiiiy yK x xstyCbyyK xxf xy K x xb 这种支持向量机是最常用的。 （4）-支持向量机分类机沈阳理工大学数字图像处理与分析课程设计6C支持向量机中的惩罚参数 C 难以选取。选择大的 C 是强调最小化训练错 误；选择较小的 C 是强调最大化分类间隔。 -支持向量机分类机的原始问题：2, , ,111min,2 . .(),0, 1,0liwbiiiiiwl styw xbil%L其对偶问题为：1111*1*11min( ,),2. .0101(,)(,) ,2( )sgn( ,)llijijij ijli

14、i iili iliiijik iliii iy yK x xstylbyK xxK xxjkf xy K x xb 一个正类样本，一个负类样本3.23.2 多分类问题多分类问题（1） 一类对余类方法： 建立将一类与其余类分开的支持向量机。如，训练数据有 M 类，则 需要建立 M 个支持向量机。识别 x 分类时，选择 gj(x)最大的分类：1( )sgn( ),1,( )( ,)jjl jjj iii ifxgxjMgxy K x xb或者：计算两个最大的 g 的差，作为置信度。如果 g，则选择 g 最大的类；反之，拒绝分类。 （2） 成对分类 建立 M 个类中任意两个类之间的分类器，共 M(

15、M-1)/2 个分类器。识 别 x 分类时采用投票方法，得票最多的类为 x 的最终分类。 2、支持向量模型的求解 从上述各种支持向量机的对偶问题表示可以看出，它们都是约束优化问题。 即在一定的约束下，求解最优（极小） 。 约束优化问题一般都转换为无约束优化问题进行求解。光滑无约束问题的求 解方法一般有梯度下降法、牛顿法等。非光滑无约束问题可以转换为近似的 光滑无约束问题。沈阳理工大学数字图像处理与分析课程设计73、整理 svmlib （1） 输入、输出方便（数据格式） ； （2） 可以在各种情况下使用（库） （3） 方便修改 svm 算法4 源代码4.1 非线性 svm 源代码clear;%清屏 clc; X =load(data.txt); n =