DILS: Constrained clustering through dual iterative local search

TitleDILS: Constrained clustering through dual iterative local search
Publication TypeJournal Article
Year of Publication2020
AuthorsGonzález-Almagro, Germán, Luengo Julián, Cano J. R., and García Salvador
JournalComputers & Operations Research
Volume121
Pagination104979
KeywordsCannot-link, constrained clustering, Dual iterative local search, Instance-level, Must-link
Abstract

Clustering has always been a powerful tool in knowledge discovery. Traditionally unsupervised, it has received renewed attention recently as it has shown to produce better results when provided with new types of information, thus leading to a new kind of semi-supervised learning: constrained clustering. This technique is a generalization of traditional clustering that considers additional information encoded by constraints. Constraints can be given in the form of instance-level must-link and cannot-link constraints, which is the focus of this paper. We propose a new metaheuristic algorithm, the Dual Iterative Local Search, and prove its ability to produce quality results for the constrained clustering problem. We compare the results obtained by this proposal to those obtained by the state-of-the-art algorithms on 25 datasets with incremental levels of constraint-based information, supporting our conclusions with the aid of Bayesian statistical tests.

Notes

TIN2017- 89517-P; PP2016.PRI.I.02.

DOI10.1016/j.cor.2020.104979