支持向量机matlab实例及理论_20131201

支持向量机matlab分类实例及理论

线性支持向量机可对线性可分的样本群进行分类，此时不需要借助于核函数就可较为理想地解决问题。非线性支持向量机将低维的非线性分类问题转化为高维的线性分类问题，然后采用线性支持向量机的求解方法求解。此时需要借助于核函数，避免线性分类问题转化为非线性分类问题时出现的维数爆炸难题，从而避免由于维数太多而无法进行求解。

第O层：Matlab的SVM函数求解分类问题实例

0.1Linear classification(线性分类)

%Two Dimension Linear-SVM Problem, Two Class and Separable Situation %Method from Christopher J. C. Burges:

%"A Tutorial on Support Vector Machines for Pattern Recognition", page 9

%Optimizing ||W|| directly:

% Objective: min "f(A)=||W||" , p8/line26

% Subject to: yi*(xi*W+b)-1>=0, function (12);

clear all;

close all

clc;

sp=[3,7; 6,6; 4,6;5,6.5] % positive sample points

nsp=size(sp);

sn=[1,2; 3,5;7,3;3,4;6,2.7] % negative sample points

nsn=size(sn)

sd=[sp;sn]

lsd=[true true true true false false false false false]

Y = nominal(lsd)

figure(1);

subplot(1,2,1)

plot(sp(1:nsp,1),sp(1:nsp,2),'m+');

hold on

plot(sn(1:nsn,1),sn(1:nsn,2),'c*');

subplot(1,2,2)

svmStruct = svmtrain(sd,Y,'showplot',true);

0.2 NonLinear classification（非线性分类）（平方核函数）

clear all;

close all

clc;

sp=[3,7; 6,6; 4,6; 5,6.5] % positive sample points

nsp=size(sp);

sn=[1,2; 3,5; 7,3; 3,4; 6,2.7; 4,3;2,7] % negative sample points

nsn=size(sn)

sd=[sp;sn]

lsd=[true true true true false false false false false false false]

Y = nominal(lsd)

figure(1);

subplot(1,2,1)

plot(sp(1:nsp,1),sp(1:nsp,2),'m+');

hold on

plot(sn(1:nsn,1),sn(1:nsn,2),'c*');

subplot(1,2,2)

% svmStruct = svmtrain(sd,Y,'Kernel_Function','linear',

'showplot',true);

svmStruct = svmtrain(sd,Y,'Kernel_Function','quadratic',

'showplot',true);

% use the trained svm (svmStruct) to classify the data

RD=svmclassify(svmStruct,sd,'showplot',true)

% RD is the classification result vector

0.3 Gaussian Kernal Classification（高斯核函数分类）

clear all;

close all

clc;

sp=[5,4.5;3,7; 6,6; 4,6; 5,6.5] % positive sample points

nsp=size(sp);

sn=[1,2; 3,5; 7,3; 3,4; 6,2.7; 4,3;2,7] % negative sample points

nsn=size(sn)

sd=[sp;sn]

lsd=[true true true true true false false false false false false false] Y = nominal(lsd)

figure(1);

subplot(1,2,1)

plot(sp(1:nsp,1),sp(1:nsp,2),'m+');

hold on

plot(sn(1:nsn,1),sn(1:nsn,2),'c*');

subplot(1,2,2)

svmStruct =

svmtrain(sd,Y,'Kernel_Function','rbf','rbf_sigma',0.6,'method','SMO', 'showplot',true);

% svmStruct = svmtrain(sd,Y,'Kernel_Function','quadratic',

'showplot',true);

% use the trained svm (svmStruct) to classify the data

RD=svmclassify(svmStruct,sd,'showplot',true)

% RD is the classification result vector

svmtrain(sd,Y,'Kernel_Function','rbf','rbf_sigma',0.2,'method','SM O','showplot',true);

0.4 Svmtrain Function

svmtrain Train a support vector machine classifier

SVMSTRUCT = svmtrain(TRAINING, Y) trains a support vector machine (SVM) classifier on data taken from two groups. TRAINING is a numeric matrix of predictor data. Rows of TRAINING correspond to observations; columns correspond to features. Y is a column vector that contains the known

class labels for TRAINING. Y is a grouping variable, i.e., it can be a categorical, numeric, or logical vector; a cell vector of strings; or a character matrix with each row representing a class label (see help for groupingvariable). Each element of Y specifies the group the corresponding row of TRAINING belongs to. TRAINING and Y must have the

same number of rows. SVMSTRUCT contains information about the trained classifier, including the support vectors, that is used by SVMCLASSIFY for classification. svmtrain treats NaNs, empty strings or 'undefined' values as missing values and ignores the corresponding rows in TRAINING and Y.

SVMSTRUCT = svmtrain(TRAINING, Y, 'PARAM1',val1, 'PARAM2',val2, ...) specifies one or more of the following name/value pairs:

Name Value

'kernel_function' A string or a function handle specifying the

kernel function used to represent the dot

product in a new space. The value can be one of the following:

'linear' - Linear kernel or dot product

(default). In this case, svmtrain

finds the optimal separating plane in the original space.

'quadratic' - Quadratic kernel

'p olynomial' - Polynomial kernel with default

order 3. To specify another order, use the 'polyorder' argument.

'rbf' - Gaussian Radial Basis Function

with default scaling factor(比例因子)

1. Tospecify another scaling factor, use the 'rbf_sigma' argument.

（多元感知核函数）'mlp' - Multilayer Perceptron kernel (MLP)

with default weight 1 and default

bias -1. To specify another weight or bias, use the 'mlp_params' argument.

function - A kernel function specified using

@(for example @KFUN), or an

anonymous function. A kernel

function must be of the form

function K = KFUN(U, V)

The returned value, K, is a matrix of size M-by-N, where M and N are

the number of rows in U and V

respectively.

'rbf_sigma' A positive number specifying the scaling factorin the

Gaussian radial basis function

kernel.Default is 1.

'polyorder' A positive integer specifying the order of the

polynomial kernel. Default is 3.

'mlp_params' A vector [P1 P2] specifying the

parameters of MLPkernel. The MLP

kernel takes the form: K =

tanh(P1*U*V' + P2),where P1 > 0 and

P2 < 0. Default is [1,-1].

'method' A string specifying the method used to find the

separating hyperplane. Choices are:

'SMO' - Sequential Minimal Optimization (SMO)

method (default). It implements the L1

soft-margin SVM classifier.

'QP' - Quadratic programming (requires an（需要一

个优化工具箱许可）Optimization Toolbox

license). It

implements the L2 soft-margin SVM

classifier. Method 'QP' doesn't scale

well for TRAINING with large number of

observations.

'LS' - Least-squares method. It implements the L2 soft-margin SVM classifier.

'options' Options structure created using either STATSET or OPTIMSET.

* When you set 'method' to 'SMO' (default),

create the options structure using STATSET.

Applicable options:

'Display' Level of display output. Choices

are 'off' (the default), 'iter', and

'final'. Value 'iter' reports every

500 iterations.

'MaxIter' A positive integer specifying the

maximum number of iterations allowed. Default is 15000 for method 'SMO'.

* When you set method to 'QP', create the

options structure using OPTIMSET. For details of applicable options choices, see QUADPROG

options. SVM uses a convex quadratic program, so you can choose the 'interior-point-convex' algorithm in QUADPROG.

'tolkkt' A positive scalar that specifies the tolerance

with which the Karush-Kuhn-Tucker (KKT) conditions are checked for method 'SMO'. Default is

1.0000e-003.

'kktviolationlevel' A scalar specifying the fraction of observations that are allowed to violate the KKT conditions for method 'SMO'. Setting this value to be positive helps the algorithm to converge faster if it is fluctuating near a good solution. Default is 0.

'kernelcachelimit' A positive scalar S specifying the size of the kernel matrix cache for method 'SMO'. The

algorithm keeps a matrix with up to S * S

double-precision numbers in memory. Default is

5000. When the number of points in TRAINING

exceeds S, the SMO method slows down. It's

recommended to set S as large as your system

permits.

'boxconstraint'The box constraint C for the soft margin. C can be

a positive numeric scalar or a vector of positive numbers with the number of elements equal to the number of rows in TRAINING.

Default is 1.

* If C is a scalar, it is automatically rescaled by N/(2*N1) for the observations of group one, and by N/(2*N2) for the observations of group two, where N1 is the number of observations in group one, N2 is the number of observations in group two. The rescaling is done to take into account unbalanced groups, i.e., when N1 and N2 are different.

* If C is a vector, then each element of C

specifies the box constraint for the

corresponding observation.

'autoscale' A logical value specifying whether or not to

shift and scale the data points before training. When the value is true, the columns of TRAINING are shifted and scaled to have zero mean unit

variance. Default is true.

'showplot' A logical value specifying whether or not to show a plot. When the value is true, svmtrain creates a plot of the grouped data and the separating line

for the classifier, when using data with 2

features (columns). Default is false.

SVMSTRUCT is a structure having the following properties:

SupportVectors Matrix of data points with each row corresponding to a support vector.

Note: when 'autoscale' is false, this field

contains original support vectors in TRAINING.

When 'autoscale' is true, this field contains

shifted and scaled vectors from TRAINING.

Alpha Vector of Lagrange multipliers for the support

vectors. The sign is positive for support vectors belonging to the first group and negative for

support vectors belonging to the second group. Bias Intercept of the hyperplane that separates

the two groups.

Note: when 'autoscale' is false, this field

corresponds to the original data points in

TRAINING. When 'autoscale' is true, this field

corresponds to shifted and scaled data points. KernelFunction The function handle of kernel function used. KernelFunctionArgs Cell array containing the additional arguments

for the kernel function.

GroupNames A column vector that contains the known

class labels for TRAINING. Y is a grouping

variable (see help for groupingvariable). SupportVectorIndices A column vector indicating the indices of support vectors.

ScaleData This field contains information about auto-scale. When 'autoscale' is false, it is empty. When

'autoscale' is set to true, it is a structure

containing two fields:

shift - A row vector containing the negative of the mean across all observations in TRAINING.

scaleFactor - A row vector whose value is

1./STD(TRAINING).

FigureHandles A vector of figure handles created by svmtrain

when 'showplot' argument is TRUE.

Example:

% Load the data and select features for classification

load fisheriris

X = [meas(:,1), meas(:,2)];

% Extract the Setosa class

Y = nominal(ismember(species,'setosa'));

% Randomly partitions observations into a training set and a test % set using stratified holdout

P = cvpartition(Y,'Holdout',0.20);

% Use a linear support vector machine classifier

svmStruct =

svmtrain(X(P.training,:),Y(P.training),'showplot',true);

C = svmclassify(svmStruct,X(P.test,:),'showplot',true);

errRate = sum(Y(P.test)~= C)/P.TestSize %mis-classification rate conMat = confusionmat(Y(P.test),C) % the con

第一层、了解SVM

1.0、什么是支持向量机SVM

要明白什么是SVM，便得从分类说起。

分类作为数据挖掘领域中一项非常重要的任务，它的目的是学会一个分类函数或分类模型(或者叫做分类器)，而支持向量机本身便是一种监督式学习的方法(至于具体什么是监督学习与非监督学习，请参见此系列Machine L&Data Mining第一篇)，它广泛的应用于统计分类以及回归分析中。

支持向量机(SVM)是90年代中期发展起来的基于统计学习理论的一种机器学习方法，通过寻求结构化风险最小来提高学习机泛化能力，实现经验风险和置信范围的最小化，从而达到在统计样本量较少的情况下，亦能获得良好统计规律的目的。

1.1、线性分类

OK，在讲SVM之前，咱们必须先弄清楚一个概念：线性分类器(也可以叫做感知机，这里的机表示的是一种算法，本文第三部分、证明SVM中会详细阐述)。

1.1.1、分类标准

这里我们考虑的是一个两类的分类问题，数据点用x来表示，这是一个n维向量，w^T中的T

代表转置，而类别用y来表示，可以取 1 或者-1 ，分别代表两个不同的类。一个线性分类器就是要在n维的数据空间中找到一个超平面，其方程可以表示为：

上面给出了线性分类的定义描述，但或许读者没有想过：为何用y取1 或者-1来表示两个不同的类别呢？其实，这个1或-1的分类标准起源于logistic回归，为了完整和过渡的自然性，咱们就再来看看这个logistic回归。

1.1.2、1或-1分类标准的起源：logistic回归

Logistic回归目的是从特征学习出一个0/1分类模型，而这个模型是将特性的线性组合作为自变量，由于自变量的取值范围是负无穷到正无穷。因此，使用logistic函数（或称作sigmoid函数）将自变量映射到(0,1)上，映射后的值被认为是属于y=1的概率。

形式化表示就是

假设函数

其中x是n维特征向量，函数g就是logistic函数。

而的图像是

可以看到，将无穷映射到了(0,1)。

而假设函数就是特征属于y=1的概率。

当我们要判别一个新来的特征属于哪个类时，只需求，若大于0.5就是y=1的类，反之属于y=0类。

再审视一下，发现只和有关，>0，那么，g(z)只不过是用来映射，真实的类别决定权还在。还有当时，=1，反之=0。如果我们只从

出发，希望模型达到的目标无非就是让训练数据中y=1的特征，而是y=0的特征

。Logistic回归就是要学习得到，使得正例的特征远大于0，负例的特征远小于0，强调

在全部训练实例上达到这个目标。

1.1.3、形式化标示

我们这次使用的结果标签是y=-1,y=1，替换在logistic回归中使用的y=0和y=1。同时将替换成w和b。以前的，其中认为。现在我们替换为b，后面替换为（即）。这样，我们让，进一步。也就是说除了y由y=0变为y=-1，只

是标记不同外，与logistic回归的形式化表示没区别。

再明确下假设函数

上面提到过我们只需考虑的正负问题，而不用关心g(z)，因此我们这里将g(z)做一个简化，将其简单映射到y=-1和y=1上。映射关系如下：

于此，想必已经解释明白了为何线性分类的标准一般用1 或者-1 来标示。

注：上小节来自jerrylead所作的斯坦福机器学习课程的笔记。

1.2、线性分类的一个例子

下面举个简单的例子，一个二维平面(一个超平面，在二维空间中的例子就是一条直线)，如下图所示，平面上有两种不同的点，分别用两种不同的颜色表示，一种为红颜色的点，另一种则为蓝颜色的点，红颜色的线表示一个可行的超平面。

从上图中我们可以看出，这条红颜色的线把红颜色的点和蓝颜色的点分开来了。而这条红颜色的线就是我们上面所说的超平面，也就是说，这个所谓的超平面的的确确便把这两种不同颜色的数据点分隔开来，在超平面一边的数据点所对应的y全是-1 ，而在另一边全是 1 。

接着，我们可以令分类函数（提醒：下文很大篇幅都在讨论着这个分类函数）：

显然，如果f(x)=0，那么x是位于超平面上的点。我们不妨要求对于所有满足f(x)<0的点，其对应的y等于-1 ，而f(x)>0则对应y=1的数据点。

注：上图中，定义特征到结果的输出函数，与我们之前定义的

实质是一样的。

（有一朋友飞狗来自Mare_Desiderii，看了上面的定义之后，问道：请教一下SVM functional margin 为

=y(wTx+b)=yf(x)中的Y是只取1和-1 吗？y的唯一作用就是确保functional margin的非负性？真是这样的么？当然不是，详情请见本文评论下第43楼）

当然，有些时候，或者说大部分时候数据并不是线性可分的，这个时候满足这样条件的超平面就根本不存在(不过关于如何处理这样的问题我们后面会讲)，这里先从最简单的情形开始推导，就假设数据都是线性可分的，亦即这样的超平面是存在的。

更进一步，我们在进行分类的时候，将数据点x代入f(x)中，如果得到的结果小于0 ，则赋予其类别-1 ，如果大于0 则赋予类别 1 。如果f(x)=0，则很难办了，分到哪一类都不是。

请读者注意，下面的篇幅将按下述3点走：

1. 咱们就要确定上述分类函数f(x) = w.x + b（w.x表示w与x的内积）中的两个参数w和

b，通俗理解的话w是法向量，b是截距（再次说明：定义特征到结果的输出函数

，与我们最开始定义的实质是一样的）；

2. 那如何确定w和b呢？答案是寻找两条边界端或极端划分直线中间的最大间隔（之所以

要寻最大间隔是为了能更好的划分不同类的点，下文你将看到：为寻最大间隔，导出

1/2||w||^2，继而引入拉格朗日函数和对偶变量a，化为对单一因数对偶变量a的求解，

当然，这是后话），从而确定最终的最大间隔分类超平面hyper plane和分类函数；

3. 进而把寻求分类函数f(x) = w.x + b的问题转化为对w，b的最优化问题，最终化为对偶

因子的求解。

总结成一句话即是：从最大间隔出发（目的本就是为了确定法向量w），转化为求对变量w和b 的凸二次规划问题。亦或如下图所示（有点需要注意，如读者@酱爆小八爪所说：从最大分类间隔开始，就一直是凸优化问题）：

1.3、函数间隔Functional margin与几何间隔Geometrical margin

一般而言，一个点距离超平面的远近可以表示为分类预测的确信或准确程度。

在超平面w*x+b=0确定的情况下，|w*x+b|能够相对的表示点x到距离超平面的远近，而w*x+b的符号与类标记y的符号是否一致表示分类是否正确，所以，可以用量y*(w*x+b)

的正负性来判定或表示分类的正确性和确信度。

于此，我们便引出了定义样本到分类间隔距离的函数间隔functional margin的概念。

1.3.1、函数间隔Functional margin

我们定义函数间隔functional margin为：

= min i (i=1，...n)

1.3.2、点到超平面的距离定义：几何间隔Geometrical margin

在给出几何间隔的定义之前，咱们首先来看下，如上图所示，对于一个点x，令其垂直投影到超平面上的对应的为x0，由于w是垂直于超平面的一个向量，为样本x到分类间隔的距离，我们有

（||w||表示的是范数，关于范数的概念参见这里） 又由于 x 0 是超平面上的点，满足 f (x 0)=0 ，代入超平面的方程即可算出：

（有的书上会写成把||w|| 分开相除的形式，如本文参考文献及推荐阅读条目11，其中，||w||为w 的二阶泛数）

不过这里的是带符号的，我们需要的只是它的绝对值，因此类似地，也乘上对应的类别 y 即可，

因此实际上我们定义 几何间隔geometrical margin 为(注：别忘了，上面

的定义，=y(wTx+b)=yf(x) )：

（代人相关式子可以得出：yi*(w/||w|| + b/||w||)）

1.3.3平面上之间的表达方程

上述平面中直线方程为：

Ax+By+C=0

比如 2x+3y+6=0；

可以改写为以下形式：

[]2360x y ??+=????

即对应w*x+b=0;

从而可以结合本节关于和γ的定义推出以下公式：

正如本文评论下读者popol1991留言：函数间隔y*(wx+b)=y*f(x)实际上就是|f(x)|，只是人为定

那么如果用向量表示，设w=(a,b),f(x)=wx+c,那么这个距离正是|f(p)|/||w||。

1.4、最大间隔分类器M aximum Margin Classifier的定义

于此，我们已经很明显的看出，函数间隔functional margin 和几何间隔geometrical margin 相差一个的缩放因子。按照我们前面的分析，对一个数据点进行分类，当它的margin 越大的时

候，分类的confidence 越大。对于一个包含n个点的数据集，我们可以很自然地定义它的margin 为所有这n个点的margin 值中最小的那个。于是，为了使得分类的confidence 高，我们希望所选择的超平面hyper plane 能够最大化这个margin 值。

通过上节，我们已经知道：

1、functional margin 明显是不太适合用来最大化的一个量，因为在hyper plane 固定以后，我们可以等比例地缩放w的长度和b的值，这样可以使得的值任意大，亦即functional margin可以在hyper plane 保持不变的情况下被取得任意大，

2、而geometrical margin 则没有这个问题，因为除上了这个分母，所以缩放w和b的时候的值是不会改变的，它只随着hyper plane 的变动而变动，因此，这是更加合适的一个margin 。

这样一来，我们的maximum margin classifier 的目标函数可以定义为：

当然，还需要满足一些条件，根据margin 的定义，我们有

其中 (等价于= /||w||，故有稍后的=1 时，= 1 / ||w||)，处于方便推导和优化的目的，我们可以令=1(对目标函数的优化没有影响，至于为什么，请见本文评论下第42楼回复)，此时，上述的目标函数转化为(其中，s.t.，即subject to的意思，它导出的是约束条件)：

（S. t.: subject to）

通过求解这个问题，我们就可以找到一个margin 最大的classifier ，如下图所示，中间的红色线条是Optimal Hyper Plane ，另外两条线到红线的距离都是等于的(便是上文所定义的geometrical margin，当令=1时，便为1/||w||，而我们上面得到的目标函数便是在相应的约束条件下，要最大化这个1/||w||值)：

通过最大化margin ，我们使得该分类器对数据进行分类时具有了最大的confidence，从而设计决策最优分类超平面。

1.5、到底什么是Support Vector

上节，我们介绍了Maximum Margin Classifier，但并没有具体阐述到底什么是Support Vector，本节，咱们来重点阐述这个概念。咱们不妨先来回忆一下上节1.4节最后一张图：

可以看到两个支撑着中间的gap 的超平面，它们到中间的纯红线separating hyper plane 的距离

相等，即我们所能得到的最大的geometrical margin，而“支撑”这两个超平面的必定会有一些点，而这些“支撑”的点便叫做支持向量Support Vector。

很显然，由于这些supporting vector 刚好在边界上，所以它们满足（还记

得我们把functional margin 定为1 了吗？上节中：“处于方便推导和优化的目的，我们可以令=1”），而对于

所有不是支持向量的点，也就是在“阵地后方”的点，则显然有。当然，除了从几何直观上之外，支持向量的概念也可以从下文优化过程的推导中得到。

第二层、深入SVM

2.1、从线性可分到线性不可分

2.1.1、从原始问题到对偶问题的求解

虽然上文1.4节给出了目标函数，却没有讲怎么来求解。现在就让我们来处理这个问题。回忆一下之前得到的目标函数（subject to导出的则是约束条件）：

此类问题由于其中b是未知的，因此无法借助于matlab的fminon函数进行求解。

由于求的最大值相当于求的最小值，所以上述问题等价于（w由分母变成分子，从而也有原来的max问题变为min问题，很明显，两者问题等价）：

1. 到这个形式以后，就可以很明显地看出来，它是一个凸优化问题，或者更具体地说，它

是一个二次优化问题——目标函数是二次的，约束条件是线性的。这个问题可以用任何

现成的QP (Quadratic Programming)的优化包进行求解；

2. 但虽然这个问题确实是一个标准的QP 问题，但是它也有它的特殊结构，通过Lagrange Duality变换到

对偶变量(dual variable) 的优化问题之后，可以找到一种更加有效的方法来进行求解，而且通常情况下

这种方法比直接使用通用的QP 优化包进行优化要高效得多。

也就说，除了用解决QP问题的常规方法之外，还可以应用拉格朗日对偶性，通过求解对偶问题得到最优解，这就是线性可分条件下支持向量机的对偶算法，这样做的优点在于：一者对偶问题往往更容易求解；二者可以自然的引入核函数，进而推广到非线性分类问题。

ok，接下来，你将看到“对偶变量dual variable的优化问题”等类似的关键词频繁出现，便是解决此凸优化问题的第二种更为高效的解--对偶变量的优化求解。

至于上述提到，关于什么是Lagrange duality？简单地来说，通过给每一个约束条件加上一个Lagrange multiplier(拉格朗日乘值)，即引入拉格朗日对偶变量，如此我们便可以通过拉格朗日函数将约束条件融和到目标函数里去(也就是说把条件融合到一个函数里头，现在只用一个函数表达式便能清楚的表达出我们的问题)：

然后我们令