Efficiently Solving Semi-supervised Clustering Problems Through Differential Evolution and Local Optimization

Abstract We propose an innovative algorithm for clustering problems with additional constraints specifying that selected pairs must or must not belong to the same cluster. Few methods have been proposed for this relevant extension. We propose, for the first time according to our knowledge, a memetic optimization framework exploiting a specialized local search algorithm. A clever use of local searches coupled with an exploration phase based on differential evolution makes our algorithm extremely efficient and effective in detecting very good feasible clusters. Our approach originates from a framework proposed in the unsupervised setting and presents several innovative extensions, like the definition of exact and greedy procedures to assign points to clusters (a nontrivial step in this problem) and the possibility of temporarily generating infeasible solutions. A wide set of numerical experiments confirms that mixing differential evolution with local optimization leads to significantly superior results with respect to the current literature.