Please use this identifier to cite or link to this item: http://inaoe.repositorioinstitucional.mx/jspui/handle/1009/507
Minería de subgrafos conexos frecuentes en colecciones de grafos etiquetados
ANDRÉS GAGO ALONSO
JESUS ARIEL CARRAZCO OCHOA
Acceso Abierto
Atribución-NoComercial-SinDerivadas
Data mining
Graph theory
Algorithm theory
Frequent connected subgraph (FCS) mining is an interesting problem in data mining with wide applications in real life. Examples of such applications appear in knowledge discovery from several sources as: chemical compound databases, XML documents, citation networks, biological networks, etc. For solving the FCS mining problem, several algorithms have been proposed to find all frequent connected subgraphs in collections of labeled graphs. The best performances in FCS mining are achieved by pattern growth-based algorithms. However, duplicate detection and support counting, during the mining process, are still a challenge in FCS mining. The four algorithms proposed in this thesis are focused on solving these subtasks in an efficient way regarding the reported methods. Specifically, novel theoretical properties of the candidate graph codifications are introduced. These properties allow to reduce the computational cost of duplicate detection in the practice. Moreover, a new data structure for indexing the graph collection is also introduced. This structure allows to accelerate support counting and candidate enumeration. On the other hand, there are some applications where analyzing all FCS is impractical. A way to face this problem is by finding only the closed FCS. Moreover, using the closed FCS set allows to reconstruct the whole set of FCS.
La minería de subgrafos conexos frecuentes (SCF) en colecciones de grafos etiquetados se ha convertido en una importante línea de investigación, dentro de la minería de datos, por sus diversas aplicaciones. Ejemplos de tales aplicaciones son el procesamiento de bases de datos de componentes químicas, documentos XML, redes de citas, redes sociales, redes biológicas, etc. Para resolver el problema de la minería de SCF se han propuesto varios algoritmos. Los mejores desempeños en la minería de SCF se han logrado con los algoritmos basados en el crecimiento de patrones. No obstante, la identificación de los patrones duplicados y el conteo de frecuencia, durante el proceso de minería, siguen siendo dos tareas que demandan muchos recursos computacionales (tiempo y espacio) y que afectan la eficiencia de los algoritmos. Los cuatro algoritmos que se proponen en esta tesis se enfocan en resolver estas dos tareas de una manera más eficiente que los métodos existentes. En particular, se presentan nuevas propiedades en las formas de representar los grafos candidatos que logran reducir el tiempo dedicado a la identificación de duplicados. Además, se introduce una nueva estructura de datos, que permite mantener valores pre-calculados, para acelerar el conteo de frecuencia y la generación de candidatos. Por otro lado, existen aplicaciones donde no es práctico considerar todos los SCF debido a que pueden ser demasiados. Una manera de abordar este problema es buscar solamente los SCF cerrados. Esta solución, además de reducir el número de patrones encontrados luego de la minería, permite describir completamente el conjunto de todos los SCF. De los cuatro algoritmos propuestos como parte de esta investigación, tres de ellos permiten encontrar todos los SCF y el cuarto se enfoca a la minería de los SCF cerrados. De acuerdo a los experimentos realizados y resultados obtenidos, los nuevos algoritmos logran mejores desempeños en comparación con algoritmos existentes.
Instituto Nacional de Astrofísica, Óptica y Electrónica
2010-01
Tesis de doctorado
Español
Estudiantes
Investigadores
Público en general
Gago-Alonso A.
CIENCIA DE LOS ORDENADORES
Versión aceptada
acceptedVersion - Versión aceptada
Appears in Collections:Doctorado en Ciencias Computacionales

Upload archives


File SizeFormat 
GagoAlA.pdf1.48 MBAdobe PDFView/Open