Descubrimiento de patrones frecuentes en flujos de trabajo

Abstract

Los grafos son estructuras de datos muy potentes que permiten representar, de forma gráfica, la unión o enlace entre diferentes entidades que mantienen algún tipo de interacción. Estas estructuras fueron inventadas en el siglo XVIII, y desde entonces han sido ampliamente utilizadas. Un tipo concreto de grafos son los grafos dirigidos, estos se caracterizan por poseer direcciones definidas en los arcos, lo que facilita el modelar flujos de ejecución en los que unos nodos deben preceder a otros. Con este tipo de estructuras se puede modelar desde las posibles secuencias de tareas efectuadas por clientes en un centro comercial, hasta el flujo de trabajo (workflow) propio de un proceso de negocio. En todos estos casos puede ser interesante conocer, dado un conjunto de ejecuciones, cuáles son las tareas que más se ejecutan, y en qué orden, con el fin de obtener información de interés en relación al proceso. Algunos ejemplos de lo que se podría hacer con esta información serían i) rediseñar la distribución del centro comercial para mejorar las ventas, ii) optimizar los procesos de negocio redistribuyendo las tareas según su frecuencia de ejecución, iii) y hasta descubrir el comportamiento más frecuente entre los alumnos de una asignatura, para poder modificar el diseño de la unidad educativa, mejorando así los resultados. Aquí es donde entra en juego el objetivo del presente Trabajo Fin de Grado. A partir de un registro de actividades (log), y un flujo de trabajo asociado a él, se obtienen los patrones frecuentes ofreciendo información que a priori no está al alcance de los usuarios. Debido a la escasez de aproximaciones que realicen esta minería de grafos, este proyecto plantea la implementación y mejora del algoritmo w-find, que introduce la base para la búsqueda de patrones frecuentes en grafos dirigidos con restricciones.