Centre de documentation
scientifique

Constrained clustering by constraint programming / Thi-Bich-Hanh Dao in Artificial intelligence, vol 244 (March 2017)  

Public [article]  inArtificial intelligence > vol 244 (March 2017) . - pp 70 - 94 Titre : Constrained clustering by constraint programming Type de document : Article/Communication Auteurs : Thi-Bich-Hanh Dao, Auteur ; Khanh-Chuong Duong, Auteur ; Christel Vrain, Auteur Année de publication : 2017 Article en page(s) : pp 70 - 94 Note générale : bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Intelligence artificielle [Termes IGN] analyse de groupement [Termes IGN] filtrage d'information [Termes IGN] modélisation [Termes IGN] optimisation (mathématiques) [Termes IGN] programmation par contraintes Résumé : (auteur) Constrained Clustering allows to make the clustering task more accurate by integrating user constraints, which can be instance-level or cluster-level constraints. Few works consider the integration of different kinds of constraints, they are usually based on declarative frameworks and they are often exact methods, which either enumerate all the solutions satisfying the user constraints, or find a global optimum when an optimization criterion is specified. In a previous work, we have proposed a model for Constrained Clustering based on a Constraint Programming framework. It is declarative, allowing a user to integrate user constraints and to choose an optimization criterion among several ones. In this article we present a new and substantially improved model for Constrained Clustering, still based on a Constraint Programming framework. It differs from our earlier model in the way partitions are represented by means of variables and constraints. It is also more flexible since the number of clusters does not need to be set beforehand; only a lower and an upper bound on the number of clusters have to be provided. In order to make the model-based approach more efficient, we propose new global optimization constraints with dedicated filtering algorithms. We show that such a framework can easily be embedded in a more general process and we illustrate this on the problem of finding the optimal Pareto front of a bi-criterion constrained clustering task. We compare our approach with existing exact approaches, based either on a branch-and-bound approach or on graph coloring on twelve datasets. Experiments show that the model outperforms exact approaches in most cases. Numéro de notice : A2017-566 Affiliation des auteurs : non IGN Thématique : GEOMATIQUE/INFORMATIQUE Nature : Article nature-HAL : ArtAvecCL-RevueIntern DOI : 10.1016/j.artint.2015.05.006 En ligne : https://doi.org/10.1016/j.artint.2015.05.006 Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=86680 [article]