Clustering contrainté incrémental par modification pondérée minimale

Le regroupement (clustering) est une tâche bien établie en fouille de données, visant à organiser les instances de données en groupes selon leur similarité. Il s’agit d’une tâche exploratoire et non supervisée, dont les résultats dépendent de nombreux paramètres, nécessitant souvent plusieurs itérations de la part de l’expert avant d’atteindre une satisfaction. Le clustering contraint a été introduit afin de mieux modéliser les attentes de l’expert. Toutefois, ce cadre reste insuffisant, car il suppose généralement que les contraintes soient fournies avant le démarrage du processus de regroupement. Dans cet article, nous abordons un problème plus général, visant à modéliser le processus exploratoire de clustering à travers une séquence de modifications itératives, durant lesquelles des contraintes provenant de l’expert sont ajoutées dynamiquement. Nous proposons un cadre de clustering contraint incrémental intégrant des stratégies d’interrogation active et un modèle de programmation par contraintes, permettant de s’adapter aux attentes de l’expert tout en préservant la stabilité de la partition, afin que celui-ci puisse comprendre le processus et appréhender son impact. Notre modèle prend en charge à la fois des contraintes au niveau des instances et au niveau des groupes, pouvant être relâchées si nécessaire. Des expériences menées sur des jeux de données standards ainsi qu’une étude de cas portant sur l’analyse de séries temporelles d’images satellitaires démontrent la pertinence de notre approche.