Local vs global interactions in clustering algorithms: Advances over K-means

Article type: Research Article

Authors: Barbakh, Wesam | Fyfe, Colin

Affiliations: The University of Paisley, Scotland. E-mail: wesam.barbakh@paisley.ac.uk, colin.fyfe@paisley.ac.uk

Abstract: We discuss one of the shortcomings of the standard K-means algorithm – its tendency to converge to a local rather than a global optimum. This is often accommodated by means of different random restarts of the algorithm, however in this paper, we attack the problem by amending the performance function of the algorithm in such a way as to incorporate global information into the performance function. We do this in three different manners and show on artificial data sets that the resulting algorithms are less initialisation-dependent than the standard K-means algorithm. We also show how to create a family of topology-preserving manifolds using these algorithms and an underlying constraint on the positioning of the prototypes.

DOI: 10.3233/KES-2008-12201

Journal: International Journal of Knowledge-based and Intelligent Engineering Systems, vol. 12, no. 2, pp. 83-99, 2008