Análisis cluster para problemas con estructuras temporales. Aplicaciones al control de redes tráfico
Estado Finalizada
Trabajo fin de master y Tesis doctoral
Director UCLM
Resumen

El análisis clúster es una colección de técnicas exploratorias de datos que persigue la realización de una taxonomía de un conjunto de objetos. Estas técnicas se han ido desarrollando durante décadas y han encontrado múltiples campos de aplicación que van desde la biología a las ciencias sociales pasando por las ciencias de la computación. El objetivo de esta tesis es el desarrollo y validación de métodos del análisis clúster para dominios de aplicación en los que la naturaleza temporal delas observaciones sea esencial. Los dos temas que articulan esta tesis doctoral son los llamados métodos clústeres particionales, tomando al algoritmo delas k - medias como su representante y los espacios de Hilbert con núcleos reproductores. El primero nos ha permitido considerar el análisis clúster como un caso especial de problema de optimización y el segundo abordar este problema en espacios vectoriales de dimensión infinita. Esta tesis consta de un capítulo 1 introductorio, los capítulos 2, 3 y 4 son de investigación y un capítulo final que recoge las conclusiones y futuras líneas de investigación. En el capítulo 2 se estudia el problema de la segmentación de series temporales mediante técnicas de análisis clúster con restricciones temporales. El objetivo perseguido es encontrar intervalos temporales (clusters) en los que los datos sean lo más homogéneos posible respecto a un modelo estadístico dado. En esta tesis se ha formulado el análisis clúster con restricciones temporales como un problema de optimización binivel. Se ha propuesto una técnica híbrida, basada en combinar la optimización del enjambre de partículas con el método simplex de Nelder-Mead, para su resolución. Este método se ha denominado PSO-NM. Este capítulo consta de una colección de experimentos numéricos en los que se ha testado, sobre señales sintéticas simuladas, la calidad de las soluciones obtenidas con la metodología propuesta frente a las encontradas con métodos clusters borrosos. También se ha desarrollado una aplicación novedosa en el campo del análisis de supervivencia. Se ha concluido esta sección estudiando el rendimiento computacional del PSO-NM sobre un problema de identificación de líneas de texto. En el capítulo 3 se analiza el algoritmo de las K - medias para datos funcionales. Se han considerado dos métricas, denominadas dvn y d?, basadas en proyecciones en espacios de Hilbert con núcleos reproductores (RKHS) y la teoría de regularización de Tikhonov. Se ha mostrado que ambas métricas son equivalentes, sin embargo, conducen a dos estrategias diferentes de reducción de la dimensionalidad del problema. En el caso de dvnla estrategia más adecuada es la proyección aleatoria de Johnson-Lindenstrauss mientras que para d?se basa en métodos espectrales. Un aspecto clave que se ha analizado es el efecto del muestreo de las funciones empíricas en el rendimiento del algoritmo de las K - medias. Se ha construido un ejemplo ex professo para mostrar numéricamente que si el muestreo no es uniforme en el dominio de las funciones, un algoritmo de las K - medias que ignore la naturaleza funcional de los datos puede reducir drásticamente su rendimiento. Se ha mostrado numéricamente que para los ejemplos considerados con muestreo uniforme el rendimiento del algoritmo original de las K - medias es similar a los basados en proyecciones pero con un coste computacional muy superior, debido a que éste no considera estrategias de reducción de la dimensionalidad. Se ha ilustrado esta metodología con un problema real de señales de radar para analizar qué problemática debe afrontar el algoritmo de las K - medias para datos funcionales. En el capítulo 4 se han analizado dos problemas de control del tráfico mediante análisis cluster. Estos problemas surgen en el diseño de un Sistema Inteligente de Transporte. El primer problema establece qué conjunto de patrones de tráfico se registran en una determinada red urbana. El segundo problema busca los denominados TODs (Time-Of-Day intervals) para cada patrón de demanda, esto es, intervalos temporales en los que la demanda de tráfico sea aproximadamente estacionaria. En el primer problema se ha propuesto una transformación de los datos para poder recoger la correlación entre los diferentes arcos aforados de la red. Esta operación convierte el conjunto de datos iniciales (series temporales) en un conjunto de matrices sobre el que se ha aplicado el algoritmo de las K - medias con distancias espectrales. Se ha realizado un estudio numérico mediante modelos de simulación de tráfico, comprobando que estos métodos son capaces de recuperar los patrones originales de demanda.