Data-Native Global Optimization for Big Data K-means Clustering

• URL: http://arxiv.org/abs/2607.15835v1
• Date: Fri, 17 Jul 2026 10:46:58 GMT
• Title: Data-Native Global Optimization for Big Data K-means Clustering
• Abstract summary: Big-means++ is an algorithm achieving scalability and global-native quality.<n>It orchestrates local K-means refinements into a data-search global search for big data clustering.<n>Experiments on 22 datasets demonstrate the effectiveness, efficiency, and robustness of Big-means++.
• Score: 0.1399948157377307
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Big data clustering remains challenging: the Minimum Sum-of-Squares Clustering (MSSC) problem underlying K-means is NP-hard, and existing methods either reach poor local minima or require prohibitive metaheuristic hybrids. We target arbitrarily tall data: a fixed feature space may contain arbitrarily many, possibly infinitely many, observations, while the algorithm accesses only finite random samples. We propose Big-means++, an algorithm achieving scalability and global-search quality by curating inputs to MSSC optimization on big data. It orchestrates local K-means refinements into a data-native global search for big data clustering. Rather than optimizing the full-data MSSC objective, Big-means++ traverses sample-induced surrogate landscapes. Each sample defines a distinct empirical MSSC approximation with a perturbed local-optimum structure, turning sample-to-sample variation into a global-search mechanism. Unlike Big-means, a flowing-incumbent strategy propagates centroid state across empirical landscapes through K-means refinements on fresh samples without rollback to a best-so-far solution. This increases mobility and favors stable, high-quality configurations across approximations of the full-data structure. A new shaking mechanism varies sample size geometrically, broadening the surrogate landscapes explored across resolution scales, accounting for cluster imbalance, and improving solution quality. A competitive multi-agent system asynchronously explores independent sampled landscapes, transforming diverse stochastic trajectories into collective search intelligence. Automatic convergence detection stops each agent after attaining a high-quality solution but before further search risks degrading it, while providing a universal speed-quality control. Experiments on 22 datasets against 11 competing algorithms demonstrate the effectiveness, efficiency, and robustness of Big-means++.

Related papers

• SCOPE: Semantic Coreset with Orthogonal Projection Embeddings for Federated learning [0.7799711162530713]
  Current ML approaches either require impractical data aggregation or fail due to class imbalance.<n>We introduce SCOPE, a coreset framework for federated data that filters anomalies and adaptively prunes redundant data to long-tail skew.<n>SCOPE yields competitive global accuracy and robust convergence, all while achieving exceptional efficiency with a 128x to 512x reduction in uplink bandwidth.
  arXiv  Detail & Related papers  (2026-03-13T13:24:12Z)
• Adaptive and Robust DBSCAN with Multi-agent Reinforcement Learning [53.527506374566485]
  We propose a novel Adaptive and Robust DBSCAN with Multi-agent Reinforcement Learning cluster framework, namely AR-DBSCAN.<n>We show that AR-DBSCAN not only improves clustering accuracy by up to 144.1% and 175.3% in the NMI and ARI metrics, respectively, but also is capable of robustly finding dominant parameters.
  arXiv  Detail & Related papers  (2025-05-07T11:37:23Z)
• 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)
• Strong bounds for large-scale Minimum Sum-of-Squares Clustering [0.45880283710344055]
  Minimum Sum-of-Squares Clustering (MSSC) is one of the most widely used clustering methods.<n>MSSC aims to minimize the total squared Euclidean distance between data points and their corresponding cluster centroids.<n>We introduce a novel method to validate MSSC solutions through optimality gaps.
  arXiv  Detail & Related papers  (2025-02-12T13:40:00Z)
• 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)
• Self-Supervised Graph Embedding Clustering [70.36328717683297]
  K-means one-step dimensionality reduction clustering method has made some progress in addressing the curse of dimensionality in clustering tasks. We propose a unified framework that integrates manifold learning with K-means, resulting in the self-supervised graph embedding framework.
  arXiv  Detail & Related papers  (2024-09-24T08:59:51Z)
• Tackling Diverse Minorities in Imbalanced Classification [80.78227787608714]
  Imbalanced datasets are commonly observed in various real-world applications, presenting significant challenges in training classifiers. We propose generating synthetic samples iteratively by mixing data samples from both minority and majority classes. We demonstrate the effectiveness of our proposed framework through extensive experiments conducted on seven publicly available benchmark datasets.
  arXiv  Detail & Related papers  (2023-08-28T18:48:34Z)
• Large-scale Fully-Unsupervised Re-Identification [78.47108158030213]
  We propose two strategies to learn from large-scale unlabeled data. The first strategy performs a local neighborhood sampling to reduce the dataset size in each without violating neighborhood relationships. A second strategy leverages a novel Re-Ranking technique, which has a lower time upper bound complexity and reduces the memory complexity from O(n2) to O(kn) with k n.
  arXiv  Detail & Related papers  (2023-07-26T16:19:19Z)
• Towards Automated Imbalanced Learning with Deep Hierarchical Reinforcement Learning [57.163525407022966]
  Imbalanced learning is a fundamental challenge in data mining, where there is a disproportionate ratio of training samples in each class. Over-sampling is an effective technique to tackle imbalanced learning through generating synthetic samples for the minority class. We propose AutoSMOTE, an automated over-sampling algorithm that can jointly optimize different levels of decisions.
  arXiv  Detail & Related papers  (2022-08-26T04:28:01Z)
• How to Use K-means for Big Data Clustering? [2.1165011830664677]
  K-means is the simplest and most widely used algorithm under the Euclidean Minimum Sum-of-Squares Clustering (MSSC) model. We propose a new parallel scheme of using K-means and K-means++ algorithms for big data clustering.
  arXiv  Detail & Related papers  (2022-04-14T08:18:01Z)

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.