Answers.Body: <p>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.</p>
  <h2>K-means vs GMM</h2>
  <p>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. <a href="https://stats.stackexchange.com/a/269619/303597">More info</a></p>
  <h2>K-means vs GMM (identity covariance matrix)</h2>
  <p>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,</p>
  <blockquote>
  <p>[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).</p>
  </blockquote>
  <blockquote>
  <p>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.</p>
  </blockquote>
  <p>So, theoretically, K-means should perform equal to GMM (identity covariance matrix) or worse. <a href="https://stats.stackexchange.com/a/489615/303597">More info</a></p>
  <h2>K-means vs Spectral clustering</h2>
  <p>K-means has a higher bias then spectral clustering because spectral clustering effectively uses K-means after processing more information from the matrices.</p>
  <blockquote>
  <p>Spectral clustering usually is spectral embedding, followed by k-means in the spectral domain.</p>
  </blockquote>
  <blockquote>
  <p>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.</p>
  </blockquote>
  <p><a href="https://datascience.stackexchange.com/a/36387/108095">More info</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-12T21:28:56.050Z
Answers.LastActivityDate: 2020-12-12T21:28:56.050Z
Answers.UserDisplayName: user3667125
Answers.Body: <p>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.</p>
  <p>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.</p>
  <p>Spectral clustering does soft assignment so they are less biased.</p>
  <p>This has been proved by taking example in this paper : <a href="https://www.researchgate.net/publication/287829457_On_the_bias_and_inconsistency_of_K-means_clustering/link/567a04a608ae40c0e27df98c/download" rel="nofollow noreferrer">https://www.researchgate.net/publication/287829457_On_the_bias_and_inconsistency_of_K-means_clustering/link/567a04a608ae40c0e27df98c/download</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-07T05:39:54.917Z
Answers.LastActivityDate: 2022-01-07T05:39:54.917Z
Answers.UserDisplayName: Ashwiniku918
Body: <p>I ran into a 2019-Entrance Exam question as follows:</p>
  <p><a href="https://i.sstatic.net/Z8Dd3.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Z8Dd3.png" alt="enter image description here" /></a></p>
  <p>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?)</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-12T21:33:49.843Z
Comments.Text: Hello. Can you please provide the link to the exam question?
Comments.UserDisplayName: nbro
Tags: <machine-learning><k-means><bias-variance-tradeoff><spectral-clustering><gaussian-mixture-models>
Title: Why does k-means have more bias than spectral clustering and GMM?
UserDisplayName: Lisa Berry
ThreadText: # Why does k-means have more bias than spectral clustering and GMM?
  
  (Asked by: username_0 on 2020-12-12)
  
  I ran into a 2019-Entrance Exam question as follows:
  
  [![enter image description here](https://i.sstatic.net/Z8Dd3.png)](https://i.sstatic.net/Z8Dd3.png)
  
  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?)
  
  **Tags:** machine-learning, k-means, bias-variance-tradeoff, spectral-clustering, gaussian-mixture-models
  > **Comments:**
  > **username_1**: Hello. Can you please provide the link to the exam question?  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2020-12-12. Score: 1
  
  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](https://stats.stackexchange.com/a/269619/303597)
  
  ## 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](https://stats.stackexchange.com/a/489615/303597)
  
  ## 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](https://datascience.stackexchange.com/a/36387/108095)
  
  
  ---
  
  ### Answer by username_3 on 2022-01-07. Score: 0
  
  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>
  
  
  ---
  
  