Algoritmos para la minería de patrones frecuentes aproximados en colecciones de grafos

Resumen

En numerosas aplicaciones reportadas, los grafos han permitido naturalmente representar las entidades y sus relaciones. La búsqueda de subgrafos frecuentes aproximados (SFA) en colecciones de grafos ha sido de gran ayuda en diferentes tareas donde se permiten variaciones en la correspondencia entre grafos. Sin embargo, no existen algoritmos para la minería de este tipo de patrones donde se permitan variaciones en las etiquetas de los vértices y aristas manteniendo la estructura de los grafos. Por este motivo, en esta investigación se propone el primer algoritmo de este tipo para la minería de SFA en colecciones de grafos. Además, con el objetivo de mostrar la utilidad de dichos patrones, se propone un método para la clasificación de imágenes representadas mediante SFA y otro para el agrupamiento de imágenes. Con el objetivo de mejorar la eficiencia del algoritmo propuesto, se proponen dos podas que inciden en la disminución del espacio de búsqueda, del número de candidatos y de las pruebas de formas canónicas. Con fines similares, pero para reducir la representación de la colección de imágenes basada en SFA, se explora el uso de algoritmos de selección de características, se propone el uso de patrones emergentes y se extiende el algoritmo propuesto para identificar solo los SFA maximales durante el proceso de minería. Consecuentemente, se realiza un estudio del impacto de la selección de patrones en la clasificación de imágenes basada en este tipo de minería. Los algoritmos y métodos propuestos trabajan sobre colecciones de grafos simples; sin embargo, en algunas aplicaciones los multigrafos han sido utilizados para modelar los datos, porque en la realidad existe comúnmente más de una relación (arista) entre las entidades representadas como vértices. Sin embargo, los algoritmos reportados para la minería de SFA han sido diseñados para trabajar con grafos simples. Por tanto, con el objetivo de solucionar el problema de minar SFA en colecciones de multigrafos, en esta investigación se proponen dos algoritmos —el primero basado en matrices de adyacencia, y el segundo basado en búsqueda en profundidad— para la minería de SFA directamente sobre las colecciones de multigrafos. Para la confección de estos dos últimos algoritmos fue necesario extender las formas canónicas basadas en matrices de adyacencia y en búsqueda en profundidad para que estas pudieran representar multigrafos, ya que están diseñadas solo para representar grafos simples. Además, con el objetivo de reducir el conjunto de SFA que se minan, se propone la extensión de un algoritmo para la minería tanto de los SFA cerrados, como de los maximales, así como de otros patrones con pequeñas diferencias en sus soportes. La novedad de esta investigación está avalada por la comunidad científica internacional a través de 15 publicaciones y una tesis doctoral.