Gaussian mixture models: k-means on steroids

Gaussian mixture models behavior on generated datasets

Let’s first apply a Gaussian mixture model on some datasets. For this purpose, Rmixmod library (I recommend the article on Rxmimod in Journal of Statistical Software for further reading) is used with its default parameters (only the number of clusters is specified).

library("Rmixmod")

processMixmod <- function(data) {
    d = data %>% select(x, y)
    x = mixmodCluster(d, 2)
    x["bestResult"]["partition"]
}

dataMixmod = data %>%
             group_by(dataset) %>%
             do(data.frame(., cluster = factor(processMixmod(.))))

scatterPlotWithLabels(dataMixmod)

One can view from the plots that the models fit better the datasets than k-means which only fits well the first dataset. In particular, the first five datasets are generated by a mixture of Gaussians, hence the Gaussian mixture models works well. The other datasets, except than the two classes of uniform data are not fitted correctly since they are generated differently (by the way, the last dataset exhibits no classes).

The internal criterion optimized by the algorithm used, namely EM, explains why it works for the mixture of Gaussians.

EM and CEM algorithms

The EM algorithm is an iterative algorithm which iterates over two steps: an “expectation” step and a “maximisation” step, hence his name. The CEM algorithm includes an other step of “classification” between the two steps of the EM algorithm. The two algorithms differ also slightly by their criterion.

CEM algorithm as an extension of k-means

The CEM algorithm applied on a mixture of Gaussians with some assumptions on the Gaussians (no covariance and equal variance) and on the mixture (equal proportions) is actually the same as the k-means algorithm. With these assumptions, the criterions are the same (see the previous post on kmeans in this series on clustering), and it can be shown that the steps are also the same.

Let’s see this in practice when fitting CEM with a mixture of Gaussians with diagonal variance matrices and equal proportions, volumes and shapes (see page 25 of the reference manual of Rmixmod):

< !-- Note that `scikit-learn uses the EM algorithm < https://scikit-learn.org/stable/modules/mixture.html>`_ to learn Gaussian mixtures models. –>

library("Rmixmod")

processMixmod2 <- function(data) {
    d = data %>% select(x, y)
    x = mixmodCluster(d, 2,
                      models=mixmodGaussianModel(listModels=c("Gaussian_p_L_I")),
                      strategy=new("Strategy", algo="CEM"))
    x["bestResult"]["partition"]
}

dataMixmod = data %>%
             group_by(dataset) %>%
             do(data.frame(., cluster = factor(processMixmod2(.))))

scatterPlotWithLabels(dataMixmod)

We obtain the same results than with k-means.

It seems that since Gaussian mixture models are more general, there is no reason to use k-means. However, it should be noted that k-means has less parameters to estimate and is thus faster and requires less memory. Let’s explore this.

< !-- Algorithm complexity --> < !-- ==================== -->

Number of parameters to estimate

When fitting a mixture of Gaussians, we have to estimate the proportions of the mixture, and the parameters of each Gaussian:

• Since the proportions sum to one, we only have to estimate \(K-1\) proportions, with \(K\) the number of Gaussians.
• We also have to estimate a mean for each Gaussian, thus \(K d\) parameters with \(d\) the number of dimensions.
• The covariance matrix is a \(d \times d\) square matrix which is symmetric (the entries below the main diagonal are the same as the entries upper the main diagonal). We have thus \(\frac{d (d-1)}{2}\) values to estimate for each Gaussian.

Overall, we have, for the general form of the mixture of Gaussians (without any conditions) : \(K-1 + Kd + \frac{Kd(d-1)}{2}\) parameters to estimate, with:

• \(K\) the number of Gaussians (or classes)
• \(d\) the number of variables

If we set conditions on the model, we can lower the number of parameters to estimate. For instance, if we assume that the covariance matrices are diagonal with equal variance (a scalar times the identity matrix) and that the proportions of the mixture are the same, we have: \(d + 1\) parameters to estimate. It corresponds to the assumptions of k-means.

To sum up

• Gaussian mixture models with the CEM algorithm can be seen as a generalisation of k-means: whereas k-means fit data generated by a mixture of Gaussians with same proportions and diagonal covariance matrices, Gaussian mixture models allows to enforce other assumptions on the proportions of the mixture and on the covariance matrices of the Gaussians.
• Setting conditions on the parameters of the Gaussians and the mixture allows to reduce the number of parameters to estimate and thus reduce the runtime of the algorithm.
• Several algorithms intend to fit a mixture of Gaussians. For instance, the EM algorithm estimates the parameters of the mixture and the classes are found a posteriori. The CEM algorithm estimates instead the parameters and the clusters assignations simultaneously, allowing a boost on the execution time.