To access the full text documents, please follow this link: http://hdl.handle.net/2117/116585

Global optimality in k-means clustering
Tîrnauca, Cristina; Gómez Pérez, Domingo; Balcázar Navarro, José Luis; Montaña Arnaiz, José Luis
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació; Universitat Politècnica de Catalunya. LARCA - Laboratori d'Algorísmia Relacional, Complexitat i Aprenentatge
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.
Peer Reviewed
-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica
-Cluster analysis
-Algorithms
-Clustering
-Voronoi diagrams
-Cell arrangement
-Anàlisi de conglomerats
-Algorismes
Attribution-NonCommercial-NoDerivs 3.0 Spain
http://creativecommons.org/licenses/by-nc-nd/3.0/es/
Article - Submitted version
Article
         

Show full item record

Related documents

Other documents of the same author

Arias Vicente, Marta; Balcázar Navarro, José Luis; Tîrnauca, Cristina
Balcázar Navarro, José Luis; Tirnauca, Cristina
Balcázar Navarro, José Luis; Tirnauca, Cristina
Balcázar Navarro, José Luis; Tirnauca, Cristina; Zorrilla Pantaleón, Marta Elena
 

Coordination

 

Supporters