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

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.

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.