Jean-François Boulicaut Equipe DM2L, LIRIS, UMR CNRS 5205 INSA de Lyon

Depuis une vingtaine d’années, nous travaillons au LIRIS à la fouille de nombreux types de données (matrices ou tenseurs, séquences d’événements, graphes éventuellement attribués et/ou dynamiques) pour le calcul efficace de collections de motifs (ensembles d’entités, séquences, sous-arbres ou sous-graphes) qui satisfont des types de contraintes variés et donc non limitées à la classique fréquence minimale. Nous avons une expertise spécifique sur le développement d’algorithmes génériques exhaustifs : tous les motifs qui satisfont les contraintes, et eux seulement, sont retournés. La généricité vient de l’exploitation des propriétés des contraintes pour obtenir des énumérations complètes faisables.

Plus récemment, nous nous sommes intéressés à la fouille de données étiquetées. Par exemple, la découverte de sous-groupes consiste à calculer des motifs qui caractérisent des sous-ensembles d’objets ayant une répartition des valeurs de classes remarquables. La découverte de sous-groupes est très souvent hors d’atteinte des méthodes exhaustives et dans ce séminaire, nous voulons présenter deux des résultats récemment obtenus au cours des études doctorales de Guillaume Bosc et Romain Mathonat sous les directions de Mehdi Kaytoue et de moi-même.

Nous présentons d’abord un travail sur la découverte de sous-groupes à partir de données séquentielles (séquences d’itemsets) par échantillonnage puis optimisation locale. C’est une démarche heuristique plutôt facile à mettre en oeuvre mais qui ne donne pas lieu à des garanties sur la qualité des solutions retournées. Nos premiers résultats vont être publiés dans (1) où nous nous comparons à des méthodes de référence comme les recherches en faisceau. Nous présentons ensuite un travail plus mature (2, 3) sur la découverte de sous-groupes dans des données transactionnelles (itemsets). Nous avons proposé un cadre générique qui vise à améliorer la qualité des sous-groupes calculés et notamment la diversité avec des garanties. Nous exploitons une technique basée sur les arbres de recherche de Monte Carlo développés en intelligence artificielle pour le contexte des jeux à deux joueurs. Nos résultats expérimentaux sont très intéressants. Cependant, l’extension de l’approche vers d’autres types de données reste un problème ouvert et a priori difficile.

(1) R. Mathonat, J-F. Boulicaut, M. Kaytoue. Découverte de sous-groupes pour données séquentielles : échantillonnage et optimisation locale, Actes Extraction et Gestion de Connaissances EGC 2019, Metz (F), janvier 2019, 12 pages, In Press.

(2) G. Bosc, J-F. Boulicaut, C. Raïssi, M. Kaytoue. Découverte de sous-groupes avec les arbres de recherche de Monte Carlo. Actes Extraction et Gestion de Connaissances EGC 2017, janvier 2017, Grenoble (F). pp. 273-284.

(3) G. Bosc, J-F. Boulicaut, C. Raïssi, M. Kaytoue. Anytime Discovery of a Diverse Set of Patterns with Monte Carlo Tree Search. Data Mining and Knowledge Discovery 32(3):604-650, 2018, Springer.