7
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ K-means itself has no such an assumption. $\endgroup$ – ttnphns Feb 3 '18 at 23:08
3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Just as a matter of terminology: what would you call k-means if it doesn't minimize the within-cluster sum of squares distance? I (and Wikipedia) would define it as a clustering that attempts to minimize that metric. $\endgroup$ – Dougal Feb 4 '18 at 1:27
  • $\begingroup$ You might be right on the terminology. I was thinking of "k-means" in the broadest sense of referring to any statistical problem involving the estimation of $k$ different means for clusters. It may be that that particular name is generally only applied to a single algorithm. $\endgroup$ – Reinstate Monica Feb 4 '18 at 3:53
  • $\begingroup$ The value of this answer mainly depends on whether this: equalises the spacial variance of the clusters, which may result in (rough) equalisation of the number of points in each cluster could be detailed more or exemplified. $\endgroup$ – ttnphns Feb 4 '18 at 7:01
  • $\begingroup$ Assume 1 dimensional data, 100 points from N(0,1) and 1 million from N(1000,1). Any reason to assume least-variance to produce equal cardinalities in any data that doesn't "naturally" have equal cardinality? (Yes, on U(0,1) data, clusters will usually be well balanced, but you may still get the point of my example). $\endgroup$ – Has QUIT--Anony-Mousse Feb 5 '18 at 20:17
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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. enter image description here

  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. enter image description here 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: enter image description here 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.
$\endgroup$
  • $\begingroup$ Your question here, is whether these disks (n-spheres) are of equal radii? Isn't the question about equal frequency, not equal radius? $\endgroup$ – ttnphns Feb 24 '18 at 5:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.