On Strategies to Fix Degenerate k-means Solutions

Daniel Aloise (), Nielsen Castelo Damasceno, Nenad Mladenović and Daniel Nobre Pinheiro
Additional contact information
Daniel Aloise: Polytechnique Montréal
Nielsen Castelo Damasceno: Federal University of Rio Grande do Norte
Nenad Mladenović: LAMIH, Université de Valenciennes et du Hainaut Cambrésis
Daniel Nobre Pinheiro: Federal University of Rio Grande do Norte

Journal of Classification, 2017, vol. 34, issue 2, No 2, 165-190

Abstract: Abstract k-means is a benchmark algorithm used in cluster analysis. It belongs to the large category of heuristics based on location-allocation steps that alternately locate cluster centers and allocate data points to them until no further improvement is possible. Such heuristics are known to suffer from a phenomenon called degeneracy in which some of the clusters are empty. In this paper, we compare and propose a series of strategies to circumvent degenerate solutions during a k-means execution. Our computational experiments show that these strategies are effective, leading to better clustering solutions in the vast majority of the cases in which degeneracy appears in k-means. Moreover, we compare the use of our fixing strategies within k-means against the use of two initialization methods found in the literature. These results demonstrate how useful the proposed strategies can be, specially inside memorybased clustering algorithms.

Keywords: k-means; Minimum sum-of-squares; Degeneracy; Clustering; Heuristics (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s00357-017-9231-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jclass:v:34:y:2017:i:2:d:10.1007_s00357-017-9231-0

Ordering information: This journal article can be ordered from
http://www.springer. ... hods/journal/357/PS2

DOI: 10.1007/s00357-017-9231-0

Access Statistics for this article

Journal of Classification is currently edited by Douglas Steinley

More articles in Journal of Classification from Springer, The Classification Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().