Source-linked AI summary
A Comparative Study of Efficient Initialization Methods for the K-Means Clustering Algorithm
M. Emre Celebi, Hassan A. Kingravi, Patricio A. Vela
TL;DR
K-means is widely used but sensitive to its initial centers, creating a need to identify effective and computationally efficient initialization methods. The paper surveys initialization methods, compares eight linear-time methods on diverse data, and applies non-parametric statistical tests. It finds that popular methods often perform poorly and that comparably efficient alternatives can be significantly better.
Problem
K-means is sensitive to initial center placement, motivating evidence about which initialization methods are effective without sacrificing its computational advantage.
Method
The study reviews initialization methods, compares eight commonly used linear-time methods on diverse real and synthetic data sets, and analyzes results with non-parametric statistical tests.
Results
Popular methods such as Forgy, MacQueen, and maximin often perform poorly, while significantly better alternatives have comparable computational requirements.
Takeaways & Limitations
Initialization methods should be assessed jointly for clustering effectiveness and computational efficiency rather than assumed effective because they are popular.
Takeaways & Limitations
The study excludes splitting methods and global k-means because they are complete clustering methods rather than initialization methods per se.
Abstract
from arXiv · showhide
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.
1. Introduction
Clustering groups unlabeled patterns for exploration, classification, and compression, while k-means remains popular because it is simple, versatile, and computationally efficient. However, its optimization is difficult and its results depend on initialization, motivating systematic comparison of initialization methods.
- Clustering organizes patterns into groups to support exploratory insight, classification, and data compression.
- The minimum SSE objective is computationally difficult because exhaustive enumeration is prohibitive and the problem is NP-hard even for K = 2 or D = 2.
- Lloyd’s algorithm alternates nearest-center assignment with centroid recomputation until a termination criterion is met.
- K-means is widely used because it is simple, versatile, and linear in N, D, and K.
- K-means has limitations including the need to specify K beforehand, detection of mainly compact well-separated clusters, and sensitivity to noise and outliers.
- The study reviews and compares initialization methods across broader data and method collections while evaluating computational efficiency and using non-parametric statistical tests.
2. Initialization Methods for K-Means
K-means initialization methods range from simple random or synthetic seeding to density-, distance-, partition-, PCA-, and pyramidal approaches. Their computational trade-offs matter because elaborate initialization can reduce iterations without necessarily improving total efficiency when fast k-means is used.
- Linear Time-Complexity Initialization Methods: Forgy, MacQueen, and related simple methods select random, ordered, or synthetic seeds, but can be sensitive to ordering, outliers, proximity, or empty clusters.
- Linear Time-Complexity Initialization Methods: Maximin selects each new center by maximizing its minimum distance from previously selected centers, targeting well-separated seeds.
- Linear Time-Complexity Initialization Methods: Bradley and Fayyad’s method clusters random subsets, combines intermediate centers, and retains the center set yielding the least SSE.
- Linear Time-Complexity Initialization Methods: K-means++ samples centers according to squared distance from existing centers, while greedy k-means++ chooses candidates that most reduce SSE.
- Linear Time-Complexity Initialization Methods: PCA-Part recursively splits the cluster with greatest SSE along its principal direction, whereas Var-Part approximates it using the highest-variance coordinate axis.
- Linear Time-Complexity Initialization Methods: Lu et al.’s pyramidal method aggregates and refines quantized points across levels, but its performance degrades as dimensionality increases.
- Linear vs. Superlinear Initialization Methods: More elaborate initialization can reduce k-means iterations, yet with fast exact k-means it is not necessarily more computationally efficient than simpler methods.
3. Experimental Setup
The experiments evaluate initialization methods on 32 real and 12,288 synthetic data sets, using normalization and multiple quality and efficiency criteria.
- Data sets: 32 real data sets ranged from 214 to 1,904,711 points, while synthetic data sets were generated with varying clustering complexity.Most real data sets came from the UCI Machine Learning Repository.
- Data sets: 12,288 synthetic data sets were divided equally among easy, moderate, and difficult complexity classes.Each class contained 4,096 data sets, defined using the complexity indicator Ω.
- Preprocessing: Real-data attributes were min-max normalized to [0, 1] to prevent large ranges from dominating distances and to avoid numerical instabilities.Synthetic attributes were already normalized by the generation algorithm.
- Performance criteria: The study measured initialization quality with initial SSE and refined quality with final SSE after k-means clustering.Final SSE is the k-means objective function, whereas initial SSE evaluates the initialization independently.
- Performance criteria: External validity was assessed with RAND, VD, and VI, normalized measures ranging from 0 to 1.These measures quantify agreement between discovered clusters and an external structure such as class labels.
- Performance criteria: Efficiency was evaluated using CPU time and the number of k-means iterations required for convergence.Iteration count is independent of programming language, implementation style, compiler, and CPU architecture; CPU time was reported only for real data sets.
4. Experimental Results and Discussion
The study evaluates eight linear-time, order-invariant initialization methods using repeated effectiveness measurements, computational cost, and non-parametric statistical tests. Results favor deterministic methods for mean performance and reveal substantial differences in reliability, efficiency, and practical suitability across settings.
- Experimental design: Eight linear-time, order-invariant initialization methods were compared, with only Var-Part and PCA-Part being deterministic.The methods were evaluated because k-means itself has linear complexity and initialization should preserve that advantage.
- Experimental design: Each non-deterministic method was run 100 times, while cluster counts were set equal to the number of data classes.Minimum, mean, and standard deviation statistics were collected for effectiveness criteria.
- Statistical analysis: Friedman and Iman–Davenport tests, followed by Bergmann–Hommel comparisons, assessed whether initialization methods differed significantly across data sets.Data sets served as blocks and initialization methods as treatments, with significance tested at α = 0.05.
- Real-data results: For real data, deterministic methods V and P were preferred when mean Final SSE mattered, whereas minimum Final SSE often could not distinguish methods reliably.The minimum-statistic analysis had limited discrimination with 32 data sets and many ties.
- Computational efficiency: Non-deterministic methods often cost more overall because selecting the best of R runs outweighs similar per-run CPU requirements.Simple methods may require more k-means iterations, while elaborate methods offset initialization overhead through fewer iterations.
- Performance trends: Across rankings, V and P generally outperformed non-deterministic methods, B remained competitive, and M and X were often among the worst performers.G often outperformed all non-deterministic methods except B, while K and G generally performed well in some comparisons.
- Reliability: Standard-deviation results placed B consistently among the best, while F and G often outperformed other methods and X and K showed moderate-to-bad performance.These findings concern reliability of non-deterministic initialization methods across repeated runs.
- Recommendations: For recommendations, F, M, and X should generally be avoided, V or P suit time-critical or deterministic applications, and B or G suit small data sets.B, G, V, and P are also recommended when approximate standalone clustering is desired because they produce strong initial clusterings.
5. Conclusions
The paper compares eight linear-time k-means initialization methods across diverse data sets and performance criteria, finding that several popular methods perform poorly while stronger alternatives have comparable computational requirements.
- Eight commonly used linear-time initialization methods were compared on diverse real and synthetic data sets using multiple performance criteria.
- The experiments emphasized computational efficiency alongside clustering effectiveness and used non-parametric statistical tests to analyze results.
- Forgy, MacQueen, and Maximin often performed poorly in the statistical analyses.
- Significantly better alternatives to these popular methods had comparable computational requirements.