Clustering Performance of an Evolutionary K-Means Algorithm

This paper continues research aimed at improving the performance accuracy of an evolutionary K-Means algorithm named Population-Based K-Means (PBKM). The PBKM design tries to overcome some limitations of basic K-Means behavior by two steps. In the first step, a population is built with a certain number of centroid candidates, some of which naturally located close to ground truth centroids. In the second step, the population candidate centroids are systematically recombined to achieve a careful clustering solution. Both steps depend on the use of Repeated K-Means together with careful seeding. The paper’s contribution paper consists in developing a new seeding method in the crucial first step of population set-up. Each candidate solution is determined by randomly splitting the dataset into a certain number of segments, clustering each segment by careful seeding, and merging the clusters of the various segments through a pairwise-nearest-neighbor (PNN) strategy. The paper demonstrates the clustering performance of the new PBKM by several simulation experiments carried out on synthetic and real-world datasets.