K ∗ -Means: A Parameter-free Clustering Algorithm

Louis Mahon, Mirella Lapata · 2025

Read K ∗ -Means: A Parameter-free Clustering Algorithm by Louis Mahon, Mirella Lapata (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-11904.txt.

Introduction

Louis Mahon and Mirella Lapata introduce a clustering method that chooses the number of groups by itself. Their 2025 paper tackles a standing annoyance in machine learning: the classic k-means method needs the user to supply k, the group count, in advance. Guesses and hidden thresholds often decide the answer before the data speaks.

Their method instead follows the minimum description length principle, favoring the grouping that compresses the data best. It splits and merges groups while improving the usual k-means fit, settling on its own count. The authors prove the process always settles. In experiments it beat rival methods when the true count was unknown, estimated that count accurately, and ran at competitive speeds even as data grew.

Catalog record

CREATORLouis Mahon, Mirella Lapata
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE40 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-11904

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

K ∗ -Means: A Parameter-free Clustering Algorithm Louis Mahon, Mirella Lapata Abstract 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 k , or by relying on thresholds that implicitly determine k k . We introduce k ∗ means , a novel clustering algorithm that eliminates the need to set k k or any other parameters. Instead, it uses the minimum description length principle to automatically determine the optimal number of clusters, k ∗ k^{*} , by splitting and merging clusters while also optimising the standard k 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 k is unknown. We also show that it is accurate in estimating k k , and that empirically its runtime is competitive with existing methods, and scales well with dataset size. 1 Introduction Clustering is a fundamental task in machine learning. As well as allowing data visualisation and exploration, it is used for several more specific functions in the context of machine learning systems, such as representation learning [ 16 , 35 ] , federated learning [ 19 ] , exploration in reinforcement learning [ 42 ] , anomaly detection [ 29 ] , and has found widespread application in the natural sciences [ 44 , 14 , 31 , 11 ] . It has also been interwoven with deep learning feature extraction in the areas of deep clustering [ 4 , 26 , 32 , 17 , 41 ] and deep graph clustering [ 33 , 8 ] . Clustering can produce meaningful and interpretable partitions of data, even in the absence of information typically required by other machine learning methods, such as annotated class labels. However, almost all existing clustering algorithms still require some user-set parameters, which limits their applicability to cases where the user can choose appropriate values. Two common classes of clustering algorithms are centroid-based and density-based. The former, typified by k -means, work by finding the optimal location for cluster centre-points (centroids), and then assigning points to nearby centres. These algorithms generally require the user to specify the number of clusters. Density-based algorithms aim to locate clusters where the density of points is high. They also require some threshold(s) to determine what constitutes a high-density region and where to separate them. In this paper, we design a clustering algorithm that eliminates the need for setting the number of clusters, tunable thresholds, or any other parameters. Our algorithm, k ∗ means , extends k -means by automatically determining the optimal number of clusters, k , using the mdl ( mdl ) principle. The MDL principle states that the optimum data representation is that containing the fewest bits. It has been shown to be effective in a number of applied tasks, including complexity quantification [ 28 , 22 , 23 ] and temporal segmentation [ 24 , 25 ] . k ∗ means uses MDL by optimising the information-theoretic objective of minimising the description length of the data under the model. Specifically, this is quantified as the number of bits required to represent the cluster centroids, and the cluster labels of each point, which we refer to as the index cost , along with the number of bits needed to represent the displacement of each point from its centroid, termed the residual cost . Too many clusters creates a prohibitively high index cost, while too few creates a prohibitively high residual cost, so the objective guides the model towards a reasonable value of k . We optimise this objective by including in the model two subclusters of every cluster. The “assign” and “update” steps of k -means are applied to the subclusters in the same way as to the main clusters, and the algorithm has the option to split a cluster into its two subclusters, or to merge two clusters together, if it will reduce the overall description length. Despite its simplicity, k -means remains the most widely used clustering algorithm, because it is fast, provably guaranteed to converge, has just one easily interpretable parameter, and achieves accuracy competitive with more complicated methods. We aim to maintain these advantages with k ∗ means . We provide a proof that k ∗ means is also guaranteed to converge. Additionally, our experiments show that k ∗ means largely maintains the speed and accuracy advantages of k -means. It is as fast or faster than most other k -agnostic clustering methods, scales well with dataset size, and is close to or on par with the accuracy of k -means, even when k -means has an oracle for the true value of k . We also show in synthetic experiments that it can successfully identify k more accurately than existing methods. Our contributions are summarised as follows: • We introduce k ∗ means , an entirely parameter-free clustering algorithm; • We give a formal proof that k ∗ means will convergence in finite time; • We design synthetic data experiments to test whether k ∗ means can infer the true value of k , and show that it can with much higher accuracy than existing methods; • We show experimentally that, with respect to standard clustering metrics, it is more accurate than all existing methods that do not require setting k , and is as fast as or faster than the majority of these methods. The remainder of this paper is organised as follows. Section 2 discusses related work, Section 3 describes the algorithm of k ∗ means in detail, Section 4 presents experimental results, and finally Section 6 concludes and summarises. 2 Related Work Two well-known centroid-based clustering algorithsm are k -means, [ 20 , 18 ] and gmm [ 6 ] . The former partition data into k clusters by iteratively assigning points to the nearest centroid and updating centroids until convergence, and the latter which fit a multivariate normal model via expectation maximization. A number of more complex clustering algorithms are also in widespread use. Spectral Clustering [ 34 ] transforms data using eigenvectors of a similarity matrix before applying a clustering algorithm such as k -means. Mean Shift [ 5 ] discovers clusters by iteratively shifting points toward areas of higher density until convergence. It does not require setting k , but does require a bandwidth parameter. Affinity Propagation [ 9 ] identifies exemplars among data points and forms clusters by exchanging messages between pairs of samples until convergence. Like mean shift, it does not require specifying the number of clusters k , but instead relies on a preference parameter and a damping factor. A common drawback of both mean shift and affinity propagation is their quadratic space complexity, which limits scalability. DBSCAN [ 7 ] identifies dense regions as clusters by grouping points with many neighbours, while marking sparse points as noise. OPTICS [ 1 ] extends DBSCAN by ordering points based on reachability distance, allowing it to identify clusters with varying densities. HDBSCAN [ 3 ] further builds on DBSCAN by introducing a hierarchical clustering framework that extracts flat clusters based on stability. Although DBSCAN

Read the complete text