<  Retour au portail Polytechnique Montréal

Résolution exacte du problème de partitionnement de données avec minimisation de variance sous contraintes de cardinalité par programmation par contraintes

Mohammed Najib Haouas

Mémoire de maîtrise (2020)

Document en libre accès dans PolyPublie
[img]
Affichage préliminaire
Libre accès au plein texte de ce document
Conditions d'utilisation: Tous droits réservés
Télécharger (2MB)
Afficher le résumé
Cacher le résumé

Résumé

Le partitionnement de données représente une procédure destinée à regrouper un ensemble d'observations dans plusieurs sous ensembles homogènes et/ou bien séparés. L'idée derrière une telle activité est de simplifier l'extraction d'information utile en étudiant les groupes résultants plutôt que les observations elles-mêmes. Cela dit, plusieurs situations appellent à ce que la solution générée respecte un ensemble de contraintes données. En particulier, on exige parfois que les groupes résultants comportent un nombre prédéfini d'éléments. On parle de partitionnement avec contraintes de cardinalité. On présente alors, dans ce travail, une approche de résolution exacte pour le partitionnement de données avec minimisation de la variance sous contraintes de cardinalité. En utilisant le paradigme de la Programmation par Contraintes, on propose d'abord un modèle adéquat du problème selon celui-ci. Ensuite, on suggère à la fois une stratégie de recherche rehaussée ainsi que deux algorithmes de filtrage. Ces outils ainsi développés tirent avantage de la structure particulière du problème afin de naviguer l'espace de recherche de façon efficace, à la recherche d'une solution globalement optimale. Des expérimentations pratiques montrent que notre approche procure un avantage important par rapport aux autres méthodes exactes existantes lors de la résolution de plusieurs exemplaires du problème.

Abstract

Data clustering is a procedure designed to group a set of observations into subsets that are homogeneous and/or well separated. The idea behind such an endeavor is to simplify extraction of useful information by studying the resulting groups instead of directly dealing with the observations themselves. However, many situations mandate that the answer conform to a set of constraints. Particularly one that involves the target number of elements each group must possess. This is known as cardinality constrained clustering. In this work we present an exact approach to solve the cardinality constrained Euclidian minimum sum-of-squares clustering. Based on the Constraint Programming paradigm, we first present an adequate model for this problem in the aforementioned framework. We then suggest both an upgraded search heuristic as well as two filtering algorithms. We take advantage of the structure of the problem in designing these tools to efficiently navigate the search space, looking for a globally optimal solution. Computational experiments show that our approach provides a substantial boost to the resolution of several instances of the problem in comparison to existing exact methods.

Département: Département de génie informatique et génie logiciel
Programme: Génie informatique
Directeurs ou directrices: Gilles Pesant et Daniel Aloise
URL de PolyPublie: https://publications.polymtl.ca/4207/
Université/École: Polytechnique Montréal
Date du dépôt: 25 août 2020 09:44
Dernière modification: 01 août 2023 08:02
Citer en APA 7: Haouas, M. N. (2020). Résolution exacte du problème de partitionnement de données avec minimisation de variance sous contraintes de cardinalité par programmation par contraintes [Mémoire de maîtrise, Polytechnique Montréal]. PolyPublie. https://publications.polymtl.ca/4207/

Statistiques

Total des téléchargements à partir de PolyPublie

Téléchargements par année

Provenance des téléchargements

Actions réservées au personnel

Afficher document Afficher document