Modified K-means with unequal cluster variances I wonder how I can modify the K-means algorithm so that the cluster volumes are not equal to each other. The K-means objective is to minimize within cluster sum of squares $\sum_{i=1}^{p} {\parallel \mathit{X}_i-\mathit{L}_{\mathit{Z}_i} \parallel}_2^2$, and this objective assumes that all cluster variances are the same. If we assume that the clusters are Gaussian with mean $\mathit{L}_{\mathit{Z}_i}$ and variance $\sigma_{\mathit{Z}_i}^2$ where $\mathit{Z}_i$ stands for the cluster assignment of data point $i$, then the objective for the cluster assignments become $\sum_{i=1}^{p} \frac {{\parallel \mathit{X}_i-\mathit{L}_{\mathit{Z}_i} \parallel}_2^2} {\sigma_{\mathit{Z}_i}^2}$. So, I tried modifying K-means such that $\mathit{Z}_i$ update is performed using this new update rule, and $\sigma_{\mathit{Z}_i}^2$ are also updated in each iteration. However, when I use this new modified K-means, almost all data points are assigned to the same cluster, which is weird. What might be the problem about that approach? I know EM can be used for this unequal-volume GMM purpose, but I want a simpler approach like K-means, and I am really curious about why what I tried is not feasible. Thanks!
 A: Use Gaussian Mixture Modeling (aka: EM Clustering) instead.
It allows different variances, depending on your model. It can even allow different covariances if you use the most complex models.
A: While not exactly K-means (see below), I ran across several clustering approaches (in addition to the EM clustering, already mentioned by @Anony-Mousse), which might be helpful. They include:


*

*weighted hierarchical clustering (search for WPGMA and WPGMC here);

*Dirichlet distribution-based clustering (Dirichlet mixture models and Bayesian-based hierarchical Dirichlet process models);

*latent class (LC) clustering (see this page and this paper; LC clustering can be viewed as K-means generalization or, using the authors' terminology, "probabilistic extension").

A: In a GMM, in the limit that the variance of each component goes to 0, and the mixing proportion is uniform, doing expectation maximization on GMM reduces to K-means. Basically one can see K-means as a very special case of a GMM. If you want to modify K-means to allow possibility of different variance in each component, I would say that you will end up with an EM on a GMM.
