posts - 46,&
comments - 18,&
trackbacks - 0
1.所需要软件下载：
& （1）libsvm（）
& （2）python
& （3）gnuplot 画图软件（）
&这里只考虑windows的环境：
& 1、 下载libsvm的zip包，只要解压到某个文件夹就好就好（随便D:\gjs\libsvm）
&2、安装python（我的是2.7.3）
&3、下载好gnuplot ，直接解压就好，无需安装（C:\gnuplot）
2.数据格式说明
0 1:5.1 2:3.5 3:1.4 4:0.22 1:4.9 2:3.0 3:1.4 4:0.21 1:4.7 2:3.2 3:1.3 4:0.2[label]& &[Index1]:[value1]&&[index2]:[value2]&&[index3]:[value3]&[label]:类别（通常是整数）[index n]: 有顺序的索引 [value n]
可能需要自己转换训练以及测试数据的格式。
3.使用方法
1. windows cmd命令窗口
& 下载的libsvm包里面已经为我们编译好了（windows）。
& 进入libsvm\windows，可以看到这几个exe文件：
& 1.svm-predict:&svmpredict& &&&test_file& && & mode_file& & output_file & & &依照已经train好的model ，输入新的数据，并输出预测新数据的类别。
& 2.svm-scale:&有时候特征值的波动范围比较大需要对特征数据进行缩放，可以缩放到0--1之间（自己定义）。
& 3.svm-toy:似乎是图形界面，可以自己画点，产生数据等。
& 4.svm-train: &svmtrain &[option]&&train_file&&[model_file] & &&train 会接受特定格式的输入，产生一个model 文件。
& 第一步：可以自己生成数据，使用svm-toy：
& & 双击svm-toy，点击change可以在画布上画点：
& &点击run,其实就是train的过程，划分的区域：
&点击save可以保存数据（假设保存的数据在D：//libsvm.txt）。
第二步：使用训练数据libsvm.txt进行建模，使用svm-train：
& &使用cmd命令进入到我们解压的libsvm目录中的windows目录，使用svm-train，如下：
#iter为迭代次数，
nu 是你选择的核函数类型的参数，
obj为SVM文件转换为的二次规划求解得到的最小值，
rho为判决函数的偏置项b，
nSV 为标准支持向量个数(0&a[i]&c)，
nBSV为边界上的支持向量个数(a[i]=c)，
Total nSV为支持向量总个数（对于两类来说，因为只有一个分类模型Total nSV = nSV，但是对于多类，这个是各个分类模型的nSV之和 &
同时在该目录下会生成一个训练好的model（libsvm.txt.model）可以打开文件查看里面的内容，主要包括一些参数和支持向量等
& 第三步：使用建好的model进行预测，使用svm-predict& & &同时会生成一个输出文件（libsvm.txt.out）,每行代表该行的预测值类别。
参数优化：
& & & svm的参数优化很重要，libsvm包里面包含了参数的优化函数，主要是暴力求解参数。一般来说我们会使用高斯核函数，包含两个参数（c 和 g）
使用gird.py文件进行参数优化选择:
& & grid.py在libsvm/tools里面，首先需要修改gird.py中的gnuplot文件路径问题，把文件里的路径改成gnuplot 存放的目录：
& &进入grid.py的相应目录，执行grid.py D://libsvm.txt
& &前面两个分别是c 跟g的值，这时候我们重新训练模型（加上参数c g）
& & 可以看到，准确率有了显著的提升， 其实这些步骤完全可以使用easy.py进行实现，同理也需要修改eays.py里面的gnuplot文件路径问题，把文件里的路径改成gnuplot 存放的目录：
& &步骤总结如下：
& &1.转换训练数据为相应的格式。
& &2.有时候可能需要使用&svm-scale对数据进行相应的缩放，有利于训练建模。
& 3.使用grid.py或者easy.py进行参数优化。
& 4.使用svm-train建模和svm-predict进行预测。
2.python版本 使用：
&&& import os
&&& os.chdir('D://gjs//libsvm//python')
&&& from svmutil import *
&&& y,x=svm_read_problem("D://libsvm.txt")
&&& m=svm_train(y,x,'-c 8.0 -g 8.0')
&&& p_lable,p_acc,p_val=svm_predict(y,x,m)
Accuracy = 96.1538% (25/26) (classification)
&&& import os
&&& os.chdir('D://gjs//libsvm//python')
&&& from svmutil import*
&&& data=svm_problem([1,-1],[[1,0,1],[-1,0,-1]]) #元组一表示分类类别
&&& param=svm_parameter('-c 8.0 -g 8.0')
&&& model=svm_train(data,param)
&&& svm_predict([1],[1,1,1],model)
&&&svm_predict([1,-1],[[1,-1,-1],[1,1,1]],model)
Accuracy = 0% (0/2) (classification)
([-1.0, 1.0], (0.0, 4.0, 1.0), [[0.0], [0.]])
3.weka中使用libSVM：
& 可以参照：&
4.eclipse中调用libsvm:
&下载以上两个包libsvm的包，然后在eclipse工程目录里面添加相应的jar包：
DataSource source = new DataSource("D://iris.arff");
Classifier clas=new LibSVM();
String[] optSVM = weka.core.Utils.splitOptions("-c 8.0 -g 8.0");
((LibSVM) clas).setOptions(optSVM);
Instances data=source.getDataSet();
data.setClassIndex(data.numAttributes()-1);
Evaluation eval=new Evaluation(data);
eval.crossValidateModel(clas, data, 10, new Random(1));
System.out.println(eval.toClassDetailsString());
System.out.println(eval.toSummaryString());
System.out.println(eval.toMatrixString());
输出结果为：
&5. linux下使用libsvm：
确认已经安装好python & &
1.&wget http://www.csie.ntu.edu.tw/~cjlin/cgi-bin/libsvm.cgi?+http://www.csie.ntu.edu.tw/~cjlin/libsvm+tar.gz。
2.&tar -zxvf /home/gjs/libsvm.tar.gz。
3. 进入目录执行 make 编译。
4.&./svm-train /home/gjs/libsvm.txt &其他也类似。
5. python grid.py /home/gjs/libsvm.txt &优化参数。
阅读(...) 评论()7893人阅读
数据处理（2）
数据挖据（2）
大数据和云计算（17）
代码文件主要针对Matlab进行说明,但个人仍觉得讲解的支持向量机内容非常棒,可以做为理解这一统计方法的辅助资料;
&&&&&&LibSVM是台湾林智仁(Chih-Jen Lin)教授2001年开发的一套支持向量机的库，这套库运算速度还是挺快的，可以很方便的对数据做分类或回归。由于libSVM程序小，运用灵活，输入参数少，并且是开源的，易于扩展，因此成为目前国内应用最多的SVM的库。
这套库可以从免费获得，目前已经发展到2.89版。下载.zip格式的版本，解压后可以看到，主要有5个文件夹和一些c++源码文件。
Java——主要是应用于java平台；
Python——是用来参数优选的工具，稍后介绍；
svm-toy——一个可视化的工具，用来展示训练数据和分类界面，里面是源码，其编译后的程序在windows文件夹下；
tools——主要包含四个python文件，用来数据集抽样(subset)，参数优选（grid），集成测试(easy),数据检查(checkdata)；
windows——包含libSVM四个exe程序包，我们所用的库就是他们，里面还有个heart_scale，是一个样本文件，可以用记事本打开，用来测试用的。
其他.h和.cpp文件都是程序的源码，可以编译出相应的.exe文件。其中，最重要的是svm.h和svm.cpp文件，svm-predict.c、svm-scale.c和svm-train.c（还有一个svm-toy.c在svm-toy文件夹中）都是调用的这个文件中的接口函数，编译后就是windows下相应的四个exe程序。另外，里面的&README&跟&FAQ也是很好的文件，对于初学者如果E文过得去，可以看一下。
下面以svm-train为例，简单的介绍下，怎么编译：（这步很简单，也没必要，对于仅仅使用libsvm库的人来说，windows下的4个exe包已经足够了，之所以加这步，是为了那些做深入研究的人，可以按照自己的思路改变一下svm.cpp，然后编译验证）
我用的是VC 6.0，新建一个控制台（win32 console application）程序，程序名叫svm-train（这个可以随意），点击OK后，选择empty。
进入程序框架后，里面什么都没有，然后找到你的程序目录，把svm-train.c、svm.h和svm.cpp拷贝过去（.c文件是c语言的，要是你习惯了c++，你尽可以改成.cpp），然后把这3个文件添加到工程，编译。。。如果没错误，到debug下面看看，是不是有个svm-train.exe。其实windows下的svm-train.exe就是这样编译出来的。
哈哈，怎么样是不是很简单。但是，这样的程序直接运行没意义，他要在dos下运行，接收参数才行。下面开始我们的libsvm的体验之旅。
第一次体验LibSvm
&&&&&&& 1.把LibSVM包解压到相应的目录（因为我只需要里面windows文件夹中的东东，我们也可以只把windows文件夹拷到相应的目录），比如D:/libsvm。
&&&&&&& 2.在电脑“开始”的“运行”中输入cmd，进入DOS环境。定位到d:/ libsvm下，具体命令如下:
&&&&&&&&&&&&& d: (回车)
&&&&&&&&&&&&cd /libsvm/windows (回车)
&&&&&&&&&&&& &(上面第一行是先定位到盘符d，第二行cd是定位到相应盘符下的目录)
&&&&&&& 3.进行libsvm训练，输入命令：(这里要注意文件的名字，2.89以前版本都是svmtrain.exe)
&&&&&&& svm-train heart_scale train.model
&&&&&&&&heart_scale——是目录下的已经存在的样本文件，要换成自己的文件，只需改成自己的文件名就可以了
&&&&&&& train.model——是创建的结果文件，保存了训练后的结果
可以看到结果：
optimization finished, #iter = 162
nu = 0.431029
obj = -100.877288, rho = 0.424462
nSV = 132, nBSV = 107
&&&&& Total nSV = 132
其中，#iter为迭代次数，nu是你选择的核函数类型的参数，obj为SVM文件转换为的二次规划求解得到的最小值，rho为判决函数的偏置项b，nSV为标准支持向量个数(0&a[i]&c)，nBSV为边界上的支持向量个数(a[i]=c)，Total nSV为支持向量总个数（对于两类来说，因为只有一个分类模型Total nSV = nSV，但是对于多类，这个是各个分类模型的nSV之和）。
在目录下，还可以看到产生了一个train.model文件，可以用记事本打开，记录了训练后的结果。
svm_type c_svc//所选择的svm类型，默认为c_svc
&&&&&&kernel_type rbf//训练采用的核函数类型，此处为RBF核
gamma 0.0769231//RBF核的参数γ
&&&&&&nr_class 2//类别数，此处为两分类问题
total_sv 132//支持向量总个数
rho 0.424462//判决函数的偏置项b
label 1 -1//原始文件中的类别标识
nr_sv 64 68//每个类的支持向量机的个数
SV//以下为各个类的权系数及相应的支持向量
1 1:0.:1 3:-0.333333 … 10:-0.:-1 12:-1 13:1
0..125 2:1 3:0.333333 … 10:-0.:-0.:0.5
-1 1:-0.375 2:1 3:-0.333333…. 10:-1 11:-1 12:-1 13:1
-1 1:0.:1 3:1 …. 10:-0.:-1 13:0.5
到现在，第一次体验libsvm到这就基本结束了，其他的两个(svm-predict、svm-scale)的使用过程类似。怎么样，挺爽的吧。对于个别参数你还不理解，没关系，下面我们会具体讲到。
LibSvm使用规范:
其实，这部分写也是多余，google一下“libsvm使用”，就会N多的资源，但是，为了让你少费点心，在这里就简单的介绍一下，有不清楚的只有动动你的mouse了。需要说明的是，2.89版本以前，都是svmscale、svmtrain和svmpredict，最新的是svm-scale、svm-train和svm-predict，要是用不习惯，只需要把那四个exe文件名去掉中间的短横线，改成svmscale、svmtrain和svmpredict就可以了，我们还是按原来函数名的讲。
1. libSVM的数据格式
Label 1:value 2:value ….
Label：是类别的标识，比如上节train.model中提到的1 -1，你可以自己随意定，比如-10，0，15。当然，如果是回归，这是目标值，就要实事求是了。
Value：就是要训练的数据，从分类的角度来说就是特征值，数据之间用空格隔开
比如: -15 1:0.708 2:.3333
需要注意的是，如果特征值为0，特征冒号前面的(姑且称做序号)可以不连续。如：
-15 1:0.708 3:-0.3333
表明第2个特征值为0，从编程的角度来说，这样做可以减少内存的使用，并提高做矩阵内积时的运算速度。我们平时在matlab中产生的数据都是没有序号的常规矩阵，所以为了方便最好编一个程序进行转化。
2. svmscale的用法
svmscale是用来对原始样本进行缩放的，范围可以自己定，一般是[0,1]或[-1,1]。缩放的目的主要是
1）防止某个特征过大或过小，从而在训练中起的作用不平衡；
2）为了计算速度。因为在核计算中，会用到内积运算或exp运算，不平衡的数据可能造成计算困难。
用法：svmscale [-l lower] [-u upper]
[-y y_lower y_upper]
[-s save_filename]
[-r restore_filename] filename
其中，[]中都是可选项：
&&&&&&-l：设定数据下限；lower：设定的数据下限值，缺省为-1
&&&&&-u：设定数据上限；upper：设定的数据上限值，缺省为&1
&&&&&-y：是否对目标值同时进行缩放；y_lower为下限值，y_upper为上限值；
&&&&&-s save_filename：表示将缩放的规则保存为文件save_filename；
&&&&&-r restore_filename：表示将按照已经存在的规则文件restore_filename进行缩放；
&&&&& filename：待缩放的数据文件，文件格式按照libsvm格式。
默认情况下，只需要输入要缩放的文件名就可以了：比如(已经存在的文件为test.txt)
svmscale test.txt
这时，test.txt中的数据已经变成[-1,1]之间的数据了。但是，这样原来的数据就被覆盖了，为了让规划好的数据另存为其他的文件，我们用一个dos的重定向符&&&来另存为(假设为out.txt)：
&&&&& svmscale test.txt & out.txt
运行后，我们就可以看到目录下多了一个out.txt文件，那就是规范后的数据。假如，我们想设定数据范围[0,1]，并把规则保存为test.range文件:
svmscale –l 0 –u 1 –s test.range test.txt & out.txt
这时，目录下又多了一个test.range文件，可以用记事本打开，下次就可以用-r test.range来载入了。
3. svmtrain的用法
svmtrain我们在前面已经接触过，他主要实现对训练数据集的训练，并可以获得SVM模型。
用法：&svmtrain [options] training_set_file [model_file]
其中，options为操作参数，可用的选项即表示的涵义如下所示:
-s设置svm类型：
0 – C-SVC
1 – v-SVC
2 – one-class-SVM
3 –ε-SVR
4 – n - SVR
-t设置核函数类型，默认值为2
0 --线性核：u'*v
1 --多项式核：(g*u'*v+coef0)degree
2 -- RBF核：exp(-γ*||u-v||2)
3 -- sigmoid核：tanh(γ*u'*v+coef0)
-d degree:设置多项式核中degree的值，默认为3
-gγ:设置核函数中γ的值，默认为1/k，k为特征（或者说是属性）数；
-r coef 0:设置核函数中的coef 0，默认值为0；
-c cost：设置C-SVC、ε-SVR、n - SVR中从惩罚系数C，默认值为1；
-n v：设置v-SVC、one-class-SVM与n - SVR中参数n，默认&#；
-pε：设置v-SVR的损失函数中的e，默认值为0.1；
-m cachesize：设置cache内存大小，以MB为单位，默认值为40；
-eε：设置终止准则中的可容忍偏差，默认值为0.001；
-h shrinking：是否使用启发式，可选值为0或1，默认值为1；
-b概率估计：是否计算SVC或SVR的概率估计，可选&#，默认0；
-wi weight：对各类样本的惩罚系数C加权，默认值为1；
-v n：n折交叉验证模式；
model_file：可选项，为要保存的结果文件，称为模型文件，以便在预测时使用。
默认情况下，只需要给函数提供一个样本文件名就可以了，但为了能保存结果，还是要提供一个结果文件名，比如:test.model,则命令为：
svmtrain test.txt test.model
结果说明见LibSVM学习（二）.
4.&svmpredict的用法
svmpredict是根据训练获得的模型，对数据集合进行预测。
用法：svmpredict [options] test_file model_file output_file
其中，options为操作参数，可用的选项即表示的涵义如下所示:
-b probability_estimates——是否需要进行概率估计预测，可选值为0或者1，默认值为0。
model_file ——是由svmtrain产生的模型文件；
test_file——是要进行预测的数据文件，格式也要符合libsvm格式，即使不知道label的值，也要任意填一个，svmpredict会在output_file中给出正确的label结果，如果知道label的值，就会输出正确率；
output_file ——是svmpredict的输出文件，表示预测的结果值。
至此，主要的几个接口已经讲完了，满足一般的应用不成问题。对于要做研究的，还需要深入到svm.cpp文件内部，看看都做了什么。
逐步深入LibSVM(个人认为最精彩部分)
其实，在之前上海交大模式分析与机器智能实验室对2.6版本的svm.cpp做了部分注解，（在哪里？google一下你就知道）。但是，这个注释只是针对代码而注释，整篇看下来，你会发现除了理解几个参数的含义，还是会对libsvm一头雾水。当然作为理解程序的辅助材料，还是有很大用处的。特别是，对几个结构体的说明，比较清楚。但是要清楚程序具体做了什么，还是要追踪程序中去。
&&&&&& 由于svm涉及的数学知识比较多，我们这篇只是讲一些基本的思路，所以就从最基本的C-SVC型svm，核函数采用常用的RBF函数。LibSVM就采用2.6版本的好了，因为后续的版本作者又加了很多内容，不易理解作者最初的思路。我是做模式识别，主要从分类的角度来解析函数的调用过程，我们从svmtrain.c看起，其调用的函数过程如下:
&&& 上图是整个C-SVC的计算过程，下面对一些重要的内容进行具体说明:
1. svm_group_class
&&&&& 在2.6版中没有此函数的，其功能直接在svm_train实现，为了增强可读性，2.89版中设置了这个函数，其实所作的工作都是一样的。需要说明的是其重新排列后perm中只存储的是各个样本在原始位置的序号，而非数据。这样做的好处有两个：
&&&&&& 1）不必破坏原始数据（也就是读进来的x的数据）；
&&&&&& 2）检索起来方便，只需要L维的数据检索，得到序号后，然后定位到原始数据中相应的位置就可以。
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&& perm是中各类的排列顺序是按照原始样本中各类出现的先后顺序排列的，不一定是按照你原始样本的label序号排列，假如原始样本的label是{-1，0，1}，而最先出现的label为1的样本，那么perm中就把label为1的作为类0最先排列。而start中记录的是各类的起始序号，而这个序号是在perm中的序号。
2. 多类判别的one-against-one
&&&&& svm做判别是用的分界线(面)，两类之间只有一个分界线(面)，因此分类器也只有1种，要么是1类要么是2类。但是对于多类，分类方式就有多种。目前，存在的方法主要有：
&&&&&& 1）1-V-R方式
&&&&&& 对于k类问题，把其中某一类的n个训练样本视为一类，所有其他类别归为另一类，因此共有k个分类器。最后预测时，判别式使用竞争方式，也就是哪个类得票多就属于那个类。
&&&&&& 2）1-V-1方式
&&&&&& 也就是我们所说的one-against-one方式。这种方法把其中的任意两类构造一个分类器，共有(k-1)×k/2个分类器。最后预测也采用竞争方式。
&&&&&& 3）有向无环图（DAG-SVM）
&&&&&& 该方法在训练阶段采用1-V-1方式，而判别阶段采用一种两向有向无环图的方式。
&&&&&& LibSVM采用的是1-V-1方式，因为这种方式思路简单，并且许多实践证实效果比1-V-R方式要好。&
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &
&&&&&& 上图是一个5类1-V-1组合的示意图，红色是0类和其他类的组合，紫色是1类和剩余类的组合，绿色是2类与右端两类的组合，蓝色只有3和4的组合。因此，对于nr_class个类的组合方式为：
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& for(i = 0; i & nr_ i ++)
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& {
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& for(j = i+1; i & nr_ j ++)&&&&&
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& { 类 i –V – 类 j }
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& }
3. hessian矩阵的内存处理&&&&&&&&
&&&&& 因为svm是基于结构风险最小的，因此在分类识别方式具有较传统的基于经验风险最小的方式有优势。但是svm也有一个致命的缺陷，因为要计算hessian矩阵Qij所耗的内存巨大，不利于实践中应用。目前，怎么减小内存的使用依旧是SVM的研究的课题。LibSVM对hessian矩阵处理的策略是定义了一个内存处理类Cache类，预先认为分配一定的内存，存储计算好的Qij，其序号的检索采用双向链表的方式，加快了检索速度。其最重要的函数为：
&&&&&&&int Cache::get_data(const int&index,Qfloat&**data,int&len)
&&&&&&//len&是&data 的长度，data为返回的内存首地址，index为Qij的行。
&&&&&& 每次都要查找链表中行为index的Qi，假如已经计算过了，就返回计算过的内存地址，并把储存首地址的链表节点插入到链表尾部。假如没计算过，就分配内存并进行计算，当剩余的内存不够时，就要回收链表头指向的内存。这里，可能有人会问，难道以前计算的就没有用了吗？？其实，是因为Qij是稀疏矩阵，在训练过程中只要其对应的alpha[i]不再变动（这时alpha[i]=0或者alpha[i]=C），其对应的Qi就不会被选到来训练，因此原来计算的Qi就没有用了。其实，链表的顺序代表了别选到的频率，最头部的是最不可能被选到，因为这时alpha[i]=0或者alpha[i]=C，而最尾部的最容易被选到。
4. 数据选择select_working_set(i,j)&&&&&
&&&& 对于样本数量比较多的时候（几千个），SVM所需要的内存是计算机所不能承受的。目前，对于这个问题的解决方法主要有两种：块算法和分解算法。这里，libSVM采用的是分解算法中的SMO(串行最小化)方法，其每次训练都只选择两个样本。我们不对SMO做具体的讨论，要想深入了解可以查阅相关的资料，这里只谈谈和程序有关的知识。
&&&&& 一般SVM的对偶问题为：&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&(4.1)&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
S.t.&&&&&&&&
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&& SVM收敛的充分必要条件是KKT条件，其中:
&&&&&&&&&&&&&&&&&&&&& (4.2）
&&&& 由4.1式求导可得：&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&（4.3）
&&&& 进一步推导可知：
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& （4.4）
&&& 也就是说，只要所有的样本都满足4.4式，那么得到解就是最优值。因此，在每轮训练中，每次只要选择两个样本(序号为i和j)，是最违反KKT条件（也就是4.4式）的样本，就能保证其他样本也满足KKT条件。序号i和j的选择方式 :&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
5. 停止准则
&&& LibSVM程序中，停止准则蕴含在了函数select_working_set(i,j)返回值中。也就是，当找不到符合4.5式的样本时，那么理论上就达到了最优解。但是，实际编程时，由于KKT条件还是蛮苛刻的，要进行适当的放松。令：
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&（4.6）
&&&& 由4.4式可知，当所有样本都满足KKT条件时，gi&≤ -gj
&&&&&& 加一个适当的宽松范围ε，也就是程序中的eps，默认为0.001，那么最终的停止准则为：
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &gi&≤ -gj+ε& →&&& gi&+ gj≤ε&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& （4.7）
6. 因子α的更新
&&& 由于SMO每次都只选择2个样本，那么4.1式的等式约束可以转化为直线约束：
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& （4.8）
&& 转化为图形表示为：
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&&& 把4.8式中α1由α2&表示，即：，结合上图由解析几何可得α2的取值范围：
&&&&&&&&&&&&&&&&&（4.9）
&&&& 经过一系列变换，可以得到的α2更新值α2new：
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& （4.10）
&&& 结合4.9和4.10式得到α2new最终表达式：
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&&&&&&&& （4.11）
&&&&& 得到α2new后，就可以由4.8式求α1new。
&&&&& 这里，具体操作的时候，把选择后的序号i和j代替这里的1和2就可以了。当然，编程时，这些公式还是太抽象。对于4.9式，还需要具体细分。比如，对于y1&y2&= -1时的L = max(0,α2&- α1)，是0大还α2&- α1是大的问题。总共需要分8种情况。
7. 数据缩放do_shrinking()
&&&& 上面说到SVM用到的内存巨大，另一个缺陷就是计算速度，因为数据大了，计算量也就大，很显然计算速度就会下降。因此，一个好的方式就是在计算过程中逐步去掉不参与计算的数据。因为，实践证明，在训练过程中，alpha[i]一旦达到边界（alpha[i]=0或者alpha[i]=C），alpha[i]值就不会变，随着训练的进行，参与运算的样本会越来越少，SVM最终结果的支持向量（0&alpha[i]&C）往往占很少部分。
&&&&&& LibSVM采用的策略是在计算过程中，检测active_size中的alpha[i]值，如果alpha[i]到了边界，那么就应该把相应的样本去掉（变成inactived），并放到栈的尾部，从而逐步缩小active_size的大小。
8. 截距b的计算
&&& b计算的基本公式为：
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& （4.12）
&&&& 理论上，b的值是不定的。当程序达到最优后，只要用任意一个标准支持向量机（0&alpha[i]&C）的样本带入4.12式，得到的b值都是可以的。目前，求b的方法也有很多种。在libSVM中，分别对y=+1和y=-1的两类所有支持向量求b，然后取平均值：
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& （4.13）
&&& 至此，libSVM的整个思路我们简单的过了一遍，里面涉及到很到理论知识，许多细节需要查看相关的SVM的书籍。说实话，笔者也是新手，有些理论也没弄很清楚，我只能把我知道的尽量的讲出来。希望对一些想要了解SVM的有所帮助。
分界线的输出
对于学习SVM人来说，要判断SVM效果，以图形的方式输出的分解线是最直观的。LibSVM自带了一个可视化的程序svm-toy，用来输出类之间的分界线。他是先把样本文件载入，然后进行训练，通过对每个像素点的坐标进行判断，看属于哪一类，就附上那类的颜色，从而使类与类之间形成分割线。我们这一节不讨论svm-toy怎么使用，因为这个是“傻瓜”式的，没什么好讨论的。这一节我们主要探讨怎么结合训练结果文件，自己编程输出分界线。
&&&&&& 为什么说是分界线呢，其实严格说来是分解超平面，但是我们为了能直观用绘图工具绘(比如matlab)出图来只能输出具有二维（也就是特征数是2）的样本分界，因此也就成了线了。好了，闲话少说，进入正题。要绘分界线，就要用到训练结果，我们在第二节和第三节都讨论了，训练结果（或训练模型）文件怎么输出，但是，没怎么详细说明怎么使用训练结果，现在具体说明。下面是两个模型文件：
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&&&&&& 图5.1 两类模型文件&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 图5.2 三类模型文件
&&&& 从图5.1和5.2比较可以看出，两类只存在一个分类器，因此每个支持向量对应的系数α(也就是SV的第一排)，也只有 1个（当然，截距rho也只有一个）。这种情况最简单，只要把相应的支持向量和α的值带入方程：
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& (5.1)
&&&& 找到为0的解，就是分界点了。（式中，有些文献是+b，libSVM采用的是-b）
&&& 对于三类或多类时，情况就比较复杂。我们原来讨论过，对于类数k&2的情况，分类器个数为k×(k-1)/2个，那么对应的b值（也就是rho）应该也是k×(k-1)/2个。那么每个支持向量对应的系数α是多少呢？是k-1个，因为每个支持向量（sv）与其他每个类都有一个系数相对应。当然，和有的类对应时可能不是标准支持向量(0&alpha[i]&C)，但是至少和其中一个类对应是标准的。我们先看一下图5.2的SV的数据结构：
各nSV对应的αiyi
类0(label为-1)
类0 - V -类1
类0 - V -类2
1:0.297595
2:1.197805
类1(label为0)
类1 - V -类0
类1 - V -类2
1:3.621706
2:1.263636
类2(label为1)
类2 - V -类0
类2 - V -类1
1:8.296066
2:7.225341
&&& 从表中，可以看出，每个支持向量(SV)都有相应的k-1（这里的k为3）个α，后面就是向量的数据。因此，输出分界线时，只要认清系数的位置就可以了。如要输出类0和类2之间的分界线，就要带入类0的第二列和类2的第1列中的α。
&& 这里需要重点说明的是：文件输出的不是单纯的α，实际上是αiyi（这里的yi是在训练时的+1或-1，而不是原始样本的label），因此在带入5.1式时，不需要判断yi的值了。
&&&&& 了解了数据结构以后，就是求解方程。5.1式是个多元方程（这和x的维数有关，这里讨论的是2维的，因此是二元方程），而只有一个等式，因此要对其中一个参数做定常处理。先求出其中一个参数的范围，不妨设为x[0]（在绘图时相当于x坐标轴）x_max和x_min，然后分成100等分，对每一个节点处
&&&&& x[0]i&= i×(x_max- x_min)/100+ x_min
&&&&& 这样，x[0]就相当于固定了，然后代入5.1式求x[1]（也就是y）。这就转化成了一元方程，可以采用传统的数学解法，这里，我采用的是网络遍历法。也就是对x[1]也分成100分进行遍历，把节点处的x[1]：
&&&&&& x[1]j&= j×(y_max- y_min)/100+ y_min
&&&& 代入5.1式，看是否接近于0，如果接近0，说明此点是边界点，然后输出坐标就可以了。
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& for(i = 0; i & 100; i ++)
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& for(j = 0; j & 100; j ++)
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& {
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& X[0] = x[0]i;
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& X[1] = x[1]j;
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& if()
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& cout && X[0] && “ “ &&& X[1] &&
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& }
&&& 分界点坐标输出以后，就可以用matlab把分界线绘制出来了。
easy.py和grid.py的使用
我们在“LibSVM学习（一）”中，讲到libSVM有一个tools文件夹，里面包含有四个python文件，是用来对参数优选的。其中，常用到的是easy.py和grid.py两个文件。其实，网上也有相应的说明，但很不系统，下面结合本人的经验，对使用方法做个说明。
&&&&&& 这两个文件都要用python（可以在上下载到，需要安装）和绘图工具gnuplot（可以在上下载，不需要安装）。假设python安装在d:/libsvm/tools/python26下，而gnuplot解压到d:/libsvm/tools/gnuplot，libsvm放在了d:/libsvm/program中（这时easy.py和grid.py文件的目录为d:/libsvm/program/tools）。另外，需要注意的是版本，我的是python
2.6、gnuplot 4.2&和libsvm 2.89，操作系统是WINXP。
1.&grid.py使用方法
&&&&&&& 文件grid.py是对C-SVC的参数c和γ做优选的，原理也是网格遍历，假设我们要对目录d:/libsvm/program/tools下的样本文件heart_scale做优选，其具体用法为：
&&&&&& 第一步：打开d:/libsvm/program下的tools文件夹，找到grid.py文件。用python打开（不能双击，而要右键选择“Edit with IDLE”），修改svmtrain_exe和gnuplot_exe的路径。
&&&&&&&&&&&&&&&&&&&&&&&&&&&&& svmtrain_exe = r&D:/libSVM/program/svm-train.exe&
&&&&&&&&&&&&&&&&&&&&&&&&&&&&& gnuplot_exe = r&D:/libSVM/gnuplot/pgnuplot.exe&
&&&&&& （这里面有一个是对非win32的，可以不用改，只改# example for windows下的就可以了）
&&&&& 第二步：运行cmd，进入dos环境，定位到d:/libsvm/program/tools文件夹，这里是放置grid.py的地方。怎么定位可以参看第一节。
&&&&& 第三步：输入以下命令：
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& d:/libsvm/python26/python grid.py heart_scale
&&&&&& 你就会看到dos窗口中飞速乱串的[local]数据，以及一个gnuplot的动态绘图窗口。大约过10秒钟，就会停止。Dos窗口中的[local]数据时局部最优值，这个不用管，直接看最后一行：
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& .5 84.0741
&&&&&& 其意义表示：C = 2048.0；γ=0.5（γ是哪个参数？参看LibSVM学习（三）中svmtrain的参数说明）；交叉验证精度CV Rate = 84.0741%，这就是最优结果。
&&&&& 第四步：打开目录d:/libsvm/program/tools，我们可以看到新生成了两个文件：heart_scale.out和heart_scale.png，第一个文件就是搜索过程中的[local]和最优数据，第二文件就是gnuplot图像。
&&&&&& 现在，grid.py已经运行完了，你可以把最优参数输入到svmtrain中进行训练了。当然了，你在当中某一步很可能出现问题，不过不要紧，我也不是一下子成功的，摸索了半天才成功。下面就需要注意的问题说明一下：
&&&&&&& 1）grid.py和svm-train的版本要统一，也就是说你不能用2.6的grid.py去调用2.89的svm-train。
&&&&&&& 2）你的目录中如果有空格，比如d:/program files/ libsvm/...，那么无论是在第一步还是第二步，请把目录改成d:/progra~1/ libsvm/...
&&&&&&& 3) 第三步的命令问题。首先要看你定位到哪个目录，那么其下的文件就不需要带路径，否则就要带。像我们上面的命令，我当前的目录是d:/libsvm/program/tools，那么其下的easy.py和heart_scale文件就不需要加路径，而python.exe是在d:/libsvm/python26/下，因此不在当前目录下，所以要加路径。比如，当我首先用dos定位到d:/libsvm/python26时，其命令就可以改成：
&&&&&&&&&&&&&&&&&&&& python& d:/libsvm/program/tools/grid.py& d:/libsvm/program/tools/heart_scale
&&&&&& 总起来说，命令为python 目标文件 样本文件，其原则是要让系统找得到文件。假如系统提示你“不是内部或外部命令”，说明你python的路径错误，而如果是‘not found file’的提示，很可能是其他两个文件路径错误。
&&&&&&& 4）假如，你仍旧出现问题，那么请换一下python或者gnuplot的版本，目前python最新版本是3.1，但是好像会出问题，老一点的版本2.4或2.5的兼容性会更好。
2.&easy.py使用方法
&&& 文件easy.py对样本文件做了“一条龙服务”，从参数优选，到文件预测。因此，其对grid.py、svm-train、svm-scale和svm-predict都进行了调用（当然还有必须的python和gnuplot）。因此，运行easy.py需要保证这些文件的路径都要正确。当然还需要样本文件和预测文件，这里样本文件还是用heart_scale，预测文件我们复制一份然后改名heart_test，下面说一下使用方法：
&&& 第一步：打开easy.py，修改# example for windows下的几个路径：&
&& 第二步：运行cmd，进入dos环境，定位到放置easy.py的目录d:/libsvm/program/tools。
&& 第三步：输入命令：
&&&&&&&&&&&&&&&&&&& d:/libsvm/python26/python easy.py heart_scale heat_test
&&&&&&&&&& 你就会看到一个gnuplot的动态绘图窗口。大约20s以后停止，dos窗口显示为：
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& Scaling training data...
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& Cross validation...
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& Best c=2048.0, g=0.5 CV rate=84.0741
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& Training...
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& Output model: heart_scale.model
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& Scaling testing data...
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& Testing...
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& Accuracy = 85.1852% (230/270) (classification)
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& Output prediction: heart_test.predict
&&& 这就是最终预测结果，可以看到第三行就是调用grid.py的结果。在d:/libsvm/program/tools下你会看到又多了7个文件，都是以前我们碰到的过程文件，都可以用记事本打开。
3. 常见的问题解析：
&&&&&&&&&&&&Scaling training data...
&&&&&&&&&&&&& Cross validation...
&&&&&&&&&&&&& Traceback (most recent call last):
&&&&&&&&&&&&& File &easy.py&, line 61, in ?
&&&&&&&&&&&&& c,g,rate = map(float,last_line.split())
&&&&&&&&&&&&& ValueError: need more than 0 values to unpack
&&&&&& [解析] 说明你的grid.py运行出现错误，你可以参照第一部分“grid.py使用方法”运行一下就会发现问题。另外，有的说是相对路径的问题，建议找到easy.py的以下部分：
&&&&&&&cmd = &%s -svmtrain %s -gnuplot %s %s& % (grid_py, svmtrain_exe, gnuplot_exe, scaled_file)
&&&&&&&&& cmd = &%s %s -svmtrain %s -gnuplot %s %s& % (python_path, grid_py, svmtrain_exe, gnuplot_exe, scaled_file)
&&&&&&&&&&&&Traceback (most recent call last)
&&&&&&&&&&&&& File &grid.py&, line 349, in ?
&&&&&&&&&&&&& main()
&&&&&&&&&&&&& File &grid.py&, line 344, in main
&&&&&&&&&&&&& redraw(db)
&&&&&&&&&&&&& File &grid.py&, line 132, in redraw
&&&&&&&&&&&&& gnuplot.write(&set term windows/n&)
&&&&&&&&&&&&& IOError [Errno 22] Invalid argument
&&&&&&&[解析]说明你的gnuplot.exe在调用过程中出现问题，要么是你的路径不对，要么是你的版本不对，请检查。
&&&&&&&&&&&&Traceback (most recent call last):
&&&&&&&&&&&&& File &C:/Python24/lib/threading.py&, line 442, in __bootstrap&
&&&&&&&&&&&&& self.run()&
&&&&&&&&&&&&& File &c:/libsvm/tools/gridregression.py&, line 212, in run&
&&&&&&&&&&&&& self.job_queue.put((cexp,gexp,pexp))&
&&&&&&&&&&&&& File &C:/Python24/lib/Queue.py&, line 88, in put&
&&&&&&&&&&&&& self._put(item)&
&&&&&&&&&&&&& File &c:/libsvm/tools/gridregression.py&, line 268, in _put&
&&&&&&&&&&&&& self.queue.insert(0,item)&
&&&&&&&&&&&&& AttributeError: 'collections.deque' object has no attribute 'insert
&&&&&& [解析] 很显然，你调用的是gridregression.py，其是用来做回归用的。如果你调用easy.py也出现这种问题按照原作者的说法，这里是因为你的python调用出现错误，很可能是版本不对，如果是2.4的版本，请把easy.py中的
&&&&& self.queue.insert(0,item)
&&&&& if sys.hexversion &= 0x:
&&&&&&&&&&&&& self.queue.appendleft(item)
&&&&&& else
&&&&&&&&&&&&& self.queue.insert(0,item)
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：49412次
排名：千里之外
转载：37篇
(4)(4)(2)(2)(3)(3)(5)(1)(5)(1)(1)(8)(1)(1)