Por favor, use este identificador para citar o enlazar este ítem:
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 | |
| Aparece en las colecciones: | Doctorado en Ciencias Computacionales |
Cargar archivos:
| Fichero | Tamaño | Formato | |
|---|---|---|---|
| GagoAlA.pdf | 1.48 MB | Adobe PDF | Visualizar/Abrir |