Les Séries Temporelles d'Images Satellitaires (STIS), visant la même scène en évolution, sont très intéressantes parce qu'elles acquièrent conjointement des informations temporelles et spatiales. L'extraction de ces informations pour aider les experts dans l'interprétation des données satellitaires devient une nécessité impérieuse. Dans ce mémoire, nous exposons comment on peut adapter l'extraction de motifs séquentiels fréquents à ce contexte spatio-temporel dans le but d'identifier des ensembles de pixels connexes qui partagent la même évolution temporelle. La démarche originale est basée sur la conjonction de la contrainte de support avec différentes contraintes de connexité qui peuvent filtrer ou élaguer l'espace de recherche pour obtenir efficacement des motifs séquentiels fréquents groupés (MSFG) avec signification pour l'utilisateur. La méthode d'extraction proposée est non supervisée et basée sur le niveau pixel. Pour vérifier la généricité du concept de MSFG et la capacité de la méthode proposée d'offrir des résultats intéressants à partir des SITS, sont réalisées des expérimentations sur des données réelles optiques et radar.

L'extraction de motifs séquentiels est devenue, depuis son introduction, une technique majeure du domaine de la fouille de données avec de nombreuses applications (analyse du comportement des consommateurs, bioinformatique, sécurité, musique, etc.). Les motifs séquentiels permettent la découverte de corrélations entre événements en fonction de leurs chronologies d'apparition. Il existe de nombreux algorithmes permettant l'extraction de tels motifs. Toutefois, ces propositions ne prennent en compte qu'une seule dimension d'analyse (e.g le produit dans les applications de type étude des achats des consommateurs) alors que la plupart des données réelles sont multidimensionnelles par nature. Dans ce manuscrit, nous définissons les motifs séquentiels multidimensionnels afin de prendre en compte les spécificités inhérentes aux bases de données multidimensionnelles (plusieurs dimensions, hiérarchies, valeurs agrégées). Nous définissons des algorithmes permettant l'extraction de motifs séquentiels multi- dimensionnels en tenant compte des ces spécificités. Des expérimentations menées sur des données synthétiques et sur des données réelles sont rapportées et montrent l'intérêt de nos propositions. Nous nous intéressons également à l'extraction de comportements temporels atypiques dans des données multidimensionnelles. Nous montrons qu'il peut y avoir plusieurs interprétations d'un comportement atypique (fait ou connaissance). En fonction de chaque interprétation, nous proposons une méthode d'extraction de tels comportements. Ces méthodes sont également validées par des expérimentations sur des données réelles.

Extraction de séquences fréquentes : des bases de données statiques aux flots de données Il est reconnu aujourd'hui que l'être humain est généralement noyé sous une profusion d'informations et que sa capacité d'analyse n'est plus capable de faire face au volume sans cesse croissant de données. C'est dans ce contexte qu'est né le processus d'Extraction de Connaissance dans les bases de Données. Un des buts de ce processus est de passer d'un grand volume d'informations à un petit ensemble de connaissances à fortes valeurs ajoutées pour l'analyste ou le décideur. De plus, le processus d'ECD n'est pas un processus monolithique et univoque au cours duquel il s'agirait d'appliquer un principe général à tous les types de données stockées ou récupérées. Ainsi, une des étapes de ce processus qu'est la fouille de données peut se dériver sous plusieurs formes tels que : le clustering, la classification, l'extraction d'itemset et de règles d'associations, l'extraction de structures plus complexes tels que les épisodes, les graphes ou comme dans le cadre de cette thèse l'extraction de motifs séquentiels. Malheureusement, dans un monde sans cesse en évolution, le contexte dans lequel les travaux d'ECD ont été définis ces dernières années considérait que les données, sur lesquelles la fouille était réalisée, étaient disponibles dans des bases de données statiques. Aujourd'hui, suite au développement de nouvelles technologies et applications associées, nous devons faire face à de nouveaux modèles dans lesquels les données sont disponibles sous la forme de flots. Une question se pose alors : quid des approches d'extraction de connaissances traditionnelles ? Dans ce mémoire, nous présentons un ensemble de résultat sur les motifs séquentiels dans les bases de données d'un point de vue des représentations condensées et des méthodes d'échantillonnage puis nous étendons nos différentes approches afin de prendre en compte le nouveau modèle des flots de données. Nous présentons des algorithmes permettant ainsi l'extraction de motifs séquentiels (classiques et multidimensionnels) sur les flots. Des expérimentations menées sur des données synthétiques et sur des données réelles sont rapportées et montrent l'intérêt de nos propositions.

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.

Avec le développement des nouvelles technologies d'analyse (comme par exemple les puces à ADN) et de gestion de l'information (augmentation des capacités de stockage), le domaine de la santé a particulièrement évolué ces dernières années. En effet, des techniques de plus en plus avancées et efficaces sont mises à disposition des chercheurs, et permettent une étude approfondie des paramètres génomiques intervenant dans des problèmes de santé divers (cancer, maladie d'Alzheimer ...) ainsi que la mise en relation avec les paramètres cliniques. Parallèlement, l'évolution des capacités de stockage permet désormais d'accumuler la masse d'information générée par les diverses expériences menées. Ainsi, les avancées en terme de médecine et de prévention passent par l'analyse complète et pertinente de cette quantité de données. Le travail de cette thèse s'inscrit dans ce contexte médical. Nous nous sommes particulièrement intéressé à l'extraction automatique de motifs graduels, qui mettent en évidence des corrélations de variation entre attributs de la forme "plus un patient est âgé, moins ses souvenirs sont précis". Nous décrivons divers types de motifs graduels tels que les itemsets graduels, les itemset multidimensionnels graduels ou encore les motifs séquentiels graduels, ainsi que les sémantiques associées à ces motifs. Chacune de nos approches est testée sur un jeu de données synthétique et/ou réel.

L'information occupe désormais une place centrale dans notre vie quotidienne, elle est à la fois omniprésente et facile d'accès. Pourtant, l'extraction de l'information à partir des données est un processus souvent inaccessible. En effet, même si les méthodes de fouilles de données sont maintenant accessibles à tous, les résultats de ces fouilles sont souvent complexes à obtenir et à exploiter pour l'utilisateur. La fouille de motifs combinée à l'utilisation de contraintes est une direction très prometteuse de la littérature pour à la fois améliorer l'efficience de la fouille et rendre ses résultats plus appréhendables par l'utilisateur. Cependant, la combinaison de contraintes désirée par l'utilisateur est souvent problématique car, elle n'est pas toujours adaptable aux caractéristiques des données fouillées tel que le bruit. Dans cette thèse, nous proposons deux nouvelles contraintes et un algorithme pour pallier ce problème. La contrainte de robustesse permet de fouiller des données bruitées en conservant la valeur ajoutée de la contrainte de contiguïté. La contrainte de clôture allégée améliore l'appréhendabilité de la fouille de motifs tout en étant plus résistante au bruit que la contrainte de clôture classique. L'algorithme C3Ro est un algorithme générique de fouille de motifs séquentiels intégrant de nombreuses contraintes, notamment les deux nouvelles contraintes que nous avons introduites, afin de proposer à l'utilisateur la fouille la plus efficiente possible tout en réduisant au maximum la taille de l'ensemble des motifs extraits. C3Ro rivalise avec les meilleurs algorithmes de fouille de motifs de la littérature en termes de temps d'exécution tout en consommant significativement moins de mémoire. C3Ro a été expérimenté dans le cadre de l’extraction de compétences présentes dans les offres d'emploi sur le Web / Information now occupies a central place in our daily lives, it is both ubiquitous and easy to access. Yet extracting information from data is often an inaccessible process. Indeed, even though data mining methods are now accessible to all, the results of these mining are often complex to obtain and exploit for the user. Pattern mining combined with the use of constraints is a very promising direction of the literature to both improve the efficiency of the mining and make its results more apprehensible to the user. However, the combination of constraints desired by the user is often problematic because it does not always fit with the characteristics of the searched data such as noise. In this thesis, we propose two new constraints and an algorithm to overcome this issue. The robustness constraint allows to mine noisy data while preserving the added value of the contiguity constraint. The extended closedness constraint improves the apprehensibility of the set of extracted patterns while being more noise-resistant than the conventional closedness constraint. The C3Ro algorithm is a generic sequential pattern mining algorithm that integrates many constraints, including the two new constraints that we have introduced, to provide the user the most efficient mining possible while reducing the size of the set of extracted patterns. C3Ro competes with the best pattern mining algorithms in the literature in terms of execution time while consuming significantly less memory. C3Ro has been experienced in extracting competencies from web-based job postings

La quantité de données aujourd'hui emmagasinées dans tous les domaines ainsi que leur diversité d'origines et de formats rendent impossibles l'analyse, le résumé ou l'extraction manuelle de connaissances. Pour répondre à ces besoins, diverses communautés se sont intéressées à la conception et au développement d'outils permettant d'extraire automatiquement de la connaissance de ces grandes bases. Désormais ces travaux visent à prendre en compte l'hétérogénéité de ces données, de leur format et de leur qualité. Notre travail s'inscrit dans cet axe de recherche et, plus précisément, dans le contexte de la découverte de schémas fréquents à partir de données regroupées sous la forme de séquences ordonnées. Ces schémas, appelés motifs séquentiels, n'étaient jusqu'alors extraits que sur des bases de données de séquences symboliques et parfaites, c'est-à-dire des bases ne contenant que des informations binaires ou pouvant être traitées comme telles et ne contenant aucun enregistrement incomplet. Nous avons donc proposé plusieurs améliorations des techniques d'extraction de séquences fréquentes afin de prendre en compte des données hétérogènes, incomplètes, incertaines ou mal connues de leur utilisateur, tout en minimisant les pertes éventuelles d'informations. Ainsi, le travail présenté dans cette thèse comporte la mise en oeuvre d'un cadre pour l'extraction de motifs séquentiels en présence de données numériques quantitatives, la définition de contraintes temporelles relâchées autorisant l'utilisateur à spécifier des contraintes temporelles approximatives et permettant un tri des résultats obtenus selon un indice de précision temporelle, enfin, le développement de deux approches pour l'extraction de motifs séquentiels sur des données symboliques incomplètes.

Les motifs séquentiels peuvent être vus comme une extension de la notion d'itemsets fréquents intégrant diverses contraintes temporelles. La recherche de tels motifs consiste ainsi à extraire des enchaînements d'ensembles d'items, couramment associés sur une période de temps bien spécifiée. La construction de règles à partir de ces motifs séquentiels permet d'étendre la notion de règles d'association pour la pris en compte de la temporalité. En fait, cette recherche met en évidence des associations inter-transactions, contrairement à celle des règles d'association qui extrait des combinaisons intra-transactions. Ce problème, posé à l'origine dans un contexte de marketing, intéresse à présent des domaines aussi variés que les télécommunications, la finance, ou encore la médecine et la bioinformatique. Même s'il existe aujourd'hui de très nombreuses approches efficaces pour extraire des motifs, ces derniers ne sont pas forcément adaptés aux besoins des applications réelles. En fait, les résultats obtenus sont basés sur une mesure statistique et ne tiennent pas compte de la connaissance du domaine. De plus, ces approches sont principalement axées sur la recherche de tendances et ne permettent pas d'extraire des connaissances sur les éléments atypiques ou inattendus. Dans le cadre de cette thèse, nous nous intéressons donc à la problématique de l'extraction de motifs séquentiels et règles inattendus en intégrant la connaissance du domaine. Le travail présenté dans cette thèse comporte la mise en œuvre d'un cadre MUSE pour l'extraction de séquences inattendues par rapport à un système de croyances, des extensions avec la théorie de logique floue, l'intégration des données hiérarchisées, la définition des motifs séquentiels et règles inattendus et, enfin, l'extraction de phrases inattendues dans des documents textes. Des expérimentations menées sur des données synthétiques et sur des données réelles sont rapportées et montrent l'intérêt de nos propositions.

Les Séries Temporelles d'Images Satellitaires (STIS), visant la même scène en évolution, sont très intéressantes parce qu'elles acquièrent conjointement des informations temporelles et spatiales. L'extraction de ces informations pour aider les experts dans l'interprétation des données satellitaires devient une nécessité impérieuse. Dans ce mémoire, nous exposons comment on peut adapter l'extraction de motifs séquentiels fréquents à ce contexte spatio-temporel dans le but d'identifier des ensembles de pixels connexes qui partagent la même évolution temporelle. La démarche originale est basée sur la conjonction de la contrainte de support avec différentes contraintes de connexité qui peuvent filtrer ou élaguer l'espace de recherche pour obtenir efficacement des motifs séquentiels fréquents groupés (MSFG) avec signification pour l'utilisateur. La méthode d'extraction proposée est non supervisée et basée sur le niveau pixel. Pour vérifier la généricité du concept de MSFG et la capacité de la méthode proposée d'offrir des résultats intéressants à partir des SITS, sont réalisées des expérimentations sur des données réelles optiques et radar. / The Satellite Image Time Series (SITS), aiming the same scene in evolution, are of high interest as they capture both spatial and temporal information. The extraction of this infor- mation to help the experts interpreting the satellite data becomes a stringent necessity. In this work, we expound how to adapt frequent sequential patterns extraction to this spatiotemporal context in order to identify sets of connected pixels sharing a same temporal evolution. The original approach is based on the conjunction of support constraint with different constraints based on pixel connectivity that can filter or prune the search space in order to efficiently ob- tain Grouped Frequent Sequential (GFS) patterns that are meaningful to the end user. The proposed extraction method is unsupervised and pixel level based. To verify the generality of GFS-pattern concept and the proposed method capability to offer interesting results from SITS, real data experiments on optical and radar data are presented.

Cette thèse présente un cadre de travail d'analyse de trajectoires contenant une phase de prétraitement et un processus d’extraction de trajectoires d’objets mobiles. Le cadre offre des fonctions visuelles reflétant le comportement d'évolution des motifs de trajectoires. L'originalité de l’approche est d’allier extraction de motifs fréquents, extraction de motifs émergents et analyse formelle de concepts pour analyser les trajectoires. A partir des données de trajectoires, les méthodes proposées détectent et caractérisent les comportements d'évolution des motifs. Trois contributions sont proposées : Une méthode d'analyse des trajectoires, basée sur les concepts formels fréquents, est utilisée pour détecter les différents comportements d’évolution de trajectoires dans le temps. Ces comportements sont “latents”, "emerging", "decreasing", "lost" et "jumping". Ils caractérisent la dynamique de la mobilité par rapport à l'espace urbain et le temps. Les comportements détectés sont visualisés sur des cartes générées automatiquement à différents niveaux spatio-temporels pour affiner l'analyse de la mobilité dans une zone donnée de la ville. Une deuxième méthode basée sur l'extraction de concepts formels séquentiels fréquents a également été proposée pour exploiter la direction des mouvements dans la détection de l'évolution. Enfin, une méthode de prédiction basée sur les chaînes de Markov est présentée pour prévoir le comportement d’évolution dans la future période pour une région. Ces trois méthodes sont évaluées sur ensembles de données réelles . Les résultats expérimentaux obtenus sur ces données valident la pertinence de la proposition et l'utilité des cartes produites / This dissertation presents a trajectory analysis framework, which includes both a preprocessing phase and trajectory mining process. Furthermore, the framework offers visual functions that reflect trajectory patterns evolution behavior. The originality of the mining process is to leverage frequent emergent pattern mining and formal concept analysis for moving objects trajectories. These methods detect and characterize pattern evolution behaviors bound to time in trajectory data. Three contributions are proposed: (1) a method for analyzing trajectories based on frequent formal concepts is used to detect different trajectory patterns evolution over time. These behaviors are "latent", "emerging", "decreasing", "lost" and "jumping". They characterize the dynamics of mobility related to urban spaces and time. The detected behaviors are automatically visualized on generated maps with different spatio-temporal levels to refine the analysis of mobility in a given area of the city, (2) a second trajectory analysis framework that is based on sequential concept lattice extraction is also proposed to exploit the movement direction in the evolution detection process, and (3) prediction method based on Markov chain is presented to predict the evolution behavior in the future period for a region. These three methods are evaluated on two real-world datasets. The obtained experimental results from these data show the relevance of the proposal and the utility of the generated maps