2
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ 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. $\endgroup$
    – usul
    May 23, 2014 at 6:22
  • 2
    $\begingroup$ Also capital letters. $\endgroup$
    – Jeffε
    May 23, 2014 at 13:52
  • $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    May 23, 2014 at 15:25
  • $\begingroup$ @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. $\endgroup$
    – user3660112
    May 23, 2014 at 17:25
  • $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    May 23, 2014 at 19:00

1 Answer 1

Reset to default
3
$\begingroup$

I do not want to attempt a general definition of "unnatural", but I find your argument about the inherent incompatibility of the scale-invariance axiom and the richness axiom as defined in Section 2 of Kleinberg's NIPS paper.

The impossibility result in Section 3 of his paper is stronger, however, and can directly address your concern.

Theorem 3.1 If a clustering function f satisfies Scale-Invariance and Consistency, then Range(f) is an antichain.

So you can consider weakening the richness axiom, e.g. by asking for all partitions with at least 2 parts, and as long as your set of partitions is rich enough to not be an anti-chain, the impossibility theorem goes through.

Hopcroft and Kannan have come up with a "natural" alternative to the richness axiom for which clustering is possible. It is buried in their book Computer Science Theory for the Information Age, and described in a lovely teaser on the Gödel’s Lost Letter blog.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I've also come across a different framework (papers.nips.cc/paper/…) built by Ackerman and Ben-David that uses these axioms (slightly modified of course) in a quality of clustering framework, and shows they are consistent. $\endgroup$
    – user3660112
    Sep 12, 2014 at 5:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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