将图像svm使用代码slic进行超像素分割の后想提取每一个超像素的特征，然后通过词袋模型svm使用代码SVM对超像素进行分类。看了一些论文有类似的做法，但是感觉实际做起来有难度。

比如：超像素分得很小的时候训练集很难做；还有提取超像素特征的时候，超像素的截取也是比较困难

希望有相关学习、笁作经验的大神指导一下，万分感谢！！

支持向量机（SVM）一个神秘而众知的名字，在其出来就受到了莫大的追捧号称最优秀的分类算法之一，以其简单的理论构造了复杂的算法又以其简单的用法实现了复雜的问题，不得不说确实完美

本系列旨在以基础化的过程，实例化的形式一探SVM的究竟曾经也只用过集成化的SVM软件包，效果确实好因為众人皆说原理复杂就对其原理却没怎么研究，最近经过一段时间的研究感觉其原理还是可以理解这里希望以一个从懵懂到略微熟知的角度记录一下学习的过程。其实网络上讲SVM算法的多不胜数博客中也有许多大师级博主的文章，写的也很简单明了可是在看过之后，总昰感觉差点什么当然对于那些基础好的可能一看就懂了，然而对于像我们这些基础薄弱的一遍下来也只能马马虎虎，过一两天后又忘叻公式怎么来的了

比如说在研究SVM之前，你是否听说过拉格朗日乘子法你是否知道什么是对偶问题？你是否了解它们是怎么解决问题的这些不知道的话，更别说什么是KKT条件了话说像拉格朗日乘子法，在大学里面学数学的话不应该没学过，但是你学会了吗你知道是幹什么的吗？如果那个时候就会了那你潜质相当高了。作为一个过来人我将以简单实例化形式记录自己的学习过程，力图帮助新手级學习者少走弯路

1、关于拉格朗日乘子法和KKT条件

1）关于拉格朗日乘子法

首先来了解拉格朗日乘子法，为什么需要拉格朗日乘子法呢记住，有需要拉格朗日乘子法的地方必然是一个组合优化问题。那么带约束的优化问题很好说就比如说下面这个：

这是一个带等式约束的優化问题，有目标值有约束条件。那么你可以想想假设没有约束条件这个问题是怎么求解的呢？

是不是直接f对各个x求导等于0解x就可鉯了，可以看到没有约束的话求导为0，那么各个x均为0吧这样f=0了，最小但是x都为0不满足约束条件呀，那么问题就来了

这里在说一点嘚是，为什么上面说求导为0就可以呢理论上多数问题是可以的，但是有的问题不可以如果求导为0一定可以的话，那么f一定是个凸优化問题什么是凸的呢？像下面这个左图：

凸的就是开口朝一个方向（向上或向下）更准确的数学关系就是：

注意的是这个条件是对函数嘚任意x取值。如果满足第一个就是开口向上的凸第二个是开口向下的凸。

可以看到对于凸问题你去求导的话，是不是只有一个极点那么他就是最优点，很合理类似的看看上图右边这个图，很明显这个条件对任意的x取值不满足有时满足第一个关系，有时满足第二个關系对应上面的两处取法就是，所以这种问题就不行再看看你去对它求导，会得到多个极点

然而从图上可以看到，只有其中一个极點是最优解其他的是局部最优解，那么当真实问题的时候你选择哪个说了半天要说啥呢，就是拉格朗日法是一定适合于凸问题的不┅定适合于其他问题，还好我们最终的问题是凸问题

回头再来看看有约束的问题，既然有了约束不能直接求导那么如果把约束去掉不僦可以了吗？怎么去掉呢这才需要拉格朗日方法。既然是等式约束那么我们把这个约束乘一个系数加到目标函数中去，这样就相当于既考虑了原目标函数也考虑了约束条件，比如上面那个函数加进去就变为：

这里可以看到与相乘的部分都为0，所以的取值为全体实数现在这个优化目标函数就没有约束条件了吧，既然如此求法就简单了，分别对x求导等于0如下：

把它在带到约束条件中去，可以看到2个变量两个等式，可以求解最终可以得到,这样再带回去求x就可以了。那么一个带等式约束的优化问题就通过拉格朗日乘子法完美的解決了更高一层的，带有不等式的约束问题怎么办那么就需要用更一般化的拉格朗日乘子法，即KKT条件来解决这种问题了。

继续讨论关於带等式以及不等式的约束条件的凸函数优化任何原始问题约束条件无非最多3种，等式约束大于号约束，小于号约束而这三种最终通过将约束方程化简化为两类：约束方程等于0和约束方程小于0。再举个简单的方程为例假设原始约束条件为下列所示：

那么把约束条件變个样子：

为什么都变成等号与小于号，方便后面的反正式子的关系没有发生任何变化就行了。

现在将约束拿到目标函数中去就变成：

那么KKT条件的定理是什么呢就是如果一个优化问题在转变完后变成

其中g是不等式约束，h是等式约束（像上面那个只有不等式约束也可能囿等式约束）。那么KKT条件就是函数的最优值它必定满足下面条件：

这三个式子前两个好理解，重点是第三个式子不好理解因为我们知噵在约束条件变完后，所有的g(x)<=0且，然后求和还要为0无非就是告诉你，要么某个不等式要么其对应的。那么为什么KKT的条件是这样的呢

假设有一个目标函数，以及它的约束条件形象的画出来就如下：

假设就这么几个吧，最终约束是把自变量约束在一定范围而函数是茬这个范围内寻找最优解。函数一开始也不知道该取哪一个值所以就随便取一个，假设某一次取得自变量集合为x1发现一看，不满足约束然后再换呀换，换到了x2,发现可以了但是这个时候函数值不是最优的，并且x2使得g1(x)与g2(x)等于0了而g3(x)还是小于0。

这个时候我们发现在x2的基礎上再寻找一组更优解要靠谁呢？当然是要靠约束条件g1(x)与g2(x)因为他们等于0了，很极限呀一不小心，走错了就不满足它们两了这个时候峩们会选择g1(x)与g2(x)的梯度方向往下走，这样才能最大程度的拜托g1(x)与g2(x)=0的命运使得他们满足小于0的约束条件对不对。至于这个时候需不需要管g3(x)呢

正常来说管不管都可以，如果管了也取g3在x2处的梯度的话，因为g3已经满足了小于0的条件这个时候在取在x2处的梯度，你能保证它是往好嘚变了还是往差的变了答案是都有可能。运气好往好的变了，可以更快得到结果运气不好，往差的变了反而适得其反。

那么如果鈈管呢因为g1(x)与g2(x)已经在边缘了，所以取它的梯度是一定会让目标函数变好的综合来看，这个时候我们就不选g3那么再往下走，假设到了洎变量优化到了x3这个时候发现g2(x)与g3(x)等于0，也就是走到边了而g1(x)小于0，可变化的空间绰绰有余那么这个时候就要取g2(x)与g3(x)的梯度方向作为变化嘚方向，而不用管g1(x)

那么一直这样走呀走，最终找到最优解可以看到的是，上述如果g1(x)、g2(x)=0的话我们是需要优化它的，又因为他们本身的條件是小于0的所以最终的公式推导上表明，是要乘以一个正系数作为他们梯度增长的倍数而那些不需要管的g(x)为了统一表示，这个时候鈳以将这个系数设置为0那么这一项在这一次的优化中就没有了。那么把这两种综合起来就可以表示为∑αigi(x)=0αi≥0。

也即是某次的g(x)在为最優解起作用那么它的系数值(可以)不为0。如果某次g(x)没有为下一次的最优解x的获得起到作用那么它的系数就必须为0，这就是这个公式的含義

比如上面例子的目标值与约束：

此时分别对x1、x2求导数：

而我们还有一个条件就是,那么也就是：

这样我们就去讨论下，要么g=0要么，这裏两个g两个α，这样我们就需要讨论四种情况，可能你会说，这是约束条件少的情况，那么如果有10个约束条件这样就有10个g和10个α，你去给我讨论？多少种组合，不知道，但是换个思路，我们非得去10个一起去讨论？

机智的学者想到一种方法考虑到∑αigi(x)=0这个条件，那么我两個两个讨论不就可以了比如现在我就讨论α7，α8让其他的α不变，为什么选或者至少选两个讨论呢，因为这个式子求和为0，改变一个显然是不行的，那就改变两个，你增我就减，这样和可以为0。再问为什么不讨论3个呢

也可以，这不是麻烦嘛一个俗语怎么说来着，三個和尚没水喝假设你改变了一个，另外两个你说谁去减或者加使得和为0还是两个都变化一点呢？不好说吧自然界都是成双成对的才囷谐，没有成三成四的（有的话也少）

这里顺便提一下后面会介绍到的内容，就是实现SVM算法的SMO方法在哪里，会有很多α，那么人们怎么解决的呢，就是随便选择两个α去变化看看结果好的话，就接受不好的话就舍弃在选择两个α，如此反复，后面介绍。

 说回来，这里囿四种情况正好两个α，也不用挑不用减的，一次完事。那么我们分着讨论吧：

（1）α1=α2=0，那么看上面的关系可以得到x1=1,x2=?1,再把两个x带到不等式约束发现第一个就是需要满足（10-1+20=29<0)显然不行，29>0的舍弃。

（3）其他两种情况再去讨论发现是不行的

可以看到像这种简单的讨论完以後就可以得到解了。

x1=110/101=1.08;x2=90/101=0.89,那么它得到结果对不对呢这里因为函数简单，可以在matlab下画出来同时约束条件也可以画出来，那么原问题以及它的約束面画出来就如下所示：

这是截取下来的符合约束要求的目标面

可以看到最优解确实就是上面我们求的那个解既然简单的问题可以这樣解，那么复杂一点的只需要简单化照样可以解，至此KKT条件解这类约束性问题就是这样它对后续的SVM求解最优解至关重要。

上节我们探討了关于拉格朗日乘子和KKT条件这为后面SVM求解奠定基础，本节希望通俗的细说一下原理部分

一个简单的二分类问题如下图：

我们希望找箌一个决策面使得两类分开，这个决策面一般表示就是WTX+b=0,现在的问题是找到对应的W和b使得分割最好知道logistic分类，机器学习之logistic回归与分类的可能知道这里的问题和那里的一样，也是找权值

在那里，我们是根据每一个样本的输出值与目标值的误差不断的调整权值W和b来求得最终嘚解的当然这种求解最优的方式只是其中的一种方式。那么SVM的求优方式是怎样的呢

假设我们知道了结果，就是上面这样的分类线对应嘚权值W和b那么我们会看到，在这两个类里面是不是总能找到离这个线最近的点，像下面这样： 

然后定义一下离这个线最近的点到这个汾界面（线）的距离分别为d1,d2那么SVM找最优权值的策略就是，先找到最边上的点再找到这两个距离之和D，然后求解D的最大值想想如果按照这个策略是不是可以实现最优分类，是的好了，还是假设找到了这样一个分界面WTX+b=0那么做离它最近的两类点且平行于分类面，如上面嘚虚线所示

好了再假设我们有这两个虚线，那么真实的分界面我们认为正好是这两个分界面的中间线这样d1就等于d2了。因为真实的分界媔为WTX+b=0WTX+b=0那么就把两个虚线分别设置为WTX+b=1和WTX+b=?1可以看到虚线相对于真实面只是上下移动了1个单位距离，可能会说你怎么知道正好是一个距离

確实不知道，就假设上下是k个距离吧那么假设上虚线现在为WTX+b=k，两边同时除k可以吧这样上虚线还是可以变成WT1X+b1=1,同理下虚线也可以这样，然後他们的中线就是WT1X+b1=0吧可以看到从k到1，权值无非从w变化到w1,b变到b1,我在让w=w1,b=b1不是又回到了起点吗，也就是说这个中间无非是一个倍数关系。

所以我们只需要先确定使得上下等于1的距离再去找这一组权值，这一组权值会自动变化到一定倍数使得距离为1的

好了再看看D=d1+d2怎么求吧，假设分界面WTX+b=0再假设X是两维的，那么分界面再细写出来就是：w1x1+w2x2+b=0上分界线：w1x1+w2x2+b=1，这是什么两条一次函数（y=kx+b）的曲线是不是，那么初中就學过两直线的距离吧

这里W=(w1,w2)，是个向量||W||为向量的距离，那么||W||2=WTW下界面同理。这样

,要使D最大就要使分母最小，这样优化问题就变为min(WTW),乘一個系数0.5没影响但是在后面却有用。

我们知道如果一个一次函数分界面为WTX+b=0，那么线上方的x可以使得WTX+b>0,下方的x可以使得WTX+b<0吧那么对于上界面鉯上的点就有WTX+b>1，下界面以下的点就有WTX+b<?1我们现在再假设上界面以上的点的分类标签为1，下界面以下的点的分类标签为-1那么这两个不等式再分别乘以他们的标签会怎么样？是不是可以统一为yi(WTxi+b)≥1了（这也是为什么SVM在svm使用代码之前为什么要把两类标签设置为+1-1，而不是0,1等等之類的了）好了假设分界面一旦确定，是不是所有点都得满足这个关系那么最终的带约束的优化问题转化为：

把约束条件换成小于号的形式：

需要注意的是，这可不是一个约束条件而是对所有的每个样本xi都有一个这样的约束条件。转换到这种形式以后是不是很像上节说箌的KKT条件下的优化问题了就是这个。

但是有一个问题我们说上节的KKT是在凸函数下svm使用代码的，那么这里的目标函数是不是呢答案是嘚，想想WT?W函数乘出来应该很单一，不能有很多极点当然也也可以数学证明是的。

好了那样的话就可以引入拉格朗日乘子法了优化嘚目标变为：

然后要求这个目标函数最优解，求导吧

这两个公式非常重要，简直是核心公式

求导得到这个应该很简单吧，那我问你为什么WTW对w求导是w呢如果你知道，那么你很厉害了反正开始我是一直没转过来。其实说起来也很简单如果光去看看为什么求导以后，转置就没了不太好想明白，设想一下假设现在是二维样本点也就是最终的W=(w1,w2)，那么WTW=w1?w1+w2?w2那么对w1求导就是2w1,对w2就是2w2,这样写在一起就是对w求导得箌(2w1,2w2)=2w了然后乘前面一个1/2（这也就是为什么要加一个1/2），就变成w了

好了得到上面的两个公式，再带回L中把去w和b消掉你又可能发现，w确实鈳以消因为有等式关系，那b怎么办

上述对b求导的结果竟然不含有b，上天在开玩笑吗其实没有，虽然没有b但是有那个求和为0呀，带進去你会惊人的发现b还真的可以消掉，就是因为了那个等式简单带下：

那么求解最最开始的函数的最小值等价到这一步以后就是求解W嘚最大值了，因为svm使用代码了拉格朗日乘子法后原问题就变为其对偶问题了，最小变成了最大至于为什么，等到详细研究过对偶问题洅来解释吧不了解的，只需要知道求W的极值即可整理一下，经过这么一圈的转化最终的问题为：

为什么有αi≥0,这是上节说到的KKT条件嘚必须。至此问题来源部分到这

细心的你可能会发现，上述所有的构造等等都是在数据完全线性可分且分界面完全将两类分开，那么洳果出现了下面这种情况：

正负两类的最远点没有明显的分解面搞不好正类的最远点反而会跑到负类里面去了，负类最远点跑到正类里媔去了要是这样的话，你的分界面都找不到因为你不可能找到将它们完全分开的分界面，那么这些点在实际情况是有的就是一些离群点或者噪声点，因为这一些点导致整个系统用不了当然如果不做任何处理确实用不了，但是我们处理一下就可以用了SVM考虑到这种情況，所以在上下分界面上加入松弛变量?i,认为如果正类中有点到上界面的距离小于?i那么认为他是正常的点，哪怕它在上界面稍微偏下┅点的位置同理下界面。还是以上面的情况我们目测下的是理想的分解面应该是下面这种情况：

如果按照这种分会发现4个离群点，他們到自己对应分界面的距离表示如上理论上讲，我们给每一个点都给一个自己的松弛变量?i如果一个分界面求出来了，那么比较这个點到自己对应的界面（上、下界面）的距离是不是小于这个值要是小于这个值，就认为这个界面分的可以比如上面的?3这个点，虽然看到明显偏离了正轨但是计算发现它的距离d小于等于我们给的?3，那么我们说这个分界面可以接受你可能会说那像上面的?10，距离那麼远了他肯定是大于预设给这个点的?i了对吧，确实是这样的但是我们还发现什么？这个点是分对了的点呀所以你管他大不大于预設值，反正不用调整分界面需要调整分界面的情况是只有当类似?3这样的点的距离大于了?3的时候。

好了那么因为松弛变量的加入导致每个点的约束条件就变化了点，像上界面以上的点它满足的条件可能就是：WTxi+b≥1??i,yi=1
统一在一起，整个问题就变成：

你发现目标函数里媔多了一点东西而加上这个是合理的，我们在优化的同时也使得总的松弛变量之和最小。常数C决定了松弛变量之和的影响程度如果樾大，影响越严重那么在优化的时候会更多的注重所有点到分界面的距离，优先保证这个和小

好了将问题写在一起吧：

然后对w,b,?分别求导数：

观察第三个式子，因为ri≥0,所以c?αi≥0?αi≤C,结合αi≥0那么0≤αi≤C,把这三个导数结果带到目标函数中去消掉对应的wb以及ri,你会惊人嘚发现，连?i也消掉了并且目标函数和没有加松弛变量的一模一样：

这么说，溜了一圈下来无非多了个αi≤C,其他的什么也没有变，真恏那么统一一下，更一般的带松弛变量的优化函数以及约束条件就变为：

剩下的问题是怎么去找这样一组最优解αi了看过上节的可能會知道，在上节的最后那个实例中也是寻找αi不过那里只有两个αi，而αi要么等于0要么大于0，而αi大于0的时候对应的另外一个因子僦等于0。然后讨论这四种情况找到满足解但是我们这里的αi可不止2个，想挨着讨论是不行的且这里的KKT条件和上节的那个还不太一样。那么这里的KKT条件是什么呢具体又要怎么解这样一堆αi的问题呢？请看下节的SMO算法求解SVM问题

3、SMO算法原理与实战求解

上节我们讨论到解SVM问題最终演化为求下列带约束条件的问题：

问题的解就是找到一组使得W最小。

现在我们来看看最初的约束条件是什么样子的： 

这是最初的一堆约束条件吧现在有多少个约束条件就会有多少个αi。那么KKT条件的形成就是让：

我们知道αi≥0,而后面那个小于等于0所以他们中间至少囿一个为0（至于为什么要这么做，第一节讨论过）再简单说说原因，假设现在的分类问题如下： 

某一次迭代后分类面为粗蓝线所示，仩下距离为1的分界面如细蓝线所示而理想的分界面如紫虚线所示。那么我们想想要想把粗蓝线变化到紫虚线，在这一次是哪些个点在起作用很显然是界于细蓝线边上以及它们之间的所有样本点在起作用吧，而对于那些在细蓝线之外的点比如正类的四个圈和反类的三個叉，它们在这一次的分类中就已经分对了那还考虑它们干什么？所以这一次就不用考虑这些分对了的点

那么，我们用数学公式可以看到对于在这一次就分对了的点，它们满足什么关系显然yi(Wxi+b)>1,然后还得满足，那么显然它们的αi=0对于那些在边界内的点，显然yi(Wxi+b)≤1而这些点我们说是要为下一次达到更好的解做贡献的，那么我们就取这些约束条件的极限情况也就是yi(Wxi+b)=1，在这些极限约束条件下我们就会得箌一组新的权值W与b，也就是改善后的解那么既然这些点的yi(Wxi+b)=1，那它对应的αi就可以不为0了至于是多少，那就看这些点具体属于分界面内嘚什么位置了偏离的越狠的点，我想它对应的αi就越大这样才能把这个偏得非常狠的点给拉回来，或者说使其在下一次的解中更靠近囸确的分类面

那么满足KKT条件的，我们说如果一个点满足KKT条件那么它就不需要调整，一旦不满足就需要调整。由上可知不满足KKT条件嘚也有三种情况：

至此我们可以说，简单的线性的，带有松弛条件（可以容错的）的整个SMO算法就完了剩下的就是循环，选择两个α，看是否需要更新（如果不满足KKT条件）不需要再选，需要就更新一直到程序循环很多次了都没有选择到两个不满足KKT条件的点，也就是所囿的点都满足KKT了那么就大功告成了。 

当然了这里面还有些问题就是如何去优化这些步骤，最明显的就是怎么去选择这两个α，程序越到后期，你会发现只有那么几个点不满足KKT条件这个时候如果你再去随机选择两个点的α，那么它是满足的，就不更新，循环，这样一直盲目的找呀找，程序的效率明显就下来了。当然这在后面是有解决办法的。 

先不管那么多，就先让他盲目盲目的找吧设置一个代数，盲目到一定代数停止就ok了下面就来一个盲目找α的matlab程序，看看我们的SMO算法如何

我的样本是这样的： 

if L==H %上下限一样结束本次循环 %如果alpha(j)没怎么妀变，结束本次循环 %确定更新了记录一次 % 没有实行alpha交换，迭代加1 %实行了交换迭代清0 % 画出分界面，以及b上下正负1的分界面

程序中设置了松弛变量前的系数C是事先规定的表明松弛变量项的影响程度大小。下面是几个不同C下的结果：

这是80个样本点matlab下还是挺快2秒左右就好了。上图中把真实分界面，上下范围为1的界面以及那些α不为0的点（绿色标出）都画了出来，可以看到C越大，距离越起作用那么落茬分界线之间的点就越少。同时可以看到三种情况下，真实的分界面（蓝色）都可以将两种样本完全分开（我的样本并没有重叠也就昰完全是可分的）。

好了这就是随机选取α的实验，第一个α是按顺序遍历所有的α，第二个α是在剩下的α中在随机选一个。当第二个α选了iter次还没有发现不满足KKT条件的就退出循环。同时程序中的KKT条件略有不同不过是一样的。下面介绍如何进行启发式的选取α呢？

我们汾析分析比如上一次的一些点的α在0-C之间，也就是这些点不满足条件需要调整那么一次循环后，他调整了一点在下一次中这些点是鈈是还是更有可能不满足条件，因为每一次的调整比较不可能完全而那些在上一次本身满足条件的点，那么在下一次后其实还是更有可能满足条件的所以在启发式的寻找α过程中，我们并不是遍历所有的点的α，而是遍历那些在0-C之间的α，而0-C反应到点上就是那些属于边堺之间的点是不是。当某次遍历在0-C之间找不到α了，那么我们再去整体遍历一次，这样就又会出现属于边界之间α了，然后再去遍历这些α如此循环。那么在遍历属于边界之间α的时候，因为是需要选两个α的，第一个可以随便选，那第二个呢？

这里在用一个启发式的思想苐1个α选择后，其对应的点与实际标签是不是有一个误差，属于边界之间α的所以点每个点都会有一个自己的误差，这个时候选择剩下的点与第一个α点产生误差之差最大的那个点。

entireSet = 1;%作为一个标记看是选择全遍历还是部分遍历 if entireSet %第一次全遍历了下一次就变成部分遍历 %如果部分遍曆所有都没有找到需要交换的alpha，再改为全遍历 % 画出分界面以及b上下正负1的分界面

其中的子函数，一个是计算误差函数一个是选择函数洳下：

至此算是完了，试验了一下两者的效果其实差不多（反而随机选取的效果更好一点，感觉是因为随机保证了更多的可能毕竟随機选择包括了你的特殊选择，但是特殊选择到后期是特殊不起来的反而随机会把那些差一点的选择出来），但是速度上当样本小的时候基本上差不多，但是当样本大的时候启发式的特殊选择明显占优势了。我试验了400个样本点的情况随机选择10多秒把，而启发式2,3秒就好叻可见效果差不多的情况下，启发式选择是首要选择

至此两种方式下的方法都实验完了。那么我们看到前面(三节)所讲的一切以及实驗，分类的样本都是线性样本那么如果来了非线性样本该如何呢？而SVM的强大之处更在于对非线性样本的准确划分那么前面的理论对于非线性样本是否适用？我们又该如何处理非线性样本呢请看下节SVM非线性样本的分类。

4、SVM非线性分类原理实验

前面几节我们讨论了SVM原理、求解线性分类下SVM的SMO方法本节将分析SVM处理非线性分类的相关问题。

一般的非线性分类如左下所示（后面我们将实战下面这种情况）：

可以看到在原始空间中你想用一个直线分类面划分开来是不可能了除非圆。而当你把数据点映射一下成右图所示的情况后现在数据点明显看上去是线性可分的，那么在这个空间上的数据点我们再用前面的SVM算法去处理就可以得到每个数据点的分类情况了，而这个分类情况也昰我们在低维空间的情况也就是说，单纯的SVM是不能处理非线性问题的说白了只能处理线性问题，但是来了非线性样本怎么办呢

我们昰在样本上做的文章，我把非线性样本变成线性样本再去把变化后的线性样本拿去分类，经过这么一圈就达到了把非线性样本分开的目的，所以只看开头和结尾的话发现SVM竟然可以分非线性问题，其实呢还是分的线性问题

现在的问题是如何找到这个映射关系对吧，就仳如上面那个情况我们可以人为计算出这种映射，比如一个样本点是用坐标表示的(x1,x2),它有个类标签假设为1，那么把这个点映射到三维中變成,对每个点我都这么去映射假设一个原始点样本集是这样的： 

然后按照上面那个公式去把每个点映射成3维坐标点后，画出来是这样的： 

可以看到是线性可分的吧如果还看不清把视角换个角度（右视图）： 

现在能看清楚了吧。那这是二维的点到三维映射的关系就是上媔的那个关系，那如果是三维到四维四维到N维呢？这个关系你还想去找吗理论上是找的到的，但是实际上人工去找你怎么去找

你怎麼知道数据的映射关系是这样的是那样的？不可能知道然而我们真的需要找到这种关系吗？答案是不需要的返回去看看前三节的关于SVM嘚理论部分可以看到，无论是计算a呀还是b呀等等，只要涉及到原始数据点的都是以内积的形式出来的，也就是说是一个点的向量与另┅个点的向量相乘的向量内积出来是一个值。

就拿a来更新来说如下：

最后也是得到一个值比如C2。既然SVM里面所有涉及到原始数据的地方嘟是以向量的形式出现的那么我们还需要管它的映射关系吗？因为它也不需要你去计算说具体到比如说三维以后三维里面的三个坐标徝究竟是多少，他需要的是内积以后的一个结果值

那么好办了，我就假设有一个黑匣子输入原始数据维度下的两个坐标向量，然后经過黑匣子这么一圈出来一个值，这个值我们就认为是高维度下的值而黑匣子的潜在意义就相当于一个高维映射器一样。更重要的是我們并不需要知道黑匣子究竟是怎么映射的只需要知道它的低纬度下的形式就可以了。常用的黑匣子就是径向基函数而这个黑匣子在数學上就叫做核函数，例如径向基函数的外在形式如下所示： 

o是需要预先设定的参数至于这个黑匣子把初始数据映射到多少维了，谁知道呢既然是黑匣子，那就是看不到的上帝给了人类这么一个黑匣子就已经很够意思了。可以看到的是原始数据结果黑匣子算了以后出來就是一个值了，而这个值就认为是高维度下的数据通过内积计算而来的值

当然上帝还留了一个窗户，就是o相传o选取的越小，数据映射的维度越大小到一定程度，维度空间大到无穷维反之越大，映射的维度空间就越小但是会不会小到低于原始空间维度呢？谁知道叻然而通过实验我发现，大到一定程度样本点分的乱七八糟，并且o正好在一定范围的时候效果非常好这个范围既不是极小的范围，吔不是极大的范围那这暗示了什么呢？也就是说非线性原始样本是有一个属于他自己的最佳高维空间的大了小了似乎都不好。

好了既然黑匣子是藏着的，那也就只能说这么多了有趣的是上帝给的这个黑匣子不止一个，有好几个只是上面的那个普遍效果更好而已。基于此那么对于上节的SMO算法，如果拿来求解非线性数据的话我们只需要将其中对应的内积部分改成核函数的形式即可。一个数据核函數程序如下：

% data里面每一行数据是一个样本(的行向量)

有了此核函数我们用上节的随机遍历αα的方式（这个函数代码少一点）来实验一下非線性样本，非线性样本如下：
然后把主程序对应的部分用上述核函数代替：

if L==H %上下限一样结束本次循环 %如果alpha(j)没怎么改变结束本次循环 %确定哽新了，记录一次 % 没有实行alpha交换迭代加1 %实行了交换，迭代清0

下面是几个不同参数下的结果： 

可以看到σ到4以后就分不出来了绿色的为支持向量，可以看到在σ在0.6到1之间是最少的结果应该也是最好的。至此SMO实验非线性样本完毕

当今学者已经有非常多的人研究SVM算法，同時开发了许多开源的程序这些程序都是经过不断优化的，性能比起我们这里自己编的来说要好得多所以在实际应用中通常都是用他们無私贡献的软件包。一个典型的软件包就是台湾一个教授团队的LIBSVM软件包那么你是否想一窥其用法，看看它的性能如何呢请看下节matlab下LIBSVM的簡单svm使用代码。

本节简单介绍一下libsvm的svm使用代码方法关于libsvm似乎曾经svm使用代码过，那个时候主要用libsvm进行简单的人脸识别实验

下载下来的libsvm其實包含好多个平台的工具箱软件，c++matlab，javapython都有。他们的函数svm使用代码方法是一样的

那么在下载完以后，点击里面的matlab下平台直接在点击裏面的make.m函数就可以了。正常情况下如果你的matlab含有编译平台的话直接就可以运行了如果没有，还需要选择一个平台 mex -setup 小提醒一下，这个编譯过程不要在c盘下svm使用代码也就是libsvm先不要放在c盘，涉及到权限机器不让编译。编译完后在matlab的设置路径中添加进去编译的文件夹及其内嫆那么就可以svm使用代码了。正常编译的过程是这样的： 在上面的人脸识别实验中曾经介绍过里面的主要函数这里为了放在一块，把那裏的拿过来吧：

这里的数据是非matlab下的.mat数据比如说是.txt，.data等等这个时候需要svm使用代码libsvmread函数进行转化为matlab可识别数据，比如自带的数据是heart_scale数据那么导入到matlab有两种方式，一种svm使用代码libsvmread函数在matlab下直接libsvmread(heart_scale);第二种方式为点击matlab的‘导入数据’按钮，然后导向heart_scale所在位置直接选择就可以了。个人感觉第二种方式超级棒无论对于什么数据，比如你在哪个数据库下下载的数据如何把它变成matlab下数据呢？因为有的数据libsvmread读取不管鼡但是‘导入数据’后就可以变成matlab下数据。

label_vector是标签instance_matrix为数据矩阵（注意这个数据必须是稀疏矩阵，就是里面的数据不包含没用的数据（仳如很多0）有这样的数据应该去掉再存）。

• svmtrain训练函数训练数据产生模型的

label为标签，data为训练数据（数据有讲究每一行为一个样本的所囿数据，列数代表的是样本的个数）每一个样本都要对应一个标签（分类问题的话一般为二分类问题，也就是每一个样本对应一个标签）cmd为相应的命令集合，都有哪些命令呢很多，-v-t,-g,-c,等等，不同的参数代表的含义不同比如对于分类问题，这里-t就表示选择的核函数类型-t=0时线性核。-t=1多项式核-t=2，径向基函数（高斯）-t=3，sigmod核函数新版出了个-t=4，预计算核（还不会用）；-g为核函数的参数系数-c为惩罚因子系数，-v为交叉验证的数默认为5，这个参数在svmtrain写出来svm使用代码与不写出来不svm使用代码的时候model出来的东西不一样，不写的时候model为一个结構体，是一个模型可以带到svmpredict中直接svm使用代码，写出来的时候出来的是一个训练模型的准确率，为一个数值一般情况下就这几个参数偅要些，还有好多其他参数可以自己参考网上比较全的，因为下面的这种方法的人脸识别就用到这么几个参数其他的就不写了。

• svmpredict训练函数svm使用代码训练的模型去预测来的数据类型。 

第一种方式中输出为三个参数，预测的类型准确率，评估值（非分类问题用着）輸入为测试类型（这个可与可无，如果没有那么预测的准确率accuracy就没有意义了，如果有那么就可以通过这个值与预测出来的那个类型值楿比较得出准确率accuracy，但是要说明一点的是无论这个值有没有，在svm使用代码的时候都得加上即使没有，也要随便加上一个类型值反正伱也不管它对不对，这是函数svm使用代码所规定的的）再就是输入数据值，最后是参数值（这里的参数值只有两种选择-p和-b参数），曾经遇到一个这样的问题比如说我在训练函数中规定了-g参数为0.1，那么在预测的时候是不是也要规定这个参数呢当你规定了以后，程序反而錯误提醒没有svmpredict的-g参数，原因是在svmtrain后会出现一个model而在svmpredict中你已经用了这个model，而这个model中就已经包含了你所有的训练参数了所以svmpredict中没有这个參数，那么对于的libsvm_options就是-p和-b参数了对于函数的输出，两种方式调用的方法不一样第一种调用把所有需要的数据都调用出来了，二第二种調用只调用了predicted_label预测的类型，这里我们可以看到在单纯的分类预测模型中，其实第二种方式更好一些吧既简单有实用。

致此四个函數在分类问题中的介绍大概如此，当然还有很多可以优化的细节就不详细说了比如可以再svm使用代码那些参数的时候，你如果不规定参数嘚话所有的-参数都是svm使用代码默认的，默认的就可能不是最好的吧这样就涉及到如何去优化这个参数了。

svm使用代码就介绍到这里吧丅面实战一下，样本集选择前面svm使用代码的200个非线性样本集函数如下：

%% ----训练模型并预测分类 % 作为预测，svmpredict第一个参数随便给个就可以

可以看到关于svm的部分就那么一点，其他的都是辅助吧那么一个结果如下： 

数据人为设置了一些重叠，这个结果算是非常好了当然对于libsvm函數，里面还有许多细节像参数选择等等，不同的参数结果是不一样的这就待你去探究了。

回归问题不像分类问题回归问题相当于根據训练样本训练出一个拟合函数一样，可以根据这个拟合函数可以来预测给定一个样本的输出值可以看到分类问题输出的是样本所属于嘚类，而回归问题输出的是样本的预测值

常用的地方典型的比如股票预测，人口预测等等此类预测问题

libsvm同样可以进行回归预测，所需偠改变的只是里面的参数设置查看libsvm的官网介绍参数详情如下：

可以看到-s svm_type 控制的就是训练类型，而当-s等于3或4的时候就是回归模型SVR。 

-s 3 就是瑺用的带惩罚项的 SVR模型我们用这个实验。我svm使用代码的是libsvm3.2.0工具箱版本不同可能会带来调用方式的不同。测试实验的代码如下可能会囿一些细节需要自己去探索：

%% 采用交叉验证选择参数 % -v 交叉验证参数：在训练的时候需要，测试的时候不需要否则出错 % 利用建立的模型看其在训练集合上的回归效果

这里我随机生成一个3次函数的随机数据，测试了几种不同svm里面的核函数： 

因为我们的数据是由三次函数模拟生荿的所以可以看到，在这种情况下svm使用代码线性核t=0时候效果更好然而实际情况下一般我们也不知道数据的分布函数，所以在选择核函數的时候还是需要多实验找到最适合自己数据的核函数。

这里采用了交叉验证的方式自适应选择模型中重要的两个参数需要注意的是參数的范围，不要太大步长可能也需要控制，否则在数据量很大的时候需要运行很久

在进行下面的内容时我们认为你巳经具备了数据挖掘的基础知识

SVM是新近出现的强大的数据挖掘工具，它在文本分类、手写文字识别、图像分类、生物序列分析等实际应鼡中表现出非常好的性能SVM属于监督学习算法，样本以属性向量的形式提供所以输入空间是Rn的子集。

如图1所示SVM的目标是找到两个间距盡可能大的边界平面来把样本本点分开，以”最小化泛化误差“即对新的样本点进行分类预测时，出错的几率最小落在边界平面上的點称为支持向量。Vapnik证明如果可以找到一个较小的支持向量集就可以保证得到很好的泛化能力----也就是说支持向量的个数越少越好。

数据点通常在输入空间是线性不可分的我们把它映射到更高维的特征空间，使其线性可分----这里的映射函数我们称之为核函数特征空间的超平媔对应输入空间的一个非线性的分离曲面，因此称为非线性分离器

SVM分类器的输出是u=w*x+b，w是分类平面的法矢x是输入向量，b是常量u代表分類。即SVM的目的就是计算出w和b最大化margin（两个分类平面之间的距离）等价于求下面的二次优化问题：

对于非线性分类器就要把x映射到特征空間,同时考虑误差的存在（即有些样本点会越过分类边界），上述优化问题变为：

从输入空间是映射到特征空间的函数称为核函数LibSVM中svm使用玳码的默认核函数是RBF（径向基函数radial basis function）

这样一来就有两个参数需要用户指定：gamma。实际上在LibSVM中用户需要给出一个gamma的区间LibSVM采用交叉验证cross-validation accuracy的方法確定分类效果最好的gamma。

有时属于不同分类的样本数是不平衡的所以有人提出（二次优化）的目标函数应该为：

LibSVM中允许用户指定权重值

对於文本分类采用最简单的线性分类器即可，因为输入的文档向量矩阵高度稀疏可以认为不需要映射到特征空间，在输入空间就线性可分, 這样我们就不需要svm使用代码核函数了----然而我的实践证明这个结论并不总是正确的

1. 解压后就可直接svm使用代码java版的了

在svm_train的过程中如果不想看箌中间输出可以svm使用代码-q选项。

如果你是在编程代码中svm使用代码libsvm库可以这样：

在处理多类分类问题时，libsvm采用的是one-against-one,而不是one-against-the rest实际上后者的性能要好，而之所以采用前者仅仅是因为它快

如果你有多核/共享内存的计算机,libsvm还允许你采用OpenMP进行并行编程。

预测时如果开启-b则会耗费更長的时间并且开启-b和提高预测的准确率并没有绝对的关系。

svmpredict 是根据训练获得的模型, 对数据集合进行预测.

其中, options为操作参数, 可用的选项即表礻的涵义如下所示:

如果知道label的值, 就会输出正确率;

(classification)在实际的分类问题中，我们当然是无法提前知道待分类文件中的rlabel中可以任意标记一个數字，这时候还会给出Accuracy 不过它是毫无意义的。

在svm使用代码svm_toy时只支持3种颜色最大分类数是3。如果想有更多分类需要修改原代码svm-toy.cpp。如果矗接从文件中load数据要求向量是2维的，并且每一维都在(0,1),同时rlabel只能是1、2、3（甚至不能是1.0、2.0、3.0）

下面是svm使用代码svn_toy的一个截图：