# 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!

• Interesting question. I don't see the need for a variance assumption in k-means. In fact, I thought the objective was to minimize $\sum_{i=1}^K\sum_{x_j\in S_i} ||x_j - \mu_i ||^2$. If so, there is no equal variance assumption. – Drew75 Mar 6 '14 at 7:07
• In fact, since K-means does not assume that the data points are generated from a Gaussian mixture model, it doesn't deal with the variances explicitly, but it actually includes equal-variance assumption implicitly. If all the denominators in the new objective function that I wrote in the question are equal, then you can just omit this denominator, and you will be left with the K-means objective. – user5054 Mar 6 '14 at 8:11
• Is your algorithm assignes a case to that cluster to which centroid it is closer by the distance, inversly weighted by the variance of the cluster? – ttnphns Mar 7 '14 at 7:33
• Yes, that's what the algorithm I suggest would do. Is there a valid algorithm like that? I mean, if we also learn the cluster variances in K-means and use them while assigning the data points to clusters, does it happen to be a valid algorithm? Mathematically, when you learn univariate GGM parameters by MLE and hard assignment, what I suggested looks correct, but intuitively, this would result in a situation where one of the clusters has a high variance, so, the distance of the points to that cluster is small, and as a result, more data points are assigned to it, so on (a vicious circle). – user5054 Mar 14 '14 at 21:16
• So, I just wonder if the algorithm I suggested is a pathologic one in general, or it behaves in this way just on the dataset I am working on. ? – user5054 Mar 14 '14 at 21:17