info:eu-repo/semantics/doctoralThesis
Minería de subgrafos conexos frecuentes en colecciones de grafos etiquetados
Autor
ANDRÉS GAGO ALONSO
Resumen
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.
Materias
Ítems relacionados
Mostrando ítems relacionados por Título, autor o materia.
-
Compendio de innovaciones socioambientales en la frontera sur de México
Adriana Quiroga -
Caminar el cafetal: perspectivas socioambientales del café y su gente
Eduardo Bello Baltazar; Lorena Soto_Pinto; Graciela Huerta_Palacios; Jaime Gomez -
Material de empaque para biofiltración con base en poliuretano modificado con almidón, metodos para la manufactura del mismo y sistema de biofiltración
OLGA BRIGIDA GUTIERREZ ACOSTA; VLADIMIR ALONSO ESCOBAR BARRIOS; SONIA LORENA ARRIAGA GARCIA