Authors: Hansen, Pierre
Ngai, Eric
Cheung, Bernard K.
Mladenović, Nenad 
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: Analysis of global k-means, an incremental heuristic for minimum sum-of-squares clustering
Journal: Journal of Classification
Volume: 22
Issue: 2
First page: 287
Last page: 310
Issue Date: 1-Jan-2005
Rank: M22
ISSN: 0176-4268
DOI: 10.1007/s00357-005-0018-3
The global k-means heuristic is a recently proposed (Likas, Vlassis and Verbeek, 2003) incremental approach for minimum sum-of-squares clustering of a set X of N points of Rd into M clusters. For k = 2,3,..., M - 1 it considers the best-known set of k - 1 centroids previously obtained, adds a new cluster center at each point of X in turn and applies k-means to each set of k centroids so-obtained, keeping the best k-partition found. We show that global k-means cannot be guaranteed to find the optimum partition for any M ≥ 2 and d ≥ 1; moreover, the same holds for all M ≥ 3 if the new cluster center is chosen anywhere in Rd instead of belonging to X. The empirical performance of global k-means is also evaluated by comparing the values it obtains with those obtained for three data sets with N ≤ 150 which are solved optimally, as well as with values obtained by the recent j-means heuristic and extensions thereof for three larger data sets with N ≤ 3038.
Keywords: Clustering | Global k-means | J-means | K-means | Minimum sum-of-squares
Publisher: Springer Link

Show full item record


checked on May 16, 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.