Dans un premier temps, nous étudions l'échantillonnage de flux de trajectoires. Garder l'intégralité des trajectoires capturées par les terminaux de géo-localisation modernes peut s'avérer coûteux en espace de stockage et en temps de calcul. L'élaboration de techniques d'échantillonnage adaptées devient primordiale afin de réduire la taille des données en supprimant certaines positions tout en veillant à préserver le maximum des caractéristiques spatiotemporelles des trajectoires originales. Dans le contexte de flux de données, ces techniques doivent en plus être exécutées "à la volée" et s'adapter au caractère continu et éphémère des données. A cet effet, nous proposons l'algorithme STSS (spatiotemporal stream sampling) qui bénéficie d'une faible complexité temporelle et qui garantit une borne supérieure pour les erreurs d’échantillonnage. Nous montrons les performances de notre proposition en la comparant à d'autres approches existantes. Nous étudions également le problème de la classification non supervisée de trajectoires contraintes par un réseau routier. Nous proposons trois approches pour traiter ce cas. La première approche se focalise sur la découverte de groupes de trajectoires ayant parcouru les mêmes parties du réseau routier. La deuxième approche vise à grouper des segments routiers visités très fréquemment par les mêmes trajectoires. La troisième approche combine les deux aspects afin d'effectuer un co-clustering simultané des trajectoires et des segments. Nous démontrons comment ces approches peuvent servir à caractériser le trafic et les dynamiques de mouvement dans le réseau routier et réalisons des études expérimentales afin d'évaluer leurs performances. / In this thesis, we explore two problems related to managing and mining moving object trajectories. First, we study the problem of sampling trajectory data streams. Storing the entirety of the trajectories provided by modern location-aware devices can entail severe storage and processing overheads. Therefore, adapted sampling techniques are necessary in order to discard unneeded positions and reduce the size of the trajectories while still preserving their key spatiotemporal features. In streaming environments, this process needs to be conducted "on-the-fly" since the data are transient and arrive continuously. To this end, we introduce a new sampling algorithm called spatiotemporal stream sampling (STSS). This algorithm is computationally-efficient and guarantees an upper bound for the approximation error introduced during the sampling process. Experimental results show that stss achieves good performances and can compete with more sophisticated and costly approaches. The second problem we study is clustering trajectory data in road network environments. We present three approaches to clustering such data: the first approach discovers clusters of trajectories that traveled along the same parts of the road network; the second approach is segment-oriented and aims to group together road segments based on trajectories that they have in common; the third approach combines both aspects and simultaneously clusters trajectories and road segments. We show how these approaches can be used to reveal useful knowledge about flow dynamics and characterize traffic in road networks. We also provide experimental results where we evaluate the performances of our propositions.

Dans cette thèse, nous abordons les problèmes bien connus de clustering et de fouille de règles d’association. Notre première contribution introduit un nouveau cadre de clustering, où les objets complexes sont décrits par des formules propositionnelles. Premièrement, nous adaptons les deux fameux algorithmes de clustering, à savoir, le k-means et l’algorithme hiérarchique ascendant, pour traiter ce type d’objets complexes. Deuxièmement, nous introduisons un nouvel algorithme hiérarchique descendant pour le clustering des objets représentés explicitement par des ensembles de modèles. Enfin, nous proposons un encodage basé sur la satisfiabilité propositionnelle du problème de clustering des formules propositionnelles sans avoir besoin d’une représentation explicite de leurs modèles. Dans une seconde contribution, nous proposons une nouvelle approche basée sur la satisfiabilité pour extraire les règles d’association en une seule étape. La tâche est modélisée comme une formule propositionnelle dont les modèles correspondent aux règles à extraire. Pour montrer la flexibilité de notre cadre, nous abordons également d’autres variantes, à savoir, l’extraction des règles d’association fermées, minimales non redondantes, les plus générales et les indirectes. Les expérimentations sur de nombreux jeux de données montrent que sur la majorité des tâches de fouille de règles d’association considérées, notre approche déclarative réalise de meilleures performances que les méthodes spécialisées. / In this thesis, We adress the well-known clustering and association rules mining problems. Our first contribution introduces a new clustering framework, where complex objects are described by propositional formulas. First, we extend the two well-known k-means and hierarchical agglomerative clustering techniques to deal with these complex objects. Second, we introduce a new divisive algorithm for clustering objects represented explicitly by sets of models. Finally, we propose a propositional satisfiability based encoding of the problem of clustering propositional formulas without the need for an explicit representation of their models. In a second contribution, we propose a new propositional satisfiability based approach to mine association rules in a single step. The task is modeled as a propositional formula whose models correspond to the rules to be mined. To highlight the flexibility of our proposed framework, we also address other variants, namely the closed, minimal non-redundant, most general and indirect association rules mining tasks. Experiments on many datasets show that on the majority of the considered association rules mining tasks, our declarative approach achieves better performance than the state-of-the-art specialized techniques.

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.

Cette thèse se situe à l'interface de la statistique et de la fouille de données. Elle est composée de trois parties indépendantes. Dans la première, nous cherchons à estimer l'ordre (le nombre d'États cachés) d'un modèle de Markov caché dont la distribution d'émission appartient à la famille exponentielle. Nous nous plaçons dans le cas où aucune borne supérieure sur cet ordre n'est connue a priori. Nous définissons deux estimateurs pénalisés pour cet ordre, l'un basé sur le maximum de vraisemblance et l'autre sur une statistique de mélange bayésien. Nous montrons la consistance forte de ces estimateurs. Dans la deuxième partie, nous extrayons des motifs séquentiels dont la fréquence est exceptionnellement élevée par rapport à un modèle de Markov. L'approche consiste à dénombrer dynamiquement toutes les positions possibles d'un motif au sein d'une séquence. Puis la fréquence observée est comparée à la fréquence attendue à l'aide d'un test binomial. Une procédure est utilisée pour tenir compte des tests multiples. Des expérimentations sont menées sur des bases synthétiques et des séquences de protéines. Enfin, dans la troisième partie, nous nous intéressons au calcul de l'estimateur à noyau de la densité. Les observations sont regroupées dans des structures hiérarchiques d'arbres binaires. Les calculs sont réalisés sur les nœuds, plutôt que sur les points, pour une plus grande efficacité. Nous effectuons le calcul sur un Échantillon de points de chaque nœud, au lieu de sa totalité, en utilisant des inégalités de concentration non-paramétriques pour contrôler l'erreur. Puis, nous proposons un nouveau parcours de l'arbre pour effectuer ces échantillonnages sur un nombre réduit de nœuds. Nous testons notre approche sur des jeux de données synthétiques. / This Ph.D thesis lies at the interface of statistics and data mining. It contains three independent parts. In the first one, we aim at estimating the order (the number of hidden states) of a Hidden Markov Model, whose emission distribution belongs to the exponential family. We suppose that no upper bound is known on this order. We define two penalised estimators for this order, one based on the maximum likelihood, an the other on a bayesian mixture statistic. We prove that both estimators are strongly consistent. In the second part, we extract sequential patterns of exceptional frequency given a Markov model. We first dynamically enumerate all the possible occurences of a pattern in a sequence. Then, the observed frequency is compared to the expected frequency using a binomial test. Multiple testing is taken into account. Experiments are led on synthetic databases and protein sequences. Finally, in the third chapter, we are interested in kernel density estimation. The observations are gathered in hierarchical structures called binary trees. Computations are done on nodes of trees, rather than on raw observations, for greater efficiency. We only take into account samples on each node, instead of all the observations, using a non-parametric concentration inequality to control the error. We also propose to only browse some parts of the tree. We test our approach on synthetic datasets.

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal.

Le regroupement d'objets, dans un cadre non-supervisé, est une tâche importante et difficile en apprentissage. Ce processus intervient dans des contextes variés tels que la découverte de connaissances, la simplification dans le représentation ou la description d'un ensemble de données.<br /><br />Nous proposons, dans cette étude, l'algorithme de clustering PoBOC permettant de structurer un ensemble d'objets en classes non-disjointes. Nous utilisons cette méthode de clustering comme outil de traitement dans deux applications très différentes.<br /><br />- En apprentissage supervisé, l'organisation préalable des instances apporte une connaissance utile pour la tâche d'induction de règles propositionnelles et logiques.<br /><br />- En Recherche d'Information, les ambiguïtés et subtilités de la langue naturelle induisent naturellement des recouvrements entre thématiques.<br /><br />Dans ces deux domaines de recherche, l'intérêt d'organiser les objets en classes non-disjointes est confirmé par les études expérimentales adaptées.

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.

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Nous nous intéressons au problème de la prédiction de l’occurrence d’une baisse de prix pour fournir un conseil à l’achat immédiat ou reporté d’un voyage sur un site web de comparaison des prix. La méthodologie proposée repose sur l’apprentissage statistique d’un modèle d’évolution du prix à partir de l’information conjointe d’attributs du voyage considéré et d’observations passées du prix et de la "popularité" celui-ci. L’originalité principale consiste à représenter l’évolution des prix par le processus ponctuel inhomogène des sauts de celui-ci. A partir d’une base de données constituée par liligo.com, nous mettons en oeuvre une méthode d’apprentissage d’un modèle d’évolution des prix. Ce modèle permet de fournir un prédicteur de l’occurrence d’une baisse du prix sur une période future donnée et donc de prodiguer un conseil d’achat ou d’attente au client. / The goal of this paper is to consider the design of decision-making tools in the context of varying travel prices from the customer’s perspective. Based on vast streams of heterogeneous historical data collected through the internet, we describe here two approaches to forecasting travel price changes at a given horizon, taking as input variables a list of descriptive characteristics of the flight, together with possible features of the past evolution of the related price series. Though heterogeneous in many respects ( e.g. sampling, scale), the collection of historical prices series is here represented in a unified manner, by marked point processes (MPP). State-of-the-art supervised learning algorithms, possibly combined with a preliminary clustering stage, grouping flights whose related price series exhibit similar behavior, can be next used in order to help the customer to decide when to purchase her/his ticket.

Le développement du Web 2.0 a donné lieu à la production d'une grande quantité de discussions en ligne. La fouille et l'extraction de données de qualité de ces discussions en ligne sont importantes dans de nombreux domaines (industrie, marketing) et particulièrement pour toutes les applications de commerce électronique. Les discussions de ce type contiennent des opinions et des croyances de personnes et cela explique l'intérêt de développer des outils d'analyse efficaces pour ces discussions. L'objectif de cette thèse est de définir un modèle qui représente les discussions en ligne et facilite leur analyse. Nous proposons un modèle basé sur des graphes. Les sommets du graphe représentent les objets de type message. Chaque objet de type message contient des informations comme son contenu, son auteur, l'orientation de l'opinion qui y été exprimée et la date où il a été posté. Les liens parmi les objets message montrent une relation de type "répondre à". En d'autres termes, ils montrent quels objets répondent à quoi, conséquence directe de la structure de la discussion en ligne. Avec ce nouveau modèle, nous proposons un certain nombre de mesures qui guident la fouille au sein de la discussion et permettent d'extraire des informations pertinentes. Il existe des mesures centrées sur l'analyse de l'opinion qui traitent de l'évolution de l'opinion au sein de la discussion. Nous définissons également des mesures centrées sur le temps, qui exploitent la dimension temporelle du modèle, alors que les mesures centrées sur le sujet peuvent être utilisées pour mesurer la présence de sujets dans une discussion. La présence de l'utilisateur dans des discussions en ligne peut être exploitée soit par les techniques des réseaux sociaux, soit à travers notre nouveau modèle qui inclut la connaissance des auteurs de chaque objet message. De plus, une liste de messages clés est recommandée à l'utilisateur pour permettre une participation plus efficace au sein de la discussion.