Sensitivity Sampling with Predictions for k-Means Clustering

• URL: http://arxiv.org/abs/2607.04949v1
• Date: Mon, 06 Jul 2026 11:24:56 GMT
• Title: Sensitivity Sampling with Predictions for k-Means Clustering
• Abstract summary: We study the problem of k-means clustering on large datasets.<n>One of the most popular and advanced approaches to derive coresets for k-means is sensitivity sampling.<n>We 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.
• Score: 4.766451696574634
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

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)
• CavMerge: Merging K-means Based on Local Log-Concavity [2.579311291240392]
  K-means clustering is known to exhibit suboptimal performance when applied to non-linearly separable data.<n>We present emphCavMerge, a novel K-means merging algorithm that is intuitive, free of parameter tuning, and computationally efficient.
  arXiv  Detail & Related papers  (2026-04-05T22:47:36Z)
• K*-Means: A Parameter-free Clustering Algorithm [55.20132267309382]
  k*-means is a novel clustering algorithm that eliminates the need to set k or any other parameters.<n>It uses the minimum description length principle to automatically determine the optimal number of clusters, k*, by splitting and merging clusters.<n>We prove that k*-means is guaranteed to converge and demonstrate experimentally that it significantly outperforms existing methods in scenarios where k is unknown.
  arXiv  Detail & Related papers  (2025-05-17T08:41:07Z)
• Geometric Median Matching for Robust k-Subset Selection from Noisy Data [75.86423267723728]
  We propose a novel k-subset selection strategy that leverages Geometric Median -- a robust estimator with an optimal breakdown point of 1/2.<n>Our method iteratively selects a k-subset such that the mean of the subset approximates the GM of the (potentially) noisy dataset, ensuring robustness even under arbitrary corruption.
  arXiv  Detail & Related papers  (2025-04-01T09:22:05Z)
• Categorical Data Clustering via Value Order Estimated Distance Metric Learning [53.28598689867732]
  This paper introduces a novel order distance metric learning approach to intuitively represent categorical attribute values.<n>A new joint learning paradigm is developed to alternatively perform clustering and order distance metric learning.<n>The proposed method achieves superior clustering accuracy on categorical and mixed datasets.
  arXiv  Detail & Related papers  (2024-11-19T08:23:25Z)
• Boosting K-means for Big Data by Fusing Data Streaming with Global Optimization [0.3069335774032178]
  K-means clustering is a cornerstone of data mining, but its efficiency deteriorates when confronted with massive datasets. We propose a novel algorithm that leverages the Variable Neighborhood Search (VNS) metaheuristic to optimize K-means clustering for big data.
  arXiv  Detail & Related papers  (2024-10-18T15:43:34Z)
• Inference with K-means [0.0]
  k-means is an iterative clustering algorithm that randomly assigns k centroids, then assigns data points to the nearest centroid, and updates centroids based on the mean of assigned points. Research investigates the prediction of the last component of data points obtained from a distribution of clustered data using the online balanced k-means approach.
  arXiv  Detail & Related papers  (2024-10-04T06:51:58Z)
• Downstream-Pretext Domain Knowledge Traceback for Active Learning [138.02530777915362]
  We propose a downstream-pretext domain knowledge traceback (DOKT) method that traces the data interactions of downstream knowledge and pre-training guidance. DOKT consists of a traceback diversity indicator and a domain-based uncertainty estimator. Experiments conducted on ten datasets show that our model outperforms other state-of-the-art methods.
  arXiv  Detail & Related papers  (2024-07-20T01:34:13Z)
• Fuzzy K-Means Clustering without Cluster Centroids [21.256564324236333]
  Fuzzy K-Means clustering is a critical technique in unsupervised data analysis. This paper proposes a novel Fuzzy textitK-Means clustering algorithm that entirely eliminates the reliance on cluster centroids.
  arXiv  Detail & Related papers  (2024-04-07T12:25:03Z)
• Rethinking k-means from manifold learning perspective [122.38667613245151]
  We present a new clustering algorithm which directly detects clusters of data without mean estimation. Specifically, we construct distance matrix between data points by Butterworth filter. To well exploit the complementary information embedded in different views, we leverage the tensor Schatten p-norm regularization.
  arXiv  Detail & Related papers  (2023-05-12T03:01:41Z)
• Sketch-and-solve approaches to k-means clustering by semidefinite programming [14.930208990741132]
  We introduce a sketch-and-solve approach to speed up the Peng-Wei semidefinite relaxation of k-means clustering. If the data is appropriately separated we identify the k-means optimal clustering. Otherwise, our approach provides a high-confidence lower bound on the optimal k-means value.
  arXiv  Detail & Related papers  (2022-11-28T19:51:30Z)
• Far Away in the Deep Space: Dense Nearest-Neighbor-Based Out-of-Distribution Detection [33.78080060234557]
  Nearest-Neighbors approaches have been shown to work well in object-centric data domains. We show that nearest-neighbor approaches also yield state-of-the-art results on dense novelty detection in complex driving scenes.
  arXiv  Detail & Related papers  (2022-11-12T13:32:19Z)

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.