0
$\begingroup$

Clustering is partitioning of $n$ objects into some number $k$ of groups.

I am looking for a theorem to the effect that any such clustering is plausible. I am sure I once saw such a theorem, but I don't remember its name.

I am asking because we were recently doing this, and I told my student that the task could not be very hard, but he insisted that he could not find any defensible reason why {dog,cat},{man,woman} should go together rather than {dog,man},{cat,woman}. I am sure there is some theoretical underpinning of this insight.

Thanks!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

It is always possible to "plausibly" partition $n$ objects into $k$ groups for sufficiently loose definitions of plausibly, but it sounds like you are looking for some definition of what makes one clustering more "defensible" than another.

You could try to claim that in the space of human concepts, "dog" and "cat" are closer together than "dog" and "man", according to some semantic distance function. In general, a clustering algorithm should put items which have low distance between them in the same cluster, and items which have high distance in different clusters.

You can try to formalize this a bit more -- Jon Kleinberg proposes three axioms for what a correct clustering process should satisfy (in "An Impossibility Theorem for Clustering"). Roughly speaking:

  1. Part of the input of the clustering problem is some notion of pairwise distance between the items to be clustered. Linearly scaling that distance function should not change the clustering

  2. Given any predetermined partition of the items, it is possible to construct a distance function such that the clustering process partitions the items in exactly that way

  3. Given that you've already clustered the points, suppose you change the distance function, with only the constraints that points inside of the same cluster don't grow farther from each other, and points in different clusters don't get closer to each other. If you cluster the points again using this redefined distance, the clusters shouldn't change.

He proves that no clustering function satisfies all three axioms, so you're kind of out of luck.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the input. Saw that theorem when googling. But even though quite interesting, I'm pretty sure I once saw a more popoular theorem on wikipedia but just don't recall its name. (I'm not sure I understand what the Kleinberg theorem tells me practically ...) $\endgroup$
    – Dr. E
    Commented Dec 21, 2018 at 9:40

Your Answer

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

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