Composite Silhouette: A Subsampling-based Aggregation Strategy

Aggelos Semoglou; Aristidis Likas; John Pavlopoulos

cs.LGApr 15, 2026

Composite Silhouette: A Subsampling-based Aggregation Strategy

Authors: Aggelos Semoglou, Aristidis Likas, John Pavlopoulos

Organizations: Athens University of Economics and Business, Greece. · Archimedes, Athena Research Center, Greece. · University of Ioannina, Greece.

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. Macro-averaging 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.

Figures & tables

Panel of Figure 1 — Figure 1: Silhouette aggregation strategies: Global trends vs. local patterns.

Panel of Figure 2 — Figure 2: Overview of the $S_{\mathrm{mM}}$ evaluation for a given number of clusters $k$ .

Panel of Figure 3 — Figure 3: Synthetic datasets ( S1 - S4 ), colored by ground-truth cluster labels.

Dataset	$S_{\mathrm{mM}}$	$\overline{S}_{\mathrm{m}}$	$\overline{S}_{\mathrm{M}}$	avg $S_{\mathrm{m}}$	avg $S_{\mathrm{M}}$	avg CH	avg DB	avg EL	GAPs
S1	5	5	5	5	5	5	5	5	5
S2	6	6	3	6	3	6	6	3	6
S3	5	2	5	2	5	10	5	5	3
S4	12	8	13	9	9	16	9	9	14
Pks	2	2	2	2	2	3	2	3	7
Wne	3	3	3	3	3	3	3	3	3

Table 1: Selected number of clusters obtained via

S_{\mathrm{mM}}

\overline{S}_{\mathrm{m}}

\overline{S}_{\mathrm{M}}

, avg

S_{\mathrm{m}}

, avg

S_{\mathrm{M}}

, avg CH, avg DB, avg EL, and GAPs under the

k

-means protocol (values at

k_{\mathrm{GT}}

are reported in Appendix 9 , Table 3 ). 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

k_{\mathrm{GT}}

Figure 4: Approximation error of $S_{\mathrm{mM}}$ 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: $\pm\tfrac{1}{2}$ IQR.

Figure 5: Runtime as a function of the number of samples $N$ for a single- $k$ evaluation of $S_{\mathrm{mM}}$ and for the standard Silhouette score computed on the full dataset.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

	$S_{\mathrm{mM}}$ $k$ selection with $z_{b}$ transformation
Dataset	tanh	linear	sigmoid	step (sign)
S1	5	5	5	5
S2	6	3	6	3
S3	5	5	5	5
S4	12	13	12	13
Pks	2	2	3	2

Appendix

Table 2: Estimated numbers of clusters via

S_{\mathrm{mM}}

using various

z_{b}

transformations (original tanh, linear, sigmoid, step). Bold values indicate correct number of clusters selection, red values indicate suboptimal selection.

Dataset	$S_{\mathrm{mM}}$	$\overline{S}_{\mathrm{m}}$	$\overline{S}_{\mathrm{M}}$	avg $S_{\mathrm{m}}$	avg $S_{\mathrm{M}}$	avg CH	avg DB
S1	0.8728	0.8727	0.8728	0.8728	0.8728	284172.5	0.1781
S2	0.6924	0.6924	0.6923	0.6924	0.6924	62284.8	0.4289
S3	0.6703	0.4767	0.7013	0.4851	0.7200	3879.3	0.4852
S4	0.6114	0.4236	0.6448	0.4211	0.6540	7214.3	0.5013
Pks	0.4047	0.4195	0.3221	0.4273	0.3287	99.7	1.0917
Wne	0.2875	0.2835	0.2887	0.2835	0.2886	70.6	1.3918

Appendix

Table 3: Values attained at the ground-truth number of clusters

k_{\mathrm{GT}}

under the

k

-means protocol. Higher values indicate better performance for

S_{\mathrm{mM}}

\overline{S}_{\mathrm{m}}

\overline{S}_{\mathrm{M}}

, avg

S_{\mathrm{m}}

, avg

S_{\mathrm{M}}

, and avg CH, whereas lower values indicate better performance for avg DB.

Dataset	$S_{\mathrm{mM}}$	$\overline{S}_{\mathrm{m}}$	$\overline{S}_{\mathrm{M}}$	avg $S_{\mathrm{m}}$	avg $S_{\mathrm{M}}$	avg CH	avg DB
S1	5	5	5	5	5	5	5
S2	6	6	3	6	3	6	6
S3	3	2	5	3	3	10	5
S4	11	8	8	8	8	16	8
Pks	2	2	2	2	2	2	2
Wne	3	3	3	2	2	2	3

Appendix

Table 4: Selected number of clusters obtained via

S_{\mathrm{mM}}

\overline{S}_{\mathrm{m}}

\overline{S}_{\mathrm{M}}

, avg

S_{\mathrm{m}}

, avg

S_{\mathrm{M}}

, avg CH, and avg DB under the Bisecting

k

-means protocol. Bold entries indicate that the selected

k

matches the ground-truth

k_{\mathrm{GT}}

Dataset	$S_{\mathrm{mM}}$	$\overline{S}_{\mathrm{m}}$	$\overline{S}_{\mathrm{M}}$	avg $S_{\mathrm{m}}$	avg $S_{\mathrm{M}}$	avg CH	avg DB
S1	5	5	5	5	5	5	5
S2	6	6	3	6	3	6	6
S3	3	3	3	3	5	10	5
S4	11	8	9	9	9	16	9
Pks	2	2	2	2	2	3	2
Wne	3	3	3	3	3	3	3

Appendix

Table 5: Selected number of clusters obtained via

S_{\mathrm{mM}}

\overline{S}_{\mathrm{m}}

\overline{S}_{\mathrm{M}}

, avg

S_{\mathrm{m}}

, avg

S_{\mathrm{M}}

, avg CH, and avg DB under the Gaussian mixture model protocol. Bold entries indicate that the selected

k

matches the ground-truth

k_{\mathrm{GT}}

Panel of Figure 6 — Figure 6: Trends of $S_{\mathrm{mM}}$ , $\overline{S}_{\mathrm{m}}$ , and $\overline{S}_{\mathrm{M}}$ over the candidate numbers of clusters $k$ . Stars ( $\star$ ) denote the optimal cluster count selected by each criterion. The dashed line denotes the ground-truth number of clusters. Datasets: S1, S2, and S3.

Panel of Figure 7 — Figure 7: Trends of $S_{\mathrm{mM}}$ , $\overline{S}_{\mathrm{m}}$ , and $\overline{S}_{\mathrm{M}}$ over the candidate numbers of clusters $k$ . Stars ( $\star$ ) denote the optimal cluster count selected by each criterion. The dashed line denotes the ground-truth number of clusters. Datasets: S4, Pks , and Wne .

Panel of Figure 8 — Figure 8: Trends of $S_{\mathrm{mM}}$ , $\overline{S}_{\mathrm{m}}$ , and $\overline{S}_{\mathrm{M}}$ over the candidate numbers of clusters $k$ . Stars ( $\star$ ) denote the optimal cluster count selected by each criterion. The dashed line denotes the ground-truth number of clusters. Datasets: Bld , Dig , and Bbc .

Panel of Figure 9 — Figure 9: Trends of $S_{\mathrm{mM}}$ , $\overline{S}_{\mathrm{m}}$ , and $\overline{S}_{\mathrm{M}}$ over the candidate numbers of clusters $k$ . Stars ( $\star$ ) denote the optimal cluster count selected by each criterion. The dashed line denotes the ground-truth number of clusters. Datasets: Htr , Stl , and Nsg .

Panel of Figure 10 — Figure 10: Trends of $S_{\mathrm{mM}}$ , $\overline{S}_{\mathrm{m}}$ , and $\overline{S}_{\mathrm{M}}$ over the candidate numbers of clusters $k$ . Stars ( $\star$ ) denote the optimal cluster count selected by each criterion. The dashed line denotes the ground-truth number of clusters. Datasets: Spm , Mds , and Bnk .

Panel of Figure 11 — Figure 11: Trends of $S_{\mathrm{mM}}$ , $\overline{S}_{\mathrm{m}}$ , and $\overline{S}_{\mathrm{M}}$ over the candidate numbers of clusters $k$ . Stars ( $\star$ ) denote the optimal cluster count selected by each criterion. The dashed line denotes the ground-truth number of clusters. Dataset: B77 .

Cluster Number Estimation

See all 13 papers

Jul 2, 2026

Scalable and Distributed Silhouette Approximation

The silhouette is one of the most widely used measures to assess the quality of a

k

-clustering of a dataset of

n

elements. Its evaluation requires no information beyond the clustering assignment. In addition, the silhouette is extremely easy to interpret, providing a score to measure the quality of a clustering as a whole or for each element. The exact computation of the: (i) silhouette of each element of a dataset; and (ii) the global silhouette of the clustering; require

Θ(n^2)

distance calculations, under general metrics. The quadratic complexity

Θ(n^2)

is extremely prohibitive, especially on massive modern datasets. Surprisingly, existing approximate methods using

O(n^2)

distance calculations are heuristics not offering provable and controllable guarantees on the quality of their results. We introduce the first rigorous and efficient algorithms to estimate: (i) the (local) silhouette of each element of a dataset; and (ii) the (global) silhouette; of any metric

k

-clustering. Our methods, based on sampling, perform

O(nk\varepsilon^{-2}\ln (nk/δ))

distance computations, and provide estimates with additive error

O(\varepsilon)

with probability at least

1-δ

. That is, parameters

\varepsilon

and

δ

(0,1)

control the trade-off between accuracy and efficiency. We also introduce a scalable and distributed design of our methods for the MapReduce and Massively Parallel Computing (MPC) frameworks. Our distributed algorithms use a constant number of rounds and sublinear local memory. Finally, we perform extensive experiments against state-of-the-art approaches. The results show that our new techniques yield the best trade-off between accuracy and efficiency for both local and global silhouette estimation. In addition, our methods scale efficiently to massive datasets for which an exact computation of the silhouette is not practical.

Ilie Sarpe, Federico Altieri, Andrea Pietracaprina +2

KTH Royal Institute of Technology · University of Padova

Clustering

Ask PDF

Mar 3, 2026

The elbow statistic: Multiscale clustering statistical significance

Selecting the number of clusters remains a fundamental challenge in unsupervised learning. Existing approaches typically focus on identifying a single "optimal" partition, often overlooking statistically meaningful structure present across multiple resolutions. We introduce ElbowSig, a general inferential framework for assessing clustering structure over a range of resolutions. The method formalizes the elbow heuristic by defining a normalized discrete curvature statistic based on the sequence of within-cluster heterogeneity values, and evaluates its significance relative to a null distribution of unstructured data. This yields hypothesis tests across resolutions, enabling simultaneous inference at multiple clustering scales. We derive the asymptotic behavior of the null statistic in both large-sample and high-dimensional regimes, characterizing its limiting form and variability. Because it depends only on the heterogeneity sequence, ElbowSig is compatible with a wide range of clustering algorithms, including hard, fuzzy, and model-based methods. Experiments on synthetic and real datasets show that the procedure controls Type-I error under unstructured data while providing power to detect multiscale organization, revealing structure that is often missed by single-resolution selection criteria.

Francisco J. Perez-Reche

School of Natural and Computing Sciences, University of Aberdeen, Fraser Noble Building, AB24 3UE, United Kingdom

Cluster Number Estimation Clustering Statistical Hypothesis Testing

Ask PDF

Mar 24, 2026

The Mass Agreement Score: A Point-centric Measure of Cluster Size Consistency

In clustering, strong dominance in the size of a particular cluster is often undesirable, motivating a measure of cluster size uniformity that can be used to filter such partitions. A basic requirement of such a measure is stability: partitions that differ only slightly in their point assignments should receive similar uniformity scores. A difficulty arises because cluster labels are not fixed objects; algorithms may produce different numbers of labels even when the underlying point distribution changes very little. Measures defined directly over labels can therefore become unstable under label-count perturbations. I introduce the Mass Agreement Score (MAS), a point-centric metric bounded in [0, 1] that evaluates the consistency of expected cluster size as measured from the perspective of points in each cluster. Its construction yields fragment robustness by design, assigning similar scores to partitions with similar bulk structure while remaining sensitive to genuine redistribution of cluster mass.

Randolph Wiredu-Aidoo

Clustering

Ask PDF

Abstract

Cluster Number Estimation

Explore similar work

Scalable and Distributed Silhouette Approximation

The elbow statistic: Multiscale clustering statistical significance

The Mass Agreement Score: A Point-centric Measure of Cluster Size Consistency