机器学习经典算法详解及Python实现--基于SMO的SVM分类器

jopen 10年前

支持向量机基本上是最好的有监督学习算法，因其英文名为support vector machine，简称SVM。通俗来讲，它是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，其学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解。

（一）理解SVM基本原理

1，SVM的本质--分类

给定一些数据点，它们分别属于两个不同的类，现在要找到一个线性分类器把这些数据分成两类--这就是最基本的线性可分。如果用x表示数据点、用y表示类别（y可以取1或者-1，分别代表两个不同的类），线性分类器的学习目标便是要在n维的数据空间中找到一个分界使得数据可以分成两类，分界方程可以表示为（此处w^T中的T代表转置，x是一个数据点（有m个属性的行向量），w也是一个大小为m的行向量，b是一个常数）：

在二维平面上，上述分界就是一条直线，如下图将黑点和白点分开的线。三维平面上分界就会是一个平面，而更高维平面上就会是其他的分界表现形式，因此将这个分界称为超平面（hyper plane）。

图1

再次重申，我们假设统计样本的分布式是均匀分布的，如此在两分类分类中（类别-1或者1）可以将阈值设为0。实际训练数据中，样本往往是不均衡的，需要算法来选择最优阈值（如ROC曲线）。

因此SVM分类器就是学习出一个分类函数，当f(x) 等于0的时候，x便是位于超平面上的点，而f(x)大于0的点对应 y=1 的数据点，f(x)小于0的点对应y=-1的点。换言之，在进行分类的时候，将新的数据点x代入f(x) 中，如果f(x)小于0则将x的类别赋为-1，如果f(x)大于0则将x的类别赋为1，f(x)=0就没法分了。

下面以二维平面为例阐明SVM的原理。不难发现能够实现分类的超平面（二维平面上就是一条直线）会有很多条，如下图2所示，如何确定哪个是最优超平面呢？直观而言，最优超平面应该是最适合分开两类数据的直线。而判定“最适合”的标准就是这条直线距直线两边最近数据的间隔最大，也就是“使样本中离超平面最近的点到超平面的距离最远”--最大间隔。所以，得寻找有着“最大间隔”的超平面。下面的问题是--如何求“最大间隔”？

图2

2，根据几何间隔计算“最大间隔”

2.1 函数间隔

对任何一个数据点(x,y)，|w^T*x+b|能够表示点x到距离超平面w^T*x+b=0的远近，而w^T*x+b的符号与类标记y的符号是否一致可判断是否分类正确。所以，可用y(w^T*x+b)的正负性判定或表示分类的正确性（为正才正确），引出了函数间隔（functional margin）的概念。定义函数间隔为：

而超平面所有样本点(xi，yi)的函数间隔最小值便为超平面关于训练数据集的函数间隔： mini (i=1，...n)

实际上，函数间隔就是几何上点到面的距离公式。

2.2 几何间隔

假定对于一个点 x ，令其垂直投影到超平面上的对应点为 x0 ，w 是垂直于超平面的一个向量，为样本x到分类间隔的距离，如下图所示：

有，||w||=w^T*w，是w的二阶泛数。

又由于 x₀是超平面上的点，满足 f(x₀)=0 ，代入超平面的方程即可算出：

数据点到超平面的几何间隔定义为：

而超平面所有样本点(xi，yi)的几何间隔最小值便为超平面关于训练数据集的函数间隔： min (i=1，...n)

几何间隔就是函数间隔除以||w||，可以理解成函数间隔的归一化。

2.3 定义最大间隔分类器Maximum Margin Classifier

前面已经提到，超平面离数据点的“间隔”越大，分类的确信度（confidence）也越大，为使分类的确信度尽量高，需要选择能最大化这个“间隔”值的超平面，而这个间隔就是最大间隔。

函数间隔不适合用来衡量最大化间隔值，因为超平面固定后通过等比例缩放w的长度和b的值可使任意大。但几何间隔除了，缩放w和b的时其值是不会改变的。所以几何间隔只随着超平面的变动而变动，最大间隔分类超平面中的“间隔”用几何间隔来衡量。于是最大间隔分类器（maximum margin classifier）的目标函数可以定义为：

（i=1,2,...,n）,

根据前面分析过的，“使样本中离超平面最近的点到超平面的距离最远”，转化成数学表达式就变为条件：

根据前面的讨论：即使在超平面固定的情况下，的值也可以随着 ∥w∥的变化而变化。为了简化计算，不妨将固定为1（实质上就相当于式子两边同除以，则有w^T=w^T‘=w^T/,b=b'=b/），于是最大间隔分类器目标函数演化为为：

式中，s.t.是subject to的意思，它导出的是约束条件。

由于求的最大值相当于求（之所以这么转化是为了求解方便，系数1/2和平方都是后面为了利用导数求最值方便，并无实质上的含义）的最小值，所以上述目标函数等价于（w由分母变成分子，从而也有原来的max问题变为min问题，很明显，两者问题等价）：

3，支持向量(Support Vector)的定义

SVM叫做支持向量机,讨论了这么久,何谓'支持向量'尚未明了.从下图3可以看到两个支撑着中间的间隙的超平面，它们到中间分离超平面的距离(即我们所能得到的最大几何间隔max()相等)，而“支撑”这两个超平面的必定会有一些点，而这些“支撑”的点便叫做支持向量。

很显然，由于这些支持向量(x,y)刚好在边界上，所以它们满足（前面，函数间隔固定为1）；而对于所有不是支持向量的点，也就是在“阵地后方”的点，则显然有y(w^Tx + b) > 1。事实上，当最优的超平面确定下来之后，这些后方的点就不会对超平面产生任何影响。SVM这样的特性一个最直接的好处就在于存储和计算上的优越性-只需要存储和计算少量的支持向量点即可完成对新数据的分类判断。例如，如果使用 100 万个点求出一个最优的超平面，其中是 supporting vector 的有 100 个，那么我只需要记住这 100 个点的信息即可，对于后续分类也只需要利用这 100 个点而不是全部 100 万个点来做计算。当然，通常除了k 近邻之类的“Memory-based Learning”算法，通常算法也都不会直接把所有的点用来做后续推断中的计算。

4，容错松弛因子Outlier

上述SVM超平面的构造过程中并未考虑数据有噪音（即偏离正常位置很远的数据点）的情况，这些点称之为 outlier。在原来的SVM 模型里，超平面本身就是只有少数几个 support vector 组成的，outlier 的存在有可能造成很大的影响，如果这些 support vector 里又存在outlier的话，其影响就很大了。

上图中用黑圈圈起来的那个蓝点是一个 outlier ，它偏离了自己原本所应该在的那个半空间，如果直接忽略掉它的话，原来的分隔超平面还是挺好的，但是由于这个 outlier 的出现，导致分隔超平面不得不被挤歪了，变成途中黑色虚线所示（这只是一个示意图，并没有严格计算精确坐标），同时 margin 也相应变小了。当然，更严重的情况是，如果这个 outlier 再往右上移动一些距离的话，我们将无法构造出能将数据分开的超平面来。

为了处理这种情况，SVM 允许数据点在一定程度上偏离一下超平面。例如上图中，黑色实线所对应的距离，就是该 outlier 偏离的距离，如果把它移动回来，就刚好落在原来的超平面上，而不会使得超平面发生变形了。加入松弛因子后，目标函数变为：

其中称为松弛变量 (slack variable) ，对应数据点xi允许偏离的 functional margin 的量。当然，如果我们允许任意大的话，那任意的超平面都是符合条件的了。所以，我们在原来的目标函数后面加上一项，使得这些的总和也要最小：

其中是一个参数，用于控制目标函数中两项（“寻找 margin 最大的超平面”和“保证数据点偏差量最小”）之间的权重。是需要优化的变量（之一），而是一个事先确定好的常量。

（二）SVM的求解

1，求解过程概述

经过第一节的讨论，我们已经明确SVM的目的就是找到一组向量w和常量b，构成一个超平面，学习出一个分类函数，在进行分类的时候，将新的数据点x代入f(x) 中，如果f(x)小于0则将x的类别赋为-1，如果f(x)大于0则将x的类别赋为1，f(x)=0就没法分了。SVM的求解就是要求出向量w和常量b，而求解过程通过转换成拉格朗日函数，最终可以转化成下述目标函数，可以利用求解对偶问题的序列最小最优化 SMO算法计算出拉格朗日因子，再计算出w和b。详细的数学推导过程这里就不再累述了，这里只在前人的基础上给出更为直观的求解表达式。

目标函数中取值为：

，u_i=f(x_i)即为根据当前的w,b组合计算得出的第i个统计样本的估计值

从中也可以看出支持向量之外的数据点其=0，即在最终分类函数中没有意义。

= T(alpha*T(Y)) * X

b在SMO求解迭代过程中逐步更新得出。

因此分类函数为：

采取矩阵表示即为f(x)= T(X*T(x)) * (alpha(叉乘)T(Y) ) +b，其中参与运算的alpha（m，1）、Y（m，1）、X(m,n)均为矩阵,X表示m个统计样本，每个统计样本有n个属性，x(1,n)表示待估计分类的新数据项。*为矩阵乘法，T()表示矩阵转置，<x_i,x>表示内积。

2，SMO算法

SMO算法的具体推导过程请参考材料’SMO算法推导一节‘。

经过一系列的推导，目标函数的问题最终变为：在上求下述目标函数的最小值。

为了求解这些乘子，每次从中任意抽取两个乘子a1和a2，然后固定其它乘子，使得目标函数只是关于a1和a2的函数。这样，不断的从一堆乘子中任意抽取两个求解，不断的迭代求解子问题，最终达到求解原问题的目的。迭代的停止条件是a2基本没有改变或者总的迭代次数达到了迭代次数上限。

为了解决这个子问题，首要问题便是每次如何选取a1和a2。实际上，其中一个乘子是选取违法KKT条件最严重的，另外一个乘子则由另一个约束条件选取。的初始值均为0，因此迭代开始时的第一对乘子是随机选择的。所以，选择乘子a1和a2就是采取启发式搜索方法结合下述约束条件进行。

对于a1

，即第一个乘子，可以通过刚刚说的那3种不满足KKT的条件来找；

（i）<=1但是<C则是不满足的，而原本=C

(ii)>=1但是>0则是不满足的，而原本=0

(iii)=1但是=0或者=C则表明不满足的，而原本应该是0<<C

而对于第二个乘子

a2可以寻找满足条件：

的乘子。（E_k=u_k-y_k，是根据当前

组合估算的第k个样本的u_k与实际的分类y_k间的差值。

启发式选择方法主要思想是每次选择拉格朗日乘子的时候，优先选择样本前面系数的 ai作优化（论文中称为无界样例），因为在界上（ai为0或C）的样例对应的系数ai一般不会更改。启发式搜索方法是选择第一个拉格朗日乘子用的，比如前面的a2。那么这样选择的话，是否最后会收敛。可幸的是Osuna定理告诉我们只要选择出来的两个ai中有一个违背了KKT条件，那么目标函数在一步迭代后值会减小。违背KKT条件不代表，在界上也有可能会违背。是的，因此循环的算法是：

（i）在给定初始值ai=0后，先对所有样例进行循环，循环中碰到违背KKT条件的（不管界上还是界内）都进行迭代更新。

（ii）第二轮开始就优先针对的样例进行迭代更新，直至此类样例没有ai更新则进入（iii）。

（iii）再次对所有样例进行循环一次后再次进入（ii）

（v）循环（ii）（iii）直至迭代终止（达到最大迭代次数或没有ai得到更新）

最后的收敛条件是在界内（）的样例都能够遵循KKT条件，且其对应的ai只在极小的范围内变动。

此外，更新的同时还要受到第二个约束条件的限制，即sum(ai*yi) = 0。

因此，如果假设选择的两个乘子a1和a2，它们在更新之前分别是、，更新之后分别是、，那么更新前后的值需要满足以下等式才能保证和为0的约束：

其中，是常数。

两个因子不好同时求解，所以可先求第二个乘子a2的解（），再用其表示a1的解（）。

第一步，求解的取值范围

为了求解，得先确定的取值范围，因为乘子都需要满足的条件。因此需要根据乘子a1和a2来计算的上下界。假设它的上下边界分别为H和L，那么有：

接下来，综合和这两个约束条件，求取的取值范围。

根据y1和y2同号或异号，可得出的上下界分别为：

第二步，求解

利用y_ia_i+y_ja_j=常数，消去a_i，可得到一个关于单变量a_j的一个凸二次规划问题，可得关于单变量的解析解（尚未考虑边界条件）：

（表示预测值与真实值之差），（若为0则中止此次循环）

然后考虑约束可得到的最终解为：

第三步，求解

根据，便可以求出，得（此处不需要再根据边界条件修剪）

第四步，更新b

b在满足下述条件下更新：（Note：这里有一个疑问，经过裁剪后的必然是在边界内的，所以：（a）第三种情况根本不会发生；（b）第一种和第二种的顺序是否故意这么安排以确定b1优先级较高？）

且每次更新完两个乘子a1\a2的优化后，都需要再重新计算b，及对应的Ei值。

另外，、还可以这么获得：

然后考虑约束0<=a_j<=C可得到：

对于

这里、与前面的不同之处在于是没有裁剪，是裁剪了，b的更新也要又有变化。这与前述方法本质上是一致的。

最后一步，获得分类函数

最后迭代完成后，更新所有ai、y和b，就可以得到分类函数：

（三）核函数Kernel Function

前面讨论的都是线性可分的情况，对于线性不可分的情况就必须采取某种手段使得数据点在另外一个维度（这个维度不一定都能够直观的视觉展示）变为可线性分类的。这种手段就是核函数。

用’机器学习中的算法(2)-支持向量机(SVM)基础‘提到的来说：世界上本来没有两个完全一样的物体，对于所有的两个物体，我们可以通过增加维度来让他们最终有所区别，当维度增加到无限维的时候，一定可以让任意的两个物体可分了。比如说两本书，从(颜色，内容)两个维度来说，可能是一样的，我们可以加上作者这个维度，还不行就加入类型、成书年代、拥有者、购买地点等等，最终必然可以将两本书区分开来。

在线性不可分的情况下，支持向量机首先在低维空间中完成计算，然后通过核函数将输入空间映射到高维特征空间，最终在高维特征空间中构造出最优分离超平面，从而把平面上本身不好分的非线性数据分开。如下图，左边的一堆数据在二维空间无法划分，右边映射到三维空间里则可以划分：

核函数能简化映射空间中的内积运算—— SVM 里需要计算的地方数据向量总是以内积的形式出现的。对比刚才我们写出来的式子，现在我们的分类函数为：

=T(k(X, x))*(alpha(叉乘)T(Y) ) +b

其中 a 由如下目标函数计算而得：

这样一来计算的问题就算解决了，避开了直接在高维空间中进行计算，而结果却是等价的。

实际应用中，根据问题和数据的不同，选择不同的参数核函数中选择。核的选择对于支持向量机至关重要，这是一个不断尝试、优化选择的过程。常用到的核函数有：

1，多项式核，该空间的维度是，其中 m是原始空间的维度。

2，高斯核，将原始空间映射为无穷维空间，是使用最广泛的核函数之一。由于这个函数类似于高斯分布，因此称为高斯核函数，也叫做径向基函数(Radial Basis Function 简称RBF)。通过调控参数，高斯核实际上具有相当高的灵活性，下图所示的例子便是把低维线性不可分的数据通过高斯核函数映射到了高维空间：

3，线性核=x₁*T(x₂)，实际上就是原始空间中的内积。这可以理解为是为了内积计算的统一而“占位”用的。代码实现时不用再区分线性、非线性，对于线性的分类代入该核函数即可。

（四）SMO算法SVM分类器的python实现

SVM分类器Python学习包包括三个.py文件，svm/object_json /testsvm.py。其中svm.py实现SVM分类器，testsvm.py包含两个测试用例。因为训练过程耗时较长，object_json.py中则是通过自定义的json编码函数将分类器对象永久保存，以后使用时只需要load分类器文件即可，除非需要更新分类器。

包中SVM分类器定义了两个对象svmTrain和svmClassifer，前者根据训练数据，通过SMO算法产生一个SVM分类器；后者则仅是一个SVM分类器，包括由svmTrain产生的支持向量、支持向量set和get函数，分类器永久保存支持函数等。

SVM分类器软件包全部源文件和测试文件的下载地址是：

TBD

（五）SVM分类的应用

1，手写识别

svm分类器包中的digits.rar是一个手写识别测试用例，感兴趣的话可以自己训练svm分类器测试识别效果。

2，文本分类

文本分类与SVM

3，多分类简介

基本的SVM分类器解决的2分类的问题，N分类的情况下有多种方式，这里介绍1vs(N–1)和1v1。更多的SVM多分类应用介绍，参考’SVM多类分类方法‘

前一种方法我们需要训练N个分类器，第i个分类器是判断新的数据属于分类i还是属于其补集（除去i的N-1个分类）。后一种方式我们需要训练N * (N – 1) / 2个分类器，分类器(i,j)能够判断某个点是属于i还是属于j，当对一个未知样本进行分类时，每个分类器都对其类别进行判断．并为相应的类别“投上一票”，最后得票最多的类别即作为该未知样本的类别。这种处理方式不仅在SVM中会用到，在很多其他的分类中也是被广泛用到，从林教授（libsvm的作者）的结论来看，1vs1的方式要优于1vs(N–1)。