Information theoretic measures for clusterings comparison

TLDR

Information‑theoretic measures are a fundamental class of similarity metrics for comparing clusterings, and their baseline behaves similarly to the Rand Index, varying with the ratio of data points to clusters. The paper argues that chance correction is necessary for information‑theoretic clustering comparison. Using a hypergeometric randomness model, the authors derive an analytical formula for expected mutual information and propose adjusted versions for several popular information‑theoretic measures. The baseline expected mutual information varies with the data‑to‑cluster ratio, and adjusted measures, illustrated by examples, mitigate this variability.

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.