Authors: Hansen, Pierre
Mladenović, Nenad 
Title: J-Means: a new local search heuristic for minimum sum of squares clustering
Journal: Pattern Recognition
Volume: 34
Issue: 2
First page: 405
Last page: 413
Issue Date: 1-Jan-2001
Rank: M21
ISSN: 0031-3203
DOI: 10.1016/S0031-3203(99)00216-2
A new local search heuristic, called J-Means, is proposed for solving the minimum sum of squares clustering problem. The neighborhood of the current solution is defined by all possible centroid-to-entity relocations followed by corresponding changes of assignments. Moves are made in such neighborhoods until a local optimum is reached. The new heuristic is compared with two other well-known local search heuristics, K- and H-Means as well as with H-Means +, an improved version of the latter in which degeneracy is removed. Moreover, another heuristic, which fits into the variable neighborhood search metaheuristic framework and uses J-Means in its local search step, is proposed too. Results on standard test problems from the literature are reported. It appears that J-Means outperforms the other local search methods, quite substantially when many entities and clusters are considered.
Publisher: Elsevier

Show full item record


checked on May 18, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.