Authors: Aloise, Daniel
Damasceno, Nielsen Castelo
Mladenović, Nenad 
Pinheiro, Daniel Nobre
Title: On Strategies to Fix Degenerate k-means Solutions
Journal: Journal of Classification
Volume: 34
Issue: 2
First page: 165
Last page: 190
Issue Date: 1-Jul-2017
Rank: M21a
ISSN: 01764268
DOI: 10.1007/s00357-017-9231-0
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: Clustering | Degeneracy | Heuristics | k-means | Minimum sum-of-squares
Publisher: Springer Link

Show full item record


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