Particle swarm clustering fitness evaluation with computational centroids

Abstract

In this paper, we propose a new way to carry out fitness evaluation in dynamic Particle Swarm Clustering (PSC) with centroid-based encoding. Generally, the PSC fitness function is selected among the clustering validity indices and most of them directly depend on the cluster centroids. In the traditional fitness evaluation approach, the cluster centroids are replaced by the centroids proposed by a particle position. We propose to first compute the centroids of the corresponding clusters and then use these computational centroids in fitness evaluation. The proposed way is called Fitness Evaluation with Computational Centroids (FECC). We conducted an extensive set of comparative evaluations and the results show that FECC leads to a clear improvement in clustering results compared to the traditional fitness evaluation approach with most of the fitness functions considered in this study. The proposed approach was found especially beneficial when underclustering is a problem. Furthermore, we evaluated 31 fitness functions based on 17 clustering validity indices using two PSC methods over a large number of synthetic and real data sets with varying properties. We used three different performance criteria to evaluate the clustering quality and found out that the top three fitness functions are Xu index, WB index, and Dunn variant DU23 applied using FECC. These fitness functions consistently performed well for both PSC methods, for all data distributions, and according to all performance criteria. In all test cases, they were clearly among the better half of the fitness functions and, in the majority of the cases, they were among the top 4 functions. Further guidance for improved fitness function selection in different situations is provided in the paper.