Agrupamiento espectral de datos dinamicos

Abstract

El análisis de datos dinámicos o variantes en el tiempo es un tema de gran interés actual para la comunidad científica, especialmente, en los campos de reconocimiento de patrones y aprendizaje de máquina. Existe un amplio espectro de aplicaciones en donde el análisis de datos dinámicos toma lugar, tales como el análisis de video, la identificación de movimiento, la segmentación de movimientos de personas y el seguimiento de naves aéreas, entre otras. Una de las alternativas para desarrollar métodos dinámicos es el análisis matricial espectral. Las técnicas espectrales, principalmente aquellas basadas en kernels, han demostrado su alta aplicabilidad en diversos aspectos del reconocimiento de patrones y aprendizaje de máquina, incluso cuando los datos son variantes en el tiempo, tales como la estimación del número de grupos, agrupamiento y clasificación. La mayoría de los métodos espectrales han sido diseñados para el análisis de datos estáticos, descartando la información temporal, es decir, omitiendo el comportamiento y la evolución de los datos a lo largo del tiempo. En el estado del arte se encuentran algunos trabajos que consideran el efecto de la variación en el tiempo,sin embargo, el diseño de un método que permita seguir la dinámica de los datos y agrupar los mismos en ambientes de tiempo real, con alta fidelidad y precisión, es aún un problema abierto. En este trabajo de tesis se presenta un método de agrupamiento espectral basado en kernels diseñado a partir de un enfoque primal-dual con el fin de realizar el proceso de agrupamiento considerando la información dinámica, es decir, los cambios de secuencia de los datos a lo largo del tiempo. Para este propósito, se plantea un esquema de agrupamiento que consiste en la extensión de una formulación primal-dual al análisis de datos dinámicos a través de un kernel dinámico. El esquema se basa en un aprendizaje de múltiples kernels (MKL) y se denomina dynamic kernel spectral clustering (DKSC). El método DKSC usa como modelo de MKL una combinación lineal de matrices kernel. Las matrices kernel se calculan a partir de una secuencia de datos representada por un conjunto de matrices de datos. Subsecuentemente, se obtiene una matriz acumulada de kernel de tal forma que los coeficientes o factores de ponderación del modelo son considerados como valores de evaluación de cada muestra del conjunto de datos o frame. Dicha evaluación se hace a partir de un novedoso método de tracking que se basa en la descomposición espectral de una matriz kernel generalizada. Finalmente, para la obtención de las asignaciones de grupo resultantes, los datos son agrupados usando la matriz acumulada como matriz kernel.

Abstract : The analysis of dynamic or time-varying data has emerged as an issue of great interest taking increasingly an important place in scientific community, especially in automation, pattern recognition and machine learning. There exists a broad range of important applications such as video analysis, motion identification, segmentation of human motion and airplane tracking, among others. Spectral matrix analysis is one of the approaches to address this issue. Spectral techniques, mainly those based on kernels, have proved to be a suitable tool in several aspects of interest in pattern recognition and machine learning even when data are time-varying, such as the estimation of the number of clusters, clustering and classification. Most of spectral clustering approaches have been designed for analyzing static data, discarding the temporal information, i.e. the evolutionary behavior along time. Some works have been developed to deal with the time varying effect. Nonetheless, an approach able to accurately track and cluster time-varying data in real time applications remains an open issue. This thesis describes the design of a kernel-based dynamic spectral clustering using a primaldual approach so as to carry out the grouping task involving the dynamic information, that is to say, the changes of data frames along time. To this end, a dynamic kernel framework aimed to extend a clustering primal formulation to dynamic data analysis is introduced. Such framework is founded on a multiple kernel learning (MKL) approach. Proposed clustering approach, named dynamic kernel spectral clustering (DKSC) uses a linear combination of kernels matrices as a MKL model. Kernel matrices are computed from an input frame sequence represented by data matrices. Then, a cumulative kernel is obtained, being the model coefficients or weighting factors obtained by ranking each sample contained in the frame. Such ranking corresponds to a novel tracking approach that takes advantages of the spectral decomposition of a generalized kernel matrix. Finally, to get the resultant cluster assignments, data are clustered using the cumulative kernel matrix. Experiments are done over real databases (human motion and moon covered by clouds)as well as artificial data (moving-Gaussian clouds). As a main result, proposed spectral clustering method for dynamic data proved to be able for grouping underlying events and movements and detecting hidden objects as well. The proposed approach may represent a contribution to the pattern recognition field, mainly, for solving problems involving dynamic information aimed to either tracking or clustering of data.