Qualité, Fouille et Gestion des Connaissances Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Sed non risus. Suspendisse lectus tortor, dignissim sit amet, adipiscing nec, ultricies sed, dolor. Cras elementum ultrices diam. Maecenas ligula massa, varius a, semper congue, euismod non, mi. Proin porttitor, orci nec nonummy molestie, enim est eleifend mi, non fermentum diam nisl sit amet erat. Duis semper. Duis arcu massa, scelerisque vitae, consequat in, pretium a, enim. Pellentesque congue. Ut in risus volutpat libero pharetra tempor. Cras vestibulum bibendum augue. Praesent egestas leo in pede. Praesent blandit odio eu enim. Pellentesque sed dui ut augue blandit sodales

Durant ces dernières années, les quantités de données collectées, dans divers domaines d'application de l'informatique, deviennent de plus en plus importantes. Cela suscite le besoin d'analyser et d'interpréter ces données afin d'en extraire des connaissances utiles. Dans cette situation, le processus d'Extraction de Connaissances à partir des Données est un processus complet visant à extraire des connaissances cachées, nouvelles et potentiellement utiles à partir de grands volumes de données. Parmi ces étapes, la fouille de données offre les outils et techniques permettant une telle extraction. Plusieurs travaux de recherche en fouille de données concernent la découverte des règles d'association, permettant d'identifier des liens entre ensembles de descripteurs (ou attributs ou items) décrivant un ensemble d'objets (ou individus ou transactions). Les règles d'association ont montré leur utilité dans plusieurs domaines d'application tels que la gestion de la relation client en grande distribution (analyse du panier de la ménagère pour déterminer les produits souvent achetés simultanément, et agencer les rayons et organiser les promotions en conséquence), la biologie moléculaire (analyse des associations entre gènes), etc. De manière générale, la construction des règles d'association s'effectue en deux étapes : l'extraction des ensembles d'items (ou itemsets) fréquents, puis la génération des règles d'association à partir de des itemsets fréquents. Dans la pratique, le nombre de motifs (itemsets fréquents ou règles d'associations) extraits ou générés, peut être très élevé, ce qui rend difficile leur exploitation pertinente par les utilisateurs. Pour pallier ce problème, certains travaux de recherche proposent l'usage d'un noyau de motifs, appelés représentations concises, à partir desquels les motifs redondants peuvent être régénérés. Le but de telles représentations est de condenser les motifs extraits tout en préservant autant que possible les informations cachées et intéressantes sur des données. Dans la littérature, beaucoup de représentations concises des motifs fréquents ont été proposées, explorant principalement l'espace de recherche conjonctif. Dans cet espace, les itemsets sont caractérisés par la fréquence de leur co-occurrence. Ceci fait l'objet de la première partie de ce travail. Une étude détaillée proposée dans cette thèse prouve que les itemsets fermés et les générateurs minimaux sont un moyen de représenter avec concision les itemsets fréquents et les règles d'association. Les itemsets fermés structurent l'espace de recherche dans des classes d'équivalence tels que chaque classe regroupe les itemsets apparaissant dans le même sous-ensemble (appelé aussi objets ou transactions) des données. Un itemset fermé inclut l'expression la plus spécifique décrivant les transactions associées, alors qu'un générateur minimal inclut une des expressions les plus générales. Cependant, une redondance combinatoire intra-classe résulte logiquement de l'absence inhérente d'un seul générateur minimal associé à un itemset fermé donné. Ceci nous amotivé à effectuer une étude approfondie visant à maintenir seulement les générateurs minimaux irréductibles dans chaque classe d'équivalence, et d'élaguer les autres. À cet égard, il est proposé une réduction sans perte d'information de l'ensemble des générateurs minimaux grâce à un nouveau processus basé sur la substitution. Une étude complète des propriétés associées aux familles obtenues est présentée. Les résultats théoriques sont ensuite étendus au cadre de règles d'association afin de réduire autant que possible le nombre de règles maintenues sans perte d'information. Puis, est présentée une étude formelle complète du mécanisme d'inférence permettant de dériver toutes les règles d'association redondantes, à partir de celles maintenues. Afin de valider l'approche proposée, les algorithmes de construction de ces représentations concises de motifs sont présentés ainsi que les résultats des expérimentations réalisées en terme de concision et de temps de calcul. La seconde partie de ce travail est consacrée à une exploration complète de l'espace de recherche disjonctif des itemsets, où ceux-ci sont caractérisés par leurs supports disjonctifs. Ainsi dans l'espace disjonctif, un itemset vérifie une transaction si au moins un de ses items y est présent. Les itemsets disjonctifs véhiculent ainsi une connaissance au sujet des occurrences complémentaires d'items dans un ensemble de données. Cette exploration est motivée par le fait que, dans certaines applications, une telle information peut être utile aux utilisateurs. Lors de l'analyse d'une séquence génétique par exemple, le fait d'engendrer une information telle que " présence d'un gène X ou la présence d'un gène Y ou ... " présente un intérêt pour le biologiste. Afin d'obtenir une représentation concise de l'espace de recherche disjonctif, une solution intéressante consiste à choisir un seul élément pour représenter les itemsets couvrant le même ensemble de données. Deux itemsets sont équivalents si leurs items respectifs couvrent le même ensemble de données. À cet égard, un nouvel opérateur consacré à cette tâche, a été introduit. Dans chaque classe d'équivalence induite, les éléments minimaux sont appelés itemsets essentiels, alors que le plus grand élément est appelé itemset fermé disjonctif. L'opérateur présenté est alors à la base de nouvelles représentations concises des itemsets fréquents. L'espace de recherche disjonctif est ensuite exploité pour dériver des règles d'association généralisées. Ces dernières règles généralisent les règles classiques pour offrir également des connecteurs de disjonction et de négation d'items, en plus de celui conjonctif. Des outils (algorithme et programme) dédiés ont été alors conçus et mis en application pour extraire les itemsets disjonctifs et les règles d'association généralisées. Les résultats des expérimentations effectuées ont montré l'utilité de notre exploration et ont mis en valeur la concision des représentations concises proposées.

Découvrir des renversements de tendances entre deux cubes de données offre aux utilisateurs une connaissance nouvelle et intéressante lors des fluctuations de l'univers réel modélisé : quelles sont les nouveautés ? Quelle tendance apparaît ou disparaît ? Nous introduisons le nouveau concept de Cube Émergent. Il capture les renversements de tendances en mettant en œuvre une contrainte d'émergence (conjonction de contrainte monotones et antimonotones). Les bordures, classiques en fouille de données, sont reprises pour le Cube Émergent. Dans un second temps, nous proposons un nouveau couple de bordures pour optimiser à la fois l'espace de stockage et le temps de calcul. Cette nouvelle représentation fournit une caractérisation simple de la taille du Cube Émergent aussi bien que des outils de classification et de navigation dans les cubes. La connexion entre les bordures classiques et celles proposées est formellement établie en utilisant le concept de cube transversal. Connaître la taille du Cube Émergent est d'un grand intérêt, en particulier pour ajuster au mieux la contrainte d'émergence sous-jacente. Cette problématique est traitée en étudiant une borne supérieure et en caractérisant la taille exacte du Cube Émergent. Deux stratégies sont proposées pour estimer rapidement cette taille : la première est basée sur une estimation analytique, sans accès à la base de données, la seconde s'appuie sur un comptage probabiliste utilisant les bordures proposées comme entrée de l'algorithme proche de l'optimal HYPERLOGLOG. Grâce à la particulière efficacité de cet algorithme, plusieurs itérations peuvent être réalisées pour calibrer au mieux la contrainte d'émergence. De plus, des nouvelles représentations réduites et sans perte d'information du Cube Émergent sont proposées en utilisant le concept de fermeture cubique.

Ce travail de thèse s'inscrit à l'intersection des deux domaines de recherche que sont l'extraction des connaissances dans les données (ECD) et de l'ingénierie des connaissances. Plus précisément, en nous appuyant sur la combinaison des travaux menés, d'une part sur l'alignement des ontologies, et d'autre part sur la fouille de règles d'association, nous proposons une nouvelle méthode d'alignement d'ontologies associées à des corpus textuels (taxonomies, hiérarchies documentaires, thésaurus, répertoires ou catalogues Web), appelée AROMA (\emph{Association Rule Matching Approach}).<br /><br />Dans la littérature, la plupart des travaux traitant des méthodes d'alignement d'ontologies ou de schémas s'appuient sur une définition intentionnelle des schémas et utilisent des relations basées sur des mesures de similarité qui ont la particularité d'être symétriques (équivalences). Afin d'améliorer les méthodes d'alignement, et en nous inspirant des travaux sur la découverte de règles d'association, des mesures de qualité associées, et sur l'analyse statistique implicative, nous proposons de découvrir des appariements asymétriques (implications) entre ontologies. Ainsi, la contribution principale de cette thèse concerne la conception d'une méthode d'alignement extensionnelle et orientée basée sur la découverte des implications significatives entre deux hiérarchies plantées dans un corpus textuel.<br />Notre méthode d'alignement se décompose en trois phases successives. La phase de prétraitement permet de préparer les ontologies à l'alignement en les redéfinissant sur un ensemble commun de termes extraits des textes et sélectionnés statistiquement. La phase de fouille extrait un alignement implicatif entre hiérarchies. La dernière phase de post-traitement des résultats permet de produire des alignements consistants et minimaux (selon un critère de redondance).<br /><br />Les principaux apports de cette thèse sont : (1) Une modélisation de l'alignement étendue pour la prise en compte de l'implication. Nous définissons les notions de fermeture et couverture d'un alignement permettant de formaliser la redondance et la consistance d'un alignement. Nous étudions également la symétricité et les cardinalités d'un alignement. (2) La réalisation de la méthode AROMA et d'une interface d'aide à la validation d'alignements. (3) Une extension d'un modèle d'évaluation sémantique pour la prise en compte de la présence d'implications dans un alignement. (4) L'étude du comportement et de la performance d'AROMA sur différents types de jeux de tests (annuaires Web, catalogues et ontologies au format OWL) avec une sélection de six mesures de qualité.<br /><br />Les résultats obtenus sont prometteurs car ils montrent la complémentarité de notre méthode avec les approches existantes.

L'analyse en ligne OLAP permet une navigation interactive dans les données, une visualisation rapide de l'information et une exploration de la structure multidimensionnelle des données. Une des limites est de se restreindre à des aspects exploratoires et navigationnels. De plus, avec l'avènement des données complexes (données multi-format et/ou multi-structure et/ou multi-source et/ou multi-modale et/ou multi-version), l'analyse en ligne doit s'adapter à la nature spécifique de ces données tout en gardant l'esprit de l'OLAP. Les opérateurs OLAP sont définis pour des données classiques et sont souvent inadaptés quand il s'agit de données complexes par exemple composées de textes, images, son ou vidéos. Les limites de l'OLAP ainsi que la spécificité des données complexes nécessitent une évolution ou adaptation de l'OLAP. Il devient nécessaire de : (1) enrichir les possibilités de l'analyse OLAP en la dotant de nouvelles possibilités ; (2) créer une analyse en ligne adaptée aux données complexes ; (3) faire évoluer l'OLAP vers une analyse sémantique des données. Dans cette vaste problématique, nous choisissons de traiter les questions d'agrégation et visualisation des données complexes, de réorganisation du cube pour identifier des régions d'analyse intéressantes, et d'étendre l'OLAP à des possibilités d'explication et de prédiction. Pour toutes ces questions, nous essayons également de tenir compte de la sémantique véhiculée par les données. Pour apporter des premières solutions, nous orientons vers une combinaison des principes de l'OLAP, de la fouille de données et de la recherche d'information. Afin d'introduire une analyse explicative dans l'OLAP, nous faisons une recherche guidée de règles d'association dans le cube. Cela nous conduit à modifier la définition du support et de la confiance d'une règle. Les arbres de régression nous permettent de proposer à l'utilisateur de faire de la prédiction dans le cube et d'avoir ainsi une démarche de type What If Analysis. Pour l'analyse des données complexes, deux méthodes factorielles (AFC et ACM) rendent possible la visualisation des faits dans un cube et la détection de régions intéressantes en réorganisant les dimensions du cube. Nous proposons également une agrégation sémantique des faits et une nouvelle hiérarchie de dimension construite automatiquement grâce aux principes d'une méthode de classification (CAH). Nos propositions sont une première démonstration de la faisabilité de combiner l'OLAP à d'autres techniques comme la fouille de données et la recherche d'information pour faire significativement évoluer l'analyse en ligne et s'adapter aux données complexes. L'OLAP a commencé à s'adapter à leur structure et à leur spécificité (XOLAP - XML OLAP, SOLAP - spatial OLAP). Mais il faut aller au delà et nous pensons qu'un des défis est d'extraire et d'analyser (en ligne) la sémantique contenue dans les données complexes. Ce point constitue un véritable verrou scientifique mais qui est que partiellement abordé par la communauté scientifique. Il faudrait également identifier tous les problèmes posés par les données complexes et ce quels que soient leur nature, contexte ou spécificités. Nous voulons poursuivre nos travaux dans cette voie et faire évoluer l'OLAP vers une nouvelle génération d'analyse en ligne : l'OLAP sémantique. Les problèmes majeurs à traiter seront comment : (1) modéliser toutes les formes de données complexes, leur sémantique et leurs liens ; (2) analyser en ligne les données complexes ; (3) Intégrer les connaissances de l'utilisateur dans le processus de l'analyse ?

La génomique comparée est essentiellement une forme de fouille de données dans des grandes collections de relations <em>n</em>-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 recherche de structures arborescentes fréquentes, également appelée fouille d'arbres, au sein de bases de données composées de documents semi-structurés (e.g. XML) est une problématique actuellement très active. Ce processus trouve de nombreux intérêts dans le contexte de la fouille de données comme par exemple la construction automatique d'un schéma médiateur à partir de schémas XML, ou bien l'analyse des structures des sites Web afin d'étudier son usage ou modifier son contenu.<br /><br />L'objectif de cette thèse est de proposer une méthode d'extraction d'arborescences fréquentes. Cette approche est basée sur une représentation compacte des arborescences cherchant à diminuer la consommation de mémoire dans le processus de fouille. En particulier, nous présentons une nouvelle technique de génération d'arborescences candidates visant à réduire leur nombre. Par ailleurs, nous proposons différents algorithmes pour valider le support des arborescences candidates dans une base de données selon divers types de contraintes d'inclusion d'arbres : induite, incrustée et floue. Finalement nous appliquons nos algorithmes à des jeux de données synthétiques et réels et nous présentons les résultats obtenus.

Les entrepôts de données forment le socle des systèmes décisionnels. Ils permettent d'intégrer les données de production d'une entreprise ou d'un organisme et sont le support de l'analyse multidimensionnelle en ligne (OLAP) ou de la fouille de données. Avec l'exploitation de plus en plus courante de données complexes dans le cadre des processus décisionnels, de nouvelles approches d'entreposage, qui exploitent notamment le langage XML, sont développées. Dans ce contexte, le problème de la performance des entrepôts de données demeure plus que jamais un enjeu crucial.<br /><br />Le travail présenté dans ce mémoire vise à proposer des solutions innovantes au niveau de l'optimisation et de l'évaluation des performances des entrepôts de données. Nous avons en effet conçu une approche générique dont l'objectif est de proposer automatiquement à l'administrateur d'un entrepôt des solutions permettant d'optimiser les temps d'accès aux données. Le principe de cette approche est d'appliquer des techniques de fouille de données sur une charge (ensemble de requêtes) représentative de l'utilisation de l'entrepôt de données afin de déduire une configuration quasi-optimale d'index et/ou de vues matérialisées. Des modèles de coût permettent ensuite de sélectionner parmi ces structures de données les plus efficaces en terme de rapport gain de performance/surcharge.<br /><br />Par ailleurs, l'évaluation de performance peut venir en appui de la conception des entrepôts de données. Ainsi, afin de valider notre approche de manière expérimentale, nous avons également conçu plusieurs bancs d'essais génériques. Le principe directeur qui a présidé à leur élaboration est l'adaptabilité. En effet, pour comparer l'efficacité de différentes techniques d'optimisation des performances, il est nécessaire de les tester dans différents environnements, sur différentes configurations de bases de données et de charges, etc. La possibilité d'évaluer l'impact de différents choix d'architecture est aussi une aide appréciable dans la conception des entrepôts de données. Nos bancs d'essais permettent donc de générer diverses configurations d'entrepôts de données, ainsi que des charges décisionnelles qui s'y appliquent.<br /><br />Finalement, nos solutions d'optimisation et d'évaluation des performances ont été mises en oeuvre dans les contextes des entrepôts de données relationnels et XML.

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

La gestion des processus-métiers, des architectures orientées-services et leur rétro-ingénierie s'appuie fortement sur l'extraction des protocoles-métier des services Web et des modèles des processus-métiers à partir de fichiers de journaux. La fouille et l'extraction de ces modèles visent la (re)découverte du comportement d'un modèle mis en œuvre lors de son exécution en utilisant uniquement les traces d'activité, ne faisant usage d'aucune information a priori sur le modèle cible. Notre étude préliminaire montre que : (i) une minorité de données sur l'interaction sont enregistrées par le processus et les architectures de services, (ii) un nombre limité de méthodes d'extraction découvrent ce modèle sans connaître ni les instances positives du protocole, ni l'information pour les déduire, et (iii) les approches actuelles se basent sur des hypothèses restrictives que seule une fraction des services Web issus du monde réel satisfont. Rendre possible l'extraction de ces modèles d'interaction des journaux d'activité, en se basant sur des hypothèses réalistes nécessite: (i) des approches qui font abstraction du contexte de l'entreprise afin de permettre une utilisation élargie et générique, et (ii) des outils pour évaluer le résultat de la fouille à travers la mise en œuvre du cycle de vie des modèles découverts de services. En outre, puisque les journaux d'interaction sont souvent incomplets, comportent des erreurs et de l'information incertaine, alors les approches d'extraction proposées dans cette thèse doivent être capables de traiter ces imperfections correctement. Nous proposons un ensemble de modèles mathématiques qui englobent les différents aspects de la fouille des protocoles-métiers. Les approches d'extraction que nous présentons, issues de l'algèbre linéaire, nous permettent d'extraire le protocole-métier tout en fusionnant les étapes classiques de la fouille des processus-métiers. D'autre part, notre représentation du protocole basée sur des séries temporelles des variations de densité de flux permet de récupérer l'ordre temporel de l'exécution des événements et des messages dans un processus. En outre, nous proposons la définition des expirations propres pour identifier les transitions temporisées, et fournissons une méthode pour les extraire en dépit de leur propriété d'être invisible dans les journaux. Finalement, nous présentons un cadre multitâche visant à soutenir toutes les étapes du cycle de vie des workflow de processus et des protocoles, allant de la conception à l'optimisation. Les approches présentées dans ce manuscrit ont été implantées dans des outils de prototypage, et validées expérimentalement sur des ensembles de données et des modèles de processus et de services Web. Le protocole-métier découvert, peut ensuite être utilisé pour effectuer une multitude de tâches dans une organisation ou une entreprise.