.. _introductiontosvms:

支持向量机(SVM)介绍
***************************************

目标
====

本文档尝试解答如下问题:

.. container:: enumeratevisibleitemswithsquare

   + 如何使用OpenCV函数 :svms:`CvSVM::train <cvsvm-train>` 训练一个SVM分类器， 以及用 :svms:`CvSVM::predict <cvsvm-predict>` 测试训练结果。  

什么是支持向量机(SVM)?
=======================

支持向量机 (SVM) 是一个类分类器，正式的定义是一个能够将不同类样本在样本空间分隔的超平面。 换句话说，给定一些标记(label)好的训练样本 (*监督式学习*), SVM算法输出一个最优化的分隔超平面。

如何来界定一个超平面是不是最优的呢? 考虑如下问题：

  假设给定一些分属于两类的2维点，这些点可以通过直线分割， 我们要找到一条最优的分割线.

.. image:: images/separating-lines.png
   :alt: A seperation example
   :align: center

.. note:: 在这个示例中，我们考虑卡迪尔平面内的点与线，而不是高维的向量与超平面。 这一简化是为了让我们以更加直觉的方式建立起对SVM概念的理解， 但是其基本的原理同样适用于更高维的样本分类情形。

在上面的图中， 你可以直觉的观察到有多种可能的直线可以将样本分开。 那是不是某条直线比其他的更加合适呢? 我们可以凭直觉来定义一条评价直线好坏的标准:

  距离样本太近的直线不是最优的，因为这样的直线对噪声敏感度高，泛化性较差。 因此我们的目标是找到一条直线，离所有点的距离最远。

由此， SVM算法的实质是找出一个能够将某个值最大化的超平面，这个值就是超平面离所有训练样本的最小距离。这个最小距离用SVM术语来说叫做 **间隔(margin)** 。 概括一下，最优分割超平面 *最大化* 训练数据的间隔。

.. image:: images/optimal-hyperplane.png
   :alt: The Optimal hyperplane
   :align: center 

如何计算最优超平面?
=======================================

下面的公式定义了超平面的表达式:

.. math:: 
  f(x) = \beta_{0} + \beta^{T} x,

:math:`\beta` 叫做 *权重向量* ， :math:`\beta_{0}` 叫做 *偏置(bias)* 。

.. seealso:: 关于超平面的更加详细的说明可以参考T. Hastie, R. Tibshirani 和 J. H. Friedman的书籍 *Elements of Statistical Learning* ， section 4.5 (*Seperating Hyperplanes*)。

最优超平面可以有无数种表达方式，即通过任意的缩放 :math:`\beta` 和 :math:`\beta_{0}` 。 习惯上我们使用以下方式来表达最优超平面

.. math::
  |\beta_{0} + \beta^{T} x| = 1

式中 :math:`x` 表示离超平面最近的那些点。 这些点被称为 **支持向量**。 该超平面也称为 **canonical 超平面**.

通过几何学的知识，我们知道点 :math:`x` 到超平面 :math:`(\beta, \beta_{0})` 的距离为:

.. math::
   \mathrm{distance} = \frac{|\beta_{0} + \beta^{T} x|}{||\beta||}.

特别的，对于 canonical 超平面, 表达式中的分子为1，因此支持向量到canonical 超平面的距离是

.. math::
  \mathrm{distance}_{\text{ support vectors}} = \frac{|\beta_{0} + \beta^{T} x|}{||\beta||} = \frac{1}{||\beta||}.

刚才我们介绍了间隔(margin),这里表示为 :math:`M`, 它的取值是最近距离的2倍:

.. math::
  M = \frac{2}{||\beta||}

最后最大化 :math:`M` 转化为在附加限制条件下最小化函数 :math:`L(\beta)` 。 限制条件隐含超平面将所有训练样本 :math:`x_{i}` 正确分类的条件,

.. math::
  \min_{\beta, \beta_{0}} L(\beta) = \frac{1}{2}||\beta||^{2} \text{ subject to } y_{i}(\beta^{T} x_{i} + \beta_{0}) \geq 1 \text{ } \forall i,

式中 :math:`y_{i}` 表示样本的类别标记。

这是一个拉格朗日优化问题，可以通过拉格朗日乘数法得到最优超平面的权重向量 :math:`\beta` 和偏置 :math:`\beta_{0}` 。

源码
===========

.. literalinclude:: ../../../../samples/cpp/tutorial_code/ml/introduction_to_svm/introduction_to_svm.cpp
   :language: cpp
   :linenos:
   :tab-width: 4

解释
===========

1. **建立训练样本**

  本例中的训练样本由分属于两个类别的2维点组成， 其中一类包含一个样本点，另一类包含三个点。

  .. code-block:: cpp

     float labels[4] = {1.0, -1.0, -1.0, -1.0};
     float trainingData[4][2] = {{501, 10}, {255, 10}, {501, 255}, {10, 501}};

  函数 :svms:`CvSVM::train <cvsvm-train>` 要求训练数据储存于float类型的 :basicstructures:`Mat <mat>` 结构中， 因此我们定义了以下矩阵:

  .. code-block:: cpp

     Mat trainingDataMat(3, 2, CV_32FC1, trainingData);
     Mat labelsMat      (3, 1, CV_32FC1, labels);    

2. **设置SVM参数**

   此教程中，我们以可线性分割的分属两类的训练样本简单讲解了SVM的基本原理。 然而，SVM的实际应用情形可能复杂得多 (比如非线性分割数据问题，SVM核函数的选择问题等等)。 总而言之，我们需要在训练之前对SVM做一些参数设定。 这些参数保存在类 :svms:`CvSVMParams <cvsvmparams>` 中。

   .. code-block:: cpp

      CvSVMParams params;
      params.svm_type    = CvSVM::C_SVC;
      params.kernel_type = CvSVM::LINEAR;
      params.term_crit   = cvTermCriteria(CV_TERMCRIT_ITER, 100, 1e-6);

   * *SVM类型*. 这里我们选择了 **CvSVM::C_SVC** 类型，该类型可以用于n-类分类问题 (n :math:`\geq` 2)。 这个参数定义在 *CvSVMParams.svm_type* 属性中.

     .. note::  **CvSVM::C_SVC** 类型的重要特征是它可以处理非完美分类的问题 (及训练数据不可以完全的线性分割)。在本例中这一特征的意义并不大，因为我们的数据是可以线性分割的，我们这里选择它是因为它是最常被使用的SVM类型。

   * *SVM 核类型*. 我们没有讨论核函数，因为对于本例的样本，核函数的讨论没有必要。然而，有必要简单说一下核函数背后的主要思想， 核函数的目的是为了将训练样本映射到更有利于可线性分割的样本集。 映射的结果是增加了样本向量的维度，这一过程通过核函数完成。 此处我们选择的核函数类型是 **CvSVM::LINEAR** 表示不需要进行映射。 该参数由 *CvSVMParams.kernel_type* 属性定义。

   * *算法终止条件*. SVM训练的过程就是一个通过 **迭代** 方式解决约束条件下的二次优化问题，这里我们指定一个最大迭代次数和容许误差，以允许算法在适当的条件下停止计算。 该参数定义在 :oldbasicstructures:`cvTermCriteria <cvtermcriteria>` 结构中。

3. **训练支持向量机**

   调用函数 `CvSVM::train <http://opencv.itseez.com/modules/ml/doc/support_vector_machines.html#cvsvm-train>`_ 来建立SVM模型。

   .. code-block:: cpp

      CvSVM SVM;
      SVM.train(trainingDataMat, labelsMat, Mat(), Mat(), params);

4. **SVM区域分割**

 函数 :svms:`CvSVM::predict <cvsvm-predict>` 通过重建训练完毕的支持向量机来将输入的样本分类。 本例中我们通过该函数给向量空间着色， 及将图像中的每个像素当作卡迪尔平面上的一点，每一点的着色取决于SVM对该点的分类类别：绿色表示标记为1的点，蓝色表示标记为-1的点。 

  .. code-block:: cpp

     Vec3b green(0,255,0), blue (255,0,0);
     
     for (int i = 0; i < image.rows; ++i)
         for (int j = 0; j < image.cols; ++j)
         {
         Mat sampleMat = (Mat_<float>(1,2) << i,j);
         float response = SVM.predict(sampleMat);

         if (response == 1)
            image.at<Vec3b>(j, i)  = green;
         else 
         if (response == -1) 
            image.at<Vec3b>(j, i)  = blue;
         }

5. **支持向量**

   这里用了几个函数来获取支持向量的信息。 函数 :svms:`CvSVM::get_support_vector_count <cvsvm-get-support-vector>` 输出支持向量的数量，函数 :svms:`CvSVM::get_support_vector <cvsvm-get-support-vector>` 根据输入支持向量的索引来获取指定位置的支持向量。 通过这一方法我们找到训练样本的支持向量并突出显示它们。 

   .. code-block:: cpp

      int c     = SVM.get_support_vector_count();

      for (int i = 0; i < c; ++i)
      {
      const float* v = SVM.get_support_vector(i); // get and then highlight with grayscale
      circle(	image,  Point( (int) v[0], (int) v[1]),   6,  Scalar(128, 128, 128), thickness, lineType);
      }

结果
=======

.. container:: enumeratevisibleitemswithsquare

   * 程序创建了一张图像，在其中显示了训练样本，其中一个类显示为白色圆圈，另一个类显示为黑色圆圈。

   * 训练得到SVM，并将图像的每一个像素分类。 分类的结果将图像分为蓝绿两部分，中间线就是最优分割超平面。 

   * 最后支持向量通过灰色边框加重显示。

.. image:: images/result.png
  :alt: The seperated planes
  :align: center 

翻译者
=================
niesu@ `OpenCV中文网站 <http://www.opencv.org.cn>`_  <sisongasg@hotmail.com>