Por favor, use este identificador para citar o enlazar este ítem:
http://inaoe.repositorioinstitucional.mx/jspui/handle/1009/905| Representative frequent approximate subgraph mining on multi-graph collections | |
| NIUSVEL ACOSTA MENDOZA | |
| JESUS ARIEL CARRAZCO OCHOA ANDRÉS GAGO ALONSO | |
| Acceso Abierto | |
| Atribución-NoComercial-SinDerivadas | |
| Mining of frequent graphs Correspondence between multi-graphs Representative frequent subgraphs | |
| Nowadays, there has been an increase in the use of frequent approximate subgraph (FAS)
mining for different real-world applications such as image classification, social network analysis and natural language processing, among others. In several of these applications, in the last years, multi-graphs have been used to model data, because, in the real-world, commonly there are more than one relation (edge) between the entities represented as vertices. However, the reported FAS miners have been designed to work with simple-graphs. Therefore, in order to solve the problem of mining FASs from multi-graph collections, we explore two alternatives in this research: (1) transforming the multi-graphs into simple-graphs and the FASs are obtained by applying conventional FAS miners over the transformed simple-graph collection, and (2) proposing algorithms for mining FAS directly from multi-graph collections. Following the first alternative, a method, called allEdges, based on graph transformations for mining all FASs on multi-graph collections by means of applying simple-graph FAS miners was proposed. Later, for speeding up the mining process, an alternative method, called onlyMulti, based on graph transformation for mining some FASs over multi-graph collections was proposed. Despite the fact that both allEdges and onlyMulti allow using simple-graph FAS miners for mining multi-graph FASs, the graph transformation processes increase the size of the graph collection and therefore, the mining process cost is increased. Thus, an algorithm, called MgVEAM, for mining all FASs directly over multi-graph collections without graph transformations was proposed. After, in order to accelerate the mining process, another algorithm, called AMgMiner, for directly mining all multi-graph FASs was proposed. AMgMiner is faster than MgVEAM, but the former requires more memory than the later. All the proposed methods and algorithms were evaluated and compared by using di_erent multi-graph datasets. The large number of mined FASs is one of the fundamental drawbacks of FAS mining, which makes difficult the further use of the mined FASs. Therefore, in order to mine only a subset of representative FASs from multi-graph collections, we proposed two algorithms; one for mining generalized closed FASs and another for mining clique FASs.
Experiments on different databases were carried out to show the performance of our
proposals.
Actualmente existe un incremento del uso de la minería de subgrafos frecuentes aproximados en diferentes aplicaciones, por ejemplo clasificación de imágenes, análisis de redes sociales y procesamiento del lenguaje natural, entre otros. En varias de estas aplicaciones, en los últimos años, los multi-grafos han sido utilizados para modelar los datos, porque en la realidad, comúnmente existen más de una relación (arista) entre las entidades representadas como vértices. Sin embargo, los algoritmos reportados para la minería de este tipo de patrones han sido diseñados para trabajar con grafos simples. Por tanto, con el objetivo de solucionar el problema de minar subgrafos frecuentes aproximados en colecciones de multi-grafos, en esta tesis se exploran dos alternativas: (1) transformar los multi-grafos en grafos simples, obteniendo los subgrafos frecuentes aproximados al aplicar algoritmos convencionales sobre los grafos simples transformados, y (2) proponer algoritmos para la minería de subgrafos frecuentes aproximados directamente sobre colecciones de multi-grafos. Siguiendo la primera alternativa se propone un método, llamado allEdges, que se basa en transformaciones de grafos para la minería de todos los subgrafos frecuentes aproximados en colecciones de multi-grafos mediante la aplicación de algoritmos que minan grafos simples. Luego, para acelerar el proceso de minería se propuso un método alternativo, llamado onlyMulti, el cual está basado en transformaciones de grafos para minar algunos subgrafos frecuentes aproximados en colecciones de multi-grafos. A pesar del hecho de que los métodos allEdges y onlyMulti permiten usar algoritmos que mina grafos simples para minar subgrafos frecuentes aproximados en el contexto de multi-grafos, los procesos de transformación incrementan el tamaño de la colección de grafos y por consiguiente se incrementa el costo del proceso de minería. Por lo que se propone un algoritmo, llamado MgVEAM, para minar todos los subgrafos frecuentes aproximados directamente de la colección de multi-grafos sin procesos de transformación de grafos. Después, con el objetivo de acelerar el proceso de minería, se propone otro algoritmo, llamado AMgMiner, para minar todos los subgrafos frecuentes aproximados directamente en colecciones de multi-grafos. AMgMiner es más rápido que MgVEAM, pero el primero requiere más memoria que el segundo. | |
| Instituto Nacional de Astrofísica, Óptica y Electrónica | |
| 20-02-2018 | |
| Tesis de doctorado | |
| Inglés | |
| Estudiantes Investigadores Público en general | |
| Acosta-Mendoza N. | |
| LENGUAJES DE PROGRAMACIÓN | |
| Versión aceptada | |
| acceptedVersion - Versión aceptada | |
| Aparece en las colecciones: | Doctorado en Ciencias Computacionales |
Cargar archivos:
| Fichero | Tamaño | Formato | |
|---|---|---|---|
| AcostaMeN.pdf | 2.77 MB | Adobe PDF | Visualizar/Abrir |