Best of Both: A Hybridized Centroid-Medoid Clustering Heuristic

Best of Both: A Hybridized Centroid-Medoid Clustering Heuristic
Nizar Grira - National Institute of Informatics, Japan Michael E. Houle - National Institute of Informatics, Japan
Although each iteration of the popular k Means clustering heuristic scales well to larger problem sizes, it often requires an unacceptably-high number of iterations to converge to a solution. This paper introduces an enhancement of k -Means in which local search is used to accelerate convergence without greatly increasing the average computational cost of the iterations. The local search involves a carefully-controlled number of swap operations resembling those of the more robust k -Medoids clustering heuristic. We show empirically that the proposed method improves convergence results when compared to standard k -Means.

Nizar Grira - National Institute of Informatics, Japan
Michael E. Houle - National Institute of Informatics, Japan

Although each iteration of the popular k Means clustering heuristic scales well to larger problem sizes, it often requires an unacceptably-high number of iterations to converge to a solution. This paper introduces an enhancement of k -Means in which local search is used to accelerate convergence without greatly increasing the average computational cost of the iterations. The local search involves a carefully-controlled number of swap operations resembling those of the more robust k -Medoids clustering heuristic. We show empirically that the proposed method improves convergence results when compared to standard k -Means.