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.

Entre les villes et les réseaux de transport s'établissent des relations particulièrement complexes, qui mélangent les niveaux d'échelle et croisent des temporalités multiples. Remontant aussi loin que le permettent les données, abordant des pays aux histoires contrastées, nous évoquons deux grands types d'articulations : d'une part, l'évolution des réseaux de transport permet un changement de dimension des villes et des systèmes de villes ; d'autre part, elle se traduit par une différenciation croissante des positions relatives des noeuds. Dans une première partie, nous analysons les transformations des contours et des dimensions des villes rendues possibles par l'évolution des transports urbains depuis la révolution industrielle, en témoignant des débats passionnants qui agitent les contemporains depuis deux siècles et les solutions envisagées et parfois adoptées par des organismes officiels pour suivre ces évolutions. Nous montrons que l'hétérogénéité très grande des définitions nationales de la ville en Europe prend sa source à la fin du 19ème siècle, lorsque certains pays font le choix des critères morpho-statistiques alors que d'autres gardent des approches juridiques et administratives. Dans une deuxième partie, nous nous appuyons sur une ontologie de la ville dans le temps long pour proposer des constructions de bases de données urbaines harmonisées pour la comparaison dynamique et internationale. Nos méthodes sont notamment fondées sur une modélisation de l'emprise spatiale des villes selon un rayon théorique correspondant, à chaque époque, au budget-temps moyen des navetteurs. Les résultats obtenus pour la France et les Etats-Unis révèlent l'impact du choix des délimitations sur les mesures du poids ou de la croissance des villes, et nous proposons des pistes pour construire des bases de données harmonisées pour les villes d'Europe. Dans la dernière partie, nous montrons que les grandes phases de transformation des systèmes de villes coïncident avec des innovations technologiques majeures dans les transports, même si des facteurs politiques et sociaux interviennent aussi (l'appréhension de territoires « nationaux », la perception d'un espace de plus en plus relativisé par la vitesse de déplacement). Dans les effets de dimensionnement des territoires par les réseaux rapides, nous soulignons l'importance d'un échelon régional, permettant, par des actions d'aménagement de grande ampleur, une structuration en réseau des zones centrales de l'économie-monde. Par des mesures d'accessibilité et de forme des réseaux, nous mettons en évidence des processus historiques d'adaptation mutuelle puis de co-évolution entre réseaux de transport et trame urbaine. Dans la phase de co-évolution, nous observons une différenciation croissante des positions relatives des lieux qui explique pour partie le processus de hiérarchisation des tailles de villes observable tant en Europe qu'aux Etats-Unis.

Les peptides non-ribosomiaux sont des molécules produites par les micro-organismes et présentant un large éventail d'activités biologiques et pharmaceutiques. Par exemple, ils peuvent présenter des activités antibiotiques, immuno-modulatrices ou anti-tumorales. Ces peptides sont synthétisés par de grands complexes multi-enzymatiques, appelés synthétases ou NRPS (NonRibosomal Peptide Synthetases). Deux traits caractéristiques distinguent ces peptides des peptides ribosomiaux classiques : le premier est que leur structure primaire n'est pas toujours linéaire mais peut être totalement ou partiellement cyclique, branchée voir même poly-cyclique, et le second est la diversité des monomères incorporés au sein de ces peptides qui dépasse largement les vingt acides aminés protéogéniques. Nous avons développé Norine, la première ressource publique entièement dédiée aux peptides nonribosomiaux. Norine contient actuellement plus de 1 000 peptides, modélisés par des graphes étiquetés non-orientés, ainsi que des outils informatiques permettant leur analyse, comme la comparaison de compositions en monomères, la recherche de motifs structuraux ou la recherche par similarité. Des analyses statistiques sur les données contenues dans Norine ont permis de mettre en évidence des caractéristiques biologiques intéressantes comme la spécificité des monomères en fonction de l'activité biologique qui nous a conduit à l'élaboration d'un outil d'aide à la prédiction de la fonction biologique d'un peptide à partir de sa composition monomérique. En trois ans, Norine est devenue la ressource internationale pour les peptides non-ribosomiaux.

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.

Cette thèse s'inscrit dans le cadre de réflexions sur la réhabilitation des structures urbaines des stations touristiques françaises de montagne, visant à une meilleure adéquation entre les pratiques actuelles des individus et l'organisation de l'espace environnant existant. Au sein de cette thématique apparaît le besoin d'élaborer un outil d'aide à la réflexion capable d'évaluer les fonctionnements des espaces des stations touristiques de montagne. A partir de ce constat, ce travail cherche à articuler une réflexion sur les pratiques de populations de stations touristiques de montagne avec une analyse de l'utilisation du temps et de l'espace par les individus (emplois du temps et de l'espace). L'approche méthodologique et théorique est fondée sur les principes et concepts de la « Time-Geography » développé par Torsten Hägerstrand (université de Lund). Les fondements de la « Time-Geography » sont développés et commentés à travers les travaux de l'école de géographie de Lund. Sont ensuite définis les objectifs d'une méthodologie cherchant à rendre compte de l'image globale des actions individuelles et collectives et de comprendre les mécanismes qui régulent, au quotidien, les processus mis en œuvre dans l'élaboration de la chaîne des activités que les individus réalisent dans l'espace et dans le temps. A titre d'exemple, une enquête est réalisée auprès des touristes, d'habitants permanents et de travailleurs saisonniers dans la station de Valloire (Savoie). Les emplois du temps et de l'espace de chaque individu interrogé sont analysés de façon exploratoire grâce à deux approches : un traitement statistique résume l'information en cherchant des homogénéités dans les emplois du temps et de l'espace ; l'utilisation d'une base de données temporelles gérant des historiques enrichit les conclusions du traitement statistique en mettant en évidence des formes de structures d'organisation des emplois du temps et de l'espace.

Les bases actuelles de données multimédia nécessitent des outils de plus en plus avancés pour pouvoir être parcourues avec efficacité. Dans ce contexte, la recherche en interaction avec un utilisateur est une approche qui permet de résoudre des requêtes à la sémantique complexe avec rapidité, sans pour autant nécessiter un haut niveau d'expertise utilisateur. Parmi les différents éléments intervenant dans la conception d'un système de recherche interactive, deux parties essentielles interviennent: l'indexation et la similarité entre les documents multimédia, et la gestion du processus interactif. Dans le contexte de la recherche multimédia par le contenu, on s'appuie sur des descriptions visuelles extraites automatiquement des documents. Suite à cette étape initiale, il est nécessaire de produire des structures de données, appelées index, ainsi qu'une métrique capable de comparer ces structures. Pour ce faire, nous proposons de représenter un document sous la forme d'un graphe, où chaque sommet du graphe représente une partie du document (région, point d'intérêt, ...) et chaque arête du graphe représente une relation entre deux parties du document. Puis, nous introduisons des métriques associées, sous la forme de fonctions noyaux sur graphes, qui permettent d'utiliser ces représentations complexes avec les méthodes d'apprentissages Hilbertiennes, telle que les SVMs. La gestion du processus interactif entre le système et un utilisateur a fait d'important progrès grâce à l'approche dite par apprentissage actif. Les premières approches proposent des critères pertinents pour la sélection de document à faire annoter par l'utilisateur, dans le but de trouver les documents recherchés au plus vite. Dans ce contexte, nous proposons d'aller plus loin en nous intéressant à la fabrication "en ligne" d'index et métriques associées en fonction de la nature de la recherche. En d'autres termes, nous proposons de remplacer le schéma traditionnel, où un unique index général est utilisé, par un schéma d'indexation active, où chaque utilisateur dispose d'un index dédié à sa requête.

Cette thèse est composée de deux contributions à l'étude des bases de données : (i) la première contribution porte sur l'amélioration de la compréhension, par l'étude formelle, de la tension entre les fonctionnalités de cohérence et de confidentialité. Cette tension permet, dans certaines situations, d'utiliser les contraintes d'intégrité (cohérence) pour révéler des secrets (confidentialité) et donc réaliser des fraudes. L'étude fixe tout d'abord un cadre général de recherche en donnant une définition formelle des notions de secret, révélation et fraude. Puis, une occurrence particulière, et originale, de tension est formalisée selon une méthode inspirée des méthodes de programmation. Cette occurrence s'est avérée liée aux treillis de Galois. (ii) la deuxième contribution porte sur la spécification et l'implémentation d'une fonctionalité originale : le classement d'objets selon leur histoire. A cette fin, l'étude répond successivement aux trois questions : qu'est-ce que l'histoire d'un objet, comment exprimer des propriétés sur l'histoire des objets, et comment les vérifier efficacement ? L'expression est réalisée par des formules de logique temporelle et la méthode de vérification repose sur la traduction de ces formules en expressions régulières puis en automates d'états finis. L'implémentation réalisée utilise cette méthode de classement pour classer a posteriori des objets du langage prototypique NewtonScript.

La fouille de données et la Programmation Par Contraintes (PPC) sont deux domaines de l'informatique qui ont eu, jusqu'à très récemment, des destins séparés. Cette thèse est l'une des toutes premières à s'intéresser aux liens entre la fouille de données et la PPC, et notamment aux apports de cette dernière à l'extraction de motifs sous contraintes. Différentes méthodes génériques pour la découverte de motifs locaux ont été proposées. Mais, ces méthodes ne prennent pas en considération le fait que l'intérêt d'un motif dépend souvent d'autres motifs. Un tel motif est appelé motif n-aire. Très peu de travaux concernant l'extraction de motifs n-aires ont été menés et les méthodes développées sont toutes ad hoc. Cette thèse propose un cadre unifié pour modéliser et résoudre les contraintes n-aires en fouille de données. Tout d'abord, l'extraction de motifs n-aires est modélisée sous forme de problème de satisfaction de contraintes (CSP). Puis, un langage de requêtes à base de contraintes de haut niveau est proposé. Ce langage permet d'exprimer une large panoplie de contraintes n-aires. Plusieurs méthodes de résolution sont développées et comparées. Les apports principaux de ce cadre sont sa déclarativité et sa généricité. Il s'agit du premier cadre générique et flexible permettant la modélisation et la résolution de contraintes n-aires en fouille de données.

Ce mémoire décrit mes activités de recherche et d'animation de recherche depuis ma thèse, soutenue en 2002. Les travaux décrits ici ont été principalement menés au LIRMM (Université Montpellier 2, CNRS UMR 5506), au sein de l'équipe TATOO. Dans ce contexte, je me suis attachée à concilier des visions trop souvent vues comme divergentes au sein des communautés liées à la fouille de données complexes : gérer l'approximation (à la fois dans les données et dans les résultats produits), la fouille de données et les bases de données complexes et volumineuses, notamment les entrepôts de données. Plus précisément, mes travaux visent à montrer qu'il est possible de relever le défi jusqu'à présent non totalement solutionné d'extraire des connaissances exploitables par les experts non informaticiens à partir d'entrepôts de données, en prenant en compte au mieux les particularités de ce domaine. En particulier, j'ai porté d'une part une grande attention à exploiter la dimension temporelle des entrepôts et d'autre part à montrer autant que faire se peut que flou et passage à l'échelle ne sont pas des notions antagonistes. Dans cet objectif, j'ai mené, dirigé, encadré et valorisé à travers des collaborations scientifiques et industrielles des travaux dont je rapporte ici une synthèse.

Au cours des dernières années, le volume des données qui sont capturées et générées a explosé. Les progrès des technologies informatiques, qui fournissent du stockage à bas prix et une très forte puissance de calcul, ont permis aux organisations d'exécuter des analyses complexes de leurs données et d'en extraire des connaissances précieuses. Cette tendance a été très importante non seulement pour l'industrie, mais a également pour la science, où les meilleures instruments et les simulations les plus complexes ont besoin d'une gestion efficace des quantités énormes de données. Le parallélisme est une technique fondamentale dans la gestion de données extrêmement volumineuses car il tire parti de l'utilisation simultanée de plusieurs ressources informatiques. Pour profiter du calcul parallèle, nous avons besoin de techniques de partitionnement de données efficaces, qui sont en charge de la division de l'ensemble des données en plusieurs partitions et leur attribution aux nœuds de calculs. Le partitionnement de données est un problème complexe, car il doit prendre en compte des questions différentes et souvent contradictoires telles que la localité des données, la répartition de charge et la maximisation du parallélisme. Dans cette thèse, nous étudions le problème de partitionnement de données, en particulier dans les bases de données parallèles scientifiques qui sont continuellement en croissance. Nous étudions également ces partitionnements dans le cadre MapReduce. Dans le premier cas, nous considérons le partitionnement de très grandes bases de données dans lesquelles des nouveaux éléments sont ajoutés en permanence, avec pour exemple une application aux données astronomiques. Les approches existantes sont limitées à cause de la complexité de la charge de travail et l'ajout en continu de nouvelles données limitent l'utilisation d'approches traditionnelles. Nous proposons deux algorithmes de partitionnement dynamique qui attribuent les nouvelles données aux partitions en utilisant une technique basée sur l'affinité. Nos algorithmes permettent d'obtenir de très bons partitionnements des données en un temps d'exécution réduit comparé aux approches traditionnelles. Nous étudions également comment améliorer la performance du framework MapReduce en utilisant des techniques de partitionnement de données. En particulier, nous sommes intéressés par le partitionnement efficient de données d'entrée avec l'objectif de réduire la quantité de données qui devront être transférées dans la phase intermédiaire, connu aussi comme " shuffle ". Nous concevons et mettons en œuvre une stratégie qui, en capturant les relations entre les tuples d'entrée et les clés intermédiaires, obtient un partitionnement efficace qui peut être utilisé pour réduire de manière significative le surcharge de communications dans MapReduce.