I ran into a 2019-Entrance Exam question as follows:
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?)
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 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 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 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.
K means tried to cluster data points into 0 and 1 rules for cluster assignment i.e. Data Point belongs to a class or it does not. But sometimes the data points comes from classes whose probability distribution functions have overlap with each other.
Now Hard Clustering of K means leads to truncation on the data generating\original probability distribution which lead to the Bias in K means algorithm.
Spectral clustering does soft assignment so they are less biased.
This has been proved by taking example in this paper : https://www.researchgate.net/publication/287829457_On_the_bias_and_inconsistency_of_K-means_clustering/link/567a04a608ae40c0e27df98c/download
