Jeudi 1 Octobre


Retour à la vue des calendrier
Jeudi 1 Octobre
Heure: 12:15 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Clustering sous contraintes en Programmation par Contraintes
Description: Christel Vrain La classification non supervisée sous contraintes (aussi appelée clustering sous contraintes) est une tâche importante de fouille de données, permettant de modéliser plus finement une tâche de clustering en intégrant des contraintes utilisateur. Divers types de contraintes peuvent être considérés ; les contraintes les plus courantes sont les contraintes must-link (ML) ou cannot-link (CL) spécifiant que des paires d’objets doivent être (respectivement, ne doivent pas être) dans le même cluster. D’autres contraintes peuvent aussi être posées sur les clusters, précisant par exemple, une borne sur leur diamètre ou sur leur taille. Néanmoins, concevoir un algorithme capable de traiter différents types de contraintes est difficile et la plupart des approches tendent à étendre les méthodes classiques de clustering en intégrant un unique type de contraintes.

Plusieurs travaux ont montré l’intérêt de la Programmation par Contraintes (PPC) pour la fouille de données. Modéliser en PPC a deux avantages : la déclarativité qui permet d’ajouter facilement de nouvelles contraintes, la capacité à énumérer toutes les solutions satisfaisant les contraintes et la capacité, dans le cas de l’optimisation d’un critère, à trouver une solution optimale satisfaisant toutes les contraintes (s’il en existe une).

Dans cet exposé, nous ne considérons que l’apprentissage de partitions et nous donnons deux exemples de l’utilisation de la Programmation par Contraintes pour le clustering sous contraintes. Le premier exemple, proposé par [T. Guns, S. Nijssen, .L De Raedt] modélise le clustering conceptuel : les données sont décrites par leurs propriétés et à chaque cluster est associé un motif, i.e, un ensemble de propriétés que toutes les données du cluster satisfont. Dans le second exemple, issu de nos travaux [T.B. H. Dao, K.C. Duong, C. Vrain], un cadre déclaratif et générique permet de modéliser différentes tâches de clustering sous contraintes, étant donnée une mesure de dissimilarité entre les objets.