Classification non supervise à deux niveaux guidée par le voisinage et la densité
Institution:
Paris 13Disciplines:
Directors:
Abstract EN:
The research outlined in this thesis concerns the development of approaches based on self-organizing maps (SOM) for the discovery and the monitoring of class structures in the data through unsupervised learning. We propose a simultaneously two levels clustering method. This method is based on the estimate, from the data, of connectivity and density values of the SOM's prototypes. The number of clusters is detected automatically. Moreover, the complexity is linear with the number of data. We show that it is relatively simple and efficient to adapt these algorithms to variants of the SOM in order to obtain a versatile method capable of analyzing different data types. We also propose an improvement of the quality of the SOM using the connectivity values during the learning of the prototypes. We describe a new method of condensed description of the data distribution and a heuristic measure of similarity between these models. These algorithms are based on an estimate of the underlying density for learning a modified SOM. In addition, we combine the clustering algorithm to measure similarity between distributions for the analysis of evolutionary data, and we propose an algorithm for monitoring data stream. Finally, we present two applications for tracking individuals in a RFID device. The first application is a study of the behavior of a colony of ants while moving. The second application, require tracking of customers in a store.
Abstract FR:
Le travail de recherche exposé dans cette thèse concerne le développement d'approches à base de Cartes Auto-Organisatrices (SOM) pour la découverte et le suivi de structures de classes dans les données par apprentissage non supervisé. Nous proposons des méthodes de classification à deux niveaux simultanés qui se basent sur l'estimation, à partir des données, de valeurs de connectivité et de densité des prototypes de la SOM. Le nombre de clusters est détecté automatiquement et la complexité est linéaire selon le nombre de données. Nous montrons aussi qu’il est relativement simple et efficace d’adapter ces algorithmes aux variantes de l’algorithme SOM, de façon à obtenir une méthode très polyvalente capable par exemple d’analyser différents types de données. Nous proposons en outre une amélioration de la qualité de la SOM en utilisant les valeurs de connectivité lors de l'apprentissage des prototypes. Nous décrivons une nouvelle méthode de description condensée de la distribution des données, ainsi qu’une mesure heuristique de similarité entre ces modèles. Par ailleurs, nous proposons un algorithme de suivi des données d'un flux. Ces algorithmes se basent sur une estimation de la densité sous-jacente des données pendant l'apprentissage d'une SOM modifiée. Enfin, nous présentons deux applications réelles pour le suivi d'individus dans un dispositif RFID. La première application est une étude du comportement d'une colonie de fourmis pendant un déménagement. La deuxième est une étude commerciale nécessitant le suivi de clients dans un magasin pendant leurs achats.