Une carte combinatoire est un modèle topologique qui permet de représenter les subdivisions de l'espace en cellules et les relations d'adjacences et d'incidences entre ces cellules en n dimensions. Cette structure de données est de plus en plus utilisée en traitement d'images, mais elle manque encore d'outils pour les analyser. Notre but est de définir de nouveaux outils pour les cartes combinatoires nD. Nous nous intéressons plus particulièrement à l'extraction de sous-cartes fréquentes dans une base de cartes. Nous proposons deux signatures qui sont également des formes canoniques de cartes combinatoires. Ces signatures ont chacune leurs avantages et leurs inconvénients. La première permet de décider de l'isomorphisme entre deux cartes en temps linéaire, en contrepartie le coût de stockage en mémoire est quadratique en la taille de la carte. La seconde signature a un coût de stockage en mémoire linéaire en la taille de la carte, cependant le temps de calcul de l'isomorphisme est quadratique. Elles sont utilisables à la fois pour des cartes connexes, non connexes, valuées ou non valuées. Ces signatures permettent de représenter une base de cartes combinatoires et de rechercher un élément de manière efficace. De plus, le temps de recherche ne dépend pas du nombre de cartes présent dans la base. Ensuite, nous formalisons le problème de recherche de sous-cartes fréquentes dans une base de cartes combinatoires nD. Nous implémentons deux algorithmes pour résoudre ce problème. Le premier algorithme extrait les sous-cartes fréquentes par une approche en largeur tandis que le second utilise une approche en profondeur. Nous comparons les performances de ces deux algorithmes sur des bases de cartes synthétiques. Enfin, nous proposons d'utiliser les motifs fréquents dans une application de classification d'images. Chaque image est décrite par une carte qui est transformée en un vecteur représentant le nombre d'occurrences des motifs fréquents. À partir de ces vecteurs, nous utilisons des techniques classiques de classification définies sur les espaces vectoriels. Nous proposons des expérimentations en classification supervisée et non supervisée sur deux bases d'images.

La génomique comparée est essentiellement une forme de fouille de données dans des grandes collections de relations n-aires. La croissance du nombre de génomes sequencés créé un stress sur la génomique comparée qui croit, au pire géométriquement, avec la croissance en données de séquence. Aujourd'hui même des laboratoires de taille modeste obtient, de façon routine, plusieurs génomes à la fois - et comme des grands consortia attend de pouvoir réaliser des analyses tout-contre-tout dans le cadre de ses stratégies multi-génomes. Afin d'adresser les besoins à tous niveaux il est nécessaire de repenser les cadres algorithmiques et les technologies de stockage de données utilisés pour la génomique comparée. Pour répondre à ces défis de mise à l'échelle, dans cette thèse nous développons des méthodes originales basées sur les technologies NoSQL et MapReduce. À partir d'une caractérisation des sorts de données utilisés en génomique comparée et d'une étude des utilisations typiques, nous définissons un formalisme pour le Big Data en génomique, l'implémentons dans la plateforme NoSQL Cassandra, et évaluons sa performance. Ensuite, à partir de deux analyses globales très différentes en génomique comparée, nous définissons deux stratégies pour adapter ces applications au paradigme MapReduce et dérivons de nouveaux algorithmes. Pour le premier, l'identification d'événements de fusion et de fission de gènes au sein d'une phylogénie, nous reformulons le problème sous forme d'un parcours en parallèle borné qui évite la latence d'algorithmes de graphe. Pour le second, le clustering consensus utilisé pour identifier des familles de protéines, nous définissons une procédure d'échantillonnage itérative qui converge rapidement vers le résultat global voulu. Pour chacun de ces deux algorithmes, nous l'implémentons dans la plateforme MapReduce Hadoop, et évaluons leurs performances. Cette performance est compétitive et passe à l'échelle beaucoup mieux que les algorithmes existants, mais exige un effort particulier (et futur) pour inventer les algorithmes spécifiques.

La découverte et l'interprétation de motifs et de règles sont deux tâches centrales en extraction de connaissances dans les bases de données. Cette thèse traite de l'extraction et des usages de motifs minimaux à la fois en fouille de données et dans le domaine des hypergraphes. D'une part, nous proposons une méthode efficace pour la découverte de motifs delta-libres dans les données larges, malgré les difficultés algorithmiques inhérentes à ce type de données. Cette méthode repose sur l'utilisation de l'extension des motifs et d'un nouveau critère d'élagage. D'autre part, nous nous intéressons à la qualité des règles d'associations et nous présentons un cadre générique qui permet de mieux comprendre les similarités et différences entre mesures. Il montre que de nombreuses mesures (appelées SBMs pour Simultaneously Bounded Measures) ont des comportements proches. Ce résultat permet de garantir des valeurs minimales pour toutes les SBMs et la production de règles de qualité par rapport à l'ensemble de ces mesures. Enfin, l'apport des méthodes de type <> pour d'autres domaines est mis en évidence. Nous montrons que notre approche de découverte de motifs dans les données larges est exploitable pour calculer efficacement les traverses minimales d'un hypergraphe, un problème réputé comme particulièrement difficile. Différentes applications, notamment en biologie, montrent l'intérêt pratique de nos méthodes.

Cette thèse est consacrée aux tests statistiques, visant à comparer un vecteur de données numériques, indicées par l'ensemble des gènes du génome humain, à un certain ensemble de gènes, connus pour être associés par exemple à un type donné de cancer. Parmi les méthodes existantes, le test Gene Set Enrichment Analysis est le plus utilisé. Néanmoins, il a deux inconvénients. D'une part, le calcul des p-valeurs est coûteux et peu précis. D'autre part, il déclare de nombreux résultats significatifs, dont une majorité n'ont pas de sens biologique. Ces deux problèmes sont traités, par l'introduction de deux procédures statistiques nouvelles, les tests de Kolmogorov-Smirnov pondéré et doublement pondéré. Ces deux tests ont été appliqués à des données simulées et réelles, et leurs résultats comparés aux procédures existantes. Notre conclusion est que, au-delà leurs avantages mathématiques et algorithmiques, les tests proposés pourraient se révéler, dans de nombreux cas, plus informatifs que le test GSEA classique, et traiter efficacement les deux problèmes qui ont motivé leur construction. / Our focus is on statistical testing methods, that compare a given vector of numeric values, indexed by all genes in the human genome, to a given set of genes, known to be associated to a particular type of cancer for instance. Among existing methods, Gene Set Enrichment Analysis is the most widely used. However it has several drawbacks. Firstly, the calculation of p-values is very much time consuming, and insufficiently precise. Secondly, like most other methods, it outputs a large number of significant results, the majority of which are not biologically meaningful. The two issues are addressed here, by two new statistical procedures, the Weighted and Doubly Weighted Kolmogorov-Smirnov tests. The two tests have been applied both to simulated and real data, and compared with other existing procedures. Our conclusion is that, beyond their mathematical and algorithmic advantages, the WKS and DWKS tests could be more informative in many cases, than the classical GSEA test and efficiently address the issues that have led to their construction.

Les travaux présentés dans ce mémoire, ont été développés sur le thème de la découverte de motifs intéressants à travers la fouille de données et mis en oeuvre dans le cadre de la conception de systèmes d'information. Ils sont essentiellement consacrés aux problèmes soulevés par l'étape de fouille pour la découverte de modèles et de motifs fréquents. Ils sont à la fois d'ordre méthodologique et applicatif.

La découverte de motifs est une tâche centrale pour<br />l'extraction de connaissances dans les bases de données. Cette thèse<br />traite de l'extraction de motifs locaux sous contraintes. Nous<br />apportons un éclairage nouveau avec un cadre combinant des primitives<br />monotones pour définir des contraintes quelconques. La variété de ces<br />contraintes exprime avec précision l'archétype des motifs recherchés<br />par l'utilisateur au sein d'une base de données. Nous proposons alors<br />deux types d'approche d'extraction automatique et générique malgré les<br />difficultés algorithmiques inhérentes à cette tâche. Leurs efficacités<br />reposent principalement sur l'usage de conditions nécessaires pour<br />approximer les variations de la contrainte. D'une part, des méthodes<br />de relaxations permettent de ré-utiliser les nombreux algorithmes<br />usuels du domaines. D'autre part, nous réalisons des méthodes<br />d'extraction directes dédiées aux motifs ensemblistes pour les données<br />larges ou corrélées en exploitant des classes d'équivalences. Enfin,<br />l'utilisation de nos méthodes ont permi la découverte de phénomènes<br />locaux lors d'applications industrielles et médicales.

Dans le domaine de l'extraction de motifs, il existe un grand nombre d'algorithmes pour résoudre une large variété de sous problèmes sensiblement identiques. Cette variété d'algorithmes freine l'adoption des techniques d'extraction de motifs pour l'analyse de données. Dans cette thèse, nous proposons un formalisme qui permet de capturer une large gamme de problèmes d'extraction de motifs. Pour démontrer la généralité de ce formalisme, nous l'utilisons pour décrire trois problèmes d'extraction de motifs : le problème d'extraction d'itemsets fréquents fermés, le problème d'extraction de graphes relationnels fermés ou le problème d'extraction d'itemsets graduels fermés. Ce formalisme nous permet de construire ParaMiner qui est un algorithme générique et parallèle pour les problèmes d'extraction de motifs. ParaMiner est capable de résoudre tous les problèmes d'extraction de motifs qui peuvent ˆtre décrit dans notre formalisme. Pour obtenir de bonne performances, nous avons généralisé plusieurs optimisations proposées par la communauté dans le cadre de problèmes spécifique d'extraction de motifs. Nous avons également exploité la puissance de calcul parallèle disponible dans les archi- tectures parallèles. Nos expériences démontrent qu'en dépit de la généricité de ParaMiner ses performances sont comparables avec celles obtenues par les algorithmes les plus rapides de l'état de l'art. Ces algorithmes bénéficient pourtant d'un avantage important, puisqu'ils incorporent de nombreuses optimisations spécifiques au sous problème d'extraction de motifs qu'ils résolvent.

Nous présentons dans cette thèse une approche probabiliste pour déterminer les valeurs manquantes des objets incomplets pendant leur classement dans les arbres de décision. Cette approche est dérivée de la méthode d'apprentissage supervisé appelée Arbres d'Attributs Ordonnées (AAO) proposée par Lobo et Numao en 2000, qui construit un arbre de décision pour chacun des attributs, selon un ordre croissant en fonction de l'Information Mutuelle entre chaque attribut et la classe. Notre approche étend la méthode de Lobo et Numao, d'une part en prenant en compte les dépendances entre les attributs pour la construction des arbres d'attributs, et d'autre part en fournissant un résultat de classement d'un objet incomplet sous la forme d'une distribution de probabilités (au lieu de la classe la plus probable). <br />Nous expliquons notre méthode et nous la testons sur des bases de données réelles. Nous comparons nos résultats avec ceux donnés par la méthode C4.5 et AAO. <br /><br />Nous proposons également un algorithme basé sur la méthode des k plus proches voisins qui calcule pour chaque objet de la base de test sa fréquence dans la base d'apprentissage. Nous comparons ces fréquences avec les résultats de classement données par notre approche, C4.5 et AAO. Finalement, nous calculons la complexité de construction des arbres d'attributs ainsi que la complexité de classement d'un objet incomplet en utilisant notre approche, C4.5 et AAO.

Cette thèse s'articule autour des problèmes d'optimisation à grande échelle, et plus particulièrement autour des méthodes de factorisation matricielle sur des problèmes de grandes tailles. L'objectif des méthodes de factorisation de grandes matrices est d'extraire des variables latentes qui permettent d'expliquer les données dans un espace de dimension réduite. Nous nous sommes intéressés au domaine d'application de la recommandation et plus particulièrement au problème de prédiction de préférences d'utilisateurs. Dans une contribution nous nous sommes intéressés à l'application de méthodes de factorisation dan un environnement de recommandation contextuelle et notamment dans un contexte social. Dans une seconde contribution, nous nous sommes intéressés au problème de sélection de modèle pour la factorisation où l'on cherche à déterminer de façon automatique le rang de la factorisation par estimation de risque.

Cette thèse s'articule autour des problèmes d'optimisation à grande échelle, et plus particulièrement autour des méthodes de factorisation matricielle sur des problèmes de grandes tailles. L'objectif des méthodes de factorisation de grandes matrices est d'extraire des variables latentes qui permettent d'expliquer les données dans un espace de dimension réduite. Nous nous sommes intéressés au domaine d'application de la recommandation et plus particulièrement au problème de prédiction de préférences d'utilisateurs.Dans une contribution, nous nous sommes intéressés à l'application de méthodes de factorisation dans un environnement de recommandation contextuelle et notamment dans un contexte social.Dans une seconde contribution, nous nous sommes intéressés au problème de sélection de modèle pour la factorisation où l'on cherche à déterminer de façon automatique le rang de la factorisation par estimation de risque.