Cheung, Bernard K.
|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||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.
|Keywords:||Clustering | Global k-means | J-means | K-means | Minimum sum-of-squares||Publisher:||Springer Link|
Show full item record
checked on Dec 2, 2021
checked on Dec 3, 2021
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.