On the Persistence of Clustering Solutions and True Number of Clusters in a Dataset

Amber Srivastava, Mayank Baranwal, Srinivasa M. SalapakaAAAI 2019 · DOI

Introduction

Determining the optimal number of clusters, $k$, remains one of the most fundamental challenges in unsupervised learning. While algorithms like $k$-means and Expectation-Maximization (EM) are widely used, they typically require $k$ as an input parameter. In exploratory data analysis, where the underlying structure is unknown, practitioners often rely on heuristics like the Gap Statistic or X-means. However, these methods frequently struggle with high-dimensional data, overlapping clusters, or non-Gaussian distributions.

This paper presents a novel framework based on the concept of persistence. By viewing clustering through the lens of statistical physics, the authors define the "true" number of clusters as the solution that remains stable over the widest range of resolution scales.

The Persistence Framework

The core innovation lies in treating the resolution of a clustering solution as a continuous parameter, $\beta$. This approach is inspired by Deterministic Annealing (DA). At low resolution (low $\beta$), the entire dataset is perceived as a single, blurry mass. As $\beta$ increases—analogous to sharpening a lens—the data begins to resolve into distinct groups.

The persistence of clustering solutions across different scales of resolution. Panels (a1-a3) and (b1-b3) illustrate how clusters bifurcate as the resolution parameter $\beta$ increases, creating stable plateaus for specific values of $k$.

Persistence, denoted as $v(k)$, is defined as the "lifespan" of a $k$-cluster solution in the log-resolution space: $$v(k) = \log \beta_k - \log \beta_{k-1}$$ where $\beta_k$ is the critical value at which the $k$-th cluster splits into $k+1$. A high $v(k)$ indicates a robust clustering solution that is not merely an artifact of a specific scale.

Mathematical Foundation: Phase Transitions and Covariance

The authors demonstrate that the emergence of a new cluster corresponds to a phase transition in the system's "free energy." Mathematically, this transition occurs when the Hessian of the cost function becomes singular. Crucially, they show that for Gaussian-like clusters, this split is triggered when the resolution $\beta$ reaches a value inversely proportional to the maximum eigenvalue of the cluster's covariance matrix. This means that compact clusters (low variance) are more persistent than spread-out ones.

Importantly, while the theory is rooted in DA, the persistence metric can be applied as a "wrapper" to evaluate the output of any hard-clustering algorithm, such as standard $k$-means, making it highly versatile.

Experimental Results and Performance

The proposed method was evaluated against 14 benchmark datasets, including synthetic challenges and real-world data like the Wisconsin Breast Cancer and Banknote Authentication sets. The persistence method correctly identified the true $k$ in 13 out of 14 cases, significantly outperforming the Gap Statistic and Information-Theoretic approaches.

Performance of the persistence metric $v(k)$ across diverse synthetic datasets. The peaks in $v(k)$ correctly identify the number of clusters in overlapping Gaussians (a), non-spherical shapes (c, d), and complex topologies like concentric rings (e) and spirals (f).

Handling Overlap and Complex Shapes

One of the method's primary strengths is its robustness to cluster overlap. In high-variance Gaussian tests where clusters merged visually, persistence correctly identified $k=4$, whereas traditional methods often collapsed to $k=1$. Furthermore, by employing a kernel-based extension, the framework successfully identified natural groupings in non-linearly separable data, such as concentric rings and spirals—scenarios where variance-based methods typically fail.

Discussion and Limitations

Despite its robustness, the method is not infallible. It failed on the Iris dataset, predicting two clusters instead of three. This is attributed to the extreme overlap between the Versicolor and Virginica classes, which share nearly identical covariance structures at common resolutions. Additionally, as a wrapper method, its accuracy is partially dependent on the quality of the initial clustering solutions provided to it.

Conclusion

The persistence metric offers a principled, scale-aware approach to the model selection problem in clustering. By identifying solutions that are stable across resolutions, it provides a more reliable indicator of "true" data structure than methods based on fixed-scale assumptions. Future work may involve integrating this metric directly into hierarchical clustering algorithms to automate branch pruning based on cluster stability.

Summary updated

BibTeX
@inproceedings{srivastava2019persistence,
  author = {Amber Srivastava and Mayank Baranwal and Srinivasa M. Salapaka},
  title = {{On the Persistence of Clustering Solutions and True Number of Clusters in a Dataset}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33015000},
}
Figure