Scalable and Distributed Silhouette Approximation

Ilie Sarpe; Federico Altieri; Andrea Pietracaprina; Geppino Pucci; Fabio Vandin

cs.DSJul 2, 2026

Scalable and Distributed Silhouette Approximation

Authors: Ilie Sarpe, Federico Altieri, Andrea Pietracaprina, Geppino Pucci, Fabio Vandin

Abstract

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 $δ$ in $(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.

Explore similar work

Jan 9, 2026cs.LG

A Fast and Effective Method for Euclidean Anticlustering: The Assignment-Based-Anticlustering Algorithm

Anticlustering is an NP-hard combinatorial optimization problem that consists of partitioning a set of objects into equal-sized groups called anticlusters such that the objects in the same anticluster are as dissimilar as possible and thereby representative of the entire set of objects. Here we study the case where the dissimilarity metric is the squared Euclidean distance between the respective feature vectors. Applications of Euclidean anticlustering include social studies, cross-validation, creating mini-batches for stochastic gradient descent, and finding balanced K-cut partitions. In particular, machine-learning applications such as mini-batch generation involve million-scale datasets and very large values of K, making scalable anticlustering algorithms essential. We propose a new algorithm, the Assignment-Based Anticlustering (ABA) algorithm, that scales to instances with millions of objects and hundreds of thousands of anticlusters within seconds to minutes, which is far beyond what existing anticlustering methods can manage. We demonstrate here, via an extensive computational study, that our algorithm outperforms existing anticlustering methods in both solution quality and running time. This is so also for anticlustering with categories. For the related problem of balanced K-cut partitioning, our algorithm is superior to the well-known METIS method. The code of our algorithm is available on GitHub.

Philipp Baumann, Olivier Goldschmidt, Dorit S. Hochbaum +1

Clustering Max Cut Patient-To-Room Assignment Problem Unsupervised Maximum Mean Discrepancy

Ask PDF

Jul 6, 2026cs.LG

Sensitivity Sampling with Predictions for k-Means Clustering

We study the problem of k-means clustering on large datasets. The state-of-the-art for the problem is given by coresets-based approaches, which build small weighted summaries of the input and derive approximate solutions with rigorous quality guarantees from them. One of the most popular and advanced approaches to derive coresets for k-means is sensitivity sampling. However, sensitivity sampling requires to compute the importance of each input point with respect to the whole dataset over all possible choices of centers. Since the exact computation of such quantities is unfeasible, current approaches work by approximating the sensitivity values. Nevertheless, the runtime of such approaches is still impractical for large datasets. In this work, we propose to reduce the runtime of sensitivity-based approaches for k-means by leveraging predictions to approximate the importance of input points. We first formally prove that current theoretical results on coresets construction via sensitivity sampling hold for coarser approximations of sensitivities compared to the one required by existing approaches. This implies that even fairly noisy predictors can be leveraged for sensitivity-sampling approaches. We then propose a natural predictor, which applies to the common scenario where clustering is performed (over time) on a sequence of datasets from the same problem. We prove that when the datasets in the sequence come from the same (unknown) distribution, centers resulting in a low error on one dataset can be used as predictions for sensitivity sampling in subsequent datasets, with guarantees on their quality. We perform an extensive experimental evaluation showing that our approach significantly improves, in terms of clustering cost vs runtime, over uniform sampling and state-of-the-art sensitivity sampling approaches when applied to sequences of datasets.

Cristian Boldrin, Fabio Vandin

K$-Means Clustering Geometry-Aware Uncertainty Coresets Adaptive Sampling Noisy Data

Ask PDF

Jun 10, 2022cs.LG

Anisotropic View Distance Metric for High-Dimensional Data: Theory, Geometry, and Fast Computation

K-Means clustering algorithm is one of the most commonly used clustering algorithms because of its simplicity and efficiency. K-Means clustering algorithm based on Euclidean distance only pays attention to the linear distance between Euclidean distance is an efficient and interpretable similarity measurement, but its effectiveness may deteriorate in sample spaces with anisotropic structures, redundant features, or complex feature interactions. In this paper, we propose a novel distance metric called View distance. Inspired by orthographic projection, the proposed metric projects the sample space onto

n(n-1)/2

two-dimensional planes and defines the final distance as the sum of the Euclidean distances across the projected planes. Theoretical derivations verify that the View distance strictly satisfies the metric axioms and norm constraints. Beyond that, the View distance achieves feature coupling through projection and not only enables constant features to indirectly participate in distance calculation, but also suppresses interference from redundant features while exhibiting anisotropic geometric properties. Furthermore, to address the high computational complexity and poor scalability of full-projection View distance, we propose a two-dimensional projection plane selection strategy based on iterative Maximum Weight Matching, which reduces the computational complexity of distance calculation from

\mathcal{O}(n^2)

\mathcal{O}(k)

. Extensive experiments on 12 diverse datasets demonstrate that View distance and the deterministic selection strategy provide competitive or superior performance compared with Euclidean distance and other

L_{p}

metrics while maintaining strong interpretability and computational efficiency. The View distance provides a new perspective and option for similarity measurements.

Yiqun Zhang, Hou-biao Li

K$-Means Distance High-Dimensional Maximum Mean Discrepancy Anisotropy Projection

Ask PDF