I ran into a 2019-Entrance Exam question as follows:

enter image description here

The answer mentioned is (4), but some search on google showed me maybe (1) and (2) is equal to (4). Why would k-means be the algorithm with the highest bias? (Can you please also provide references to valid material to study more?)

  • $\begingroup$ Hello. Can you please provide the link to the exam question? $\endgroup$
    – nbro
    Dec 12 '20 at 21:33

I'm not an expert on clustering, but here's my take below. Note that this is only based on theoretical arguments, I haven't had enough clustering experience to say if this is generally true in practice.

K-means vs GMM

K-means has a higher bias than GMM because it is a special case of GMM. K-means specifically assumes the clustering is spherical (meaning each dimension is weighted equally important) and that the clustering problem is a hard clustering problem (each data point can only belong to one label). So, theoretically, K-means should perform equal to GMM (under very specific conditions) or worse. More info

K-means vs GMM (identity covariance matrix)

K-means has a higher bias than GMM (identity covariance matrix) because it is also a special case. K-mean specifically assumes the hard clustering problem, but GMM does not. Because of this, GMM has stronger estimates for the mean of the centroids. More specifically,

[GMM] 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.

So, theoretically, K-means should perform equal to GMM (identity covariance matrix) or worse. More info

K-means vs Spectral clustering

K-means has a higher bias then spectral clustering because spectral clustering effectively uses K-means after processing more information from the matrices.

Spectral clustering usually is spectral embedding, followed by k-means in the spectral domain.

So yes, it also uses k-means. But not on the original coordinates, but on an embedding that roughly captures connectivity. Instead of minimizing squared errors in the input domain, it minimizes squared errors on the ability to reconstruct neighbors. That is often better.

More info


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.