# The Impact of Random Models on Clustering Similarity

arXiv: https://arxiv.org/abs/1701.06508 · HTML: https://mlsanity.com/paper/1701.06508/

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jan 2017.

## Built on by (most cited first, 30 of 34)

- [Are Cluster Validity Measures (In)valid?](https://mlsanity.com/paper/2208.01261/) (2022)
- [UnweaveNet: Unweaving Activity Stories](https://mlsanity.com/paper/2112.10194/) (2021)
- [A Tighter Analysis of Spectral Clustering, and Beyond](https://mlsanity.com/paper/2208.01724/) (2022)
- [Lead-lag detection and network clustering for multivariate time series with an application to the US equity market](https://mlsanity.com/paper/2201.08283/) (2022)
- [Leveraging Model-based Trees as Interpretable Surrogate Models for Model Distillation](https://mlsanity.com/paper/2310.03112/) (2023)
- [Normalized mutual information is a biased measure for classification and community detection](https://mlsanity.com/paper/2307.01282/) (2023)
- [Characterizing and comparing external measures for the assessment of cluster analysis and community detection](https://mlsanity.com/paper/2102.00708/) (2021)
- [Local Algorithms for Finding Densely Connected Clusters](https://mlsanity.com/paper/2106.05245/) (2021)
- [Fast and Simple Spectral Clustering in Theory and Practice](https://mlsanity.com/paper/2310.10939/) (2023)
- [Categorical Data Clustering via Value Order Estimated Distance Metric Learning](https://mlsanity.com/paper/2411.15189/) (2024)
- [Skew-Symmetric Adjacency Matrices for Clustering Directed Graphs](https://mlsanity.com/paper/2203.01388/) (2022)
- [Break the Tie: Learning Cluster-Customized Category Relationships for Categorical Data Clustering](https://mlsanity.com/paper/2511.09049/) (2025)
- [Learning Unified Distance Metric for Heterogeneous Attribute Data Clustering](https://mlsanity.com/paper/2603.04458/) (2026)
- [Learning Order Forest for Qualitative-Attribute Data Clustering](https://mlsanity.com/paper/2603.03387/) (2026)
- [Normalised clustering accuracy: An asymmetric external cluster validity measure](https://mlsanity.com/paper/2209.02935/) (2022)
- [Random Models for Fuzzy Clustering Similarity Measures](https://mlsanity.com/paper/2312.10270/) (2023)
- [Estimating Agreement by Chance for Sequence Annotation](https://mlsanity.com/paper/2407.11371/) (2024)
- [Doubly Robust Fusion of Many Treatments for Policy Learning](https://mlsanity.com/paper/2505.08092/) (2025)
- [Bridging the Semantic Gap for Categorical Data Clustering via Large Language Models](https://mlsanity.com/paper/2601.01162/) (2026)
- [GraphPMU: Event Clustering via Graph Representation Learning Using Locationally-Scarce Distribution-Level Fundamental and Harmonic PMU Measurements](https://mlsanity.com/paper/2205.13116/) (2022)
- [Bayesian CART models for aggregate claim modeling](https://mlsanity.com/paper/2409.01908/) (2024)
- [Mini-Batch Kernel k-means](https://mlsanity.com/paper/2410.05902/) (2024)
- [A Pragmatic Method for Comparing Clusterings with Overlaps and Outliers](https://mlsanity.com/paper/2602.14855/) (2026)
- [CanvasAgent: Enabling Complex Image Creation and Editing via Visual Tool Orchestration](https://mlsanity.com/paper/2607.05465/) (2026)
- [An objective function for order preserving hierarchical clustering](https://mlsanity.com/paper/2109.04266/) (2021)
- [Shape complexity in cluster analysis](https://mlsanity.com/paper/2205.08046/) (2022)
- [visClust: A visual clustering algorithm based on orthogonal projections](https://mlsanity.com/paper/2211.03894/) (2022)
- [Spectral Clustering for Directed Graphs via Likelihood Estimation on Stochastic Block Models](https://mlsanity.com/paper/2403.19516/) (2024)
- [SPINEX-Clustering: Similarity-based Predictions with Explainable Neighbors Exploration for Clustering Problems](https://mlsanity.com/paper/2407.07222/) (2024)
- [Random Normed k-Means: A Paradigm-Shift in Clustering within Probabilistic Metric Spaces](https://mlsanity.com/paper/2504.03928/) (2025)

## Abstract (arXiv)

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.