[Paper] Assigning Confidence: K-partition Ensembles

Source: arXiv - 2602.18435v1

Overview

Clustering algorithms are great at uncovering hidden structure in data, but they rarely tell you how confident they are about each individual assignment. This makes it hard for developers to trust the results, especially when using initialization‑sensitive methods like k‑means. The paper Assigning Confidence: K‑partition Ensembles proposes CAKE (Confidence in Assignments via K‑partition Ensembles), a lightweight framework that attaches a [0, 1] confidence score to every data point by looking at how consistently it is clustered across multiple runs and how well it fits the local geometry of its assigned cluster.

Key Contributions

• Point‑wise confidence metric: Introduces a unified score that combines assignment stability and local geometric fit, giving an interpretable confidence value for each instance.
• Theoretical guarantees: Proves that the metric remains robust under realistic noise models and can provably separate stable from unstable points.
• Ensemble‑agnostic design: Works with any collection of clustering runs (e.g., different seeds, algorithms, or hyper‑parameters) without requiring changes to the underlying clustering method.
• Practical tooling: Demonstrates how the confidence ranking can be used to filter ambiguous points, improve downstream tasks, or guide human inspection.
• Extensive evaluation: Validates CAKE on synthetic benchmarks (controlled noise, overlapping clusters) and several real‑world datasets (image features, text embeddings, network data).

Methodology

1. Generate an ensemble – Run the chosen clustering algorithm multiple times (different random seeds, subsamples, or parameter settings) to obtain a set of K‑partitions.
2. Assignment stability – For each data point i, compute the proportion of ensemble members that assign i to the same cluster. This yields a stability value (s_i \in [0,1]).
3. Local geometric fit – Within each cluster, fit a simple geometric model (e.g., a Gaussian or a k‑nearest‑neighbors density estimate). Measure how well point i conforms to the model of its most‑frequent cluster, producing a fit score (g_i \in [0,1]).
4. Combine scores – The final confidence is a weighted combination, typically a product (c_i = s_i \times g_i) or a convex blend, ensuring that low stability or poor fit drives the confidence down.
5. Interpretation – Scores close to 1 indicate a “core” member of a cluster, while scores near 0 flag ambiguous or noisy points.

The pipeline requires only the raw cluster assignments and a cheap local density estimator, making it easy to plug into existing pipelines.

Results & Findings

• Stable cores consistently receive high confidence scores, matching ground‑truth cluster memberships where available.
• Ambiguous points (e.g., near cluster boundaries or corrupted by noise) receive low scores, and removing the bottom 10‑15 % of points yields noticeably cleaner clusters.
• The confidence metric correlates strongly (ρ ≈ 0.78) with external validation measures such as silhouette width and adjusted Rand index, confirming that CAKE captures meaningful uncertainty.
• Runtime overhead is modest: generating a 50‑run ensemble for a 100 k‑point dataset adds ~15 % to total clustering time, while the confidence computation itself is linear in the number of points.

Practical Implications

• Data cleaning: Developers can automatically flag low‑confidence instances for review, reducing manual labeling effort in semi‑supervised pipelines.
• Robust downstream models: Feeding only high‑confidence cluster assignments into recommendation engines, anomaly detectors, or feature engineering steps improves stability and reduces error propagation.
• Active learning: The confidence scores can guide query selection, focusing human labeling on the most uncertain points to accelerate model improvement.
• Model selection: By comparing confidence distributions across different clustering algorithms or hyper‑parameters, teams can pick the configuration that yields the most decisive assignments.
• Explainability: Providing a per‑instance confidence score helps stakeholders understand why a particular grouping may be unreliable, which is valuable in regulated domains (e.g., healthcare, finance).

Limitations & Future Work

• Ensemble size trade‑off: Very small ensembles may produce noisy confidence estimates, while very large ensembles increase computational cost. Adaptive stopping criteria are an open question.
• Choice of geometric model: The current approach uses simple density estimators; more expressive models (e.g., deep autoencoders) could capture complex cluster shapes but would add overhead.
• Scalability to massive data: For billions of points, distributed implementations of the ensemble and confidence calculation are needed.
• Extension to hierarchical or overlapping clusters: The paper focuses on flat partitions; extending CAKE to dendrograms or soft clustering remains future work.

Overall, CAKE offers a practical, theory‑backed way to turn “black‑box” clustering results into actionable insights, giving developers the confidence scores they need to make smarter decisions about unsupervised data.

Authors

• Aggelos Semoglou
• John Pavlopoulos

Paper Information

• arXiv ID: 2602.18435v1
• Categories: cs.LG
• Published: February 20, 2026
• PDF: Download PDF