Comparing clusterings—an information based distance

  • Department of Statistics, University of Washington, Box 354322, Seattle, WA 98195-4322, USA
  Open Archive

Abstract

This paper proposes an information theoretic criterion for comparing two partitions, or clusterings, of the same data set. The criterion, called variation of information (VI), measures the amount of information lost and gained in changing from clustering C to clustering C. The basic properties of VI are presented and discussed. We focus on two kinds of properties: (1) those that help one build intuition about the new criterion (in particular, it is shown the VI is a true metric on the space of clusterings), and (2) those that pertain to the comparability of VI values over different experimental conditions. As the latter properties have rarely been discussed explicitly before, other existing comparison criteria are also examined in their light. Finally we present the VI from an axiomatic point of view, showing that it is the only “sensible” criterion for comparing partitions that is both aligned to the lattice and convexely additive. As a consequence, we prove an impossibility result for comparing partitions: there is no criterion for comparing partitions that simultaneously satisfies the above two desirable properties and is bounded.

MSC

  • 91C20;
  • 94A17;
  • 05A18

Keywords

  • Agreement measures;
  • Clustering;
  • Comparing partitions;
  • Information theory;
  • Mutual information;
  • Similarity measures

References

    • [1]
    • M.R. Anderberg
    • Cluster Analysis for Applications

    • Academic Press, New York, NY (1973)

    • [3]
    • T.M. Cover, J.A. Thomas
    • Elements of Information Theory

    • Wiley, New York (1991)

    • [4]
    • E.B. Fowlkes, C.L. Mallows
    • A method for comparing two hierarchical clusterings

    • J. Amer. Statist. Assoc., 78 (383) (1983), pp. 553–569

    • [5]
    • J.A. Hartigan
    • Clustering Algorithms

    • Wiley, New York, NY (1975)

    • [7]
    • A.K. Jain, R.C. Dubes
    • Algorithms for Clustering Data

    • Prentice-Hall, Englewood Cliffs, NJ (1988)

    • [8]
    • B. Larsen, C. Aone
    • Fast and effective text mining using linear time document clustering

    • Proceedings of the Conference on Knowledge Discovery and Data Mining (1999), pp. 16–22

    • [10]
    • G.J. MacLachlan, K.E. Bashford
    • Mixture Models: Inference and Applications to Clustering

    • Marcel Dekker, NY (1988)

    • [11]
    • M. Meilă
    • Comparing clusterings—an axiomatic view

    • S. Wrobel, L. De Raedt (Eds.), Proceedings of the International Machine Learning Conference (ICML), ACM Press, New York (2005)

    • [13]
    • B.G. Mirkin
    • Mathematical Classification and Clustering

    • Kluwer Academic Press, Dordrecht (1996)

    • [15]
    • W.M. Rand
    • Objective criteria for the evaluation of clustering methods

    • J. Amer. Statist. Assoc., 66 (1971), pp. 846–850

    • [16]
    • A. Rényi
    • Probability Theory

    • North-Holland, Amsterdam (1970)

    • [17]
    • R.P. Stanley
    • Enumerative Combinatorics

    • Cambridge University Press, Cambridge (1997)

    • [19]
    • S. van Dongen, Performance criteria for graph clustering and Markov cluster experiments, Technical Report INS-R0012, Centrum voor Wiskunde en Informatica, 2000.