svm分类器原理

数据分类是数据挖掘中的一个重要题目。数据分类是指在已有分类的训练数据的基础上，根据某种原理，经过训练形成一个分类器；然后使用分类器判断没有分类的数据的类别。注意，数据都是以向量形式出现的，如<0.4, 0.123, 0.323,…>。 支持向量机是一种基于分类边界的方法。其基本原理是（以二维数据为例）：如果训练数据分布在二维平面上的点，它们按照其分类聚集在不同的区域。基于分类边界的分类算法的目标是，通过训练，找到这些分类之间的边界（直线的――称为线性划分，曲线的――称为非线性划分）。对于数据（如N维），可以将它们视为N维空间中的点，而分类边界就是N维空间中的面，称为超面（超面比N维空间少一维）。线性分类器使用超平面类型的边界，非线性分类器使用超曲面。

线性划分如下图：可以根据新的数据相对于分类边界的位置来判断其分类。注意，我们一般首先讨论二分类问题，然后再拓展到多分类问题。以下主要介绍二分类问题。

2、 支持向量机分类的基本原理

支持向量机是基于线性划分的。但是可以想象，并非所有数据都可以线性划分。如二维空间中的两个类别的点可能需要一条曲线来划分它们的边界。支持向量机的原理是将低维空间中的点映射到高维空间中，使它们成为线性可分的。再使用线性划分的原理来判断分类边界。在高维空间中，它是一种线性划分，而在原有的数据空间中，它是一种非线性划分。

但是讨论支持向量机的算法时，并不是讨论如何定义低维到高维空间的映射算法（该算法隐含在其“核函数”中），而是从最优化问题（寻找某个目标的最优解）的角度来考虑的。 3、 最优化问题

我们解决一个问题时，如果将该问题表示为一个函数f(x)，最优化问题就是求该函数的极小值。通过高等数学知识可以知道，如果该函数连续可导，就可以通过求导，计算导数＝0的点，来求出其极值。但现实问题中，如果f(x)不是连续可导的，就不能用这种方法了。最优化问题就是讨论这种情况。 求最优解的问题可以分为两种：（1）无约束最优问题；（2）有约束最优问题。

无约束最优算法可以表达为：minf(x)。可以用数值计算方法中的牛顿法、最速梯度

x下降法等，通过多次循环，求得一次近似的最优解。 有约束问题，一般表达为：

f(x)minxti(x)0s..xEni{1,2,,m}

4、 线性可分的二分类问题

线性可分的二分类问题是指：原数据可以用一条直线（如果数据只有二维）或一个超平面划分开。用一个空间中的超平面将数据分隔为两个类有三种基本方法： （1） 平方最近点法：用两类点中最近的两点连线的平分线作为分类线（面）

（2） 最大间隔法：求分类面，使分类边界的间隔最大。分类边界是值从分类面分别

向两个类的点平移，直到遇到第一个数据点。两个类的分类边界的距离就是分类间隔。

分类平面表示为：(wx)b0。注意，x是向量。分类间隔的倒数为：

12w。所以该最优化问题表达为： 2minw,bs..t12w,2yi((wxi)b)1)1,i1,

,l 1min ||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） 线性支持向量分类机：

分类面：(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 说明：线性支持向量机是基于最大间隔法的。该问题是一个二次规划问题，使用拉格朗日函数合并优化问题和约束，再使用对偶理论，得到上述的分类优化问题。需要注意的是，该问题仍然是一个有约束的最优化问题。 5、 线性不可分问题

(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)，则高维空间中的线性支持向量机模型为：

分类面：(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j,yiyjijK(xi,xj)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）ν-支持向量机分类机

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

11l2 minwi,w,,b,2li1s..tyi((wxi)b)i, i0, i1,,l 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j一个正类样本，k一个负类样本

6、 多分类问题

（1） 一类对余类方法：

建立将一类与其余类分开的支持向量机。如，训练数据有M类，则需要建立M

j

个支持向量机。识别x分类时，选择g(x)最大的分类：

fj(x)sgn(gj(x)),j[1,M]g(x)ijyiK(x,xi)bjji1l

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

（2） 成对分类

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

7、 支持向量模型的求解

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

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

8、 整理svmlib

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

（4） SVM实验由KNN人员进行。