Initial Centroid Selection Method for an Enhanced K-means Clustering Algorithm

摘要

Clustering is an important method to discover structures and patterns in high-dimensional data and group similar ones together. K-means is one of the most popular clustering algorithms. K-means groups observations by minimizing distances between them and maximizing group distances. One of the primordial steps in this algorithm is centroid selection, in which k initial centroids are estimated either randomly, calculated, or given by the user. Existing k-means algorithms uses the 'k-means++' option for this selection. In this paper, we suggest an enhanced version of k-means clustering that minimize the runtime of the algorithm using 'Ndarray' option. Experiments have shown that if the first choice of centroids is close to the final centers, the results will be quickly found. Thus, we propose a new concept that provides one of the best choices of starting centroids that reduces the execution time by ≈80% on average for UCI, Shape and Miscellaneous datasets.