Clustering by an Evolutionary Random Swap Algorithm

This paper proposes the Evolutionary Random Swap (ERS) clustering algorithm that extends the basic behavior of Random Swap (RS) by a population of candidate solutions (centroid configurations), preliminarily established through a proper seeding procedure, which provides the swap data points that RS uses in the attempting step of improving the current clustering solution. The new centroid solution improves the previous solution in the case it reduces the Sum of Squared Errors (SSE) index. ERS, though, can also be used to optimize (maximize), in not large datasets, the Silhouette (SI) coefficient which measures the degree of separation of clusters. High-quality clustering is mirrored by clusters with high internal cohesion and a high external separation. The paper describes the design of ERS that is currently implemented in parallel Java. Different clustering experiments concerning the application of ERS to both benchmark and real-world datasets are reported. Clustering results can be compared, for accuracy and execution time performance, to the use of the basic RS algorithm. Clustering quality is also checked with the application of other known algorithms.