Résumé : La fouille de données est le domaine qui vise à extraire automatiquement de l'information dans de grandes masses de données. Une manière de faire est d'extraire des motifs qui vont contenir cette information et qui servent ensuite à créer des règles d'association. Il existe un grand nombre de motifs (motifs fréquents, fermés, libres, émergents, satisfaisant des mesures d'intérêts, bordure négative, etc.) et une large famille d'algorithmes dédiés pour les extraire. Dans le pire des cas, le nombre de motifs est souvent exponentiel et c'est souvent la seule information dont on dispose sur la complexité des problèmes et des algorithmes. Pourtant en pratique, les algorithmes sont efficaces lorsqu'ils sont utilisés avec des paramètres raisonnables. L'analyse en moyenne qui, contrairement à celle dans le pire des cas, tient compte de toutes les entrées possibles peut expliquer ce genre de phénomène. L'exposé présentera des analyses en moyenne concernant les motifs fréquents et les traverses minimales d'hypergraphes. Le calcul des traverses minimales est fondamental en fouille de données puisqu'il existe par exemple une bijection avec les motifs de la bordure négative. Une question algorithmique encore ouverte est de savoir si le calcul des traverses minimales est output-polynomial (polynomial en la taille de l'entrée plus celle de la sortie) dans le pire des cas. Un éclairage en moyenne sera apporté à cette question.

 [Slides.pdf]

Dernière modification : Monday 18 March 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr