# K*-Means: A Parameter-free Clustering Algorithm

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 43 references that are in the map.
- First posted on arXiv 17 May 2025.

## Builds on (most cited first, 19 of 19)

- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction](https://mlsanity.com/paper/1802.03426/) (2018)
- [Deep Clustering for Unsupervised Learning of Visual Features](https://mlsanity.com/paper/1807.05520/) (2018)
- [Graph Embedded Pose Clustering for Anomaly Detection](https://mlsanity.com/paper/1912.11850/) (2019)
- [Automatic Data Curation for Self-Supervised Learning: A Clustering-Based Approach](https://mlsanity.com/paper/2405.15613/) (2024)
- [DinoSR: Self-Distillation and Online Clustering for Self-supervised Speech Representation Learning](https://mlsanity.com/paper/2305.10005/) (2023)
- [Deep Temporal Graph Clustering](https://mlsanity.com/paper/2305.10738/) (2023)
- [Semi-supervised learning made simple with self-supervised clustering](https://mlsanity.com/paper/2306.07483/) (2023)
- [A Modular Approach for Multimodal Summarization of TV Shows](https://mlsanity.com/paper/2403.03823/) (2024)
- [Minimum Description Length Clustering to Measure Meaningful Image Complexity](https://mlsanity.com/paper/2306.14937/) (2023)
- [Selective Pseudo-label Clustering](https://mlsanity.com/paper/2107.10692/) (2021)
- [Hard Regularization to Prevent Deep Online Clustering Collapse without Data Augmentation](https://mlsanity.com/paper/2303.16521/) (2023)
- [Revisiting Self-Supervised Heterogeneous Graph Learning from Spectral Clustering Perspective](https://mlsanity.com/paper/2412.00742/) (2024)
- [Breaking the Reclustering Barrier in Centroid-based Deep Clustering](https://mlsanity.com/paper/2411.02275/) (2024)
- [Just Cluster It: An Approach for Exploration in High-Dimensions using Clustering and Pre-Trained Representations](https://mlsanity.com/paper/2402.03138/) (2024)
- [OwMatch: Conditional Self-Labeling with Consistency for Open-World Semi-Supervised Learning](https://mlsanity.com/paper/2411.01833/) (2024)
- [Parameter-free Video Segmentation for Vision and Language Understanding](https://mlsanity.com/paper/2503.01201/) (2025)
- [Towards a Universal Method for Meaningful Signal Detection](https://mlsanity.com/paper/2408.00016/) (2024)
- [Local Compositional Complexity: How to Detect a Human-readable Messsage](https://mlsanity.com/paper/2501.03664/) (2025)

## Built on by (most cited first, 3 of 3)

- [Cross-Attention Calibrated Deduplication for Retrieval-Augmented Generation System](https://mlsanity.com/paper/2607.24332/) (2026)
- [Density-aware Hierarchical Clustering Based on Element-Categorized Connection Subgraphs](https://mlsanity.com/paper/2608.06990/) (2026)
- [Automatic depth-based local center clustering via β-integrated local depth and adaptive grouping](https://mlsanity.com/paper/2609.26748/) (2026)

## Abstract (arXiv)

Clustering is a widely used and powerful machine learning technique, but its effectiveness is often limited by the need to specify the number of clusters, k, or by relying on thresholds that implicitly determine k. We introduce k*-means, a novel clustering algorithm that eliminates the need to set k or any other parameters. Instead, it uses the minimum description length principle to automatically determine the optimal number of clusters, k*, by splitting and merging clusters while also optimising the standard k-means objective. We prove that k*-means is guaranteed to converge and demonstrate experimentally that it significantly outperforms existing methods in scenarios where k is unknown. We also show that it is accurate in estimating k, and that empirically its runtime is competitive with existing methods, and scales well with dataset size.