5
$\begingroup$

Is there a good notion of distance between partitions of a (fixed, finite) set? The context is this: suppose I have a clustering algorithm, which clusters points using some method or other. Now, I perturb the positions of the points, the clustering changes, and I want some quantitative estimate of how much it has changed.

When there are two clusters $K_1, K_2$ which morph into $L_1, L_2,$ then it seems reasonable to look at the minimum of the sizes of $K_1 \Delta L_1$ and $K_1 \Delta L_2,$ but for more clusters it seems less clear.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
4
$\begingroup$

The variation of information seems to be the sort of thing you're looking for.

Improve this answer
$\endgroup$
4
  • $\begingroup$ PS- You might also look at doi.org/10.1016/S0020-0190(01)00263-0 but IMO the variation of information is a pretty elegant and lightweight distance $\endgroup$
    – Steve Huntsman
    Sep 22, 2018 at 0:54
  • $\begingroup$ An obvious question not obviously answered is: what is a "small" and what is a "large" distance? $\endgroup$
    – Igor Rivin
    Sep 22, 2018 at 2:05
  • $\begingroup$ FYI there is a reasonable way to lift a metric on PDFs to mixtures. I don’t have the reference handy but it’s in ICASSP 2000. $\endgroup$
    – Steve Huntsman
    Sep 22, 2018 at 14:56
  • $\begingroup$ The aforementioned lifting is in doi.org/10.1109/ICASSP.2000.862057 $\endgroup$
    – Steve Huntsman
    Oct 7, 2018 at 1:52

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.