k*-means:: A new generalized k-means clustering algorithm

This paper presents a generalized version of the conventional k-means clustering algorithm [Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability, 1, University of California Press, Berkeley, 1967, p. 281]. Not only is this new one applicable to ellipse-shaped data clusters without dead-unit problem, but also performs correct clustering without pre-assigning the exact cluster number. We qualitatively analyze its underlying mechanism, and show its outstanding performance through the experiments. (C) 2003 Elsevier B.V. All rights reserved.