In cluster analysis, how does Gaussian mixture model differ from K Means when we know the clusters are spherical?

Question

I understand how main difference between K-mean and Gaussian mixture model (GMM) is that K-Mean only detects spherical clusters and GMM can adjust its self to elliptic shape cluster. However, how do they differ when GMM has spherical covariance matrices?

Answer 1

Ok, we need to start off by talking about models and estimators and algorithms.

• A model is a set of probability distributions, usually chosen because you think the data came from a distribution like one in the set. Models typically have parameters that specify which model you mean from the set. I'll write $\theta$ for the parameters
• An estimator of a parameter is something you can compute from the data that you think will be close to the parameter. Write $\hat\theta$ for an estimator of $\theta$
• An algorithm is a recipe for computing something from the data, usually something you hope will be useful.

The Gaussian mixture model is a model. It is an assumption or approximation to how the data (and future data, often) were generated. Data from a Gaussian mixture model tend to fall into elliptical (or spherical) clumps

$k$-means is an algorithm. Given a data set, it divides it into $k$ clusters in a way that attempts to minimise the average Euclidean distance from a point to the centre of its clusters.

There's no necessary relationship between the two, but they are at least good friends. If your data are a good fit to a spherical Gaussian mixture model they come in roughly spherical clumps centered at the means of each mixture component. That's the sort of data where $k$-means clustering does well: it will tend to find clusters that each correspond to a mixture component, with cluster centres close to the mixture means.

However, you can use $k$-means clustering without any assumption about the data-generating process. As with other clustering tools, it can be used just to chop up data into convenient and relatively homogenous pieces, with no philosophical commitment to those pieces being real things (eg, for market segmentation). You can prove things about what $k$-means estimates without assuming mixture models (eg, this and this by David Pollard)

You can fit Gaussian mixture models by maximum likelihood, which is a different estimator and different algorithm than $k$-means. Or with Bayesian estimators and their corresponding algorithms (see eg)

So: spherical Gaussian mixture models are quite closely connected to $k$-means clustering in some ways. In other ways they are not just different things but different kinds of things.

Answer 2

In short, $k$-means can be viewed as the limiting case of Expectation-Maximization for spherical Gaussian Mixture Models as the trace of the covariance matrices goes to zero. What follows is a presentation of portions of sections 9.1 and 9.3 of Pattern Recognition and Machine Learning.

$K$-means

$K$-means seeks to find a binary assignment matrix $[r_{j,i}]$, with exactly one non-zero value in each row, one row for each of $N$ observations, and one column for each of $K$ clusters. The algorithm itself amounts to picking initial mean vectors $\mu_i$, and then alternating between the following two steps:

• E-step: For each observation $j$, set $r_{j,k^*}=1$ and $r_{j, k} = 0$ for $k \neq k^*$, where $k^*$ is the index of the closest cluster center: \begin{align} k^* = \underset{k}{\text{argmin}}~ ||x_j - \mu_k||^2 \end{align}
• M-step: For each cluster $j$, re-estimate the cluster center as the mean of the points in that cluster: \begin{align} \mu_k^{\text{new}} = \frac{\sum_{j=1}^N r_{j,k}x_j}{\sum_{j=1}^N r_{j,k}} \end{align}

Expectation-Maximization for Gaussian Mixture Models

Next, consider the standard Expectation-Maximization steps for Gaussian Mixture models, after picking initial mean vectors $\mu_k$, covariances $\Sigma_k$, and mixing coefficients $\pi_k$:

• E-step: For each observation $j$, evaluate the "responsibility" of each cluster $k$ for that observation: \begin{align} r_{j,k} & = \frac{\pi_k \mathcal{N}(x_j | \mu_k, \sigma_k)}{\sum_{i=1}^K\pi_i \mathcal{N}(x_j | \mu_i, \sigma_i)} \end{align}
• M-step: For each cluster $k$, re-estimate the parameters $\mu_k$, $\Sigma_k$, $\pi_k$ as a weighted average using the responsibilities as weights: \begin{align} \mu_k^{\text{new}} & = \frac{1}{\sum_{j=1}^N r_{j, k}} \sum_{j=1}^N r_{j,k} x_j \\ \Sigma_k^{\text{new}} & = \frac{1}{\sum_{j=1}^N r_{j, k}} \sum_{j=1}^N r_{j,k}( x_j - \mu_k^{\text{new}})(x_j - \mu_k^{\text{new}})^T \\ \pi_k^{\text{new}} & = \frac{\sum_{j=1}^N r_{j, k}}{N} \end{align}

If we compare these update equations to the update equations for $K$-means, we see that, in both, $r_{j,i}$ serves as a probability distribution over clusters for each observation. The primary difference is that in $K$-means, the $r_{j,\cdot}$ is a probability distribution that gives zero probability to all but one cluster, while EM for GMMs gives non-zero probability to every cluster.

Now consider EM for Gaussians in which we treat the covariance matrix as observed and of the form $\epsilon\textbf{I}$. Because $\mathcal{N}(x | \mu, \epsilon\textbf{I}) \propto \exp\left(-\frac{1}{2\epsilon}||x - \mu||^2\right)$, the M-step now computes the responsibilities as: \begin{align} r_{j,k} & = \frac{\pi_k \exp\left(-\frac{1}{2\epsilon}||x_j - \mu_k||^2\right)}{ \sum_{i=1}^K \pi_i \exp\left(-\frac{1}{2\epsilon}||x_j - \mu_i||^2\right) } \end{align} Due to the exponential in the numerator, $r_{j, k}$ here approaches the $K$-means $r_{j, k}$ as $\epsilon$ goes to zero. Moreover, as we are now treating the covariances $\Sigma_k$ as observed, there is no need to re-estimate $\Sigma_k$; it's simply $\epsilon\text{I}$.

Answer 3

@ThomasLumley's answer is excellent.

For a concrete difference, consider that the only thing you get from $k$-means is a partition. The output from fitting a GMM can include much more than that. For example, you can compute the probability a given point came from each of the different fitted components.

A GMM can also fit and return overlapping clusters, whereas $k$-means necessarily imposes a hard break between clusters.

Answer 4

$K$-means can be derived as a Maximum Likelihood (ML) estimator of a fixed partition model with Gaussian distributions with equal and spherical covariance matrices. A fixed partition model has a parameter for every observation that says to which cluster it belongs. Note that this is not an i.i.d. model, because the distribution is different for observations that belong to different clusters. Also note that this is not a standard ML problem, because the number of parameters grows with the number of points, so standard asymptotic results for ML estimators do not hold. In fact $K$-means is a counterexample for the claim that all ML estimators are consistent. If you have one-dimensional data, 50% from a ${\cal N}(-1,1)$-distribution and 50% from a ${\cal N}(1,1)$-distribution, the true difference between the means is 2, however $K$-means will overestimate that, because it will for $n\to\infty$ assign all observations smaller than 0 to the lower mean cluster and all larger than 0 to the higher mean cluster. The estimated means will then be means from truncated Gaussians (e.g., on the lower side, the left part of the lower mean Gaussian truncated at 0 plus the left part of the higher mean Gaussian truncated at 0), not from the original Gaussians. See P.G. Bryant, J. Williamson, Asymptotic behaviour of classification maximum likelihood estimates, Biometrika, 65 (1978), pp. 273-281.

The Gaussian mixture model models data as i.i.d., with a probability of $\pi_k$, using fkpate's notation, for each observation to have come from cluster $k$. It estimates the cluster means as weighted means, not assigning observations in a crisp manner to one of the clusters. In this way it avoids the problem explained above and it will be consistent as ML estimator (in general this is problematic because of issues of degeneration of the covariance matrix, however not if you assume them spherical and equal).

In practice, if you generate observations from a number of Gaussians with same spherical covariance matrix and different means, $K$-means will therefore overestimate the distances between the means, whereas the ML-estimator for the mixture model will not. It will be much slower though, if you have a big dataset, because crisp point assignment makes the $K$-means algorithm much faster (if somewhat less stable, but you can repeat it umpteen times before the Gaussian mixture EM has finished).