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

By M. Emre Celebi, Hassan A. Kingravi, Patricio A. Vela. Expert systems with applications, 2012

1,219 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/a2986864eb361e4e66bd4c10f8fd3bf129408147

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

Citations in the corpus

Towards transferring skills to flexible surgical robots with programming by demonstration and reinforcement learning (2016, methodology): “Given the training set, Expectation maximization (EM) [18] algorithm is used to estimate the parameters of GMM, and k-means [19] is applied to initialize the EM algorithm.”
How much can k-means be improved by using better initialization and repeats? (2019, methodology): “In [39], SSE is also measured relative to the SSE-value of the ground truth solution ( SSE opt ): If the ground truth is known, external indexes such as adjusted Rand index (ARI), Van Dongen (VD), variation of information (VI) or normalized mutual information (NMI) can also be used [22].”
One Size Fits All for Semantic Shifts: Adaptive Prompt Tuning for Continual Learning (2023, methodology): “Accordingly, we implement simulation-based clustering techniques (Celebi et al., 2013; Gama et al., 2014) that permute task orders within each set N ti during grouping to identify the one with the fewest semantic groups.”
Integration K-Means Clustering Method and Elbow Method For Identification of The Best Customer Profile Cluster (2018, methodology): “According to (Celebi et al., 2013) the K-Means algorithm is also versatile, which is easy to modify at every stage of the process, simple in the distance calculation function, and depends on iteration termination criteria.”