25
$\begingroup$

I'm reading Bishop on EM algorithm for GMM and the relationship between GMM and k-means.

In this book it says that k-means is a hard assign version of GMM. I'm wondering does that imply that if the data I'm trying to cluster are not Gaussian, I can't use k-means (or at least it's not suitable to use)? For example, what if the data are images of handwritten digits, consisting of 8*8 pixels each with value 0 or 1 (and assume they are independent thus it should be mixture of Bernoulli)?

I'm a little bit confused on this and will appreciate any thoughts.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ If you are asking whether it is valid to perform k-means clustering on non-normal data, the answer is yes if the data are assumed to be continuous. Binary data isn't continuous. Some people do k-means on such data, which thing is heuristically permissible, but theoretically invalid. $\endgroup$
    – ttnphns
    Sep 7, 2013 at 11:12
  • $\begingroup$ There's no probability model for k-means so there's no normality assumption to invalidate. (doesn't mean it will work well though) $\endgroup$
    – conjectures
    Sep 8, 2013 at 19:34
  • 1
    $\begingroup$ @conjectures Hmm... But k-menas is equivalent to GMM, and GMM assumes normal. $\endgroup$
    – Eddie Xie
    Sep 9, 2013 at 1:54
  • $\begingroup$ @ttnphns Thanks for your answer! So I guess if I use TF-IDF to transfer text into scores and make it continuous then I can apply and it's valid? $\endgroup$
    – Eddie Xie
    Sep 9, 2013 at 1:56
  • $\begingroup$ I suddenly realize that GMM is mixture (sum of) a few gaussians and it should able to express whatever distribution given enough mixtures. Thus, even GMM and K-means are equivalent does not mean K-means can't use non-normal data because GMM can express whatever distribution. Is that correct? $\endgroup$
    – Eddie Xie
    Sep 9, 2013 at 3:29

2 Answers 2

Reset to default
25
$\begingroup$

In typical EM GMM situations, one does take variance and covariance into account. This is not done in k-means.

But indeed, one of the popular heuristics for k-means (note: k-means is a problem, not an algorithm) - the Lloyd algorithm - is essentially an EM algorithm, using a centroid model (without variance) and hard assignments.

When doing k-means style clustering (i.e. variance minimization), you

  • coincidentally minimize squared Euclidean distance, because WCSS (within-cluster sum of squares) variance contribution = squared euclidean distance
  • coincidentally assign objects to the nearest cluster by Euclidean distance, because the sqrt function is monotone (note that the mean does not optimize Euclidean distances, but the WCSS function)
  • represent clusters using a centroid only
  • get Voronoi cell shaped clusters, i.e. polygons
  • it works best with spherical clusters

The k-means objective function can be formalized as this: $$\text{argmin}_S \sum_{i=1}^{k} \sum_{x_j \in S_i} \sum_{d=1}^{D} \left(x_{jd} - \mu_{id} \right)^2$$ where $S=\{S_1 \ldots S_k\}$ are all possible partitionings of the data set into $k$ partitions, $D$ is the data set dimensionality, and e.g. $x_{jd}$ is the coordinate of the $j$th instance in dimension $d$.

It is commonly said that k-means assumes spherical clusters. It is also commonly acknowledged that k-means clusters are Voronoi cells, i.e. not spherical. Both are correct, and both are wrong. First of all, the clusters are not complete Voronoi cells, but only the known objects therein. There is no need to consider the dead space in-between the clusters to be part of either cluster, as having an object there would affect the algorithm result. But it is not much better to call it "spherical" either, just because the euclidean distance is spherical. K-means doesn't care about Euclidean distance. All it is, is a heuristic to minimize the variances. And that is actually, what you should consider k-means to be: variance minimization.

Improve this answer
$\endgroup$
11
  • $\begingroup$ Let me suggest you to refine a bit some of your expressions - for more accuracy. For instance, what is to minimize squared euclidean distance or minimize the variances? There must be words "sum of" or "pooled" or such, because we have 2+ clusters, isn't it? $\endgroup$
    – ttnphns
    Sep 8, 2013 at 9:26
  • $\begingroup$ BTW, since k-means minimizes the pooled within-cluster sum of d^2 divided by the number of objects in the respective cluster, your point coincidentally minimize Euclidean distance, because the sqrt function is monotone is, to be precise, not correct. $\endgroup$
    – ttnphns
    Sep 8, 2013 at 9:47
  • $\begingroup$ The proper objective function, for which you can prove convergence, is WCSS, within-cluster sum-of-squares. And indeed, it doesn't minimize Euclidean distances, but it the nearest-centroid-by-euclidean distance is also the WCSS optimal assignment. $\endgroup$
    – Has QUIT--Anony-Mousse
    Sep 8, 2013 at 14:40
  • $\begingroup$ Your wording remains unfortunately dubious. What does phrase minimize squared Euclidean distance, because WCSS variance contribution = squared euclidean distance mean? Are you saying "squared d's between the objects in clusters get minimized because WCSS of deviations get minimized", or just "WCSS of deviations get minimized, which - the deviations - are euclidean distances by nature"? Or smth else? $\endgroup$
    – ttnphns
    Sep 8, 2013 at 16:18
  • 1
    $\begingroup$ Obviously, k-means is a good choice only if you want a centroid model of your data. If you want to optimize pairwise distances, use hierarchical clustering. $\endgroup$
    – Has QUIT--Anony-Mousse
    Sep 8, 2013 at 19:10
8
$\begingroup$

GMM uses overlapping hills that stretch to infinity (but practically only count for 3 sigma). Each point gets all the hills' probability scores. Also, the hills are "egg-shaped" [okay, they're symmetric ellipses] and, using the full covariance matrix, may be tilted.

K-means hard-assigns a point to a single cluster, so the scores of the other cluster centers get ignored (are implicitly reset to zero/don't care). The hills are spherical soap bubbles. Where two soap bubbles touch, the boundary between them becomes a flat (hyper-)plane. Just as when you blow a foam of many soap bubbles, the bubbles on the inside are not flat but are boxy, so the boundaries between many (hyper-)spheres actually forms a Voronoi partition of the space. In 2D, this tends to look vaguely like hexagonal close-packing, think a bee-hive (although of course Voronoi cells are not guaranteed to be hexagons). A K-means hill is round and does not get tilted, so it has less representation power; but it is much faster to compute, especially in the higher dimensions.

Because K-means uses the Euclidean distance metric, it assumes that the dimensions are comparable and of equal weight. So if dimension X has units of miles per hour, varying from 0 to 80, and dimension Y has units of pounds, varying from 0 to 400, and you're fitting circles in this XY space, then one dimension (and its spread) is going to be more powerful than the other dimension and will overshadow the results. This is why it's customary to normalize the data when taking K-means.

Both GMM and K-means model the data by fitting best approximations to what's given. GMM fits tilted eggs, and K-means fits untilted spheres. But the underlying data could be shaped like anything, it could be a spiral or a Picasso painting, and each algorithm would still run, and take its best shot. Whether the resulting model looks anything like the actual data depends on the underlying physical process generating the data. (For instance, time-delay measurements are one-sided; is a Gaussian a good fit? Maybe.)

However, both GMM and K-means implicitly assume data axes/domains coming from the field of real numbers $R^n$. This matters based on what kind of data axis/domain you are trying to cluster. Ordered integer counts map nicely onto reals. Ordered symbols, such as colors in a spectrum, not so nicely. Binary symbols, ehn. Unordered symbols do not map onto reals at all (unless you're using creative new mathematics since 2000).

Thus your 8x8 binary image is going to be construed as a 64-dimensional hypercube in the first hyperquadrant. The algorithms then use geometric analogies to find clusters. Distance, with K-means, shows up as Euclidean distance in 64-dimensional space. It's one way to do it.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Note both algorithms also implicitly assume space axes are equally dense at all points, so fitting exponentially, logarithmically, or sinusoidally-varying data typically benefits from a pre-transform to remap the data into an approximately-linearly-varying domain. $\endgroup$
    – DragonLord
    Mar 24, 2017 at 16:27

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.