NeurIPS 2017spotlight42 citations
K-Medoids For K-Means Seeding
James Newling, François Fleuret
Abstract
We show experimentally that the algorithm CLARANS of Ng and Han (1994) finds better K-medoids solutions than the Voronoi iteration algorithm of Hastie et al. (2001). This finding, along with the similarity between the Voronoi 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++ 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.
BibTeX
@inproceedings{NIPS2017_a8345c3b,
author = {Newling, James and Fleuret, Fran\c{c}ois},
booktitle = {Advances in Neural Information Processing Systems},
editor = {I. Guyon and U. Von Luxburg and S. Bengio and H. Wallach and R. Fergus and S. Vishwanathan and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {K-Medoids For K-Means Seeding},
url = {https://proceedings.neurips.cc/paper_files/paper/2017/file/a8345c3bb9e3896ea538ce77ffaf2c20-Paper.pdf},
volume = {30},
year = {2017}
}