Scalable and Distributed Silhouette Approximation

• URL: http://arxiv.org/abs/2607.01993v1
• Date: Thu, 02 Jul 2026 10:27:49 GMT
• Title: Scalable and Distributed Silhouette Approximation
• Abstract summary: The silhouette is one of the most widely used measures to assess the quality of a $k$-clustering of a dataset of $n$ elements.<n>Previous approximate methods using $O(n2)$ distance calculations are not offering controllable guarantees on the quality of their results.<n>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.
• Score: 4.628299420104186
• License: http://creativecommons.org/licenses/by-sa/4.0/
• 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.

Related papers

• Active Learning with Low-Rank Structure for Data Selection [85.43185363043362]
  We introduce a new data selection framework based on low-rank approximation and residual-based sampling.<n>We show that it is possible to select a weighted subset of $tildeOleft(k + frac1varepsilon2right)$ data points whose average loss approximates the average loss over the full dataset.
  arXiv  Detail & Related papers  (2026-06-14T22:29:59Z)
• Efficient Mean Curvature Computation on High-Dimensional Data Manifolds [52.452902154360565]
  Estimating local mean curvature at each point of a high-dimensional dataset is a key ingredient of machine learning algorithms.<n>This paper introduces two complementary contributions that together reduce this cost by several orders of magnitude.<n> Experiments on real-world datasets confirm speedups of 50 to 300 times relative to the original implementation.
  arXiv  Detail & Related papers  (2026-06-04T16:04:31Z)
• Fast unsupervised ground metric learning with tree-Wasserstein distance [14.235762519615175]
  unsupervised ground metric learning approaches have been introduced.<n>One promising option employs Wasserstein singular vectors (WSVs), which emerge when computing optimal transport distances between features and samples simultaneously.<n>We propose to augment the WSV method by embedding samples and features on trees, on which we compute the tree-Wasserstein distance (TWD)
  arXiv  Detail & Related papers  (2024-11-11T23:21:01Z)
• Simple, Scalable and Effective Clustering via One-Dimensional Projections [10.807367640692021]
  Clustering is a fundamental problem in unsupervised machine learning with many applications in data analysis. We introduce a simple randomized clustering algorithm that provably runs in expected time $O(mathrmnnz(X) + nlog n)$ for arbitrary $k$. We prove that our algorithm achieves approximation ratio $smashwidetildeO(k4)$ on any input dataset for the $k$-means objective.
  arXiv  Detail & Related papers  (2023-10-25T16:37:45Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  We show that our method computes a solution with cost at most $O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$, where $epsilon$ is the privacy guarantee. Although the worst-case guarantee is worse than that of state of the art private clustering methods, the algorithm we propose is practical.
  arXiv  Detail & Related papers  (2022-06-17T09:24:41Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  We study the problem of list-decodable mean estimation, where an adversary can corrupt a majority of the dataset. We develop new algorithms for list-decodable mean estimation, achieving nearly-optimal statistical guarantees.
  arXiv  Detail & Related papers  (2021-06-16T03:34:14Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  We study the fundamental task of list-decodable mean estimation in high dimensions. Our algorithm runs in time $widetildeO(ndk)$ for all $k = O(sqrtd) cup Omega(d)$, where $n$ is the size of the dataset. A variant of our algorithm has runtime $widetildeO(ndk)$ for all $k$, at the expense of an $O(sqrtlog k)$ factor in the recovery guarantee
  arXiv  Detail & Related papers  (2020-11-19T17:21:37Z)
• Computationally efficient sparse clustering [67.95910835079825]
  We provide a finite sample analysis of a new clustering algorithm based on PCA. We show that it achieves the minimax optimal misclustering rate in the regime $|theta infty$.
  arXiv  Detail & Related papers  (2020-05-21T17:51:30Z)
• Scalable Distributed Approximation of Internal Measures for Clustering Evaluation [5.144809478361603]
  Internal measure for clustering evaluation is the silhouette coefficient, whose computation requires a quadratic number of distance calculations. We present the first scalable algorithm to compute such a rigorous approximation for the evaluation of clusterings based on any metric distances. We also prove that the algorithm can be adapted to obtain rigorous approximations of other internal measures of clustering quality, such as cohesion and separation.
  arXiv  Detail & Related papers  (2020-03-03T10:28:14Z)
• Explainable $k$-Means and $k$-Medians Clustering [25.513261099927163]
  We consider using a small decision tree to partition a data set into clusters, so that clusters can be characterized in a straightforward manner. We show that popular top-down decision tree algorithms may lead to clusterings with arbitrarily large cost. We design an efficient algorithm that produces explainable clusters using a tree with $k$ leaves.
  arXiv  Detail & Related papers  (2020-02-28T04:21:53Z)
• Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives [10.291482850329892]
  Mixed integer programming (MIP) can be used to solve (to optimality) $ell_0$-regularized regression problems. We propose two classes of scalable algorithms: an exact algorithm that can handlepapprox 50,000$ features in a few minutes, and approximate algorithms that can address instances with $papprox6$. In addition, we present new estimation error bounds for $ell$-regularizeds.
  arXiv  Detail & Related papers  (2020-01-17T18:47:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.