Time Sequence Summarization: Theory and Applications
Résumé
Domains such as medicine, the WWW, business or nance generate and store on a daily basis massive amounts of data. This data is represented as a collection of time sequences of events where each event is described as a set of descriptors taken from various descriptive domains and associated to a time of occurrence. These archives represent valuable sources of insight for analysts to browse, analyze and discover golden nuggets of knowledge. For instance, biologists could discover disease risk factors by analyzing patient history, web content producers and marketing people are interested in proling client behaviors, traders investigate nancial data for understanding global trends or anticipating market moves. However, these applications require mining massive sequences, e.g., nance can generate millions of events daily, where the variability of event descriptors could be very high, since descriptors could be extracted from textual contents. For these reasons, discovering golden nuggets of knowledge for such domains with conventional data mining techniques is a challenging task. Recent studies show that data mining methods might need to operate on derived forms of the data, including aggregate values, previous mining results or summaries. Knowledge extracted in such a way is called Higher Order Knowledge. In this thesis work, we propose to address this challenge and we dene the concept of Time sequence summarization whose purpose is to support chronology-dependent applications to scale on very large data sources. Time sequence summarization uses the content and temporal information of events to generate a more concise, yet informative enough, time sequence that can seamlessly be substituted for the original time sequence in the desired application. We propose a user-oriented approach called TSaR built on a 3-step process: Generalization, grouping and concept formation. TSaR uses background knowledge in the form of taxonomies to represent event descriptors at a higher level of abstraction. A temporal parameter controls the grouping process and only allows events close on the timeline to be gathered. Also, we propose to make the time sequence summarization process parameter-free. For this purpose, we reformulate the summarization problem into a novel clustering problem. The originality of this clustering problem relies on the specicity of the objective function to optimize. Indeed, the objective function takes into account both the content and the proximity of events on the timeline. We present two greedy approaches calledG-BUSS and GRASS to build a solution to this problem. Finally, we explore and analyze how time sequence summaries contribute to discovering Higher Order Knowledge. We analytically characterize the higher order patterns discovered from summaries and devise a methodology that uses the patterns discovered to uncover even more rened patterns. We evaluate and validate our summarization algorithms and our methodology by an extensive set of experiments on real world data extracted from Reuters's nancial news archives.
Les domaines de la médecine, du web, du commerce ou de la nance génèrent et stockent de grandes masses d'information sous la forme de séquences d'événements. Ces archives représentent des sources d'information très riches pour des analystes avides d'y découvrir des perles de connaissance. Par exemple, les biologistes cherchent à découvrir les facteurs de risque d'une maladie en analysant l'historique des patients, les producteurs de contenu web et les bureaux de marketing examinent les habitudes de consommation des clients et les opérateurs boursiers suivent les évolutions du marché pour mieux l'anticiper. Cependant, ces applications requièrent l'exploration de séquences d'événements très volumineuses, par exemple, la nance génère quotidiennement des millions d'événements, où les événements peuvent être décrits par des termes extraits de riches contenus textuels. La variabilité des descripteurs peut alors être très grande. De ce fait, découvrir des connaissances non triviales à l'aide d'approches classiques de fouille de données dans ces sources d'information prolixes est un problème dicile. Une étude récente montre que les approches classiques de fouille de données peuvent tirer prot de formes condensées de ces données, telles que des résultats d'agrégation ou encore des résumés. La connaissance ainsi extraite est qualiée de connaissance d'ordre supérieur. À partir de ce constat, nous présentons dans ces travaux le concept de résumé de séquence d'événements dont le but est d'amener les applications dépendantes du temps à gagner un facteur d'échelle sur de grandes masses de données. Un résumé s'obtient en transformant une séquence d'événements où les événements sont ordonnés chronologiquement. Chaque événement est précisément décrit par un ensemble ni de descripteurs symboliques. Le résumé produit est alors une séquence d'événements, plus concise que la séquence initiale, et pouvant s'y substituer dans les applications. Nous proposons une première méthode de construction guidée par l'utilisateur, appelée TSaR. Il s'agit d'un processus en trois phases : i) une généralisation, ii) un regroupement et iii) une formation de concepts. TSaR utilise des connaissances de domaine exprimées sous forme de taxonomies pour généraliser les descripteurs d'événements. Une fenêtre temporelle est donnée pour contrôler le processus de regroupement selon la proximité temporelle des événements. Dans un second temps, pour rendre le processus de résumé autonome, c'est- à-dire sans paramétrage, nous proposons une redénition du problème de résumé en un nouveau problème de classication. L'originalité de ce problème de classication tient au fait que la fonction objective à optimiser dépend simultanément du contenu des événements et de leur proximité dans le temps. Nous proposons deux algorithmes gloutons appelés G-BUSS et GRASS pour répondre à ce problème. Enn, nous explorons et analysons l'aptitude des résumés de séquences d'événements à contribuer à l'extraction de motifs séquentiels d'ordre supérieur. Nous analysons les caractéristiques des motifs fréquents extraits des résumés et proposons une méthodologie qui s'appuie sur ces motifs pour en découvrir d'autres, à granularité plus ne. Nous évaluons et validons nos approches de résumé et notre méthodologie par un ensemble d'expériences sur un jeu de données réelles extraites des archives d'actualités nancières produites par Reuters.
Fichier principal
_These_Quang-Khai_Pham_RA_sumA_de_sA_quences_d_A_vA_nements-thA_orie_et_applications.pdf (8.6 Mo)
Télécharger le fichier