支持向量机（理论+opencv实现）-白红宇

支持向量机（理论+opencv实现）

阅读量：4287 次

发布时间：2019-05-27

本文共 10763 字，大约阅读时间需要 35 分钟。

从基础开始讲起，没有这些东西看支持向量机真的很难！

1.拉格朗日乘子(Lagrangemultiplier)

　　　　假设需要求极值的目标函数(objectivefunction)为f(x,y)，限制条件为φ(x,y)=M

　　　　设

　　　　定义一个新函数

　　　　则用偏导数方法列出方程：

、

求出x,y,λ的值，代入即可得到目标函数的极值。

　　　　扩展为多个变量的式子为：

　　　　F(x1,x2,...,xn,λ)=f(x1,x2,...,xn)-λg(x1,x2,...,xn)

　　　　则求极值点的方程为：∂F/∂xi=0(xi即为x1,x2,...,xn等自变量)∂F/∂λ=g(x1,x2,...,xn)=0

2.凸二次规划

　　　　二次规划的一般形式可以表示为，如右下图：

　　　　其中G是矩阵，τ是有限指标集，c，x和{ai}，都是R中的向量。如果

Hessian矩阵是半正定的，则我们说(1.1)是一个凸二次规划，

　　　　在这种情况下该问题的困难程度类似于线性规划如果=0，二次规划问题就变成线性规划问题了)。

　　　　如果有至少一个向量满足约束并且在可行域有下界，则凸二次规划问题就有一个全局最小值。

　　　　如果是正定的，则这类二次规划为严格的凸二次规划，那么全局最小值就是唯一的。如果是一个不定矩阵，则为非凸二次规划，

　　　　这类二次规划更有挑战性，因为它们有多个平稳点和局部极小值点。

3.线性中的对偶

　　　　线性规划有一个有趣的特性，就是任何一个求极大的问题都有一个与其匹配的求极小的线性规划问题。 　　　　例；原问题为 　　　　 MAX X=8*Z1+10*Z2+2*Z3           　　　　s.t.  2*Z1+1*Z2+3*Z3  <=70                 　　　　4*Z1+2*Z2+2*Z3  <=80                　　　　 3*Z1+     1*Z3  <=15                　　　　 2*Z1+2*Z2       <=50                　　　　 Z1，Z2，Z3 〉=0 　　　　Z则其对偶问题为 　　　　MIN =70*Y1+80*Y2+15*Y3+50*Y4        　　　　 s.t    2*y1+4*y2+3*y3+2*y4>=8            　　　　    1*y1+2*y2+       1*y4>=10             　　　　   3*y1+2*y2+1*y3      >=2           　　　　   y1,y2,y3,y3>=0 　　　　可以看出： 　　　　1、若一个模型为目标求 极大 约束为 小于等于的不等式，则它的对偶模型为目标求极小 约束为极大的不等式 　　　　即 “MAX，〈=”  “与MIN，〉=”相对应 　　　　2、从约束条件系数矩阵来看，一个模型中为A 另一个为A的转质，一个模型是 m个约束n个变量 则他的对偶模型为n个约束 m个变量 　　　　3、从数据b c 的位置看 两个规划模型中b和 c的位置对换 　　　　即8、10、2 与 70、80、15、50 对换   　　　　4、两个规划模型中变量非负。

4. 内积空间

5.欧式空间

6.线性空间、希尔伯特空间、巴拿赫空间

在数学中有许多空间表示，比如欧几里德空间、赋范空间、希尔伯特空间等。这些空间之间有什么关系呢？

首先要从距离的定义说起。什么是距离呢？实际上距离除了我们经常用到的直线距离外，还有向量距离如

设X是任一非空集，对X中任意两点x,y，有一实数d(x,y)与之对应且满足：

1. d(x,y)

定义了距离后，我们再加上线性结构，如向量的加法、数乘，使其满足加法的交换律、结合律、零元、负元；数乘的交换律、单位一；数乘与加法的结合律(两个)共八点要求，从而形成一个线性空间，这个线性空间就是向量空间。

在向量空间中，我们定义了范数的概念，表示某点到空间零点的距离： 1. ||x||

2. ||ax||=|a|||x||;

3. ||x+y||

将范数与距离比较，可知，范数比距离多了一个条件2，数乘的运算，表明其是一个强化了的距离概念。范数与距离的关系可以类似理解为与红富士苹果与苹果的关系。

接下来对范数和距离进行扩展，形成如下：范数的集合

距离的集合

下面在已经构成的线性赋范空间上继续扩展，添加内积运算，使空间中有角的概念，形成如下：线性赋范空间+内积运算这时的内积空间已经有了距离、长度、角度等，有限维的内积空间也就是我们熟悉的欧氏空间。

继续在内积空间上扩展，使得内积空间满足完备性，形成希尔伯特空间如下：内积空间+完备性其中完备性的意思就是空间中的极限运算不能跑出该空间，如有理数空间中的

此外，前面提到的赋范空间，使其满足完备性，扩展形成巴拿赫空间如下：赋范空间+完备性

以上均是在距离的概念上进行添加约束形成的，递增关系如下：距离

向量空间+范数

顺便提以下，对距离进行弱化，保留距离的极限和连续概念，就形成拓扑的概念。

有了上面的基础知识，下面开始支持向量机的理论学习

注：已经有很多关于SVM的优秀文章，自认为我距离大牛很远而且表达的没他们好，所以接下来的分析是我觉得难懂的地方，或者自认为老师和前辈们感觉太简单没说到的地方。

1.开篇距离公式推导

　　　　　　　　　　推导如下的公式：

2.SMO算法(主体来自博客，下面会给出链接，自己更改的部分已经标注)

假设我们选取了初始值

满足了问题中的约束条件。接下来，我们固定，这样W就是和的函数。并且和满足条件：

由于

，所以推到出：

由于

都是已知固定值，因此为了方面，可将等式右边标记成实数值。

当

和异号时，也就是一个为1，一个为-1时，他们可以表示成一条直线： a1-a2=ζ，相当于x-y=c作图，斜率为1。如下图：

横轴是

，纵轴是，和既要在矩形方框内，也要在直线上，因此

，

注：这里L、H表示a1给定之后a2的取值范围，从图中可以看到a2取值两种情况，其中{0，C-ζ}属于一条直线、{-ζ，C}属于一条直线，且后者在前者之上，那么：

a2的最小值从{0，-ζ}取最大的值，a2的最大值从{C-ζ，C}取最小的值，因为 ζ = a1 - a2，所以：

同理，当

和同号时，

，

opencv实现SVM

按照以前的性格肯定是用C++把SVM写出来，现在感觉没多大意思，因为很多算法都要自己去实现太难了而且没那么多时间，毕竟现在还用不到SVM，先用opencv自带的例子测试再说。

　　　　　　　　本文用的opencv3.1实现的非线性分类，看了网上的基本都是2.4或者2.9，要么就是用的线性实现的，弄了很长世间才实现！　

　　　　其实主要是讲解一些参数的意义和怎么调用：

SVM的类型：

1 enum Types { 2 /** C-Support Vector Classification. n-class classification (n \f$\geq\f$ 2), allows 3 imperfect separation of classes with penalty multiplier C for outliers. */ 4 C_SVC=100, //C类支持向量分类机。 n类分组  (n≥2)，允许用异常值惩罚因子C进行不完全分类。 5 /** \f$\nu\f$-Support Vector Classification. n-class classification with possible 6 imperfect separation. Parameter \f$\nu\f$ (in the range 0..1, the larger the value, the smoother 7 the decision boundary) is used instead of C. */ 8 NU_SVC=101,//        
              
              
      类支持向量分类机。n类似然不完全分类的分类器。参数为       
              
              
      取代C(其值在区间【0，1】中，nu越大，决策边界越平滑)。 9 /** Distribution Estimation (One-class %SVM). All the training data are from10 the same class, %SVM builds a boundary that separates the class from the rest of the feature11 space. */12 ONE_CLASS=102,//单分类器，所有的训练数据提取自同一个类里，然后SVM建立了一个分界线以分割该类在特征空间中所占区域和其它类在特征空间中所占区域。13 /** \f$\epsilon\f$-Support Vector Regression. The distance between feature vectors14 from the training set and the fitting hyper-plane must be less than p. For outliers the15 penalty multiplier C is used. */16 EPS_SVR=103,//        
                
                
       类支持向量回归机。        
              
              
      代替了 p。 17 /** \f$\nu\f$-Support Vector Regression. \f$\nu\f$ is used instead of p.18 See @cite LibSVM for details. */19 NU_SVR=10420 };

核函数：

1 enum KernelTypes { 2         /** Returned by SVM::getKernelType in case when custom kernel has been set */ 3         CUSTOM=-1, 4         /** Linear kernel. No mapping is done, linear discrimination (or regression) is 5         done in the original feature space. It is the fastest option. \f$K(x_i, x_j) = x_i^T x_j\f$. */ 6         LINEAR=0,//线性核函数 7         /** Polynomial kernel: 8         \f$K(x_i, x_j) = (\gamma x_i^T x_j + coef0)^{degree}, \gamma > 0\f$. */ 9         POLY=1,//多项式函数(r*u'v + coef0)^degree10         /** Radial basis function (RBF), a good choice in most cases.11         \f$K(x_i, x_j) = e^{-\gamma ||x_i - x_j||^2}, \gamma > 0\f$. */12         RBF=2,//exp(-gamma|u-v|^2)基于径向的函数，对于大多数情况都是一个较好的选择：13         /** Sigmoid kernel: \f$K(x_i, x_j) = \tanh(\gamma x_i^T x_j + coef0)\f$. */14         SIGMOID=3,//tanh(r*u'v + coef0)15         /** Exponential Chi2 kernel, similar to the RBF kernel:16         \f$K(x_i, x_j) = e^{-\gamma \chi^2(x_i,x_j)}, \chi^2(x_i,x_j) = (x_i-x_j)^2/(x_i+x_j), \gamma > 0\f$. */17         CHI2=4,18         /** Histogram intersection kernel. A fast kernel. \f$K(x_i, x_j) = min(x_i,x_j)\f$. */19         INTER=520     };

核函数的参数：

成员变量degree针对多项式核函数degree的设置，

gamma针对多项式/rbf/sigmoid核函数的设置，

coef0针对多项式/sigmoid核函数的设置，

Cvalue为损失函数，在C-SVC、e-SVR、v-SVR中有效，

nu设置v-SVC、一类SVM和v-SVR参数，

p为设置e-SVR中损失函数的值，

class_weightsC_SVC的权重，

一些函数的参数：

1  TermCriteria::TermCriteria(int _type, int _maxCount, double _epsilon)2     : type(_type), maxCount(_maxCount), epsilon(_epsilon) {}3     //_type:迭代结束的类型，如果为CV_TERMCRIT_ITER，则用最大迭代次数作为终止条件，如果为CV_TERMCRIT_EPS 则用精度作为迭代条件，如果为CV_TERMCRIT_ITER+CV_TERMCRIT_EPS则用最大迭代次数或者精度作为迭代条件，看哪个条件先满足。4     //_maxCount：终止程序的最大迭代次数5     //_epsilon：终止程序的精度

1     train( InputArray samples, int layout, InputArray responses );2     //samples：输入数据3     //layout： 读取数据方式4                     //----ROW_SAMPLE = 0, //!< 一行为一个样本5                     //----COL_SAMPLE = 1  //!< 一列为一个样本6     //responses：返回的数据(默认为不返回)

上代码：

1 #include 
      
         2 #include 
       
          3 #include "math.h"  4   5 using namespace cv;  6 using namespace std;  7 int test = 0;  8 RNG rng(99999);  9 void drawCross(Mat &img, Point center, Scalar color) 10 { 11     int col = center.x > 2 ? center.x : 2; 12     int row = center.y> 2 ? center.y : 2; 13     line(img, Point(col - 2, row - 2), Point(col + 2, row + 2), color); 14     line(img, Point(col + 2, row - 2), Point(col - 2, row + 2), color); 15 } 16  17 void newSvmTest(int rows, int cols, int testCount) 18 { 19     assert(testCount >= rows * cols); 20  21     Mat img = Mat::zeros(rows, cols, CV_8UC3); 22     Mat testPoint = Mat::zeros(rows, cols, CV_8UC1); 23     Mat data = Mat::zeros(testCount, 2, CV_32FC1); 24     Mat res = Mat::zeros(testCount, 1, CV_32SC1); 25  26     //Create random test points   27     for (int i = 0; i < testCount; i++) 28     { 29         int row = rng.uniform(0,255) % rows; 30         int col = rng.uniform(0,255) % cols; 31         //-----存储数据 32         if (testPoint.at
        
         (row, col) == 0) 33         { 34             testPoint.at
         
          (row, col) = 1; 35             data.at
          
           (i, 0) = float(col) / cols; 36             data.at
           
            (i, 1) = float(row) / rows; 37 } 38 else//防止重复 39 { 40 i--; 41 continue; 42 } 43 //分成三类 44 if (row > (50 * cos(col * CV_PI / 100) + 200)) 45 { 46 drawCross(img, Point(col, row), CV_RGB(255, 0, 0)); 47 res.at
            
             (i, 0) = 1; 48 } 49 else 50 { 51 if (col > 200) 52 { 53 drawCross(img, Point(col, row), CV_RGB(0, 255, 0)); 54 res.at
             
              (i, 0) = 2; 55 } 56 else 57 { 58 drawCross(img, Point(col, row), CV_RGB(0, 0, 255)); 59 res.at
              
               (i, 0) = 3; 60 } 61 } 62 63 } 64 Mat show = img.clone(); 65 //----SVM训练 66 cv::Ptr
               
                 svm = cv::ml::SVM::create(); 67 svm->setType(cv::ml::SVM::Types::C_SVC); 68 svm->setKernel(cv::ml::SVM::KernelTypes::RBF); 69 svm->setDegree(3); 70 svm->setGamma(3); 71 svm->setCoef0(1.0); 72 svm->setC(10); 73 svm->setNu(0); 74 svm->setP(0.1); 75 svm->setTermCriteria(cv::TermCriteria(cv::TermCriteria::EPS, 1000, FLT_EPSILON)); 76 // train operation 77 svm->train(data, cv::ml::SampleTypes::ROW_SAMPLE, res); 78 //----预测数据 79 for (int i = 0; i< rows; i++) 80 { 81 for (int j = 0; j< cols; j++) 82 { 83 Mat m = Mat::zeros(1, 2, CV_32FC1); 84 m.at
                
                 (0, 0) = float(j) / cols; 85 m.at
                 
                  (0, 1) = float(i) / rows; 86 87 float ret = 0.0; 88 ret = svm->predict(m); 89 Scalar rcolor; 90 91 switch ((int)ret) 92 { 93 case 1: rcolor = Scalar(100, 0, 0); break; 94 case 2: rcolor = Scalar(0, 100, 0); break; 95 case 3: rcolor = Scalar(0, 0, 100); break; 96 } 97 98 line(img, Point(j, i), Point(j, i), rcolor); 99 }100 }101 //-------获得支持向量102 int thickness = 2;103 int lineType = 8;104 //Mat sv = svm->getUncompressedSupportVectors();//不能使用，不知道什么原因，网上有的人可以使用105 Mat sv = svm->getSupportVectors();106 for (int i = 0; i < sv.rows; ++i)107 {108 const float* v = sv.ptr
                  
                   (i);109 circle(img, Point((int)(v[0]*600), (int)(v[1]*400)), 4, Scalar(255, 255, 255), thickness, lineType);110 }111 112 imshow("dst", img);113 waitKey(0);114 }115 116 int main(int argc,char** argv[])117 {118 newSvmTest(400, 600, 500);119 return 0;120 }