| dc.contributor | JESUS ARIEL CARRAZCO OCHOA | |
| dc.creator | ANDRÉS GAGO ALONSO | |
| dc.date | 2010-01 | |
| dc.date.accessioned | 2023-07-25T16:21:45Z | |
| dc.date.available | 2023-07-25T16:21:45Z | |
| dc.identifier | http://inaoe.repositorioinstitucional.mx/jspui/handle/1009/507 | |
| dc.identifier.uri | https://repositorioslatinoamericanos.uchile.cl/handle/2250/7805725 | |
| dc.description | 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. | |
| dc.description | 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. | |
| dc.format | application/pdf | |
| dc.language | spa | |
| dc.publisher | Instituto Nacional de Astrofísica, Óptica y Electrónica | |
| dc.relation | citation:Gago-Alonso A. | |
| dc.rights | info:eu-repo/semantics/openAccess | |
| dc.rights | http://creativecommons.org/licenses/by-nc-nd/4.0 | |
| dc.subject | info:eu-repo/classification/Minería de datos/Data mining | |
| dc.subject | info:eu-repo/classification/Teoría de grafos/Graph theory | |
| dc.subject | info:eu-repo/classification/Teoría de algoritmos/Algorithm theory | |
| dc.subject | info:eu-repo/classification/cti/1 | |
| dc.subject | info:eu-repo/classification/cti/12 | |
| dc.subject | info:eu-repo/classification/cti/1203 | |
| dc.subject | info:eu-repo/classification/cti/1203 | |
| dc.title | Minería de subgrafos conexos frecuentes en colecciones de grafos etiquetados | |
| dc.type | info:eu-repo/semantics/doctoralThesis | |
| dc.type | info:eu-repo/semantics/acceptedVersion | |
| dc.audience | students | |
| dc.audience | researchers | |
| dc.audience | generalPublic | |
