The Euclidean Minimum Sum-of-Squares Clustering (MSSC) is one of the most important models for the clustering problem. Due to its NP-hardness, the problem continues to receive much attention in the scientific literature and several heuristic procedures have been proposed. Recent research has been devoted to the improvement of the classical K-MEANS algorithm, either by suitably selecting its starting configuration or by using it as a local search method within a global optimization algorithm. This paper follows this last approach by proposing a new implementation of a Memetic Differential Evolution (MDE) algorithm specifically designed for the MSSC problem and based on the repeated execution of K-MEANS from selected configurations. In this paper we describe how to adapt MDE to the clustering problem and we show, through a vast set of numerical experiments, that the proposed method has very good quality, measured in terms of the minimization of the objective function, as well as a very good efficiency, measured in the number of calls to the local optimization routine, with respect to state of the art methods.
Memetic Differential Evolution methods for Clustering Problems / Mansueto Pierluigi; Schoen Fabio. - In: PATTERN RECOGNITION. - ISSN 0031-3203. - STAMPA. - 114:(2021), pp. 1-37. [10.1016/j.patcog.2021.107849]
Memetic Differential Evolution methods for Clustering Problems
Mansueto Pierluigi;Schoen Fabio
2021
Abstract
The Euclidean Minimum Sum-of-Squares Clustering (MSSC) is one of the most important models for the clustering problem. Due to its NP-hardness, the problem continues to receive much attention in the scientific literature and several heuristic procedures have been proposed. Recent research has been devoted to the improvement of the classical K-MEANS algorithm, either by suitably selecting its starting configuration or by using it as a local search method within a global optimization algorithm. This paper follows this last approach by proposing a new implementation of a Memetic Differential Evolution (MDE) algorithm specifically designed for the MSSC problem and based on the repeated execution of K-MEANS from selected configurations. In this paper we describe how to adapt MDE to the clustering problem and we show, through a vast set of numerical experiments, that the proposed method has very good quality, measured in terms of the minimization of the objective function, as well as a very good efficiency, measured in the number of calls to the local optimization routine, with respect to state of the art methods.File | Dimensione | Formato | |
---|---|---|---|
1-s2.0-S0031320321000364-main.pdf
Accesso chiuso
Tipologia:
Pdf editoriale (Version of record)
Licenza:
Tutti i diritti riservati
Dimensione
2.76 MB
Formato
Adobe PDF
|
2.76 MB | Adobe PDF | Richiedi una copia |
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.