Memetic differential evolution methods for clustering problems

Pierluigi Mansueto

doi:10.1016/j.patcog.2021.107849

Return

Memetic differential evolution methods for clustering problems

2021-06-01

PRE

Pierluigi Mansueto

Fabio Schoen *

DOI：10.1016/j.patcog.2021.107849

Original

Original request for help

Save

Abstract

En 中文

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. (c) 2021 Elsevier Ltd. All rights reserved.

Keywords:

Global optimization

Clustering

Minimum sum-of-squares

Hybrid genetic algorithm

K-MEANS