Título
Diseño de un algoritmo de minería de datos basado en grafos para la tarea de aprendizaje de conceptos
Autor
RIGOBERTO SALOMON FONSECA DELGADO
Colaborador
JESUS ANTONIO GONZALEZ BERNAL (Asesor de tesis)
MARIA DEL PILAR GOMEZ GIL (Asesor de tesis)
IVAN OLMOS PINEDA (Asesor de tesis)
Nivel de Acceso
Acceso Abierto
Materias
Resumen o descripción
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.
Editor
Instituto Nacional de Astrofísica, Óptica y Electrónica
Fecha de publicación
febrero de 2012
Tipo de publicación
Tesis de maestría
Versión de la publicación
Versión aceptada
Recurso de información
Formato
application/pdf
Idioma
Español
Audiencia
Estudiantes
Investigadores
Público en general
Sugerencia de citación
Fonseca-Delgado R.S.
Repositorio Orígen
Repositorio Institucional del INAOE
Descargas
5323