modules/ml/doc/support_vector_machines.rst

   1 Support Vector Machines
   2 =======================
   3
   4 .. highlight:: cpp
   5
   6 Originally, support vector machines (SVM) was a technique for building an optimal binary (2-class) classifier. Later the technique was extended to regression and clustering problems. SVM is a partial case of kernel-based methods. It maps feature vectors into a higher-dimensional space using a kernel function and builds an optimal linear discriminating function in this space or an optimal hyper-plane that fits into the training data. In case of SVM, the kernel is not defined explicitly. Instead, a distance between any 2 points in the hyper-space needs to be defined.
   7
   8 The solution is optimal, which means that the margin between the separating hyper-plane and the nearest feature vectors from both classes (in case of 2-class classifier) is maximal. The feature vectors that are the closest to the hyper-plane are called *support vectors*, which means that the position of other vectors does not affect the hyper-plane (the decision function).
   9
  10 SVM implementation in OpenCV is based on [LibSVM]_.
  11
  12 .. [Burges98] C. Burges. *A tutorial on support vector machines for pattern recognition*, Knowledge Discovery and Data Mining 2(2), 1998 (available online at http://citeseer.ist.psu.edu/burges98tutorial.html)
  13
  14 .. [LibSVM] C.-C. Chang and C.-J. Lin. *LIBSVM: a library for support vector machines*, ACM Transactions on Intelligent Systems and Technology, 2:27:1--27:27, 2011. (http://www.csie.ntu.edu.tw/~cjlin/papers/libsvm.pdf)
  15
  16
  17 CvParamGrid
  18 -----------
  19 .. ocv:struct:: CvParamGrid
  20
  21   The structure represents the logarithmic grid range of statmodel parameters. It is used for optimizing statmodel accuracy by varying model parameters, the accuracy estimate being computed by cross-validation.
  22
  23   .. ocv:member:: double CvParamGrid::min_val
  24
  25      Minimum value of the statmodel parameter.
  26
  27   .. ocv:member:: double CvParamGrid::max_val
  28
  29      Maximum value of the statmodel parameter.
  30
  31   .. ocv:member:: double CvParamGrid::step
  32
  33      Logarithmic step for iterating the statmodel parameter.
  34
  35 The grid determines the following iteration sequence of the statmodel parameter values:
  36
  37 .. math::
  38
  39     (min\_val, min\_val*step, min\_val*{step}^2, \dots,  min\_val*{step}^n),
  40
  41 where :math:`n` is the maximal index satisfying
  42
  43 .. math::
  44
  45     \texttt{min\_val} * \texttt{step} ^n <  \texttt{max\_val}
  46
  47 The grid is logarithmic, so ``step`` must always be greater then 1.
  48
  49 CvParamGrid::CvParamGrid
  50 ------------------------
  51 The constructors.
  52
  53 .. ocv:function:: CvParamGrid::CvParamGrid()
  54
  55 .. ocv:function:: CvParamGrid::CvParamGrid( double min_val, double max_val, double log_step )
  56
  57 The full constructor initializes corresponding members. The default constructor creates a dummy grid:
  58
  59 ::
  60
  61     CvParamGrid::CvParamGrid()
  62     {
  63         min_val = max_val = step = 0;
  64     }
  65
  66 CvParamGrid::check
  67 ------------------
  68 Checks validness of the grid.
  69
  70 .. ocv:function:: bool CvParamGrid::check()
  71
  72 Returns ``true`` if the grid is valid and ``false`` otherwise. The grid is valid if and only if:
  73
  74 * Lower bound of the grid is less then the upper one.
  75 * Lower bound of the grid is positive.
  76 * Grid step is greater then 1.
  77
  78 CvSVMParams
  79 -----------
  80 .. ocv:struct:: CvSVMParams
  81
  82 SVM training parameters.
  83
  84 The structure must be initialized and passed to the training method of :ocv:class:`CvSVM`.
  85
  86 CvSVMParams::CvSVMParams
  87 ------------------------
  88 The constructors.
  89
  90 .. ocv:function:: CvSVMParams::CvSVMParams()
  91
  92 .. ocv:function:: CvSVMParams::CvSVMParams( int svm_type, int kernel_type, double degree, double gamma, double coef0, double Cvalue, double nu, double p, CvMat* class_weights, CvTermCriteria term_crit )
  93
  94     :param svm_type: Type of a SVM formulation. Possible values are:
  95
  96         * **CvSVM::C_SVC** C-Support Vector Classification. ``n``-class classification (``n`` :math:`\geq` 2), allows imperfect separation of classes with penalty multiplier ``C`` for outliers.
  97
  98         * **CvSVM::NU_SVC** :math:`\nu`-Support Vector Classification. ``n``-class classification with possible imperfect separation. Parameter :math:`\nu`  (in the range 0..1, the larger the value, the smoother the decision boundary) is used instead of ``C``.
  99
 100         * **CvSVM::ONE_CLASS** Distribution Estimation (One-class SVM). All the training data are from the same class, SVM builds a boundary that separates the class from the rest of the feature space.
 101
 102         * **CvSVM::EPS_SVR** :math:`\epsilon`-Support Vector Regression. The distance between feature vectors from the training set and the fitting hyper-plane must be less than ``p``. For outliers the penalty multiplier ``C`` is used.
 103
 104         * **CvSVM::NU_SVR** :math:`\nu`-Support Vector Regression. :math:`\nu` is used instead of ``p``.
 105
 106         See [LibSVM]_ for details.
 107
 108     :param kernel_type: Type of a SVM kernel. Possible values are:
 109
 110         * **CvSVM::LINEAR** Linear kernel. No mapping is done, linear discrimination (or regression) is done in the original feature space. It is the fastest option. :math:`K(x_i, x_j) = x_i^T x_j`.
 111
 112         * **CvSVM::POLY** Polynomial kernel: :math:`K(x_i, x_j) = (\gamma x_i^T x_j + coef0)^{degree}, \gamma > 0`.
 113
 114         * **CvSVM::RBF** Radial basis function (RBF), a good choice in most cases. :math:`K(x_i, x_j) = e^{-\gamma ||x_i - x_j||^2}, \gamma > 0`.
 115
 116         * **CvSVM::SIGMOID** Sigmoid kernel: :math:`K(x_i, x_j) = \tanh(\gamma x_i^T x_j + coef0)`.
 117
 118     :param degree: Parameter ``degree`` of a kernel function (POLY).
 119
 120     :param gamma: Parameter :math:`\gamma` of a kernel function (POLY / RBF / SIGMOID).
 121
 122     :param coef0: Parameter ``coef0`` of a kernel function (POLY / SIGMOID).
 123
 124     :param Cvalue: Parameter ``C`` of a SVM optimization problem (C_SVC / EPS_SVR / NU_SVR).
 125
 126     :param nu: Parameter :math:`\nu` of a SVM optimization problem (NU_SVC / ONE_CLASS / NU_SVR).
 127
 128     :param p: Parameter :math:`\epsilon` of a SVM optimization problem (EPS_SVR).
 129
 130     :param class_weights: Optional weights in the C_SVC problem , assigned to particular classes. They are multiplied by ``C`` so the parameter ``C`` of class ``#i`` becomes :math:`class\_weights_i * C`. Thus these weights affect the misclassification penalty for different classes. The larger weight, the larger penalty on misclassification of data from the corresponding class.
 131
 132     :param term_crit: Termination criteria of the iterative SVM training procedure which solves a partial case of constrained quadratic optimization problem. You can specify tolerance and/or the maximum number of iterations.
 133
 134 The default constructor initialize the structure with following values:
 135
 136 ::
 137
 138     CvSVMParams::CvSVMParams() :
 139         svm_type(CvSVM::C_SVC), kernel_type(CvSVM::RBF), degree(0),
 140         gamma(1), coef0(0), C(1), nu(0), p(0), class_weights(0)
 141     {
 142         term_crit = cvTermCriteria( CV_TERMCRIT_ITER+CV_TERMCRIT_EPS, 1000, FLT_EPSILON );
 143     }
 144
 145
 146
 147 CvSVM
 148 -----
 149 .. ocv:class:: CvSVM : public CvStatModel
 150
 151 Support Vector Machines.
 152
 153 CvSVM::CvSVM
 154 ------------
 155 Default and training constructors.
 156
 157 .. ocv:function:: CvSVM::CvSVM()
 158
 159 .. ocv:function:: CvSVM::CvSVM( const Mat& trainData, const Mat& responses, const Mat& varIdx=Mat(), const Mat& sampleIdx=Mat(), CvSVMParams params=CvSVMParams() )
 160
 161 .. ocv:function:: CvSVM::CvSVM( const CvMat* trainData, const CvMat* responses, const CvMat* varIdx=0, const CvMat* sampleIdx=0, CvSVMParams params=CvSVMParams() )
 162
 163 .. ocv:pyfunction:: cv2.SVM([trainData, responses[, varIdx[, sampleIdx[, params]]]]) -> <SVM object>
 164
 165 The constructors follow conventions of :ocv:func:`CvStatModel::CvStatModel`. See :ocv:func:`CvStatModel::train` for parameters descriptions.
 166
 167 CvSVM::train
 168 ------------
 169 Trains an SVM.
 170
 171 .. ocv:function:: bool CvSVM::train( const Mat& trainData, const Mat& responses, const Mat& varIdx=Mat(), const Mat& sampleIdx=Mat(), CvSVMParams params=CvSVMParams() )
 172
 173 .. ocv:function:: bool CvSVM::train( const CvMat* trainData, const CvMat* responses, const CvMat* varIdx=0, const CvMat* sampleIdx=0, CvSVMParams params=CvSVMParams() )
 174
 175 .. ocv:pyfunction:: cv2.SVM.train(trainData, responses[, varIdx[, sampleIdx[, params]]]) -> retval
 176
 177 The method trains the SVM model. It follows the conventions of the generic :ocv:func:`CvStatModel::train` approach with the following limitations:
 178
 179 * Only the ``CV_ROW_SAMPLE`` data layout is supported.
 180
 181 * Input variables are all ordered.
 182
 183 * Output variables can be either categorical (``params.svm_type=CvSVM::C_SVC`` or ``params.svm_type=CvSVM::NU_SVC``), or ordered (``params.svm_type=CvSVM::EPS_SVR`` or ``params.svm_type=CvSVM::NU_SVR``), or not required at all (``params.svm_type=CvSVM::ONE_CLASS``).
 184
 185 * Missing measurements are not supported.
 186
 187 All the other parameters are gathered in the
 188 :ocv:class:`CvSVMParams` structure.
 189
 190
 191 CvSVM::train_auto
 192 -----------------
 193 Trains an SVM with optimal parameters.
 194
 195 .. ocv:function:: bool CvSVM::train_auto( const Mat& trainData, const Mat& responses, const Mat& varIdx, const Mat& sampleIdx, CvSVMParams params, int k_fold = 10, CvParamGrid Cgrid = CvSVM::get_default_grid(CvSVM::C), CvParamGrid gammaGrid = CvSVM::get_default_grid(CvSVM::GAMMA), CvParamGrid pGrid = CvSVM::get_default_grid(CvSVM::P), CvParamGrid nuGrid  = CvSVM::get_default_grid(CvSVM::NU), CvParamGrid coeffGrid = CvSVM::get_default_grid(CvSVM::COEF), CvParamGrid degreeGrid = CvSVM::get_default_grid(CvSVM::DEGREE), bool balanced=false)
 196
 197 .. ocv:function:: bool CvSVM::train_auto( const CvMat* trainData, const CvMat* responses, const CvMat* varIdx, const CvMat* sampleIdx, CvSVMParams params, int kfold = 10, CvParamGrid Cgrid = get_default_grid(CvSVM::C), CvParamGrid gammaGrid = get_default_grid(CvSVM::GAMMA), CvParamGrid pGrid = get_default_grid(CvSVM::P), CvParamGrid nuGrid = get_default_grid(CvSVM::NU), CvParamGrid coeffGrid = get_default_grid(CvSVM::COEF), CvParamGrid degreeGrid = get_default_grid(CvSVM::DEGREE), bool balanced=false )
 198
 199 .. ocv:pyfunction:: cv2.SVM.train_auto(trainData, responses, varIdx, sampleIdx, params[, k_fold[, Cgrid[, gammaGrid[, pGrid[, nuGrid[, coeffGrid[, degreeGrid[, balanced]]]]]]]]) -> retval
 200
 201     :param k_fold: Cross-validation parameter. The training set is divided into ``k_fold`` subsets. One subset is used to test the model, the others form the train set. So, the SVM algorithm is executed ``k_fold`` times.
 202
 203     :param \*Grid: Iteration grid for the corresponding SVM parameter.
 204
 205     :param balanced: If ``true`` and the problem is 2-class classification then the method creates more balanced cross-validation subsets that is proportions between classes in subsets are close to such proportion in the whole train dataset.
 206
 207 The method trains the SVM model automatically by choosing the optimal
 208 parameters ``C``, ``gamma``, ``p``, ``nu``, ``coef0``, ``degree`` from
 209 :ocv:class:`CvSVMParams`. Parameters are considered optimal
 210 when the cross-validation estimate of the test set error
 211 is minimal.
 212
 213 If there is no need to optimize a parameter, the corresponding grid step should be set to any value less than or equal to 1. For example, to avoid optimization in ``gamma``, set ``gamma_grid.step = 0``, ``gamma_grid.min_val``, ``gamma_grid.max_val`` as arbitrary numbers. In this case, the value ``params.gamma`` is taken for ``gamma``.
 214
 215 And, finally, if the optimization in a parameter is required but
 216 the corresponding grid is unknown, you may call the function :ocv:func:`CvSVM::get_default_grid`. To generate a grid, for example, for ``gamma``, call ``CvSVM::get_default_grid(CvSVM::GAMMA)``.
 217
 218 This function works for the classification
 219 (``params.svm_type=CvSVM::C_SVC`` or ``params.svm_type=CvSVM::NU_SVC``)
 220 as well as for the regression
 221 (``params.svm_type=CvSVM::EPS_SVR`` or ``params.svm_type=CvSVM::NU_SVR``). If ``params.svm_type=CvSVM::ONE_CLASS``, no optimization is made and the usual SVM with parameters specified in ``params`` is executed.
 222
 223 CvSVM::predict
 224 --------------
 225 Predicts the response for input sample(s).
 226
 227 .. ocv:function:: float CvSVM::predict( const Mat& sample, bool returnDFVal=false ) const
 228
 229 .. ocv:function:: float CvSVM::predict( const CvMat* sample, bool returnDFVal=false ) const
 230
 231 .. ocv:function:: float CvSVM::predict( const CvMat* samples, CvMat* results ) const
 232
 233 .. ocv:pyfunction:: cv2.SVM.predict(sample[, returnDFVal]) -> retval
 234
 235 .. ocv:pyfunction:: cv2.SVM.predict_all(samples[, results]) -> results
 236
 237     :param sample: Input sample for prediction.
 238
 239     :param samples: Input samples for prediction.
 240
 241     :param returnDFVal: Specifies a type of the return value. If ``true`` and the problem is 2-class classification then the method returns the decision function value that is signed distance to the margin, else the function returns a class label (classification) or estimated function value (regression).
 242
 243     :param results: Output prediction responses for corresponding samples.
 244
 245 If you pass one sample then prediction result is returned. If you want to get responses for several samples then you should pass the ``results`` matrix where prediction results will be stored.
 246
 247 The function is parallelized with the TBB library.
 248
 249
 250 CvSVM::get_default_grid
 251 -----------------------
 252 Generates a grid for SVM parameters.
 253
 254 .. ocv:function:: CvParamGrid CvSVM::get_default_grid( int param_id )
 255
 256     :param param_id: SVM parameters IDs that must be one of the following:
 257
 258             * **CvSVM::C**
 259
 260             * **CvSVM::GAMMA**
 261
 262             * **CvSVM::P**
 263
 264             * **CvSVM::NU**
 265
 266             * **CvSVM::COEF**
 267
 268             * **CvSVM::DEGREE**
 269
 270         The grid is generated for the parameter with this ID.
 271
 272 The function generates a grid for the specified parameter of the SVM algorithm. The grid may be passed to the function :ocv:func:`CvSVM::train_auto`.
 273
 274 CvSVM::get_params
 275 -----------------
 276 Returns the current SVM parameters.
 277
 278 .. ocv:function:: CvSVMParams CvSVM::get_params() const
 279
 280 This function may be used to get the optimal parameters obtained while automatically training :ocv:func:`CvSVM::train_auto`.
 281
 282 CvSVM::get_support_vector
 283 --------------------------
 284 Retrieves a number of support vectors and the particular vector.
 285
 286 .. ocv:function:: int CvSVM::get_support_vector_count() const
 287
 288 .. ocv:function:: const float* CvSVM::get_support_vector(int i) const
 289
 290 .. ocv:pyfunction:: cv2.SVM.get_support_vector_count() -> retval
 291
 292     :param i: Index of the particular support vector.
 293
 294 The methods can be used to retrieve a set of support vectors.
 295
 296 CvSVM::get_var_count
 297 --------------------
 298 Returns the number of used features (variables count).
 299
 300 .. ocv:function:: int CvSVM::get_var_count() const
 301
 302 .. ocv:pyfunction:: cv2.SVM.get_var_count() -> retval