Groupe d’études et de recherche en analyse des décisions

G-2019-96

A Lagrangian-based score for assessing the quality of pairwise constraints in SSC

, , et

Les algorithmes de partitionnement de données aident à identifier des sous-groupes homogènes en ce sens que les données de chaque groupe partagent des caractéristiques communes. Dans certains cas, on dispose d'information supplémentaire sur la relation entre certains sous-ensembles de données. Par exemple, lors de l'utilisation d'un algorithme de partitionnement semi-supervisé, un expert peut fournir des informations supplémentaires pour contraindre la solution recherchée en fonction de ses connaissances et guider ainsi l'algorithme vers une solution plus significative. L'expert peut ainsi spécifier des contraintes par paires en ce sens qu'il peut imposer que deux points ne fassent pas partie d'un même groupe ou, qu'au contraire, ces deux points doivent impérativement faire partie d'un même groupe. Un défi majeur pour les utilisateurs d'algorithmes d'apprentissage semi-supervisés, cependant, est que l'ajout de contraintes inexactes ou conflictuelles peut diminuer la précision du partitionnement généré et on sait peu de choses sur la façon de détecter si les contraintes imposées par des experts sont éventuellement erronées. Dans le présent travail, nous proposons une méthode permettant d'évaluer individuellement chacune des contraintes par paires et aider ainsi les utilisateurs à identifier celles qui doivent être modifiées ou supprimées. À l'aide d'exemples expérimentaux synthétiques et de données réelles, nous montrons que la méthode d'évaluation proposée permet d'identifier avec succès les contraintes erronées.

, 20 pages