# an axiomatic framework for clustering by jon kleinberg may have a problem?

In the paper An Impossibility Theorem for Clustering, Jon Kleinberg introduced an axiomatic framework for clustering and showed that his set of axioms are inconsistent. One of the axioms is the Richness Axiom: any partition of the input can be produced by some distance function.

My question is:

Isn't the richness axiom unnatural?

The axiom implies that both trivial partitions: the one which puts all elements in the same cluster, and the one in which each cluster is a singleton, are both considered as valid clusterings. However, this is counter-intuitive in real life situations. In many (i guess most) real life situations we wouldn't have both these clusterings considered as valid simultaneously. so i guess the richness axiom could be modified. do we truly need all partitions to be considered as valid clusterings?

• To make this question better, maybe link to the paper (or at least give the reference), and bonus for defining the terms and providing some background -- thanks.
– usul
May 23 '14 at 6:22
• Also capital letters. May 23 '14 at 13:52
• Why shouldn't these two partitions be considered legal? They make sense if either all points are very close, or if every pair of points are far apart. May 23 '14 at 15:25
• @sasho nikolov: if both these cases are to be considered simultaneouly as valid clusters for the same data set, which the richness axiom does, then clearly we will have problems. for example: If you are given two points, and your clustering algorithm is scale and rotation invariant it is not possible to achieve all partitions of the input set. There is nothing wrong with this, yet it violates the richness axiom. May 23 '14 at 17:25
• Ok, that's fair. I edited your question to reflect this. I also fixed your link. However, I still don't know what your question is. What do you mean by "the need for the axiom"? The axioms are meant to be intuitive, and this of course is debatable. Richness is not implied by the other two axioms. Kleinberg shows that the range of any scale-invariant consistent clustering function, for any input size, is an anti-chain in the refinement partial order on partitions. This generalizes your observation considerably. May 23 '14 at 19:00