If k-means clustering is a form of Gaussian mixture modeling, can it be used when the data are not normal? 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.
 A: 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.
A: 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.
