Auteur : Julien DARLAY
Directeur de thèse : Nadia BRAUNER
Codirigée par : Julien MONCEL
Date : 19 Décembre 2012
Directeur de thèse : Nadia BRAUNER
Codirigée par : Julien MONCEL
Date : 19 Décembre 2012
Analyse Combinatoire de Données
Structures et Optimisation
Structures et Optimisation
Cette thèse porte sur des problèmes d'exploration de données avec le point de vue de la recherche opérationnelle. L'exploration de données consiste en l'apprentissage de nouvelles connaissances à partir d'observations contenues dans une base de données. La nature des problèmes rencontrés dans ce domaine est proche de celle des problèmes de la recherche opérationnelle : grandes instances, objectifs complexes et difficulté algorithmique. L'exploration de données peut aussi se modéliser comme un problème d'optimisation avec un objectif partiellement connu. Cette thèse se divise en deux parties. La première est une introduction à l'exploration de données. Elle présente l'Analyse Combinatoire de Données (ACD), une méthode d'exploration de données issue de l'optimisation discrète. Cette méthode est appliquée à des données médicales originales et une extension aux problèmes d'analyse de temps de survie est proposée. L'analyse de temps de survie consiste à modéliser le temps avant un événement (typiquement un décès ou une rechute). Les heuristiques proposées utilisent des techniques classiques de recherche opérationnelle telles que la programmation linéaire en nombres entiers, la décomposition de problème, des algorithmes gloutons. La seconde partie est plus théorique et s'intéresse à deux problèmes combinatoires rencontrés dans le domaine de l'exploration de données. Le premier est un problème de partitionnement de graphes n sous-graphes denses pour l'apprentissage non supervisé. Nous montrons la complexité algorithmique de ce problème et nous proposons un algorithme polynomial basé sur la programmation dynamique lorsque le graphe est un arbre. Cet algorithme repose sur des résultats de la théorie des couplages. Le second problème est une génération des problèmes de couverture par les tests pour la sélection d'attributs. Les lignes d'une matrice sont coloriées en deux couleurs. L'objectif est de trouver un sous-ensemble minimum de colonnes tel que toute paire de lignes avec des couleurs différentes restent distinctes lorsque la matrice est restreinte au sous-ensemble de colonnes. Nous montrons des résultats de complexité ainsi que des bornes serrées sur la taille des solutions optimales pour différentes structures de matrices.