License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2023.10
URN: urn:nbn:de:0030-drops-190478
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19047/
Beauchamp, Aymeric ;
Dao, Thi-Bich-Hanh ;
Loudni, Samir ;
Vrain, Christel
Incremental Constrained Clustering by Minimal Weighted Modification
Abstract
Clustering is a well-known task in Data Mining that aims at grouping data instances according to their similarity. It is an exploratory and unsupervised task whose results depend on many parameters, often requiring the expert to iterate several times before satisfaction. Constrained clustering has been introduced for better modeling the expectations of the expert. Nevertheless constrained clustering is not yet sufficient since it usually requires the constraints to be given before the clustering process. In this paper we address a more general problem that aims at modeling the exploratory clustering process, through a sequence of clustering modifications where expert constraints are added on the fly. We present an incremental constrained clustering framework integrating active query strategies and a Constraint Programming model to fit the expert expectations while preserving the stability of the partition, so that the expert can understand the process and apprehend its impact. Our model supports instance and group-level constraints, which can be relaxed. Experiments on reference datasets and a case study related to the analysis of satellite image time series show the relevance of our framework.
BibTeX - Entry
@InProceedings{beauchamp_et_al:LIPIcs.CP.2023.10,
author = {Beauchamp, Aymeric and Dao, Thi-Bich-Hanh and Loudni, Samir and Vrain, Christel},
title = {{Incremental Constrained Clustering by Minimal Weighted Modification}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {10:1--10:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-300-3},
ISSN = {1868-8969},
year = {2023},
volume = {280},
editor = {Yap, Roland H. C.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/19047},
URN = {urn:nbn:de:0030-drops-190478},
doi = {10.4230/LIPIcs.CP.2023.10},
annote = {Keywords: Incremental constrained clustering, Constrained optimization problem, User feedback}
}
