A hybrid particle swarm clustering algorithm with novel fitness function based on minimum spanning tree and local Centroids

Most particle swarm clustering studies focus primarily on improving search strategies and update mechanisms, neglecting the critical role of fitness functions in guiding search direction and determining clustering quality. Notably, many algorithms commonly adopt the objective function of K-means or classical clustering validity indices as their fitness functions. These functions typically assume convex clusters and struggle with complex data distributions. To address this limitation, we propose a novel fitness function that computes all distances based on Minimum Spanning Tree (MST) paths and represents each cluster with multiple centroids. MST avoids the assumption of spatial convexity, thereby better capturing non-convex structures; meanwhile, multiple local centroids per cluster enable more accurate representation of complex cluster shapes. Specifically, our function defines intra-cluster compactness as the sum of subclusters’ compactness and inter-subcluster connection distances. Inter-cluster separation is estimated using the minimum shortest path distance between local centroids of different clusters. This novel fitness function provides a more accurate optimization direction for particle swarm clustering. Experiments on six synthetic datasets demonstrate that the proposed fitness function significantly enhances the adaptability of particle swarm optimization algorithm to complex data structures. Comparative evaluations on 13 datasets with 11 mainstream clustering algorithms further confirm the proposed fitness function’s superiority in clustering performance. Crucially, the proposed function maintains consistent performance improvements when applied to other swarm intelligence-based clustering, highlighting its strong generalizability and broad application potential. Finally, the Wilcoxon rank sum test statistically validates the effectiveness of our approach.