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.

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.

La recherche de règles d'association intéressantes est un domaine important et actif en fouille de données. Puisque les algorithmes utilisés en extraction de connaissances à partir de données (ECD), ont tendance à générer un nombre important de règles, il est difficile à l'utilisateur de sélectionner par lui même les connaissances réellement intéressantes. Pour répondre à ce problème, un post-filtrage automatique des règles s'avère essentiel pour réduire fortement leur nombre. D'où la proposition de nombreuses mesures d'intérêt dans la littérature, parmi lesquelles l'utilisateur est supposé choisir celle qui est la plus appropriée à ses objectifs. Comme l'intérêt dépend à la fois des préférences de l'utilisateur et des données, les mesures ont été répertoriées en deux catégories : les mesures subjectives (orientées utilisateur ) et les mesures objectives (orientées données). Nous nous focalisons sur l'étude des mesures objectives. Néanmoins, il existe une pléthore de mesures objectives dans la littérature, ce qui ne facilite pas le ou les choix de l'utilisateur. Ainsi, notre objectif est d'aider l'utilisateur, dans sa problématique de sélection de mesures objectives, par une approche par catégorisation. La thèse développe deux approches pour assister l'utilisateur dans sa problématique de choix de mesures objectives : (1) étude formelle suite à la définition d'un ensemble de propriétés de mesures qui conduisent à une bonne évaluation de celles-ci ; (2) étude expérimentale du comportement des différentes mesures d'intérêt à partir du point de vue d'analyse de données. Pour ce qui concerne la première approche, nous réalisons une étude théorique approfondie d'un grand nombre de mesures selon plusieurs propriétés formelles. Pour ce faire, nous proposons tout d'abord une formalisation de ces propriétés afin de lever toute ambiguïté sur celles-ci. Ensuite, nous étudions, pour différentes mesures d'intérêt objectives, la présence ou l'absence de propriétés caractéristiques appropriées. L'évaluation des mesures est alors un point de départ pour une catégorisation de celle-ci. Différentes méthodes de classification ont été appliquées : (i) méthodes sans recouvrement (CAH et k-moyennes) qui permettent l'obtention de groupes de mesures disjoints, (ii) méthode avec recouvrement (analyse factorielle booléenne) qui permet d'obtenir des groupes de mesures qui se chevauchent. Pour ce qui concerne la seconde approche, nous proposons une étude empirique du comportement d'une soixantaine de mesures sur des jeux de données de nature différente. Ainsi, nous proposons une méthodologie expérimentale, où nous cherchons à identifier les groupes de mesures qui possèdent, empiriquement, un comportement semblable. Nous effectuons par la suite une confrontation avec les deux résultats de classification, formel et empirique dans le but de valider et mettre en valeur notre première approche. Les deux approches sont complémentaires, dans l'optique d'aider l'utilisateur à effectuer le bon choix de la mesure d'intérêt adaptée à son application.

Notre travail porte sur l'extraction de connaissances sur des langages graphiques dont les symboles sont a priori inconnus. Nous formons l'hypothèse que l'observation d'une grande quantité de documents doit permettre de découvrir les symboles composant l'alphabet du langage considéré. La difficulté du problème réside dans la nature bidimensionnelle et manuscrite des langages graphiques étudiés. Nous nous plaçons dans le cadre de tracés en-ligne produit par des interfaces de saisie de type écrans tactiles, tableaux interactifs ou stylos électroniques. Le signal disponible est alors une trajectoire échantillonnée produisant une séquence de traits, eux-mêmes composés d'une séquence de points. Un symbole, élément de base de l'alphabet du langage, est donc composé d'un ensemble de traits possédant des propriétés structurelles et relationnelles spécifiques. L'extraction des symboles est réalisée par la découverte de sous-graphes répétitifs dans un graphe global modélisant les traits (noeuds) et leur relations spatiales (arcs) de l'ensemble des documents. Le principe de description de longueur minimum (MDL : Minimum Description Length) est mis en oeuvre pour choisir les meilleurs représentants du lexique des symboles. Ces travaux ont été validés sur deux bases expérimentales. La première est une base d'expressions mathématiques simples, la seconde représente des graphiques de type organigramme. Sur ces bases, nous pouvons évaluer la qualité des symboles extraits et comparer à la vérité terrain. Enfin, nous nous sommes intéressés à la réduction de la tâche d'annotation d'une base en considérant à la fois les problématiques de segmentation et d'étiquetage des différents traits.

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.

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.

Les progrès technologiques en systèmes de localisation (AIS, radar, GPS, RFID, etc.), de télétransmission (VHF, satellite, GSM, etc.), en systèmes embarqués et leur faible coût de production a permis leur déploiement à une large échelle. Énormément de données sur les déplacements d'objets sont produites par le biais de ces technologies et utilisées dans diverses applications de surveillance temps-réel comme la surveillance du trafic maritime. L'analyse a posteriori des données de déplacement de navires et d'événements à risques peut présenter des perspectives intéressantes pour la compréhension et l'aide à la modélisation des comportements à risques. Dans ce travail de thèse une méthodologie basée sur la fouille de données spatio-temporelle est proposée pour l'extraction de connaissances sur les comportements potentiellement à risques de navires. Un atelier d'aide à l'analyse de comportements de navires fondé sur cette méthodologie est aussi proposé.

Les travaux de recherche présentés dans ce mémoire s’inscrivent dans le cadre de la valorisation des connaissances issues des expériences passées afin d’améliorer les performances des processus industriels. La connaissance est considérée aujourd'hui comme une ressource stratégique importante pouvant apporter un avantage concurrentiel décisif aux organisations. La gestion des connaissances (et en particulier le retour d’expérience) permet de préserver et de valoriser des informations liées aux activités d’une entreprise afin d’aider la prise de décision et de créer de nouvelles connaissances à partir du patrimoine immatériel de l’organisation. Dans ce contexte, les progrès des technologies de l’information et de la communication jouent un rôle essentiel dans la collecte et la gestion des connaissances. L’implémentation généralisée des systèmes d’information industriels, tels que les ERP (Enterprise Resource Planning), rend en effet disponible un grand volume d’informations issues des événements ou des faits passés, dont la réutilisation devient un enjeu majeur. Toutefois, ces fragments de connaissances (les expériences passées) sont très contextualisés et nécessitent des méthodologies bien précises pour être généralisés. Etant donné le potentiel des informations recueillies dans les entreprises en tant que source de nouvelles connaissances, nous proposons dans ce travail une démarche originale permettant de générer de nouvelles connaissances tirées de l’analyse des expériences passées, en nous appuyant sur la complémentarité de deux courants scientifiques : la démarche de Retour d’Expérience (REx) et les techniques d’Extraction de Connaissances à partir de Données (ECD). Le couplage REx-ECD proposé porte principalement sur : i) la modélisation des expériences recueillies à l’aide d’un formalisme de représentation de connaissances afin de faciliter leur future exploitation, et ii) l’application de techniques relatives à la fouille de données (ou data mining) afin d’extraire des expériences de nouvelles connaissances sous la forme de règles. Ces règles doivent nécessairement être évaluées et validées par les experts du domaine avant leur réutilisation et/ou leur intégration dans le système industriel. Tout au long de cette démarche, nous avons donné une place privilégiée aux Graphes Conceptuels (GCs), formalisme de représentation des connaissances choisi pour faciliter le stockage, le traitement et la compréhension des connaissances extraites par l’utilisateur, en vue d’une exploitation future. Ce mémoire s’articule en quatre chapitres. Le premier constitue un état de l’art abordant les généralités des deux courants scientifiques qui contribuent à notre proposition : le REx et les techniques d’ECD. Le second chapitre présente la démarche REx-ECD proposée, ainsi que les outils mis en œuvre pour la génération de nouvelles connaissances afin de valoriser les informations disponibles décrivant les expériences passées. Le troisième chapitre présente une méthodologie structurée pour interpréter et évaluer l’intérêt des connaissances extraites lors de la phase de post-traitement du processus d’ECD. Finalement, le dernier chapitre expose des cas réels d’application de la démarche proposée à des interventions de maintenance industrielle. / The research work presented in this thesis relates to knowledge extraction from past experiences in order to improve the performance of industrial process. Knowledge is nowadays considered as an important strategic resource providing a decisive competitive advantage to organizations. Knowledge management (especially the experience feedback) is used to preserve and enhance the information related to a company’s activities in order to support decision-making and create new knowledge from the intangible heritage of the organization. In that context, advances in information and communication technologies play an essential role for gathering and processing knowledge. The generalised implementation of industrial information systems such as ERPs (Enterprise Resource Planning) make available a large amount of data related to past events or historical facts, which reuse is becoming a major issue. However, these fragments of knowledge (past experiences) are highly contextualized and require specific methodologies for being generalized. Taking into account the great potential of the information collected in companies as a source of new knowledge, we suggest in this work an original approach to generate new knowledge based on the analysis of past experiences, taking into account the complementarity of two scientific threads: Experience Feedback (EF) and Knowledge Discovery techniques from Databases (KDD). The suggested EF-KDD combination focuses mainly on: i) modelling the experiences collected using a knowledge representation formalism in order to facilitate their future exploitation, and ii) applying techniques related to data mining in order to extract new knowledge in the form of rules. These rules must necessarily be evaluated and validated by experts of the industrial domain before their reuse and/or integration into the industrial system. Throughout this approach, we have given a privileged position to Conceptual Graphs (CGs), knowledge representation formalism chosen in order to facilitate the storage, processing and understanding of the extracted knowledge by the user for future exploitation. This thesis is divided into four chapters. The first chapter is a state of the art addressing the generalities of the two scientific threads that contribute to our proposal: EF and KDD. The second chapter presents the EF-KDD suggested approach and the tools used for the generation of new knowledge, in order to exploit the available information describing past experiences. The third chapter suggests a structured methodology for interpreting and evaluating the usefulness of the extracted knowledge during the post-processing phase in the KDD process. Finally, the last chapter discusses real case studies dealing with the industrial maintenance domain, on which the proposed approach has been applied.

Pour rester performants et compétitifs, les systèmes de production doivent être capables de s’adapter pour faire face aux changements tels que l’évolution de la demande des clients. Il leur est essentiel de pouvoir déterminer quand et comment s’adapter (capacités, etc.). Malheureusement, de tels problèmes sont connus pour être difficiles. Les systèmes de production étant complexes, dynamiques et spécifiques, leurs gestionnaires n’ont pas toujours l’expertise nécessaire ni les prévisions suffisantes concernant l’évolution de leur système. Cette thèse vise à étudier la contribution que peut apporter l’apprentissage automatique à l’auto-adaptation des systèmes de production. Dans un premier temps, nous étudions la façon dont la littérature aborde ce domaine et en proposons un cadre conceptuel dans le but de faciliter l’analyse et la formalisation des problèmes associés. Ensuite, nous étudions une stratégie d’apprentissage à partir de modèles qui ne nécessite pas d’ensemble d’apprentissage. Nous nous intéressons plus précisément à une nouvelle approche basée sur la programmation génétique linéaire visant à extraire des connaissances itérativement à partir d’un modèle de simulation pour déterminer quand et quoi faire évoluer. Notre approche est implémentée à l’aide d’Arena et μGP. Nous l’appliquons à différents exemples qui concernent l’ajout/retrait de cartes dans un système à flux tiré, le déménagement de machines ou encore le changement de politique de réapprovisionnement. Les connaissances qui en sont extraites s’avèrent pertinentes et permettent de déterminer en continu comment chaque système peut s’adapter à des évolutions. De ce fait, elles peuvent contribuer à doter un système d’une forme d’intelligence. Exprimées sous forme d’un arbre de décision, elles sont par ailleurs facilement communicables à un gestionnaire de production. Les résultats obtenus montrent ainsi l’intérêt de notre approche tout en ouvrant de nombreuses voies de recherche. / Manufacturing systems must be able to continuously adapt their characteristics to cope with the different changes that occur along their life, in order to remain efficient and competitive. These changes can take the form of the evolution of customers demand for instance. It is essential for these systems to determine when and how to adapt (e.g., through changes in capacities). Unfortunately, such issues are known to be difficult. As manufacturing systems are complex, dynamic and specific in nature, their managers do not always have all the necessary expertise nor accurate enough forecasts on the evolution of their system. This thesis aims at studying the possible contributions of machine learning to the self-adaptation of manufacturing systems. We first study how the literature deals with self-adaptation and we propose a conceptual framework to facilitate the analysis and the formalization of the associated problems. Then, we study a learning strategy relying on models, which presents the advantage of not requiring any training set. We focus more precisely on a new approach based on linear genetic programming that iteratively extracts knowledge from a simulation model. Our approach is implemented using Arena and μGP. We show its benefits by applying it to increase/decrease the number of cards in a pull control system, to move machines or to change the inventory replenishment policy. The extracted knowledge is found to be relevant for continuously determining how each system can adapt to evolutions. It can therefore contribute to provide these systems with some intelligent capabilities. Moreover, this knowledge is expressed in the simple and understandable form of a decision tree, so that it can also be easily communicated to production managers in view of their everyday use. Our results thus show the interest of our approach while opening many research directions.

La popularité des réseaux sociaux a rapidement augmenté au cours de la dernière décennie. Selon Statista, environ 2 milliards d'utilisateurs utiliseront les réseaux sociaux d'ici janvier 2018 et ce nombre devrait encore augmenter au cours des prochaines années. Tout en gardant comme objectif principal de connecter le monde, les réseaux sociaux jouent également un rôle majeur dans la connexion des commerçants avec les clients, les célébrités avec leurs fans, les personnes ayant besoin d'aide avec les personnes désireuses d'aider, etc.. Le succès de ces réseaux repose principalement sur l'information véhiculée ainsi que sur la capacité de diffusion des messages dans les réseaux sociaux. Notre recherche vise à modéliser la diffusion des messages ainsi qu'à extraire et à représenter l'information des messages dans les réseaux sociaux. Nous introduisons d'abord une approche de prédiction de la diffusion de l'information dans les réseaux sociaux. Plus précisément, nous prédisons si un tweet va être re-tweeté ou non ainsi que son niveau de diffusion. Notre modèle se base sur trois types de caractéristiques: basées sur l'utilisateur, sur le temps et sur le contenu. Nous avons évalué notre modèle sur différentes collections correspondant à une douzaine de millions de tweets. Nous avons montré que notre modèle améliore significativement la F-mesure par rapport à l'état de l'art, à la fois pour prédire si un tweet va être re-tweeté et pour prédire le niveau de diffusion. La deuxième contribution de cette thèse est de fournir une approche pour extraire des informations dans les microblogs. Plusieurs informations importantes sont incluses dans un message relatif à un événement, telles que la localisation, l'heure et les entités associées. Nous nous concentrons sur l'extraction de la localisation qui est un élément primordial pour plusieurs applications, notamment les applications géospatiales et les applications liées aux événements. Nous proposons plusieurs combinaisons de méthodes existantes d'extraction de localisation dans des tweets en ciblant des applications soit orientées rappel soit orientées précision. Nous présentons également un modèle pour prédire si un tweet contient une référence à un lieu ou non. Nous montrons que nous améliorons significativement la précision des outils d'extraction de lieux lorsqu'ils se focalisent sur les tweets que nous prédisons contenir un lieu. Notre dernière contribution présente une base de connaissances permettant de mieux représenter l'information d'un ensemble de tweets liés à des événements. Nous combinons une collection de tweets de festivals avec d'autres ressources issues d'Internet pour construire une ontologie de domaine. Notre objectif est d'apporter aux utilisateurs une image complète des événements référencés au sein de cette collection. / The popularity of online social networks has rapidly increased over the last decade. According to Statista, approximated 2 billion users used social networks in January 2018 and this number is still expected to grow in the next years. While serving its primary purpose of connecting people, social networks also play a major role in successfully connecting marketers with customers, famous people with their supporters, need-help people with willing-help people. The success of online social networks mainly relies on the information the messages carry as well as the spread speed in social networks. Our research aims at modeling the message diffusion, extracting and representing information and knowledge from messages on social networks. Our first contribution is a model to predict the diffusion of information on social networks. More precisely, we predict whether a tweet is going to be diffused or not and the level of the diffusion. Our model is based on three types of features: user-based, time-based and content-based features. Being evaluated on various collections corresponding to dozen millions of tweets, our model significantly improves the effectiveness (F-measure) compared to the state-of-the-art, both when predicting if a tweet is going to be retweeted or not, and when predicting the level of retweet. The second contribution of this thesis is to provide an approach to extract information from microblogs. While several pieces of important information are included in a message about an event such as location, time, related entities, we focus on location which is vital for several applications, especially geo-spatial applications and applications linked to events. We proposed different combinations of various existing methods to extract locations in tweets targeting either recall-oriented or precision-oriented applications. We also defined a model to predict whether a tweet contains a location or not. We showed that the precision of location extraction tools on the tweets we predict to contain a location is significantly improved as compared when extracted from all the tweets.Our last contribution presents a knowledge base that better represents information from a set of tweets on events. We combined a tweet collection with other Internet resources to build a domain ontology. The knowledge base aims at bringing users a complete picture of events referenced in the tweet collection (we considered the CLEF 2016 festival tweet collection).