Is it true that K-Means has an assumption "each cluster has a roughly equal number of observations"?

Question

A lecturer claimed in a recent class that "K-means assumes that each cluster includes a roughly equal number of observations."

However, when I searched online, there is conflicting information regarding this point.

The answer to this question claims that the "size" in K-Means refers to the area, not cardinality.

The answer to this question, however, explicitly claims that "size" in K-Means refers to "the amount of points in a cluster", not the "spread"!

This highly upvoted question also didn't help. The question included a statement that K-Means has the following assumption:

the prior probability for all k clusters is the same, i.e., each cluster has roughly equal number of observations

Unfortunately, the answers to that question didn't seem to directly address that "assumption" at all. So I still don't know if it's true or false.

Wikipedia says

k-means clustering and EM clustering on an artificial dataset ("mouse"). The tendency of k-means to produce equal-sized clusters leads to bad results, while EM benefits from the Gaussian distribution present in the data set

which further adds to the confusion.

The answers to the first two questions seem to directly contradict each other. So one of them must be false/inaccurate?

What exactly is K-Means' relationship with "equal number of observations in each cluster"? Is it an assumption? A tendency in the result? Or neither?

Answer 1

There is certainly no assumption in standard K-means algorithms that assumes an equal number of points in each cluster. However, certain standard algorithms do have a tendency towards equalising the spatial variance of clusters, which can result in a (rough) tendency towards equality of cluster sizes in cases where there is overlap between the clusters. For example, one standard method is to estimate the clusters by minimising the within-cluster sum-of-squares (WCSS). In cases where there are several overlapping clusters, this method has a tendency to allocate points in a way that (roughly) equalises the spacial variance of the clusters, which may result in (rough) equalisation of the number of points in each cluster. Alternative methods that use parametric forms to allow greater freedom of variance in each cluster will lack this tendency.

Answer 2

I would recommend to interpret it as often similar area/extend. But of course, opinions may vary.

As the decision boundaries of neighboring clusters are exactly halfway in between of the centers (c.f. Voronoi diagram), there is a good argument to call these 'somewhat equal', even if it does not hold on the empty outside 'areas' that can even be infinite. So formally, area will be a problem, too.

I don't see much of a "tendency" to produce the same number of observations unless you assume, for example, a uniform distribution. On the contrary, it is trivial to construct counterexamples. For example, the 1 dimensional data set 1,2,3,4,5,6,7,8,9,10,100 will produce maximally unbalanced clusters (as unbalanced as you can have with 2 partitions).

Because of such examples, I'd reject the claim that kmeans produces clusters of the same cardinality. And there exist modifications for exactly this purpose of balancing the cardinalities: e.g., https://elki-project.github.io/tutorial/same-size_k_means

Answer 3

Let's review k-means first:

• k-means algorithm clusters the data points based on the update of the centroids (hence the category, center-based clustering).
• Centroids are initially randomly chosen. (Not in all variations of k-means, of course.)
• Centroids will be updated by getting the mean of each cluster in each iteration. I think we are assuming the distance metric is Euclidean. (Yes, it matters.)

These facts, results in spherical clustering. That means, in a 2D space, clusters can be separated using k disks. In n-dimensional space, k n-spheres will partition the space. Your question here, is whether these disks (n-spheres) wrap around roughly equal number of data points. My answer is "yes and no"! Let me elaborate on that:

1. If the distribution of data is uniform, no matter how the centroids are initially chosen, the space (and hence the data) will be roughly equally partitioned.

2. If the distribution is NOT uniform, the results depend on how the centroids are chosen. But, still, it is not easy to think of an example where the space (and NOT the data) is not equally partitioned. Therefore, we cannot say if k-means produces equal-size clusters (clusters with the same number of data-pints), unless it is assumed that the date have a uniform (or even Gaussian) distribution. Since in many scientific examples, data are normally distributed, very often we don't bother mentioning that what assumptions we are building our theories on.

As a side note, we already know that none of the clustering algorithms that tend to find spherical clusters should be used on data points of a particular distribution. Look at the master-piece on the right figure, done by a wrong choice of the method: Yet, this does not make k-means a less powerful clustering algorithm. It is still the first tool for us to get to know our data, since it is fast (O(n⋅k⋅d⋅i) -here-, Lloyd version), and very easy to interpret.

Depending on the type of clusters we should expect (well-separated, contiguous, center-based, density-based, etc), we need to utilize different clustering algorithms.

References for the figures:

1. The first two set of plots are my screen-shots of a great applet to play around with k-means: Naftali Harris
2. The last plot, I borrowed from a great post on Spectral Clustering by Sandipan Dey.