L’extraction de connaissances à base de motifs (Pattern Mining) s'appuie sur de nombreux algorithmes ou structures de données pour extraire de l'information sous forme de motifs des bases de données. Les analyses dans le pire des cas conduisent très souvent à des complexités exponentielles mais les instances ne correspondent pas à des cas “réels”. Afin de décrire plus finement la complexité générique des problèmes issus du Pattern Mining, il convient de réaliser des analyses en moyenne. Dans cet exposé, nous introduirons quelques problèmes liés à l'extraction de motifs dits fréquents et nous montrerons leurs liens avec le calcul des traverses minimales d'hypergraphes. Ensuite, nous présenterons plusieurs résultats d'analyses en moyenne liés à ces objets. En particulier, nous montrons que sous certains modèles aléatoires de bases de données, l'extraction de motifs fréquents peut être de complexité polynomiale. Nous apporterons aussi un éclairage en moyenne sur la complexité d'extraction des traverses minimales d'hypergraphes. Ceci est un travail en commun avec Julien David, Arnaud Mary et François Rioult.