Source-linked AI summary
The Impact of Random Models on Clustering Similarity
Alexander J Gates, Yong-Yeol Ahn
TL;DR
Clustering comparisons need chance-adjusted baselines, but the usual fixed-size permutation model may not represent practical clustering ensembles. The paper derives corrections under broader random models and one-sided comparisons, showing that these choices can substantially change rankings and evaluations, and should be justified for the clustering context.
Problem
Chance-adjusted clustering similarity usually assumes fixed cluster numbers and sizes, although practical clusterings can vary in these properties and reference comparisons may be one-sided.
Method
The paper derives adjusted Rand-index and Mutual Information variants for Mnum and Mall random models and studies one-sided comparisons with a reference clustering.
Results
The choice of random model and one-sided comparison can significantly affect clustering-pair rankings and evaluations against random baselines across synthetic, handwriting, and gene-expression examples.
Takeaways & Limitations
Clustering comparisons should justify both the random clustering model and whether comparisons are one-sided or two-sided.
Takeaways & Limitations
Normalized mutual information can favor comparisons between clusterings with more clusters, while the Rand index becomes less sensitive to co-occurring pairs as N increases.
Abstract
from arXiv · showhide
Clustering is a central approach for unsupervised learning. After clustering is applied, the most fundamental analysis is to quantitatively compare clusterings. Such comparisons are crucial for the evaluation of clustering methods as well as other tasks such as consensus clustering. It is often argued that, in order to establish a baseline, clustering similarity should be assessed in the context of a random ensemble of clusterings. The prevailing assumption for the random clustering ensemble is the permutation model in which the number and sizes of clusters are fixed. However, this assumption does not necessarily hold in practice; for example, multiple runs of K-means clustering returns clusterings with a fixed number of clusters, while the cluster size distribution varies greatly. Here, we derive corrected variants of two clustering similarity measures (the Rand index and Mutual Information) in the context of two random clustering ensembles in which the number and sizes of clusters vary. In addition, we study the impact of one-sided comparisons in the scenario with a reference clustering. The consequences of different random models are illustrated using synthetic examples, handwriting recognition, and gene expression data. We demonstrate that the choice of random model can have a drastic impact on the ranking of similar clustering pairs, and the evaluation of a clustering method with respect to a random baseline; thus, the choice of random clustering model should be carefully justified.
1. Introduction
The paper argues that chance-adjusted clustering comparisons depend critically on the random clustering model and comparison direction. It develops broader random models and one-sided variants, then demonstrates substantial effects on clustering-pair rankings and method evaluation.
- 1. Introduction: Clustering similarity measures are important for evaluating methods, comparing clustering pairs, parameter estimation, taxonomies, and consensus clustering.The introduction highlights the Rand index and normalized mutual information as prominent measures.
- 1. Introduction: The common permutation model fixes both the number and sizes of clusters, but these assumptions are often violated when cluster counts or size distributions vary.K-means runs can retain a fixed cluster count while producing substantially different cluster-size sequences.
- 1. Introduction: One-sided comparisons use a fixed reference clustering against random clusterings, providing a baseline that accounts for the reference structure.This differs from assuming both clusterings were independently drawn from the same random model.
- 1. Introduction: The framework introduces Mnum, uniform over clusterings with a fixed number of clusters, and Mall, uniform over all clusterings, alongside the permutation model.Expected Rand-index and Mutual Information values are derived for these models.
- 1. Introduction: Random-model and one-sided-comparison choices can significantly affect clustering-pair rankings and evaluations against random baselines.The effects are demonstrated with a hypothetical example, MNIST K-means clusterings, and gene-expression hierarchical clustering.
2. Clusterings
A clustering partitions a set of labeled elements into non-empty, disjoint clusters. Each clustering is characterized by its number of clusters and sequence of cluster sizes.
- 2. Clusterings: A clustering partitions N distinct elements into non-empty, disjoint subsets called clusters.The clusters together form a partition of the element set.
- 2. Clusterings: Each clustering has a cluster-size sequence [c1, c2, . . . , cKC], where ci is the size of its i-th cluster.Cluster sizes are defined by ci = |Ci|.
- 2. Clusterings: The paper compares two clusterings A and B over the same set of N labeled elements, allowing their cluster counts and sizes to differ.A has KA clusters with sizes ai, while B has KB clusters with sizes bj.
3. Correction for Chance
Chance correction rescales a clustering similarity measure using its expected value under a specified random clustering model. The normalization also depends on the measure and, for mutual information, on the random model.
- 3. Correction for Chance: Chance correction uses the expected similarity Emodel[s] from pairwise comparisons in a specified random ensemble.The corrected score is constructed from the observed similarity and its random-model expectation.
- 3. Correction for Chance: The normalization denominator uses the ensemble’s maximum similarity so identical clusterings receive a score of 1.0.For the Rand index, the upper bound is always 1.0; for mutual information, the maximum depends on the random model.
4. Rand Index
The Rand index measures pairwise agreement between clusterings, but its chance-corrected expectation depends on the random clustering model. The paper derives expectations under permutation, fixed-number-of-clusters, and all-clusterings models, including one-sided reference comparisons.
- Rand index definition: The Rand index measures agreement over element pairs, counting pairs coassigned or separated in both clusterings; N11 and N00 indicate agreement, while N10 and N01 indicate disagreement.It can also be represented as the normalized number of positive entries in the element-wise product of binary pair vectors.
- Rand index limitation: As the number of elements grows, the Rand index becomes dominated by pairs assigned to different clusters, reducing sensitivity to coassigned pairs.This limitation arises because N00 can overwhelm the other pair-count categories.
- Permutation model: The commonly used adjusted Rand index uses the permutation model, which fixes both clusterings’ cluster-size sequences when calculating expected similarity.This expectation is combined with the maximum Rand index of 1.0 to correct the observed score for chance.
- Fixed number of clusters: Under Mnum, the expected Rand index is derived for independently uniform clusterings with fixed numbers of clusters, using probabilities based on Stirling numbers of the second kind.The resulting expectation applies when cluster sizes vary while the number of clusters remains fixed.
- All clusterings: Under Mall, the expected Rand index is obtained for independently uniform clusterings drawn from all partitions of N elements, using Bell numbers related to Stirling numbers.This model allows both the number and sizes of clusters to vary.
- One-sided comparisons: One-sided Rand-index expectations keep a reference clustering fixed while averaging over random clusterings drawn from Mnum or Mall.This accounts for the reference clustering’s fixed pair structure rather than treating both clusterings as random.
5. Mutual Information
Mutual Information measures clustering dependence and is commonly normalized for comparison, but chance correction depends on the chosen random-clustering model. The paper derives expectations and adjusted variants for permutation, fixed-number, and unrestricted clustering ensembles, including one-sided comparisons.
- Mutual Information: Mutual information measures the information shared by two clusterings and is normalized to [0, 1] for comparison.It ranges from 0 to min{H(A), H(B)} before normalization.
- Mutual Information: Normalized mutual information can favor comparisons between clusterings with more clusters because it depends on their cluster counts.This bias is reported despite NMI’s dependence on relative cluster-size proportions.
- Permutation model: The permutation-model AMI subtracts expected mutual information and rescales by the model-specific maximum similarity.Under the permutation model, cluster sizes and entropies remain fixed, enabling the expected MI derivation through contingency tables and hyper-geometric probabilities.
- Fixed number of clusters (Mnum): For Mnum, expected mutual information depends on average and joint partition entropy because cluster sizes vary across random clusterings.The exact expectation requires summations over possible cluster sizes and has computational complexity O(N^3).
- All clusterings (Mall): For Mall, both single-clustering and joint entropies are averaged over the ensemble, with maxall[MI(A, B)] = log N.The maximum bound must be selected over the entire random-clustering ensemble.
- One-sided comparisons: One-sided adjusted mutual information fixes the reference clustering while drawing the other clustering from Mnum or Mall.The one-sided expected joint entropy and MI follow from treating the reference cluster sequence as fixed, with the maximum bound chosen for the relevant ensemble.
6. Results
Results show that random-model assumptions can change clustering-similarity rankings, K-means evaluations, and whether methods appear better or worse than chance.
- Results: Random-model choice changes similarity rankings and random-baseline evaluations across synthetic, K-means, and gene-expression examples.The paper identifies altered rankings, biased K-means comparisons, and changed better- or worse-than-chance classifications.
- Clustering Similarity Ranking: The Rand-index rankings of five clustering pairs vary widely across random models, although every measure identifies W and X as the most similar pair.The differences arise because Mperm preserves cluster-size sequences, whereas Mnum and Mall treat some sequences as rarer.
- Clustering Similarity Ranking: Under Mall, negative adjusted Rand scores indicate that two random clusterings are expected to be more similar than the observed comparison.This interpretation provides a random-baseline criterion for identifying solutions that may not meaningfully represent the data.
- Clustering Similarity Ranking: Mutual-information rankings depend on both the random model and maximum-bound choice, with several NMI variants restoring W–X as the top pair.Mall is independent of the maximum bound, while Min normalization can still favor clusterings with more clusters.
- Appropriate Random Model for Comparing K-means Clusterings: Most K-means clusterings changed relative ranking under Mnum versus Mperm, with Mperm consistently biased toward higher similarity.Nearly all 400 runs had different cluster-size sequences despite sharing the same number of clusters.
- Performing at Random in Tumor Gene Expression Clustering: Seven gene-expression studies judged better than chance under Mperm were judged worse than chance under M1num, while three showed the reverse classification.These reversals show that the selected random model can change the practical conclusion about method performance.
7. Discussion
The discussion argues that chance-corrected clustering comparisons require a random model and one-sidedness treatment matched to the clustering scenario. It also highlights unresolved modeling choices and limitations affecting interpretation.
- Practitioners should justify the random clustering model because chance-corrected baselines facilitate comparisons between clustering solutions.
- Use Mnum when the number of clusters is user-specified, Mperm when the cluster-size sequence is fixed, and one-sided or two-sided comparisons according to the reference structure.
- The study does not establish a universally superior clustering technique or random model, and its conclusions assume uniformly sampled partitions subject to ensemble constraints.Alternative priors could model inferred cluster counts or heavy-tailed cluster-size distributions, potentially changing similarity expectations.
- The framework exposes a counterintuitive increase in expected Rand-index and Mutual-Information similarity as the number of elements grows.This behavior conflicts with the intuition that matching memberships should become harder for larger random clusterings.
- Selecting the random model and treatment of one-sided comparisons is essential because corrected-similarity conclusions can change with these choices.The practitioner should justify both choices for the context being analyzed.
Appendix A. Stirling and Bell Numbers
The appendix introduces Stirling and Bell numbers as combinatorial counts of clusterings and notes both their recurrence relations and computational approximations.
- The Stirling number S(n, k) counts partitions of n elements into k clusters.
- Recurrence relations are provided for both Stirling and Bell numbers, while asymptotic approximations describe their large-n behavior.
- The Bell number B_n counts all clusterings of n elements by summing the Stirling numbers S(n, k) over k.
- Because direct recurrence calculations can be expensive, the analysis uses efficient arbitrary-precision approximations implemented through Python’s mpmath library.
B.1 Digits Data Set
The digits dataset contains 1,797 grayscale images of handwritten digits, with a reference clustering defined by the ten true digit classes.
- The dataset contains 1,797 images represented as 8 × 8 grayscale pixels.
- Its reference clustering contains 10 clusters corresponding to the true digit labels.
- For visualization, the data were projected into two dimensions using t-SNE.
B.2 Gene Expression Data Set
The gene-expression data comprise studies of cancer tumors or healthy controls using Affymetrix and cDNA microarrays.
- The studies measure gene expression in cancer-tumor or healthy-control tissue samples.
- Affymetrix microarrays measure RNA-copy counts, whereas cDNA microarrays measure copy-number ratios relative to a control sample.