Search

Knowledge discovery in database (KDD) is a process which is applied to possibly large volumes of data for discovering patterns which can be significant and useful. In this thesis, we are interested in data transformation and data mining in knowledge discovery applied to complex data, and we present several experiments related to different approaches and different data types.The first part of this thesis focuses on the task of biclustering using formal concept analysis (FCA) and pattern structures. FCA is naturally related to biclustering, where the objective is to simultaneously group rows and columns which verify some regularities. Related to FCA, pattern structures are its generalizations which work on more complex data. Partition pattern structures were proposed to discover constant-column biclustering, while interval pattern structures were studied in similar-column biclustering. Here we extend these approaches to enumerate other types of biclusters: additive, multiplicative, order-preserving, and coherent-sign-changes.The second part of this thesis focuses on two experiments in mining complex data. First, we present a contribution related to the CrossCult project, where we analyze a dataset of visitor trajectories in a museum. We apply sequence clustering and FCA-based sequential pattern mining to discover patterns in the dataset and to classify these trajectories. This analysis can be used within CrossCult project to build recommendation systems for future visitors. Second, we present our work related to the task of antibacterial drug discovery. The dataset for this task is generally a numerical matrix with molecules as rows and features/attributes as columns. The huge number of features makes it more complex for any classifier to perform molecule classification. Here we study a feature selection approach based on log-linear analysis which discovers associations among features.As a synthesis, this thesis presents a series of different experiments in the mining of complex real-world data.; L'extraction de connaissances dans les bases de données (ECBD) est un processus qui s'applique à de (potentiellement larges) volumes de données pour découvrir des motifs qui peuvent être signifiants et utiles. Dans cette thèse, on s'intéresse à deux étapes du processus d'ECBD, la transformation et la fouille, que nous appliquons à des données complexes. Nous présentons de nombreuses expérimentations s'appuyant sur des approches et des types de données variés.La première partie de cette thèse s'intéresse à la tâche de biclustering en s'appuyant sur l'analyse formelle de concepts (FCA) et aux pattern structures. FCA est naturellement liées au biclustering, dont l'objectif consiste à grouper simultanément un ensemble de lignes et de colonnes qui vérifient certaines régularités. Les pattern structures sont une généralisation de la FCA qui permet de travailler avec des données plus complexes. Les "partition pattern structures'' ont été proposées pour du biclustering à colonnes constantes tandis que les "interval pattern structures'' ont été étudiées pour du biclustering à colonnes similaires. Nous proposons ici d'étendre ces approches afin d'énumérer d'autres types de biclusters : additif, multiplicatif, préservant l'ordre, et changement de signes cohérents.Dans la seconde partie, nous nous intéressons à deux expériences de fouille de données complexes. Premièrement, nous présentons une contribution dans la quelle nous analysons les trajectoires des visiteurs d'un musée dans le cadre du projet CrossCult. Nous utilisons du clustering de séquences et de la fouille de motifs séquentiels basée sur l'analyse formelle de concepts pour découvrir des motifs dans les données et classifier les trajectoires. Cette analyse peut ensuite être exploitée par un système de recommandation pour les futurs visiteurs. Deuxièmement, nous présentons un travail sur la découverte de médicaments antibactériens. Les jeux de données pour cette tâche, généralement des matrices numériques, décrivent des molécules par un certain nombre de variables/attributs. Le grand nombre de variables complexifie la classification des molécules par les classifieurs. Ici, nous étudions une approche de sélection de variables basée sur l'analyse log-linéaire qui découvre des associations entre variables.En somme, cette thèse présente différentes expériences de fouille de données réelles et complexes.

In this thesis, we are interested in the web of data and knowledge units that can be possibly discovered inside. The web of data can be considered as a very large graph consisting of connected RDF triple databases. An RDF triple, denoted as (subject, predicate, object), represents a relation (i.e. the predicate) existing between two resources (i.e. the subject and the object). Resources can belong to one or more classes, where a class aggregates resources sharing common characteristics. Thus, these RDF triple databases can be seen as interconnected knowledge bases. Most of the time, these knowledge bases are collaboratively built thanks to human users. This is particularly the case of DBpedia, a central knowledge base within the web of data, which encodes Wikipedia content in RDF format. DBpedia is built from two types of Wikipedia data: on the one hand, (semi-)structured data such as infoboxes, and, on the other hand, categories, which are thematic clusters of manually generated pages. However, the semantics of categories in DBpedia, that is, the reason a human agent has bundled resources, is rarely made explicit. In fact, considering a class, a software agent has access to the resources that are regrouped together, i.e. the class extension, but it generally does not have access to the ``reasons'' underlying such a cluster, i.e. it does not have the class intension. Considering a category as a class of resources, we aim at discovering an intensional description of the category. More precisely, given a class extension, we are searching for the related intension. The pair (extension, intension) which is produced provides the final definition and the implementation of classification-based reasoning for software agents. This can be expressed in terms of necessary and sufficient conditions: if x belongs to the class C, then x has the property P (necessary condition), and if x has the property P, then it belongs to the class C (sufficient condition). Two complementary data mining methods allow us to materialize the discovery of definitions, the search for association rules and the search for redescriptions. In this thesis, we first present a state of the art about association rules and redescriptions. Next, we propose an adaptation of each data mining method for the task of definition discovery. Then we detail a set of experiments applied to DBpedia, and we qualitatively and quantitatively compare the two approaches. Finally, we discuss how discovered definitions can be added to DBpedia to improve its quality in terms of consistency and completeness.; Dans cette thèse, nous nous intéressons au web des données et aux ``connaissances'' que potentiellement il renferme. Le web des données se présente comme un très grand graphe constitué de bases de triplets RDF connectées entre elles. Un triplet RDF, dénoté (sujet, prédicat, objet), représente une relation (le prédicat) qui existe entre deux ressources (le sujet et l'objet). Les ressources peuvent appartenir à une ou plusieurs classes, où une classe regroupe des ressources partageant des caractéristiques communes. Ainsi, ces bases de triplets RDF peuvent être vues comme des bases de connaissances interconnectées. La plupart du temps ces bases de connaissances sont construites de manière collaborative par des utilisateurs. C'est notamment le cas de DBpedia, une base de connaissances centrale dans le web des données, qui encode le contenu de Wikipédia au format RDF. DBpedia est construite à partir de deux types de données de Wikipédia : d'une part, des données (semi-)structurées telles que les infoboxes et d'autre part les catégories, qui sont des regroupements thématiques de pages générés manuellement. Cependant, la sémantique des catégories dans DBpedia, c'est-à-dire la raison pour laquelle un agent humain a regroupé des ressources, n'est pas explicite. De fait, en considérant une classe, un agent logiciel a accès aux ressources qui y sont regroupées --- il dispose de la définition dite en extension --- mais il n'a généralement pas accès aux ``motifs'' de ce regroupement --- il ne dispose pas de la définition dite en intension. Dans cette thèse, nous cherchons à associer une définition à une catégorie en l'assimilant à une classe de ressources. Plus précisément, nous cherchons à associer une intension à une classe donnée en extension. La paire (extension, intension) produite va fournir la définition recherchée et va autoriser la mise en œuvre d'un raisonnement par classification pour un agent logiciel. Cela peut s'exprimer en termes de conditions nécessaires et suffisantes : si x appartient à la classe C, alors x a la propriété P (condition nécessaire), et si x a la propriété P, alors il appartient à la classe C (condition suffisante). Deux méthodes de fouille de données complémentaires nous permettent de matérialiser la découverte de définitions, la fouille de règles d'association et la fouille de redescriptions. Dans le mémoire, nous présentons d'abord un état de l'art sur les règles d'association et les redescriptions. Ensuite, nous proposons une adaptation de chacune des méthodes pour finaliser la tâche de découverte de définitions. Puis nous détaillons un ensemble d'expérimentations menées sur DBpedia, où nous comparons qualitativement et quantitativement les deux approches. Enfin les définitions découvertes peuvent potentiellement être ajoutées à DBpedia pour améliorer sa qualité en termes de cohérence et de complétude

In this thesis, we are interested in the web of data and knowledge units that can be possibly discovered inside. The web of data can be considered as a very large graph consisting of connected RDF triple databases. An RDF triple, denoted as (subject, predicate, object), represents a relation (i.e. the predicate) existing between two resources (i.e. the subject and the object). Resources can belong to one or more classes, where a class aggregates resources sharing common characteristics. Thus, these RDF triple databases can be seen as interconnected knowledge bases. Most of the time, these knowledge bases are collaboratively built thanks to human users. This is particularly the case of DBpedia, a central knowledge base within the web of data, which encodes Wikipedia content in RDF format. DBpedia is built from two types of Wikipedia data: on the one hand, (semi-)structured data such as infoboxes, and, on the other hand, categories, which are thematic clusters of manually generated pages. However, the semantics of categories in DBpedia, that is, the reason a human agent has bundled resources, is rarely made explicit. In fact, considering a class, a software agent has access to the resources that are regrouped together, i.e. the class extension, but it generally does not have access to the ``reasons'' underlying such a cluster, i.e. it does not have the class intension. Considering a category as a class of resources, we aim at discovering an intensional description of the category. More precisely, given a class extension, we are searching for the related intension. The pair (extension, intension) which is produced provides the final definition and the implementation of classification-based reasoning for software agents. This can be expressed in terms of necessary and sufficient conditions: if x belongs to the class C, then x has the property P (necessary condition), and if x has the property P, then it belongs to the class C (sufficient condition). Two complementary data mining methods allow us to materialize the discovery of definitions, the search for association rules and the search for redescriptions. In this thesis, we first present a state of the art about association rules and redescriptions. Next, we propose an adaptation of each data mining method for the task of definition discovery. Then we detail a set of experiments applied to DBpedia, and we qualitatively and quantitatively compare the two approaches. Finally, we discuss how discovered definitions can be added to DBpedia to improve its quality in terms of consistency and completeness.; Dans cette thèse, nous nous intéressons au web des données et aux ``connaissances'' que potentiellement il renferme. Le web des données se présente comme un très grand graphe constitué de bases de triplets RDF connectées entre elles. Un triplet RDF, dénoté (sujet, prédicat, objet), représente une relation (le prédicat) qui existe entre deux ressources (le sujet et l'objet). Les ressources peuvent appartenir à une ou plusieurs classes, où une classe regroupe des ressources partageant des caractéristiques communes. Ainsi, ces bases de triplets RDF peuvent être vues comme des bases de connaissances interconnectées. La plupart du temps ces bases de connaissances sont construites de manière collaborative par des utilisateurs. C'est notamment le cas de DBpedia, une base de connaissances centrale dans le web des données, qui encode le contenu de Wikipédia au format RDF. DBpedia est construite à partir de deux types de données de Wikipédia : d'une part, des données (semi-)structurées telles que les infoboxes et d'autre part les catégories, qui sont des regroupements thématiques de pages générés manuellement. Cependant, la sémantique des catégories dans DBpedia, c'est-à-dire la raison pour laquelle un agent humain a regroupé des ressources, n'est pas explicite. De fait, en considérant une classe, un agent logiciel a accès aux ressources qui y sont regroupées --- il dispose de la définition dite en extension --- mais il n'a généralement pas accès aux ``motifs'' de ce regroupement --- il ne dispose pas de la définition dite en intension. Dans cette thèse, nous cherchons à associer une définition à une catégorie en l'assimilant à une classe de ressources. Plus précisément, nous cherchons à associer une intension à une classe donnée en extension. La paire (extension, intension) produite va fournir la définition recherchée et va autoriser la mise en œuvre d'un raisonnement par classification pour un agent logiciel. Cela peut s'exprimer en termes de conditions nécessaires et suffisantes : si x appartient à la classe C, alors x a la propriété P (condition nécessaire), et si x a la propriété P, alors il appartient à la classe C (condition suffisante). Deux méthodes de fouille de données complémentaires nous permettent de matérialiser la découverte de définitions, la fouille de règles d'association et la fouille de redescriptions. Dans le mémoire, nous présentons d'abord un état de l'art sur les règles d'association et les redescriptions. Ensuite, nous proposons une adaptation de chacune des méthodes pour finaliser la tâche de découverte de définitions. Puis nous détaillons un ensemble d'expérimentations menées sur DBpedia, où nous comparons qualitativement et quantitativement les deux approches. Enfin les définitions découvertes peuvent potentiellement être ajoutées à DBpedia pour améliorer sa qualité en termes de cohérence et de complétude

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.

One of the first models ever to be considered as an index for documents using terms as descriptors, was a lattice structure, a couple of decades before the arrival of Formal Concept Analysis (FCA) as a solid theory for data mining and knowledge discovery.While the Information Retrieval (IR) community has shifted to more advanced techniques for document retrieval, like probabilistic and statistic paradigms, the interest of the FCA community on developing techniques that would improve the state-of-the-art in IR while providing relevance feedback and semantic based features, never decayed.In this thesis we present a set of contributions on what we call FCA-based IR systems. We have divided our contributions in two sets, namely retrieval and indexing. For retrieval, we propose a novel technique that exploits semantic relations among descriptors in a document corpus and a new concept lattice navigation strategy (called cousin concepts), enabling us to support classification-based reasoning to provide better results compared with state-of-the-art retrieval techniques. The basic notion in our strategy is supporting query modification using ``term replacements'' using the lattice structure and semantic similarity.For indexing, we propose a new model that allows supporting the vector space model of retrieval using concept lattices. One of the main limitations of current FCA-based IR systems is related to the binary nature of the input data required for FCA to generate a concept lattice. We propose the use of pattern structures, an extension of FCA to deal with complex object descriptions, in order to support more advanced retrieval paradigms like the vector space model.In addition, we propose an advanced model for heterogeneous indexing through which we can combine the vector space model and the Boolean retrieval model. The main advantage of this approach is the ability of supporting indexing of convex regions in an arbitrary vectorial space built from a document collection.Finally, we move forward to a mining model associated with document indexing, namely exhaustive bicluster enumeration using FCA.Biclustering is an emerging data analysis technique in which objects are related by similarity under certain attributes of the description space, instead of the whole description space like in standard clustering. By translating this problem to the framework of FCA, we are able to exploit the robust machinery associated with the computation of concept lattices to provide an algorithm for mining biclusters based on similar values. We show how our technique performs better than current exhaustive enumeration biclustering techniques.; Un des premiers modèles d'indexation de documents qui utilise des termes comme descripteurs était une structure de treillis, cela une vingtaine d'années avant l'arrivée de l'analyse formelle de concepts (FCA pour "Formal Concept Analysis"), qui s'affirme maintenant comme un formalisme théorique important et solide pour l'analyse de données et la découverte de connaissances.Actuellement, la communauté en recherche d'information (RI) s'intéresse particulièrement à des techniques avancées pour la recherche des documents qui relèvent des probabilités et des statistiques.En parallèle, l'intérêt de la communauté FCA au développement de techniques qui font avancer l'état de l'art en RI tout en offrant des fonctionnalités sémantiques lui est toujours bien vivant.Dans cette thèse, nous présentons un ensemble de contributions sur ce que nous avons appelé les systèmes FCA de recherche d'information ("FCA-based IR systems"). Nous avons divisé nos contributions en deux parties, à savoir l'extraction et l'indexation. Pour la récupération, nous proposons une nouvelle technique qui exploite les relations sémantiques entre les descripteurs dans un corpus de documents.Pour l'indexation, nous proposons un nouveau modèle qui permet de mettre en oeuvre un modèle vectoriel d'indexation des documents s'appuyant sur un treillis de concepts (ou treillis de Galois). En outre, nous proposons un modèle perfectionné pour l'indexation hétérogène dans lequel nous combinons le modèle vectoriel et le modèle de recherche booléen.Finalement, nous présentons une technique de fouille de données inspiré de l'indexation des documents, à savoir un modèle d'énumération exhaustive des biclusters en utilisant la FCA.Le biclustering est une nouvelle technique d'analyse de données dans laquelle les objets sont liés via la similitude dans certains attributs de l'espace de description, et non pas par tous les attributs comme dans le "clustering" standard. En traduisant ce problème en termes d'analyse formelle de concepts, nous pouvons exploiter l'algorithmique associée à la FCA pour développer une technique d'extraction de biclusters de valeurs similaires. Nous montrons le très bon comportement de notre technique, qui fonctionne mieux que les techniques actuelles de biclustering avec énumération exhaustive.

Ontologies are used in different fields like the semantic Web or the knowledge engineering. The ontologies allow to share, to diffuse and to update knowledge domain. This thesis propose a methodology to build ontologies using methods of Natural Language Processing (NLP) and Information Extraction (IE) for extracting prepared data from each kind of available resources in the domain (text corpora, databases, thesaurus). Then, these prepared data are mining with the mining methods : Formal Concepts Analysis (FCA) and Relational Concepts Analysis (RCA). The FCA regroups a set of objects sharing the same set of attributes in the same concept. The RCA, an extension of the FCA regroups a set of objects sharing the same attributes and the same relations (relational attributes) in the same concept. The apposition of contexts, a property of the FCA, affects a set of attributes and relational attributes to classes pre-defined and hierarchised by the domain experts. These affectations allow us to present classes and their definitions to the experts of domain as well as new nonexistent classes in the initial hierarchy. These new classes can be considered appropriate and added by experts as new « knowledge units ». The Lattices resulting from the data mining methods are considered as « ontology schema ». This ontology schema is represented in the FLE description logics language to obtain ontology. This ontology is implemented in the OWL language (Web Ontology Language) for allowing us to request it. This methodology was tested in different domains: Microbiology and Astronomy., Les ontologies sont diversement employées notamment dans les domaines du Web sémantique, de l'ingénierie des connaissances,... En effet, elles permettent de partager, de diffuser et d'actualiser les connaissances d'un domaine. Afin de construire ces ontologies, notre méthodologie utilise tout d'abord des méthodes de Traitement Automatique de la Langue Naturelle (TALN) et d'Extraction d'Information (IE) pour extraire des données préparées à partir de chaque ressource du domaine (corpus de textes, bases de données, thesaurus). Puis, ces données sont fouillées avec les méthodes de fouilles : l'Analyse Formelle de concepts (AFC) et l'Analyse Relationnelle de Concepts (ARC). L'AFC regroupe des objets partageant les mêmes attributs binaires dans des concepts d'un treillis. L'ARC est une extension de l'AFC qui permet de regrouper des objets partageant les mêmes attributs binaires, mais aussi les mêmes attributs relationnels. L'apposition de contextes (une propriété de l'AFC) permet d'associer ces attributs (binaires et relationnels) à un ensemble de classes prédéfinies et hiérarchisées par les experts du domaine. De cette façon, des définitions étendues sont proposées aux experts du domaine pour ces classes prédéfinies ainsi que de nouvelles classes inexistantes dans la hiérarchie initiale. Ces nouvelles classes peuvent être considérées pertinentes et ajoutées par les experts en tant que nouvelles « unités de connaissances ». Les treillis résultant des méthodes de fouille constituent ce que nous appelons schéma d?ontologie. Ce schéma d'ontologie est ensuite représenté par le langage FLE de la famille des logiques de descriptions afin d'avoir une ontologie. Cette ontologie, implémentée en OWL (Web Ontology Language), a permis à notre système de répondre automatiquement à différentes questions proposées par les experts du domaine (instanciation de concepts, comparaison de concepts,...). Des expériences pratiques ont été menées dans deux domaines d'application que sont l'astronomie et la microbiologie.

Millions of chemical reactions are described in databases as transformations of molecular graphs. This thesis proposes different data-mining methods to extract relevant patterns included in those graphs and therefore to help chemists in improving knowledge about chemical reactions and molecules. One first shows how the central problem of searching frequent reaction patterns can be solved using existing graph-mining methods. Introducing the general model of most informative patterns then allows experts to reduce the analysis of these frequent patterns to a very small set of non-redundant patterns characteristic of data. If the application of this model to reaction database identifies large and characteristic families of reactions, the model doesn't allow in practice the extraction of reaction patterns characteristic of synthesis methods (abbr. CSM patterns) as their frequencies are far too low. In order to overcome this problem, is introduced a heuristic search algorithm based on a graph interval constraint and able to extract patterns with very low frequency. Thus this method determines from examples of chemical reactions and under some conditions the CSM pattern underlying a given input reaction. The same approach is then used to address the problem of supervised classification of vertices or edges based on their environment and then applied to evaluate formability of bonds in molecules. Experimental results have been analyzed by experts and are very encouraging., Des millions de réactions chimiques sont décrites dans des bases de données sous la forme de transformations de graphes moléculaires. Cette thèse propose différentes méthodes de fouille de donnés pour extraire des motifs pertinents contenus dans ces graphes et ainsi aider les chimistes à améliorer leurs connaissances des réactions chimiques et des molécules. Ainsi on commence par montrer comment le problème central de la recherche des schémas de réactions fréquents peut se résoudre à l'aide de méthodes existantes de recherche de sous-graphes fréquents. L'introduction du modèle général des motifs les plus informatifs permet ensuite de restreindre l'analyse de ces motifs fréquents à un nombre réduit de motifs peu redondants et représentatifs des données. Si l'application du modèle aux bases de réactions permet d'identifier de grandes familles de réactions, le modèle est inadapté pour extraire les schémas caractéristiques de méthodes de synthèse (schémas CMS) dont la fréquence est trop faible. Afin de surmonter cet obstacle, est ensuite introduite une méthode de recherche heuristique fondée sur une contrainte d'intervalle entre graphes et adaptée à l'extraction de motifs de très faible fréquence. Cette méthode permet ainsi de déterminer à partir d'exemples de réactions et sous certaines conditions le schéma CMS sous-jacent à une réaction donnée. La même approche est ensuite utilisée pour traiter le problème de la classification supervisée de sommets ou d'arêtes fondée sur leurs environnements puis exploitée pour évaluer la formabilité des liaisons d'une molécule. Les résultats produits ont pu être analysés par des experts de la synthèse organique et sont très encourageants.

This thesis deals with knowledge-based biological data sources discovery. First, domain ontologies are used for encoding metadata describing the content of biological data sources. Then the data sources are organized into a concept lattice according to their common metadata. The data source discovery process can be performed either by navigation into the obtained concept lattice or by defining queries to be inserted into the concept lattice. In both cases, domain knowledge can be used to guide the discovery. In the case of navigation, domain knowledge is used to reduce the search space and/or to guide the navigation to some concepts rather than others. In the case of querying, domain knowledge is used to express preferences between the query keywords or to refine the query. In order to take more advantage of domain knowledge, we introduce many-valued concept lattices. Several many-valued concept lattices with different levels of precision can be built from the data sources metadata set based on domain knowledge. The use of such many-valued concept lattices allows to improve the discovery process in its both forms. In the case of navigation, it is possible to consider more than one lattice and to dynamically switch form ont to another in a zooming operation. In the case of querying, more complex expressive queries can be defined and inserted into the many-valued concept lattice.; Cette thèse porte sur l'exploitation des connaissances de domaine dans un processus de découvertes de sources de données biologiques sur le Web. Tout d'abord, des ontologies de domaine sont utilisées pour représenter un ensemble de connaissances qui reflètent le contenu et la qualité des sources de données. Ensuite, en s'appuyant sur ces connaissances, les sources sont organisées dans un treillis de concepts en fonction de leurs caractéristiques communes. Le treillis de concept constitue le support de la découverte qui peut être effectuée de deux manières différentes et complémentaires : par navigation et par interrogation. Dans les deux cas la découverte peut être guidée par des connaissances de domaines. Lors d'une découverte par navigation, les connaissances sont utilisées soit pour réduire l'espace de recherche soit pour orienter la navigation vers des concepts plutôt que d'autres. Lors d'une découverte par interrogation les connaissances de domaine sont soit exprimées sous la forme de préférences entre mots clés dans la requête soit utilisées pour l'enrichissement (ou reformulation) de la requête. Pour assurer une meilleure prise en compte des connaissances de domaine nous avons introduit les treillis de concepts multivalués. L'organisation des sources sous la forme d'un treillis de concepts multivalués permet de contrôler la taille de l'espace de recherche et d'augmenter la flexibilité et les performances du processus de découverte dans ses deux modes. La navigation peut être effectuée dans des treillis de différents niveaux de précision avec la possibilité d'effectuer des zooms dynamiques permettant le passage d'un treillis à l'autre. L'interrogation bénéficie d'une augmentation de l'expressivité dans les requêtes.

This thesis deals with knowledge-based biological data sources discovery. First, domain ontologies are used for encoding metadata describing the content of biological data sources. Then the data sources are organized into a concept lattice according to their common metadata. The data source discovery process can be performed either by navigation into the obtained concept lattice or by defining queries to be inserted into the concept lattice. In both cases, domain knowledge can be used to guide the discovery. In the case of navigation, domain knowledge is used to reduce the search space and/or to guide the navigation to some concepts rather than others. In the case of querying, domain knowledge is used to express preferences between the query keywords or to refine the query. In order to take more advantage of domain knowledge, we introduce many-valued concept lattices. Several many-valued concept lattices with different levels of precision can be built from the data sources metadata set based on domain knowledge. The use of such many-valued concept lattices allows to improve the discovery process in its both forms. In the case of navigation, it is possible to consider more than one lattice and to dynamically switch from one lattice to another in a zooming operation. In the case of querying, more complex expressive queries can be defined and inserted into the many-valued concept lattice., Cette thèse porte sur l'exploitation des connaissances de domaine dans un processus de découvertes de sources de données biologiques sur le Web. Tout d'abord, des ensembles de métadonnées sont utilisés pour décrire le contenu et la qualité des sources de données. Ensuite, en s'appuyant sur ces métadonnées, les sources sont organisées dans un treillis de concepts en fonction de leurs caractéristiques communes. Le treillis de concepts constitue le support de la découverte de sources de données qui s'effectue de deux manières différentes et complémentaires : par navigation et par interrogation. Dans les deux cas la découverte de sources de données peut être guidée par des connaissances du domaine. Lors d'une découverte de sources de données par navigation, les connaissances sont utilisées soit pour réduire l'espace de recherche soit pour orienter la navigation vers des concepts sectionnés. Lors d'une découverte de sources de données par interrogation, les connaissances du domaine sont soit exprimées sous la forme de préférences entre métadonnées dans la requête soit utilisées pour l'enrichissement (ou reformulation) de la requête. Pour assurer une prise en compte des connaissances du domaine plus fidèle, nous avons introduit les treillis de concepts multivalués. L'organisation des sources de données sous la forme d'un treillis de concepts multivalués permet de contrôler la taille de l'espace de recherche et d'augmenter la flexibilité et les performances du processus de découverte dans ses deux modes. La navigation peut être effectuée dans des treillis de différents niveaux de spécialisation avec la possibilité d'effectuer des zooms dynamiques permettant le passage d'un treillis à l'autre. L'interrogation bénéficie d'une augmentation de l'expressivité dans les requêtes.

Chronic diseases are a major concern in public health. They require a multidisciplinary approach and chronic patients have multiple contacts with the healthcare system. In order to improve quality of life, quality and efficiency of healthcare, the care process of chronic patients must be assessed. This implies that the whole succession of health events of such patients should be monitored. From now on, in France, no information system was design to describe cross-institutional and long-term patient care trajectories. Moreover, there have been few attempts to classify and build a typology of patient trajectories. However, enormous amount of data are collected each year by several healthcare information systems. In this work, we propose a new approach to analyze and represent patient care trajectories from data that are originally collected for a different purpose. Our system is based on Formal Concept Analysis (FCA). FCA is a method of conceptual classification aiming at discovering natural relationships in a binary table and representing them in a concept lattice. We show the advantages of FCA for describing and understanding processes in the healthcare system and we give some perspectives for the exploration of social networks in general. We also study and compare two measures of interestingness of concepts : stability and support. The measures are computed in order to reduce the complexity of big concept lattices and filter the most relevant knowledge. Drawing a parallel with itemset mining and sequential itemset mining, we propose an unsupervised classification method with interesting properties for visualization and interpretation., Enjeu majeur de santé publique, les maladies chroniques nécessitent souvent une approche multidisciplinaire et des contacts multiples entre le patient et le système de soins. La maîtrise de ce parcours, la trajectoire de soins, est un gage de qualité des soins, qualité de vie et d'efficience médico-économique. Pour maîtriser les trajectoires de soins, il faut les connaître. Or, à ce jour en France, aucun système d'information en santé à grande échelle n'est conçu pour décrire les trajectoires de soins, encore moins d'en établir une typologie. Malgré tout, d'énormes quantités de données sont produites chaque année par le système de soins. Dans ce travail, nous proposons un système d'analyse et de représentation des trajectoires de soins à partir de données récoltées à l'origine pour d'autres utilisations. Ce système est fondé sur l'Analyse Formelle de Concepts (AFC), une méthode de classification conceptuelle capable de découvrir des liens naturels dans les données d'un tableau binaire et de les représenter sous forme de treillis de concepts. Nous montrons les apports de l'AFC dans la compréhension du fonctionnement du système de soins et les perspectives en termes d'exploration des réseaux sociaux en général. Par ailleurs, nous étudions, combinons et comparons deux mesures d'intérêt pour réduire la complexité des grands treillis et sélectionner les connaissances les plus pertinentes : la stabilité et le support d'un concept. Dans un parallèle avec la recherche de motifs fréquents simple et séquentiels, nous proposons une méthode de classification non supervisée des trajectoires de soins qui présente d'intéressantes capacités de visualisation et d'interprétabilité.

This thesis presents an application and some extensions of the semantic Web principles and technologies for the building of a portal dedicated to knowledge management in oncology. OWL, the Web ontology language, is used for representing the knowledge contained in medical decision protocols. The inferences associated with OWL are applied for decision support for the purpose of protocol application. But the knowledge contained in the protocols is not sufficient to take into account all the possible situations and needs to be adapted for some particular cases. For this reason, we propose an extension of the semantic Web technologies in order to allow the representation of adaptation knowledge and to implement a case-based reasoning (CBR) mechanism integrated to the semantic Web infrastructure. Furthermore, in complex domains like oncology, there exist multiple viewpoints, that are different ways to consider the domain knowledge and different ways to use it. The idea of ontology does not take into account this multiplicity of viewpoints. For this reason, we have studied the knowledge representation formalisms that explicitly integrate viewpoints.We have chosen the C-OWL language in order to establish a multiple viewpoint representation of the knowledge contained in the protocols, in accordance with the semantic Web technologies. On the basis of this multiple viewpoint representation in C-OWL, a decentralized CBR mechanism is defined. It exploits the viewpoints to distribute CBR in several processes. The relations existing between viewpoints are then used to allow knowledge sharing and collaboration between these multiple processes. Following the application in oncology, the multiple viewpoint representation has shown contributions concerning some of the difficulties of knowledge engineering (acquisition, evolution), the building of the CBR mechanism (use of several cases, viewpoint combination) and the scalability of reasoning mechanisms for the semantic Web, including CBR.; Cette thèse présente une application et des extensions des principes et des technologies relatives au Web sémantique pour la construction d'un portail dédié à la gestion des connaissances en cancérologie. OWL, langage de représentation d'ontologies, est notamment employé pour la représentation des connaissances contenues dans les référentiels, sortes de protocoles de décision médicaux. Les inférences associées à OWL sont utilisées pour l'aide à la décision dans le cadre de l'application des référentiels. Mais les connaissances contenues dans les référentiels ne permettent pas de prendre en compte toutes les situations et nécessitent d'être adaptées pour certains cas particuliers. Pour cette raison, nous proposons une extension des technologies du Web sémantique afin de permettre la représentation de connaissances d'adaptation et l'implémentation d'un mécanisme de raisonnement à partir de cas (RÀPC) intégré à l'infrastructure du Web sémantique. Par ailleurs, dans des domaines complexes tels que la cancérologie, coexistent différents points de vue, c'est-à-dire différentes façons de considérer les connaissances du domaine et différentes façons de les utiliser. La notion d'ontologie ne permet pas de prendre en compte cette multiplicité de points de vue. Pour cette raison, nous avons étudié les formalismes de représentation des connaissances intégrant de façon explicite la notion de point de vue. Nous nous appuyons sur le langage C-OWL afin d'établir une représentation multi-points de vue des connaissances contenues dans les référentiels en accord avec les technologies du Web sémantique. Sur la base de cette représentation multi-points de vue en C-OWL, un mécanisme de RÀPC décentralisé est défini. Celui-ci exploite les multiples points de vue pour distribuer le RÀPC en différents processus. Les relations existant entre les points de vue sont quant à elles utilisées pour l'échange de connaissances et la collaboration entre ces différents processus. Au travers de l'application en cancérologie, la représentation multi-points de vue montre ainsi des apports concernant les difficultés inhérentes à l'ingénierie des connaissances (acquisition, évolution), la mise en oeuvre du mécanisme de RÀPC (utilisation de plusieurs cas, combinaison de points de vue) et le « passage à l'échelle » des mécanismes de raisonnements pour le Web sémantique, RÀPC compris.

The frame of this study is the case-based reasoning to bring a better understanding of relationships between spatial and functional organisation within a farm environment. Research initial data is based on interviews of farm owners. This data was compiled in choremes, that highlight the core entities for analysis. Their spatial organisation enable the connection with their functional organisation. We use graphs to model these choremes. They also have the convenience that they can be entered directly in the computer. This effort to formalise choremes into graphs has greatly modified the appearance of choremes and brings to the constitution of a cases base and a knwoledge model domain of concepts. Comparing graphs, with the principles of Case Based Reasoning, enable the matching of organisations. Thus the analysis of the behaviour of a farm from which we would only know the spatial description can be done by asking the system to retrieve explanation from previously analysed data., Cette thèse porte sur l'étude du raisonnement à partir de cas pour aider à l'interprétation d'organisations spatiales agricoles. Les agronomes effectuent des enquêtes auprès d'exploitants agricoles, afin d'appréhender les relations entre structure spatiale et fonctionnement des exploitations. Des chorèmes d'exploitations, permettent de synthétiser ces données d'enquêtes. Nous avons modélisé l'organisation spatiale des exploitations par des graphes bipartites. à certains sous-graphes, décrivant des structures spatiales intéressantes, sont adjoints des explications, décrivant l'organisation fonctionnelle, pour constituer des cas. La modélisation conjointe a abouti à la reconception des chorèmes et à la constitution d'une base de cas et de hiérarchies de concepts du domaine. Le système de RàPC ROSA permet de proposer des explications de fonctionnement à un graphe en utilisant les cas enregistrés. La comparaison des graphes s'appuie sur le mécanisme des logiques de descriptions.

This thesis presents an application and some extensions of the semantic Web principles and technologies for the building of a portal dedicated to knowledge management in oncology. OWL, the Web ontology language, is used for representing the knowledge contained in medical decision protocols. The inferences associated with OWL are applied for decision support for the purpose of protocol application. But the knowledge contained in the protocols is not sufficient to take into account all the possible situations and needs to be adapted for some particular cases. For this reason, we propose an extension of the semantic Web technologies in order to allow the representation of adaptation knowledge and to implement a case-based reasoning (CBR) mechanism integrated to the semantic Web infrastructure. Furthermore, in complex domains like oncology, there exist multiple viewpoints, that are different ways to consider the domain knowledge and different ways to use it. The idea of ontology does not take into account this multiplicity of viewpoints. For this reason, we have studied the knowledge representation formalisms that explicitly integrate viewpoints.We have chosen the C-OWL language in order to establish a multiple viewpoint representation of the knowledge contained in the protocols, in accordance with the semantic Web technologies. On the basis of this multiple viewpoint representation in C-OWL, a decentralized CBR mechanism is defined. It exploits the viewpoints to distribute CBR in several processes. The relations existing between viewpoints are then used to allow knowledge sharing and collaboration between these multiple processes. Following the application in oncology, the multiple viewpoint representation has shown contributions concerning some of the difficulties of knowledge engineering (acquisition, evolution), the building of the CBR mechanism (use of several cases, viewpoint combination) and the scalability of reasoning mechanisms for the semantic Web, including CBR.; Cette thèse présente une application et des extensions des principes et des technologies relatives au Web sémantique pour la construction d'un portail dédié à la gestion des connaissances en cancérologie. OWL, langage de représentation d'ontologies, est notamment employé pour la représentation des connaissances contenues dans les référentiels, sortes de protocoles de décision médicaux. Les inférences associées à OWL sont utilisées pour l'aide à la décision dans le cadre de l'application des référentiels. Mais les connaissances contenues dans les référentiels ne permettent pas de prendre en compte toutes les situations et nécessitent d'être adaptées pour certains cas particuliers. Pour cette raison, nous proposons une extension des technologies du Web sémantique afin de permettre la représentation de connaissances d'adaptation et l'implémentation d'un mécanisme de raisonnement à partir de cas (RÀPC) intégré à l'infrastructure du Web sémantique. Par ailleurs, dans des domaines complexes tels que la cancérologie, coexistent différents points de vue, c'est-à-dire différentes façons de considérer les connaissances du domaine et différentes façons de les utiliser. La notion d'ontologie ne permet pas de prendre en compte cette multiplicité de points de vue. Pour cette raison, nous avons étudié les formalismes de représentation des connaissances intégrant de façon explicite la notion de point de vue. Nous nous appuyons sur le langage C-OWL afin d'établir une représentation multi-points de vue des connaissances contenues dans les référentiels en accord avec les technologies du Web sémantique. Sur la base de cette représentation multi-points de vue en C-OWL, un mécanisme de RÀPC décentralisé est défini. Celui-ci exploite les multiples points de vue pour distribuer le RÀPC en différents processus. Les relations existant entre les points de vue sont quant à elles utilisées pour l'échange de connaissances et la collaboration entre ces différents processus. Au travers de l'application en cancérologie, la représentation multi-points de vue montre ainsi des apports concernant les difficultés inhérentes à l'ingénierie des connaissances (acquisition, évolution), la mise en oeuvre du mécanisme de RÀPC (utilisation de plusieurs cas, combinaison de points de vue) et le « passage à l'échelle » des mécanismes de raisonnements pour le Web sémantique, RÀPC compris.