CAKE: Confidence in Assignments via K-partition Ensembles

Aggelos Semoglou; John Pavlopoulos

cs.LGFeb 20, 2026

CAKE: Confidence in Assignments via K-partition Ensembles

Authors: Aggelos Semoglou, John Pavlopoulos

Organizations: Department of Informatics, Athens University of Economics and Business, Athens, Greece · Archimedes Research Unit, Athena Research Center, Athens, Greece

Abstract

Clustering is widely used for unsupervised structure discovery, yet it offers limited insight into how reliable each individual assignment is. Diagnostics, such as convergence behavior or objective values, may reflect global quality, but they do not indicate whether particular instances are assigned confidently, especially for initialization-sensitive algorithms like k-means. This assignment-level instability can undermine both accuracy and robustness. Ensemble approaches improve global consistency by aggregating multiple runs, but they typically lack tools for quantifying pointwise confidence in a way that combines cross-run agreement with geometric support from the learned cluster structure. This work introduces CAKE (Confidence in Assignments via K-partition Ensembles), a framework that evaluates each point using two complementary statistics computed over a clustering ensemble: assignment stability and consistency of local geometric fit. These are combined into a single, interpretable score in [0,1]. The theoretical analysis shows that CAKE remains effective under noise and separates stable from unstable points. Experiments on synthetic and real-world datasets indicate that CAKE effectively highlights ambiguous points and stable core members, providing a confidence ranking over instances that can be used for selection or prioritization in downstream clustering workflows.

Figures & tables

(a) Low $\rightarrow$ high $\mathrm{CAKE}$ scores.

(b) Bottom 1% $\rightarrow$ top 90% $\mathrm{CAKE}$ scores

Dataset	Subset	avg ARI	avg AMI	avg ACC
S1	Full	0.879 [0.8785, 0.8791]	0.833 [0.8331, 0.8338]	0.958 [0.9578, 0.9580]
	Random	0.879 [0.8790, 0.8790]	0.834 [0.8339, 0.8339]	0.958 [0.9579, 0.9579]
	Consensus	0.884 [0.8842, 0.8842]	0.839 [0.8394, 0.8394]	0.960 [0.9596, 0.9596]
	$C$ component	0.884 [0.8842, 0.8842]	0.839 [0.8394, 0.8394]	0.960 [0.9596, 0.9596]
	$\tilde{S}$ component	0.992 [0.9921, 0.9921]	0.983 [0.9827, 0.9827]	0.997 [0.9971, 0.9971]
	$\mathrm{CAKE}^{\text{(PR)}}$	0.992 [0.9921, 0.9921]	0.983 [0.9827, 0.9827]	0.997 [0.9971, 0.9971]

Table 2: ARI, AMI, ACC (clustering accuracy) averages and

t

-95% confidence intervals, computed over multiple independent clustering runs with varying random seeds. Results are reported for the full datasets (Full) and their filtered subsets mentioned in § 5.2 . Highest values in bold .

(a) Coverage–accuracy on synthetic datasets: S1 , S2 , S3 , S4 , S5 , S6 , S7 .

(b) Coverage–accuracy on real datasets: Ir , Bc , Dg , Ng , Fm , Pd , Lt , Sa .

(b) Runtime (s) vs. $n$ (number of samples)

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

(a) Synthetic datasets: S1 , S2 , S3 , S4 , S5 , S6 , S7 .

(b) Real datasets: Ir , Bc , Dg , Ng , Fm , Pd , Lt , Sa .

Dataset	Subset	avg Silhouette	avg NMI	CORR (CAKE $\sim$ ACC)
S1	Full	0.539 [0.5390, 0.5391]	0.834 [0.8332, 0.8339]	0.881
	Random	0.546 [0.5460, 0.5460]	0.834 [0.8340, 0.8340]
	Consensus	0.539 [0.5389, 0.5389]	0.839 [0.8395, 0.8395]
	$C$ component	0.539 [0.5389, 0.5389]	0.839 [0.8395, 0.8395]
	$\tilde{S}$ component	0.692 [0.6921, 0.6921]	0.983 [0.9828, 0.9828]
	$\mathrm{CAKE}^{\text{(PR)}}$	0.692 [0.6921, 0.6921]	0.983 [0.9828, 0.9828]

Appendix

Table 7: Average Silhouette and NMI (Normalized Mutual Information) with

t

-95% confidence intervals and Spearman’s rank correlation of CAKE percentiles with clustering accuracy percentiles. Results are reported for the full datasets (Full) and their filtered subsets mentioned in § 5.2 . Highest values in bold .

		Clustering results on filtered datasets
Data	Subset	avg Silhouette	avg NMI	avg ARI	avg AMI	avg ACC
S1	Full	0.486	0.742	0.732	0.742	0.848
	Random	0.546	0.833	0.878	0.833	0.958
	Consensus	0.581	0.858	0.889	0.858	0.937
	$C$ component	0.590	0.864	0.910	0.864	0.959
	$\tilde{S}$ component	0.632	0.928	0.928	0.928	0.952

Appendix

Table 11: Average Silhouette, NMI, ARI, AMI, and ACC over multiple independent MiniBatchKMeans runs (different random seeds). Results are reported for the full dataset and for subsets selected by the different filtering strategies (random, consensus-agree,

C

component,

\tilde{S}

component,

\mathrm{CAKE}^{\text{(PR)}}

\mathrm{CAKE}^{\text{(HM)}}

). Best performance per dataset and metric is shown in bold .

		Clustering results on filtered datasets
Data	Subset	avg Silhouette	avg NMI	avg ARI	avg AMI	avg ACC
S1	Full	0.539	0.834	0.879	0.834	0.958
	Random	0.546	0.833	0.878	0.833	0.957
	Consensus	0.538	0.836	0.881	0.836	0.959
	$C$ component	0.538	0.836	0.881	0.836	0.959
	$\tilde{S}$ component	0.692	0.983	0.992	0.983	0.997

Appendix

Table 12: Average Silhouette, NMI, ARI, AMI, and ACC over multiple independent GMM runs (different random seeds). Results are reported for the full dataset and for subsets selected by the different filtering strategies (random, consensus-agree,

C

component,

\tilde{S}

component,

\mathrm{CAKE}^{\text{(PR)}}

\mathrm{CAKE}^{\text{(HM)}}

). Best performance per dataset and metric is shown in bold .

Dataset	Subset	Retained	ARI	AMI	ACC
Bc	Full	569/569	0.663 [0.6558, 0.6698]	0.543 [0.5343, 0.5518]	0.908 [0.9058, 0.9101]
	Random	228/569	0.612 [0.6071, 0.6175]	0.484 [0.4786, 0.4892]	0.893 [0.8909, 0.8942]
	Consensus	228/569	0.831 [0.8233, 0.8393]	0.730 [0.7139, 0.7469]	0.957 [0.9553, 0.9596]
	$C$ component	228/569	0.831 [0.8233, 0.8393]	0.730 [0.7139, 0.7469]	0.957 [0.9553, 0.9596]
	$\tilde{S}$ component	228/569	0.924 [0.9239, 0.9239]	0.851 [0.8515, 0.8515]	0.987 [0.9868, 0.9868]
	$\mathrm{CAKE}^{\text{(PR)}}$	228/569	0.924 [0.9239, 0.9239]	0.851 [0.8515, 0.8515]	0.987 [0.9868, 0.9868]

Appendix

Table 13: Adaptive filtering with coverage selected by maximizing the Silhouette score over a fixed grid of retained fractions. For each dataset, the retained size is chosen from the

\mathrm{CAKE}^{(\mathrm{HM})}

ranking, and all competing filtering criteria are then evaluated at the same matched subset size. ARI, AMI, and ACC are reported as means over multiple independent runs, with

95\%

Student’s

t

-confidence intervals shown in brackets. The highest reported value for each metric is shown in bold .

Clustering

Clustering groups data points by shared structure, developing methods to discover, validate, and interpret groups across diverse data and constraints.

See all 335 papers

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

May 28, 2026

ExDBSCAN: Explaining DBSCAN with Counterfactual Reasoning -- Additional Material

Clustering is an unsupervised technique for grouping data points by similarity. While explainability methods exist for supervised machine learning, they are not directly applicable to clustering, making it challenging to understand cluster assignments. This interpretability gap is particularly evident in the popular density-based method DBSCAN, which assigns points as inliers (cluster members in dense regions) or outliers (noise points in sparse regions). DBSCAN does not provide insight into why a particular point receives its assignment or whether its assignment is robust to small changes in the data. To address the lack of explainability, we introduce ExDBSCAN, a density-aware, post-hoc explanation method. ExDBSCAN offers actionable counterfactual explanations, with theoretical guarantees for validity. It generates multiple counterfactuals using a density connected weighted graph, adopting a physics-inspired model that repels counterfactual candidates from one another (diversity), while pulling them toward the instance to explain (proximity). Empirical evaluation on 30 tabular datasets comparing against four baselines shows that ExDBSCAN outperforms all baselines while attaining perfect validity and retrieving diverse, proximal counterfactuals.

Pernille Matthews, Lena Krieger, Tommaso Amico +3

LMU Munich, DBS, MCML Munich, Germany

Explainable Artificial Intelligence Counterfactual Explanations Clustering Unsupervised Clustering Density-Based Clustering

Ask PDF

Mar 3, 2026

Scalable Posterior Uncertainty for Flexible Density-Based Clustering

We introduce a novel framework for uncertainty quantification in clustering that combines martingale posterior distributions with density-based clustering. Unlike classical model-based approaches, which define clusters at the latent level of a mixture model, we treat clusters as explicit functionals of the data-generating density, without assuming any specific parametric form. To characterize density uncertainty, we obtain martingale posterior samples via a predictive resampling scheme driven by model score evaluations. This allows us to leverage state-of-the-art differentiable density estimators, such as normalizing flows, making density resampling efficient in large-scale settings and fully parallelizable on modern GPU hardware. Martingale posterior samples of the clustering structure are then obtained by applying density-based clustering to the density draws, enabling principled inference on any clustering-related quantity. Casting the inference target as a density functional further enables a rigorous theoretical analysis of the procedure's convergence properties. We apply our methodology to image and single-cell RNA sequencing data, demonstrating the computational efficiency afforded by its GPU compatibility as well as its ability to recover meaningful clustering structures, with associated uncertainty, across diverse domains.

Nicola Bariletto, Stephen G. Walker

Department of Statistics and Data Sciences, UT Austin

Density-Based Clustering Clustering Uncertainty Quantification Bayesian Inference

Ask PDF

Abstract

Clustering

Explore similar work

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

ExDBSCAN: Explaining DBSCAN with Counterfactual Reasoning -- Additional Material

Scalable Posterior Uncertainty for Flexible Density-Based Clustering