Minería de grafos
Como caso general de la minería de datos está la Minería de grafos,[1] esta consiste en encontrar elementos o patrones representativos dentro de un grafo, pero no es solo el encontrar subestructuras que se repitan una y otra vez, sino que también es el proceso de identificar conceptos que describen a las estructuras más importantes para una mejor interpretación de los datos. Una vez descubierta una estructura, puede usarse para simplificar el grafo original mediante el reemplazo de la subestructura por un vértice que represente a la recién descubierta subestructura. Debido a que existen muchos fenómenos diferentes que pueden ser representados con grafos (ejemplo: una red de computadoras, redes sociales, la composición química de un elemento, la estructura de una proteína, etc) se hace importante poder extraer información implícita de dichos fenómenos.
¿Qué es un grafo?
Un grafo es una estructura compuesta por un conjunto de vértices V y un conjunto de aristas E en donde los elementos del conjunto de aristas E representan relaciones entre pares de vértices del conjunto V. Dentro de un grafo los vértices pueden representar a cualquier objeto mientras que las aristas representan la relación existente entre esos objetos.
Reconocimiento de patrones frecuentes[2]
Una de las tareas principales de la minería de grafos es precisamente encontrar patrones frecuentes dentro de un grafo , este proceso se puede dividir en dos tareas fundamentales; encontrar posibles patrones frecuentes (Generación de candidatos) y hacer un conteo de frecuencia para esos patrones. Para generación de candidatos existen dos estrategias fundamentales:
A priori: Los algoritmos que utilizan esta estrategia requieren de una operación FUSION para unir dos subgrafos y obtener un subgrafo candidato de tamaño mayor.
Crecimiento de patrones: En esta estrategia un grafo g puede ser extendido adicionándole una nueva arista e. hay dos formas de realizar esta extensión dependiendo de que la arista este compuesta por dos vértices de g(extensiones cerradas) o un vértice en g y uno nuevo (extensiones por vértice). El grafo que resulta de esta extensión se le suele decir que es hijo de g.
Una vez que se tienen los posibles patrones frecuentes solo queda hacer un conteo de la cantidad de veces que aparece este patrón en el grafo que se está minando y decidir si con esa cantidad de ocurrencia ese patrón es frecuente o no.
Criterio de evaluación
Una parte importante de cualquier algoritmo de minería de datos (en este caso la minería de grafo como caso particular) es el criterio de evaluación. Este criterio se utiliza para determinar cuáles subgrafos del espacio de búsqueda son relevantes y pueden ser considerados como parte de los resultados. Existe un método basado en grafos que utiliza el principio de longitud mínima (MDL) para evaluar los subgrafos descubiertos, este método es conocido por Subdue. El principio MDL dice que la mejor descripción del conjunto de datos es aquella que minimiza la longitud de la descripción del conjunto de datos. En el método basado en grafos el principio MDL se utiliza para determinar que tan bien un grafo comprime al grafo de entrada
Subdue[3]
Subdue es un sistema de aprendizaje relacional utilizado para encontrar subestructuras (subgrafos) que aparecen repetidamente en la representación basada en grafos de bases de Datos. Una vez que la base de datos está representada con grafos, Subdue busca la subestructura que mejor comprime al grafo utilizando el principioMDL. Después de encontrar esta subestructura, Subdue comprime el grafo y puede iterar repitiendo este proceso. Subdue tiene la capacidad de realizar un macheo inexacto que permite descubrir subestructuras con pequeñas variaciones. Otra característica importante de Subdue es que permite utilizar conocimiento previo representado como subestructuras predefinidas.
Macheo Inexacto de Grafos[4]
Subdue tiene la capacidad de encontrar subestructuras con ligeras diferencias en sus instancias. Estas diferencias pueden ser causa de ruido o por la naturaleza de la información. Algunas de estas pequeñas diferencias pueden ser un vértice adicional o uno mejor, una etiqueta diferente en un vértice, un arco que no existe en una instancia, etc. La manera en que Subdue maneja el macheo inexacto es asignando un costo a cada diferencia que encuentra en la nueva instancia y lleva un registro del costo total de las diferencias de la nueva instancia con respecto a la original. Si el costo es menor que un umbral (este umbral se da como parámetro),entonces se considera que la nueva instancia hace un macheo con la original. Se utilizan reglas para asignar un costo a cada tipo de diferencia, estas reglas se ajustan de acuerdo al dominio. El procedimiento de macheo de grafos está restringido a ser polinomial con respecto al tamaño de los grafos que se comparan.
Método de Búsqueda
Subdue utiliza una búsqueda restringida computacionalmente para encontrar subestructuras. Una subestructura es un subgrafo contenido en el grafo de entrada. El algoritmo inicia con un solo vértice como subestructura inicial y en cada iteración expande las instancias de aquella subestructura añadiendo un arco en cada posible manera. De esta forma genera nuevas subestructuras que podrían considerarse para expansión. El método de búsqueda también puede sesgarse utilizando conocimiento previo (ejemplo.subestructuras que creemos que pueden existir en los datos, pero que queremos estudiar con mayor detalle) dadas por el usuario. En este caso, el usuario provee subestructuras de conocimiento previo como entrada a Subdue. Subdue encuentra instancias de las subestructuras de conocimiento previo en el grafo de entrada y continúa buscando extensiones de aquellas subestructuras.
Véase también
Referencias
- Graph Mining: Laws, Generators, and Algorithms
- http://www.cenatav.co.cu/doc/RTecnicos/RT%20SerieGris_001web.pdf
- http://ailab.wsu.edu/subdue/
- . Archivado desde el original el 21 de marzo de 2014. Consultado el 23 de diciembre de 2012.