Author: RIGOBERTO SALOMON FONSECA DELGADO

Diseño de un algoritmo de minería de datos basado en grafos para la tarea de aprendizaje de conceptos

RIGOBERTO SALOMON FONSECA DELGADO (2012)

In many domains, it is becoming more common to store data that inherently possess a structure or relational features. Such data are better represented with graphs, which can quite naturally, represent entities, its attributes, and their relationship with other entities. In this thesis, we present a data mining algorithm firstly with an unsupervised phase to divide the data, and another supervised phase that performs data mining generating only possible candidates to find useful patterns in the classification task for structured data. The first task was to design a new spectrum for labeled graphs. This spectrum was implemented in the graph clustering algorithm called Spectral_SOM. The input labeled graphs are transformed in their spectral representation, which are given as input to an SOM network; this network can group these graphs in polynomial time, which is shown through the complexity analysis performed. The second task developed was a data mining graph based algorithm for searching concepts, CL_COBRA. This algorithm uses DFC codes and it was necessary to modify the SICOBRA algorithm to better use the isomorphic subgraphs searching. Finally, the CL_COBRA algorithm was integrated with Spectral_SOM to develop the algorithm KODISSOM_COBRA, result of this thesis. The algorithm was tested with sets of synthetic data and real data. The results show that the patterns found are competitive in the classification task with those found by the concept learning graph based algorithm SubdueCL. The algorithm developed can improve the runtime increasing the minimum support required, but there exists a compromise between runtime and quality of patterns found. An additional outcome is the implementation of an initial framework for working with graphs, with profits of clustering, feature extraction, isomorphism, graphs’ drawing and data mining.

En muchos dominios se está volviendo cada vez más común almacenar datos que poseen inherentemente una estructura o características relacionales. Este tipo de datos se representan mejor con grafos, los cuales pueden, de forma natural, representar entidades, sus atributos, y su relación con otras entidades. En este trabajo de tesis se presenta un algoritmo de minería de datos con una primera fase no supervisada para dividir los datos, y otra fase supervisada que realiza la minería generando solo candidatos posibles para obtener patrones útiles en la tarea de clasificación sobre datos estructurados. La primera parte que se diseñó fue un novedoso espectro para grafos etiquetados. Este espectro se implementó en un algoritmo de agrupamiento de grafos denominado Spectral_SOM. Los grafos etiquetados de entrada se transforman a su representación espectral y se le dan como entrada a una red SOM capaz de agrupar estos grafos en tiempo polinomial, lo que se muestra con el análisis de complejidad realizado. La segunda parte que se desarrolló es un algoritmo de minería de datos basado en grafos para buscar conceptos, CL_COBRA. Este algoritmo utiliza códigos DFC y requirió modificar el algoritmo SICOBRA para aprovechar en mejor manera la búsqueda de subgrafos isomorfos. Finalmente, se integró Spectral_SOM con CL_COBRA para obtener el algoritmo KODISSOM_COBRA, resultado de esta tesis. El algoritmo fue evaluado con conjuntos de datos sintéticos y datos reales. Los resultados muestran que los patrones encontrados son competitivos en la tarea de clasificación con los encontrados por el algoritmo de aprendizaje de conceptos basado en grafos SubdueCL. El algoritmo desarrollado puede mejorar su tiempo de ejecución aumentando el soporte mínimo requerido, sin embargo existe un compromiso entre tiempo de ejecución y calidad de patrones encontrados. Un resultado adicional es la implementación de un marco de trabajo inicial para manejar grafos, con utilidades de agrupamiento, extracción de características, isomorfismo, dibujado de grafos y minería de datos.

Master thesis

Data mining Neural nets Graph theory CIENCIAS FÍSICO MATEMÁTICAS Y CIENCIAS DE LA TIERRA MATEMÁTICAS CIENCIA DE LOS ORDENADORES

Meta-aprendizaje auto-organizado temporal para predicción a largo plazo de series de tiempo caóticas

RIGOBERTO SALOMON FONSECA DELGADO (2017)

Long-term prediction of time series from chaotic systems is a difficult task but required in various fields such as economics, medicine, government, etc. In recent years, several studies have turned their attention to reuse prior knowledge with the aim of combining models and improving prediction. The process of learning from previous results is called meta-learning. On the context of model combination, the meta-learning strategy lets to automatically generate an expert, able to recommend an appropriate combination of models to predict a time series in particular. However, the process of meta-learning in time series imposes nontrivial challenges such as: analyzing model behavior with time series data, look for models that can be combined with each series and even generate new methods of meta-learning those consider variations of model performance over time. This research focuses on the problem of meta-learning of model combination, using self-organization and an automatic analysis of the behavior of the models. The goal is to improve the accuracy on long-term prediction achieved by state of the art algorithms in chaotic time series. The main contribution of this work is a new method, based on meta-features and self-organized maps neural networks, capable of generating combinations of prediction models considering the accuracy of the models and their diversity of behavior over time. The developed method was compared with other methods of the state of the art, and validated using synthetic series and series obtained from real applications, that have a chaotic and non-chaotic behavior.

La predicción a largo plazo de series de tiempo de sistemas caóticos es una tarea difícil pero requerida en diversos dominios como economía, medicina, gobierno, etc. En los últimos años, varias investigaciones han puesto su atención en reutilizar conocimiento previo a fin de combinar modelos y mejorar la predicción. El proceso de aprender a partir de resultados previos es denominado meta-aprendizaje. En el contexto de combinación de modelos, la estrategia de meta-aprendizaje permite generar automáticamente un experto, capaz de recomendar una combinación de modelos apropiada para predecir una serie de tiempo en particular. Sin embargo, el proceso de meta-aprendizaje en series de tiempo impone retos no triviales tales como: analizar el comportamiento de los modelos con los datos, buscar modelos que puedan combinarse adecuadamente para cada serie, e incluso generar nuevos métodos de meta-aprendizaje, que consideren las variaciones de desempeño de los modelos en el tiempo. Esta investigación se centra en el problema de meta-aprendizaje de combinación de modelos, utilizando auto-organización y un análisis automático del comportamiento de los modelos. La meta es mejorar la exactitud en predicción a largo plazo alcanzada por los algoritmos del estado del arte en series de tiempo caóticas. La principal contribución de este trabajo es un nuevo método, basado en meta-características y en las redes neuronales de mapas auto-organizados, capaz de generar combinaciones de modelos de predicción considerando la exactitud de los modelos y su diversidad de comportamiento en el tiempo. El método desarrollado fue comparado con otros métodos del estado del arte, y validado utilizando series sintéticas y series obtenidas de aplicaciones reales, que presentan comportamientos tanto caóticos como no caóticos.

Doctoral thesis

Time series Meta-learning Forecasting Self-organijing maps Neural networks CIENCIAS FÍSICO MATEMÁTICAS Y CIENCIAS DE LA TIERRA MATEMÁTICAS CIENCIA DE LOS ORDENADORES