Complexite moyenne de la recherche de motifs frequents et de traverses minimales d'hypergraphe

Complexite moyenne de la recherche de motifs frequents
et de traverses minimales d’hypergraphe
Lo ck Lhote
GREYC, ENSICAEN
13 mars 2012
Lo ck Lhote (GREYC, ENSICAEN) Traverses et motifs 06/09/2006 1 / 45Plan
1 Contexte de la Fouille de donnees
2 Motifs frequents
De nitions
Combinatoire des motifs frequents
3 Traverses minimales d’hypergraphe et FDD
Bordure negative
Hypergraphes et traverses
probleme THG
4 Resultats sur les motifs frequents
Modele aleatoire
Experiences
5 Resultats sur les traverses minimales
R
Elements de preuve
6 Conclusion
Lo ck Lhote (GREYC, ENSICAEN) Traverses et motifs 06/09/2006 2 / 45Plan
1 Contexte de la Fouille de donnees
2 Motifs frequents
De nitions
Combinatoire des motifs frequents
3 Traverses minimales d’hypergraphe et FDD
Bordure negative
Hypergraphes et traverses
probleme THG
4 Resultats sur les motifs frequents
Modele aleatoire
Experiences
5 Resultats sur les traverses minimales
R
Elements de preuve
6 Conclusion
Lo ck Lhote (GREYC, ENSICAEN) Traverses et motifs 06/09/2006 3 / 45Etapes successives en fouille de donnees
extraction clustering
mise en classification
forme
règles
d’associationsélection
connaissanceinformation
(motifs)
données mises
données en forme
brutes (bases binaires)
base de données
cas particulier : bases de donnees binaires
Lo ck Lhote (GREYC, ENSICAEN) Traverses et motifs 06/09/2006 4 / 45