A new local search heuristic, called J-MEANS, is proposed for solving the m
inimum sum of squares clustering problem. The neighborhood of the current s
olution is defined by all possible centroid-to-entity relocations followed
by corresponding changes of assignments. Moves are made in such neighborhoo
ds 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 sea
rch metaheuristic framework and uses J-MEANS in its local search step, is p
roposed too. Results on standard test problems from the literature are repo
rted. It appears that J-MEANS outperforms the other local search methods, q
uite substantially when many entities and clusters are considered. (C) 2000
Pattern Recognition Society. Published by Elsevier Science Ltd. All rights
reserved.