modules/legacy/doc/expectation_maximization.rst

   1 Expectation Maximization
   2 ========================
   3
   4 This section describes obsolete ``C`` interface of EM algorithm. Details of the algorithm and its ``C++`` interface can be found in the other section :ref:`ML_Expectation Maximization`.
   5
   6 .. highlight:: cpp
   7
   8 .. note::
   9
  10    * An example on using the Expectation Maximalization algorithm can be found at opencv_source_code/samples/cpp/em.cpp
  11
  12    * (Python) An example using Expectation Maximalization for Gaussian Mixing can be found at opencv_source_code/samples/python2/gaussian_mix.py
  13
  14
  15 CvEMParams
  16 ----------
  17 .. ocv:struct:: CvEMParams
  18
  19 Parameters of the EM algorithm. All parameters are public. You can initialize them by a constructor and then override some of them directly if you want.
  20
  21 CvEMParams::CvEMParams
  22 ----------------------
  23 The constructors
  24
  25 .. ocv:function:: CvEMParams::CvEMParams()
  26
  27 .. ocv:function:: CvEMParams::CvEMParams( int nclusters, int cov_mat_type=EM::COV_MAT_DIAGONAL, int start_step=EM::START_AUTO_STEP, CvTermCriteria term_crit=cvTermCriteria(CV_TERMCRIT_ITER+CV_TERMCRIT_EPS, 100, FLT_EPSILON), const CvMat* probs=0, const CvMat* weights=0, const CvMat* means=0, const CvMat** covs=0 )
  28
  29     :param nclusters: The number of mixture components in the Gaussian mixture model. Some of EM implementation could determine the optimal number of mixtures within a specified value range, but that is not the case in ML yet.
  30
  31     :param cov_mat_type: Constraint on covariance matrices which defines type of matrices. Possible values are:
  32
  33         * **CvEM::COV_MAT_SPHERICAL** A scaled identity matrix :math:`\mu_k * I`. There is the only parameter :math:`\mu_k` to be estimated for each matrix. The option may be used in special cases, when the constraint is relevant, or as a first step in the optimization (for example in case when the data is preprocessed with PCA). The results of such preliminary estimation may be passed again to the optimization procedure, this time with ``cov_mat_type=CvEM::COV_MAT_DIAGONAL``.
  34
  35         * **CvEM::COV_MAT_DIAGONAL** A diagonal matrix with positive diagonal elements. The number of free parameters is ``d`` for each matrix. This is most commonly used option yielding good estimation results.
  36
  37         * **CvEM::COV_MAT_GENERIC** A symmetric positively defined matrix. The number of free parameters in each matrix is about :math:`d^2/2`. It is not recommended to use this option, unless there is pretty accurate initial estimation of the parameters and/or a huge number of training samples.
  38
  39     :param start_step: The start step of the EM algorithm:
  40
  41         * **CvEM::START_E_STEP** Start with Expectation step. You need to provide means :math:`a_k` of mixture components to use this option. Optionally you can pass weights :math:`\pi_k` and covariance matrices :math:`S_k` of mixture components.
  42         * **CvEM::START_M_STEP** Start with Maximization step. You need to provide initial probabilities :math:`p_{i,k}` to use this option.
  43         * **CvEM::START_AUTO_STEP** Start with Expectation step. You need not provide any parameters because they will be estimated by the kmeans algorithm.
  44
  45     :param term_crit: The termination criteria of the EM algorithm. The EM algorithm can be terminated by the number of iterations ``term_crit.max_iter`` (number of M-steps) or when relative change of likelihood logarithm is less than ``term_crit.epsilon``.
  46
  47     :param probs: Initial probabilities :math:`p_{i,k}` of sample :math:`i` to belong to mixture component :math:`k`. It is a floating-point matrix of :math:`nsamples \times nclusters` size. It is used and must be not NULL only when ``start_step=CvEM::START_M_STEP``.
  48
  49     :param weights: Initial weights :math:`\pi_k` of mixture components. It is a floating-point vector with :math:`nclusters` elements. It is used (if not NULL) only when ``start_step=CvEM::START_E_STEP``.
  50
  51     :param means: Initial means :math:`a_k` of mixture components. It is a floating-point matrix of :math:`nclusters \times dims` size. It is used used and must be not NULL only when ``start_step=CvEM::START_E_STEP``.
  52
  53     :param covs: Initial covariance matrices :math:`S_k` of mixture components. Each of covariance matrices is a valid square floating-point matrix of :math:`dims \times dims` size. It is used (if not NULL) only when ``start_step=CvEM::START_E_STEP``.
  54
  55 The default constructor represents a rough rule-of-the-thumb:
  56
  57 ::
  58
  59     CvEMParams() : nclusters(10), cov_mat_type(1/*CvEM::COV_MAT_DIAGONAL*/),
  60         start_step(0/*CvEM::START_AUTO_STEP*/), probs(0), weights(0), means(0), covs(0)
  61     {
  62         term_crit=cvTermCriteria( CV_TERMCRIT_ITER+CV_TERMCRIT_EPS, 100, FLT_EPSILON );
  63     }
  64
  65
  66 With another constructor it is possible to override a variety of parameters from a single number of mixtures (the only essential problem-dependent parameter) to initial values for the mixture parameters.
  67
  68
  69 CvEM
  70 ----
  71 .. ocv:class:: CvEM : public CvStatModel
  72
  73     The class implements the EM algorithm as described in the beginning of the section :ref:`ML_Expectation Maximization`.
  74
  75
  76 CvEM::train
  77 -----------
  78 Estimates the Gaussian mixture parameters from a sample set.
  79
  80 .. ocv:function:: bool CvEM::train( const Mat& samples, const Mat& sampleIdx=Mat(), CvEMParams params=CvEMParams(), Mat* labels=0 )
  81
  82 .. ocv:function:: bool CvEM::train( const CvMat* samples, const CvMat* sampleIdx=0, CvEMParams params=CvEMParams(), CvMat* labels=0 )
  83
  84     :param samples: Samples from which the Gaussian mixture model will be estimated.
  85
  86     :param sampleIdx: Mask of samples to use. All samples are used by default.
  87
  88     :param params: Parameters of the EM algorithm.
  89
  90     :param labels: The optional output "class label" for each sample: :math:`\texttt{labels}_i=\texttt{arg max}_k(p_{i,k}), i=1..N` (indices of the most probable mixture component for each sample).
  91
  92 Unlike many of the ML models, EM is an unsupervised learning algorithm and it does not take responses (class labels or function values) as input. Instead, it computes the
  93 *Maximum Likelihood Estimate* of the Gaussian mixture parameters from an input sample set, stores all the parameters inside the structure:
  94 :math:`p_{i,k}` in ``probs``,
  95 :math:`a_k` in ``means`` ,
  96 :math:`S_k` in ``covs[k]``,
  97 :math:`\pi_k` in ``weights`` , and optionally computes the output "class label" for each sample:
  98 :math:`\texttt{labels}_i=\texttt{arg max}_k(p_{i,k}), i=1..N` (indices of the most probable mixture component for each sample).
  99
 100 The trained model can be used further for prediction, just like any other classifier. The trained model is similar to the
 101 :ocv:class:`CvNormalBayesClassifier`.
 102
 103 For an example of clustering random samples of the multi-Gaussian distribution using EM, see ``em.cpp`` sample in the OpenCV distribution.
 104
 105
 106 CvEM::predict
 107 -------------
 108 Returns a mixture component index of a sample.
 109
 110 .. ocv:function:: float CvEM::predict( const Mat& sample, Mat* probs=0 ) const
 111
 112 .. ocv:function:: float CvEM::predict( const CvMat* sample, CvMat* probs ) const
 113
 114     :param sample: A sample for classification.
 115
 116     :param probs: If it is not null then the method will write posterior probabilities of each component given the sample data to this parameter.
 117
 118
 119 CvEM::getNClusters
 120 ------------------
 121 Returns the number of mixture components :math:`M` in the Gaussian mixture model.
 122
 123 .. ocv:function:: int CvEM::getNClusters() const
 124
 125 .. ocv:function:: int CvEM::get_nclusters() const
 126
 127
 128 CvEM::getMeans
 129 ------------------
 130 Returns mixture means :math:`a_k`.
 131
 132 .. ocv:function:: Mat CvEM::getMeans() const
 133
 134 .. ocv:function:: const CvMat* CvEM::get_means() const
 135
 136
 137 CvEM::getCovs
 138 -------------
 139 Returns mixture covariance matrices :math:`S_k`.
 140
 141 .. ocv:function:: void CvEM::getCovs(std::vector<cv::Mat>& covs) const
 142
 143 .. ocv:function:: const CvMat** CvEM::get_covs() const
 144
 145
 146 CvEM::getWeights
 147 ----------------
 148 Returns mixture weights :math:`\pi_k`.
 149
 150 .. ocv:function:: Mat CvEM::getWeights() const
 151
 152 .. ocv:function:: const CvMat* CvEM::get_weights() const
 153
 154
 155 CvEM::getProbs
 156 --------------
 157 Returns vectors of probabilities for each training sample.
 158
 159 .. ocv:function:: Mat CvEM::getProbs() const
 160
 161 .. ocv:function:: const CvMat* CvEM::get_probs() const
 162
 163 For each training sample :math:`i` (that have been passed to the constructor or to :ocv:func:`CvEM::train`) returns probabilities :math:`p_{i,k}` to belong to a mixture component :math:`k`.
 164
 165
 166 CvEM::getLikelihood
 167 -------------------
 168 Returns logarithm of likelihood.
 169
 170 .. ocv:function:: double CvEM::getLikelihood() const
 171
 172 .. ocv:function:: double CvEM::get_log_likelihood() const
 173
 174
 175 CvEM::write
 176 -----------
 177 Writes the trained Gaussian mixture model to the file storage.
 178
 179 .. ocv:function:: void CvEM::write( CvFileStorage* fs, const char* name ) const
 180
 181     :param fs: A file storage where the model will be written.
 182     :param name: A name of the file node where the model data will be written.
 183
 184
 185 CvEM::read
 186 -----------------
 187 Reads the trained Gaussian mixture model from the file storage.
 188
 189 .. ocv:function:: void CvEM::read( CvFileStorage* fs, CvFileNode* node )
 190
 191     :param fs: A file storage with the trained model.
 192
 193     :param node: The parent map. If it is NULL, the function searches a node with parameters in all the top-level nodes (streams), starting with the first one.