DISCO: Internal Evaluation of Density-Based Clustering

Anna Beer, Lena Krieger, Pascal Weber, Martin Ritzert, Ira Assent, Claudia Plant

Introduction

In unsupervised machine learning, evaluating the quality of clustering results is a fundamental challenge. Without ground-truth labels, researchers rely on internal Cluster Validation Indices (CVIs) to tune hyperparameters and assess model performance. However, traditional CVIs like the Silhouette Coefficient (SC) are often ill-suited for density-based clustering. They typically assume clusters are compact and spherical, leading to poor scores for the complex, non-convex shapes (like rings or spirals) that algorithms like DBSCAN are designed to find. Furthermore, most existing metrics fail to account for noise—a key feature of density-based methods—either ignoring outliers or penalizing their presence indiscriminately.

The DISCO Framework

This paper introduces DISCO (Density-based Internal Score for Clusterings with nOise), a deterministic CVI designed to address these limitations. DISCO innovates in two primary ways:

  1. Density-Connectivity Distance (dc-dist): Rather than using Euclidean distance, DISCO employs a "minimax path" approach. This measures distance through high-density regions, allowing the metric to correctly identify points as "close" if they are part of the same continuous, winding structure.
  2. Explicit Noise Scoring: DISCO evaluates whether a point assigned as noise actually belongs there. It calculates a score based on sparseness (is the point in a low-density area?) and distance (is it far from dense clusters?). This prevents the metric from biasing against algorithms that correctly identify outliers.

The Flaw in DBCV

The current state-of-the-art for density-based evaluation, Density-Based Clustering Validation (DBCV), was found to have a significant reproducibility flaw. The authors demonstrate that DBCV is non-deterministic; because it relies on non-unique Minimum Spanning Trees, shuffling the input data can result in different scores for the exact same clustering.

DBCV score distributions for identical clusterings.

As shown in the figure above, the distribution of DBCV scores for the same dataset can vary widely, making it an unreliable tool for precise hyperparameter tuning.

Performance and Interpretability

DISCO provides a score between -1 and 1 for every point, which can be averaged for a global assessment or visualized to identify specific areas of clustering failure. In comparative tests, DISCO showed high correlation with external ground-truth metrics (e.g., 96.87% Pearson correlation on high-dimensional synthetic data) and outperformed competitors in identifying optimal DBSCAN parameters.

Comparison of DISCO with SC and DBCV on various clustering results.

The figure above illustrates DISCO's effectiveness. In scenario (a), where clusters are concentric rings, the Silhouette Coefficient (SC) fails due to the non-spherical shapes, while DISCO correctly identifies a high-quality clustering. In scenario (b), where clusters are incorrectly split, DISCO's score drops appropriately, whereas SC might still report a relatively high value.

Conclusion

DISCO offers a robust, deterministic alternative for evaluating density-based clustering. By incorporating density-connectivity and a nuanced treatment of noise, it provides researchers with a more accurate and interpretable tool for unsupervised model validation. Future work will look into optimizing its $O(n^2)$ computational complexity for massive datasets and exploring more complex local noise distributions.

Summary updated

BibTeX
@inproceedings{beer2026disco,
  author = {Anna Beer and Lena Krieger and Pascal Weber and Martin Ritzert and Ira Assent and Claudia Plant},
  title = {{DISCO: Internal Evaluation of Density-Based Clustering}},
  booktitle = {International Conference on Learning Representations},
  year = {2026},
  url = {https://openreview.net/forum?id=izbBFuHtAX},
}
Figure