Réinitialiser mot de passe
E-mail
Password
RNTI

MODULAD
Découverte de sous-groupes avec les arbres de recherche de Monte Carlo
In EGC 2017, vol. RNTI-E-33, pp.273-284
Résumé
Découvrir des règles qui distinguent clairement une classe d'une autre
reste un problème difficile. De tels motifs permettent de suggérer des hypothèses
pouvant expliquer une classe. La découverte de sous-groupes (Subgroup Disco-
very, SD), un cadre qui définit formellement cette tâche d'extraction de motifs,
est toujours confrontée à deux problèmes majeurs: (i) définir des mesures de
qualité appropriées qui caractérisent la singularité d'un motif et (ii) choisir une
heuristique d'exploration de l'espace de recherche correcte lorsqu'une énuméra-
tion complète est irréalisable. À ce jour, les algorithmes de SD les plus efficaces
sont basés sur une recherche en faisceau (Beam Search, BS). La collection de
motifs extraits manque cependant de diversité en raison de la nature gloutonne de
l'exploration. Nous proposons ici d'utiliser une technique d'exploration récente,
la recherche arborescente de Monte Carlo (Monte Carlo Tree Search, MCTS).
Le compromis entre l'exploitation et l'exploration ainsi que la puissance de la
recherche aléatoire permettent d'obtenir une solution disponible à tout moment
et de surpasser généralement les approches de type BS. Notre étude empirique,
avec plusieurs mesures de qualité, sur divers jeux de données de référence et du
monde réel démontre la qualité de notre approche.