Boosting K-means for Big Data by Fusing Data Streaming with Global Optimization
This addresses the problem of scaling K-means for big data in data mining, with incremental improvements over existing methods.
The paper tackles the inefficiency of K-means clustering on massive datasets by proposing a novel heuristic algorithm that uses Variable Neighborhood Search to optimize partial objective functions from random samples, resulting in significant accuracy and efficiency improvements, establishing it as the new state of the art.
K-means clustering is a cornerstone of data mining, but its efficiency deteriorates when confronted with massive datasets. To address this limitation, we propose a novel heuristic algorithm that leverages the Variable Neighborhood Search (VNS) metaheuristic to optimize K-means clustering for big data. Our approach is based on the sequential optimization of the partial objective function landscapes obtained by restricting the Minimum Sum-of-Squares Clustering (MSSC) formulation to random samples from the original big dataset. Within each landscape, systematically expanding neighborhoods of the currently best (incumbent) solution are explored by reinitializing all degenerate and a varying number of additional centroids. Extensive and rigorous experimentation on a large number of real-world datasets reveals that by transforming the traditional local search into a global one, our algorithm significantly enhances the accuracy and efficiency of K-means clustering in big data environments, becoming the new state of the art in the field.