loading沈阳理工大学数字图像处理与分析课程设计
1 设计目的
Vapnik等人在多年研究统计学习理论基础上对线性分类器提出了另一种设计最佳准则。其原理也从线性可分说起，然后扩展到线性不可分的情况。甚至扩展到使用非线性函数中去，这种分类器被称为支持向量机（Support Vector Machine，简称SVM）。支持向量机的提出有很深的理论背景。 支持向量机方法是在近年来提出的一种新方法。
SVM的主要思想可以概括为两点：⑴它是针对线性可分情况进行分析，对于线性不可分的情况，通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分，从而 使得高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可能；
2 设计方案
2.1 SVM简介
SVM方法是通过一个非线性映射p，把样本空间映射到一个高维乃至无穷维的特征空间中（Hilbert空间），使得在原来的样本空间中非线性可分的问题转化为在特征空间中的线性可分的问题．简单地说，就是升维和线性化．升维，就是把样本向高维空间做映射，一般情况下这会增加计算的复杂性，甚至会引起“维数灾难”，因而人们很少问津．但是作为分类、回归等问题来说，很可能在低维样本空间无法线性处理的样本集，在高维特征空间中却可以通过一个线性超平面实现线性划分（或回归）．一般的升维都会带来计算的复杂化，SVM方法巧妙地解决了这个难题：应用核函数的展开定理，就不需要知道非线性映射的显式表达式；由于是在高维特征空间中建立线性学习机，所以与线性模型相比，不但几乎不增加计算的复杂性，而且在某种程度上避免了“维数灾难”．这一切要归功于核函数的展开和计算理论．
选择不同的核函数，可以生成不同的SVM，常用的核函数有以下4种： ⑴线性核函数K(x,y)=x·y；
⑵多项式核函数K(x,y)=[(x·y)+1]^d； ⑶径向基函数K(x,y)=exp(-|x-y|^2/d^2）
⑷二层神经网络核函数K(x,y)=tanh(a(x·y)+b）．
2.2 SVM的基本原理与过程
SVM的主要思想可以概括为两点：⑴它是针对线性可分情况进行分析，对于线性不可分的情况，通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分，从而 使得高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可能； 举例来说：
1
沈阳理工大学数字图像处理与分析课程设计
如右图：
图2.1
将1维的“线性不可分”上升到2维后就成为线性可分了。
⑵它基于结构风险最小化理论之上在特征空间中建构最优分割超平面，
图2.2
使得学习器得到全局最优化，并且在整个样本空间的期望风险以某个概率满足一定上界。
在学习这种方法时，首先要弄清楚这种方法考虑问题的特点，这就要从线性可分的最简单情况讨论起，在没有弄懂其原理之前，不要急于学习线性不可分等较复杂的情况，支持向量机在设计时，需要用到条件极值问题的求解，因此需用拉格朗日乘子理论，但对多数人来说，以前学到的或常用的是约束条件为等式表示的方式，但在此要用到以不等式作为必须满足的条件，此时只要了解拉格朗日理论的有关结论就行。
⑴SVM学习问题可以表示为凸优化问题，因此可以利用已知的有效算法发现目标函数的全局最小值。而其他分类方法（如基于规则的分类器和人工神经网络）都采用一种基于贪心学习的策略来搜索假设空间，这种方法一般只能获得局部最优解。
⑵SVM通过最大化决策边界的边缘来控制模型的能力。尽管如此，用户必须提供其他参数，如使用核函数类型和引入松弛变量等。
⑶通过对数据中每个分类属性引入一个哑变量，SVM可以应用于分类数据。 ⑷SVM一般只能用在二类问题，对于多类问题效果不好。
3 具体设计内容
3.1 支持向量机分类的基本原理
支持向量机是基于线性划分的。但是可以想象，并非所有数据都可以线性划分。如二维空间中的两个类别的点可能需要一条曲线来划分它们的边界。在高维空间中，它是一种线性划分，而在原有的数据空间中，它是一种非线性划分。
2
沈阳理工大学数字图像处理与分析课程设计
但是讨论支持向量机的算法时，并不是讨论如何定义低维到高维空间的映射算法（该算法隐含在其“核函数”中），而是从最优化问题（寻找某个目标的最优解）的角度来考虑的。
3.1.1问题分析
我们解决一个问题时，如果将该问题表示为一个函数f(x)，最优化问题就是求该函数的极小值。通过高等数学知识可以知道，如果该函数连续可导，就可以通过求导，计算导数＝0的点，来求出其极值。但现实问题中，如果f(x)不是连续可导的，就不能用这种方法了。最优化问题就是讨论这种情况。 求最优解的问题可以分为两种：（1）无约束最优问题；（2）有约束最优问题。 无约束最优算法可以表达为：minf(x)。可以用数值计算方法中的牛顿法、
x最速梯度下降法等，通过多次循环，求得一次近似的最优解。 有约束问题，一般表达为：
n?minf(x)x?E?x ?t?i(x)?0i?{1,2,,m}??s..
线性可分的二分类问题是指：原数据可以用一条直线（如果数据只有二维）或一个超平面划分开。用一个多维空间中的超平面将数据分隔为两个类有三种基本方法： 1）平方最近点法：用两类点中最近的两点连线的平分线作为分类线（面） 2）最大间隔法：求分类面，使分类边界的间隔最大。分类边界是值从分类面分别向两个类的点平移，直到遇到第一个数据点。两个类的分类边界的距离就是分类间隔。
分类平面表示为：(w?x)?b?0。注意，x是多维向量。分类间隔的倒数为：
12w。所以该最优化问题表达为： 2minw,bs..t12w,2yi((w?xi)?b)?1)?1,i?1,
,l1
min ||w||2, (1.2.1)w,b 2 ?1,,l (1.2.2)s.t. yi((w?xi)?b)?1,i 其中的约束是指：要求各数据点(xi,yi)到分类面的距离大于等于1。其中，yi 为数据的分类。
3.1.2线性支持向量分类机
3
沈阳理工大学数字图像处理与分析课程设计
分类面：(w?x)?b?0.要求：min?l1llyiyj?i?j(xi?xj)???j,??2i?1j?1j?1s..t?y?ii?1l
i?0?i?0
据此求出?*（最优解，算法另述）后：
w??yiaixi，b?yj??yi?i(xi?xj)
***i?1i?1ll 说明：线性支持向量机是基于最大间隔法的。该问题是一个二次规划问
题得到上述的分类优化问题。需要注意的是，该问题仍然是一个有约束的最优化问题。
（1）线性不可分问题
基本思路：由于样本线性不可分，原来对间隔的要求不能达到。引入松弛变量ξi，使约束条件弱化为：yi((w?xi)?b)?1)?1??i。但是，我们仍然希望该松弛变量ξi最小化（如果ξi＝0，则就是原线性硬间隔分类机）。于是，在优化目标函数中使用惩罚参数C来引入对ξi最小化的目标。这样，该分类机的模型为：
分类面：(w?x)?b?0.要求：l12minw?C??i,w,b2i?1s..tyi((w?xi)?b)?1)?1??i,i?1,
,l以此为原问题，其对偶问题为：
l1ll??j,??yiyj?i?j(xi?xj)???min?2i?1j?1j?1?l?tyi?i?0?s..?i?1? ?0??i?C??w??yiaixi,**i?1lb?yj??yi?i(xi?xj)*i?1l(2)非线性硬间隔分类机
基本思路是：可以将低维空间中的曲线（曲面）映射为高维空间中的直线或
x???(x)，平面。数据经这种映射后，在高维空间中是线性可分的。设映射为：
则高维空间中的线性支持向量机模型为：
4