Avoiding Local Minima in Overlap-Based Clustering by Random Swap

Abstract

Context: Cluster overlap has been recently introduced as an alternative objective function to the traditional sum-of-squared error (SSE) function used in k-means. It estimates the overlap by counting how many points are shared between the neighbor clusters. The overlap k-means was shown to provide more stable centroid locations than SSE, but at the cost of losing the dynamics of the k-means algorithm. Objective: In this paper, we address this drawback by adding a random swap step to the algorithm and introducing a new Overlap random swap. Method: It consists of three steps: (1) selective replacement of the centroids, (2) standard cluster assignment step, (3) weighted centroid calculation giving less weight to the overlapping points. Results: Experimental results confirm that ORS achieves competitive clustering accuracy, stable centroid locations, and improved boundary separation. The clustering accuracy (ACC) is about 95% and the centroid index (CI) is about 0.1. The algorithm converges within 3000 swap iterations. Conclusions: These results indicate that ORS helps avoid local minima and maintains the robustness of overlap-based clustering.