Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/25569
Title: Analysis of global k-means, an incremental heuristic for minimum sum-of-squares clustering
Authors: Hansen, P
Ngai, E 
Cheung, BK
Mladenovic, N
Keywords: Clustering
Global k-means
J-means
K-means
Minimum sum-of-squares
Issue Date: 2005
Publisher: Springer
Source: Journal of classification, 2005, v. 22, no. 2, p. 287-310 How to cite?
Journal: Journal of classification 
Abstract: 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.
URI: http://hdl.handle.net/10397/25569
ISSN: 0176-4268
EISSN: 1432-1343
DOI: 10.1007/s00357-005-0018-3
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

29
Last Week
0
Last month
0
Citations as of Apr 11, 2018

WEB OF SCIENCETM
Citations

21
Last Week
0
Last month
0
Citations as of Apr 17, 2018

Page view(s)

79
Last Week
3
Last month
Citations as of Apr 16, 2018

Google ScholarTM

Check

Altmetric


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