Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 13 mars 2012 à 14h45 en B311, Loïck Lhote nous parlera de : Complexité moyenne de la recherche de motifs fréquents et de traverses minimales d'hypergraphes

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 : lundi 05 mars 2012 Valid HTML 4.01! Valid CSS! Contact : Cyril.Banderier at lipn.univ-paris13.fr