svm以及各种版本的实现
一、简述
以二维平面上的分类为例，下面给出了不同的分类可能，哪个才是最优的分类呢？
可以看出第一种分类方法是最好的，为什么呢？因为它的分类平面到两类边界的距离（Margin）最大。
所以SVM也叫Large Margin分类器。
各种资料对它评价甚高，说“ 它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中”。
SVM之线性分类器
如果一个线性函数能够将样本完全正确的分开，就称这些数据是线性可分的，否则称为非线性可分的。
什么叫线性函数呢？在一维空间里就是一个点，在二维空间里就是一条直线，三维空间里就是一个平面，以此类推。
如果不关注空间的维数，这种线性函数就是前言中所说的那个统一的名称——超平面（Hyper Plane）！
在样本空间中，划分超平面可通过如下线性方程来描述：
如图：
在这两个超平面上的样本点也就是理论上离分隔超平面最近的点，是它们的存在决定了H1和H2的位置，支撑起了分界线，它们就是所谓的支持向量，这就是支持向量机的由来
有了这两个超平面就可以顺理成章的定义上面提到的间隔（margin）了
二维情况下 ax+by=c1和ax+by=c两条平行线的距离公式为：
而且这是一个凸二次规划问题，一般的解决方法有两种1是用现成的优化工具包直接求解，2是使用Lagrange Duality找到一种更有效的方法求解。
其中方法2具有两个优点:
a、更好解
b、可以自然地引入核函数，推广到非线性分类
所以这里选用了第二种方法。
二、opencv版本svm
备注：
opencv svm预测的结果是对应的标签值，是不带置信度的，要想获得置信度可以采用libsvm，经过测试比较opencv svm（libsvm2.6版本）比libsvm3.22的准确率高10%左右。为了获得高的准确率，最后修改了opencv svm的源码，采用sigmod函数来获得置信度，预测函数的最后返回值是置信度，大于0.5的代表类别1。具体修改的地方如下：
源码位置：opencv-2.4.13/modules/ml/src/svm.cpp
修改函数：floatCvSVM::predict( const float* row_sample, int row_len, bool returnDFVal ) const
添加代码：红色区域, 1减的目的是为了使输出结果大于0.5的为类别1.
重新编译opencv: cd到opencv所在的目录
mkdir build
cd build
cmake ..
sudo make
sudo make install
或者
不改变opencv源码，在调用处加代码实现；
代码如下：
sum = svm.predict(data[i], True)
res= 1.0-(float)(1 / (1 + math.exp((-1.0)*sum)));
1. python版本
数据格式：numpy数组，假如训练样本为1000，10个特征、每个特征最多10个
train_data = np.array(np.zeros((num, feat_num*obj_num)),dtype=np.float32) #（1000,100）
train_label = np.array(np.zeros((num, 1)),dtype=np.float32) # （1000, 1）
svm = cv2.SVM() #
param = dict(kernel_type=cv2.SVM_LINEAR,svm_type=cv2.SVM_C_SVC, C=1)
#cv2.SVM_LINEAR, cv2.SVM_RBF
svm_type：SVM的类型：
C_SVC表示SVM分类器，该类型可以用于n-类分类问题 (n 2)
C_SVR表示SVM回归
C = 1; //给参数赋初始值
CvSVM::LINEAR : 线性内核，没有任何向映射至高维空间，线性区分（或回归）在原始特征空间中被完成，这是最快的选择。
CvSVM::RBF: 基于径向的函数，对于大多数情况都是一个较好的选择.
ret = svm.train(train_data, train_label, None, None, param) #训练
svm.save(path_model)#保存模型
svm.load(path_model)#加载模型
sum = svm.predict(data, True)#预测，返回值为置信度，大于0.5为违建1.
res= 1.0-(float)(1 / (1 + math.exp((-1.0)*sum)));
2.c++版本
CvSVMParams param;
params.svm_type = CvSVM::C_SVC; //用于n-类分类问题 (n 2)
params.C = 1;
params.kernel_type = CvSVM::LINEAR; //CvSVM::RBF; //向量积
params.term_crit =cvTermCriteria(CV_TERMCRIT_ITER, 100, 1e-6);
CvSVM svm;
Mat data = Mat::zeros(nSampleNum, nCols,CV_32FC1);
Mat label = Mat::zeros(nSampleNum, 1,CV_32FC1);
svm.train(data, label, Mat(), Mat(),m_cParams); //训练
svm.save(“model.xml”); //保存模型
svm.load(“model.xml”); //保存模型
sum = svm.predict(data, True)#预测
dCof= 1.0-(float)(1 / (1 + math.exp((-1.0)*sum)));
// dCof = 1.0-max(min((float)(1 / (1 + exp((-1.0)*dSum))),float(1.0)),float(0.0));
备注:
1. opencv2.4.13 python、c++版本预测结果不同，原因是params.term_crit= cvTermCriteria(CV_TERMCRIT_ITER, 100, 1e-6); python版本采用默认的迭代次数1000；
1. cvTermCriteria(type,max_iter, epsilon);
int type---迭代算法终止条件的类型，是下面之一:
CV_TERMCRIT_ITER---在完成最大的迭代次数之后,停止算法
CV_TERMCRIT_EPS----当算法的精确度小于参数double epsilon指定的精确度时，停止算法
CV_TERMCRIT_ITER+CV_TERMCRIT_EPS--无论是哪一个条件先达到,都停止算法
默认：CV_TERMCRIT_ITER+CV_TERMCRIT_EPS
max_iter; 最大迭代次数，默认：1000
epsilon; 精度， 默认：1e-6
三、libsvm
libsvm：*大学林智仁(Lin Chih-Jen)教授等开发设计的一个简单、易于使用和快速有效的SVM模式识别与回归的软件包.
1. 软件包下载地址：https://www.csie.ntu.edu.tw/~cjlin/libsvm/#download
1. 安装过程：
1）解压到某个你指定的路径；
2）cd 进入libsvm-3.22文件夹，然后make；
3）cd 进入libsvm的python子文件夹 /libsvm-3.17/python，然后make；
4）假设你此时位于libsvm的python子文件夹/libsvm-3.22/python路径下：
$ sudo cp *.py /usr/lib/python2.7/dist-packages/
$ cd ..
$ sudo cp libsvm.so.2 /usr/lib/python2.7/
5） 检验一下，新开一个terminal，进入python
import svm
import svmutil
如果成功，说明装好了
2.代码路径：/home/zhangjing/ocr/svm/train_libsvm.py
数据集：/home/zhangjing/ocr/svm/datasets
train:训练集
txt:存放检测到的特征以及置信度，格式（特征编号置信度）
txt/label0.txt: 存放非违建的标签，格式（08280001.txt 0）
txt/label1.txt 存放违建对应的标签，格式（08280002.txt 1）
test:测试集
参数说明：
训练的参数：
param = svmutil.svm_parameter('-t 2 -b 1')
-t: 核函数类型(kernel_type)
· 0 --linear(线性核):
u'*v
· 1 --polynomial(多项式核):
(gamma*u'*v + coef0)^degree
· 2 --radial basis function(RBF,径向基核/高斯核):
exp(-gamma*|u-v|^2)
· 3 --sigmoid(S型核):
tanh(gamma*u'*v + coef0)
· 4 --precomputed kernel(预计算核)：
核矩阵存储在training_set_file中
-b: 是否估算正确概率,取值0 - 1，默认为0；备注：该参数只有在训练时设置为1时，预测时使用’-b 1’时才计算置信度的。
测试的参数：
p_label, p_acc, p_val = svmutil.svm_predict(label,data, model, '-b 1')
p_labs: 是存储预测标签的列表。
p_acc: 存储了预测的精确度，均值和回归的平方相关系数。
p_vals: 在指定参数'-b 1'时将返回判定系数(判定的可靠程度)。
实验结果：
1. libsvm可预测出置信度，opencv svm只预测出标签号；
2. opencv、matlab是libsvm2.6版本，而测试的libsvm3.22，发现opencv的svm准确率能高些；
http://blog.csdn.net/ybdesire/article/details/53915093
http://blog.csdn.net/luoshixian099/article/details/51073885
http://blog.csdn.net/u012581541/article/details/51181041