Mannila et Toivonen ont décrit un cadre pour la découverte de motifs intéressants dans les bases de données en 1997. Entre autre chose, ils y ont proposé la classe RAS des problèmes dits représentables par les ensembles. Le problème difficile sous jacent à la découverte des motifs est connu sous le nom de dualisation, qui est le problème d'énumération des transversaux minimaux d'un hypergraphe pour RAS. Son intérêt pratique est que tout problème de RAS peut être résolu par un algorithme d'énumération à délai quasi-polynomial. Notons que La librairie iZi (liris.cnrs.fr/iZi) développée au LIMOS puis au LIRIS attaque exactement les problèmes RAS.
Pourtant, même si de nombreux problèmes y entrent, e.g. itemsets (fréquents/non redondant/generateurs) ou dépendances d'inclusion, force est de constater que la plupart des problèmes de motifs étudiés depuis 30 ans n'y entre pas : séquences, épisodes, arbres, graphes ...
Dans cet exposé, je présenterai WRAS, une relaxation de RAS qui permet de capter de nombreux motifs "non trivialement ensemblistes". Les problèmes WRAS pour lesquels il existe un algorithme à délai quasi-polynomial seront caractérisés (EWRAS). Ceci fait, je prendrai un exemple très simple -- les motifs séquentiels -- n'appartenant pas à RAS, mais appartenant à EWARS.
Je tenterai de montrer l'impact que devrait avoir ces résultats pour la promotion les approches déclaratives "à la BD" pour la fouille de motifs.
Ce travail est fait en collaboration avec Lhouari Nourine dans le cadre du projet ANR DAG (liris.cnrs.fr/dag).
