Vingt-deux ans de recherche en fouille de motifs: du parcours en largeur au parcours en profondeur?!
Albrecht Zimmermann (GREYC, Caen)C’est en 1995 que la fouille de données (ou plus précisément la fouille de motifs) arrive comme un domaine de recherche distinct, avec l’article qui introduit l’algorithme Apriori. Cet algorithme parcourt l’espace de recherche en largeur, en exploitant la propriété d’anti-monotone de la contrainte de fréquence minimale. Les premières approches alternatives, qui elles utilisent le parcours en profondeur, sont proposées peu après. Vingt-deux ans plus tard, les algorithmes de fouille de motifs les plus performants parcourent cet espace en profondeur et d’autres approches restent rares.
Dans cet exposé, j’introduirai les développements algorithmiques les plus importants dans la fouille de motifs, puis j’indiquerai quelques raisons qui expliquent l’absence d’ approches alternatives. Puis, je décrirai quelques idées plus (ou moins) récentes qui pourraient ouvrir de futures directions.