k is the Magic Number - Inferring the Number of Clusters Through Nonparametric Concentration Inequalities

Sibylle Hess, Wouter Duivesteijn

Abstract

Most convex and nonconvex clustering algorithms come with one crucial parameter: the $k$ in $k$-means. To this day, there is not one generally accepted way to accurately determine this parameter. Popular methods are simple yet theoretically unfounded, such as searching for an elbow in the curve of a given cost measure. In contrast, statistically founded methods often make strict assumptions over the data distribution or come with their own optimization scheme for the clustering objective. This limits either the set of applicable datasets or clustering algorithms. In this paper, we strive to determine the number of clusters by answering a simple question: given two clusters, is it likely that they jointly stem from a single distribution? To this end, we propose a bound on the probability that two clusters originate from the distribution of the unified cluster, specified only by the sample mean and variance. Our method is applicable as a simple wrapper to the result of any clustering method minimizing the objective of $k$-means, which includes Gaussian mixtures and Spectral Clustering. We focus in our experimental evaluation on an application for nonconvex clustering and demonstrate the suitability of our theoretical results. Our SpecialK clustering algorithm automatically determines the appropriate value for $k$, without requiring any data transformation or projection, and without assumptions on the data distribution. Additionally, it is capable to decide that the data consists of only a single cluster, which many existing algorithms cannot.

Introduction

Determining the optimal number of clusters ($k$) remains a fundamental challenge in unsupervised learning. While clustering algorithms like $k$-means or spectral clustering are highly effective at partitioning data, they typically require the user to specify $k$ a priori. In practice, practitioners often resort to the "elbow method"—identifying a kink in a cost curve—which is subjective, difficult to automate, and frequently ambiguous.

Existing statistical alternatives often impose restrictive assumptions, such as requiring the data to follow a Gaussian distribution. These assumptions fail when dealing with complex, non-convex data shapes like interlocking rings or manifolds. Furthermore, many methods struggle with the "null case": identifying when a dataset contains no inherent clusters at all (i.e., $k=1$). This paper introduces SpecialK, a nonparametric approach that leverages concentration inequalities to infer $k$ without distributional assumptions.

The SpecialK Methodology

The core of SpecialK is a statistical test designed to determine if a split in the data is justified or if it is merely an artifact of overfitting to noise. The algorithm operates through a combination of spectral embedding and a novel statistical bound.

The ZZ Top Bound

The authors derive a new statistical tool termed the ZZ Top Bound (referencing the product matrix $ZZ^\top$). Derived from the Matrix Bernstein concentration inequality, this bound allows the algorithm to calculate the probability that two separate clusters actually originated from the same "unified" distribution. Because the bound relies only on the sample mean and variance, it is entirely nonparametric and does not require the data to be Gaussian.

Algorithm Workflow

  1. Spectral Embedding: The process begins by decomposing a similarity matrix into a lower-dimensional space using a method called SpectACl. This allows the algorithm to handle non-convex shapes.
  2. Iterative Splitting: The algorithm executes $k$-means for an increasing number of clusters ($k = 1, 2, 3, \dots$).
  3. The Merge Test: For every pair of clusters identified at level $k$, SpecialK uses the ZZ Top Bound to evaluate the likelihood that these groups should be merged.
  4. Stopping Criterion: If the calculated probability exceeds a user-defined significance level ($\alpha$), the algorithm concludes that the current $k$ is over-splitting the data. It halts and returns the previous model ($k-1$).

Experimental Evaluation

The researchers evaluated SpecialK against state-of-the-art competitors, including STSC and PGMeans, across a variety of synthetic and real-world scenarios.

Synthetic Benchmarks and the "Sea of Noise"

On classic synthetic datasets like "Two Moons" and "Two Circles," SpecialK correctly identified the cluster count even as noise levels increased. A significant finding was the "Sea of Noise" test—a dataset of pure random points. While most popular algorithms insist on finding structure in noise (returning $k > 1$), SpecialK was the only method tested that correctly identified $k=1$.

Real-World Applications

  • MNIST Digit Recognition: When applied to the MNIST dataset (70,000 handwritten digits), SpecialK often selected $k=2$ or $k=6$ rather than the 10 human-assigned labels. The authors argue this reflects "natural groupings"—for instance, grouping bulbous digits like 0, 6, 8, and 9 together—demonstrating that the algorithm finds structural similarity rather than just replicating labels.
  • Scientific Datasets: In the Pulsar and Sloan astronomical datasets, SpecialK successfully distinguished between distinct celestial objects and background noise, showcasing its utility in high-stakes scientific discovery.

Key Insights and Results

  • Non-Convex Flexibility: By integrating the ZZ Top Bound with spectral clustering, the method provides statistical rigor to complex shapes that standard $k$-means cannot resolve.
  • Stability: The algorithm exhibits a "watershed moment" in its probability calculations. For the "correct" $k$, $p$-values are extremely low (e.g., $10^{-23}$); as soon as $k$ exceeds the true number of clusters, the $p$-value jumps to 1.0, providing a very stable stopping signal.
  • Distribution Independence: Unlike methods that assume Gaussianity, SpecialK remains robust across diverse data distributions, making it a versatile "wrapper" for various clustering objectives.

Limitations and Future Work

While SpecialK removes the need to manually select $k$, it introduces a dependency on the number of eigenvectors ($n$) used for the spectral embedding. Although the algorithm is relatively robust to this choice, it remains a parameter for the user to consider. Additionally, the iterative nature of the algorithm (repeated $k$-means and eigendecompositions) may pose computational challenges for massive, high-dimensional datasets. Future research may explore "soft" stopping procedures that analyze the overall trend of $p$-values rather than a binary threshold, potentially further increasing the algorithm's nuance in complex data landscapes.

Summary updated

Abstract

Most convex and nonconvex clustering algorithms come with one crucial parameter: the $k$ in $k$-means. To this day, there is not one generally accepted way to accurately determine this parameter. Popular methods are simple yet theoretically unfounded, such as searching for an elbow in the curve of a given cost measure. In contrast, statistically founded methods often make strict assumptions over the data distribution or come with their own optimization scheme for the clustering objective. This limits either the set of applicable datasets or clustering algorithms. In this paper, we strive to determine the number of clusters by answering a simple question: given two clusters, is it likely that they jointly stem from a single distribution? To this end, we propose a bound on the probability that two clusters originate from the distribution of the unified cluster, specified only by the sample mean and variance. Our method is applicable as a simple wrapper to the result of any clustering method minimizing the objective of $k$-means, which includes Gaussian mixtures and Spectral Clustering. We focus in our experimental evaluation on an application for nonconvex clustering and demonstrate the suitability of our theoretical results. Our \textsc{SpecialK} clustering algorithm automatically determines the appropriate value for $k$, without requiring any data transformation or projection, and without assumptions on the data distribution. Additionally, it is capable to decide that the data consists of only a single cluster, which many existing algorithms cannot.
BibTeX
@inproceedings{hess2019k,
  author = {Sibylle Hess and Wouter Duivesteijn},
  title = {{k is the Magic Number - Inferring the Number of Clusters Through Nonparametric Concentration Inequalities}},
  booktitle = {ECML/PKDD},
  year = {2019},
  url = {https://openreview.net/forum?id=fXfv8mERbAx},
}
Figure