Etude et analyse des données temporelles par un processus à base d'HMMs.

Abstract

L'extraction des connaissances a prouvé son sucée dans différents domaines d'applications comme le domaine médical, spatial, économique, etc. En raison de la disponibilité de quantités énormes de données, ceci devient un problème critique pour extraire des connaissances de manière automatique. Le traitement de ces grandes masses de données a été principalement orienté sur la classification ou le clustering. Un des problèmes qui n'est pas des moindres est le traitement de données avec des dépendances temporelles et spatiales. Cependant, la plupart des techniques d'exploration et d'analyse ont tendance à traiter les données temporelles comme une collection non ordonnée d'événements, ignorant ainsi la dimension temporelle de ces données. De plus, peu de théories et de méthodes générales d'analyse et de construction de modèles pour le traitement de données temporelles sont connues. Les modèles de Markov cachés (HMMs) constituent une des meilleures techniques pour l'étude de telles données. Les HMMs sont basés sur les théories de probabilités et statistiques. Leur principal avantage est l'existence d'algorithmes d'apprentissage non supervisé, comme Forward, Backpropagation, Viterbi, et Baum Walch, qui permettent d'estimer les paramètres du modèle de l'ensemble de données d'observations et du modèle initial. Nous proposons une méthodologie de clustering pour l'analyse des séquences temporelles à base de modèles de Markov cachés (HMM), utilisant le critère de vraisemblance pour définir une fonction objective dans le but de déterminer le nombre optimal de clusters ainsi que leurs structures cohérentes. L'algorithme se résume en quatre étapes ; i) la recherche du nombre optimal de clusters, ii) la recherche de structure cohérente de chaque cluster, iii) distribution d'objet aux clusters, iv) configuration des paramètres de chaque cluster. Cette étude est validée par des résultats expérimentaux montrant l'efficacité de notre méthodologie.\\ Mots clés: Données temporelles, HMM, Clustering, Viterbi, la vraisemblance.

Abstract: Extraction of knowledge has proven its success in different domains such as medical and space applications, economics, etc. Due to the availability of large quantities of data, this becomes a critical issue for extracting knowledge automatically. Moreover most of these datasets tend to contain temporal and/or spatial dimensions, and until now they are treated as unordered collections of events, ignoring the temporal aspect of the data. Hidden Markov models (HMMs) represent one of the best techniques for studying such data. HMMs are based on probabilities and statistics. Their main advantage is the existence of non-supervised learning algorithms such as feed-forward and Back-propagation, allowing a proper estimation of the parameters of all observations and building models of the original data. We propose a methodology for clustering temporal sequences based on hidden Markov Model (HMM). We use likelihood criteria to define an objective function and determine the optimal number of clusters as well as their coherent structures. The algorithm consists of four steps; 1) search for the optimal number of clusters, 2) find coherent structure of each cluster 3) distribute the objects over the clusters, 4) configure settings for each cluster. This study is validated by experimental datasets demonstrating the efficiency of our methodology. Keywords: temporal data, HMM, Clustering.