A cute and thought-provoking theorem for sure, but arguably none of the three given criteria for clustering are well motivated, so the result is much less relevant than usually claimed.
- scale-invariance: stretching data along some dimensions should not change clustering.
This is clearly not true: . . . (three well-spaced spots) may be reasonably seen as three clusters, whereas ||| (three nearby elongated bars) not.
- richness: all groupings must be reachable.
Also not quite true, both of the two cases: (1) all clusters are singleton points and (2) a single cluster that contains all points, mean the same: no useful cluster structure found. So it is enough if one of these groupings are reachable, and not both.
- consistency: increasing inter-cluster differences and decreasing intra-cluster differences should not change clustering.
Also not quite true: suppose we have 9 clusters:
. . .
. . .
. . .
now move the points so that the columns get further apart, at some point we will get:
| | |, where 3 clusters are more reasonable.
Actually, scale-invariance only refers to scaling all dimensions by the same scalar (this is more clearly specificed in the paper linked by the article, page 3). For arbitrary scaling on each coordinate, of course you're correct, it's impossible to have a clustering algorithm that is invariant for such transformations (e.g., the 6-point group ::: may look like either 2 or 3 clusters, depending on whether it's stretched horizontally or vertically).
As for your last two points, I believe I agree! It seems that in the counterexample you give for consistency, some notion of scale-invariance is implicitly assumed -- perhaps this connection plays some role in the theorem's proof (which I haven't read).
This reminds me a bit of Arrow's impossibility theorem for voting, which similarly has questionable premises.
But in almost all cases that doesn't make any sense? Typically the data in different dimensions will have different "units". So there isn't any meaning in the scale in the first place. How could scaling by a single scalar be "more natural"?
If different components of the dataset have different units, I would argue that it is a prerequisite of clustering to first specify the relative importance of each particular unit (thereby putting all units on the same scale). Otherwise, there's no way the clustering algorithm could possibly know what to in certain cases (such as the ::: example).
It's true that there is no intrinsic meaning to the scale, but you must specify at least a relative scale -- how you want to compare (or weigh) different units -- before you can meaningfully cluster the data. Clustering can only work on dimensionless data.
This is the point I think - there's no inherent meaning to the scaling factor(s) as far as overall structure is concerned (they're dimensionless, so the units thing isn't a problem), so the outcome of a clustering algorithm should not depend on it.
Ah I see. As I understand it a general linear map like that isn't what the linked paper means by "scale-invariance", so it wouldn't be considered a violation for a dataset and it's PCA to be given different clusters by your clustering algorithm. It's only the dataset and its scaled up or down counterparts (i.e. the metric is multiplied by a fixed non-zero constant) that are required to get the same clusters for scale-invariance to hold.
In fact the paper doesn't assume that your dataset is contained in a vector space at all. All you have to give a clustering algorithm (as they define it) is a set and a metric function on it.
Scale invariance is well motivated in the sense that perhaps you already normalized your data (usually to fit [-1, 1] or something) and you would be bummed to discover it fucked up your clusters
Or likewise: if you have physical data recorded in some units (say, meters), it would suck if the clusters changed if you had measured stuff in another unit instead
- scale-invariance: stretching data along some dimensions should not change clustering.
This is clearly not true: . . . (three well-spaced spots) may be reasonably seen as three clusters, whereas ||| (three nearby elongated bars) not.
- richness: all groupings must be reachable.
Also not quite true, both of the two cases: (1) all clusters are singleton points and (2) a single cluster that contains all points, mean the same: no useful cluster structure found. So it is enough if one of these groupings are reachable, and not both.
- consistency: increasing inter-cluster differences and decreasing intra-cluster differences should not change clustering.
Also not quite true: suppose we have 9 clusters:
now move the points so that the columns get further apart, at some point we will get: | | |, where 3 clusters are more reasonable.