11
$\begingroup$

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?

$\endgroup$
17
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I like the distinction between models, estimators, and algorithms in this answer, but I think the presentation of K-means as involving no assumptions about the data generating process is misleading. As my answer shows, it can be derived as the limiting case of gaussian mixture models with known spherical covariance whose precision approaches infinity -- quite a strong assumption! Maybe it's better to say K-means can be useful even if you don't believe its assumptions about the data generating process. $\endgroup$ – jkpate Sep 28 at 21:59
  • 3
    $\begingroup$ I don't agree. Historically, $k$-means was invented without reference to Gaussian models, eg, this is the first published use of the name projecteuclid.org/euclid.bsmsp/1200512992 and the earliest use is also not distribution-based. It can be reconstructed as an algorithm for a Gaussian model, as you note in your answer, but only in the case of precision going to infinity. It did not originally have assumptions about the data generating process and it doesn't need them. $\endgroup$ – Thomas Lumley Sep 28 at 22:33
  • 2
    $\begingroup$ Early uses may not have realized that it made these assumptions, but we can see that it does make these assumptions. There is no inference without a model, even if the model is not explicit or well understood. $\endgroup$ – jkpate Sep 28 at 22:36
  • 2
    $\begingroup$ There is no inference without a model, but there is inference without a Gaussian mixture model. I linked to two papers that demonstrate inference for k-means cluster under the model that the data are an iid sample from some distribution. $\endgroup$ – Thomas Lumley Sep 29 at 3:50
  • 3
    $\begingroup$ @jkpate: $\bar x$ is the MLE for $\mu$ for Gaussian data. Does that mean every time we look at a mean, we are assuming the data is Gaussian? No. But if we say approximately 95% of the data are within two standard deviations without checking this empirically, then we are applying the Gaussian assumption. With that context, very few data analysts apply Gaussian assumptions you could apply to the K-means approach. $\endgroup$ – Cliff AB Sep 29 at 19:55
9
$\begingroup$

@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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ best answer. only real difference between the two methods is that k-means makes crisp partitions while GMM makes soft partitions. $\endgroup$ – carlo Sep 29 at 9:31
8
$\begingroup$

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}$.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

$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).

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.