|
![](images/spacer.gif) |
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 dobjets doivent être (respectivement, ne doivent pas être) dans le même cluster. Dautres 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é linté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 dajouter facilement de nouvelles contraintes, la capacité à énumérer toutes les solutions satisfaisant les contraintes et la capacité, dans le cas de loptimisation dun critère, à trouver une solution optimale satisfaisant toutes les contraintes (sil en existe une).
Dans cet exposé, nous ne considérons que lapprentissage de partitions et nous donnons deux exemples de lutilisation 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. |
|
|