A Comparative Study of Efficient Initialization Methods for the K-Means Clustering Algorithm

Abstract

K-means is undoubtedly the most widely used partitional clustering algorithm. Unfortunately, due to its gradient descent nature, this algorithm is highly sensitive to the initial placement of the cluster centers. Numerous initialization methods have been proposed to address this problem. In this paper, we first present an overview of these methods with an emphasis on their computational efficiency. We then compare eight commonly used linear time complexity initialization methods on a large and diverse collection of data sets using various performance criteria. Finally, we analyze the experimental results using non-parametric statistical tests and provide recommendations for practitioners. We demonstrate that popular initialization methods often perform poorly and that there are in fact strong alternatives to these methods.

17 pages, 1 figure, 7 tables

References in corpus (1)

• Improving the Performance of K-Means for Color Quantization

Cited by in corpus (39)

• Load Balancing for Ultra-Dense Networks: A Deep Reinforcement Learning Based Approach
• Deterministic Initialization of the K-Means Algorithm Using Hierarchical Clustering
• Universal image segmentation for optical identification of 2D materials
• Progressive Wasserstein Barycenters of Persistence Diagrams
• Practical Quantum K-Means Clustering: Performance Analysis and Applications in Energy Grid Classification
• Recombinator-k-means: An evolutionary algorithm that exploits k-means++ for recombination
• On the Efficiency of K-Means Clustering: Evaluation, Optimization, and Algorithm Selection
• An NWDAF Approach to 5G Core Network Signaling Traffic: Analysis and Characterization
• ECMdd: Evidential c-medoids clustering with multiple prototypes
• Remote sensing framework for geological mapping via stacked autoencoders and clustering
• Agglomerative Hierarchical Clustering with Dynamic Time Warping for Household Load Curve Clustering
• Data-driven classification of individual cells by their non-Markovian motion
• An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering
• Robust and efficient multi-way spectral clustering
• Minimal Learning Machine: Theoretical Results and Clustering-Based Reference Point Selection
• Unsupervised Event Classification with Graphs on Classical and Photonic Quantum Computers
• Balanced k-Means Clustering on an Adiabatic Quantum Computer
• Exchangeability, Conformal Prediction, and Rank Tests
• Simple and Scalable Sparse k-means Clustering via Feature Ranking
• Leveraging Machine Learning for Accurate and Fast Stellar Mass Estimation of Galaxies
• Simple and sharp analysis of k-means||
• Noisy, Greedy and Not So Greedy k-means++
• Semi-supervised classification of stars, galaxies and quasars using K-means and random-forest approaches
• Merge Tree Geodesics and Barycenters with Path Mappings
• Effective Deterministic Initialization for $k$-Means-Like Methods via Local Density Peaks Searching
• Quantifying dependencies for sensitivity analysis with multivariate input sample data
• A Tabu Search based clustering algorithm and its parallel implementation on Spark
• Polynomial algorithms for p-dispersion problems in a planar Pareto Front
• Research on the construction method of vehicle driving cycle based on Mean Shift clustering
• Entropy Regularized Power k-Means Clustering
• Multi-Sound-Source Localization Using Machine Learning for Small Autonomous Unmanned Vehicles with a Self-Rotating Bi-Microphone Array
• Rock the KASBA: Blazingly Fast and Accurate Time Series Clustering
• K-Medoids For K-Means Seeding
• Scalable Initialization Methods for Large-Scale Clustering
• Active Learning for Argument Mining: A Practical Approach
• Analysis of Cellular Feature Differences of Astrocytomas with Distinct Mutational Profiles Using Digitized Histopathology Images
• Interdependence of clusters measures and distance distribution in compact metric spaces
• On improved bound for measure of cluster structure in compact metric spaces
• Mathematical Foundations in Visualization