K-Medoids For K-Means Seeding

We show experimentally that the algorithm clarans of Ng and Han (1994) finds better K -medoids solutions than the V oronoi iteration algorithm of Hastie et al. (2001). This finding, along with the similarity between the V oronoi iteration algorithm and Lloyd's K -means algorithm, motivates us to use clarans as a K -means initializer. We show that clarans outperforms other algorithms on 23/23 datasets with a mean decrease over k-means-++ (Arthur and V assilvitskii, 2007) of 30% for initialization mean squared error (MSE) and 3% for final MSE. We introduce algorithmic improvements to clarans which improve its complexity and runtime, making it a viable initialization scheme for large datasets.