Composite Silhouette: A Subsampling-based Aggregation Strategy Aggelos Semoglou1,2*, Aristidis Likas3 and John Pavlopoulos1,2
arXiv:2604.13816v1 [cs.LG] 15 Apr 2026
1*
Athens University of Economics and Business, Greece. 2 Archimedes, Athena Research Center, Greece. 3 University of Ioannina, Greece.
*Corresponding author(s). E-mail(s): [email protected]; Contributing authors: [email protected]; [email protected]; Abstract Determining the number of clusters is a central challenge in unsupervised learning, where ground-truth labels are unavailable. The Silhouette coefficient is a widely used internal validation metric for this task, yet its standard micro-averaged form tends to favor larger clusters under size imbalance. Macroaveraging mitigates this bias by weighting clusters equally, but may overemphasize noise from under-represented groups. We introduce Composite Silhouette, an internal criterion for cluster-count selection that aggregates evidence across repeated subsampled clusterings rather than relying on a single partition. For each subsample, micro- and macro-averaged Silhouette scores are combined through an adaptive convex weight determined by their normalized discrepancy and smoothed by a bounded nonlinearity; the final score is then obtained by averaging these subsample-level composites. We establish key properties of the criterion and derive finite-sample concentration guarantees for its subsampling estimate. Experiments on synthetic and real-world datasets show that Composite Silhouette effectively reconciles the strengths of micro- and macro-averaging, yielding more accurate recovery of the ground-truth number of clusters.
1 Introduction Clustering evaluation remains a crucial but challenging step in unsupervised learning, largely due to the inherent difficulty of assessing solutions without labeled data [1]. Among various internal clustering evaluation metrics, the Silhouette coefficient [2]
1
is one of the most widely adopted, as it effectively quantifies the compactness and separation of clusters using only intrinsic dataset properties. Its ease of interpretation and widespread implementation in libraries such as scikit-learn [3] have made it a default choice in many practical applications. However, the traditional approach, micro-averaging Silhouette scores across all individual data points [4], is known to exhibit significant bias, particularly in datasets with imbalanced cluster sizes, frequently encountered in real-world applications. In such cases, larger clusters can disproportionately influence the final score, potentially masking poor separation in minor clusters [5]. An alternative yet rarely utilized strategy, macro-averaging, aggregates Silhouette scores by first computing the mean Silhouette per cluster and then averaging across clusters. Although macro-averaging mitigates cluster-size bias by assigning equal weight to clusters irrespective of their sizes, it can overly emphasize smaller or under-represented clusters. This trade-off is especially evident in real-world settings.
Clustered Data
C1
Silhouette Aggregation
Domain Impact
Micro-Averaging
Business Analytics
Point-wise Weighting Evaluation across all data points: Every individual data point exerts equal influence on the score.
Focus on global utility. System performance is dominated by the bulk population (C1 ); minority clusters are marginal.
Macro-Averaging
Medical Diagnostics
Cluster-wise Weighting
Focus on patient-pattern discovery. Minority clusters (C2 ) represent meaningful subgroups that must remain visible.
Majority Group
C2 Minority Group
Evaluation across all identified clusters: Each cluster is weighted equally on the score.
The Inductive Bias Conflict It is often unclear whether a local structure represents a valuable subgroup (requiring Macro) or irrelevant statistical noise (requiring Micro). Practitioners face a bias trade-off with no universal selection criterion. Fig. 1: Silhouette aggregation strategies: Global trends vs. local patterns. For instance, in medical clustering [6], where rare but clinically important patient subgroups must be identified, macro-averaging is often preferable because it ensures that these small clusters are not overshadowed. In contrast, in customer segmentation [7], where the business impact of large, well-defined customer groups dominates, microaveraging tends to better reflect practical utility. Yet in other domains, such as topic 2
clustering [8], where some themes are broad and frequent while others are niche but still valuable, it is often unclear which strategy should be preferred. Depending on the application, both majority coherence and minority representation may be important. Consequently, practitioners face a critical choice between two fundamentally different aggregation strategies, each having its own limitations, and with no clear rule for balancing them across datasets and clustering solutions (Fig. 1). Moreover, the disagreement between micro- and macro-averaging may itself carry useful information, as it can indicate whether clustering quality is driven primarily by majority structure or by the fidelity of smaller groups. This suggests that, rather than selecting one aggregation strategy globally, a more effective criterion should adapt to how these two perspectives agree or diverge across different views of the data. The absence of such a criterion is particularly problematic in practical settings, where internal validation metrics guide the choice of the optimal number of clusters. In such cases, inconsistent or biased metrics can lead to misleading evaluations and suboptimal clustering decisions. This raises a central question:
Could an internal validation metric combine the strengths of micro- and macroaveraged Silhouette scores to guide cluster-count selection more accurately and reliably, without prior assumptions about which aggregation strategy is preferable? To address this question, we introduce Composite Silhouette, a subsampling-based internal validation criterion that aggregates micro- and macro-averaged Silhouette scores over repeated subsampled clusterings. Instead of relying on a single partition or enforcing a fixed global preference between micro- and macro-averaging, our method computes the two scores on each subsampled clustering and combines them through a subsample-specific convex combination, whose mixing weight is determined by the normalized discrepancy between them and smoothed by a bounded nonlinearity. The final score is then obtained by averaging these per-subsample composite scores across subsampling trials, yielding a more stable and adaptive criterion for cluster-count selection. In this sense, Composite Silhouette performs discrepancy-driven adaptive aggregation: the relative weight assigned to the two Silhouette views is determined locally at the subsample level, rather than fixed in advance for the entire dataset. This allows the criterion to respond to heterogeneous structure without committing a priori to either majority-dominated or minority-sensitive evaluation. We show that this formulation enjoys useful deterministic properties and admits finite-sample concentration guarantees for its subsampling estimate. Across synthetic and real-world datasets, Composite Silhouette accurately identifies the number of clusters in regimes where either micro- or macro-averaging alone would be effective, without requiring prior knowledge of which aggregation strategy is better suited to the data, while remaining competitive in balanced settings. Against a broad range of internal validation baselines, including both averages over subsampled clustering runs and averages from repeated clustering runs on the full dataset, Composite Silhouette achieves the strongest overall performance in recovering the ground-truth number of clusters. Overall, this work offers a principled and practical alternative to existing internal validation metrics, enabling more reliable model selection in settings where traditional approaches may fail to capture the underlying cluster structure accurately. Our code for Composite Silhouette is publicly available at: https://github.com/semoglou/comp sil. 3
2 Related Work Internal cluster validity indices Internal validity indices provide a label-free way to evaluate clustering solutions by examining only the geometry and dispersion of the data [9–11]. Some indices focus on cluster separation, such as the Dunn index [12], which takes the ratio of the minimum inter-cluster distance to the maximum intra-cluster diameter to ensure worst-case separation. Other measures, like the Calinski–Harabasz criterion [13], compare between-cluster dispersion against within-cluster dispersion, favoring compact, well-separated groups. The Davies–Bouldin index [14] quantifies cluster similarity by averaging, for each cluster, the worst ratio of its scatter to its nearest neighbor’s separation and selects the clustering that minimizes this average. Among these, the Silhouette Coefficient stands out for its interpretability: it assigns each point a score in [−1, 1] that balances cohesion against separation. Aggregated as an overall metric or examined at the per-sample level, Silhouette offers both global validation and a diagnostic for potentially misassigned points, making it a versatile tool in practice [15]. Yet, despite its popularity, the Silhouette metric, like other internal indices, can be sensitive to dataset characteristics such as cluster shape, density variation, and especially cluster-size imbalance, which may distort aggregated scores and lead to suboptimal model selection [16, 17]; similar challenges also arise for unsupervised cluster-count selection procedures such as the Elbow method [18, 19] and the Gap Statistic [20].
Silhouette aggregation strategies Most implementations of the Silhouette score rely solely on micro-averaging [21], which aggregates the Silhouette values of all data points, effectively giving greater influence to larger clusters. While this approach is intuitive and widely used, it can introduce bias when cluster sizes are highly imbalanced. Macro-averaging, which first computes the mean Silhouette per cluster and then averages across clusters, has been proposed as an alternative to mitigate this effect [5]. However, macro-averaging can overemphasize small or under-represented clusters, reducing the influence of majority groups. These two aggregation strategies therefore reflect different perspectives on clustering quality, and neither is uniformly preferable across datasets. Sampling approaches and heuristics Sampling-based strategies have also been explored as a way to stabilize internal validation or reduce the computational burden of repeated clustering evaluation. Uniform subsampling can make large-scale validation more tractable, while repeated runs and averaging can reduce sensitivity to random initialization or sampling variability [22]. In the context of Silhouette-based evaluation, such approaches may partially alleviate the dominance of large clusters or improve robustness, but they do not by themselves resolve the underlying tension between micro- and macro-aggregation. More generally, heuristic combinations of validation criteria or averaging schemes have been considered, though such approaches often rely on fixed design choices or manually selected weights that may not adapt well to the structure of a given dataset [23].
4
Filling the gap Although a wide range of internal validation methods has been proposed, existing approaches do not directly address how micro- and macro-averaged Silhouette scores should be combined in a data-adaptive way for cluster-count selection. In particular, current methods typically rely on a single aggregation strategy, fixed averaging rules, or standalone internal indices, without exploiting how the discrepancy between micro- and macro-level evaluations evolves across repeated subsampled clusterings. This leaves a methodological gap in settings where cluster-size imbalance or heterogeneous structure makes either aggregation strategy alone insufficient. Our work addresses this gap by introducing a subsampling-based Composite Silhouette criterion that adaptively combines micro- and macro-averaged Silhouette scores at the subsample level through a discrepancy-sensitive weighting mechanism. The resulting score provides a principled and practical approach to internal cluster-count selection without requiring prior assumptions about which aggregation perspective is more appropriate.
3 Methodology In this section, we formalize Composite Silhouette, denoted by SmM , and introduce the notation used throughout the method. The proposed formulation evaluates clustering quality through repeated subsampled clusterings, allowing the relationship between micro- and macro-averaged Silhouette to be assessed across multiple views of the data rather than through a single partition. The resulting construction yields an adaptive composite criterion that captures the relative behavior of the two aggregation strategies while producing a single score for cluster-count selection.
3.1 Setup and Notation Let X = {xi }i∈I ⊂ Rd be a dataset, where I = {1, 2, . . . , N } indexes the N observations. Our goal is to evaluate candidate numbers of clusters by examining how clustering quality behaves across repeated subsampled views of the data, rather than relying on a single partition of the full dataset. To this end, let K ⊂ N>1 denote the set of candidate cluster counts, and fix k ∈ K. We also fix a subsampling fraction ϕ ∈ (0, 1], define the subsample size as m = ⌊ϕN ⌋, and let B ∈ N denote the number of subsamples. For each b ∈ {1, . . . , B}, we draw independently a subset Ib ⊂ I of size m, uniformly at random without replacement from I , and define the subsample by:
X (b) = {xi ∈ X : i ∈ Ib } ⊂ X .
(1)
These subsamples provide multiple partial views of the dataset, allowing us to study how internal validation behaves under repeated perturbations of the data. Let F (· ; k ) denote a clustering algorithm that, given a dataset and a candidate number of clusters k , returns a partition into k distinct (non-empty) clusters. Applied to the subsample X (b) , it yields the partition: (b)
(b)
F (X (b) ; k ) = {C1 , . . . , Ck },
5
(2)
(b)
where {Cr }kr=1 are the clusters obtained on the b-th subsample. In this way, each candidate k is associated with B subsampled clusterings, which provide repeated local views of the structure induced at that value of k .
3.2 Subsample Silhouette Scores For a fixed number of clusters k ∈ K and a fixed subsample X (b) , we now define the Silhouette quantities associated with the partition F (X (b) ; k ). For each observation (b) xi ∈ X (b) , let Ci denote the cluster to which xi is assigned. The Silhouette value of xi is based on two quantities: its average dissimilarity to the points in its own cluster (b) (b) ai = ai (k ), and its average dissimilarity to the nearest competing cluster bi = bi (k ):
ai =
1
X
(b) |Ci | − 1 (b) xj ∈C
∥xi − xj ∥,
bi = min
(b) ℓ̸=ci
i
1
X
(b) |Cℓ | (b) xj ∈C
∥xi − xj ∥
(3)
ℓ
j̸=i
Here, ai measures how well xi is embedded within its assigned cluster, while bi measures its average dissimilarity to the closest alternative cluster. Smaller values of ai indicate stronger within-cluster cohesion, whereas larger values of bi indicate stronger separation from neighboring clusters. Using these two quantities, the Silhouette score of xi , si = si (k ), on the b-th subsample is given by: (b)
si
=
bi − ai ∈ [−1, 1]. max{ai , bi }
(4)
A value close to 1 indicates that the observation is well matched to its assigned cluster and well separated from competing clusters, a value near 0 indicates ambiguity, and a negative value suggests that the observation may fit better in another cluster. We (b) next aggregate these per-instance values in two different ways: micro-averaged (Sm ) (b) and macro-averaged (SM ) Silhouette scores: (b) = Sm
1 X (b) si , m
(b)
SM =
i∈Ib
k X (b) 1X 1 si . (b) k r=1 |Cr | (b)
(5)
xi ∈Cr
These correspond to two complementary ways of evaluating clustering quality on the same subsample. The micro-averaged score (Sm ∈ [−1, 1]) assigns equal weight to all observations and is therefore more strongly influenced by the structure of larger clusters. In contrast, the macro-averaged score (SM ∈ [−1, 1]) first averages within clusters and then across clusters, so that each cluster contributes equally regardless of its size. As a result, it is more sensitive to the quality of smaller groups. These scores form the components of our composite criterion. In the next subsection, we compare these subsample-level quantities and use their relationship to define the weighting scheme underlying Composite Silhouette.
6
3.3 Subsample-Level Discrepancy and Weighting Scheme (b)
(b)
For a fixed candidate number of clusters k , Sm and SM may evaluate the same subsampled clustering differently. We quantify this difference on the b-th subsampled clustering through the discrepancy: (b)
(b) ∆b = Sm − SM .
(6)
When ∆b > 0, micro-averaging assigns a higher score than macro-averaging, indicating that the clustering quality on that subsample is reflected to a greater extent by the observation-level, global view. Conversely, when ∆b < 0, macro-averaging assigns the higher score, indicating that the evaluation is better represented by the cluster-level view. Thus, ∆b captures both the direction and the magnitude of the disagreement between the two aggregation strategies. This discrepancy is not meant to declare one aggregation inherently correct. Rather, it serves as a local signal of how the clustering structure revealed by a given subsample is reflected by the two Silhouette aggregations. Instead of imposing a fixed preference for either perspective, we use this local disagreement to balance micro- and macro-averaging adaptively within each subsampled clustering. Since the magnitude of ∆b may vary across b ∈ {1, . . . , B}, we normalize it relative to the largest absolute discrepancy observed ∆max = max1≤b≤B |∆b |:
eb = ∆
∆b ∈ (−1, 1), ∆max + ε
ε > 0 small for numerical stability.
(7)
This ensures that the difference is interpreted relative to the range of disagreement observed across the current collection of subsampled clusterings, rather than through its raw scale. To obtain a smooth and stable transformation of the normalized e b through the hyperbolic tangent function: difference, we pass ∆
e b ). zb = tanh(∆
(8)
eb This transformation is monotone and nearly linear around zero, so small values of ∆ are preserved almost proportionally, whereas larger ones are gradually compressed. Its smoothness, symmetry, and gradual saturation make tanh(·), a natural choice for “encoding” local micro–macro disagreement in a stable and interpretable way (see Appendix B Table B1 for an ablation over alternative transformations, including linear, nonlinear, and hard-threshold mappings). (b) (b) For each subsample b ∈ {1, . . . , B}, we use zb to combine Sm and SM in a way that reflects their relative behavior on that subsample; we map zb ∈ (−1, 1) to (0, 1) and (b) define the subsample-specific convex weight assigned to Sm as: wb =
1 + zb ∈ (0, 1), 2
(b)
(9)
so that the weight assigned to SM is 1 − wb . By construction the weighting remains centered around 12 . In particular, when ∆b > 0, we have wb > 12 , so the combination 7
places greater emphasis on micro-averaging; when ∆b < 0, then wb < 12 , so the emphasis shifts toward macro-averaging. If ∆b ≈ 0 ⇒ wb ≈ 21 , meaning the two strategies are weighted equally. Thus, the sign of ∆b determines which aggregation is favored on a given subsample, while its transformed magnitude determines how strongly that preference is expressed. This yields a subsample-specific balancing mechanism between the two Silhouette aggregations, favoring the strategy that is better supported on each subsampled clustering while still accounting for the other in proportion to the (b) (b) magnitude of their discrepancy, namely wb Sm + (1 − wb )SM .
3.4 Composite Silhouette For a fixed candidate number of clusters k , the Composite Silhouette score is obtained by averaging the B subsample convex combinations induced by the weights wb (Eq. 9):
SmM =
B i 1 Xh (b) (b) wb Sm + (1 − wb )SM B
(10)
b=1
This yields a single criterion that summarizes clustering quality across repeated subsampled views of the data while preserving how the relative support for micro- and macro-averaging varies from one subsample to another (Fig. 2).
Sm − SM Differences
Subsamples
Dataset
X (1)
clustering (1)
(1)
Weights
f
w1
∆1
Composite Silhouette
Sm , S M
..
X
X (B)
clustering (B) (B) Sm , S M
.. f
wB
∆B
X
(b)
(b)
wb Sm + (1 − wb )SM
b
where f : ∆b 7→ 1+tanh(∆2 b /∆max )
Fig. 2: Overview of the SmM evaluation for a given number of clusters k . Properties (b)
(b)
(b)
For convenience, let SmM := wb Sm + (1 − wb )SM denote the composite score on (b) (b) the b-th subsample. Since wb ∈ (0, 1), each SmM is a convex combination of Sm and (b) (b) (b) (b) (b) (b) SM , and therefore satisfies min{Sm , SM } ≤ SmM ≤ max{Sm , SM }. Substituting
8
(b)
(b)
b wb = 1+z and ∆b = Sm − SM gives (see detailed analysis in Appendix A.1): 2
(b) (b) (b) (b) Sm + SM Sm + SM ∆b z b ∆b (b) + = + tanh SmM = 2
2
2
2
∆b ∆max + ε
.
(11)
Thus, each subsample-level composite starts from the midpoint of the micro- and macro-averaged Silhouette scores and is then pulled toward the larger one by an amount controlled by the transformed difference. Averaging over the B subsamples: B
B
b=1
b=1
1 X 1 X (b) (b) (b) (b) min{Sm , SM } ≤ SmM ≤ max{Sm , SM } ⇒ SmM ∈ [−1, 1]. B B (b)
Notably, although each SmM lies between its corresponding micro- and macro-averaged components, the final score SmM need not lie between the sample-averaged quantities B
B
1 X (b) Sm = Sm , B
1 X (b) SM = SM , B
b=1
(12)
b=1
since our proposed formulation averages subsample-specific convex combinations rather than applying a single global convex combination to S m and S M (illustrated (b) (b) b (Eq. 9) and ∆b = Sm − SM in Appendix Figs. C1–C6). Indeed, using wb = 1+z 2 (Eq. 6), we obtain (detailed analysis in Appendix A.2): B
Sm + SM 1 X SmM = + ∆b zb . 2 2B
(13)
b=1
Thus, SmM is the midpoint of S m and S M plus a discrepancy-dependent correction term, rather than a single convex combination of the two sample-averaged scores.
Cluster count selection with SmM Evaluating SmM over the candidate set K, allows us to select the number of clusters as the value of k that maximizes the Composite Silhouette score:1 k ⋆ = arg max SmM (k ). k∈K
(14)
Complexity Let TF (m, d, k ) denote the cost of applying the clustering algorithm F (·; k ) to a subsample of size m in dimension d. For a fixed candidate number of clusters k , clustering across the B subsamples costs O(B TF (m, d, k )), while computing the corresponding subsample-level micro- and macro-averaged Silhouette scores costs O(B m2 d). The 1 A more conservative alternative (supported by our implementation) is to select k by maximizing a lower confidence bound (LCB) of SmM (k), thus favoring candidates with both high score and low subsampling variability.
9
remaining operations specific to SmM —namely the computation of differences, transformations, weights, and the final averaging—are linear in B and therefore negligible. Hence, for a fixed k , the overall complexity is O B TF (m, d, k ) + B m2 d . In the case of k -means: TF (m, d, k ) = O(kmd), yielding O(Bkmd + Bm2 d). Thus, SmM preserves the dominant computational profile of repeated subsampled Silhouette evaluation while adding only negligible discrepancy-aware overhead.
4 Theoretical Analysis We briefly summarize the main probabilistic guarantee underlying Composite Silhouette; full statements, extensions, and proofs are deferred in Appendix A. For the analysis, we consider the candidate set K and assume that the subsamples are drawn independently according to the sampling scheme, while any randomness of the clustering algorithm is also independent across trials and independent of the subsampling. In our method, the normalizing quantity ∆max = ∆max (k ) is computed from the same subsamples used to form SmM , which induces dependence across the resulting terms. To obtain concentration bounds with standard tools, we therefore analyze a closely related version in which ∆max is estimated from an independent set of subsamples and then used to form the final score. This preserves the form of the method while ensuring that the per-subsample composite scores used in the analysis are independent and identically distributed. In practice, this distinction is mainly technical: the independent estimation of ∆max is introduced to obtain clean concentration bounds, while the empirical behavior remains very similar to that of the implemented version for moderate to large values of B . Under this setup, each subsample com(b) (b) posite wb Sm + (1 − wb )SM lies in [−1, 1], so Hoeffding’s inequality applies directly. In particular, when the candidate set K is q finite, for any δ ∈ (0, 1), the estimate h i (b) supk∈K SmM (k ) − E SmM (k ) | ∆max (k ) ≤ 2 ln(2|K|/δ) holds with conditional probB ability at least 1 − δ (proof in Appendix A.4). Thus, the entire curve k 7→ SmM (k ) is uniformly estimated at rate O(B −1/2 ), so the relative ordering of candidate cluster counts is increasingly stable as the number of subsamples grows. The corresponding fixed-k concentration bound is given in Appendix A.3, while Appendix A.5 shows that, under a standard positive-margin condition on the subsampling objective (i.e., the optimal candidate is separated from all others by a strictly positive gap in the subsampling expectation), the probability of selecting the optimal candidate approaches one as B increases. Together, these results show that increasing the number of subsamples improves both the accuracy of the estimated Composite Silhouette curve and the reliability of the resulting choice of k ⋆ .
5 Empirical Validation 5.1 Synthetic and Real-World Datasets We evaluate Composite Silhouette on four synthetic datasets and twelve real-world datasets spanning balanced and imbalanced cluster structures, heterogeneous cluster scales, tabular data, image representations, and text embeddings. 10
The synthetic datasets (S1–S4, visualization in Fig. 3) are designed to probe different structural regimes, from clean and well-separated clusters to strongly imbalanced and heterogeneous mixtures: S1 consists of 10,000 samples generated from 5 Gaussian clusters with standard deviation 0.5. This dataset provides a clean and nearly balanced benchmark with sharply separated groups, for which we expect both aggregation strategies to perform well (Eq. 5). S2 consists of 10,000 samples generated from 6 Gaussian clusters with standard deviation 0.9. Relative to S1, the clusters are less sharply separated, yielding a balanced but more diffuse setting in which micro-averaging is expected to provide the stronger signal. S3 contains 2,300 samples arranged in 5 clusters with pronounced size and scale imbalance: two large clusters of 1,000 samples each and three small clusters of 100 samples each. The two large clusters are placed relatively close to one another and have larger spread (σ = 1.8), whereas the three small clusters are more compact (σ = 0.5). This dataset is intended to highlight the tension between observation-level and cluster-level aggregation under imbalance, and we expect macro-averaging to be more informative in this setting. S4 contains 4,090 samples distributed over 12 clusters with multiple size regimes: two large clusters (1,500 samples each), two medium clusters (300 each), five small clusters (80 each), and three tiny clusters (30 each). The cluster spreads vary across groups (σ ∈ {2.2, 1.2, 0.9, 0.6}), producing a challenging setting with substantial heterogeneity in both scale and cluster size, in which we do not expect either micro- or macro-averaging alone to perform consistently well. The real-world datasets include binary and multiclass data from tabular, vision, and text domains:2 Parkinsons (Pks) contains 195 voice recordings described by 22 features and forms 2 classes. Wine (Wne) contains 178 wine samples with 13 chemical attributes and 3 classes. Blood Transfusion (Bld) contains 748 donor records with 4 numerical features and 2 classes. Digits (Dgt) contains 1,797 handwritten digit images with 64 features and 10 classes. BBC News (Bbc) contains 2,225 news articles across 5 topics; documents are embedded with all-MiniLM-L6-v2 [24] and reduced to 50 dimensions by PCA. HTRU2 (Htr) contains 17,898 astrophysical signal instances described by 8 features and 2 classes, with strong class imbalance. STL-10 (Stl) contains 5,000 natural images from 10 classes; images are represented by pretrained ResNet-18 embeddings of dimension 512. 20 Newsgroups (Nsg) contains 11,314 training documents from 20 topic categories; we use TF–IDF representations, reduced to 100 dimensions via truncated SVD. Spambase (Spm) contains 4,601 email instances represented by 57 numerical features and 2 classes. Minds14 (Mds) contains 2,797 utterances from 14 intent classes; utterances are embedded with all-MiniLM-L6-v2, and reduced to 100 dimensions by PCA, and ℓ2 -normalized. Bank Marketing (Bnk) contains 45,211 customer records with 7 features and 2 classes. Banking77 (B77) contains 13,083 utterances from 77 intent classes; utterances are embedded with all-MiniLM-L6-v2, reduced to 50 dimensions by PCA, and ℓ2 -normalized. For tabular datasets, numerical features were standardized before clustering. 2
All real datasets are available via scikit-learn, OpenML, UCI, and Hugging Face Datasets.
11
(a) S1
(b) S2
(c) S3
(d) S4
Fig. 3: Synthetic datasets (S1-S4), colored by ground-truth cluster labels.
5.2 Experiments We compare SmM (Eq. 10) against a broad set of internal validation baselines under a common k -means evaluation protocol. The comparison includes subsample-averaged micro- and macro-averaged Silhouette scores S m , S M (Eq. 12), computed on exactly the same subsamples used by SmM , as well as repeated full-data averages of microand macro-averaged Silhouette (avg Sm , avg SM ), Calinski–Harabasz (avg CH), and Davies–Bouldin (avg DB), where the number of repeated runs matches the number of subsamples used by SmM . Here, “full-data average” refers to averaging the corresponding index across repeated k -means runs on the full dataset under different random initializations. For completeness, we also report the number of clusters selected by the mean Elbow criterion (avg EL) and by the Gap statistic (GAPs). For each dataset, we evaluate methods over a candidate set of cluster counts centered at the groundtruth value, namely K = {kGT − 5, . . . , kGT + 5}. When kGT < 5, we instead use K = {2, . . . , kGT + 5}, ensuring that the search range always begins at 2. For each score-based method, we report the selected number of clusters (Table 1) and the value attained at the ground-truth number of clusters kGT (§5.1, Appendix C; Table C2). 12
Trend figures over candidate values of k for SmM , S m , and S M , together with the corresponding results obtained using GMM, and Bisecting k -means are provided in Appendix C) (Figs C1–C6, Tables C3–C4).
SmM parameters Across all experiments, we use B = 20 − 30 subsamples and the subsample size is selected automatically from the dataset size N and the largest candidate number of clusters kmax . Specifically, the subsample size is chosen as the larger of two quantities: a fraction (ϕ) of the dataset size, and a minimum size of 30 observations per candidate cluster at kmax . The fraction is set to 80% of the data for datasets with at most 2,000 samples, 60% for datasets with between 2,001 and 20,000 samples, and 40% for larger datasets. The resulting value is then capped at the full dataset size. In this way, the rule preserves sufficient cluster representation for large candidate values of k while keeping the computational cost manageable on larger datasets. Table 1: Selected number of clusters obtained via SmM , S m , S M , avg Sm , avg SM , avg CH, avg DB, avg EL, and GAPs under the k -means protocol (values at kGT are reported in Appendix C, Table C2). All score-based criteria select k by maximizing their respective scores, except avg DB, which is minimized. Bold entries indicate that the selected k matches the ground-truth kGT . Dataset SmM S m S M avg Sm avg SM avg CH avg DB avg EL GAPs S1 S2 S3 S4
5 6 5 12
5 6 2 8
5 3 5 13
5 6 2 9
5 3 5 9
5 6 10 16
5 6 5 9
5 3 5 9
5 6 3 14
Pks Wne Bld Dgt Bbc Htr Stl Nsg Spm Mds Bnk B77
2 3 2 10 5 2 10 20 2 14 2 77
2 3 2 10 6 2 10 24 2 15 2 82
2 3 6 10 5 2 10 21 2 12 2 77
2 3 2 10 5 2 6 23 2 15 2 81
2 3 6 9 5 2 6 24 2 14 2 77
3 3 6 3 2 4 6 24 3 14 8 72
2 3 4 9 7 3 10 24 2 14 8 81
3 3 4 3 5 4 8 21 3 14 8 81
7 3 5 10 9 7 14 24 3 16 2 75
To examine how the Composite Silhouette score stabilizes as the number of subsamples B increases, we study its approximation error as a function of B at the ground-truth number of clusters kGT . For each dataset, we first compute a reference estimate using Bmax =200 subsamples under the same automatic subsample-size rule described above. We then treat this Bmax estimate as a high-precision proxy and, for each smaller value B ∈ {10, 20, . . . , 200}, approximate it by recomputing SmM from only B subsamples drawn without replacement from the full pool of 200. This subsampling of subsamples is repeated 25 times for each value of B , producing a distribution of absolute errors 13
relative to the Bmax estimate. Figure 4 summarizes how this error decreases as the number of subsamples grows, shown separately for synthetic and real-world datasets.
Fig. 4: Approximation error of SmM as a function of the number of subsamples B (left: synthetic datasets, right: real-world datasets). Curves: gray: per-dataset median absolute error, blue: across-dataset median, shaded band: ± 21 IQR. Finally, to complement our complexity analysis (§3.4), we examine how the runtime of SmM scales with dataset size. We generate synthetic Gaussian data with fixed cluster structure (k = 5, d = 10), and increasing sample size N (from 1, 000 to 500, 000), and compare a single-k evaluation of SmM (using B = 20) with the standard (scikit-learn) Silhouette score computed on the full dataset.
Fig. 5: Runtime as a function of the number of samples N for a single-k evaluation of SmM and for the standard Silhouette score computed on the full dataset.
14
5.3 Results Table 1 shows that SmM (Eqs. 10,14) recovers the ground-truth number of clusters on all sixteen datasets considered (§5.1), making it the only criterion in our comparison to do so consistently. This holds across balanced synthetic data (S1, S2), strongly imbalanced and heterogeneous synthetic settings (S3, S4), tabular datasets, image embeddings, and text representations. Importantly, whenever one of the two subsample-averaged Silhouette views (Eq. 12) provides the stronger signal, SmM follows it without requiring prior knowledge of whether micro- or macro-averaging should be preferred (Table 1, Appendix C); see, for example, S1, where both S m , S M identify the ground-truth number of clusters, S2, where the micro view is more informative, and S3 and B77, where the macro view is more informative (Table 1, Appendix C; Table C2, Figs. C1–C6). At the same time, SmM remains effective in more ambiguous cases where neither view alone identifies kGT , such as S4, Nsg, and Mds. This behavior also extends beyond k -means, as shown by the corresponding GMM, Bisecting k -means in Appendix C (Tables C3–C4). These findings directly support our motivating question: SmM is able to combine the strengths of micro- and macro-averaged Silhouette for cluster-count selection without assuming in advance which aggregation strategy is preferable. This remains the case even in settings where neither view alone aligns with the ground truth, suggesting that the composite captures a more informative signal than either aggregation strategy on its own. A second observation is that the subsample-averaged baselines S m and S M are generally more reliable than the corresponding averages across repeated full-data runs, which supports the use of repeated subsampled views rather than repeated random initializations alone. The automatic subsample-size rule (§5.2) is sufficient across all datasets and does not require dataset-specific tuning. Figure 4 further shows that the approximation error of SmM decreases rapidly with the number of subsamples: the across-dataset median error is already below 0.01 at B = 10 for both synthetic and real data, while even the most difficult real datasets remain within roughly 0.05 and improve steadily as B increases. Thus, moderate values such as B = 20–30 are adequate in practice. Table B1 in Appendix B additionally shows that the tanh transformation yields the most reliable SmM ground-truth recovery among the tested zb transformations (§3.3; Eq. 8). Finally, Fig. 5 shows that SmM remains computationally competitive: despite including repeated subsampling, clustering, and aggregation, its runtime stays competitive with the full-data Silhouette baseline and the advantage becomes more pronounced as the dataset size grows.
6 Conclusion We introduced Composite Silhouette (SmM ), a discrepancy-aware internal validation criterion that combines micro- and macro-averaged Silhouette scores through repeated subsampled clusterings. By using subsample-specific convex weights derived from the local disagreement between the two aggregation views, SmM adaptively favors the more informative perspective without discarding the other. At the same time, the method remains computationally practical, with modest additional overhead beyond repeated
15
subsampled Silhouette evaluation and natural compatibility with parallel computation. Empirical results show that SmM identifies the correct number of clusters more reliably than either subsample-averaged micro- or macro-averaged Silhouette alone, as well as standard internal baselines, across balanced, imbalanced, and structurally heterogeneous settings. These findings indicate that combining the two Silhouette views locally, rather than committing to one of them globally, yields a more robust basis for cluster-count selection. A natural direction for future work is a more systematic study of the regimes in which the composite remains informative even when both component views are individually misleading, in order to better characterize the structural conditions that favor discrepancy-aware aggregation. Overall, SmM provides a practical and broadly applicable framework for cluster-count selection that is adaptive and effective across diverse data domains.
Declarations • Funding. This work was supported by the Archimedes Research Unit, Athena Research Center, through the project “ARCHIMEDES Unit: Research in Artificial Intelligence, Data Science, and Algorithms”, implemented within the framework of the National Recovery and Resilience Plan “Greece 2.0” and funded by the European Union – NextGenerationEU. • Disclosure of Interests. The authors declare that they have no competing interests.
References [1] Jain, A.K., Murty, M.N., Flynn, P.J.: Data clustering: a review. ACM computing surveys (CSUR) 31(3), 264–323 (1999) [2] Rousseeuw, P.J.: Silhouettes: a graphical aid to the interpretation and validation of cluster analysis. Journal of computational and applied mathematics 20, 53–65 (1987) [3] Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., Duchesnay, É.: Scikit-learn: Machine learning in python. Journal of Machine Learning Research 12, 2825–2830 (2011) [4] Batool, F., Hennig, C.: Clustering with the average silhouette width. Computational Statistics & Data Analysis 158, 107190 (2021) [5] Pavlopoulos, J., Vardakas, G., Likas, A.: Revisiting silhouette aggregation. In: Pedreschi, D., Monreale, A., Guidotti, R., Pellungrini, R., Naretto, F. (eds.) Discovery Science, pp. 354–368. Springer, Cham (2025) [6] Wang, Y., Zhao, Y., Therneau, T., Atkinson, E., P. Tafti, A., Zhang, N., Amin, S., Limper, A., Khosla, S., Liu, H.: Unsupervised machine learning for the discovery
16
of latent disease clusters and patient subgroups using electronic health records. Journal of Biomedical Informatics 102, 103364 (2019) [7] John, J., Shobayo, O., Ogunleye, B.: An exploration of clustering algorithms for customer segmentation in the uk retail market. Analytics 2, 809–823 (2023) [8] Yuan, M., Zobel, J., Lin, P.: Measurement of clustering effectiveness for document collections. Information Retrieval Journal 25, 239–268 (2022) [9] Halkidi, M., Batistakis, Y., Vazirgiannis, M.: Cluster validity methods: Part i. SIGMOD Record 31 (2002) [10] Halkidi, M., Batistakis, Y., Vazirgiannis, M.: Clustering validity checking methods: Part ii. ACM SIGMOD Record 31 (2002) [11] Arbelaitz, O., Gurrutxaga, I., Muguerza, J., Pérez, J.M., Perona, I.: An extensive comparative study of cluster validity indices. Pattern Recognit. 46, 243–256 (2013) [12] Dunn, J.C.: A fuzzy relative of the isodata process and its use in detecting compact well-separated clusters. Journal of Cybernetics 3(3), 32–57 (1973) [13] Caliński, T., Harabasz, J.: A dendrite method for cluster analysis. Communications in Statistics-theory and Methods 3(1), 1–27 (1974) [14] Davies, D.L., Bouldin, D.W.: A cluster separation measure. IEEE transactions on pattern analysis and machine intelligence (2), 224–227 (1979) [15] Dudek, A.: Silhouette index as clustering evaluation tool. In: Classification and Data Analysis: Theory and Applications 28, pp. 19–33 (2020). Springer [16] Vendramin, L., Campello, R.J.G.B., Hruschka, E.R.: Relative clustering validity criteria: A comparative overview. Statistical Analysis and Data Mining: The ASA Data Science Journal 3 (2010) [17] Hassan, B.A., Tayfor, N., Hassan, A.A., Ahmed, A.M., Hamad, R.K., Abdalla, N.N.: From a-to-z review of clustering validation indices. ArXiv abs/2407.20246 (2024) [18] Thorndike, R.L.: Who belongs in the family? Psychometrika 18(4), 267–276 (1953) [19] Shi, C., Wei, B., Wei, S., Wang, W., Liu, H., Liu, J.: A quantitative discriminant method of elbow point for the optimal number of clusters in clustering algorithm. EURASIP Journal on Wireless Communications and Networking 2021 (2020) [20] Tibshirani, R., Walther, G., Hastie, T.: Estimating the number of clusters in a data set via the gap statistic. Journal of the Royal Statistical Society: Series B 17
(Statistical Methodology) 63 (2001) [21] Shahapure, K.R., Nicholas, C.: Cluster quality analysis using silhouette score. In: 2020 IEEE 7th International Conference on Data Science and Advanced Analytics (DSAA), pp. 747–748 (2020). IEEE [22] Lange, T., Roth, V., Braun, M.L., Buhmann, J.M.: Stability-based validation of clustering solutions. Neural Computation 16, 1299–1323 (2004) [23] Liu, Y., Li, Z., Xiong, H., Gao, X., Wu, J.: Understanding of internal clustering validation measures. In: 2010 IEEE International Conference on Data Mining, pp. 911–916 (2010). IEEE [24] Reimers, N., Gurevych, I.: Sentence-BERT: Sentence embeddings using Siamese BERT-networks. In: Inui, K., Jiang, J., Ng, V., Wan, X. (eds.) Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLPIJCNLP), pp. 3982–3992. Association for Computational Linguistics, Hong Kong, China (2019)
18
Appendix A A.1
Extended Theoretical Analysis
Property 1 (b) (b) (b) (b) Sm + SM Sm + SM ∆b z b ∆b (b) SmM = + = + tanh 2
2
2
2
∆b ∆max + ε
.
Proof. Starting from the definition of the subsample-specific composite score, (b)
(b)
(b) + (1 − wb )SM . SmM = wb Sm
Rewriting, (b)
(b)
(b) SmM = wb Sm − SM (b)
(b)
+ SM .
(b)
b Using ∆b = Sm − SM and wb = 1+z 2 , we obtain
(b)
SmM = (b)
1 + zb ∆b ∆b zb (b) (b) ∆b + S M = + + SM . 2 2 2
(b)
Since ∆b = Sm − SM , (b)
(b)
(b)
(b)
Sm − SM Sm + SM ∆b (b) (b) + SM = + SM = . 2 2 2 Therefore, (b)
(b)
Sm + SM ∆b zb + . 2 2 ∆b zb = tanh ∆max + ε
(b)
SmM = Finally, substituting
yields
(b) (b) Sm + SM ∆b (b) + tanh SmM = 2
2
∆b ∆max + ε
. □
A.2
Property 2 B
SmM =
Sm + SM 1 X + ∆b zb . 2 2B b=1
Proof. Starting from the definition of the Composite Silhouette score, B
SmM =
i 1 Xh (b) (b) wb Sm + (1 − wb )SM . B b=1
19
Using the subsample-level identity (b)
(b)
(b) wb Sm + (1 − wb )SM =
we obtain
(b)
Sm + SM ∆b z b + , 2 2
" # B (b) (b) 1 X Sm + SM ∆b zb SmM = + . B 2 2 b=1
Distributing the average gives
SmM =
B
B
b=1
b=1
1 X 1 X (b) (b) Sm + SM + ∆b z b . 2B 2B
By the definitions B
Sm =
B
1 X (b) Sm , B
SM =
b=1
1 X (b) SM , B b=1
the first term becomes B
S +S 1 X (b) m M (b) Sm + SM = . 2B 2 b=1
Therefore, B
SmM =
Sm + SM 1 X + ∆b z b . 2 2B b=1
□ Probabilistic setup. For the probabilistic results below, we consider a fixed candidate number of clusters k ∈ K. The subsamples are assumed to be drawn independently according to the sampling scheme, while any internal randomness of the clustering algorithm is also independent across trials and independent of the subsampling. Since, in our implemented method, the normalizing quantity ∆max (k ) is computed from the same subsamples used to form SmM (k ), the resulting terms are not independent. To obtain concentration bounds with standard tools, we therefore analyze a closely related version in which ∆max (k ) is estimated from an independent set of subsamples and then used to form the final score. This preserves the form of the method while ensuring that the per-subsample composite scores used in the analysis are independent and identically distributed. In practice, this modification is mainly technical. The quantity ∆max (k ) enters the method only through the normalization of the discrepancies, so it acts as a relative scale parameter rather than as a source of structural information on its own. Consequently, replacing the empirical ∆max (k ) computed from the same subsamples by an independent estimate does not alter the form of the weighting rule, but only its normalization. When B is moderate to large, both quantities are expected to provide similar scaling of the discrepancies, and therefore to induce similar normalized values, weights, and final composite scores. The two versions are thus introduced 20
to separate dependence for the sake of analysis, rather than because they represent different procedures.
A.3
Fixed-k concentration
Fix k ∈ K, and define
h i (b) µ(k ) = E SmM (k ) | ∆max (k ) . Then, for any t > 0,
Bt2 P(|SmM (k ) − µ(k )| ≥ t | ∆max (k )) ≤ 2 exp − 2
.
Equivalently, for any δ ∈ (0, 1), with conditional probability at least 1 − δ ,
r |SmM (k ) − µ(k )| ≤
2 ln(2/δ ) . B
Proof. Under our setup, the random variables (1)
(B)
SmM (k ), . . . , SmM (k ) are independent and identically distributed conditional on ∆max (k ). Each of them lies in [−1, 1]. Hoeffding’s inequality for bounded independent random variables therefore gives ! B Bt2 1 X (b) SmM (k ) − µ(k ) ≥ t ∆max (k ) ≤ 2 exp − , P B 2 b=1
which is exactly the desired bound since B
1 X (b) SmM (k ) = SmM (k ). B b=1
Solving
Bt2 2 exp − =δ 2 for t yields
r t=
2 ln(2/δ ) , B
□
which proves the claim.
21
A.4
Uniform concentration over the candidate set
Assume that the candidate set K is finite. Then, for any δ ∈ (0, 1),
r sup |SmM (k ) − µ(k )| ≤ k∈K
2 ln(2|K|/δ ) B
with conditional probability at least 1 − δ .
Proof. Fix t > 0. By the fixed-k concentration result above, for each k ∈ K, Bt2 P(|SmM (k ) − µ(k )| ≥ t | ∆max (k )) ≤ 2 exp − . 2 Applying the union bound over k ∈ K gives
Bt2 P(∃ k ∈ K : |SmM (k ) − µ(k )| ≥ t | ∆max (k )) ≤ 2|K| exp − . 2 Setting the right-hand side equal to δ and solving for t yields
r t=
2 ln(2|K|/δ ) , B
□
which proves the claim.
A.5
Recovery guarantee under a margin condition
Let
k † ∈ arg max µ(k ) k∈K
be an optimal candidate under the subsampling objective, and assume that this maximizer is unique with positive margin
γ := µ(k † ) −
max
k∈K, k̸=k†
µ(k ) > 0.
Let
k ⋆ ∈ arg max SmM (k ) k∈K
denote the maximizer of the empirical Composite Silhouette score. If
B≥
8 2|K| ln , γ2 δ
then
P k ⋆ = k † ∆max (k ) ≥ 1 − δ.
22
Proof. By A.2, with conditional probability at least 1 − δ , r sup |SmM (k ) − µ(k )| ≤ k∈K
2 ln(2|K|/δ ) . B
Suppose this event holds and let
r η :=
2 ln(2|K|/δ ) . B
Then
SmM (k † ) ≥ µ(k † ) − η, †
while for every k ̸= k ,
SmM (k ) ≤ µ(k ) + η ≤ µ(k † ) − γ + η. Hence, if η ≤ γ/2, then
SmM (k † ) ≥ µ(k † ) − η ≥ µ(k † ) − γ + η ≥ SmM (k ) for all k ̸= k † , so k † is the unique maximizer of SmM (k ). The condition η ≤ γ/2 is equivalent to r 2 ln(2|K|/δ ) γ ≤ , B 2 which in turn gives 2|K| 8 B ≥ 2 ln . γ δ Therefore, under this condition,
P k ⋆ = k † ∆max (k ) ≥ 1 − δ. □
Appendix B
Transformations Ablation
We examine the sensitivity of Composite Silhouette to the choice of transformae b before constructing the tion applied to the normalized micro–macro discrepancy ∆ subsample-specific weight, while keeping the remaining pipeline fixed (including subsampling, k -means clustering, and Silhouette computation). In the main method, we e b ) (Eq. 8), which yields the weight wb = (1 + zb )/2 (Eq. 9). To use zb = tanh(∆ assess whether this choice is important in practice, we compare the proposed tanh e b ; a sigmoid transformation against three alternatives: a linear mapping, zb = ∆ −1 e transformation, implemented as wb = (1 + exp(−α∆b )) with α = 1; and a stepbased transformation, which assigns full weight to the micro-averaged Silhouette when e b > 0 and full weight to the macro-averaged Silhouette otherwise. For each variant, ∆ 23
we recompute SmM and report the resulting selected number of clusters across the benchmark datasets. Table B1 shows that the proposed tanh transformation is the most stable and accurate choice overall. In particular, it recovers the correct number of clusters on all datasets reported, whereas the alternative transformations yield several under- and over-estimations. This empirical pattern supports the role of tanh as a principled compromise: unlike the linear mapping, it smoothly compresses large discrepancies and thus avoids excessive sensitivity to extreme values; unlike the step rule, it preserves gradual adjustments in the relative weighting between micro- and macro-averaged Silhouette scores. We note that a sigmoid transformation with α = 2 would be mathematically equivalent to the tanh weighting used in the main method, so in this ablation we use α = 1 to obtain a genuinely distinct smooth alternative.
Table B1: Estimated numbers of clusters via SmM using various zb transformations (original tanh, linear, sigmoid, step). Bold values indicate correct number of clusters selection, red values indicate suboptimal selection. SmM k selection with zb transformation Dataset
tanh
linear
sigmoid
step (sign)
S1 S2 S3 S4
5 6 5 12
5 3 5 13
5 6 5 12
5 3 5 13
Pks Wne Htr Dgt Bnk Nsg Spm Stl Bbc Bld Mds B77
2 3 2 10 2 20 2 10 5 2 14 77
2 3 2 8 2 20 2 10 5 3 14 72
3 4 2 10 2 20 2 10 5 2 14 77
2 3 2 10 2 21 2 8 6 2 15 77
24
Appendix C
Extended Empirical Validation
Table C2: Values attained at the ground-truth number of clusters kGT under the k means protocol. Higher values indicate better performance for SmM , S m , S M , avg Sm , avg SM , and avg CH, whereas lower values indicate better performance for avg DB. Dataset
SmM
Sm
S1 S2 S3 S4
0.8728 0.8727 0.8728 0.8728 0.8728 284172.5 0.1781 0.6924 0.6924 0.6923 0.6924 0.6924 62284.8 0.4289 0.6703 0.4767 0.7013 0.4851 0.7200 3879.3 0.4852 0.6114 0.4236 0.6448 0.4211 0.6540 7214.3 0.5013
Pks Wne Bld Dgt Bbc Htr Stl Nsg Spm Mds Bnk B77
0.4047 0.2875 0.4186 0.1848 0.1111 0.5874 0.0292 0.1996 0.4320 0.2689 0.2325 0.1720
0.4195 0.2835 0.4277 0.1800 0.1084 0.6128 0.0303 0.0853 0.4508 0.2680 0.2409 0.1674
SM
0.3221 0.2887 0.3681 0.1861 0.1114 0.4444 0.0244 0.2222 0.3658 0.2681 0.2091 0.1736
avg Sm avg SM
0.4273 0.2835 0.4315 0.1776 0.1081 0.6147 0.0303 0.0778 0.3760 0.2657 0.2980 0.1679
25
0.3287 0.2886 0.3689 0.1819 0.1109 0.4509 0.0225 0.2019 0.3084 0.2654 0.2314 0.1758
avg CH
99.7 70.6 429.4 165.0 160.9 9821.5 136.3 321.0 245.1 45.6 6315.7 281.4
avg DB
1.0917 1.3918 1.0225 1.9596 2.6293 0.9174 3.6423 1.8722 2.0751 1.7025 1.7660 1.9576
Table C3: Selected number of clusters obtained via SmM , S m , S M , avg Sm , avg SM , avg CH, and avg DB under the Bisecting k -means protocol. Bold entries indicate that the selected k matches the ground-truth kGT . Dataset SmM S m S M avg Sm avg SM avg CH avg DB
S1 S2 S3 S4
5 6 3 11
5 6 2 8
5 3 5 8
5 6 3 8
5 3 3 8
5 6 10 16
5 6 5 8
Pks Wne Bld Dgt Bbc Htr Stl Nsg Spm Mds Bnk B77
2 3 2 10 5 2 10 19 2 15 2 72
2 3 2 10 5 2 10 15 2 15 2 72
2 3 4 10 5 2 9 19 2 14 2 72
2 2 2 10 5 2 12 15 2 16 2 72
2 2 4 9 5 2 8 23 2 13 2 72
2 2 4 2 2 2 6 15 3 13 3 72
2 3 4 10 5 4 8 24 7 14 8 82
Table C4: Selected number of clusters obtained via SmM , S m , S M , avg Sm , avg SM , avg CH, and avg DB under the Gaussian mixture model protocol. Bold entries indicate that the selected k matches the ground-truth kGT . Dataset SmM S m S M avg Sm avg SM avg CH avg DB
S1 S2 S3 S4
5 6 3 11
5 6 3 8
5 3 3 9
5 6 3 9
5 3 5 9
5 6 10 16
5 6 5 9
Pks Wne Bld Dgt Bbc Htr Stl Nsg Spm Mds Bnk B77
2 3 2 10 5 2 10 24 2 14 2 77
2 3 2 10 6 2 10 24 2 15 2 82
2 3 2 10 5 2 10 24 2 12 2 77
2 3 5 10 5 2 6 24 2 15 2 81
2 3 2 9 5 2 6 24 2 14 2 77
3 3 5 6 2 3 6 24 2 14 2 72
2 3 2 10 7 3 10 24 2 14 2 81
26
(a) S1
(b) S2
(c) S3
Fig. C1: Trends of SmM , S m , and S M over the candidate numbers of clusters k . Stars (⋆) denote the optimal cluster count selected by each criterion. The dashed line denotes the ground-truth number of clusters. Datasets: S1, S2, and S3.
27
(a) S4
(b) Pks
(c) Wne
Fig. C2: Trends of SmM , S m , and S M over the candidate numbers of clusters k . Stars (⋆) denote the optimal cluster count selected by each criterion. The dashed line denotes the ground-truth number of clusters. Datasets: S4, Pks, and Wne.
28
(a) Bld
(b) Dig
(c) Bbc
Fig. C3: Trends of SmM , S m , and S M over the candidate numbers of clusters k . Stars (⋆) denote the optimal cluster count selected by each criterion. The dashed line denotes the ground-truth number of clusters. Datasets: Bld, Dig, and Bbc.
29
(a) Htr
(b) Stl
(c) Nsg
Fig. C4: Trends of SmM , S m , and S M over the candidate numbers of clusters k . Stars (⋆) denote the optimal cluster count selected by each criterion. The dashed line denotes the ground-truth number of clusters. Datasets: Htr, Stl, and Nsg.
30
(a) Spm
(b) Mds
(c) Bnk
Fig. C5: Trends of SmM , S m , and S M over the candidate numbers of clusters k . Stars (⋆) denote the optimal cluster count selected by each criterion. The dashed line denotes the ground-truth number of clusters. Datasets: Spm, Mds, and Bnk.
31
(a) B77
Fig. C6: Trends of SmM , S m , and S M over the candidate numbers of clusters k . Stars (⋆) denote the optimal cluster count selected by each criterion. The dashed line denotes the ground-truth number of clusters. Dataset: B77.
32