<p>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.</p>

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

<blockquote>
  <p><strong>Theorem 3.1</strong> If a clustering function f satisfies Scale-Invariance and Consistency,
  then Range(f) is an antichain.</p>
</blockquote>

<p>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 <em>not</em> be an anti-chain, the impossibility theorem goes through.</p>

<p>Hopcroft and Kannan have come up with a "natural" alternative to the richness axiom for which clustering <em>is</em> possible.  It is buried in their book <a href="http://www.cs.cmu.edu/~venkatg/teaching/CStheory-infoage/hopcroft-kannan-feb2012.pdf" rel="nofollow">Computer Science Theory for the Information Age</a>, and described in a lovely teaser on the <a href="http://rjlipton.wordpress.com/2013/12/09/a-negative-impossibility-theorem/" rel="nofollow">Gödel’s Lost Letter</a> blog.</p>

CC BY-SA 3.0
2014-09-12T05:17:51.157Z
I've also come across a different framework (http://papers.nips.cc/paper/3491-measures-of-clustering-quality-a-working-set-of-axioms-for-clustering.pdf)  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.
user3660112
CC BY-SA 3.0
2014-09-11T21:18:29.117Z
2014-09-11T21:18:29.117Z
Abraham D Flaxman
<p>In the paper <a href="http://www.cs.cornell.edu/home/kleinber/nips15.pdf" rel="nofollow">An Impossibility Theorem for Clustering</a>, Jon Kleinberg introduced an axiomatic framework for clustering and showed that his set of axioms are inconsistent. One of the axioms is the <em>Richness Axiom</em>: any partition of the input can be produced by some distance function. </p>

<p>My question is:</p>

<blockquote>
  <p>Isn't the richness axiom unnatural?</p>
</blockquote>

<p>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? </p>

CC BY-SA 3.0
2014-05-23T06:22:53.340Z
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
CC BY-SA 3.0
2014-05-23T13:52:18.960Z
Also capital letters.
Jeffε
CC BY-SA 3.0
2014-05-23T15:25:18.433Z
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.
Sasho Nikolov
CC BY-SA 3.0
2014-05-23T17:25:49.140Z
@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.
user3660112
CC BY-SA 3.0
2014-05-23T19:00:34.480Z
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.
Sasho Nikolov
CC BY-SA 3.0
2014-05-23T19:28:51.560Z
@SashoNikolov: i think you've got my question wrong. i've edited it to what i really wanted to ask.
user3660112
CC BY-SA 3.0
2014-05-24T06:46:50.950Z
@SashoNikolov My question was whether the axiom was intuitive. I guess i could've put it this way.
user3660112
<clustering>
an axiomatic framework for clustering by jon kleinberg may have a problem?
user3660112
# an axiomatic framework for clustering by jon kleinberg may have a problem?

(Asked by: username_0 on 2014-05-22)

In the paper [An Impossibility Theorem for Clustering](http://www.cs.cornell.edu/home/kleinber/nips15.pdf), 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?

**Tags:** clustering

> **Comments:**
> **username_1**: 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.  
> **username_2**: Also capital letters.  
> **username_3**: 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.  
> **username_0**: @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.  
> **username_3**: 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.  
> **username_0**: @SashoNikolov: i think you've got my question wrong. i've edited it to what i really wanted to ask.  
> **username_0**: @SashoNikolov My question was whether the axiom was intuitive. I guess i could've put it this way.  

---

## 1 answers

### Answer by username_4 on 2014-09-11. Score: 3

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](http://www.cs.cmu.edu/~venkatg/teaching/CStheory-infoage/hopcroft-kannan-feb2012.pdf), and described in a lovely teaser on the [Gödel’s Lost Letter](http://rjlipton.wordpress.com/2013/12/09/a-negative-impossibility-theorem/) blog.

> **Comments:**
> **username_0**: I've also come across a different framework (http://papers.nips.cc/paper/3491-measures-of-clustering-quality-a-working-set-of-axioms-for-clustering.pdf)  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.  

---

