Refining K-means Algorithm by Detecting Superfluous and Oversized Clusters

Abstract

In this paper we present a novel heuristic approach that increases the accuracy of the K-means algorithm. K-means is a widely used iterative clustering algorithm but usually converges to a local best solution away from the optimal one. While some of the resulting clusters may include more than one natural cluster, some others may not correspond to any natural cluster. After several K-means iterations, clusters of each type are heuristically located in the proposed algorithm. The cluster of latter type is removed and a new cluster is introduced in the cluster of former type. Experimental results show that, our approach not only improves the results produced by the state of art K-means methods if it is employed as post process, but also outperforms them when initialized randomly.