Title: Bridging Information-Theoretic and Pair-Counting Clustering Similarity

Abstract:

Evaluating unsupervised models fundamentally relies on comparing clusterings, yet the proliferation of existing similarity metrics often yields conflicting or widely divergent results. These measures generally fall into two primary categories: pair-counting and information-theoretic. The former assesses agreement by examining individual element pairs, while the latter aggregates data across entire cluster contingency tables. Although previous studies have noted similarities between these families and have employed empirical normalization or chance-correction techniques, the underlying analytical link between them has remained incompletely resolved.

This study introduces an analytical framework that unifies these two families through two distinct but complementary lenses. First, we demonstrate that both families can be formulated as weighted expansions contrasting observed co-occurrences with expected ones. Within this structure, pair-counting metrics represent a quadratic, low-order approximation, whereas information-theoretic measures serve as higher-order extensions that incorporate frequency weighting. Second, we extend the concept of pair-counting to k-tuple agreement, revealing that information-theoretic measures effectively accumulate higher-order co-assignment structures that extend beyond simple pairwise interactions.

We apply these perspectives analytically to the Rand index and Mutual Information, illustrating how other indices within each family arise as logical extensions. Collectively, these insights elucidate the specific conditions and reasons for divergence between the two regimes, linking their differing sensitivities directly to weighting schemes and approximation orders. This framework offers a rigorous foundation for the selection, interpretation, and extension of clustering similarity measures across various applications.

Source: arXiv Generated at: 2026-06-04 00:00:00 UTC