Information theoretic measures for clusterings comparison: is a correction for chance necessary?

ABSTRACT

Information theoretic based measures form a fundamental class of similarity measures for comparing clusterings, beside the class of pair-counting based and set-matching based measures. In this paper, we discuss the necessity of correction for chance for information theoretic based measures for clusterings comparison. We observe that the baseline for such measures, i.e. average value between random partitions of a data set, does not take on a constant value, and tends to have larger variation when the ratio between the number of data points and the number of clusters is small. This effect is similar in some other non-information theoretic based measures such as the well-known Rand Index. Assuming a hypergeometric model of randomness, we derive the analytical formula for the expected mutual information value between a pair of clusterings, and then propose the adjusted version for several popular information theoretic based measures. Some examples are given to demonstrate the need and usefulness of the adjusted measures.

REFERENCES

• 1: Albatineh, A. N., Niewiadomska-Bugaj, M., & Mihalko, D. (2006). On similarity indices and correction for chance agreement. Journal of Classification, 23, 301--313.
• 2: Arindam Banerjee , Inderjit S. Dhillon , Joydeep Ghosh , Suvrit Sra, Clustering on the Unit Hypersphere using von Mises-Fisher Distributions, The Journal of Machine Learning Research, 6, p.1345-1382, 12/1/2005
• 3: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 4: Hubert, L., & Arabie, P. (1985). Comparing partitions. Journal of Classification, 193--218.
• 5: Lancaster, H. (1969). The chi-squared distribution. New York: John Wiley.
• 6: Marina Meilǎ, Comparing clusterings: an axiomatic view, Proceedings of the 22nd international conference on Machine learning, p.577-584, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102424]
• 7: Stefano Monti , Pablo Tamayo , Jill Mesirov , Todd Golub, Consensus Clustering: A Resampling-Based Method for Class Discovery and Visualization of Gene Expression Microarray Data, Machine Learning, v.52 n.1-2, p.91-118, July-August 2003 [doi>10.1023/A:1023949509487]
• 8: Rand, W. M. (1971). Objective criteria for the evaluation of clustering methods. Journal of the American Statistical Association, 66, 846--850.
• 9: Alexander Strehl , Joydeep Ghosh, Cluster ensembles --- a knowledge reuse framework for combining multiple partitions, The Journal of Machine Learning Research, 3, p.583-617, 3/1/2003 [doi>10.1162/153244303321897735]
• 10: Vinh, N. X., & Epps, J. (2009). A novel approach for automatic number of clusters detection in microarray data based on consensus clustering. BIBE'09: The IEEE International Conference on BioInformatics and BioEngineering, to appear.
• 11: Vinh, N. X., Epps, J., & Bailey, J. (2009). Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance. to be submitted.
• 12: Warrens, M. (2008). On similarity coefficients for 2x2 tables and correction for chance. Psychometrika, 73, 487--502.
• 13: Zhiwen Yu , Hau-San Wong , Hongqiang Wang, Graph-based consensus clustering for class discovery from gene expression data, Bioinformatics, v.23 n.21, p.2888-2896, November 2007 [doi>10.1093/bioinformatics/btm463]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory
          Subjects: Information theory

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Measurement, Performance