Sensitivity Sampling with Predictions for k-Means Clustering
2026-07-06 • Machine Learning
Machine LearningData Structures and Algorithms
AI summaryⓘ
The authors study how to speed up k-means clustering on large datasets by improving sensitivity sampling, a popular method to create small summaries (coresets) of data for fast approximate solutions. They show that rough estimates of point importance (sensitivities) are enough, meaning predictions—even if somewhat noisy—can help reduce computation time. They propose using solutions from previous similar datasets to predict these sensitivities for new datasets, proving this works well if the data come from the same distribution. Experiments show their method is faster and more efficient than existing approaches on sequences of related datasets.
k-means clusteringcoresetssensitivity samplingapproximate algorithmsdata summarizationmachine learning predictiondistributional assumptionslarge datasetsruntime optimizationclustering cost
Authors
Cristian Boldrin, Fabio Vandin
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.