Buscar

Estamos realizando la búsqueda. Por favor, espere...

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.

 Fuente: Information Sciences, 2018, 439-440, 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

 Proyecto español: MTM2014-55262-P

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