Les données hospitalières présentent de nombreuses spécificités qui rendent difficilement applicables les méthodes de fouille de données traditionnelles. Dans cette thèse, nous nous intéressons à l'hétérogénéité de ces données ainsi qu'à leur aspect temporel. Dans le cadre du projet ANR ClinMine et d'une convention CIFRE avec la société Alicante, nous proposons deux nouvelles méthodes d'extraction de connaissances adaptées à ces types de données. Dans la première partie, nous développons l'algorithme MOSC (Multi-Objective Sequence Classification) pour la classification supervisée sur données hétérogènes, numériques et temporelles. Cette méthode accepte, en plus des termes binaires ou symboliques, des termes numériques et des séquences d'événements temporels pour former des ensembles de règles de classification. MOSC est le premier algorithme de classification supportant simultanément ces types de données. Dans la seconde partie, nous proposons une méthode de biclustering pour données hétérogènes, un problème qui n'a à notre connaissance jamais été exploré. Cette méthode, HBC (Heterogeneous BiClustering), est étendue pour supporter les données temporelles de différents types : événements temporels et séries temporelles irrégulières. HBC est utilisée pour un cas d'étude sur un ensemble de données hospitalières, dont l'objectif est d'identifier des groupes de patients ayant des profils similaires. Les résultats obtenus sont cohérents et intéressants d'un point de vue médical ; et amènent à la définition de cas d'étude plus précis. L'intégration dans une solution logicielle est également engagée, avec une version parallèle de HBC et un outil de visualisation des résultats. / Hospital data exhibit numerous specificities that make the traditional data mining tools hard to apply. In this thesis, we focus on the heterogeneity associated with hospital data and on their temporal aspect. This work is done within the frame of the ANR ClinMine research project and a CIFRE partnership with the Alicante company. In this thesis, we propose two new knowledge discovery methods suited for hospital data, each able to perform a variety of tasks: classification, prediction, discovering patients profiles, etc.In the first part, we introduce MOSC (Multi-Objective Sequence Classification), an algorithm for supervised classification on heterogeneous, numeric and temporal data. In addition to binary and symbolic terms, this method uses numeric terms and sequences of temporal events to form sets of classification rules. MOSC is the first classification algorithm able to handle these types of data simultaneously. In the second part, we introduce HBC (Heterogeneous BiClustering), a biclustering algorithm for heterogeneous data, a problem that has never been studied so far. This algorithm is extended to support temporal data of various types: temporal events and unevenly-sampled time series. HBC is used for a case study on a set of hospital data, whose goal is to identify groups of patients sharing a similar profile. The results make sense from a medical viewpoint; they indicate that relevant, and sometimes new knowledge is extracted from the data. These results also lead to further, more precise case studies. The integration of HBC within a software is also engaged, with the implementation of a parallel version and a visualization tool for biclustering results.

Les outils de simulation ont déjà été éprouvés pour l'étude de nombreux phénomènes, mais simuler le comportement humain reste un défi à la fois pour l'informatique et les sciences humaines. Dans ce contexte, nous avons travaillé sur la simulation des comportements individuels et des interactions sociales dans les groupes d'individus pour observer l'émergence de phénomènes sociaux. À cette fin, nous avons mener un travail inter-disciplinaire mêlant des techniques d'intelligence artificielle, de systèmes multi-agents, de sciences humaines et de fouille de données spatio-temporelles. Cette thèse présente un nouveau modèle d'agent émotionnel : l'agent EFT (Emotion, Feeling, Temperament). Basée sur une architecture BDI, notre modèle intègre le modèle émotionnel OCC et le modèle comportemental PerformanSe. Nous présentons également une implémentation concrète de notre modèle : la simulation de personnes cérébrolésés sur une chaîne de conditionnement. Nous décrivons la modélisation des interactions de notre système grâce à AgentUML. Via des méthodes de fouille de données spatio-temporel, nous extrayons les informations pertinentes à partir des données issues de la simulation.

La production d’énergie, et en particulier la production d’électricité, est la principale responsable de l’émission de gaz à effet de serre au niveau mondial. Le secteur résidentiel étant le plus consommateur d’énergie, il est essentiel d’agir au niveau personnel afin de réduire ces émissions. Avec le développement de l’informatique ubiquitaire, il est désormais aisé de récolter des données de consommation d’électricité des appareils électriques d’un logement. Cette possibilité a permis le développement des technologies eco-feedback, dont l’objectif est de fournir aux consommateurs un retour sur leur consommation dans le but de la diminuer. Dans cette thèse nous proposons une méthode de visualisation de données temporelles personnelles basée sur une interaction what if, qui signifie que les utilisateurs peuvent appliquer des changements de comportement de manière virtuelle. En particulier notre méthode permet de simuler une modification de l’utilisation des appareils électriques d’un logement, puis d’évaluer visuellement l’impact de ces modifications sur les données. Cette méthode a été implémentée dans le système Activelec, que nous avons évalué avec des utilisateurs sur des données réelles. Nous synthétisons les éléments de conception indispensables aux systèmes eco-feedback dans un état de l’art. Nous exposons également les limitations de ces technologies, la principale étant la difficulté rencontrée par les utilisateurs pour trouver des modifications de comportement pertinentes leur permettant de consommer moins d’énergie.Nous présentons ensuite trois contributions. La première contribution est la conception d’une méthode what if appliquée à l’eco-feedback ainsi que son implémentation dans le système Activelec. La seconde contribution est l’évaluation de notre méthode grâce à deux expérimentations menées en laboratoire. Dans ces expérimentations nous évaluons si des participants utilisant notre méthode trouvent des modifications qui économisent de l’énergie et qui nécessitent suffisamment peu d’efforts pour être appliquées en vrai. Enfin la troisième contribution est l’évaluation in-situ du système Activelec dans des logements personnels pour une durée d’environ un mois. Activelec a été déployé dans trois appartements privés afin de permettre l’évaluation de notre méthode en contexte domestique réel. Dans ces trois expérimentations, les participants ont pu trouver des modifications d’utilisation des appareils qui économiseraient une quantité d’énergie significative, et qui ont été jugées faciles à appliquer en réalité. Nous discutons également de l’application de notre méthode what if au-delà des données de consommation électrique au domaine de la visualisation personnelle, qui est définie comme l’analyse visuelle des données personnelles. Nous présentons ainsi plusieurs applications possibles à d’autres données temporelles personnelles, par exemple concernant l’activité physique ou les transports. Cette thèse ouvre de nouvelles perspectives pour l’utilisation d’un paradigme d’interaction what if pour la visualisation personnelle. / The production of energy, in particular the production of electricity, is the main responsible for the emission of greenhouse gases at world scale. The residential sector being the most energy consuming, it is essential to act at a personal scale to reduce these emissions. Thanks to the development of ubiquitous computing, it is now easy to collect data about the electricity consumption of electrical appliances of a housing. This possibility has allowed the development of eco-feedback technologies, whose objective is to provide to consumers a feedback about their consumption with the aim to reduce it. In this thesis we propose a personal visualization method for time-dependent data based on a what if interaction, which means that users can apply modifications in their behavior in a virtual way. Especially our method allows to simulate the modification of the usage of electrical appliances of a housing, and then to evaluate visually the impact of the modifications on data. This approach has been implemented in the Activelec system, which we have evaluated with users on real data.We synthesize the essential elements of conception for eco-feedback systems in a state of the art. We also outline the limitations of these technologies, the main one being the difficulty faced by users to find relevant modifications in their behavior to decrease their energy consumption. We then present three contributions. The first contribution is the development of a what if approach applied to eco-feedback as well as its implementation in the Activelec system. The second contribution is the evaluation of our approach with two laboratory studies. In these studies we assess if participants using our method manage to find modifications that save energy and which require a sufficiently low effort to be applied in reality. Finally the third contribution is the in-situ evaluation of the Activelec system. Activelec has been deployed in three private housings and used for a duration of approximately one month. This in-situ experiment allows to evaluate the usage of our approach in a real domestic context. In these three studies, participants managed to find modifications in the usage of appliances that would savea significant amount of energy, while being judged easy to be applied in reality.We also discuss of the application of our what if approach to the domain of personal visualization, beyond electricity consumption data, which is defined as the visual analysis of personal data. We hence present several potential applications to other types of time-dependent personal data, for example related to physical activity or to transportation. This thesis opens new perspectives for using a what if interaction paradigm for personal visualization.

Cette thèse introduit un nouveau type de motif appelé signature. La signature segmente une séquence d'itemsets, afin de maximiser la taille de l'ensemble d'items qui apparaît dans tous les segments. La signature a été initialement introduite pour identifier les produits favoris d'un consommateur de supermarché à partir de son historique d'achat. L'originalité de la signature vient du fait qu'elle identifie les items récurrents qui 1) peuvent apparaître à différentes échelles temporelles, 2) peuvent avoir des occurrences irrégulières et 3) peuvent être rapidement compris par des analystes. Étant donné que les approches existantes en fouille de motifs n'ont pas ces 3 propriétés, nous avons introduit la signature. En comparant la signature avec les méthodes de l'état de l'art, nous avons montré que la signature est capable d'identifier de nouvelles régularités dans les données, tout en identifiant les régularités détectées par les méthodes existantes. Bien qu'initialement liée au domaine de la fouille de motifs, nous avons également lié le problème de la fouille de signatures au domaine de la segmentation de séquences. Nous avons ensuite défini différents algorithmes, utilisant des méthodes liées à la fouille de motifs et à la segmentation de séquences. Les signatures ont été utilisées pour analyser un large jeu de données issu d'un supermarché français. Une analyse qualitative des signatures calculées sur ces consommateurs réels a montré que les signatures sont capables d'identifier les produits favoris d'un consommateur. Les signatures ont également été capables de détecter et de caractériser l'attrition de consommateurs. Cette thèse définit également 2 extensions de la signature. La première extension est appelée la sky-signature. La sky-signature permet de présenter les items récurrents d'une séquence à différentes échelles de temps. La sky-signature peut être vue comme une manière efficace de résumer les signatures calculées à toutes les échelles de temps possibles. Les sky-signatures ont été utilisées pour analyser les discours de campagne des candidats à la présidentielle américaine de 2016. Les sky-signatures ont identifié les principaux thèmes de campagne de chaque candidat, ainsi que leur rythme de campagne. Cette analyse a également montré que les signatures peuvent être utilisées sur d'autres types de jeux de données. Cette thèse introduit également une deuxième extension de la signature, qui permet de calculer la signature qui correspond le plus aux données. Cette extension utilise une technique de sélection de modèle basée sur le principe de longueur de description minimale, communément utilisée en fouille de motifs. Cette extension a également été utilisée pour analyser des consommateurs de supermarché. / Cette thèse introduit un nouveau type de motif appelé signature. La signature segmente une séquence d'itemsets, afin de maximiser la taille de l'ensemble d'items qui apparaît dans tous les segments. La signature a été initialement introduite pour identifier les produits favoris d'un consommateur de supermarché à partir de son historique d'achat. L'originalité de la signature vient du fait qu'elle identifie les items récurrents qui 1) peuvent apparaître à différentes échelles temporelles, 2) peuvent avoir des occurrences irrégulières et 3) peuvent être rapidement compris par des analystes. Étant donné que les approches existantes en fouille de motifs n'ont pas ces 3 propriétés, nous avons introduit la signature. En comparant la signature avec les méthodes de l'état de l'art, nous avons montré que la signature est capable d'identifier de nouvelles régularités dans les données, tout en identifiant les régularités détectées par les méthodes existantes. Bien qu'initialement liée au domaine de la fouille de motifs, nous avons également lié le problème de la fouille de signatures au domaine de la segmentation de séquences. Nous avons ensuite défini différents algorithmes, utilisant des méthodes liées à la fouille de motifs et à la segmentation de séquences. Les signatures ont été utilisées pour analyser un large jeu de données issu d'un supermarché français. Une analyse qualitative des signatures calculées sur ces consommateurs réels a montré que les signatures sont capables d'identifier les produits favoris d'un consommateur. Les signatures ont également été capables de détecter et de caractériser l'attrition de consommateurs. Cette thèse définit également 2 extensions de la signature. La première extension est appelée la sky-signature. La sky-signature permet de présenter les items récurrents d'une séquence à différentes échelles de temps. La sky-signature peut être vue comme une manière efficace de résumer les signatures calculées à toutes les échelles de temps possibles. Les sky-signatures ont été utilisées pour analyser les discours de campagne des candidats à la présidentielle américaine de 2016. Les sky-signatures ont identifié les principaux thèmes de campagne de chaque candidat, ainsi que leur rythme de campagne. Cette analyse a également montré que les signatures peuvent être utilisées sur d'autres types de jeux de données. Cette thèse introduit également une deuxième extension de la signature, qui permet de calculer la signature qui correspond le plus aux données. Cette extension utilise une technique de sélection de modèle basée sur le principe de longueur de description minimale, communément utilisée en fouille de motifs. Cette extension a également été utilisée pour analyser des consommateurs de supermarché.

Les données temporelles sont fréquemment manipulées dans plusieurs domaines d'application (bancaire, clinique, géographique, etc.). Malgré la diversité des techniques proposées pour visualiser ce type de données, nous constatons un manque d'approches et de méthodes de conception. Dans cette thèse, nous proposons une approche de conception de techniques de visualisation et plus généralement d'interaction avec des espaces de données temporelles. Pour garantir l'utilisabilité de ces techniques, nous proposons de prendre en compte les caractéristiques des données manipulées et les tâches utilisateur, nous situant ainsi à la jonction de deux domaines de l'informatique : les Bases de Données et les Interfaces Homme-Machine. Ce travail contribue donc à la conception de systèmes interactifs pour l'analyse visuelle de données temporelles. Dans ce contexte, nous proposons une taxonomie qui organise les travaux existants de visualisation de données temporelles selon leur processus de visualisation. Cette taxonomie est construite à partir du processus de visualisation proposé par Chi. En collaboration avec des utilisateurs géographes, nous avons identifié une liste de tâches utilisateur pertinentes pour la manipulation de données temporelles. A partir de cette liste, nous avons conçu et implémenté cinq techniques d'interaction adaptées aux tâches identifiées. Nous avons intégré ces techniques pour développer INVEST (Interactive Visualization and Explorative System of Temporal data) qui est une plate-forme multi-techniques pour l'analyse visuelle de données temporelles. Chaque technique de visualisation est une vue du même espace de données. INVEST inclut un moteur de sélection de techniques de visualisation en fonction des tâches utilisateur spécifiées.

La technologie des puces à ADN a rendu aujourd'hui possible de mesurer les niveaux d'expression de milliers de gènes durant des processus biologiques importants. Analyser des profils d'expression de multiples gènes offre la possibilité d'éclairer certains aspects de la génomique fonctionnelle. Ce travail porte sur l'analyse, la classification et l'interprétation de profils d'expressions de gènes durant le processus de division cellulaire. La division cellulaire est le processus biologique de prolifération des cellules qui devient drastiquement aberrant dans le cas de cellules cancéreuses. Tenant compte de la structure temporelle des données d'expression, nous avons étudié trois familles de mesures de proximités. La première famille définit des mesures limitées à la comparaison des valeurs des expressions en ignorant la contrainte de dépendance temporelle des données. La seconde famille se limite à la comparaison des formes des expressions. Enfin, la troisième famille de mesures couvre simultanément les aspects formes et valeurs. Une formalisation unifiée de ces mesures est proposée. Une classification adaptative de milliers de gènes est appliquée afin d'apprendre la mesure de proximité à considérer pour l'identification et la caractérisation de gènes impliqués dans les phases du cycle cellulaire.

De nombreuses données sont enregistrées dans le cadre d'applications variées et leur analyse est un challenge abordé par de nombreuses études. Parmi ces différentes applications, cette thèse est motivée par l'analyse de parcours patients pour mener des études de pharmaco-épidémiologie. La pharmaco-épidémiologie est l'étude des usages et effets de produits de santé au sein de populations définies. Le but est donc d'automatiser ce type d'étude en analysant des données. Parmi les méthodes d'analyses de données, les approches d'extraction de motifs extraient des descriptions de comportements, appelées motifs, caractérisant ces données. L'intérêt principal de telles approches est de donner un aperçu des comportements décrivant les données. Dans cette thèse, nous nous intéressons à l'extraction de motifs temporels discriminants au sein de séquences temporelles, c'est-à-dire une liste d'évènements datés. Les motifs temporels sont des motifs représentant des comportements par leur dimension temporelle. Les motifs discriminants sont des motifs représentant les comportements apparaissant uniquement pour une sous-population bien définie. Alors que les motifs temporels sont essentiels pour décrire des données temporelles et que les motifs discriminants le sont pour décrire des différences de comportement, les motifs temporels discriminants ne sont que peu étudiés. Dans cette thèse, le modèle de chronique discriminante est proposé pour combler le manque d'approches d'extraction de motifs temporels discriminants. Une chronique est un motif temporelle représentable sous forme de graphe dont les nœuds sont des évènements et les arêtes sont des contraintes temporelles numériques. Le modèle de chronique a été choisi pour son expressivité concernant la dimension temporelle. Les chroniques discriminantes sont, de ce fait, les seuls motifs temporels discriminants représentant numériquement l'information temporelle. Les contributions de cette thèse sont : (i) un algorithme d'extraction de chroniques discriminantes (DCM), (ii) l'étude de l'interprétabilité du modèle de chronique au travers de sa généralisation et (iii) l'application de DCM sur des données de pharmaco-épidémiologie. L'algorithme DCM est dédié à l'extraction de chroniques discriminantes et basé sur l'algorithme d'extraction de règles numériques Ripperk . Utiliser Ripperk permet de tirer avantage de son efficacité et de son heuristique incomplète évitant la génération de motifs redondants. La généralisation de cet algorithme permet de remplacer Ripperk par n'importe quel algorithme de machine learning. Les motifs extraits ne sont donc plus forcément des chroniques mais une forme généralisée de celles-ci. Un algorithme de machine learning plus expressif extrait des chroniques généralisées plus expressives mais impacte négativement leur interprétabilité. Le compromis entre ce gain en expressivité, évalué au travers de la précision de classification, et cette perte d'interprétabilité, est comparé pour plusieurs types de chroniques généralisées. L'intérêt des chroniques discriminantes à représenter des comportements et l'efficacité de DCM est validée sur des données réelles et synthétiques dans le contexte de classification à base de motifs. Des chroniques ont finalement été extraites à partir des données de pharmaco-épidémiologie et présentées aux cliniciens. Ces derniers ont validés l'intérêt de celles-ci pour décrire des comportements d'épidémiologie discriminants. / Data are recorded for a wide range of application and their analysis is a great challenge addressed by many studies. Among these applications, this thesis was motivated by analyzing care pathway data to conduct pharmaco-epidemiological studies. Pharmaco-epidemiology is the study of the uses and effects of healthcare products in well defined populations. The goal is then to automate this study by analyzing data. Within the data analysis approaches, pattern mining approaches extract behavior descriptions, called patterns, characterizing the data. Patterns are often easily interpretable and give insights about hidden behaviors described by the data. In this thesis, we are interested in mining discriminant temporal patterns from temporal sequences, i.e. a list of timestamped events. Temporal patterns represent expressively behaviors through their temporal dimension. Discriminant patterns are suitable adapted for representing behaviors occurring specifically in small subsets of a whole population. Surprisingly, if temporal patterns are essential to describe timestamped data and discriminant patterns are crucial to identify alternative behaviors that differ from mainstream, discriminant temporal patterns received little attention up to now. In this thesis, the model of discriminant chronicles is proposed to address the lack of interest in discriminant temporal pattern mining approaches. A chronicle is a temporal pattern representable as a graph whose nodes are events and vertices are numerical temporal constraints. The chronicle model was choosen because of its high expressiveness when dealing with temporal sequences and also by its unique ability to describe numerically the temporal dimension among other discriminant pattern models. The contribution of this thesis, centered on the discriminant chronicle model, is threefold: (i) a discriminant chronicle model mining algorithm (DCM), (ii) the study of the discriminant chronicle model interpretability through its generalization and (iii) the DCM application on a pharmaco-epidemiology case study. The DCM algorithm is an efficient algorithm dedicated to extract discriminant chronicles and based on the Ripperk numerical rule learning algorithm. Using Ripperk allows to take advantage to its efficiency and its incomplete heuristic dedicated to avoid redundant patterns. The DCM generalization allows to swap Ripperk with alternative machine learning algorithms. The extracted patterns are not chronicles but a generalized form of chronicles. More expressive machine learning algorithms extract more expressive generalized chronicles but impact negatively their interpretability. The trade-off between this expressiveness gain, evaluated by classification accuracy, and this interpretability loss, is compared for several types of generalized chronicles. The interest of the discriminant chronicle model and the DCM efficiency is validated on synthetic and real datasets in pattern-based classification context. Finally, chronicles are extracted from a pharmaco-epidemiology dataset and presented to clinicians who validated them to be interesting to describe epidemiological behaviors.

Les données temporelles sont présentes dans de nombreuses applications utilisant des Systèmes de Gestion de Bases de Données (SGBD). Aussi, la plupart de ces systèmes offrent des types correspondant aux concepts de date et de durée, grâce auxquels il est possible de modéliser des associations temporelles simples, comme par exemple la date de naissance ou l'âge d'une personne. Toutefois, à quelques nuances près, aucun de ces systèmes n'offre des abstractions dédiées à la modélisation d'associations temporelles plus complexes, telles que l'historique du salaire d'un employé, ou la séquence d'annotations attachées à une vidéo. Dès lors, ces associations doivent être codées au travers de constructeurs de type tels que ''liste'' et ''n-uplet'', et la sémantique de ce codage doit être intégrée dans la logique des programmes applicatifs, accroissant par là leur complexité. Pour combler ces lacunes, des extensions dites ''temporelles'' de modèles et de langages pour Bases de Données ont été proposées. Cette thèse analyse et unifie les contributions de ces travaux, dans le but de les intégrer dans une extension temporelle du standard pour SGBD à objets de l'ODMG. Le résultat est une plate-forme logicielle baptisée TEMPOS, fondée sur trois modèles de sophistication croissante : un modèle du temps, un modèle d'historiques et un modèle d'objets et de propriétés temporels. Ce dernier fournit des fonctionnalités facilitant la transformation de bases de données conformes à l'ODMG en des bases de données temporelles. à partir de ces trois modèles, des extensions des langages de spécification de schéma et d'interrogation de l'ODMG sont définies. Enfin, un outil de visualisation basé sur un nouveau paradigme de navigation interactive au travers d'objets temporels est développé. L'ensemble des propositions sont formalisées, implantées au dessus d'un SGBD commercial, et validées par des études de cas.

Dans cette thèse, nous étudions des algorithmes pour le monitoring des traces d’activité à grande échelle. Le monitoring est une aptitude clé dans plusieurs domaines, permettant d’extraire de la valeur des données ou d’améliorer les performances d’un système. Nous explorons d’abord le monitoring de données temporelles. Nous présentons un nouveau type de jointure sur des intervalles, qui inclut des fonctions de score caractérisant le degré de satisfaction de prédicats temporels. Nous étudions ces jointures dans le contexte du batch processing (traitement par lots). Nous formalisons la Ranked Temporal Join (RTJ), une jointure qui combine des collections d’intervalles et retourne les k meilleurs résultats. Nous montrons comment exploiter les propriétés des prédicats temporels et de la sémantique de score associée afin de concevoir TKIJ , une méthode d’évaluation de requête distribuée basée sur Map-Reduce. Nos expériences sur des données synthétiques et réelles montrent que TKIJ est plus performant que les techniques de l’état de l’art et démontre de bonnes performances sur des requêtes RTJ n-aires sur des données temporelles. Nous proposons également une étude préliminaire afin d’étendre nos travaux sur TKIJ au domaine du stream processing (traitement de flots). Nous explorons ensuite le monitoring dans le crowdsourcing (production participative). Nous soutenons la nécessité d’intégrer la motivation des travailleurs dans le processus d’affectation des tâches. Nous proposons d’étudier une approche adaptative, qui évalue la motivation des travailleurs lors de l’exécution des tâches et l’exploite afin d’améliorer l’affectation de tâches qui est réalisée de manière itérative. Nous explorons une première variante nommée Individual Task Assignment (Ita), dans laquelle les tâches sont affectées individuellement, un travailleur à la fois. Nous modélisons Ita et montrons que ce problème est NP-Difficile. Nous proposons trois méthodes d’affectation de tâches qui poursuivent différents objectifs. Nos expériences en ligne étudient l’impact de chaque méthode sur la performance globale dans l’exécution de tâches. Nous observons que différentes stratégies sont dominantes sur les différentes dimensions de performance. En particulier, la méthode affectant des tâches aléatoires et correspondant aux intérêts d’un travailleur donne le meilleur flux d’exécution de tâches. La méthode affectant des tâches correspondant au compromis d’un travailleur entre diversité et niveau de rémunération des tâches donne le meilleur niveau de qualité. Nos expériences confirment l’utilité d’une affectation de tâches adaptative et tenant compte de la motivation. Nous étudions une deuxième variante nommée Holistic Task Assignment (Hta), où les tâches sont affectées à tous les travailleurs disponibles, de manière holistique. Nous modélisons Hta et montrons que ce problème est NP-Difficile et MaxSNP-Difficile. Nous développons des algorithmes d’approximation pour Hta. Nous menons des expériences sur des données synthétiques pour évaluer l’efficacité de nos algorithmes. Nous conduisons également des expériences en ligne et comparons notre approche avec d’autres stratégies non adaptatives. Nous observons que notre approche présente le meilleur compromis sur les différentes dimensions de performance. / In this thesis, we study scalable algorithms for monitoring activity traces. In several domains, monitoring is a key ability to extract value from data and improve a system. This thesis aims to design algorithms for monitoring two kinds of activity traces. First, we investigate temporal data monitoring. We introduce a new kind of interval join, that features scoring functions reflecting the degree of satisfaction of temporal predicates. We study these joins in the context of batch processing: we formalize Ranked Temporal Join (RTJ), that combine collections of intervals and return the k best results. We show how to exploit the nature of temporal predicates and the properties of their associated scored semantics to design TKIJ , an efficient query evaluation approach on a distributed Map-Reduce architecture. Our extensive experiments on synthetic and real datasets show that TKIJ outperforms state-of-the-art competitors and provides very good performance for n-ary RTJ queries on temporal data. We also propose a preliminary study to extend our work on TKIJ to stream processing. Second, we investigate monitoring in crowdsourcing. We advocate the need to incorporate motivation in task assignment. We propose to study an adaptive approach, that captures workers’ motivation during task completion and use it to revise task assignment accordingly across iterations. We study two variants of motivation-aware task assignment: Individual Task Assignment (Ita) and Holistic Task Assignment (Hta). First, we investigate Ita, where we assign tasks to workers individually, one worker at a time. We model Ita and show it is NP-Hard. We design three task assignment strategies that exploit various objectives. Our live experiments study the impact of each strategy on overall performance. We find that different strategies prevail for different performance dimensions. In particular, the strategy that assigns random and relevant tasks offers the best task throughput and the strategy that assigns tasks that best match a worker’s compromise between task diversity and task payment has the best outcome quality. Our experiments confirm the need for adaptive motivation-aware task assignment. Then, we study Hta, where we assign tasks to all available workers, holistically. We model Hta and show it is both NP-Hard and MaxSNP-Hard. We develop efficient approximation algorithms with provable guarantees. We conduct offline experiments to verify the efficiency of our algorithms. We also conduct online experiments with real workers and compare our approach with various non-adaptive assignment strategies. We find that our approach offers the best compromise between performance dimensions thereby assessing the need for adaptability.

L'apprentissage de modèles temporels constitue l'une des grandes problématiques de l'Exploration de Données (Data Mining). Dans cette thèse, nous avons développé un nouveau modèle temporel appelé TITA Rules (Règle associative temporelle basé sur des arbres d'intervalles). Ce modèle permet de décrire des phénomènes ayant un certain degré d'incertitude et/ou d'imprécision. Ce modèle permet entre autres d'exprimer la synchronicité entre évènements, les contraintes temporelles disjonctives et la négation temporelle. De par leur nature, les TITA Rules peuvent êtes utilisées pour effectuer des prédictions avec une grande précision temporel. Nous avons aussi développé un algorithme capable de découvrir et d'extraire de manière efficace des TITA Rules dans de grandes bases de données temporelles. Le cœur de l'algorithme est basé sur des techniques de minimisation d'entropie, de filtrage par Apriori et par des analyses de co-dépendance. Note modèle temporelle et notre algorithme ont été appliqués et évalués sur plusieurs jeux de données issues de phénomènes réels et de phénomènes simulés. La seconde partie de cette thèse à consisté à étudier l'utilisation de notre modèle temporel sur la problématique de la Planification Automatique. Ces travaux ont mené au développement d'un algorithme de planification automatique. L'algorithme prend en entrée un ensemble de TITA Rules décrivant le fonctionnement d'un système quelconque, une description de l'état initial du système, et un but à atteindre. En retour, l'algorithme calcule un plan décrivant la meilleure façon d'atteindre le but donné. Par la nature même des TITA Rules, cet algorithme est capable de gérer l'incertain (probabilités), l'imprécision temporelle, les contraintes temporelles disjonctives, ainsi que les événements exogènes prédictibles mais imprécis.