  We run experiments showing that algorithm clarans (Ng et al., 2005) finds
better K-medoids solutions than the Voronoi iteration algorithm. This finding,
along with the similarity between the Voronoi iteration algorithm and Lloyd's
K-means algorithm, suggests that clarans may be an effective K-means
initializer. We show that this is the case, with clarans outperforming other
seeding algorithms on 23/23 datasets with a mean decrease over K-means++ of 30%
for initialization mse and 3% or final mse. We describe how the complexity and
runtime of clarans can be improved, making it a viable initialization scheme
for large datasets.
