Global optimality in k-means clustering

Abstract: Abstract: We study the problem of finding an optimum clustering, a problem known to be NP-hard. Existing literature contains algorithms running in time proportional to the number of points raised to a power that depends on the dimensionality and on the number of clusters. Published validations of some of these algorithms are unfortunately incomplete; besides, the constant factors (with respect to the number of points) in their running time bounds have seen several published important improvements but are still huge, exponential on the dimension and on the number of clusters, making the corresponding algorithms fully impractical. We provide a new algorithm, with its corresponding complexity-theoretic analysis. It reduces both the exponent and the constant factor, to the extent that it becomes feasible for relevant particular cases. Additionally, it parallelizes extremely well, so that its implementation on current high-performance hardware is quite straightforward. Our proposal opens the door to potential improvements along a research line that had no practical significance so far; besides, a long but single-shot run of our algorithm allows one to identify absolutely optimum solutions for benchmark problems, whereby alternative heuristic proposals can evaluate the goodness of their solutions and the precise price paid for their faster running times.

Otras publicaciones de la misma revista o congreso con autores/as de la Universidad de Cantabria

 Fuente: Information Sciences, Volumes 439-440, May 2018, Pages 79-94

Editorial: Elsevier

 Fecha de publicación: 01/05/2018

Nº de páginas: 39

Tipo de publicación: Artículo de Revista

DOI: 10.1016/j.ins.2018.02.001

ISSN: 0020-0255,1872-6291

Url de la publicación: https://doi.org/10.1016/j.ins.2018.02.001