Does Determination of Initial Cluster Centroids Improve the Performance of K-Means Clustering Algorithm? Comparison of Three Hybrid Methods by Genetic Algorithm, Minimum Spanning Tree, and Hierarchical Clustering in an Applied Study

Abstract EN

Random selection of initial centroids (centers) for clusters is a fundamental defect in K-means clustering algorithm as the algorithm’s performance depends on initial centroids and may end up in local optimizations.

Various hybrid methods have been introduced to resolve this defect in K-means clustering algorithm.

As regards, there are no comparative studies comparing these methods in various aspects, the present paper compared three hybrid methods with K-means clustering algorithm using concepts of genetic algorithm, minimum spanning tree, and hierarchical clustering method.

Although these three hybrid methods have received more attention in previous researches, fewer studies have compared their results.

Hence, seven quantitative datasets with different characteristics in terms of sample size, number of features, and number of different classes are utilized in present study.

Eleven indices of external and internal evaluating index were also considered for comparing the methods.

Data indicated that the hybrid methods resulted in higher convergence rate in obtaining the final solution than the ordinary K-means method.

Furthermore, the hybrid method with hierarchical clustering algorithm converges to the optimal solution with less iteration than the other two hybrid methods.

However, hybrid methods with minimal spanning trees and genetic algorithms may not always or often be more effective than the ordinary K-means method.

Therefore, despite the computational complexity, these three hybrid methods have not led to much improvement in the K-means method.

However, a simulation study is required to compare the methods and complete the conclusion.