K^*-means: a parameter-free clustering algorithm

## Abstract

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 italic_k , or by relying on thresholds that implicitly determine k 𝑘 k italic_k . We introduce k ∗ means , a novel clustering algorithm that eliminates the need to set k 𝑘 k italic_k or any other parameters. Instead, it uses the minimum description length principle to automatically determine the optimal number of clusters, k ∗ superscript 𝑘 k^{*} italic_k start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT , by splitting and merging clusters while also optimising the standard k 𝑘 k italic_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 italic_k is unknown. We also show that it is accurate in estimating k 𝑘 k italic_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 minimum description length (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](https://arxiv.org/html/2505.11904v1#S2) discusses related work, Section [3](https://arxiv.org/html/2505.11904v1#S3) describes the algorithm of k^∗means in detail, Section [4](https://arxiv.org/html/2505.11904v1#S4) presents experimental results, and finally Section [6](https://arxiv.org/html/2505.11904v1#S6) concludes and summarises.

## 2 Related Work

Two well-known centroid-based clustering algorithsm are $k$-means, [20, 18] and Gaussian mixture models [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 and its variants do not require specifying the number of clusters, they rely on other parameters—such as eps and min-pts, which specify the neighbourhood size and the number of points required to form a ‘dense region’. OPTICS avoids setting
eps
by computing reachability distances over a range of values, but in its place introduces a steepness parameter to define cluster boundaries (where the reachability value decreases faster than this steepness). Tuning these parameters can yield
a wide range of values for the number of predicted clusters (see Appendix [A](https://arxiv.org/html/2505.11904v1#A1)). Thus, in the absence of prior knowledge about the number of clusters or appropriate parameter values, DBSCAN and its derivatives can be difficult to apply effectively.

X-Means [36] extends $k$-means by automatically determining the optimal number of clusters using the Bayesian information criterion (BIC) [39].
Our method is similar to X-Means in two respects: firstly, in that it selects $k$ using an agnostic criterion from probability/information theory and secondly in that it considers bifurcating each centroid as the means by which to explore different values of $k$. However, there are some important differences between the two methods. Our method uses MDL as the criterion, whereas X-Means uses BIC.
Secondly, our method does not require the $max_{K}$ parameter. It can, in principle, return any value of $k$ (although this would have to be bounded by $N$). Thirdly, X-Means operates in two steps, returning a set of possible models by iteratively using local BIC on each cluster to determine whether it should split, and then using global BIC to select the best model from this set. This means it needs to run $k$-means to convergence multiple times, once for each model. k^∗means, in contrast, returns the best model in one stage, by only splitting when it reduces the MDL, and keeping a pre-initialised pair of sub-centroids for each cluster, which are updated one step at a time while $k$ is being optimised. This means k^∗means only needs to run $k$-means to convergence once. Ishioka [13] uses a very similar method to X-means, keeping a stack of clusters during training, and sequentially running $k$-means with $k$=2 on each. Again, this is much less efficient than k^∗means, which does not need to run multiple models to convergence.

Another common usage of BIC is to select the number of clusters at a model selection stage. It is common in clustering applications to deal with the problem of unknown $k$ by training many $k$-means models with varying values of $k$, and selecting that with the lowest BIC [45, 15, 38]. Our experiments (Section [4.3](https://arxiv.org/html/2505.11904v1#S4.SS3)) find that this is not only much slower than k^∗means, as it requires running many models to convergence, but also less accurate, often severely overestimating $k$. A summary of the clustering algorithms discussed in this section and their parameters is presented in Table [1](https://arxiv.org/html/2505.11904v1#S2.T1).

**Table 1: Common clustering algorithms and their required parameters**
| Algorithm | Required Parameters |
| --- | --- |
| K-means | Number of clusters ($k$) |
| Gaussian Mixture Models (GMM) | Number of components ($k$); Covariance type |
| Spectral Clustering | Number of clusters ($k$); Affinity type |
| Mean Shift | Bandwidth parameter (kernel width) |
| Affinity Propagation | Preference parameter; Damping factor |
| DBSCAN | Neighborhood radius (eps); Minimum points (minpts) |
| HDBSCAN | Minimum cluster size; Minimum samples; Cluster selection eps |
| OPTICS | Cut threshold for eps ($\xi$); Minimum neighborhood points (MinPts) |
| X-Means | Maximum number of clusters; Minimum number of clusters |
| k^∗means | — |

## 3 The k ∗ means Algorithm

### 3.1 Quantifying Description Length

The Minimum Description Length (MDL) principle states that the best representation of the data is the one that can be specified exactly using the fewest number of bits.
In k^∗means, we quantify a bit cost for the various components of a clustering model and how they change over training. This allows k^∗means to directly minimise the description length in a single procedure that simultaneously finds the optimal number of clusters, $k^{*}$, and fits a $k$-means model with $k^{*}$ clusters. The bitcost of a data point $x$ under a clustering model has two parts, the cost of specifying which cluster it belongs to, which we call the *index cost*, and the cost of specifying its displacement from that cluster‘s centroid, which we call the *residual cost*. The former requires selecting an element of $\{0,\dots,K-1\}$, thus taking $\log{K}$ bits. The latter can be approximated, by the Kraft-McMillan inequality, as $-\log{p(x|c)}$, where $c$ is the centroid of $x$’s assigned cluster. We model the cluster distribution as a multivariate normal distribution with unit variance

$$ $\displaystyle p(x|c)$ $\displaystyle=\frac{1}{(2\pi)^{d/2}}\exp\left(-\frac{1}{2}(x-c)^{T}(x-c)\right)$ $\displaystyle\iff-\log{p(x|c)}$ $\displaystyle=\frac{d\log{2\pi}+||x-c||^{2}}{2}\,.$ $$

The total cost of the data under the model is the sum of this cost for all data points, plus the cost of the model itself, which for $k$ clusters, $d$ dimensions and floating point precision $m$, is $kdm$ bits. (The precision $m$ is chosen from the data as the smallest value that allows perfect representation.) This is the quantity minimised by k^∗means. Formally, let $X$ be the data to be clustered. Let $\Pi(X)$ be the set of all partitions of $X$, and let $|P|$ be the number of subsets in a partition. The optimal partition $P^{*}$ is

$$ $P^{*}=\operatorname*{argmin}_{P\in\Pi(X)}|P|dm+|X|\log{|P|}+\frac{1}{2}\sum_{S \in P}Q(S)\,,$ (1) $$

where $Q$ computes the total sum of squares: $Q(X)=|X|\operatorname{Var}{X}$ and then $k^{*}=|P^{*}|$. (Full derivation is provided in Appendix [B](https://arxiv.org/html/2505.11904v1#A2)).

Figure: Algorithm 1 K*-means Algorithm

### 3.2 Minimising Description Length

In this section, we describe the algorithm by which k^∗means efficiently optimises Equation ([1](https://arxiv.org/html/2505.11904v1#S3.E1)). For a more formal exposition, see Algorithm 1.
The familiar Lloyd’s algorithm for $k$-means alternates between two steps: assign, which assigns each point to its nearest centroid, and update, which updates the centroids of each cluster to the mean of all of its assigned points. As well as the centroids and clusters, k^∗means keeps track of subcentroids and subclusters. Subclusters consist of a partition of each cluster into two, and subcentroids are the means of all points in each subcluster. These are updated during the update and assign steps in just the same way as the main clusters and centroids. Essentially, each cluster has a mini version of $k$-means happening inside it during training.

k^∗means introduces two additional steps, maybe-split and maybe-merge, to the standard assign-update procedure. After the assign and update steps, the algorithm calls maybe-split, which uses the subclusters and subcentroids to determine whether any cluster should be split. If no clusters are split, it proceeds with maybe-merge. In the case of a split, each constituent subcluster is promoted to a full cluster, and a new set of subclusters and subcentroids is initialised within each of them, following the k++-means initialisation method [2]. If two clusters are merged, their subclusters are discarded, and the clusters themselves are demoted to become two subclusters inside a new cluster that is their union. k^∗means is initialised with just a single cluster containing all data points (and its two sub-clusters), and then cycles between assign, update, maybe-split and maybe-merge until the assignments remain unchanged for a full cycle. (In practice, for speed, we terminate if the cost has improved by $<2$ in the past 5 cycles. These are not core parameters of the algorithm, and can easily be omitted, in which the runtime is $\sim$30% longer.) In this way, it simultaneously optimises $k$ *and* the standard $k$-means objective, with respect to Equation ([1](https://arxiv.org/html/2505.11904v1#S3.E1)).

#### 3.2.1 Maybe-Split Step

This method (Algorithm 2) checks whether each cluster should be split into two. A naive approach would involve computing Equation ([1](https://arxiv.org/html/2505.11904v1#S3.E1)) for the current parameters and again with the given cluster replaced with its two subclusters, splitting if the latter is smaller. However, we can perform a faster, equivalent check by simply measuring the difference in cost.
If there are currently $k$ clusters, splitting would increase the index cost of each point by $\log(k+1)-\log(k)\approx 1/(k+1)$. It would also decrease the residual cost by $Q(S)-(Q(S_{1})+Q(S_{2}))$, where $S$ is the original cluster and $S_{1},S_{2}$ are its subclusters. To determine whether a split is beneficial, we compute $Q(S)-(Q(S_{1})+Q(S_{2}))$ for every cluster. If any value exceeds $2N/(k+1)$, the cluster with the largest difference is split.

#### 3.2.2 Maybe-Merge Step

This method (Algorithm 3) checks whether a pair of clusters should be merged. To avoid the time taken to compare every pair, we compare only the closest pair of centroids. Analogously to maybe-split, the potential change from merging is $\frac{1}{2}(Q(S)-(Q(S_{1})+Q(S_{2})))-N/k$, where $S_{1}$ and $S_{2}$ are the two clusters with the closest centroids, and $S=S_{1}\cup S_{2}$. If this value is positive, then $S_{1}$ and $S_{2}$ are merged, and become the new subclusters inside the new cluster $S$.

Figure: Algorithm 2 Maybe-Split Procedure

##### Proof of Convergence

We prove in Appendix [C](https://arxiv.org/html/2505.11904v1#A3) that k^∗means is guaranteed to converge in finite time. This is an extension of the proof of convergence for $k$-means, and uses the fact that all four of the steps at each cycle–assign, update, maybe-split, and maybe-merge–can only decrease the cost function in ([1](https://arxiv.org/html/2505.11904v1#S3.E1)).

## 4 Experimental Evaluation

We evaluate our clustering algorithm with three sets of experiments. Firstly, we use synthetic data where we control the true number of clusters and test whether the algorithm can correctly identify this true number. Secondly, we measure performance on labelled data, and compare the predicted cluster labels to the true class labels using supervised clustering metrics. Thirdly, we examine the runtime as a function of dataset size, and show that it scales well compared to existing methods.

### 4.1 Synthetic Data

For a range of values of $k$, we first use Bridson sampling to sample $k$ centroids in $\mathbb{R}^{2}$ near the origin with a minimum inter-point distance of $d$. Then we sample 1000/$k$ points
from a multivariate normal distribution, with unit variance, centred at each centroid. Examples of this synthetic data with varying $d$ are shown in Figure [1](https://arxiv.org/html/2505.11904v1#S4.F1). We then run k^∗means, and comparison methods, on these 1,000 points and compare the number of clusters it finds to $k$. We repeat this 10 times each for each $(k,d)\in\{1,\dots,50\}\times\{2,3,4,5\}$. For each value of $d$, there are 10 examples each of 50 different values of $k$. We compute the accuracy, i.e fraction of these 500 examples with perfectly correct prediction of $k$, and also the mean squared error (MSE) from the predicted $k$ to the true $k$.

Table [2](https://arxiv.org/html/2505.11904v1#S4.T2) presents the results. As can be seen, k^∗means consistently outperforms the baseline algorithms in inferring the value of $k$. Unsurprisingly, its performance improves as the distance between centroids increases, and notably, the accuracy gap between k^∗means and the baselines also widens under these conditions. k^∗means reaches near perfect accuracy in the highly separable setting, c.f. the next highest of HDBSCAN at 58%. Figure [1](https://arxiv.org/html/2505.11904v1#S4.F1) contains visualisations of the predictions of k^∗means.

Figure: Figure 1: Synthetic data of standard, multivariate Normal clusters, with varying degrees of separation. Left: weak separation, inter-centroid distance constrained to $\geq 2$, k^∗means is 9% accurate in inferring $k$ and baselines are $\leq$4.4%. Middle: inter-centroid distance constrained to $\geq~{}3$, k^∗means is 25% accurate in inferring $k$ and baselines are $\leq$16%. Right: strong separation, inter-centroid distance constrained to $\geq 5$, k^∗means is 99% accurate in inferring $k$ and baselines are $\leq$57%.
Refer to caption: extracted/6448360/imgs/min_dist2-plot-20clusters.png

**Table 2: Performance on predicting the true number of clusters in synthetic data for varying degrees of cluster separation. k^∗means performs consistently the best, and reaches near perfect accuracy when $d=5$.**
|  | mse | acc |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  | k^∗means | dbscan | hdbscan | xmeans | k^∗means | dbscan | hdbscan | xmeans |
| synthetic d=2 | 306.35 | 126.10 | 414.73 | 721.54 | 9.00 | 4.40 | 4.00 | 3.80 |
| synthetic d=3 | 81.70 | 252.41 | 116.35 | 681.97 | 25.40 | 5.40 | 7.80 | 16.00 |
| synthetic d=4 | 1.94 | 244.28 | 28.34 | 630.13 | 68.00 | 7.60 | 21.40 | 22.20 |
| synthetic d=5 | 0.00 | 238.18 | 12.83 | 623.99 | 99.80 | 6.60 | 57.60 | 25.40 |

**Table 3: Accuracy on labelled datasets, using supervised metrics. Both with respect to predicting the number of clusters, $k$, and the accuracy with respect to the class labels, (ACC, NMI and ARI), k^∗means significantly outperforms all existing models that do not know the true number of clusters. As an upper-bound, we include results from two standard clustering models that do know $k$, $k$-means and GMM. k^∗means performs very close or even equivalent to these upper bounds, despite not having $k$ or any other parameter, specified. ’-1’ indicates the algorithm still had not converged after 10hrs.**
|  |  | ACC | ARI | NMI | $k$ | Num<br>Outliers | Runtime (s) |
| --- | --- | --- | --- | --- | --- | --- | --- |
|  | affinity | -1.00 | -1.00 | -1.00 | -1.00 | 0 | 36000+ |
|  | meanshift | 77.23 | 63.42 | 80.28 | 7.00 | 0 | 463.39 |
|  | DBSCAN | 68.75 | 54.84 | 77.66 | 6.00 | 1 | 2.95 |
|  | HDBSCAN | 79.73 | 84.84 | 70.70 | 1214.00 | 11190 | 46.24 (0.79) |
| MNIST<br>domain = images<br>n classes = 10 | OPTICS | 0.32 | 0.06 | 36.95 | 20696.00 | 11122 | 225.34 |
| xmeans | 40.89 (4.75) | 34.77 (4.70) | 64.74 (2.25) | 118.80 (23.59) | 0 | 16.40 (6.41) |  |
| k^∗means | 91.26 (3.56) | 84.99 (2.97) | 87.44 (1.14) | 10.90 (0.32) | 0 | 3.38 (0.39) |  |
| \hdashline | kmeans | 84.12 (8.13) | 79.64 (6.92) | 85.31 (2.73) | 10.00 | 0 | 0.09 (0.05) |
|  | GMM | 86.29 (7.05) | 82.61 (6.89) | 87.41 (2.74) | 10.00 | 0 | 0.78 (0.26) |
|  | affinity | 61.29 | 49.37 | 75.94 | 25.00 | 0 | 148.15 |
|  | meanshift | 74.55 | 63.88 | 78.03 | 6.00 | 0 | 27.93 |
|  | DBSCAN | 80.46 | 71.00 | 83.51 | 7.00 | 0 | 0.13 |
|  | HDBSCAN | 77.49 | 82.16 | 79.09 | 108.00 | 829 | 0.80 (0.01) |
| USPS<br>domain = images<br>n classes = 10 | OPTICS | 1.88 | 0.46 | 43.95 | 2681.00 | 1617 | 11.68 |
| xmeans | 55.12 (5.03) | 46.09 (4.23) | 73.27 (1.71) | 41.00 (8.12) | 0 | 1.00 (0.43) |  |
| k^∗means | 88.68 (0.00) | 81.57 (0.00) | 87.14 (0.00) | 8.00 (0.00) | 0 | 0.80 (0.26) |  |
| \hdashline | kmeans | 79.72 (8.15) | 78.68 (6.66) | 86.41 (2.12) | 10.00 | 0 | 0.03 (0.03) |
|  | GMM | 81.72 (6.76) | 80.27 (5.68) | 86.84 (1.82) | 10.00 | 0 | 0.11 (0.01) |
|  | affinity | 41.49 | 27.73 | 57.58 | 46.00 | 0 | 233.19 |
|  | meanshift | 55.98 | 36.05 | 58.67 | 6.00 | 0 | 103.31 |
|  | DBSCAN | 26.09 | 3.70 | 22.00 | 3.00 | 1 | 0.22 |
|  | HDBSCAN | 51.62 | 46.01 | 55.52 | 402.00 | 4193 | 1.09 (0.02) |
| Imagenet<br>(subset)<br>domain = images<br>n classes = 10 | OPTICS | 1.35 | 0.28 | 40.22 | 3916.00 | 2262 | 18.11 |
| xmeans | 39.21 (3.19) | 25.53 (3.03) | 55.92 (0.88) | 70.00 (8.54) | 0 | 2.76 (0.68) |  |
| k^∗means | 66.18 (1.55) | 46.42 (1.45) | 60.20 (0.86) | 6.40 (0.70) | 0 | 0.94 (0.34) |  |
| \hdashline | kmeans | 69.79 (5.18) | 55.08 (4.65) | 64.16 (2.81) | 10.00 | 0 | 0.05 (0.04) |
|  | GMM | 66.85 (6.11) | 53.97 (5.44) | 64.01 (2.76) | 10.00 | 0 | 0.30 (0.09) |
|  | affinity | -1.00 | -1.00 | -1.00 | -1.00 | 0 | 36000+ |
|  | meanshift | 52.08 | 17.89 | 59.53 | 16.00 | 0 | 1205.21 |
|  | DBSCAN | 50.60 | 10.52 | 61.59 | 20.00 | 0 | 2.22 |
|  | HDBSCAN | 65.35 | 67.68 | 67.12 | 2453.00 | 24170 | 53.98 (7.86) |
| Speech<br>Commands<br>domain = audio<br>n classes = 36 | OPTICS | 0.74 | 0.13 | 47.76 | 28932.00 | 17163 | 325.78 |
| xmeans | 26.32 (7.78) | 14.33 (8.22) | 47.70 (18.56) | 190.10 (161.25) | 0 | 16.00 (13.01) |  |
| k^∗means | 68.73 (1.57) | 48.43 (2.49) | 70.22 (0.67) | 26.50 (0.97) | 0 | 20.98 (5.22) |  |
| \hdashline | kmeans | 71.08 (1.72) | 57.78 (1.67) | 72.67 (0.47) | 36.00 | 0 | 0.30 (0.06) |
|  | GMM | 71.04 (1.27) | 56.12 (1.63) | 72.90 (0.42) | 36.00 | 0 | 6.46 (0.89) |
|  | affinity | 40.36 | 23.94 | 48.27 | 75.00 | 0 | 597.33 |
|  | meanshift | 21.50 | 9.19 | 30.45 | 9.00 | 0 | 275.23 |
|  | DBSCAN | 16.40 | 1.98 | 18.59 | 12.00 | 0 | 0.40 |
|  | HDBSCAN | 30.08 | 24.05 | 47.72 | 664.00 | 6153 | 3.27 (0.03) |
| 20 NG<br>domain = text<br>n classes = 20 | OPTICS | 1.60 | 0.27 | 43.73 | 5529.00 | 3211 | 28.84 |
| xmeans | 30.01 (10.66) | 15.48 (8.18) | 37.78 (19.83) | 107.60 (56.16) | 0 | 4.78 (2.51) |  |
| k^∗means | 42.33 (1.14) | 26.08 (0.44) | 46.61 (0.67) | 11.20 (0.42) | 0 | 2.46 (0.96) |  |
| \hdashline | kmeans | 46.73 (1.47) | 33.68 (0.53) | 50.42 (0.48) | 20.00 | 0 | 0.07 (0.06) |
|  | GMM | 47.03 (1.22) | 33.71 (0.78) | 50.68 (0.50) | 20.00 | 0 | 0.86 (0.19) |
|  | affinity | 36.60 | 18.12 | 40.75 | 46.00 | 0.00 | 31.09 |
|  | meanshift | 41.30 | 12.82 | 35.96 | 15.00 | 0.00 | 25.09 |
|  | DBSCAN | 37.65 | 11.51 | 39.23 | 27.00 | 0.00 | 0.05 |
|  | HDBSCAN | 18.40 | 5.90 | 45.39 | 321.00 | 1275.00 | 0.26 (0.73) |
| MSRVTT<br>domain = video & text<br>n classes = 20 | OPTICS | 4.30 | 0.70 | 46.86 | 1763.00 | 1091.00 | 5.02 |
| xmeans | 31.78 (580.54) | 11.64 (965.93) | 24.36 (1441.93) | 32.40 (3924.62) | 0.00 | 0.39 (40.48) |  |
| k^∗means | 44.10 (136.25) | 25.75 (65.28) | 38.16 (33.06) | 18.10 (87.56) | 0.00 | 2.57 (40.59) |  |
| \hdashline | kmeans | 40.07 (108.95) | 25.35 (128.11) | 38.43 (62.75) | 20.00 | 0.00 | 0.04 (1.01) |
|  | GMM | 41.41 (193.57) | 25.28 (101.87) | 38.44 (49.71) | 20.00 | 0.00 | 0.31 (9.16) |

### 4.2 Labelled Datasets

We evaluate k^∗means on six datasets spanning multiple modalities. MNIST and USPS both consist of handwritten digit images from 0–9, Imagenette [12] is a subset of ImageNet with ten image classes, Speech Commands consists of short spoken words for command recognition in 36 classes, 20 NewsGroups is a dataset of text documents across twenty topics, and MSRVTT consists of video clips paired with natural language captions in 20 categories. For all datasets, we dimensionally reduce with UMAP [30] (min-dist=0, n-neighbours=10). For ImageNet we first apply CLIP [37] and for 20 Newsgroups we first take features from Llama-3.1 [40] (mean across all tokens). For MSRVTT, we first take CLIP features of both the video and text (mean across all frames and tokens). As well as tracking the predicted number of classes, we assess partition quality by comparing to the ground truth partition arising from the class labels using three metrics: clustering accuracy (ACC), adjusted rand index (ARI), and normalised mutual information (NMI), as defined, for example in [27].

As baselines for clustering with unknown $k$, we compare to the following: affinity propagation (damping factor = 0.5), mean shift (bandwidth = median of pairwise distances), DBSCAN (eps=0.5, min-samples = 5), HDBSCAN (eps=0.5, min-samples = 5), OPTICS, ($\xi=0.05$, min-samples=5), and XMeans (kmax=$\sqrt{\text{dataset size}}$). These methods are all described in Section [2](https://arxiv.org/html/2505.11904v1#S2) (see also Table [1](https://arxiv.org/html/2505.11904v1#S2.T1)). For XMeans, in the absence of any guidance on selecting kmax, we select it in this way because it is the value at which the information content is roughly equal between the index cost and the residual cost. All other parameter values are the sci-kit learn(^1^11[https://scikit-learn.org/stable/](https://scikit-learn.org/stable/)) defaults.

Our results are summarised in Table [3](https://arxiv.org/html/2505.11904v1#S4.T3). k^∗means consistently outperforms all other methods that do not require setting $k$. Meanshift and DBSCAN tend to underestimate $k$, while affinity propagation, HDBSCAN, XMeans, and OPTICS tend to overestimate it, often by a factor of 10 or more. k^∗means, on average, slightly underestimates $k$, but is much closer than existing methods. It is also much more accurate with respect to the clustering metrics, on some datasets (MNIST, USPS) even performing on par with $k$-means and GMM, which have the *true* value of $k$ specified.

Occasionally (20-NG, MSRVTT), one of the existing methods gets a high NMI score. However, we observe that they also vastly overpredict $k$ in these cases, which means that there are very different numbers of classes in the true and predicted partitions. This can cause NMI to give unreliable results as the entropy in the latter is then unnaturally high. For existing methods, it is quite likely that one could obtain better results by manually tuning the parameters. We find that it is possible to get almost any value of $k$ by such tuning (see Appendix [A](https://arxiv.org/html/2505.11904v1#A1)), but the focus of the present paper is on cases in which the user does not know the true value of $k$. In other words, they do not have a ground truth against which to tune these parameters, and instead have to use the defaults. Table [3](https://arxiv.org/html/2505.11904v1#S4.T3) shows that k^∗means is a much better choice in such cases. Figure [2](https://arxiv.org/html/2505.11904v1#S4.F2) shows example visualisations of the predicted clusters for ImageNet and Speech Commands.

Figure: Figure 2: Clusters predicted by k^∗means for the UMAP representations on the Speech Commands dataset, by k^∗means (left) and XMeans (right). k^∗means predicts 33 classes and XMeans predicts 315, vs. 36 in the annotations.
Refer to caption: extracted/6448360/imgs/ours-speech-commands-scatter.png

### 4.3 Comparison to Sweeping k 𝑘 k italic_k

A common approach when clustering with unknown $k$ is to train $k$-means models with multiple values of $k$, compute some external model-selection criterion, commonly the Bayesian information criterion [39] for each, and select whichever $k$ gives the lowest BIC [43, 45, 15, 38].
Table [4](https://arxiv.org/html/2505.11904v1#S4.T4) shows the performance of this common approach compared to k^∗means. As we are simulating the scenario in which there is no knowledge of $k$, we sweep in increments of 10% up to the dataset size. Sweeping plus BIC selection tends to favour very high values of $k$, generally 4-5x the number of annotated classes. It is also between 10 and 50x slower than k^∗means.

**Table 4: Comparison of k^∗means with the common approach of sweeping $k$ and selecting with BIC. k^∗means is consistently faster and more accurate.**
|  |  | ACC | ARI | NMI | NC | Runtime (s) |
| --- | --- | --- | --- | --- | --- | --- |
| MNIST | sweepkm | 12.86 | 8.17 | 56.01 | 25.00 | 148.15 |
| k^∗means | 91.26 (3.56) | 84.99 (2.97) | 87.44 (1.14) | 10.90 (0.32) | 3.38 (0.39) |  |
| USPS | sweepkm | 32.36 (0.81) | 21.77 (0.77) | 65.20 (0.40) | 68.40 (3.10) | 11.21 (0.73) |
| k^∗means | 88.68 (0.00) | 81.57 (0.00) | 87.14 (0.00) | 8.00 (0.00) | 0.80 (0.26) |  |
| ImageNet (subset) | sweepkm | 8.16 (0.26) | 1.18 (0.05) | 7.62 (0.05) | 83.20 (4.13) | 19.54 (0.23) |
| k^∗means | 66.18 (1.55) | 46.42 (1.45) | 60.20 (0.86) | 6.40 (0.70) | 0.94 (0.34) |  |
| Speech Commands | sweepm | 32.19 (1.27) | 20.10 (0.90) | 62.29 (0.30) | 239.50 (12.12) | 951.58 (11.31) |
| k^∗means | 68.73 (1.57) | 48.43 (2.49) | 70.22 (0.67) | 26.50 (0.97) | 20.98 (5.22) |  |
| 20 NG | sweepkm | 32.75 (0.54) | 17.44 (0.54) | 46.84 (0.17) | 107.30 (5.83) | 36.61 (1.28) |
| k^∗means | 42.33 (1.14) | 26.08 (0.44) | 46.61 (0.67) | 11.20 (0.42) | 2.46 (0.96) |  |
| MSRVTT | sweepkm | 27.50 (89.64) | 12.24 (53.57) | 41.36 (18.64) | 91.60 (464.76) | 7.33 (20.57) |
| k^∗means | 44.10 (136.25) | 25.75 (65.28) | 38.16 (33.06) | 18.10 (87.56) | 2.57 (40.59) |  |

### 4.4 Runtime Analysis

The runtimes from Table [3](https://arxiv.org/html/2505.11904v1#S4.T3) already give an indication of the speed of k^∗means compared with existing methods. To examine this further, and in particular how it depends on dataset size, we use subsets of varying size from the largest of the datasets from Table [3](https://arxiv.org/html/2505.11904v1#S4.T3): Speech Commands which has 99,000 data points.
Figure [3](https://arxiv.org/html/2505.11904v1#S4.F3) shows the runtime of k^∗means, compared to the fastest baselines, on subsets of size $1,000,2,000,\dots,99,000$.
The fastest at all sizes is $k$-means, which remains well under 1s even for 99,000 samples.
The next is DBSCAN, rising to   $\sim$3s, then the GMM $\sim$5s and k^∗means $\sim$8s.

Figure: Figure 3: Runtime as a function of dataset size. Each point represents the mean runtime of 10 randomly sampled subsets from the Speech Commands dataset of the given size. The line tracks windowed averages. k^∗means has a similar speed to xmeans, faster than HDBSCAN, especially for larger input sizes, and slower than kmeans, DBSCAN and GMM.
Refer to caption: extracted/6448360/imgs/clustering_runtime-1000-ntrials5-slowsFalse.png

HDBSCAN is efficient for small samples, faster than k^∗means and GMM, but increases much faster, and by 99,000 samples its runtime is 6x that of k^∗means. XMeans is the most erratic, by far the slowest for small sample sizes, but increasing very little or even decreasing, and ending up close to k^∗means. The reason for the surprising decrease could be that XMeans predicts fewer clusters for larger datasets. It could also be related to the optimised C-Engine that the public XMeans code makes use of(^2^22[https://pyclustering.github.io](https://pyclustering.github.io)). Note that Figure [3](https://arxiv.org/html/2505.11904v1#S4.F3) shows only the fastest five algorithms. Mean-shift, affinity propagation and OPTICS are all substantially slower and would be off the chart if included.

## 5 Limitations

k^∗means lacks a theoretical guarantee of worst-case runtime. Also, it assumes roughly spherical clusters, which often does not hold in practice. However, both of these criticisms also apply to the original $k$-means [21], and they have not prevented it being the most used clustering algorithm.

## 6 Conclusion

This paper presented a new clustering algorithm, k^∗means, which can be applied in the absence of knowing $k$ and does not require setting any other parameters such as thresholds. We prove that k^∗means is guaranteed to converge, and we show empirically on synthetic data that it can more accurately infer $k$ than comparison methods, and with near-perfect accuracy for sufficiently separated centroids. We then test it on six labelled datasets spanning image, text, audio and video domains, and show that it is significantly more accurate than existing methods in terms of standard clustering metrics. We also compare it to the standard practice of sweeping $k$ in $k$-means and selecting with a model selection criterion. Finally, we demonstrate how its runtime scales with dataset size, and show that it is faster, and scales better than the majority of existing methods. k^∗means can be useful in cases where the user has large uncertainty as to the appropriate value of $k$.

## References

- Ankerst et al. [1999]
Mihael Ankerst, Markus M Breunig, Hans-Peter Kriegel, and Jörg Sander.
Optics: ordering points to identify the clustering structure.
In *Proceedings of the 1999 ACM SIGMOD international conference on Management of data*, pages 49–60, 1999.
- Arthur and Vassilvitskii [2006]
David Arthur and Sergei Vassilvitskii.
k-means++: The advantages of careful seeding.
Technical report, Stanford, 2006.
- Campello et al. [2013]
Ricardo JGB Campello, Davoud Moulavi, and Joerg Sander.
Density-based clustering based on hierarchical density estimates.
*Pacific-Asia conference on knowledge discovery and data mining*, pages 160–172, 2013.
- Caron et al. [2018]
Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze.
Deep clustering for unsupervised learning of visual features.
In *Proceedings of the European conference on computer vision (ECCV)*, pages 132–149, 2018.
- Comaniciu and Meer [2002]
Dorin Comaniciu and Peter Meer.
Mean shift: A robust approach toward feature space analysis.
*IEEE Transactions on Pattern Analysis and Machine Intelligence*, 24(5):603–619, 2002.
- Dempster et al. [1977]
Arthur P Dempster, Nan M Laird, and Donald B Rubin.
Maximum likelihood from incomplete data via the em algorithm.
*Journal of the royal statistical society: series B (methodological)*, 39(1):1–22, 1977.
- Ester et al. [1996]
Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu.
A density-based algorithm for discovering clusters in large spatial databases with noise.
In *Proceedings of the Second International Conference on Knowledge Discovery and Data Mining*, pages 226–231. AAAI Press, 1996.
- Fini et al. [2023]
Enrico Fini, Pietro Astolfi, Karteek Alahari, Xavier Alameda-Pineda, Julien Mairal, Moin Nabi, and Elisa Ricci.
Semi-supervised learning made simple with self-supervised clustering.
In *Proceedings of the IEEE/CVF conference on computer vision and pattern recognition*, pages 3187–3197, 2023.
- Frey and Dueck [2007]
Brendan J Frey and Delbert Dueck.
Clustering by passing messages between data points.
*Science*, 315(5814):972–976, 2007.
- Graham et al. [1994]
Ronald L. Graham, Donald E. Knuth, and Oren Patashnik.
*Concrete Mathematics: A Foundation for Computer Science*.
Addison-Wesley, 2nd edition, 1994.
ISBN 9780201558029.
URL [https://archive.org/details/B-001-002-135](https://archive.org/details/B-001-002-135).
- Hebdon et al. [2025]
Nicholas Hebdon, Alexa Ortega, Alexander Orlove, Nichole Wheeler, Mia Pham, Vivian Nguyen, Justin Gladman, and Lindsay D. Waldrop.
Dog skull shape challenges assumptions of performance specialization from selective breeding.
*Science Advances*, 11(5):eadq9590, 2025.
doi: 10.1126/sciadv.adq9590.
URL [https://www.science.org/doi/abs/10.1126/sciadv.adq9590](https://www.science.org/doi/abs/10.1126/sciadv.adq9590).
- Howard and Gugger [2019]
Jeremy Howard and Sylvain Gugger.
Imagenette.
[https://github.com/fastai/imagenette](https://github.com/fastai/imagenette), 2019.
- Ishioka [2000]
Tsunenori Ishioka.
Extended k-means with an efficient estimation of the number of clusters.
*Ouyou toukeigaku*, 29(3):141–149, 2000.
- Kisi et al. [2025]
Ozgur Kisi, Salim Heddam, Kulwinder Singh Parmar, Andrea Petroselli, Christoph Külls, and Mohammad Zounemat-Kermani.
Integration of gaussian process regression and k means clustering for enhanced short term rainfall runoff modeling.
*Scientific Reports*, 15(1):7444, 2025.
- Lancaster and Camarata [2019]
Hope S Lancaster and Stephen Camarata.
Reconceptualizing developmental language disorder as a spectrum disorder: issues and evidence.
*International Journal of Language & Communication Disorders*, 54(3):319–327, 2019.
- Liu et al. [2023a]
Alexander H. Liu, Anmol Gulati, Shubham Narang, Ruoming Pang, and Yonghui Wu.
Dinosr: Self-distillation and online clustering for self-supervised speech representation learning.
In *Advances in Neural Information Processing Systems*, 2023a.
URL [https://proceedings.neurips.cc/paper_files/paper/2023/file/b6404bf461c3c3186bdf5f55756af908-Paper-Conference.pdf](https://proceedings.neurips.cc/paper_files/paper/2023/file/b6404bf461c3c3186bdf5f55756af908-Paper-Conference.pdf).
- Liu et al. [2023b]
Meng Liu, Yue Liu, Ke Liang, Wenxuan Tu, Siwei Wang, Sihang Zhou, and Xinwang Liu.
Deep temporal graph clustering.
*arXiv preprint arXiv:2305.10738*, 2023b.
- Lloyd [1982]
Stuart Lloyd.
Least squares quantization in pcm.
*IEEE Transactions on Information Theory*, 28(2):129–137, 1982.
- Ma et al. [2023]
Jie Ma, Ling Liu, Cong Chen, and Zhou Yu.
Structured federated learning through clustered additive modeling.
In *Advances in Neural Information Processing Systems*, 2023.
URL [https://proceedings.neurips.cc/paper_files/paper/2023/file/8668fdc7b2ddf55a0e235824c66f2eee-Paper-Conference.pdf](https://proceedings.neurips.cc/paper_files/paper/2023/file/8668fdc7b2ddf55a0e235824c66f2eee-Paper-Conference.pdf).
- MacQueen [1967]
James MacQueen.
Some methods for classification and analysis of multivariate observations.
1(14):281–297, 1967.
- Mahajan et al. [2012]
Meena Mahajan, Prajakta Nimbhorkar, and Kasturi Varadarajan.
The planar k-means problem is np-hard.
*Theoretical computer science*, 442:13–21, 2012.
- Mahon [2024]
Louis Mahon.
Towards a universal method for meaningful signal detection.
*arXiv preprint arXiv:2408.00016*, 2024.
- Mahon [2025]
Louis Mahon.
Local compositional complexity: How to detect a human-readable messsage.
*arXiv preprint arXiv:2501.03664*, 2025.
- Mahon and Lapata [2024]
Louis Mahon and Mirella Lapata.
A modular approach for multimodal summarization of TV shows.
In Lun-Wei Ku, Andre Martins, and Vivek Srikumar, editors, *Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)*, pages 8272–8291, Bangkok, Thailand, August 2024. Association for Computational Linguistics.
doi: 10.18653/v1/2024.acl-long.450.
URL [https://aclanthology.org/2024.acl-long.450](https://aclanthology.org/2024.acl-long.450).
- Mahon and Lapata [2025]
Louis Mahon and Mirella Lapata.
Parameter-free video segmentation for vision and language understanding.
*arXiv preprint arXiv:2503.01201*, 2025.
- Mahon and Lukasiewicz [2021]
Louis Mahon and Thomas Lukasiewicz.
Selective pseudo-label clustering.
In *KI 2021: Advances in Artificial Intelligence: 44th German Conference on AI, Virtual Event, September 27–October 1, 2021, Proceedings 44*, pages 158–178. Springer, 2021.
- Mahon and Lukasiewicz [2024a]
Louis Mahon and Thomas Lukasiewicz.
Hard regularization to prevent deep online clustering collapse without data augmentation.
In *Proceedings of the AAAI Conference on Artificial Intelligence*, volume 38, pages 14281–14288, 2024a.
- Mahon and Lukasiewicz [2024b]
Louis Mahon and Thomas Lukasiewicz.
Minimum description length clustering to measure meaningful image complexity.
*Pattern Recognition*, 145:109889, 2024b.
- Markovitz et al. [2020]
Amir Markovitz, Gilad Sharir, Itamar Friedman, Lihi Zelnik-Manor, and Shai Avidan.
Graph embedded pose clustering for anomaly detection.
In *Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)*, June 2020.
- McInnes et al. [2018]
Leland McInnes, John Healy, and James Melville.
UMAP: Uniform manifold approximation and projection for dimension reduction.
*arXiv:1802.03426*, 2018.
- Meyer et al. [2025]
Ole Meyer, Rebecca Diekmann, Sandra Hellmers, Andreas Hein, and Anna Schumacher.
Uncovering hidden insights in the chair rise performance of older adults using dynamic time warping and k-means clustering.
*Scientific Reports*, 15(1):7654, 2025.
- Miklautz et al. [2024]
Lukas Miklautz, Timo Klein, Kevin Sidak, Collin Leiber, Thomas Lang, Andrii Shkabrii, Sebastian Tschiatschek, and Claudia Plant.
Breaking the reclustering barrier in centroid-based deep clustering.
*arXiv preprint arXiv:2411.02275*, 2024.
- Mo et al. [2024]
Yujie Mo, Zhihe Lu, Runpeng Yu, Xiaofeng Zhu, and Xinchao Wang.
Revisiting self-supervised heterogeneous graph learning from spectral clustering perspective.
*Advances in Neural Information Processing Systems*, 37:43133–43163, 2024.
- Ng et al. [2001]
Andrew Y Ng, Michael I Jordan, and Yair Weiss.
On spectral clustering: Analysis and an algorithm.
In *Advances in neural information processing systems*, pages 849–856, 2001.
- Niu et al. [2024]
Shengjie Niu, Wenjie Zhang, Yanyan Liang, and Xia Hu.
Owmatch: Conditional self-labeling with consistency for open-world semi-supervised learning.
In *Advances in Neural Information Processing Systems*, 2024.
URL [https://proceedings.neurips.cc/paper_files/paper/2024/file/b4fd162d3e2d015233486a2e313828a7-Paper-Conference.pdf](https://proceedings.neurips.cc/paper_files/paper/2024/file/b4fd162d3e2d015233486a2e313828a7-Paper-Conference.pdf).
- Pelleg and Moore [2000]
Dan Pelleg and Andrew W Moore.
X-means: Extending k-means with efficient estimation of the number of clusters.
In *Proceedings of the Seventeenth International Conference on Machine Learning*, pages 727–734. Morgan Kaufmann, 2000.
- Radford et al. [2021]
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever.
Learning transferable visual models from natural language supervision.
In Marina Meila and Tong Zhang, editors, *Proceedings of the 38th International Conference on Machine Learning*, volume 139 of *Proceedings of Machine Learning Research*, pages 8748–8763. PMLR, 18–24 Jul 2021.
URL [https://proceedings.mlr.press/v139/radford21a.html](https://proceedings.mlr.press/v139/radford21a.html).
- Salmanpour et al. [2022]
Mohammad R Salmanpour et al.
Longitudinal clustering analysis and prediction of parkinson’s disease progression.
*Quantitative Imaging in Medicine and Surgery*, 12(3):292–300, 2022.
- Schwarz [1978]
Gideon Schwarz.
Estimating the dimension of a model.
*The annals of statistics*, pages 461–464, 1978.
- Touvron et al. [2023]
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample.
Llama: Open and efficient foundation language models, 2023.
- Vo et al. [2024]
Huy V Vo, Vasil Khalidov, Timothée Darcet, Théo Moutakanni, Nikita Smetanin, Marc Szafraniec, Hugo Touvron, Camille Couprie, Maxime Oquab, Armand Joulin, et al.
Automatic data curation for self-supervised learning: A clustering-based approach.
*arXiv preprint arXiv:2405.15613*, 2024.
- Wagner and Harmeling [2024]
Stefan S. Wagner and Stefan Harmeling.
Just cluster it: An approach for exploration in high-dimensions using clustering and pre-trained representations.
In *International Conference on Machine Learning*, 2024.
URL [https://proceedings.mlr.press/v235/wagner24a.html](https://proceedings.mlr.press/v235/wagner24a.html).
- Wessman et al. [2012]
Jaana Wessman, Stefan Schönauer, Jouko Miettunen, Hannu Turunen, Pekka Parviainen, Jukka K. Seppänen, Eliza Congdon, Susan Service, Liisa Keltikangas-Järvinen, Jesper Ekelund, Jouko Lönnqvist, Nelson B. Freimer, Juha Veijola, Heikki Mannila, and Leena Peltonen.
Temperament clusters in a normal population: Implications for health and disease.
*PLOS ONE*, 7(7):e33088, 2012.
doi: 10.1371/journal.pone.0033088.
URL [https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0033088](https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0033088).
- Xu et al. [2025]
Gaoqing Xu, Qun Chen, Shuhang Jiang, Xiaohang Fu, Yiwei Wang, and Qingchun Jiao.
Analyzing the capability description of testing institution in chinese phrase using a joint approach of semi-supervised k-means clustering and bert.
*Scientific Reports*, 15(1):11331, 2025.
- Zhang and Li [2014]
Sheng Zhang and Chiang-shan R Li.
Functional clustering of the human inferior parietal lobule by whole-brain connectivity mapping of resting-state fmri signals.
*Brain Connectivity*, 4(7):547–557, 2014.

## Appendix A Dependence of k 𝑘 k italic_k on DBSCAN Parameters

Although DBSCAN does not explicitly require setting $k$, its two key parameters,eps and min-pts, essentially determine a value for $k$ indirectly. As can be seen in Figure [4](https://arxiv.org/html/2505.11904v1#A1.F4) the different values for $k$ found by DBSCAN for different values of eps and min-pts range from 6 to over 4,000. In general, smaller eps and smaller min-pts produces more clusters. The number of annotated classes is 10.

Figure: Figure 4: Values of $k$ (number of clusters) found on MNIST for different values of the DBSCAN parameters, min-pts (x-axis) and eps (y-axis). We sweep min-pts from 1–40, and eps from 0.03 to 1.5 in 5% increments.
Refer to caption: extracted/6448360/imgs/dbscan-varied-eps-minpts.png

## Appendix B Derivation of MDL Clustering Objective

The objective to derive is that from Section [3.1](https://arxiv.org/html/2505.11904v1#S3.SS1):

$$ $P^{*}=\operatorname*{argmin}_{P\in\Pi(X)}|P|dm+|X|\log{|P|}+\frac{1}{2}\sum_{S \in P}Q(S)\,.$ $$

The first two terms are direct expressions of the cost to specify the centroids (each costs $dm$ bits and there are $|P|$ of them), and the cluster labels (each costs $\log{|P|}$ bits and there are $|X|$ of them. The third term arises from the expression for the negative log-probability, and the fact that we can drop additive constants in the argmin. Let $c(P,x)$ be the centroid of the cluster $x$ belongs to under partition $P$. Then

$$ $\displaystyle\operatorname*{argmin}_{P\in\Pi(X)}|P|dm+|X|\log{|P|}+\sum_{x\in X }\frac{d\log{2\pi}+||x-c(P,x)||^{2}}{2}=$ $\displaystyle\operatorname*{argmin}_{P\in\Pi(X)}|P|dm+|X|\log{|P|}+\frac{1}{2} \sum_{x\in X}||x-c(P,x)||^{2}=$ $\displaystyle\operatorname*{argmin}_{P\in\Pi(X)}|P|dm+|X|\log{|P|}+\frac{1}{2} \sum_{S\in P}\sum_{x\in S}||x-c(P,x)||^{2}=$ $\displaystyle\operatorname*{argmin}_{P\in\Pi(X)}|P|dm+|X|\log{|P|}+\frac{1}{2} \sum_{S\in P}Q(S)\,.$ $$

## Appendix C Proof of Convergence

The k^∗means algorithm is guaranteed to converge. We now provide a proof of this fact.

###### Lemma 1 .

At each assign step (which is the same step as vanilla $k$-means), the MDL cost either decreases or remains the same, and it remains the same only if no points are reassigned.

###### Proof.

As defined in Section [3.1](https://arxiv.org/html/2505.11904v1#S3.SS1), there are two components to the MDL cost: the index cost, consisting of the bits to specify the cluster membership of each point, and the residual cost, consisting of the bits corresponding to the displacement of each from its cluster centre. The former depends only on the number of points $N$ and the number of clusters $k$, and is unaffected by re-assignment. The latter is proportional to the sum of squared distances of each point to its assigned centre. By definition of reassignment, if a point is reassigned, then it is closer to its new centroid than its old centroid. Thus, every reassignment does not affect the first two summands of the cost and strictly reduces the third.
∎

###### Lemma 2 .

At each update step (which is the same step as vanilla $k$-means), the MDL cost either decreases or remains the same, and it remains the same only if no centroids are updated.

###### Proof.

As with the assign step, the update step does not change $k$ or $N$ and so does not affect the index cost. The latter can be written as the sum across clusters of the sum of all points in that cluster from the centroid. When the centroids are updated, they are updated to the mean of all points of points in the cluster, which is the unique minimiser of the sum of squared distances. As well as a standard statistical fact, this can be seen by observing that the $SS(x)=\sum_{i=1}^{m}(x-x_{i})^{2}$ is a u-shaped function of $x$, so achieves its global minimum when

$$ $\displaystyle SS^{\prime}(x)=0\iff$ $\displaystyle 2\sum_{i=1}^{m}x-x_{i}=2mx-2\sum_{i=1}^{m}x_{i}=0\iff$ $\displaystyle x=\frac{1}{m}\sum_{i=1}^{m}x_{i}\,.$ $$

This holds for the reassignment of each cluster, and so for the whole reassignment step.
∎

###### Theorem 3 .

The k^∗means algorithm is guaranteed to converge in finite time.

###### Proof.

By Lemmas [1](https://arxiv.org/html/2505.11904v1#Thmtheorem1) and [2](https://arxiv.org/html/2505.11904v1#Thmtheorem2), the MDL cost strictly decreases at each step at which points are reassigned and centroids updated. The other two steps, maybe-split and maybe-merge, include explicit steps that the MDL cost decreases before being performed, so also are guaranteed to strictly decrease the MDL cost. Together, this means the algorithm will never revisit an assignment during training. Moreover, there are a finite number of assignments, equal to the number of partitions of $N$ data points, which is given by the $N+1$th Bell number [10], $B_{N+1}$. Therefore k^∗means cannot run for more than a finite number, namely $B_{N+1}$, steps.
∎

###### Remark 4 .

This is an extension of the standard proof of convergence of $k$-means. Like for $k$-means, this proof establishes a theoretical worst-case run time which is exponential but then, in practice, the algorithm converges quickly. Practical empirical runtimes are studied in detail in Section [4](https://arxiv.org/html/2505.11904v1#S4).

###### Lemma 1 .

###### Proof.

###### Lemma 2 .

###### Proof.

###### Theorem 3 .

###### Proof.

###### Remark 4 .

## Peer Reviews

confidence: 4
contribution: 1
initial_rating: 0
presentation: 3
questions: NaN
soundness: 2
strengths: They introduce k∗means, an entirely parameter-free clustering algorithm
For carefully constructed synthetic data, k∗means can infer the true number of clusters, and shows much higher accuracy than existing methods;
summary: This paper introduces a parameter-free clustering algorithm named k*means, which aims to eliminate the need for manual specification of the cluster number k and does not introduce any other parameters. The authors provide a theoretical proof of the algorithm's convergence within a finite time. Furthermore, through comprehensive experiments on diverse multimodal datasets, they demonstrate that k*means outperforms most established baseline methods.
weaknesses: The performance advantage of the proposed algorithm over existing methods appears to be marginal. As shown in Table 3, the accuracy of 
k*means does not demonstrate a significant improvement across most datasets.

The synthetic experiments are limited to clusters generated from multivariate normal distributions with fixed variance. 
The algorithm's robustness remains unverified under more complex and challenging data scenarios, such as non-convex clusters (e.g., ring-shaped), uneven cluster densities, or datasets with a high proportion of noise (e.g., >20%).

The literature review primarily contrasts the method with traditional parameter-free algorithms. However, it omits comparisons with recent advancements in this direction (e.g., PFMVKM) as well as other relevant classical algorithms (e.g., DPC). This omission may lead to an incomplete and potentially less convincing performance evaluation.

A theoretical analysis of the algorithm's time and space complexity is absent, which is crucial for understanding its scalability and practical utility.

Minor Concerns:

Some algorithms included in the empirical comparison (e.g., DPMM in Table 3) are not introduced in the Related Work section.

The algorithm name "K-Means++" is incorrectly written as "k++means" in multiple instances throughout the manuscript and should be corrected.

Table 1: There is excessive blank space above the X-Means row.

Table 5: The table appears to be cut off and is not displayed fully.
The same issue occurs with the equation on Page 17.

---

confidence: 4
contribution: 2
initial_rating: 4
presentation: 3
questions: 125: This line is misleading because under certain conditions, BIC and MDL are equivalent.

161: Explain briefly why and how the Kraft-McMillan inequality is relevant and used.

162, 271: What does "noend" mean?

172: What does the notation [ ] mean in the RHS [{...}, {...}]?

186: What does max(X) mean given that X is a set of high-dimensional points, not of scalars?

203: How sensitive is the algorithm to the value of m? Why is this the best value of m?

336: Should be ImageNette and not ImageNet?
soundness: 3
strengths: The proposed approach is sensible and the algorithm works quite well in the experiments, which are designed reasonably well.
summary: This paper presents an extension of k-means that infers the appropriate number k of clusters. The algorithm is a heuristic method to minimize the description length of the input data.
weaknesses: - This paper could have been written 20 years ago. It does not really engage with the current research in machine learning that is most relevant to ICLR. 

- The algorithm is fundamentally heuristic. The proof of convergence says only that the method reaches a local optimum after a finite number of steps. The bound on performance in Appendix D is potentially more interesting. However, the bound is not stated as a formal theorem, and the proof is long enough that this reviewer has not checked it. Lines 826 and 942 appear to say that the proof is merely about the initialization, and therefore not about the new algorithm in a substantive way. Equation 5 is complicated enough that it is not obvious when the RHS provides a trivial bound and when it is non-trivial.

- Since the algorithm is heuristic, the authors should describe how it is better than obvious variations on the same theme. In particular, it seems inefficient to consider splitting every center at every iteration. A different heuristic would be to consider splitting just the highest-cost center. However, something else missing in this submission is a discussion of time complexity (Table 3 is only empirical). At first sight, the "assign" step is much more expensive than the "update" step", which itself is much more expensive than the splitting and merging operations, because the latter involve computations on scalars only (not vectors of length d). So perhaps MDL would be minimized better and faster with more splitting and merging operations, and fewer "update" steps, and/or "update" steps that operate only on points with changed centers.

- The subroutines INITSUBCENTROIDS and KMEANSSTEP are described generally, but not given explicitly as pseudocode


Missing comparisons to related research:
- Unsupervised learning using MML by JJ Oliver, RA Baxter, CS Wallace, ICML, 1996 
- P.Kontkanen, P.Myllymaki, W.Buntine, J.Rissanen, H.Tirri, An MDL Framework for Data Clustering. In Advances in Minimum Description Length: Theory and Applications, edited by P. Gr ̈unwald, I.J. Myung and M. Pitt. MIT Press, 2005
- A novel split and merge EM algorithm for gaussian mixture model by Y Li, L Li, 2009 Fifth International Conference on Natural Computation

---

confidence: 5
contribution: 2
initial_rating: 4
presentation: 3
questions: Q1. Experimental comparison ignores several well-known or state-of-the-art methods for number of clusters estimation (see W2). Some methods are available in the ClustPy library.
Q2. The method should be tested on datasets with imbalanced clusters and/or not clearly separated clusters.
Q3. More complex datasets should be considered in the clustering comparison. In the present work dimensionality reduction takes place 
to tackle increased dimensionality, thus the clustered datasets are low-dimensional.
Q4. The method tends to underestimate the number of clusters. This is due to the fact that the MDL term is relatively big resulting in conservative estimations. This is in my opinion the main drawback of the proposed approach.
Q5. How often is merging actually triggered in the experiments? Could you provide ablation results (with vs. without merging) to demonstrate its impact?
soundness: 3
strengths: S1. The method automatically estimates the number of clusters k.
S2. It does not make use of any hyperparameter
S3. All operations ensure the minimization of the objective function.
summary: The paper proposes k*means, a parameter-free variant of k-means that automatically determines the number of clusters through the minimization of an objective (eq. 1) that involves a k-means loss term and an MDL term. The interesting aspect of the method is that it includes split and merge operations in addition to typical k-means operations that increase or decrease k always ensuring that the proposed objective is improved. Therefore, it is guaranteed that this dynamic method will converge to a minimum of the objective.
Actually, the method extends x-means which is an old incremental method (only cluster splitting takes place) based on BIC/MDL.
weaknesses: W1. Although MDL is theoretically justified, it is not considered efficient or robust in practical finite-sample settings. For this reason the MDL-based x-means algorithm has been first replaced by a Gaussianity-based criterion (g-means algorithm) and later by a unimodality-based criterion (dip-means algorithm). 
W2. Related work omits significant contributions in number of clusters estimation, such as g-means, dip-means and  more recently the Uniforce and DipDeck algorithms to mention some of them.
W3. The experimental part ignores the majority of well-known methods that conduct automatic number of clusters estimation. 
W4. Since the method starts with a single cluster, the usefulness of the merging operation is questionable.