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: https://drops.dagstuhl.de/opus/volltexte/2023/19047/
Go to the corresponding LIPIcs Volume Portal


Beauchamp, Aymeric ; Dao, Thi-Bich-Hanh ; Loudni, Samir ; Vrain, Christel

Incremental Constrained Clustering by Minimal Weighted Modification

pdf-format:
LIPIcs-CP-2023-10.pdf (5 MB)


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}
}

Keywords: Incremental constrained clustering, Constrained optimization problem, User feedback
Collection: 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)
Issue Date: 2023
Date of publication: 22.09.2023
Supplementary Material: Software (Source Code): https://github.com/aymericb213/IAC archived at: https://archive.softwareheritage.org/swh:1:dir:8f611496af5ad016912ca3d55379b50b36541f89


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI