Analyse formelle de concepts et structures de patrons pour la fouille de données structurées

Nowadays, more and more data of different kinds is becoming available. Various datasets contain valuable information that could help to solve many practical problems or to lead to a breakthrough in fundamental science. But how can one extract these precious pieces of information? Formal concept analysis (FCA) and pattern structures are theoretical frameworks that allow dealing with an arbitrary structured data. But how can one put it into practice? Furthermore, the number of concepts, i.e., elementary pieces of information, extracted by FCA is typically huge. To deal with this problem one can either simplify the data representation, which can be done by projections of pattern structures, or by introducing constraints to select the most relevant concepts. What is the best data simplification? How to find concepts efficiently satisfying a given constraint? These are the questions that we address in this work. The manuscript starts with application of FCA to mining important pieces of information from molecular structures. These molecular structures are encoded as sets of attributes. Even for this simple encoding and without any additional constraints, FCA is able to extract important pieces of information from small datasets. With the growth of dataset size good constraints begin to be essential. For that we explore stability of a concept, a well-founded formal constraint. We show experimentally that it is a good choice and apply it to analyze a dataset of mutagenetic chemical substances. Finding stable concepts in this dataset allows us finding new possible mutagenetic candidates that can be further interpreted by chemists.However for more complex cases, the simple attribute representation of data is not enough. Correspondingly, we turn to pattern structures that can deal with many different kinds of descriptions. The important point about pattern structures is that they allow data simplification by means of projections. We extend the original formalism of projections to have more freedom in data simplification. We show that this extension is essential for analyzing patient trajectories, describing patients hospitalization histories. Indeed, patient trajectories are sequences of hospitalizations and every hospitalization is described by a heterogeneous description. This data is very rich and hence, produce a lot of concepts. The new type of projections allows efficient reduction of concept space and in combination with stability constraints can find important common trajectories. In addition, projections are useful to correct linked open data, a data that is distributed all over the world and that can be enriched by any person. The errors are inevitable but some of them can be efficiently found by an approach based on pattern structures. Yet another application of pattern structures is mining of drug-drug interactions from text corpuses. Based on a text of corpuses we are able to find and explain syntactic structures encoding this kind of relation.So far pattern structures do not allow direct finding of patterns satisfying the stability constraint. Correspondingly, the manuscript ends by an original and very efficient approach that enables to mine stable patterns directly. This approach is called Σοφια and is able to find the best stable patterns in polynomial time. The efficiency is essential for mining large datasets and this highlights the importance of Σοφια. We evaluate this new algorithm on several datasets and the experiments show the significant improvement of Σοφια w.r.t. its competitors forattribute and interval tuple data. Moreover it open a new direction of research for mining different types of patterns in polynomial time that is very important in the world of large data.Aujourd’hui de plus en plus de données de différents types sont accessibles. Ces données variées contiennent des informations précieuses qui peuvent aider à résoudre des problèmes pratiques ou servir à la science fondamentale. Mais comment peut-on extraire cette information précieuse ? L’Analyse Formelle de Concepts (AFC) et les pattern structures sont des systèmes formels qui permettent de traiter les données ayant une structure complexe. Mais comment peut-on les appliquer en pratique ? De plus, le nombre de concepts, i.e., de pièces élémentaires d’information, trouvé par l’AFC est fréquemment très grand. Pour faire face à ce problème, on peut simplifier la représentation des données, soit par projection de pattern structures, soit par introduction de contraintes pour sélectionner les concepts les plus pertinents. Quelle est la meilleure simplification de données ? Comment peut-on efficacement trouver les concepts satisfaisant une contrainte donnée ? Ce sont les questions que nous abordons dans cette thèse.Le manuscrit commence avec l’application de l’AFC à l’exploration de structures moléculaires et la recherche de structures particulières. Ces structures moléculaires sont codées comme des ensembles d’attributs. Même pour ce codage simple et sans contraintes supplémentaires, l’AFC est capable d’extraire des informations importantes dans de petits ensembles de données. Avec l’augmentation de la taille des ensembles de données, de bonnes contraintes deviennent essentielles. Pour cela on explore la stabilité d’un concept. La stabilité est une contrainte formelle bien-fondée. On montre expérimentalement que c’est un bon choix et on l’applique à l’exploration d’un ensemble de données de substances chimiques mutagènes. La recherche de concepts stables dans cet ensemble de données nous a permis de trouver de nouveaux candidats mutagènes potentiels qui peuvent être interprétés par les chimistes.Cependant, pour les cas plus complexes, la représentation simple par des attributs binaires ne suffit pas. En conséquence, on se tourne vers des pattern structures qui peuvent traiter différents types de données complexes. Le point important sur les pattern structures est qu’elles permettent la simplification des données au moyen de projections. On étend le formalisme original des projections pour avoir plus de liberté dans la manipulation de données. On montre que cette extension est essentielle pour analyser les trajectoires de patients décrivant l’historique de l’hospitalisation des patients. En effet, les trajectoires de patients sont des séquences d’hospitalisations et chaque hospitalisation est décrite par une description hétérogène. Ces données sont très riches et donc produisent un grand nombre de concepts. Le nouveau type de projection permet une réduction efficace de la notion d’espace et en combinaison avec des contraintes de stabilité on peut trouver des trajectoires communes importantes. En outre, les projections sont utiles pour corriger et compléter les données liées (linked open data) où les erreurs sont inévitables. On peut efficacement trouver certaines erreurs avec une approche à base de pattern structures. Une autre application des pattern structures est la recherche des interactions médicamenteuses dans un corpus de textes. On est capable d’extraire et d’expliquer les structures syntaxiques codant ce genre des relations. Les approches présentées jusque là ne permettent pas la découverte directe de motifs sous la contrainte de stabilité. En conséquence, le manuscrit se termine par une approche originale et très efficace qui permet de trouver directement des motifs stables. Cette approche est appelée Σοφια et est capable de trouver les meilleurs modèles stables en temps polynomial. L’efficacité est essentielle pour l’analyse de grands ensembles de données et cela souligne l’importance de Σοφια. On évalue ce nouvel algorithme sur plusieurs ensembles de données et les expériences montrent l’amélioration significative de Σοφια par rapport à ses concurrents pour les données binaires et des n-uplets d’intervalles. En outre, il ouvre une nouvelle direction de recherche pour l’exploitation de différents types de motifs en temps polynomial ce qui est très important dans le monde des mégadonnées