DROPS

Document

DOI: 10.4230/LIPIcs.CP.2023.10

Incremental Constrained Clustering by Minimal Weighted Modification

Authors: Aymeric Beauchamp, Thi-Bich-Hanh Dao, Samir Loudni, and Christel Vrain

Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)

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.

Cite as

Aymeric Beauchamp, Thi-Bich-Hanh Dao, Samir Loudni, and Christel Vrain. Incremental Constrained Clustering by Minimal Weighted Modification. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 10:1-10:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.CP.2023.10},
  URN =		{urn:nbn:de:0030-drops-190478},
  doi =		{10.4230/LIPIcs.CP.2023.10},
  annote =	{Keywords: Incremental constrained clustering, Constrained optimization problem, User feedback}
}

Search Results

Documents authored by Beauchamp, Aymeric

Incremental Constrained Clustering by Minimal Weighted Modification

Abstract

Cite as

Thanks for your feedback!

Could not send message