Les documents numériques sont aujourd'hui des données complexes qui intègrent d'une manière hétérogène des informations textuelles, structurelles, multimédia ainsi que des méta-données. Le langage de balisage générique XML s'est progressivement imposé comme support privilégié non seulement pour l'échange des données mais aussi pour leur stockage. La gestion des documents stockés sous les formats XML nécessite le développement de méthodes et d'outils spécifiques pour l'indexation, la recherche, le filtrage et la fouille des données. En particulier, les fonctions de recherche et de filtrage doivent prendre en compte des requêtes disposant de connaissances incomplètes, imprécises, parfois même erronées sur la structure ou le contenu des documents XML. Ces fonctions doivent par ailleurs maintenir une complexité algorithmique compatible avec la complexité des données et surtout avec leur volume toujours en forte croissance, ceci pour assurer le passage à l'échelle des solutions informatiques. Dans cette thèse, nous étudions des méthodes et développons des outils pour indexer et rechercher des informations multimédia hétérogènes stockées dans des banques de documents XML. Plus précisément, nous abordons la question de la recherche par similarité sur des données composites décrites par des éléments structurels, textuels et séquentiels. En s'appuyant sur la partie structurelle des documents XML, nous avons défini un modèle de représentation, d'indexation et d'interrogation flexible pour des types hétérogènes de données séquentielles. Les principes que nous développons mettent en oeuvre des mécanismes de recherche qui exploitent simultanément les éléments des structures documentaires indexées et les contenus documentaires non structurés. Nous évaluons également l'impact sur la pertinence des résultats retournés par l'introduction de mécanismes d'alignement approximatif des éléments structurels. Nous proposons des algorithmes capables de détecter et de suggérer les « meilleurs points d'entrée » pour accéder directement à l'information recherchée dans un document XML. Finalement, nous étudions l'exploitation d'une architecture matérielle dédiée pour accélérer les traitements les plus coûteux du point de vue de la complexité de notre application de recherche d'information structurée. v

Des travaux récents ont montré l’intérêt de la programmation par contraintes pour la fouille de données. Dans cette thèse, nous nous intéressons à la recherche de motifs sur séquences, et en particulier à la caractérisation, à l’aide de motifs, de classes de séquences pré-établies. Nous proposons à cet effet un langage de modélisation à base de contraintes qui suppose une représentation matricielle du jeu de séquences. Un motif s’y définit comme un ensemble de caractères (ou de patrons) et pour chacun une localisation dans différentes séquences. Diverses contraintes peuvent alors s’appliquer : validité des localisations, couverture d’une classe de séquences, ordre sur les localisations des caractères commun aux séquences, etc. Nous formulons deux problèmes de caractérisation NP-complets : la caractérisation par motif totalement ordonné (e.g. sous-séquence exclusive à une classe) ou partiellement ordonné. Nous en donnons deux modélisations CSP qui intègrent des contraintes globales pour la preuve d’exclusivité. Nous introduisons ensuite un algorithme mémétique pour l’extraction de motifs partiellement ordonnés qui s’appuie sur la résolution CSP lors des phases d’initialisation et d’intensification. Cette approche hybride se révèle plus performante que l’approche CSP pure sur des séquences biologiques. La mise en forme matricielle de jeux de séquences basée sur une localisation des caractères peut être de taille rédhibitoire. Nous proposons donc de localiser des patrons plutôt que des caractères. Nous présentons deux méthodes ad-hoc, l’une basée sur un parcours de treillis et l’autre sur la programmation dynamique. / Recent works have shown the relevance of constraint programming to tackle data mining tasks. This thesis follows this approach and addresses motif discovery in sequential data. We focus in particular, in the case of classified sequences, on the search for motifs that best fit each individual class. We propose a language of constraints over matrix domains to model such problems. The language assumes a preprocessing of the data set (e.g., by pre-computing the locations of each character in each sequence) and views a motif as the choice of a sub-matrix (i.e., characters, sequences, and locations). We introduce different matrix constraints (compatibility of locations with the database, class covering, location-based character ordering common to sequences, etc.) and address two NP-complete problems: the search for class-specific totally ordered motifs (e.g., exclusive subsequences) or partially ordered motifs. We provide two CSP models that rely on global constraints to prove exclusivity. We then present a memetic algorithm that uses this CSP model during initialisation and intensification. This hybrid approach proves competitive compared to the pure CSP approach as shown by experiments carried out on protein sequences. Lastly, we investigate data set preprocessing based on patterns rather than characters, in order to reduce the size of the resulting matrix domain. To this end, we present and compare two alternative methods, one based on lattice search, the other on dynamic programming.

L'exploration des bases de données temporelles à l'aide de méthodes de fouille de données adaptées a fait l'objet de nombreux travaux de recherche. Cependant le volume d'informations extraites est souvent important et la tâche d'analyse reste alors difficile. Dans cette thèse, nous présentons des méthodes pour synthétiser et filtrer l'information extraite. L'objectif est de restituer des résultats qui soient interprétables. Pour cela, nous avons exploité la notion de séquence partiellement ordonnée et nous proposons (1) un algorithme qui extrait l'ensemble des motifs partiellement ordonnés clos; (2) un post-traitement pour filtrer un ensemble de motifs d'intérêt et(3) une approche qui extrait un consensus comme alternative à l'extraction de motifs. Les méthodes proposées ont été testées sur des données hydrobiologiques issues du projet ANR Fresqueau et elles ont été implantées dans un logiciel de visualisation destiné aux hydrobiologistes pour l'analyse de la qualité des cours d'eau. / Exploring temporal databases with suitable data mining methods have been the subject of several studies. However, it often leads to an excessive volume of extracted information and the analysis is difficult for the user. We addressed this issue and we specically focused on methods that synthesize and filter extracted information. The objective is to provide interpretable results for humans. Thus, we relied on the notion of partially ordered sequence and we proposed (1) an algorithm that extracts the set of closed partially ordered patterns ; (2) a post-processing to filter some interesting patterns for the user and (3) an approach that extracts a partially ordered consensus as an alternative to pattern extraction. The proposed methods were applied for validation on hydrobiological data from the Fresqueau ANR project. In addition, they have been implemented in a visualization tool designed for hydrobiologists for water course quality analysis.

Dans le cadre de cette thèse, nous avons établi des liens entre les modèles obtenus par des algorithmes d'inférence grammaticale et la connaissance induite par des techniques de fouille de données séquentielles. Partant du constat que le point commun entre ces deux contextes différents de travail est la manipulation de données structurées sous forme de séquences de symboles, nous avons tenté d'exploiter les propriétés des automates probabilistes inférés à partir de ces séquences au profit d'une fouille de données séquentielles plus efficace. <br />Dans ce contexte, nous avons montré que l'exploitation brute, non seulement des séquences d'origine mais aussi des automates probabilistes inférés à partir de celles-ci, ne garantit pas forcément une extraction de connaissance pertinente. Nous avons apporté dans cette thèse plusieurs contributions, sous la forme de bornes minimales et de contraintes statistiques, permettant ainsi d'assurer une exploitation fructueuse des séquences et des automates probabilistes. De plus, grâce à notre modèle nous apportons une solution efficace à certaines applications mettant en jeux des problèmes de préservation de vie privée des individus.

Les travaux présentés dans ce mémoire gravitent autour du document numérique : Extraction de connaissances, utilisation de connaissances et évaluation des connaissances extraites, d'un point de vue théorique aussi bien qu'expérimental. Le fil directeur de mes travaux de recherche est la généricité des méthodes produites, avec une attention particulière apportée à la question du passage à l'échelle. Ceci implique que les algorithmes, principalement appliqués au texte dans ce mémoire, fonctionnent en réalité pour tout type de donnée séquentielle. Sur le matériau textuel, la généricité et la robustesse algorithmique des méthodes permettent d'obtenir des approches endogènes, fonctionnant pour toute langue, pour tout genre et pour tout type de document (et de collection de documents). Le matériau expérimental couvre ainsi des langues utilisant différents alphabets, et des langues appartenant à différentes familles linguistiques. Les traitements peuvent d'ailleurs être appliqués de la même manière au grain phrase, mot, ou même caractère. Les collections traitées vont des dépêches d'agence de presse aux ouvrages numérisés, en passant par les articles scientifiques. Ce mémoire présente mes travaux en fonction des différentes étapes du pipeline de traitement des documents, de leur appréhension à l'évaluation applicative. Le document est ainsi organisé en trois parties décrivant des contributions en : extraction de connaissances (fouille de données séquentielle et veille multilingue) ; exploitation des connaissances acquises, par des applications en recherche d'information, classification et détection de synonymes via un algorithme efficace d'alignement de paraphrases ; méthodologie d'évaluation des systèmes d'information dans un contexte de données massives, notamment l'évaluation des performances des systèmes de recherche d'information sur des bibliothèques numérisées.

De nos jours, beaucoup de données peuvent être facilement accessibles. Mais toutes ces données ne sont pas utiles si nous ne savons pas les traiter efficacement et si nous ne savons pas extraire facilement les informations pertinentes à partir d'une grande quantité de données. Les techniques de détection d'anomalies sont utilisées par de nombreux domaines afin de traiter automatiquement les données. Les techniques de détection d'anomalies dépendent du domaine d'application, des données utilisées ainsi que du type d'anomalie à détecter.Pour cette étude nous nous intéressons seulement aux données séquentielles. Une séquence est une liste ordonnée d'objets. Pour de nombreux domaines, il est important de pouvoir identifier les irrégularités contenues dans des données séquentielles comme par exemple les séquences ADN, les commandes d'utilisateur, les transactions bancaires etc.Cette thèse présente une nouvelle approche qui identifie et analyse les irrégularités de données séquentielles. Cette technique de détection d'anomalies peut détecter les anomalies de données séquentielles dont l'ordre des objets dans les séquences est important ainsi que la position des objets dans les séquences. Les séquences sont définies comme anormales si une séquence est presque identique à une séquence qui est fréquente (normale). Les séquences anormales sont donc les séquences qui diffèrent légèrement des séquences qui sont fréquentes dans la base de données.Dans cette thèse nous avons appliqué cette technique à la surveillance maritime, mais cette technique peut être utilisée pour tous les domaines utilisant des données séquentielles. Pour notre application, la surveillance maritime, nous avons utilisé cette technique afin d'identifier les conteneurs suspects. En effet, de nos jours 90% du commerce mondial est transporté par conteneurs maritimes mais seulement 1 à 2% des conteneurs peuvent être physiquement contrôlés. Ce faible pourcentage est dû à un coût financier très élevé et au besoin trop important de ressources humaines pour le contrôle physique des conteneurs. De plus, le nombre de conteneurs voyageant par jours dans le monde ne cesse d'augmenter, il est donc nécessaire de développer des outils automatiques afin d'orienter le contrôle fait par les douanes afin d'éviter les activités illégales comme les fraudes, les quotas, les produits illégaux, ainsi que les trafics d'armes et de drogues. Pour identifier les conteneurs suspects nous comparons les trajets des conteneurs de notre base de données avec les trajets des conteneurs dits normaux. Les trajets normaux sont les trajets qui sont fréquents dans notre base de données.Notre technique est divisée en deux parties. La première partie consiste à détecter les séquences qui sont fréquentes dans la base de données. La seconde partie identifie les séquences de la base de données qui diffèrent légèrement des séquences qui sont fréquentes. Afin de définir une séquence comme normale ou anormale, nous calculons une distance entre une séquence qui est fréquente et une séquence aléatoire de la base de données. La distance est calculée avec une méthode qui utilise les différences qualitative et quantitative entre deux séquences. / Nowadays, huge quantities of data can be easily accessible, but all these data are not useful if we do not know how to process them efficiently and how to extract easily relevant information from a large quantity of data. The anomaly detection techniques are used in many domains in order to help to process the data in an automated way. The anomaly detection techniques depend on the application domain, on the type of data, and on the type of anomaly.For this study we are interested only in sequential data. A sequence is an ordered list of items, also called events. Identifying irregularities in sequential data is essential for many application domains like DNA sequences, system calls, user commands, banking transactions etc.This thesis presents a new approach for identifying and analyzing irregularities in sequential data. This anomaly detection technique can detect anomalies in sequential data where the order of the items in the sequences is important. Moreover, our technique does not consider only the order of the events, but also the position of the events within the sequences. The sequences are spotted as anomalous if a sequence is quasi-identical to a usual behavior which means if the sequence is slightly different from a frequent (common) sequence. The differences between two sequences are based on the order of the events and their position in the sequence.In this thesis we applied this technique to the maritime surveillance, but this technique can be used by any other domains that use sequential data. For the maritime surveillance, some automated tools are needed in order to facilitate the targeting of suspicious containers that is performed by the customs. Indeed, nowadays 90% of the world trade is transported by containers and only 1-2% of the containers can be physically checked because of the high financial cost and the high human resources needed to control a container. As the number of containers travelling every day all around the world is really important, it is necessary to control the containers in order to avoid illegal activities like fraud, quota-related, illegal products, hidden activities, drug smuggling or arm smuggling. For the maritime domain, we can use this technique to identify suspicious containers by comparing the container trips from the data set with itineraries that are known to be normal (common). A container trip, also called itinerary, is an ordered list of actions that are done on containers at specific geographical positions. The different actions are: loading, transshipment, and discharging. For each action that is done on a container, we know the container ID and its geographical position (port ID).This technique is divided into two parts. The first part is to detect the common (most frequent) sequences of the data set. The second part is to identify those sequences that are slightly different from the common sequences using a distance-based method in order to classify a given sequence as normal or suspicious. The distance is calculated using a method that combines quantitative and qualitative differences between two sequences.

Notre thèse se situe dans le domaine interdisciplinaire de la stylistique computationnelle, à savoir l'application des méthodes statistiques et computationnelles à l'étude du style littéraire. Historiquement, la plupart des travaux effectués en stylistique computationnelle se sont concentrés sur les aspects lexicaux. Dans notre thèse, l’accent est mis sur l'aspect syntaxique du style qui est beaucoup plus difficile à analyser étant donné sa nature abstraite. Comme contribution principale, dans cette thèse, nous travaillons sur une approche à l'étude stylistique computationnelle de textes classiques de littérature française d'un point de vue herméneutique, où découvrir des traits linguistiques intéressants se fait sans aucune connaissance préalable. Plus concrètement, nous nous concentrons sur le développement et l'extraction des motifs morphosyntaxiques. Suivant la ligne de pensée herméneutique, nous proposons un processus de découverte de connaissances pour la caractérisation stylistique accentué sur la dimension syntaxique du style et permettant d'extraire des motifs pertinents à partir d'un texte donné. Ce processus proposé consiste en deux étapes principales, une étape d'extraction de motifs séquentiels suivi de l'application de certaines mesures d'intérêt. En particulier, l'extraction de tous les motifs syntaxiques possibles d'une longueur donnée est proposée comme un moyen particulièrement utile pour extraire des caractéristiques intéressantes dans un scénario exploratoire. Nous proposons, évaluons et présentons des résultats sur les trois mesures d'intérêt proposées, basée chacune sur un raisonnement théorique linguistique et statistique différent. / The present thesis locates itself in the interdisciplinary field of computational stylistics, namely the application of statistical and computational methods to the study of literary style. Historically, most of the work done in computational stylistics has been focused on lexical aspects especially in the early decades of the discipline. However, in this thesis, our focus is put on the syntactic aspect of style which is quite much harder to capture and to analyze given its abstract nature. As main contribution, we work on an approach to the computational stylistic study of classic French literary texts based on a hermeneutic point of view, in which discovering interesting linguistic patterns is done without any prior knowledge. More concretely, we focus on the development and the extraction of complex yet computationally feasible stylistic features that are linguistically motivated, namely morpho-syntactic patterns. Following the hermeneutic line of thought, we propose a knowledge discovery process for the stylistic characterization with an emphasis on the syntactic dimension of style by extracting relevant patterns from a given text. This knowledge discovery process consists of two main steps, a sequential pattern mining step followed by the application of some interestingness measures. In particular, the extraction of all possible syntactic patterns of a given length is proposed as a particularly useful way to extract interesting features in an exploratory scenario. We propose, carry out an experimental evaluation and report results on three proposed interestingness measures, each of which is based on a different theoretical linguistic and statistical backgrounds.

Cette thèse s’inscrit dans le contexte de la reconnaissance des activités à partir de séquences vidéo qui est une des préoccupations majeures dans le domaine de la vision par ordinateur. Les domaines d'application pour ces systèmes de vision sont nombreux notamment la vidéo surveillance, la recherche et l'indexation automatique de vidéos ou encore l'assistance aux personnes âgées. Cette tâche reste problématique étant donnée les grandes variations dans la manière de réaliser les activités, l'apparence de la personne et les variations des conditions d'acquisition des activités. L'objectif principal de ce travail de thèse est de proposer une méthode de reconnaissance efficace par rapport aux différents facteurs de variabilité. Les représentations basées sur les points d'intérêt ont montré leur efficacité dans les travaux d'art; elles ont été généralement couplées avec des méthodes de classification globales vue que ses primitives sont temporellement et spatialement désordonnées. Les travaux les plus récents atteignent des performances élevées en modélisant le contexte spatio-temporel des points d'intérêts par exemple certains travaux encodent le voisinage des points d'intérêt à plusieurs échelles. Nous proposons une méthode de reconnaissance des activités qui modélise explicitement l'aspect séquentiel des activités tout en exploitant la robustesse des points d'intérêts dans les conditions réelles. Nous commençons par l'extractivité des points d'intérêt dont a montré leur robustesse par rapport à l'identité de la personne par une étude tensorielle. Ces primitives sont ensuite représentées en tant qu'une séquence de sac de mots (BOW) locaux: la séquence vidéo est segmentée temporellement en utilisant la technique de fenêtre glissante et chacun des segments ainsi obtenu est représenté par BOW des points d'intérêt lui appartenant. Le premier niveau de notre système de classification séquentiel hybride consiste à appliquer les séparateurs à vaste marge (SVM) en tant que classifieur de bas niveau afin de convertir les BOWs locaux en des vecteurs de probabilités des classes d'activité. Les séquences de vecteurs de probabilité ainsi obtenues sot utilisées comme l'entrées de classifieur séquentiel conditionnel champ aléatoire caché (HCRF). Ce dernier permet de classifier d'une manière discriminante les séries temporelles tout en modélisant leurs structures internes via les états cachés. Nous avons évalué notre approche sur des bases publiques ayant des caractéristiques diverses. Les résultats atteints semblent être intéressant par rapport à celles des travaux de l'état de l'art. De plus, nous avons montré que l'utilisation de classifieur de bas niveau permet d'améliorer la performance de système de reconnaissance vue que le classifieur séquentiel HCRF traite directement des informations sémantiques des BOWs locaux, à savoir la probabilité de chacune des activités relativement au segment en question. De plus, les vecteurs de probabilités ont une dimension faible ce qui contribue à éviter le problème de sur apprentissage qui peut intervenir si la dimension de vecteur de caractéristique est plus importante que le nombre des données; ce qui le cas lorsqu'on utilise les BOWs qui sont généralement de dimension élevée. L'estimation les paramètres du HCRF dans un espace de dimension réduite permet aussi de réduire le temps d'entrainement / Human activity recognition (HAR) from video sequences is one of the major active research areas of computer vision. There are numerous application HAR systems, including video-surveillance, search and automatic indexing of videos, and the assistance of frail elderly. This task remains a challenge because of the huge variations in the way of performing activities, in the appearance of the person and in the variation of the acquisition conditions. The main objective of this thesis is to develop an efficient HAR method that is robust to different sources of variability. Approaches based on interest points have shown excellent state-of-the-art performance over the past years. They are generally related to global classification methods as these primitives are temporally and spatially disordered. More recent studies have achieved a high performance by modeling the spatial and temporal context of interest points by encoding, for instance, the neighborhood of the interest points over several scales. In this thesis, we propose a method of activity recognition based on a hybrid model Support Vector Machine - Hidden Conditional Random Field (SVM-HCRF) that models the sequential aspect of activities while exploiting the robustness of interest points in real conditions. We first extract the interest points and show their robustness with respect to the person's identity by a multilinear tensor analysis. These primitives are then represented as a sequence of local "Bags of Words" (BOW): The video is temporally fragmented using the sliding window technique and each of the segments thus obtained is represented by the BOW of interest points belonging to it. The first layer of our hybrid sequential classification system is a Support Vector Machine that converts each local BOW extracted from the video sequence into a vector of activity classes’ probabilities. The sequence of probability vectors thus obtained is used as input of the HCRF. The latter permits a discriminative classification of time series while modeling their internal structures via the hidden states. We have evaluated our approach on various human activity datasets. The results achieved are competitive with those of the current state of art. We have demonstrated, in fact, that the use of a low-level classifier (SVM) improves the performance of the recognition system since the sequential classifier HCRF directly exploits the semantic information from local BOWs, namely the probability of each activity relatively to the current local segment, rather than mere raw information from interest points. Furthermore, the probability vectors have a low-dimension which prevents significantly the risk of overfitting that can occur if the feature vector dimension is relatively high with respect to the training data size; this is precisely the case when using BOWs that generally have a very high dimension. The estimation of the HCRF parameters in a low dimension allows also to significantly reduce the duration of the HCRF training phase

De nombreuses méthodes d’extraction de motifs séquentiels ont été proposées pour découvrir des motifs utiles qui décrivent les données analysées. Certaines de ces travaux se sont concentrés sur l’énumération efficace de motifs partiellement ordonnés fermés (cpo-motifs), ce qui rend leur évaluation difficile pour les experts, car leur nombre peut être important. Par suite, nous proposons une approche nouvelle, qui consiste à extraire directement des cpo-motifs multi-niveaux qui sont organisés dans une hiérarchie. Nous proposons une méthode originale dans la cadre de l’Analyse Relationnelle de Concepts (ARC), appelée RCA-SEQ, qui exploite la structure et les propriétés des treillis issus de l’ARC. RCA-SEQ comporte cinq étapes : le prétraitement des données ; l'exploration par l’ARC des données ; l'extraction automatisée d'une hiérarchie de cpo-motifs multi-niveaux par navigation des treillis issus de l’ARC ; la sélection de cpo-motifs pertinents ; l'évaluation des motifs par les experts. / Many sequential pattern mining methods have been proposed to discover useful patterns that describe the analysed sequential data. Several of these works have focused on efficiently enumerating all closed partially-ordered patterns (cpo-patterns), that makes their evaluation a laboured task for experts since their number can be large. To address this issue, we propose a new approach, that is to directly extract multilevel cpo-patterns implicitly organised into a hierarchy. To this end, we devise an original method within the Relational Concept Analysis (RCA) framework, referred to as RCA-SEQ, that exploits the structure and properties of the lattices from the RCA output. RCA-SEQ spans five steps: the preprocessing of the raw data; the RCA-based exploration of the preprocessed data; the automatic extraction of a hierarchy of multilevel cpo-patterns by navigating the lattices from the RCA output; the selection of relevant multilevel cpo-patterns; the pattern evaluation done by experts.