报告

沈阳理工大学数字图像处理与分析课程设计

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

沈阳理工大学数字图像处理与分析课程设计

分类面：(w?x)?b?0.要求：min?l1llyiyj?i?j(?(xi)??(xj))???j,??2i?1j?1j?1s..t?y?ii?1l

i?00??i?C需要注意的是，由于数据被映射到高维空间，?(xi)??(xj)的计算量比xi?xj大得多。此时引入了所谓“核函数”：

K(xi,xj)??(xi)??(xj)

由上式可见，核函数的作用是，在将x映射到高维空间的同时，也计算了两个数据的在高维空间的内积，使计算量回归到xi?xj的量级。

（3）非线性软间隔分类机（C-支持向量分类机）

非线性硬间隔分类机虽然将训练数据映射到高维空间中，但核函数的选择只有几种，它们并不能保证在任何情况下都可以将训练数据映射到足够高的维度，以使它们成为线性可分的。因此，有理由在此基础上引入线性软间隔分类机中的松弛变量。这样，原问题为：

映射： T?{(x1,y1),其中： xi??(xi)(xl,yl)}，

分类面：(w?x)?b?0. minw,bl12w?C??i,2i?1s..tyi((w?xi)?b)?1)?1??i,i?1,,l其对偶问题为：

l1ll?yiyj?i?jK(xi,xj)???j,???min?2i?1j?1j?1?l?tyi?i?0?s..?i?1??0??i?C??b?yj??yi?i*K(xi,xj)*i?1l

??f(x)?sgn???i*yiK(x,xi)?b*???这种支持向量机是最常用的。

（4）ν-支持向量机分类机

5

沈阳理工大学数字图像处理与分析课程设计

C－支持向量机中的惩罚参数C难以选取。选择大的C是强调最小化训练错误；选择较小的C是强调最大化分类间隔。 ν-支持向量机分类机的原始问题：

121l minw??????i,w,?,b,?2li?1s..tyi((w?xi)?b)????i, ?i?0, i?1, ??0其对偶问题为：

1ll?yiyj?i?jK(xi,xj),???min?2i?1j?1?l?tyi?i?0?s..??i?1?1?0??i??l?l??i????i?1?1l**b????iyi?K(xi,xj)?K(xi,xk)?,2i?1?l*?f(x)?sgn???iyiK(x,xi)?b*??i?1?,lj一个正类样本，k一个负类样本

3.2多分类问题

（1） 一类对余类方法：

建立将一类与其余类分开的支持向量机。如，训练数据有M类，则需要建立M个支持向量机。识别x分类时，选择gj(x)最大的分类：

fj(x)?sgn(gj(x)),j?[1,M]g(x)???iyiK(x,xi)?bjji?1lj

或者：计算两个最大的g的差，作为置信度。如果Δg>θ，则选择g最大的类；反之，拒绝分类。

（2） 成对分类

建立M个类中任意两个类之间的分类器，共M(M-1)/2个分类器。识别x分类时采用投票方法，得票最多的类为x的最终分类。

2、支持向量模型的求解

从上述各种支持向量机的对偶问题表示可以看出，它们都是约束优化问题。即在一定的约束下，求解最优（极小）。

约束优化问题一般都转换为无约束优化问题进行求解。光滑无约束问题的求解方法一般有梯度下降法、牛顿法等。非光滑无约束问题可以转换为近似的光滑无约束问题。

6

沈阳理工大学数字图像处理与分析课程设计

3、整理svmlib

（1） 输入、输出方便（数据格式）； （2） 可以在各种情况下使用（库） （3） 方便修改svm算法

4 源代码

4.1 非线性svm 源代码

clear;%清屏 clc;

X =load('data.txt');

n = length(X);%总样本数量 y = X(:,4);%类别标志 X = X(:,1:3);

TOL = 0.0001;%精度要求

C = 1;%参数，对损失函数的权重 b = 0;%初始设置截距b

Wold = 0;%未更新a时的W(a) Wnew = 0;%更新a后的W(a)

for i = 1 : 50%设置类别标志为1或者-1 y(i) = -1; end

a = zeros(n,1);%参数a

for i = 1 : n%随机初始化a,a属于[0,C] a(i) = 0.2; end

%为简化计算，减少重复计算进行的计算 K = ones(n,n);

for i = 1 :n%求出K矩阵，便于之后的计算 for j = 1 : n

K(i,j) = k(X(i,:),X(j,:)); end end

sum = zeros(n,1);%中间变量，便于之后的计算，sum(k)=sigma a(i)*y(i)*K(k,i); for k = 1 : n for i = 1 : n

sum(k) = sum(k) + a(i) * y(i) * K(i,k); end end

7

沈阳理工大学数字图像处理与分析课程设计

while 1%迭代过程

%启发式选点

n1 = 1;%初始化，n1,n2代表选择的2个点 n2 = 2;

%n1按照第一个违反KKT条件的点选择 while n1 <= n

if y(n1) * (sum(n1) + b) == 1 && a(n1) >= C && a(n1) <= 0 break; end

if y(n1) * (sum(n1) + b) > 1 && a(n1) ~= 0 break; end

if y(n1) * (sum(n1) + b) < 1 && a(n1) ~=C break; end

n1 = n1 + 1; end

%n2按照最大化|E1-E2|的原则选取 E1 = 0; E2 = 0;

maxDiff = 0;%假设的最大误差

E1 = sum(n1) + b - y(n1);%n1的误差 for i = 1 : n

tempSum = sum(i) + b - y(i); if abs(E1 - tempSum)> maxDiff maxDiff = abs(E1 - tempSum); n2 = i;

E2 = tempSum; end end

%以下进行更新 a1old = a(n1); a2old = a(n2);

KK = K(n1,n1) + K(n2,n2) - 2*K(n1,n2);

a2new = a2old + y(n2) *(E1 - E2) / KK;%计算新的a2 ￠必须满足约束条件 S = y(n1) * y(n2); if S == -1

U = max(0,a2old - a1old); V = min(C,C - a1old + a2old); else

8

沈阳理工大学数字图像处理与分析课程设计

U = max(0,a1old + a2old - C); V = min(C,a1old + a2old); end

if a2new > V a2new = V; end

if a2new < U a2new = U; end

a1new = a1old + S * (a2old - a2new);%计算新的a1 a(n1) = a1new;%更新a a(n2) = a2new;

%更新部分值 sum = zeros(n,1); for k = 1 : n for i = 1 : n

sum(k) = sum(k) + a(i) * y(i) * K(i,k); end end

Wold = Wnew;

Wnew = 0;%更新a后的W(a) tempSum = 0;%临时变量 for i = 1 : n for j = 1 : n

tempSum= tempSum + y(i )*y(j)*a(i)*a(j)*K(i,j); end

Wnew= Wnew+ a(i); end

Wnew= Wnew - 0.5 * tempSum;

%以下更新b：通过找到某一个支持向量来计算 support = 1;%支持向量坐标初始化

while abs(a(support))< 1e-4 && support <= n support = support + 1; end

b = 1 / y(support) - sum(support); %判断停止条件

if abs(Wnew/ Wold - 1 ) <= TOL break; end end

%输出结果：包括原分类，辨别函数计算结果，svm分类结果 for i = 1 : n

fprintf('第%d点:原标号 ',i);

9

沈阳理工大学数字图像处理与分析课程设计

if i <= 50

fprintf('-1'); else

fprintf(' 1'); end

fprintf(' 判别函数值%f 分类结果',sum(i) + b); if abs(sum(i) + b - 1) < 0.5 fprintf('1\\n');

else if abs(sum(i) + b + 1) < 0.5 fprintf('-1\\n'); else

fprintf('归类错误\\n'); end end end

4.2 线性SVM源代码

stream = output stream to write to buffer = buffer of bytes to write to stream nbytes = number of bytes to write returns = number of bytes written to stream */

int write(FILE *stream, void *buffer, int nbytes) {

struct call_struct;

call_struct.type = FILE_SYSTEM; call_struct.subtype = BUFF_OUTPUT; call_struct.param1 = (long)stream; call_struct.param2 =(long)buffer; call_struct.param3=nbytes;

10

本文来源：https://www.bwwdw.com/article/rs27.html