Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Un flot de liens représente une trace de l'activité d'un système complexe au cours du temps, où un lien apparaît lorsque deux entités du système entrent en interaction ; l'ensemble des entités et des liens forme un graphe. Ces traces constituent depuis quelques années des jeux de données stratégiques dans l'analyse de l'activité de systèmes complexes à grande échelle, impliquant des millions d'entités : réseaux de téléphone mobiles, réseaux sociaux, ou encore Internet. Cette thèse porte sur l'analyse exploratoire des flots de liens, en particulier sur la caractérisation de leur dynamique et l'identification d'anomalies au cours du temps (événements). Nous proposons un cadre exploratoire sans hypothèse sur les données, faisant appel à l'analyse statistique et à la visualisation. Les événements détectés sont statistiquement significatifs et nous proposons une méthode pour valider leur pertinence. Nous illustrons enfin notre méthodologie sur l'évolution du réseau social en ligne Github, où des centaines de milliers de développeurs collaborent sur des projets de logiciel.

Les travaux de recherche présentés par l'auteur ont pour objet l'application de techniques d'extraction de connaissances à partir de données (ECD) en biologie. Deux thèmes majeurs de recherche en bio-informatique sont abordés : la recherche d'homologues distants dans des familles de protéines et l'analyse du transcriptome. La recherche d'homologues distants à partir de séquences protéiques est une problématique qui consiste à découvrir de nouveaux membres d'une famille de protéines. Celle-ci partageant généralement une fonction biologique, l'identification de la famille permet d'investiguer le rôle d'une séquence protéique. Des classifieurs ont été développés pour discriminer une superfamille de protéines particulière, celle des cytokines. Ces protéines sont impliquées dans le système immunitaire et leur étude est d'une importance cruciale en thérapeutique. La technique des Séparateurs à Vastes Marges (SVM) a été retenue, cette technique ayant donné les résultats les plus prometteurs pour ce type d'application. Une méthode originale de classification a été conçue, basée sur une étape préliminaire de découverte de mots sur-représentés dans la famille d'intérêt. L'apport de cette démarche est d'utiliser un dictionnaire retreint de motifs discriminants, par rapport à des techniques utilisant un espace global de k-mots. Une comparaison avec ces dernières méthodes montre la pertinence de cette approche en termes de performances de classification. La seconde contribution pour cette thématique porte sur l'agrégation des classifieurs basée sur des essaims grammaticaux. Cette méthode vise à optimiser l'association de classifieurs selon des modèles de comportement sociaux, à la manière des algorithmes génétiques d'optimisation. Le deuxième axe de recherche traite de l'analyse des données du transcriptome. L'étude du transcriptome représente un enjeu considérable, tant du point de vue de la compréhension des mécanismes du vivant que des applications cliniques et pharmacologiques. L'analyse implicative sur des règles d'association, développée initialement par Régis Gras, a été appliquée aux données du transcriptome. Une approche originale basée sur des rangs d'observation a été proposée. Deux applications illustrent la pertinence de cette méthode : la sélection de gènes informatifs et la classification de tumeurs. Enfin, une collaboration étroite avec une équipe INSERM dirigée par Rémi Houlgatte a conduit à l'enrichissement d'une suite logicielle dédiée aux données de puces à ADN. Cette collection d'outils dénommée MADTOOLS a pour objectifs l'intégration de données du transcriptome et l'aide à la méta-analyse. Une application majeure de cette suite utilise les données publiques relatives aux pathologies musculaires. La méta-analyse, en se basant sur des jeux de données indépendants, améliore grandement la robustesse des résultats. L'étude systématique de ces données a mis en évidence des groupes de gènes co-exprimés de façon récurrente. Ces groupes conservent leur propriété discriminante au travers de jeux très divers en termes d'espèces, de maladies ou de conditions expérimentales. Cette étude peut évidemment se généraliser à l'ensemble des données publiques concernant le transcriptome. Elle ouvre la voie à une approche à très grande échelle de ce type de données pour l'étude d'autres pathologies humaines.

La conception des systèmes multimédia embarqués présente de nombreux défis comme la croissante complexité du logiciel et du matériel sous-jacent, ou les pressions liées aux délais de mise en marche. L'optimisation du processus de débogage et validation du logiciel peut aider à réduire sensiblement le temps de développement. Parmi les outils de débogage de systèmes embarqués, un puissant outil largement utilisé est l'analyse de traces d'exécution. Cependant, l'évolution des techniques de tra¸cage dans les systèmes embarqués se traduit par des traces d'exécution avec une grande quantité d'information, à tel point que leur analyse manuelle devient ingérable. Dans ce cas, les techniques de recherche de motifs peuvent aider en trouvant des motifs intéressants dans de grandes quantités d'information. Concrètement, dans cette thèse, nous nous intéressons à la découverte de comportements périodiques sur des applications multimédia. Donc, les contributions de cette thèse concernent l'analyse des traces d'exécution d'applications multimédia en utilisant des techniques de recherche de motifs périodiques fréquents. Concernant la recherche de motifs périodiques, nous proposons une définition de motif périodique adaptée aux caractéristiques de la programmation paralléle. Nous proposons ensuite une représentation condensée de l'ensemble de motifs périodiques fréquents, appelée Core Periodic Concepts (CPC), en adoptant une approche basée sur les relations triadiques. De plus, nous définissons quelques propriétés de connexion entre ces motifs, ce qui nous permet de mettre en oeuvre un algorithme efficace de recherche de CPC, appelé PerMiner. Pour montrer l'efficacité et le passage à l'échelle de PerMiner, nous réalisons une analyse rigoureuse qui montre que PerMiner est au moins deux ordres de grandeur plus rapide que l'état de l'art. En plus, nous réalisons un analyse de l'efficacité de PerMiner sur une trace d'exécution d'une application multimédia réelle en présentant l'accélération accompli par la version parallèle de l'algorithme. Concernant les systèmes embarqués, nous proposons un premier pas vers une méthodologie qui explique comment utiliser notre approche dans l'analyse de traces d'exécution d'applications multimédia. Avant d'appliquer la recherche de motifs fréquents, les traces d'exécution doivent ˆetre traitées, et pour cela nous proposons plusieurs techniques de pré-traitement des traces. En plus, pour le post-traitement des motifs périodiques, nous proposons deux outils : un outil qui trouve des pairs de motifs en compétition ; et un outil de visualisation de CPC, appelé CPCViewer. Finalement, nous montrons que notre approche peut aider dans le débogage des applications multimédia à travers deux études de cas sur des traces d'exécution d'applications multimédia réelles.

Les masses de données textuelles aujourd'hui disponibles engendrent un problème difficile lié à leur traitement automatique. Dans ce cadre, des méthodes de Fouille de Textes (FT) et de Traitement Automatique du Langage (TAL) peuvent, en partie, répondre à une telle problématique. Elles consistent à modéliser puis mettre en œuvre des méthodologies appliquées aux données textuelles afin d'en déterminer le sens et/ou découvrir des connaissances nouvelles. Dans ce processus, le descripteur linguistique constitue un élément pivot. Après une présentation des méthodes de traitement des descripteurs en eux-mêmes, ces derniers seront étudiés en contexte, c'est-à-dire en corpus. L'identification des descripteurs est souvent difficile à partir de corpus bruités et à faible contenu textuel sur lesquels nous concentrons nos efforts (par exemple, corpus issus du Web 2.0 ou du traitement OCR). Outre les mots considérés comme des descripteurs linguistiques pertinents en FT, nous nous sommes également intéressés à l'étude des syntagmes complexes à partir de corpus classiques puis d'une terminologie classique à partir de corpus complexes (par exemple, données logs ou corpus en français médiéval). Dans la suite, les syntagmes étudiés ne se situent plus à proprement parler dans les textes mais ils seront induits à partir des mots issus des corpus. Les méthodes proposées permettent de mettre en relief des syntagmes originaux tout à fait utiles pour l'identification d'Entités Nommées, le titrage automatique ou la construction de classes conceptuelles. Contrairement au raisonnement déductif, le raisonnement inductif est dit hypothétique. Dans ce cadre, l'utilisation de méthodes de validation automatique des relations induites par le biais d'approches de Fouille du Web se révèle déterminant. Les perspectives à ce travail se concentreront sur l'extraction de nouveaux descripteurs. Ces derniers seront associés à de nouvelles représentations sous forme d'entrepôts de données textuelles. Enfin, les travaux que nous souhaitons développer se focaliseront sur l'analyse des textes dans un contexte plus vaste lié au multimédia que le paradigme du Web 2.0 a mis en exergue ces dernières années.

Le développement des systèmes de télésurveillance médicale à domicile est fondamental face au vieillissement de la population et aux capacités limitées d admission dans les hôpitaux et centres spécialisés. Ce travail de thèse concerne particulièrement la conception d un assistant intelligent pour l analyse des données hétérogènes collectées par des capteurs au domicile afin de détecter, voire prévenir, l occurrence de situations inquiétantes. Il s agit de concevoir un système d apprentissage des habitudes de vie d une personne, tout écart par rapport à ce profil comportemental étant considéré comme critique. L étude proposée concerne d une part la conception d un processus de simulation pour la génération de grandes quantités de données appropriées au contexte expérimental. D autre part, une méthode générique pour l extraction non supervisée de motifs dans des séquences temporelles multidimensionnelles et hétérogènes est proposée puis expérimentée dans le contexte de l identification des comportements récurrents d une personne dans ses activités quotidiennes. On évalue en particulier les indices de sensibilité (tolérance aux modifications normales de comportement) et de spécificité (rejet des modifications inquiétantes) du système. L application du système d apprentissage aux séquences générées par la simulation permet également de vérifier l extraction possible de comportements récurrents interprétés a posteriori en terme de la réalisation d activités de la vie quotidienne.

Les systèmes de géolocalisation permettent la surveillance en temps réel des déplacements d'objets mobiles. Aujourd'hui, les données produites par ces capteurs sont reçues et stockées dans des bases de données spatio-temporelles. Un processus de fouille de données appliqué sur ces bases de données spatio-temporelles permet d'extraire le comportement des objets mobiles (patrons spatio-temporels) et d'analyser en temps réel les trajectoires d'objets mobiles suivant un même itinéraire. En utilisant ces modèles, des situations inhabituelles peuvent être détectés. Cette thèse définit à la fois des patrons spatio-temporels ainsi que des outils de comparaison et de qualification de trajectoires en utilisant un indice de similarité basée sur des mesures spatiales et temporelles et la logique floue. Ces outils peuvent être utilisés pour faciliter la surveillance du trafic maritime.

Face à la complexité significative du domaine mammographique ainsi que l'évolution massive de ses données, le besoin de contextualiser les connaissances au sein d'une modélisation formelle et exhaustive devient de plus en plus impératif pour les experts. C'est dans ce cadre que s'inscrivent nos travaux de recherche qui s'intéressent à unifier différentes sources de connaissances liées au domaine au sein d'une modélisation ontologique cible. D'une part, plusieurs modélisations ontologiques mammographiques ont été proposées dans la littérature, où chaque ressource présente une perspective distincte du domaine d'intérêt. D'autre part, l'implémentation des systèmes d'acquisition des mammographies rend disponible un grand volume d'informations issues des faits passés, dont la réutilisation devient un enjeu majeur. Toutefois, ces fragments de connaissances, présentant de différentes évidences utiles à la compréhension de domaine, ne sont pas interopérables et nécessitent des méthodologies de gestion de connaissances afin de les unifier. C'est dans ce cadre que se situe notre travail de thèse qui s'intéresse à l'enrichissement d'une ontologie de domaine existante à travers l'extraction et la gestion de nouvelles connaissances (concepts et relations) provenant de deux courants scientifiques à savoir: des ressources ontologiques et des bases de données comportant des expériences passées. Notre approche présente un processus de couplage entre l'enrichissement conceptuel et l'enrichissement relationnel d'une ontologie mammographique existante. Le premier volet comporte trois étapes. La première étape dite de pré-alignement d'ontologies consiste à construire pour chaque ontologie en entrée une hiérarchie des clusters conceptuels flous. Le but étant de réduire l'étape d'alignement de deux ontologies entières en un alignement de deux groupements de concepts de tailles réduits. La deuxième étape consiste à aligner les deux structures des clusters relatives aux ontologies cible et source. Les alignements validés permettent d'enrichir l'ontologie de référence par de nouveaux concepts permettant d'augmenter le niveau de granularité de la base de connaissances. Le deuxième processus s'intéresse à l'enrichissement relationnel de l'ontologie mammographique cible par des relations déduites de la base de données de domaine. Cette dernière comporte des données textuelles des mammographies recueillies dans les services de radiologies. Ce volet comporte ces étapes : i) Le prétraitement des données textuelles ii) l'application de techniques relatives à la fouille de données (ou extraction de connaissances) afin d'extraire des expériences de nouvelles associations sous la forme de règles, iii) Le post-traitement des règles générées. Cette dernière consiste à filtrer et classer les règles afin de faciliter leur interprétation et validation par l'expert vi) L'enrichissement de l'ontologie par de nouvelles associations entre les concepts. Cette approche a été mise en 'uvre et validée sur des ontologies mammographiques réelles et des données des patients fournies par les hôpitaux Taher Sfar et Ben Arous. / Facing the significant complexity of the mammography area and the massive changes in its data, the need to contextualize knowledge in a formal and comprehensive modeling is becoming increasingly urgent for experts. It is within this framework that our thesis work focuses on unifying different sources of knowledge related to the domain within a target ontological modeling. On the one hand, there is, nowadays, several mammographic ontological modeling, where each resource has a distinct perspective area of interest. On the other hand, the implementation of mammography acquisition systems makes available a large volume of information providing a decisive competitive knowledge. However, these fragments of knowledge are not interoperable and they require knowledge management methodologies for being comprehensive. In this context, we are interested on the enrichment of an existing domain ontology through the extraction and the management of new knowledge (concepts and relations) derived from two scientific currents: ontological resources and databases holding with past experiences. Our approach integrates two knowledge mining levels: The first module is the conceptual target mammographic ontology enrichment with new concepts extracting from source ontologies. This step includes three main stages: First, the stage of pre-alignment. The latter consists on building for each input ontology a hierarchy of fuzzy conceptual clusters. The goal is to reduce the alignment task from two full ontologies to two reduced conceptual clusters. The second stage consists on aligning the two hierarchical structures of both source and target ontologies. Thirdly, the validated alignments are used to enrich the reference ontology with new concepts in order to increase the granularity of the knowledge base. The second level of management is interested in the target mammographic ontology relational enrichment by novel relations deducted from domain database. The latter includes medical records of mammograms collected from radiology services. This section includes four main steps: i) the preprocessing of textual data ii) the application of techniques for data mining (or knowledge extraction) to extract new associations from past experience in the form of rules, iii) the post-processing of the generated rules. The latter is to filter and classify the rules in order to facilitate their interpretation and validation by expert, vi) The enrichment of the ontology by new associations between concepts. This approach has been implemented and validated on real mammographic ontologies and patient data provided by Taher Sfar and Ben Arous hospitals. The research work presented in this manuscript relates to knowledge using and merging from heterogeneous sources in order to improve the knowledge management process.

Les travaux présentés dans ce mémoire de thèse abordent sous différents angles très intéressants, un sujet vaste et ambitieux : l’interprétation de plans cadastraux couleurs.Dans ce contexte, notre approche se trouve à la confluence de différentes thématiques de recherche telles que le traitement du signal et des images, la reconnaissance de formes, l’intelligence artificielle et l’ingénierie des connaissances. En effet, si ces domaines scientifiques diffèrent dans leurs fondements, ils sont complémentaires et leurs apports respectifs sont indispensables pour la conception d’un système d’interprétation. Le centre du travail est le traitement automatique de documents cadastraux du 19e siècle. La problématique est traitée dans le cadre d'un projet réunissant des historiens, des géomaticiens et des informaticiens. D'une part nous avons considéré le problème sous un angle systémique, s'intéressant à toutes les étapes de la chaîne de traitements mais aussi avec un souci évident de développer des méthodologies applicables dans d'autres contextes. Les documents cadastraux ont été l'objet de nombreuses études mais nous avons su faire preuve d'une originalité certaine, mettant l'accent sur l'interprétation des documents et basant notre étude sur des modèles à base de graphes. Des propositions de traitements appropriés et de méthodologies ont été formulées. Le souci de comblé le gap sémantique entre l’image et l’interprétation a reçu dans le cas des plans cadastraux étudiés une réponse. / This thesis tackles the problem of technical document interpretationapplied to ancient and colored cadastral maps. This subject is on the crossroadof different fields like signal or image processing, pattern recognition, artificial intelligence,man-machine interaction and knowledge engineering. Indeed, each of thesedifferent fields can contribute to build a reliable and efficient document interpretationdevice. This thesis points out the necessities and importance of dedicatedservices oriented to historical documents and a related project named ALPAGE.Subsequently, the main focus of this work: Content-Based Map Retrieval within anancient collection of color cadastral maps is introduced.

L’objectif de la fouille de données consiste à extraire des connaissances à partir de grandes masses de données. Les connaissances extraites peuvent prendre différentes formes. Dans ce travail, nous allons chercher à extraire des connaissances uniquement sous la forme de règles d’association positives et de règles d’association négatives. Une règle d’association négative est une règle dans laquelle la présence ainsi que l’absence d’une variable peuvent être utilisées. En considérant l’absence des variables dans l’étude, nous allons élargir la sémantique des connaissances et extraire des informations non détectables par les méthodes d’extraction de règles d’association positives. Cela va par exemple permettre aux médecins de trouver des caractéristiques qui empêchent une maladie de se déclarer, en plus de chercher des caractéristiques déclenchant une maladie. Cependant, l’ajout de la négation va entraîner différents défis. En effet, comme l’absence d’une variable est en général plus importante que la présence de ces mêmes variables, les coûts de calculs vont augmenter exponentiellement et le risque d’extraire un nombre prohibitif de règles, qui sont pour la plupart redondantes et inintéressantes, va également augmenter. Afin de remédier à ces problèmes, notre proposition, dérivée de l’algorithme de référence A priori, ne va pas se baser sur les motifs fréquents comme le font les autres méthodes. Nous définissons donc un nouveau type de motifs : les motifs raisonnablement fréquents qui vont permettre d’améliorer la qualité des règles. Nous nous appuyons également sur la mesure M G pour connaître les types de règles à extraire mais également pour supprimer des règles inintéressantes. Nous utilisons également des méta-règles nous permettant d’inférer l’intérêt d’une règle négative à partir d’une règle positive. Par ailleurs, notre algorithme va extraire un nouveau type de règles négatives qui nous semble intéressant : les règles dont la prémisse et la conclusion sont des conjonctions de motifs négatifs. Notre étude se termine par une comparaison quantitative et qualitative aux autres algorithmes d’extraction de règles d’association positives et négatives sur différentes bases de données de la littérature. Notre logiciel ARA (Association Rules Analyzer ) facilite l’analyse qualitative des algorithmes en permettant de comparer intuitivement les algorithmes et d’appliquer en post-traitement différentes mesures de qualité. Finalement, notre proposition améliore l’extraction au niveau du nombre et de la qualité des règles extraites mais également au niveau du parcours de recherche des règles. / The purpose of data mining is to extract knowledge from large amount of data. The extracted knowledge can take different forms. In this work, we will seek to extract knowledge only in the form of positive association rules and negative association rules. A negative association rule is a rule in which the presence and the absence of a variable can be used. When considering the absence of variables in the study, we will expand the semantics of knowledge and extract undetectable information by the positive association rules mining methods. This will, for example allow doctors to find characteristics that prevent disease instead of searching characteristics that cause a disease. Nevertheless, adding the negation will cause various challenges. Indeed, as the absence of a variable is usually more important than the presence of these same variables, the computational costs will increase exponentially and the risk to extract a prohibitive number of rules, which are mostly redundant and uninteresting, will also increase. In order to address these problems, our proposal, based on the famous Apriori algorithm, does not rely on frequent itemsets as other methods do. We define a new type of itemsets : the reasonably frequent itemsets which will improve the quality of the rules. We also rely on the M G measure to know which forms of rules should be mined but also to remove uninteresting rules. We also use meta-rules to allow us to infer the interest of a negative rule from a positive one. Moreover, our algorithm will extract a new type of negative rules that seems interesting : the rules for which the antecedent and the consequent are conjunctions of negative itemsets. Our study ends with a quantitative and qualitative comparison with other positive and negative association rules mining algorithms on various databases of the literature. Our software ARA (Association Rules Analyzer ) facilitates the qualitative analysis of the algorithms by allowing to compare intuitively the algorithms and to apply in post-process treatments various quality measures. Finally, our proposal improves the extraction in the number and the quality of the extracted rules but also in the rules search path.