Review of Basic Local Searches for Solving the Minimum Sum-of-Squares Clustering Problem

Thiago Pereira, Daniel Aloise (), Jack Brimberg and Nenad Mladenović
Additional contact information
Thiago Pereira: Universidade Federal do Rio Grande do Norte
Daniel Aloise: Polytechnique Montréal
Jack Brimberg: The Royal Military College of Canada
Nenad Mladenović: Emirates College of Technologies

A chapter in Open Problems in Optimization and Data Analysis, 2018, pp 249-270 from Springer

Abstract: Abstract This paper presents a review of the well-known K-means, H-means, and J-means heuristics, and their variants, that are used to solve the minimum sum-of-squares clustering problem. We then develop two new local searches that combine these heuristics in a nested and sequential structure, also referred to as variable neighborhood descent. In order to show how these local searches can be implemented within a metaheuristic framework, we apply the new heuristics in the local improvement step of two variable neighborhood search (VNS) procedures. Computational experiments are carried out which suggest that this new and simple application of VNS is comparable to the state of the art. In addition, a very significant improvement (over 30%) in solution quality is obtained for the largest problem instance investigated containing 85,900 entities.

Keywords: Clustering; Minimum sum-of-squares; VNS; K-means (search for similar items in EconPapers)
Date: 2018
References: Add references at CitEc
Citations: View citations in EconPapers (1)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:spochp:978-3-319-99142-9_13

Ordering information: This item can be ordered from
http://www.springer.com/9783319991429

DOI: 10.1007/978-3-319-99142-9_13

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().