Stage Master 2 au LIPN
Forum 'Stages' - Sujet créé le 2009-01-22 par Lucas Létocart
Voici une offre de stage de Master 2 à effectuer au LIPN (Laboratoire d'Informatique de Paris Nord) URL
Algorithmes de graphes pour la recherche de motifs bruités
On désigne par fouille de données (ou data mining) l'étape d'extraction de motifs satisfaisant un ensemble de contraintes. Les motifs extraits peuvent être de nature diverse (séquences, arbres ou graphes). Dans ce stage, nous nous intéressons uniquement aux traditionnels motifs ensemblistes.
La recherche de motifs ensemblistes dans une matrice booléenne consiste, grossièrement, à rechercher tous les rectangles de 1 maximaux dans une matrice à valeurs dans $\{0,1\}$. C'est un problème bien posé et fort étudié dans la communauté de Fouille de Données. Néanmoins, les algorithmes de Fouille de Données développés, même parmi les plus récents, s'adaptent difficilement à des
données réelles et bruitées, car le bruit va ``pulvériser'' un motif pertinent m en un ensemble de motifs sous-ensembles de m, entraînant une explosion du nombre de motifs résultats. Une solution à ce problème consiste à rechercher des régions denses dans la matrice booléenne. Ce stage a pour but d'étudier la combinaison de méthodes de fouille de données et de méthodes d'optimisation combinatoire pour rechercher ces régions denses efficacement.
L'objectif de ce stage est donc d'explorer une voie alternative pour résoudre le problème difficile de la recherche de motifs contraints dans un environnement bruité: l'utilisation de techniques de recherche opérationnelle, notamment d'algorithmes de graphes. Une étape clé de la recherche de maximaux fréquents dans un cadre non bruité repose sur le calcul des transversaux minimaux d'hypergraphes. Les techniques usuelles d'obtention de transversaux minimaux d'hypergraphes n'offrent pas dans notre cas une solution appropriée, cela étant dû au bruitage des données. L'approche choisie consiste, à partir des matrices d'expression des régulateurs, à construire des graphes bipartis exprimant la corrélation entre les régulateurs puis à rechercher des sous-graphes denses dans ces graphes bipartis. L'approche envisagée dans ce stage s'appuie sur la recherche de sous-graphes denses avec un degré moyen maximal dans des graphes bipartis. En effet, des algorithmes performants existent pour trouver le sous-graphe le plus dense avec des contraintes spécifiques. Il convient notamment, dans ce stage, de généraliser ces approches afin de pouvoir déterminer tous les rectangles maximaux de densité minimale donnée permettant d'extraire les motifs recherchés.
Lieu du stage : LIPN
Durée du stage : 6 mois
Rémunération : environ 800 Euros par mois
Encadrants : C. Rouveirol et L. Létocart
e-mails : {celine.rouveirol,lucas.letocart}@lipn.univ-paris13.fr
Algorithmes de graphes pour la recherche de motifs bruités
On désigne par fouille de données (ou data mining) l'étape d'extraction de motifs satisfaisant un ensemble de contraintes. Les motifs extraits peuvent être de nature diverse (séquences, arbres ou graphes). Dans ce stage, nous nous intéressons uniquement aux traditionnels motifs ensemblistes.
La recherche de motifs ensemblistes dans une matrice booléenne consiste, grossièrement, à rechercher tous les rectangles de 1 maximaux dans une matrice à valeurs dans $\{0,1\}$. C'est un problème bien posé et fort étudié dans la communauté de Fouille de Données. Néanmoins, les algorithmes de Fouille de Données développés, même parmi les plus récents, s'adaptent difficilement à des
données réelles et bruitées, car le bruit va ``pulvériser'' un motif pertinent m en un ensemble de motifs sous-ensembles de m, entraînant une explosion du nombre de motifs résultats. Une solution à ce problème consiste à rechercher des régions denses dans la matrice booléenne. Ce stage a pour but d'étudier la combinaison de méthodes de fouille de données et de méthodes d'optimisation combinatoire pour rechercher ces régions denses efficacement.
L'objectif de ce stage est donc d'explorer une voie alternative pour résoudre le problème difficile de la recherche de motifs contraints dans un environnement bruité: l'utilisation de techniques de recherche opérationnelle, notamment d'algorithmes de graphes. Une étape clé de la recherche de maximaux fréquents dans un cadre non bruité repose sur le calcul des transversaux minimaux d'hypergraphes. Les techniques usuelles d'obtention de transversaux minimaux d'hypergraphes n'offrent pas dans notre cas une solution appropriée, cela étant dû au bruitage des données. L'approche choisie consiste, à partir des matrices d'expression des régulateurs, à construire des graphes bipartis exprimant la corrélation entre les régulateurs puis à rechercher des sous-graphes denses dans ces graphes bipartis. L'approche envisagée dans ce stage s'appuie sur la recherche de sous-graphes denses avec un degré moyen maximal dans des graphes bipartis. En effet, des algorithmes performants existent pour trouver le sous-graphe le plus dense avec des contraintes spécifiques. Il convient notamment, dans ce stage, de généraliser ces approches afin de pouvoir déterminer tous les rectangles maximaux de densité minimale donnée permettant d'extraire les motifs recherchés.
Lieu du stage : LIPN
Durée du stage : 6 mois
Rémunération : environ 800 Euros par mois
Encadrants : C. Rouveirol et L. Létocart
e-mails : {celine.rouveirol,lucas.letocart}@lipn.univ-paris13.fr