Understanding partition comparison indices based on counting object pairs

In unsupervised machine learning, agreement between partitions is commonly assessed with so-called external validity indices. Researchers tend to use and report indices that quantify agreement between two partitions for all clusters simultaneously. Commonly used examples are the Rand index and the adjusted Rand index. Since these overall measures give a general notion of what is going on, their values are usually hard to interpret. Three families of indices based on counting object pairs are analyzed. It is shown that the overall indices can be decomposed into indices that reflect the degree of agreement on the level of individual clusters. The overall indices based on the pair-counting approach are sensitive to cluster size imbalance: they tend to reflect the degree of agreement on the large clusters and provide little to no information on smaller clusters. Furthermore, the value of Rand-like indices is determined to a large extent by the number of pairs of objects that are not joined in either of the partitions.
Comment: 29 pages, 7 tables