Internal Evaluation of Density-Based Clusterings with Noise
Authors: Anna Beer
Lena Krieger
Pascal Weber
Martin Ritzert
Ira Assent
Claudia Plant
Venue: ICLR 2026 Poster (2026)
Keywords: Evaluation
Clustering
Unsupervised Learning
Primary area: datasets and benchmarks
TL;DR: We introduce the first internal evaluation measure that actively evaluates the quality of noise labels and density-based clustering results.

Abstract: Evaluating the quality of a clustering result without access to ground truth labels is fundamental for research in data mining.
However, most cluster validation indices (CVIs) do not consider the noise assignments by density-based clustering methods like DBSCAN or HDBSCAN, even though the ability to correctly determine noise is paramount to successful clustering. 
In this paper, we propose DISCO, a **D**ensity-based **I**nternal **S**core for **C**lusterings with n**O**ise, the first CVI to explicitly assess the *quality* of noise assignments rather than merely counting them.
DISCO is based on the Silhouette Coefficient, but adopts density-connectivity to evaluate clusters of arbitrary shapes, and proposes explicit noise evaluation: it rewards correctly assigned noise labels and penalizes noise labels where a cluster label would have been more appropriate.
The pointwise definition of DISCO allows for the seamless integration of noise evaluation into the final clustering evaluation, while also enabling explainable evaluations of the clustered data.
In contrast to most state-of-the-art methods, DISCO is well-defined and also covers edge cases that regularly appear as output from clustering algorithms, such as singleton clusters or a single cluster plus noise.

Internal Evaluation of Density- Density-Based Clusterings with Noise
INTERNAL EVALUATION OF DENSITY-BASED CLUSTERINGS WITH NOISE
Anna Beer" .1.111,, Lena Krieger* Pascal Weber 1,2,3 Martín Ritzert..9,
Ira Assent 1.7, Claudia Plant 1.3
1 Faculty of Computer Science, University of Vienna, Vienna, Austria
2 UniVie Doctoral School Computer Science, University of Vienna, Vienna, Austria
Data Science @ Uni Vienna, University of Vienna, Vienna, Austria
4 IAS-8: Data Analytics and Machine Learning. Forschungszentrram Jüilich Jülich, Germany
5 Institute for Computer Science, LMU Munich, Munich, Germany
6 Munich Center for Machine Learning, Munich, Germany
7 Department of Computer Science, Aarhus University, Aarhus, Denmark
8 Institute of Computer Science and Campus Institute Data Science, University of Göttingen, Göttingen, Germany
9 Center for Scalable Data Analyties and Artificial Intelligence (ScaDS.AA) Dresden/Leeppte Leipzig University, Leipzig, Germany Webster Vienna Private University, Vienna, Austria
Contact: weteeerreeeeteraaa...... (.r.rsseerr.aa.tiiieeeeeefffe Lerieger@@f-jjueiiccc.. pascal. weweraawwbeeruuvve..c..m
ABSTRACT
Being able to evaluate the quality of a clustering result even in the absence of ground truth cluster labels is fundamental for research in data mining. However, most cluster validation indices (CVIs) do not capture noise assignments by density- based clustering methods like DBSCAN HDBSCAN, even though the ability to correctly determine noise is crucial for a successful clustering. In this paper, we propose DISCO, Density-based /nternal Score for Clusterings with nOise, the first CVI to explicitly assess the quality of noise assignments rather than merely counting them. DISCO is based on the established idea of the Silhouette Coefficient, but adopts coaiitt-coneetivityy to evaluate clusters of arbitrary shapes, and proposes explicit noise evaluation: rewards correctly assigned noise labels and penalizes noise labels where a cluster label would have been more appropriate. The pointwise definition of DISCO allows for the seamless integration of noise evaluation into the final clustering evaluation, while also enabling explainable evaluations of the clustered data. contrast to most state-of-the-art methods, DISCO is well-defined and also covers edge cases that regularly appear output from clustering algorithms, such as singleton clusters or a single cluster plus noise.
INTRODUCTION
Density-based clustering is fundamental concept known from methods like DBSCAN (Ester et al., 1996) or HDBSCAN (Campello et al., 2013) and serves as the basis of recent solutions, e.g., for fair clustering (Krieger et al., 2025) or deep clustering (Beer et al., 2024). However, evaluating the quality of density-based clusterings still faces open challenges, especially regarding noise assignments. Density-based clusters are regions of high object density that are separated by regions of lower object density. Points that do not lie in cluster are labeled as noise. Unlike in centroid- based clustering, density-based clusters may have arbitrary shapes, and not all points need be assigned a cluster. For example, in Figure la, each ring is one density-based cluster separated from other clusters by low-density regions that contain noise points.
AAtthors contributed equally to this work and are ordered alphabetically. Work done while University of Vienna

---

Internal Evaluation of Density-Bass Based Clusterings with Noise
(a) DISCO: 0.02.
(b) DISCO -0.01, SC: 0.38, DBCV: 0.90
(c) DISCO: U.50. 0.08, DBCV: 0.46
(d) DISCO: U. DBC.:
SC: 0.15. DBCV 0.77
Figure I: Ring-shaped ground truth clusters (color-coded) with noise (gray +). Top: The density- based CVIs DISCO and DBCV rate the ground truth ring clustering in (a) higher than the k-Means clustering cutting across rings in (b), while the Silhouette Coefficient (SC) prefers the latter. Bottom: DISCO scores the "clean" clustering in (c) higher than the version where some noise points are added to the ring-shaped clusters (d). DBCV only evaluates the amount of noise, and, thus, prefers the latter.
Internal cluster validity indices (CVIs) provide quality score for clustering without known ground truth (Zaki et al., 2020). By comparing the quality of different clusterings, CVIs are essential for selecting suitable clustering algorithms and their hyperparameter settings. Typically, CVIs balance the compactness of clusters and their separation, e.g., in Davies-Bouldie (Davies & Bouldin, 1979), Dunn index (Dunn, 1974), or Silhouette Coefficient (Rousseeuw, 1987).
Inherently, most CVIs assume compact clusters and are, thus, not suitable to evaluate the quality of arbitrarily-shappe clusters like the three rings in Figure 1a. The Silhouette Coefficient (SC) of the perfect clustering is -0.15, which incorrectly indicates poor clustering. In contrast, the unintuitive k-Means clustering in Figure lb, where clusters are cut into pieces like a pie chart, and the rings are disconnected, is incorrectly scored with much higher value of 0.38 by the SC. Supporting arbitrarily-shaper clusters, the most prominent method, DBCV (Moulavi et al., 2014), correctly prefers the perfect clustering.
One key advantage of density- clustering is its ability to identify and label noise points. However, such noise labels are not evaluated by most current CVIs, which ignore them altogether. To the best of our knowledge, DBCV (Moulavi et al., 2014) is the only CVI that is properly defined for clusterings with noise labels. However, it does not evaluate their quality, but simply reduces the total score by the fraction of noise- - even for correctly identified noise points. Thus, DBCV rates the worse clustering in Figure l with a score of 0.63 as better than the perfect clustering in Figure Ic. which only yields a DBCV score of 0.46. Note that CVIs that are not designed to handle or evaluate noise labels may exhibit unintended and unintuitive biases when selecting the optimal clustering.
To overcome these limitations, we introduce DISCO, a Density-based Internal Evaluation Score for Clusterings with nOise. DISCO is the only CVI that correctly scores the clusterings in Figure consistently preferring the optimal clusterings over worse ones by evaluating the quality of noise labels based on their local object density. For cluster points, DISCO redefines the intuitive Silhouette In contrast to existing CVIs, DISCO is well-defined with
Coefficient based on a bounded value range from -1 to for any possible labeling, which may not only include noise labels but also singleton clusters and one-cluster clusterings. Our suggested internal cluster evaluation measure for density-base based clusterings, DISCO, has the following properties:
It is the first internal CVI to evaluate the quality of noise labels, an essential feature of density-based clustering.
For both noise points and clustered points, DISCO adopts the principle of density- connectivity, which allows for assessing the quality of density-based clusterings correctly.
Building on the concepts of compactness and separation, DISCO assesses clustering quality with an intuitive pointwise score, thereby enhancing interpretability.
2
RELATED WORK
Internal CVIs evaluate clustering quality without the need for ground truth labels by comparing the compactness of clusters with the separation between clusters (Zaki et al., 2020). This concept is employed in classical methods like Davies-Bouldin (Davies & Bouldin, 1979), Dunn index (Dunn,
2

---

Internal Evaluation of Density-Bass Based Clusterings with Noise
1974), Silhouette Coefficient (Rousseeuw, 1987), S_Dbw (Halkidi & Vazirgiannis, 2001), which work well for sentroid-basee clustering. However, these measures assume that clusters are ball-shaped, making them problematic for rrbitrarily-shaper clusters. While they can be combined with other distance measures like minmax-pat distance, e.g., in MMJ-SC (Liu, 2023), to capture non-spherical clusters, their definitions do not consider noise assignments.
Compactness and separation can be evaluated either at the cluster or point level. Among the clusterwise CVIs, CDbw (Halkidi & Vazirgiannis, 2008) and CVNN (Liu et al., 2013) extend centroid-based CVIs with multiple representation points to handle more complex shapes. As a downside, their scores depend on the number and choice of these representation points. CVDD (Hu Zhong, 2019) uses local density when computing the distance between clusters, allowing it to assess cluster separation without being misled by outliers. For CVDD and CVNN, the resulting scores are not bounded, making it difficult to assess how good a clustering really is, expecially as, in practice, the output spans several orders of magnitude.
In contrast, DBCV (Moulavi et al., 2014) and DCSI (Gauss et al., 2024) score compactness and sepa- ration as the longest edge within and the minimum distance between clusterwise minimal spanning trees (MSTs) under the pairwise mutual reachability distance. Neither DBCV nor DCSI considers all points to avoid outliers: DBCV builds one MST on all points of each cluster and then removes all leaves, while DCSI builds the MSTs only on core points. Importantly, as MSTs are not unique, removing all leaves may result in quite different sets of points remaining in DBCV's 's computations. Thus, DBCV outputs different scores for the exact same clustering, making it unsuitable metrie; we discuss this at the end of this section and in Section B.
LCCV (Cheng et al., 2018) and VIASCKDE (Senol, 2022) aggregate pointwise scores to capture con- nectedness and separation. LCCV builds on points with local maximum density, while VIASCKDE employs Kernel Density Estimation to assign higher weights to scores from points in regions of higher density. Another step in the direction of density-based clustering evaluation is the work by Schlake& & Beecks (2024). They suggest using the density-connective distance (de-dist) (Beer et al., 2023) that captures the essence of connsstycconecciittt-ieee based clustering algorithms like DBSCAN with various classic internal evaluation measures.
While all these methods use some notion of density for evaluating clusterings, they share a significant drawback: In most cases, noise points are not even mentioned their paper, with DBCV being the only exception. DBCV filters noise points and scales the final score with the fraction of non-noise points, a technique that could be applied in any CVI. Implicitly, LCCV and CVNN include noise points when comparing against "all other" points. Although it is not discussed in the respective papers that this might include noise points, the scores can behave desirably even for clusterings including noise labels. All of these approaches penalize the existence of noise rather than evaluating the quality of woise-labeled points, i.e., whether the noise label is desired or not (cf Section A.2). We summarize key properties of these methods in Table 1.
Table I: Features of internal evaluation measures.
arbitrary shupes
evaluates
Datsset 1: comp exi
Dastaset complexs
Method
noise
hounded deterninistic 1/
Silhouctee
Count
80
S Dbw
DRCV DCSI
X
+0.3
+0.2
0.1
DBCV
MM SC
LCCV
VIASCKDE
Figure 2: DBCV scores for ground truth cluster- ing of complex8 (complex9) in green (blue) over 1000 runs: Scores not deterministic and spread around a mean (black dashed line) for a shuffled processing order of data points.
CVDD
X
CDb
X
CVNN
DISCO (ours)
yes
X no
no, but affected by noise
Limitations of DBCV The currently used state-of-the-art internal CVI for density-based clusterings is DBCV (Moulavi et al., 2014). However, DBCV is inherently non-deterministic as excludes points at the leaf level of the cluster-wise MST from its calculations. Since these points are not uniquely determined for given dataset and clustering, DBCV scores are non-deterministic, as also shown experimentally in Figure 2. As DBCV's non-determinism has not been discussed in literature yet,
3

---

Internal Evaluation of Density-Bass Based Clusterings with Noise
give more background this novel and crucial finding in Section B. Note that consequence, clustering results cannot be compared with each other using DBCV in a reproducible way, prohibiting scientific assessment of the clustering quality. E.g., on the ground truth clusterings of the benchmark dataset complex8, DBCV yielded scores between - -0.3 and 0.1 for the exact same assignment of points clusters (see Figure 2). This non-determinism is not discussed in Moulavi al. (2014) and can lead to an overoptimistic evaluation (Ullmann et al., 2023). While the effect could be diminished, e.g., by taking the mean of several runs, users would need know about the problem, and such mitigation is not part of the standard implementations.
DISCO: INTERNAL EVALUATION OF CLUSTERINGS WITH NOISE
Preliminaries DISCO evaluates a given crnsity-baseed clustering V on dataset X E R with n m-diimensioaal points. A clustering & is set of clusters C₁: E {CI, C2...., Ck} with n,Cc = 0 for all i * j. An advantage of density-bat bbased clustering methods is that not every point needs to be assigned
cluster: There may be noise points N X U, C. For x E X, we use
shorthand Ć₂ when referring to cluster C2 such that x E C.-
Internal evaluation metrics assess compactness and separation evaluate given clusterings. Since we focus on density-based clusterings, we base our concepts on notions introduced in density-based clustering approaches like DBSCAN (Ester al., 1996), or more recently HDBSCAN (Campello et al., 2013). 3). Density-basee clusters are defined using core points and vensity-connectivv points are points with more than μ neighbors within an e-distance (their neighborhood), which makes these areas dense. The core-distance <(x²)= = deuet (w))) captures the density of the area around a point x as the Fuclidean distance to its fu-th nearest neighbor ((2)- A lower core-distance, thus, implies higher object-density around x. Two points are density-connected if there is path of core points connecting both such that the maximum distance between successive core points at most e. Density-based clusters are maximal sets of density coneeetdd core points, i.e., they form a connected component in graph with the core points as nodes and edges that connect any pair of points with a Euclidean distance smaller than
Core
To assess density-comee consity-commettivityy in a clustering, DISCO uses the density- distance (dc-dist) (1:, y) (Beer al., 2023). It is the minimax path (i.e., the path with the smallest maximum step size) distance between two points I, E X in the graph given by all pairwise mutual reachability distances dm (I,, y) max (r((z), k(V), (2, v)) (Ankerst al., 1999):
dde( v) = max lel if Ae else 0
(1)
eEp(z.g)
where le| is the weight of any edge e (given by dm,) on the path p(a, y) that connects points æ and in the minimum spanning tree (MST) over this graph. Note that, in contrast to Euclidean distance, dde not only depends on the feature values of points x and y. but rather on how they are connected in the dataset X: The minimax path may meander through the dataset reach the target using only small steps, effectively focusing on dense regions.
3.1 DEFINITION OF DISCO
To allow the assessment of individual cluster assignments and support interpretability, define DISCO pointwise, giving score p(x) to each point æ. The score for the entire dataset X is then the average over all points' scores:
DISCO:
p(X) = avg p(z).
DISCO treats cluster points and noise points differently, we detail in the following subsections:
p(x)= = Peluster (x) Pnoise (I)
i E C; for any E [l....,k] if N
(3)
where Petuster and Prenise are the pointwise DISCO scores for cluster and noise points, which we later define in Equations (4) and (7).
4

---

Internal Evaluation of Density-Bass Based Clusterings with Noise
Cluster Points: Peluster (z). When z X is assigned to cluster Cz, we compute Petuzer by comparing average distances within the cluster (compactness) with those to the closest other cluster (separation). Importantly, these assessments employ the dc-dist dde to account for density-based clustering notions using dde (x, C:) = aygyE dac(x.y):
Jaclar Ci) ddc( C,7O2 max(dae( Ci), ddc( Cz))
Peluster (2) min
In Equation (4), we compare the average distance from to points in its own cluster C₂ and the "closest" other cluster. Here, shape and density of ÖN and the "gap" to the next cluster are much more important than, e.g., the Euclidean distance to the closest point of each cluster (see also Figure 7).
Paoise (.,). One of the key advantages of density- based clustering methods their ability to detect and label noise explicitly, in contrast to clustering algorithms like k-Means or Gaussian mixtures that assume clean data without global noise. In this paper, we focus on a commonly used basic noise model: additional noise points in the data that do not belong any cluster. Those noise points usually stem from different source than the points within clusters, thus, they follow a different distribution. In order to properly evaluate the quality of ceensity-basee clustering. internal CVIs must quantify the quality of noise and cluster labels. Note that neither ignoring noise points in the score nor interpreting them as a separate cluster (as is commonly done in standard implementations) yields accurate evaluations. Excluding noise points from the evaluation can result in overly favorable scores for excessive noise labeling, while treating them as a cluster penalizes the poor compactness associated with correctly labeled noise.
Noise Points:
In contrast to other methods, DISCO actively evaluates the quality of given noise labels. we follow the notion of noise points in density-basch -based clustering (Ester al., 1996; Campello et al., 2013). There, noise points are points that are neither core points nor density-connected to any cluster. Thus, a noise point is (a) in low-density area (otherwise, the point would be core point and would start its own cluster) and (b), is far away from any existing cluster (otherwise, would be part of such a nearby cluster). We capture both properties in our score.
so,
(a) Noise points are not core points Noise points' dore-distances are larger than some E. If noise point Fn is in a low-density area, measured by comparing its core-distance to the maximum core-distance of point within cluster, then it should be considered noise. We capture this by
Psparse (1)) = min k(εn) - x(C.)
(5)
C.e% max max(K(z,)) x(C,))
where the core-distance threshold of a cluster is the maximum core-distance of any point in C: x(C) max k(x). It corresponds to the smallest e such that the entire cluster remains density- connected. By choosing the minimum over all clusters in Equation (5) instead of just comparing to the core-distance of the closest cluster, we account for clusters of varying density. This global interpretation of sparsity ensures that a group of noise points with the same density as a cluster (somewhere else) is not rated as well-labeled noise.
(b) Noise points are not density-connecter to any cluster. We assess this by comparing the dc-dist between the noise point and each cluster with the maximum core-distance in that cluster. If the de-dist between the point and the cluster is smaller than or equal to the maximum core-distance of the cluster, then it is density-connecter to said cluster and should thus be part of it (see also Figure 8). Formally, for a noise point Fa we compute a score for not being density-connecter as
Pfar (xa) = min mingec, dac(Fn. v) x((C.) C max(mingeec ddc(Fa. (Ca))
(6)
As noise should be neither in a dense region nor density-connected to an existing cluster, is scored as the minimum of these two:
Pnoiso (F min (Prparie (#n), (fr((
5

---

Internal Evaluation of Density-Bass Based Clusterings with Noise
Edge Cases We handle edge cases follows: For the extreme case of clusterings with only noise points and no clusters, we define (noise(Zn) = -1 as they have no clustering value.
Singleton clusters consist of only one point, contradicting the idea of grouping together similar points. Thus, for all points x in singleton clusters, we set Petuster ) = 0. Similarly, the clustering consists of one cluster and no noise points, we let Peluster( 0 for all E X.
there are, in addition to the only cluster C1 also noise points, we evaluate C1 w.r.t. the closest noise points instead of the (non-existent) closest cluster:
mino,, dao(I, - daola, Oz)
Peluster max (ming, EN (I, In), ddo(2, Cz))
(8)
Note that no other iV defined for clusterings with less than two clusters, even though density-based methods like DBSCAN (Ester al., 1996) or HDBSCAN (Campello al., 2013) and synchroniza- tion-based clustering methods (Böhm et al., 2010) may return such clusterings.
commonly overlooked edge case occurs when datasets have more than μ duplicate points, making their core-distances O. This can lead to zero denominators in, e.g., Eq. 5. However, as these points are always core points and, thus, "bad" noise, we simply set the fraction (and, thus, Psparse) to 0.
3.2 DISCUSSION
+1.0
40.5
00.0
-05
Figure 3: Pointwise DISCO scores for cluto-t8-8k based on the ground truth clustering (left) and k-Means clustering (right). Lines indicate k-Means cluster borders. DISCO assigns high scores to well-separated clusters and most noise points, and low scores to (disconnected) k-Means clusters.
DISCO effectively assesses compactness and separation in the density-connectivity sense, following the structure of well-established CVIs. DISCO is deterministic and produces scores that are bounded between -1 and 1. By computing scores at the individual point level, it naturally enables evaluating the quality of any point's 'ss label cluster label or noise label. DISCO is also widely applicable: being based on density-connecttiityy it is suitable not only for numeric data but also for any data type, given the pairwise similarities. It covers all edge cases that might be produced by various cluster algorithms (e.g.. clusterings with only one cluster or datasets with duplicate points). Figure showcases several of those benefits on a 2d toy dataset with two different labelings: density-based ground truth clustering (left) and k-Means clustering (right). The colors indicate the pointwise DISCO scores, which are high (blue) for most points on the left. Only one cluster in the middle right has mediocre (light brown) scores, as is the least dense cluster and relatively close to the next cluster. contrast, the k- k-Means clustering yields only low (orange) or mediocre (light brownish) DISCO scores for almost all points as density-separater clusters are merged and density clusters are split apart.
With an overall complexity of (n²), DISCO yields in practice comparable runtimes to most density- based competitors. While some CVIs (LCCV, CVDD, and CDbw) are much slower than DISCO, centroid-based methods are usually faster.
4 EXPERIMENTS
In the following, compare centroid-basee and density-basee evaluation (Section 4.1) and showcase noise handling (Section 4.2). We investigate typical use cases (Section 4.3), compare to external evaluation results (Section 4.4), and finally show DISCO's behavior in systematic ablation studies

---

Internal Evaluation of Density-Bass Based Clusterings with Noise
(Sections 4.5 and 4.6). We compare to the introduced CVIs that can also handle arbitrarily-happd clusters, and the classical approaches SC and S_Dbw. which have been shown to be useful in many scenarios (Liu al., 2010). Details on the setup and implementation can be found in Section C. Our code is available online: ht https:
com/pas weber/DISCO
4.1 DENSITY-BASED VS. CONTROID-BASER CLUSTER NOTION
Density-based based CVIs should provide better scores for correct, density- based clusterings than for unintuitive, centroid-based clusterings (that might be more compact). Thus, in Table 2, we regard two different labelings of the density-basee toy datasets 3-spiral and complex9: first, the density-based ground truth labels, and second, k--eans clustering. We compute the CVIs described in Section 2 and mark them in green if they indeed yield better scores for the density-based clustering than for the centroid- centroid-based clustering. Most of the CVIs discussed in Section 2 for the density-based -baeed notion indeed prefer (i.e., evaluate better) the density-based clustering. However, CVNN does not, VIASCKDE evaluates both labelings as similarly good, and CDbw only makes difference for complex9, but not for 3-spiral. As expected, Silhouette and S Dbw prefer the k-Means clustering (orange in Table 2).
4.2 EVALUATING NOISE LABELS IS IMPORTANT
To the best of our knowledge, no internal CVI evaluates noise labels explicitly. While most of our competitors do not define how noise should be handled at all, some unintended side effects may appear when applying the methods nevertheless: points labeled as noise are treated as their own cluster many singleton clusters. DBCV applies penalty proportional the amount of noise labels. This handling of noise or the lack thereof can yield undesirable results, as shown in Table 3.
Table 2: A daase CVI should evalu- ate the DBSCAN clustering equaling the ground truth (left) better than the k-Means clusterings (right). The color indicates the CVIs align with these expectations not. + denotes that lower scores imply better clustering.
Table 3: CVIs for different clustering qualities. The color indicates if the CVIs align with the ex- pectations not." indicates the CVI does not han- dle noise; the implementation treats noise-labeled points cluster by default. indicates noise filtering. + denotes that lower is better.
CVI
CVT
3-spiral DBSCAN
3-spiral i-Means
complex9 DBSCAN
complex0 R-Means
Quality
optimal
very bad
optimal
suboptimal
DISCO
0.59
0.00
0.36
0.02
DISCO
0:30
-0.07
0.50
0.19
Silhouette
Silhouette*
0.07
S Dbw
2.79
1,90
0.59
0.19
S.Dbw 1
0.73
0.31
0.53
0.55
CVNN
5.49
3.63
5.11
4.79
CVNN
5.59
4.56
54.67
58.14
DBCV
0.55
DBCY
.0.05
0.17
0.46
0.63
DCSI
0.93
0.01
0.95
0.71
DCSI+
0.92
0.96
0.99
0.94
MMJ-SC
0.79
-0.01
0.44
0:03
MMJ-SC
LCCV
LCCY
0.11
0.26
0.18
0.40
VIASCKDE
0.31
0.26
0.63
0.60
VIASCKDE
_1
CVDD
180.35
0.58
689.4
25. 96
CVDD*
0.01
0.15
37.74
0.07
CDbw
CDb
0.1500
0.5616
0.0016
0.0014
Here, we examine how various CVIs evaluate a good and a bad clustering (with noise labels) on two datasets. Columns and two present the cluto-t8-8k dataset from Figure 3, with ground truth labeling in the first column. The second column shows a very bad labeling of this dataset, where each cluster on the left side is split into two clusters that are separated by points labeled as noise (gray). One of the clusters is completely mislabeled as noise. Columns three and four show the dataset from Figure with two circle-shaped clusters and uniform background noise. Here, we compare the ground truth clustering (column three) with slightly worse clustering, where some noise points have been mistakenly assigned to the clusters (column four). For each CVI, we compare the scores for the optimal and the non-optimal clustering, and mark cases where the optimal one is preferred in green. Notably, DISCO the only CVI to prefer both good clusterings over their suboptimal counterparts.
Note that VIASCKDE cannot be computed for the second dataset (columns 3 and 4) the density of the circular clusters too uniform, leading division by zero in the official implementation.
7

---

Internal Evaluation of Density- Density-Based Clusterings with Noise
4.3 DETERMINING BEST PARAMETER SETTINGS
A key application of CVIs is to determine good parameter settings for clustering methods that result in high-quality clustering. Especially for density-based methods, this remains a widely discussed challenge (Nir et al., 2025; Beer et al., 2025). Ideally, the highest internal CVI score across different parameter settings corresponds
the clustering that most similar to the ground truth. Thus, in Figure 4, compare the scores of internal CVIs for DBSCAN clusterings across range of e-values (leading to [2, 20] clusters) on the Synth_high dataset that has & 10 density conneeted and well-separated ground truth clusters. Optimally, the circles indicating the highest score should fit the highest ARI values at & = 10 (red bar). However, only DISCO and DBCV have the desired peak at ten clusters. Thus, if used to find the best parameter setting, other CVIs are misleading here, while DISCO and DBCV correctly guide users to the setting aligned with the ground truth. In Section D, we show the corresponding experiments for the very high-dimensional COIL20 dataset and the 3-spirals dataset from Table 2.
4.4 CONSENSUS OF INTERNAL AND EXTERNAL. CVIS
Idcally, internal CVIs should yield similar scores to external CVIs based the ground truth. In Table 4, we study this correspondence between internal CVIs and the (external) ARI values across several datasets and clusterings: We generate clusterings by diverse standard clustering algorithms for each dataset and add two random clusterings. We compute the Pearson Correlation Coefficient (PCC) between the respective CVIs and the ARI values for those clusterings. For the ARI calculation, points labeled as noise are treated as singleton clusters. Some of our competitors are not defined for the full range of clusterings, e.g., singleton clusters. Thus, they cannot be computed in some cases, marked with "_" in Table 4, see further Section 3.1. DISCO is the only CVI inherently designed to handle all edge cases, which typically occur when. e.g., DBSCAN's parameter is set high (only one cluster) or too low (no cluster). A reliable CVI should always return some result and, ideally, have a high PCC the ARI. Table shows that DISCO, MMJ-SC, and LCCV meet those criteria best. DBCV and DCSI come close if they return value; however, their scores contradict ARI on, e.g., htru2.
4.5 HYPERPARAMETER ROBUSTNESS
DISCO has one hyperparameter, μ. which is used for the computation of the de-dist. In Figure 5, we test DISCO's robustness by varying μ in the ranges [1,30] for real-world datasets including large and high-ding digeensiini datasets like COIL20 or Pendigits, and [1. 10] for 2d benchmark data that is commonly used for density-based methods, For most datasets, DISCO yields stable results. Only on
k
6
9
10 11
12
14
15
16
17
19
1.0
DISCO
0.8
DBCV
DCSI
MMJ-SC
LCCV
VIASCKDE
0.2
CVDD (n)
CDbw (n)
0.0
CVNN (r.n)
1.0
Silhouette
ARI
0.5
S_Dbw (r.n)
4.144
3.041
2.373
2.083
2.060
2.042
1.711
1.678
1.436
0.793
0.776
0.762
0.756
0.732
0.728
0.726
0.726
0.725
Figure 4: CVIs for DBSCAN clusterings with varying ε values on the noisy Synth high dataset
(k = 10, d = 100). Top: Resulting number of clusters k. Bottom: Corresponding ARI scores.
8

---

Internal Evaluation of Density-Bass Based Clusterings with Noise
Table 4: Pearson Correlation Coefficient (PCC) between internal CVI scores and ARI values. For each tested CVI (columns) and wide range of datasets (rows) we compute the PCC based on seven clusterings//abelingss the ground truth, DBSCAN, HDBSCAN, Ward, k-Means, and two random labelings. denotes that at least one clustering could not be evaluated by the respective CVI.
Dataset
DISCO
DBCV
DCSE
MMU-SC
LCCV
VIAS. 1
CVDD
CDbw
CVNN
Silh.
S 5.Dbw
three spiral
89.16
89.01
65.82
31.60
-2.43
42.38
aggregation
90.95
75.30
92.41
86.45
81.13
chainlink
92.78
99.71
72.27
92.49
90.07
51.84
98:07
76.93
-96.53
26.001
26.50
cluto-44-8k
44.43
77.58
93.82
62
76.12
57.02
18.37
-12.69
42.40
-53.84
cluto-12-10k
48. 66
88.86
61
32.42
50.38
11.47
39.42
13.44
53.19
cluto-t8-8k
91.35
71.41
88. 53
89:000
59 69.64
81.94
-1.53
-68.51
8.44
-68.10 10
complex8
95.71
48.
-59.19
complex9
56.35
59.63
78.28
61.20
16.16
68.58
19:25
66.13
- 46.81
-1.52
62.96
compound
$6.06
87.05
92.92
67.59
62.12
67.00
danboard1
96 83
99.78
08.88
96.74
89.11
64.33
99.95
- -03.99
-35.10
-20.07
-36.22
diamond9
98.
87.13
99.31
99:27
93.52
98,
67.20
13.71
-68.
96.84
-87.33
smilel
96.60
96.40
96.58
94.62
68.53
79.20
-93.58
Synth low
98.13
92. 45
96.61
79.11
13.89
87.70
-85,88
Symth high
96.87
96.30
72.72
hin22
37.40
41.94
26.74
35.07
55.80
00.50
58.43
37.98
73.44
24.05
Pendigits
40.31
10.64
56.23
80.72
79.03
50.52
10.41
-43.22
78.22
48.76
COIL.0 20
95.79
90.44
94.17
97.94
93.13
63.98
21.84
65.84
85.15
50.29
cmm. faces
62.00 02.08
71.43
64.39
78. 78.33
80.75
-2.84
-63.60
20146
-65.85
Optdigits
91.07
92.37
65.70
86.91
-70.67
the datasets "3-spiral" and "COIL20", DISCO values drop significantly for higher values for j.. This can be explained by the sparseness on the outer ends of the spirals (3-spiral) and sparse clusters within the dataset (COIL20). However, for both cases, our default of well. In Section D.3, we additionally analyze the effect of depending on the amount of existing noise, where observe robust results indicates that DISCO's performance is not sensitive to μu, allowing us to fix = in all experiments, consistent with minPts heuristics in Ester al. (1996); Schubert et al. (2017).
captures the connityconneettviity
range of jı-values. Robustness across benchmarks
4.6 ABLATION OF CLUSTERING SCORE Peluster
We perform an extensive sensitivity analysis of the clustering score Peiuseer across data variations (see Section D.6 for exact settings and Figure 20 for detailed diagrams). We test the influence of mislabeled cluster points, separation, and fuzzy cluster borders. DISCO adapts smoothly as the number mislabeled points increases from a perfect clustering, In contrast, DBCV, CVDD, CDbw, and DCSI exhibit abrupt drops, making them more susceptible to adversarial manipulation. For increasing separation between clusters, DISCO, DBCV, and DCSI increase sharply once the clusters become clearly distinet, indicating that they effectively capture density connectivity. As clusters become increasingly fuzzy and overlapping, most CVIs, including DISCO, behave as expected, starting with high scores that gradually decrease. In contrast, CVDD rates the clustering poorly even at low fuzziness levels, while LCCV shows a bias toward fuzziness around 5%.
3-spiral
cluto-17-10k
compound darlboard1
Synth_low Synth_hig high htru2 Pendigits
COIL20
aggregation
cluto-18-8K
faces Optigitss
chainlink
complex8
diamond9 smile1
cluto-4488k
complexe
DISCO scores
0.5
0.0
5
10
1
5
10
20
30
H
Figure 5: DISCO scores (y-axis) are robust against varying μ (x-axis) for the tested datasets (implied by color). Left: Datasets from the Derie benchmark. Right: Other real world datasets.

---

Internal Evaluation of Density-Basse Based Clusterings with Noise
4.7
ABLATION OF NOISE SCORE Phoise
As our competitors do not explicitly evaluate noise, we only present DISCO's behavior.
1.0
DISCO
score
0.0
Poluster
-0.5
Ppprrs
-1.0
Plar
100
200
300
2
% additional noise
distance to remote noise point
Figure 6: Left: Influence of Pspurse on one cluster and a distant group of points with increasing size and density, labeled as noise. Right: Influence of Pjar for a single noise-labeled point with increasing distance to the cluster.
Sparseness of noise (Pspurse) True noise points lie in sparse areas as measured by Pypurse. In Figure (left), we regard a dataset with uniform, spherical cluster of points and noise points that lie far apart. We add further noise close to the first noise point by placing them uniformly within small radius, which increases the density in this area. Increasing the density of noise points quickly deteriorates Poparse when the noise points start forming cluster. This lowers the overall DISCO score, as expected.
Distance between noise and the closest cluster (pfar) Noise points should be far from any cluster, a property measured by Pjor- We evaluate this part of the noise score in Figure (right) on a dataset with uniform, spherical cluster with radius the cluster's center. When the noise point is in the middle of the cluster, DISCO yields the desired outcomes around 0. Phoise and accordingly DISCO increases sharply as soon as the noise point not density- connetee to the cluster anymore, i.c., at distance from the center larger than 2.
and one noise point increasing distance from
5 CONCLUSION
We introduced DISCO, a density- -bsed internal CVI for the evaluation of arbitrarily-shaped cluster- ings that includes evaluating the quality of noise labels. We provide extensive experiments showcasing the ability of DISCO to properly evaluate large variety of clusterings. DISCO enables fair and reproducible evaluation of density- based clustering and clusterings with noise labels.
ACKNOWLEDGEMENTS
We gratefully acknowledge financial support from the Vienna Science and Technology Fund (WWTF- ICT19-041) and the Austrian funding agency for business-oriented research, development, and innovation (FFG-9036413), This work was partially funded by project W2/W3-108 Initiative and Networking Fund of the Helmholtz Association. We also acknowledge funding from the Danish Pioncer Centre for AI DNRF grant number Pl.
REPRODUCIBILITY STATEMENT
This work includes a git repository (https://githui) htwp://bb.co//pssiieeee/////Cc.o including the code to and reproduce the experiments. Hyperparameters for competitors, well as the data, including data processing steps, are either included in the code or referenced.
http://pojjjtt...ff...a///////// Phttps://aicentres
10

---

Internal Evaluation of Density-Bass Based Clusterings with Noise
REFERENCES
Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel, and Jörg Sander. OPTICS: Ordering points to identify the clustering structure. In ACM SIGMOD International Conference on Management of Data (SIGMOD), pp. 49-60, 1999. ISBN 1581130848.
Tomas Barton and Tomas Bruna. Clustering benchmarks, 2015. URL Utt.tttss://iithbbboo
Anna Beer, Andrew Draganov, Ellen Hohma, Philipp Jahn, Christian MM Frey, and Ira Assent. Con- necting the doos-density-comectiiiyy distance unifies DBSCAN, k-Center and Spectral Clustering. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining (SIGKDD), pp. 80-92, 2023.
Anna Beer, Pascal Weber, Lukas Miklautz, Collin Leiber, Walid Durani, Christian Böhm, and Claudia Plant. SHADE: deep density-basee based clustering. In IEEE International Conference on Data Mining (ICDM), pp. 675-680, 2024.
Anna Beer, Ekaterina Kuznetsova, and Claudia Plant. Parameter Selection for DBSCAN: Insights from Persistent Homology. ECA/ 2025: 28th European Conference on Artificial Intelligence, pp. 3250-3257, 2025.
Rajen Bhatt. Wireless Indoor Localization. UCI Machine Learning Repository, 2017. DOI: (ttp:/iioorrr1102223//551/1
Christian Böhm, Claudia Plant, Junming Shao, and Qinli Yang. Clustering by synchronization. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining (SIGKDD), pp. 583-592, 2010.
Ricardo G. B. Campello, Davoud Moulavi, and Jörg Sander. Density-based clustering based on hierarchical density estimates. In Advances in Knowledge Discovery and Data Mining (PAKDD), pp. 17:00-12,200 2013.
Magorzata Charytanowicz, Jerzy Niewczas, Piotr Kulczycki, Piotr Kowalski, and Szymon Lukasik. Seeds. UCI Machine Learning Repository, 2010. DOI: https://doi.org// https://doi.org/1..4442222 2440////012122//5553
Dongdong Cheng, Qingsheng Zhu, Jinlong Huang, Quanwang Wu, and Lijun Yang. A novel cluster validity index based on local cores. IEEE Transactions on Neural Networks and Learning Systems, (((4):985-99)) 2018.
Paulo Cortez, A. Cerdeira, F. Almeida, T. Matos, , and J. Reis. Wine Quality. UCI Machine Learning Repository, 2009. DOI: https///o..org/1.22433///66
David L. Davies and Donald W. Bouldin. A cluster separation measure. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1(2):224-227) 1979.
Joseph C Dunn. Well-separated clusters and optimal fuzzy partitions. Journal of Cybernetics, 4(1): 95-104, 1974.
Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu. density- based algorithm for dis- covering clusters in large spatial databases with noise. In International Conference Knowledge Discovery and Data Mining (KDD), pp. 226-231, 1996.
R. A. Fisher. Iris. UCI Machine Learning Repository, 1936. DOI: https//dbb.ogg/1.223333CCCCC
Jana Gauss, Fabian Scheipl, and Moritz Hermmann DCSI an improved measure of cluster separa- bility based separation and connectedness, 2024. URL https: /tt//aiivv././///////ee/////aava /atxwi..gg//abbbasaa.../. /2310. 12806.
Maria Halkidi and Michalis Vazirgiannis. Clustering validity assessment: Finding the optimal partitioning of data set. In IEEE International Conference Data Mining (ICDM), pp. 187-194, 2001.
Maria Halkidi and Michalis Vazirgiannis. A density- cluster validity approach using multi- representatives. Pattern Recognition Letters, 296))7773-786 2008.

---

Internal Evaluation of Density-Bass Based Clusterings with Noise
Mark Hopkins, Erik Reeber, George Forman, and Jaap Suermondt. Spambase. UCI Machine Learning Repository, 1999. DOI: http:///bb.rrr/10.24433//33333
Lianyu Hu and Caiming Zhong. An internal validity index based on density-involved distance. IEEE Access, 7:40038-40051, 2019.
Philipp Jahn, Christian MM Frey, Anna Beer, Collin Leiber, and Thomas Seidl. Data with density- based clusters: A generator for systematic evaluation of clustering algorithms. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 3-21. Springer, 2024.
Lena Krieger, Anna Beer, Pernille Matthews, Anneka Myrup Thiesson, and Ira Assent. FairDen: Fair Density-Bare -Based Clustering. In The Thirteenth International Conference on Learning Representa- fions, 2025.
Gangli Liu. Min-max-juma distance and its applications. arXiv preprint arXiv:2301.0599) 2023.
Yanchi Liu, Zhongmou Li, Hui Xiong, Xuedong Gao, and Junjie Wu. Understanding of internal clustering validation measures. In 2010 IEEE international conference on data mining, pp. 91 911-916. leee, 2010.
Yanchi Liu, Zhongmou Li, Hui Xiong, Xuedong Gao, Junjie Wu, and Sen Wu. Understanding and enhancement of internal clustering validation measures. IEEE Transactions on Cybernttcs, 43(3): 982-994, 2013.
Kolby Nottingham Markelle Kelly, Rachel Longjohn. The UCI machine learning repository, 2023.
URL hettttt///cchii/ ics. uci edu/mml
Davoud Moulavi, Pablo A Jaskowiak, Ricardo J. G. B. Campello, Arthur Zimek, and Jörg Sander. Density-based clustering validation. In SIAM International Conference on Data Mining (SDM), pp. 839-847, 2014.
Kenta Nakai. http://oo..oog//10.244/4///////
Yeast. UCI
Machine
Learning
Repository, 1991.
DOL:
Sameer A. Nene, Shree Nayar, and Hiroshi Murase. Columbia object image library (coil-
20). 1996. URL settps:/wwit cs columb ia. http:///////offaaa///ottt..... coil-20.phs
Oron Nir, Jay Tenenbaum, and Ariel Shamir. Unimodal Strategies in Density- Based Clustering. In Joint European Conference Machine Learning and Knowledge Discovery in Databases, pp. 438-513. Springer, 2025.
Peter Rousseeuw. Silhouettes: a graphical aid to the interpretation and validation of cluster analysis. Journal of Computational and Applied Mathematics, 20:53-65, 1987.
Georg Stefan Schlake and Christian Beecks. Validating arbitrary shaped clusters A survey, In IEEE International Conference on Data Science and Advanced Analytics (DSAA), 2024.
Erich Schubert, Jörg Sander, Martin Ester, Hans Peter Kriegel, and Xiaowei Xu. DBSCAN revisited, revisited: why and how you should (still) use DBSCAN. ACM Transactions on Database Systems (TODS), 42(3):1-21 2017. doi: https://doi.org/10. 1tt..///r///.114//36633333333 145/3068335.
Ali Şenol. VIASCKDE index: novel internal cluster validity index for arbitrary-shaped clusters based on the kernel density estimation. Computational Intelligence and Neuroscience, 2022(1): 4059302, 2022.
Theresa Ullmann, Anna Beer, Maximilian Hünemörder, Thomas Seidl, and Anne-Laure Boulesteix. Over-optimistic evaluation and reporting of novel cluster algorithms: an illustrative study. Advances in Data Analysis and Classification, 17(1):211-23 2023.
Mohammed J Zaki, Wagner Meira Jr, and Wagner Meira. Data mining and machine learning: Fundamental concepts and algorithms. Cambridge University Press, 2020.
12

---

Internal Evaluation of Density- Density-Based Clusterings with Noise
A BACKGROUND ON DENSIT--CONEETIVIT
Enclidean dist to Gj 3.3.
Enclidran dist to C2.24.5
do-dist 2. defining edge
do-dist ei 1.5
C2
dafping edge
Figure 7: Regarding the dc-dist, C2 is closer to object than C1.
A.1 DENSITY-CONNECTIVEE DISTANCE
Figure 7 visualizes the distances between point v to points in the other clusters. Decisive for the de-distance between any points the widest sparse that needs to be bridged: The point in the red cluster is closer (in terms of dc-dist) C2 than C₁ because the gap between the Ö2 and C2 smaller than between C₂ and C1. Since these gaps are the longest edges one needs to pass reach Ci C2 from the length of those edges defines the respective dc-dist. This notion of "closest" contrasts with the Euclidean distance under which Ci would be the closest cluster from and not C2-
A.2 "GOOD' NOISE AND 'BAD' NOISE- A VISUALIZATION
We visualize different base
of 'good' and 'bad' noise in Figure 8. The toy example shows two dense clusters (red and teal) and a less dense cluster in yellow. The selected clustering detected the yellow and the teal cluster (objects represented by circles) and assigned the objects shown as three-ray stars to noise. Conceptually and intuitively, a CVI should return the following:
(a) (lbbella the red, dense cluster (a) as noise should yield low quality scores.
Labeling the blue point (b) with the largest core-distance in the dataset that far away from all other points as noise should yield high quality score.
(c) Labelling the red point (c) within the yellow low-density cluster as noise should yield low quality scores.
(d) Labelling point (d) correctly is hard: The closest cluster regarding Euclidean distance is the dense (teal) Cluster 2. Compared to Cluster 2, the point clearly a noise point, as is farther away than the deore of this cluster. However, the point (d) fits the sparser (yellow) Cluster 1, lying within distance deore and should, thus, be assigned to Cluster 1.
DISCO fulfills these requirements. E.g., using the minimum of Psparse and Pfar in Equation (7) ensures that not only (c) but also (a) and (d) in Figure 8 get low DISCO scores.
noise points forming
(b)
dlesse region
'good' Isolated noise
(8)
Cluster 2
in dense region and closs
(d)
Sedcom
Cluster
close to Cl
Figure 8: Assessing the quality of noise: red noise labels have low DISCO scores, and blue is prototypical noise.
13

---

Internal Evaluation of Density-Bass Based Clusterings with Noise
Furthermore, the noise Pfar of the noise point (d) that is decisive for the DISCO score in this case is determined by Cluster I and not Cluster 2, even though both have the same distance because Cluster has larger core-distance.
B DBCV IS NOT DETERMINISTIC
In Section 2, state that DBCV (Moulavi al., 2014) is deterministic. DBCV's (non-) determinism is not discussed in Moulavi et al. (2014) or to the best of our knowledge in any other literature, yet, and one might think any evaluation measure will automatically return the same values for the same clustering. The first subsection shows how non-unique MSTs lead to the observed lack of determinism, while the second includes additional experiments showcasing the problem that non-determinism might bring.
B. INFLUENCE OF MSTS
Kruskal MST on MRD
Prim MST MRD
35-
30
MRD
25
20-
Figure 9: Different MST's the graph given by the mutual reachability distance (MRD) with minPts = 15 on the complex8 dataset. MSTs are computed with Kruskal's algorithm (left) and Prim's (right). Both are equally valid, but have different of Ieaf nodes.
easy overlook that MSTs are not unique, in practice, most datasets in Euclidean space have a unique MST. However, the MSTs used in DBCV are not computed on pairwise distances in Fuclidean space, but on the mutual reachability distance d,, between points. As dm based on maximum function, it typically produces many repeated pairwise values in the distance matrix, while there are few to none when using Euclidean distance. Thus, there are many different valid MSTs with different sets of leaf nodes (c.g., in Figure 9). Most implementations simply return one possible MST (e.g., NetworkX, SciPy). For many use cases of MSTs, it does not make a difference for the downstream task, which of the valid MSTs is used (e.g. Christofides' 1.5 approximation for metric TSP). However, as DBCV relies on the structure of the MST and excludes leaves of the MST the set of excluded points as well as the number of excluded (leaf) points might change drastically between different computation methods. Experimentally, we can show this by using different algorithms to build the MST as they are not specified in Moulavi al. (2014) (see Figure 9), or even by simply choosing different processing orders of data points, for e.g., Prim or Kruskal. We performed the latter experiment in Figure on two different datasets. For both datasets, we compute the DBCV of a given, fixed clustering and solely change the order in which the points processed. Each point's cluster assignment stays the same for all 1000 runs. A deterministic CVI would yield the very same result for all 1000 runs, the order of points does not matter for data set. However, DBCV exhibits a Gaussian distribution of values. Certainly, the strength of the effect and the variance of results vary for different datasets. However, in order to prevent overoptimistic evaluation: One can easily misled into believing that a specific clustering (method) is better/worse than another one by accidentally receiving values from the tails of
argue that CVI should never be non non-eeteriinistic
14

---

Internal Evaluation of Density-Basse Based Clusterings with Noise
Parameter setting (e, (ls))
DBCV (mean)
Selected (in % across 100 runs)
(0.06, 10)
0.684 0.095
7
(0.06, 8)
0.675 + 0.113
70
Ground Truth
0.618 + 0.037
23
Table 5: Parameter selection when using DBCV for parameter optimization for cluto-t5-8k.
the distribution. We show that such effects actually appear practice and exemplarily showcase that they can lead highly suboptimal choices of hyperparameters for DBSCAN.
Note that the variance and subsequent suboptimal choices could be diminished by performing DBCV computations several times over randomized processing order. However, this is not done in state-of-the-art research, will increase the runtime drastically, and is still not deterministic.
B.2 SELECTING THE BEST PARAMETER SETTINGS FOR CLUTO-T5-8K
We conduct additional experiments highlight the drawbacks of DBCV's lack of determinism. The goal of the experiment is hyperparameter optimization. The experiment setup is as follows:
1. We calculate DBSCAN clusterings for minPts {0.04, 0.045, 0.05, 0.06, 0.1, 0.2, 0.3, 0.43 for the cluto-t5-8k benchmark dataset (overall: 40 clusterings).
{2, 4,,4,5, 10} and E
2. We evaluate the clusterings with DBCV determine the best clustering, i.e., the optimal parameter set for DBSCAN, This step is performed 100 times:
(a) For each of the 100 runs, shuffle the order of the dataset and labels, respectively. Thus, within one run, the order is the same across all 41 clusterings (DBSCAN+GT).
(b) For each run, we evaluate all clusterings with DBCV, and depending the highest DBCV value, we report which clustering is determined as the best one.
3. After evaluating the clusterings across all runs, we count how often each clustering was determined to be the best across the runs. A deterministic CVI would prefer the same clustering (with the highest value) in each case.
For this experiment, we made sure that DBCV actually achieves high scores of 0.5 and above, often approaching 0.75. We observe that only two of the 40 DBSCAN clusterings are ever chosen to be the best clustering by DBCV, namely settings (a) and (b) as shown in Table and illustrated in Figure 10. We also visualize the spread of DBCV values in Figure 11, where we observe that the spread for settings (a) and (b) much wider than for the GT clustering. On average, and (b) achieve higher mean DBCV scores than the ground truth, and in 70 out of 100 runs, users relying on DBCV would choose (b) over the other settings.
PLOUCE CLOUGE
OLOUEE
(a)
clusters + noise
(b) 3 clusters + noise
GT: clusters noise
Figure 10: Clusterings for cluto-t5-8k. 5k. that least once labeled the best by DBCV. Across the 100 runs, DBCV selects clustering (a) in 7 runs, (b) in 70 runs, and the ground truth in 23 runs.
15

---

Internal Evaluation of Density-Bass Based Clusterings with Noise
Parameter setting (a)
Parameter setting (b)
GT
Count
0.2
0.4
0.6
0.8
DBCV
Figure 11: DBCV scores for GT and two DBSCAN clusterings on cluto-t5-8k. The dashed line denotes the mean value. Across the 100 runs, DBCV selects setting (a) in 7 runs, (b) in 70 runs, and the ground truth in 23 runs.
B.3 COMPARISON BETWEEN CLUSTERINGS ON CLUTO-T8-88 -8K WITH DBCV
In the second experiment, use the cluto-t8-88 dataset. On this dataset, DBCV scores the ground truth (GT) with low values around O. For the experiment, we calculate labels for three parameter settings for DBSCAN ((a), (b), and (c) in Table 5) as well as the ground truth clustering as shown in Figure 13). We compute DBCV values for different processing orders of these clusterings and report them in Table The ground truth yields the best DBCV value in 67%, DBSCAN clustering (c) is selected in 10%, and parameter setting (6) is selected in 23% of the runs. In Figure 12, we show the DBCV score range for each clustering.
In practice, when selecting the best clustering, the ground truth labeling is often not included in the options. Thus, we also report how DBCV selects between (a), (b), and (c) when it not available. We observe in Table 6, last column, that DBCV shows even more variance than before in choosing the best possible clustering. Interestingly, for parameter setting (a), the variance between the individual DBCV scores is much lower than for the other clusterings.
Parameter setting
(e,minfts)
DBCV (mean)
Selected (in % across 100 runs)
Selected (when GT excluded)
(0.04,5
-0.278 0.015
21
(0.2, 2)
-0.242 + 0.315
23
40
(0.1. 8)
-0.213 + 0.166
10
39
Ground Truth
-0.025 + 0.076
67
Table 6: Parameter selection when using DBCV for hyperparameter tuning. The last column shows the number of selections when GT is not available.
Parameter Setting (a)
Parameter Setting (b)
Parameter Setting (c)
GT
Count
40
20
-0.8
-0.6
-0.4
-0.2 DBCV
0.0
0.2
0.4
Figure 12: DBCV score ranges across included parameter settings and 100 evaluation runs. The dashed line denotes the mean value.
16

---

Internal Evaluation of Density-Bass Based Clusterings with Noise
(a) 173 clusters + noise
(b) 2 clusters
(c) 3 clusters noise
GT: 8 clusters noise
Figure 13:
Clusterings for cluto-t8-8k dataset. Note that the second cluster in (b) is the two pink points in the lower right. Across the 100 runs, DBCV selects clustering (b) in 23 runs, (c) in 10 runs, and the ground truth 67 runs. When GT unavailable, (a) is selected 21, (b) 40, and (c) 39 times.
Thus, users who relying DBCV to find the best parameter settings encounter several problems originating in DBCV's non-determinism: 1) The DBCV scores for the same clustering deviate depending the machine, processing order, implementation of DBCV. 2) Because of the high variance of DBCV scores for some clusterings, users would need to compute DBCV sufficiently often to make sure they choose the parameter setting that reaches the highest DBCV score on average. When computing DBCV only once (like common for an evaluation measure), is likely that a worse clustering yields the better DBCV scores.
C EXPERIMENT DETAILS
Here provide all details about experiment settings, implementations, methods, and datasets.
Experiment Settings All experiments were performed with Python 3.12 on a Linux workstation with 2x Intel 6326 with 16 cores each and multithreading. as well 512GB RAM. We use the sklearn clustering implementations for our experiments with clustering algorithms.
Datasets Table gives an overview the datasets we used. The synthetic data (Synth_high Sowth is provided by the data generator DENSIRED (Jahn et al., 2024) that we also used for some of the systematic experiments in Section Those datasets have ten density censity-comnected clusters of different densities that are generated based on random walks in high-dimensional space. For the generated data, we include noise points that are uniformly distributed and positioned outside of the clusters, they guaranteed to be density-separated from the clusters. All datasets z-standardized for the experiments. For tabular data, every feature has a mean of 0 and standard deviation of 1. For image data, this step has been performed globally instead of per feature.
Other Cluster Validation Indices Table 8 provides implementation details for our competitors. We link the author implementations where available and use them when implemented in Python. Otherwise, we re- re-implemented the method in Python for our experiments (marked with / in the last column). We employ the default hyperparameters provided by the authors. The first column implies the direction of the CVI: (L) means higher (lower) is better. We distinguish between bounded methods ( and I]) and unbounded ones (1 and + Both scores (S Dbw and CVNN), where lower values are better, in the range [0, oo), i..., they have a lower bound. To allow easy comparison, we linearly normalized unbounded scores to be in [0, 1] and reversed the values where lower values better have the orientation for all diagrams.
17

---

Internal Evaluation of Density-Basse Based Clusterings with Noise
Table Dataset properties. Number of samples (n), dimensions (d), ground truth clusters (k), noise points (#noise), DISCO score for the ground truth labels, and the source.
Dataset
n
#noise
DISCO
Source
smile1
1,000
2
4
0
0.90
Barton & Bruna (2015)
Density -base Benchmark Data
dartboard1
1,000
4
0
0.87
Barton & Bruna (2015)
chainlink
1,000
3
2
0
0.84
Barton & Bruna (2015)
3-spiral
312
0
0.59
Barton & Bruna (2015)
complex8
2,551
2
8
0
0.39
Barton & Bruna (2015)
complex9
3,031
9
0
0.36
Barton & Bruna (2015)
compound
399
2
6
0
0.35
Barton & Bruna (2015)
aggregation
788
7
0
0.31
Barton & Bruna (2015)
cluto-t8-8k
8,000
2
8
323
0.30
Barton & Bruna (2015)
cluto-t7-10k 10,000
2
9
792
0.29
Barton & Bruna (2015)
cluto-t4-8k 8,000
2
6
764
0.24
Barton & Bruna (2015)
diamond9
3,000
2
9
0
0.22
Barton & Bruna (2015)
Synth high
5,000
100
10
500
0.82
Jahn et al. (2024)
Synth low
5,000
100
10
500
0.76
Jahn et al. (2024)
Real World
htru2
17,898
0
0.41
Markelle Kelly (2023)
COIL20
1,440
16,384
20
0
0.30
Nene et al. (1996)
Pendigits
10,992
16
10
0
0.11
Markelle Kelly (2023)
cmu cmu_faces 624
960
20
0
0.07
Markelle Kelly (2023)
Optdigits
5,620
64
10
0
0.06
Markelle Kelly (2023)
Table 8: Implementation details of included internal CVIs.
Hyperparameter (default)
Official implementation
Implemented ourselfs
Method
1 Silhouctte Rousseeuw (1987)
(sklcamm)
S. BbD by Halkidi Vazirgiannis (2001)
1 DBCV by Moulavi al. (2014)
distance (squared euclidean) minPis (5)
Matlab, Python
DCST by Gauss al. (2024)
R
MMJ-SC by Liu (2023)
Python
X
LCCV by Cheng et al. (2018)
Matlab
VIASCKDE by Senol (2022)
handwidth, kernel (0.05, gaussian)
Python
CVDD by
Zhong (2019)
number of neighburhouds (7)
Matlab
CDbw by Halkidi & Vazirgiannis (2008)
number of representative points (10)
CVNN by Liu al. (2013)
number of nearest neighbors (10)
DISCO (ours)
Python (github)
D ADDITIONAL EXPERIMENTS
The following subsections present the results of additional experiments, including runtime experi- ments, an analysis to determine optimal parameter settings, experiments that demonstrate DISCO's robustness towards μr, and sensitivity analysis of the clustering score.
D.1 RUNTIME EXPERIMENTS
Figure 14 illustrates runtimes across different CVIs and datasets, including high-dimensional (
COIL20 (n 1, 440, d = 16, 384), Synth high (n = 5, 000, 100), Optdigits (n = 5, 620, d 64)) and large low-dimensional datasets (cluto-t8-8k (n 8, 000, d 2). cluto-17-10k (n
10, 000,0044 d = 2. Pendigits(n = 10. 992, = 16), htru2 (n = 19,898.4 = 8)). More details regarding the datasets be found in Section C. Additional runtimes
shown in Table 9. We
find that the runtime of DISCO increases with the size the dataset rather than its dimensionality. DISCO performs similarly to CVNN, DBCV, and DCSI. However, the runtimes of CVDD, LCCV,
18

---

Internal Evaluation of Density-Basse Based Clusterings with Noise
Table 9: Runtimes of the CVIs in seconds.
Dataset
DISCO
DBCV
DCSI
MMJ SC
LOCV
VIAS.
CVDD
CDbw
CVNN
Silh.
S_Dbw
three_spiral
0.147
0.089
0.137
0.126
0.139
0.159
0.613
0.079
0.096
0.065
0.060
aggregation
0.167
0.136
0.126
0.436
0.450
0.298
2.872
0.268
0.094
0.135
0.073
chainlink
0.197
0.186
0.226
0.659
1,005
0.427
4,467
0.156
0.105
0.085
0.051
cluto-t4-8k
4,245
1,780
4.192
41.749
418.852
17.633
279.168
23.077
1,974
1,177
0.254
cluto-17-10k
6.387
7.029
65.338
790.698
26.836
431.350
57.260
2.785
1.640
0.443
cluto-t8-8k
3,982
4.303
17.844
278.174
34.016
complex8
0.578
6.583
28.112
2.205
complexy
0.669
0.720
2.648
compound
0.105
0.100
0.076
0.168
0.138
0.052
dartboard1
0.185
0.156
0.154
0.650
0,532
0.427
4.476
0.186
0.060
diamond9
0.610
0.397
0.476
5.293
16.500
2.767
38.903
7,068
0.357
0.215
0.180
smile1
0.195
0.157
0.155
0.661
0.773
0.448
4,497
0.167
0.094
0.084
0.060
Jow
2.764
1.075
2,003
16.730
27.505
30.482
107.960
18.336
0.925
0.480
0.314
Synth
2.409
1.055
1.994
16.745
22.885
31.411
107.945
18.365
0.844
0.496
0.315
hiru2
37.191
38.432
89,207
259.819
6388,110
107.973
1399.325
78.498
13.875
6.170
0.194
Pendigits
8.428
2.932
5.485
82.153
1671.582
49.325
524.496
130.090
3.476
1,971
0.578
CO1 20
0.503
6.500
20.432
1,563
33.190
580.777
24.278
176.752
0.634
0.333
3.654
ema_faces
0.157
0.176
0.258
0.309
0.490
2.862
1.954
5.397
0.107
0.087
187
Optdigits
2.862
1.083
1. 1.891
22.835
222.576
27.727
137, 3378994
32.008
1.126
0.632
0.377
DISCO
-
DBCV
DCSI
MMJ-SC
LCCV
VIASCKDE
CVDD
CDbw
CVNN
Silhouette
S_Dbw
10
10a
Runtime in seconds
10a
10
100
10
COIL20
Synth hiihh
Optdigits
cluto-t8-8k
cluto-t7-10k
Pendigits
htruz
Dataset
Figure 14: Runtimes of the CVIs for several datasets (sorted by DISCO runtime). Time in seconds (logarithmic scale).
VIASCKDE, MMJ-SC, and CDbw are much higher (note the logarithmic scaling of the y-axis). Only the centroid-based CVIs, Silhouette, and S. S_Dbw are faster.
D.2 DETERMINING BEST PARAMETER SETTINGS
Figure 15 shows the CVI scores for different parameter settings for DBSCAN on two datasets: 3-spiral (left) and COIL20 (right). DISCO, as well as some its competitors, is suitable for finding very good parameter settings for DBSCAN, where the ARI is (close to) optimal. For the 3-spiral dataset, CDbw and VIASCKDE overestimate the optimal number of clusters and suggest a too small e-value. For COIL20, there several e-values that lead 19 clusters, but value that leads to the ground truth number of clusters & = 20. While most CVIs are best for one of the settings, producing 19 clusters, CDbw, LCCV, DCST, and Dbw overestimate the number of clusters and
19

---

Internal Evaluation of Density-Basse Based Clusterings with Noise
K
2
3
6
1.00
DISCO
0.75
DBCV
0.50
DCSI
CV
MMJ-SC
0.25
LCCV
0.00
VIASCKDE
CVDD (n)
0.25
CDbw (n)
CVNN (r.n)
1.0
Silhouette
ARI
0.5
S_Dbw (r.n)
0.0
3.821
3.668
1.044
1.000
0.982
0.939
8
(a) spirrl dataset
k
15
16
17
17
18
19
18
18
19
19
19
19
23
22
24
23
21
21
22
24
DISCO
0.8
DBCV
DCSI
0.6
MMJ-SC
LCCV
VIASCKDE
0.2
CVDD (n)
CDbw (n)
CVNN (r.n)
Silhouette
0.5
S_Dbw (r,n)
0.0
6120.240
6107.645
686
5872.788
5809 921
5748.633
5486.73 732
5481.318
5458.487
5452.070
5421.436
5337.759
4984.786
4879.037
4822.420
4764.130
360
4559.038
4522.093
7487.772
6107.6
6057.
4565
448
(b) COIL20 dataset
Figure 15: CVIS for DBSCAN clusterings with varying E values on the 3-spiral dataset (a) and the COIL20 dataset (b). We report CVI scores (top) and the corresponding ARI scores (bottom). The x-axes give the e-values and the resulting number of clusters. The best CVI score (larger circles) should ideally correspond to the best ARI score (red column). Note that for COIL20,, there are various similar e-values that all yield very similar clusterings with the same number of clusters (k 19). The same happens for 3-spiral: there are various e-values that yield very similar clusterings with similar number of clusters (k 3, 4).
prefer significantly lower value for e. summary, DISCO is reliable tool find good parameter settings for DBSCAN on datasets with very different sizes, dimensionalities, and numbers of clusters.
D.3 ROBUSTNESS TOWARDS f
To additionally analyze the influence of μ on the DISCO score and its behavior under varying levels of noise perform the following experiments in Figure 16. We increase the amount of uniform additive noise on a synthetic dataset with 10 density- based clusters, generated with DENSIRED (Jahn al., 2024). DISCO is stable for μ 2 across large range of added noise. For l 1, each point
20

---

Internal Evaluation of Density-Basse Based Clusterings with Noise
0,9
0.8
0%
10%
20%
DISCO
0.7
30%
40%
50%
0.5
1
Figure 16: DISCO scores on synthetic data for varying μ and noise levels.
0.855
Data
0.775
Byrth, high
01800
0.750
Synth Jow
0.725
guussion
uniform
0.700
polcson
0.675
11
Figure 17: DISCO scores on Synth_high and Synth with different type of noise for varying J..
1.0
Synthuhigh high
0.6
Synth
NriteCisttbuliin
gaussian
uniform
02
poisson
0.0
Figure 18: Noise scores Pnoise on Synth_high and Synth low with different noise distributions for varying
has a core-distance of zero. Thus, all added noise points would ideally form singleton clusters, which leads to lower DISCO scores for higher noise percentages.
D.4 DIFFERENT NOISE DISTRIBUTIONS
To account for other noise distributions, we perform additional experiments similar to the one outlined in Figure For this experiment, we utilize the two datasets Synth high and Synth low, each of which originally contains 500 noise points. We replace the existing noise points with 500 newly generated points with Gaussian, uniform, and Poisson distributions. The Gaussian parameters are determined based the mean and standard deviation of the remaining points. For the Poisson distribution, we set the lambda parameter to 5, using the numpy random implementations. Each dataset is then evaluated across range of μ values (1, 5, 7. 9. 11). The results visualized in Figure 17 and Figure 18. We find that the DISCO scores behave very similarly across all tested noise strategies. Additionally, note that the results across varying values for (s are very consistent.
21

---

Internal Evaluation of Density-Basse Based Clusterings with Noise
Table 10: Number of objects n., dimensionality number of noise points #noise points, and number of clusters |8| found by HDBSCAN with default parameters (minclustersize=5)) and the ground truth number of classes le on five real world datasets.
Dataset
d
#noise
[8]
k
DISCO
Iris (Fisher, 1936)
150
4
2
2
3
0.61
Seeds (Charytanowicz et al., 2010)
199
7
78
3
3
0.14
WiFi (Bhatt, 2017)
2000
147
0.25
Spambase (Hopkins et al., 1999)
4601
57
3407
121
2
-0.27
Wine quality (Cortez et al., 2009)
6497
11
4946
166
-0.36
Yeast (Nakai, 1991)
1484
8
0
10
0.82
Point
Cluster
Noise
Praie
-0.5
-1.0
Ins
Seads
WIFI
Spembase
Wine quality
Yeast
Dataset
Figure 19: Pointwise noise scores (Pnoise) for cluster (yellow) and actual noise (blue) points according HDBSCAN clusterings with default parameters on six real-world datasets (described in Table 10). Note that HDBSCAN yields low quality clusterings on Spambase and Wine quality: it significantly overestimates the number of noise points as well the number of clusters, assigning 74.05% and 76.13% of all points to noise, respectively, which leads to the low values for Proise. On the Yeast dataset, it assigns all points to clusters.
D.5 NOISE IN REAL-WWORLD DATASET
We test DISCO's performance on six real-world UCI datasets as shown in Table 10. We use the labeling E given by HDBSCAN with default settings. In this experiment, compare posnt-wise noise scores between actual noise-labeled points and points that were assigned to a cluster by HDBSCAN ('cluster points'). A good evaluation measure should return higher scores for noise points than for cluster points that were labeled as noise.
To assess DISCO's noise score Pnoise (x) for cluster points, treat each cluster point xe as a noise point once, i.e., we calculate DISCO scores for the given clustering with the only change that point He labeled as noise. Thereby, we can assess which noise score this wrongly labeled noise point would receive. We do this for every cluster point in the clustering individually. Figure 19 illustrates the point-wise noise scores, categorized by point type: noise points versus cluster points. DISCO consistently evaluates noise points with higher scores than non-noise points that have been (wrongly) assigned noise.
Note that for the larger datasets, Spambase and Wine quality, the scores for many noise points are negative, indicating low quality the noise labels. This is because of the significant overestimation of noise points in the dataset by HDBSCAN: it assigns 74.05% and 76.13% of all points to noise, respectively, and finds 121 instead of clusters on the Spambase dataset and 166 clusters instead of on the Wine quality dataset. On the Yeast dataset, HDBSCAN detects three clusters and noise. The range of DISCO's s noise scores Pnoise E [-1,0] 0] suggests that the points are correctly assigned to be in some cluster (instead of noise).
22

---

Internal Evaluation of Density- Density-Based Clusterings with Noise
D.6 SENSITIVITY ANALYSIS OF CLUSTERING SCORE Peluster
As we focus on density-based clustering evaluation, we exclude S S_Dbw and CVNN in the following diagrams for clarity.
D.6.1 INFLUENCE OF MISLABELED CLUSTER POINTS
A good CVI should be robust against small changes in the clustering, and points with similar role in the dataset should have a similar influence on the score. In Figure 20a,* we increase the percentage of wrongly assigned points for the two-moons dataset. While most CVIs, including DISCO, show the intended consistent decrease in quality, DCSI and DBCV show questionable behavior. DBCV drops the worst-case evaluation of -1 soon as only 2 of 50 points per cluster wrongly assigned. DCSI gives a perfect score for less than 10% wrongly assigned points and the worst-case score for more than 14% wrongly assigned points, leaving only a very small range with distinguishable results.
D.6.2 INFLUENCE OF SEPARATION
Figure 20b shows the CVIs for increasingly distant clusters, exposing interesting behaviors for CDbw and CVDD: They display consistent, linear increase, where it not recognizable at which distance the switch from density-conneed to density-separated clusters happens. In contrast, DISCO, DBCV, and DCSI increase sharply as soon as the clusters are clearly separated.
D.6.3 INFLUENCE OF FUZZY CLUSTER BORDERS
To regard the influence of blending and fuzzy clusters, we increase the fuzziness (jitter) of the two moons dataset in Figure 20c. Most CVIs, including DISCO, behave expected, starting with high values that evenly decrease. However, CVDD drops quite rapidly for very low amounts of jitter, where the clusters still well separated. LCCV shows unexpected drop 2% jitter, yielding higher scores for less and more jitter. Being purely catroid-bbssed the Silhouette Coefficient stays constant.
E
LLM USAGE
In some paragraphs, we used LLMs a post-processing step improve wording and grammar. While we did not copy anything above sentence level, we drew inspiration for shortening or phrasing more elegantly. Figures and content of the paper are our own work and have not been generated, updated, or processed with LLMs.
'For clarity, we linearly normalize CVDD and CDbw to [0. 1] in all plots, marked with (n). CVIs with reversed orientation additionally subtracted from their largest value, marked with (r).
23

---

Internal Evaluation of Density-Basse Based Clusterings with Noise
DISCO
DBCV
DCSI
MMJ-SC
LCCV
VIASCKDE
CVDD (n)
CDbw (n)
Silhouette
1.0
0.5
Score
0.0
-055
-1.0
10
20
30
40
50
% points moved from each cluster to the other cluster
(a) Influence of mislabeled points: Increasing percentage of random points assigned to the wrong cluster in the two moons dataset.
1.0
0.5
Score
0.0
-05
-1.
9
12
15
distance between the two clusters
(b) Influence of separation: Increasing distance between cluster centers for uniform, spherical clusters of radius 2.
1.0
0.5
Score
0.0
0.5
0.000
0.025
0.050
0.075
0.100
0.125
0.150
0.175
0.200
fuzziness
(c) Influence of fuzzy cluster borders: Increasing fuzziness of two moons (in percent of "jitter").
Figure 20: Ablation of Clustering Score Petnter (data shown along the x-axes).
24


Reviews:
[{"review_id": "9vNXmhZYOn", "reviewer": "Reviewer_i8eV", "summary": "This paper introduces DICSCO (Density-based Internal Score for Clustering with Noise), a new validation metric designed to assess the quality of noise assignments in density-based clustering. The work addresses the limitation in existing cluster validation indices (CVIs) with improved noise condition modeling. Results indicate that DICSCO can better represent clustering quality in some cases presented.", "questions": "How well can the method handle other noise distributions?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The evaluation of density-based clustering quality with noise is an important topic.\n2. The paper is clearly presented and well-organized. The concept of “bad noise examples” is effectively illustrated with a toy example\n3. The experimental results show its improvements over the baselines.", "weaknesses": "1. The method only considers the uniformly distributed noises, which is limited in real-world situations.\n2. The evaluation uses a few 2D synthetic datasets except for COIL20 and Pendigits. The few examples feel arbitrary and it is unclear how results will change if layouts are changed. While the method performs well in this setting, including more real-world or high-dimensional datasets will help to see if the proposed CVI performs consistently beyond artificial 2D cases. For example, more existing datasets with labels can be used to evaluate the scoring quality by comparing to ground truth.\n3. The comparison uses some very bad clustering results to show the strength. But because the paper focuses on density-based clustering, it is unclear if those \"very bad\" clustering results  are useful for experiments as methods like HDBSCAN likely won't generate those.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tdoGLrs8s0", "reviewer": "Reviewer_u9M9", "summary": "This paper introduces DISCO, a novel internal cluster validity index (CVI) designed for evaluating density-based clusterings that include noise points. The authors identify a critical gap in existing internal CVIs: most either ignore noise points or penalize their mere presence without assessing the quality of their assignment. DISCO addresses this by extending the concept of the Silhouette Coefficient to use density-connectivity distance, making it suitable for arbitrary-shaped clusters, and by introducing a pointwise noise evaluation mechanism that rewards correct noise labels and penalizes incorrect ones. Through extensive experiments, the paper demonstrates that DISCO outperforms existing methods in evaluating density-based clusterings, selecting optimal parameters, and aligning with external validation measures, while also being deterministic and handling edge cases robustly.", "questions": "1. Given the O(n²) complexity, what are the practical limits of DISCO on large-scale datasets? Do the authors have plans or can they discuss potential strategies for approximate computation of the dc-dist or MST to improve scalability? Could you add a runtime comparison table against key competitors like DBCV and LCCV?\n2. Could the authors design a supplementary experiment that quantifies the risk posed by DBCV's non-determinism in a model selection scenario? For instance, when comparing two clusterings, how frequently does the random variation in DBCV's output lead to the selection of the objectively worse clustering?", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper tackles a long-overlooked problem in clustering validation: evaluating the quality of noise assignments. DISCO is the first internal CVI to explicitly assess whether a noise label is appropriate, moving beyond simple counting.\n2. The experimental section is thorough and systematic. The authors not only compare DISCO against a wide range of baselines on standard tasks like parameter selection but also design specific experiments to highlight its unique capability in noise assessment.\n3. The identification and empirical demonstration of non-determinism in DBCV is a valuable finding for the community.", "weaknesses": "1. While the O(n²) time complexity is stated and argued to be comparable to other density-based CVIs like DBCV, no actual runtime comparisons are provided.\n2. The evaluation of DISCO's noise-handling capability relies heavily on well-structured synthetic datasets. While effective for proof-of-concept, demonstrating its performance on real-world datasets with complex, real noise would greatly enhance the generalizability and impact of the claims.\n3. Parameter μ is not fully discussed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "50Xpcf5L7p", "reviewer": "Reviewer_r7HB", "summary": "The paper introduces DISCO, a new internal cluster validity index (CVI) designed to evaluate density-based clusterings (like DBSCAN or HDBSCAN), especially when noise points are present and when clusters have irregular (non-spherical) shapes. The authors tested the new CVI on 20+ synthetic and real-world datasets, including 2D toy data (rings, spirals) and high-dimensional sets (COIL20, Pendigits). The paper also shows that DISCO is robust to parameter changes, computationally efficient (O(n²)), and capable of evaluating all edge cases including single-cluster or all-noise situations.\n\nWhile the paper makes a novel contribution, its main weaknesses lie in computational scalability, limited generality beyond density-based clustering, limited comparison with other CVIs, and modest theoretical depth, leaving room for future improvements and broader extensions.", "questions": "I have encountered difficulties when reproducing the experiments in \"DISCO-E358/src/Experiments\" folder. Could you provide a jupyter notebook file to reproduce the values in Figure 1? It is preferable to include all the necessary code in one or two files. E.g., using one file to define all the necessary functions and classes. It is a pain to check different functions and classes in multiple files.\n\nYou can provide the jupyter notebook file in an anonymous URL.", "limitations": "", "rating": 2, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The method provides a pointwise evaluation that treats both cluster points and noise points consistently, allowing fine-grained interpretability and explainable assessment of individual point assignments.\n\n2. DISCO remains well-defined even for special scenarios, such as having only one cluster, only noise, or singleton clusters—cases that typically break other indices.\n\n3. Its output is normalized between −1 and 1, making scores easy to interpret and compare across datasets and algorithms.\n\n4. The authors conduct extensive experiments across many benchmark and real-world datasets, demonstrating that DISCO consistently aligns with external metrics (like ARI) and correctly identifies optimal clustering results.", "weaknesses": "1. Although comparable to other density-based CVIs, DISCO still requires quadratic time with respect to the number of data points, which may become computationally expensive for very large datasets (e.g., millions of points), limiting scalability.\n\n2. While the authors claim robustness to the hyperparameter μ, the paper provides limited theoretical justification or adaptive mechanism for choosing it automatically; its effect is shown empirically but not deeply analyzed.\n\n3. The experiments focus on accuracy and robustness but lack detailed runtime or memory usage comparisons against lightweight metrics like the Silhouette or Davies–Bouldin indices, which could highlight performance trade-offs more clearly.\n\n4. Although code is shared, I have encountered difficulties when reproducing the experiments in \"DISCO-E358/src/Experiments\" folder.\n\n5. The paper does not compare with other powerful CVIs like MMJ-SC and MMJ-CH. See:\n\n https://arxiv.org/abs/2301.05994\n \nPython code of MMJ-SC and MMJ-CH can be found at:\n\nhttps://github.com/mike-liuliu/Min-Max-Jump-distance/blob/main/test%20MMJ-based%20%20Silhouette%20coefficient%20(MMJ-SC).ipynb\n\n\nhttps://github.com/mike-liuliu/Min-Max-Jump-distance/blob/main/test%20MMJ-based%20Calinski-Harabasz%20index%20(MMJ-CH).ipynb", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)