El algoritmo α es un algoritmo utilizado en la minería de procesos , cuyo objetivo es reconstruir la causalidad a partir de un conjunto de secuencias de eventos . Fue presentado por primera vez por van der Aalst , Weijters y Măruşter. [1] Desde entonces se han presentado varias extensiones o modificaciones, que se enumeran a continuación.
Construye redes P / T con propiedades especiales ( redes de flujo de trabajo ) a partir de registros de eventos (como podría recopilar un sistema ERP ). Cada transición en la red corresponde a una tarea observada.
Breve descripción
El algoritmo toma un registro de flujo de trabajo como entrada y da como resultado la construcción de una red de flujo de trabajo.
Lo hace examinando las relaciones causales observadas entre tareas. Por ejemplo, una tarea específica siempre puede preceder a otra tarea específica en cada seguimiento de ejecución, lo que sería información útil.
Definiciones utilizadas
Descripción
Declarativamente, el algoritmo se puede presentar de la siguiente manera. Se determinan tres conjuntos de tareas:
- es el conjunto de todas las tareas que ocurren en al menos una traza
- es el conjunto de todas las tareas que ocurren en el rastreo inicial
- es el conjunto de todas las tareas que ocurren de forma terminal
Se determinan las relaciones de ordenamiento básicas ( primero, los tres últimos se pueden construir a partir de allí)
- si precede directamente en algún rastro
- si
- si
- si
Se descubren lugares. Cada lugar se identifica con un par de conjuntos de tareas, con el fin de mantener bajo el número de lugares.
- es el conjunto de todos los pares de conjuntos máximos de tareas tales que
- Ninguno de los dos y contener cualquier miembro de y
- es un subconjunto de
- contiene un lugar para cada miembro de , más el lugar de entrada y el lugar de salida
La relación de flujo es la unión de lo siguiente:
El resultado es
- una estructura de red de Petri
- con un lugar de entrada y un lugar de salida
- porque cada transición de está en un -camino de a , es de hecho una red de flujo de trabajo.
Propiedades
Se puede demostrar [2] que en el caso de un registro de flujo de trabajo completo generado por una red SWF sólida , se puede reconstruir la red que lo genera. Completo significa que sula relación es máxima. Se no requiere que todos los rastros posibles estén presentes (que sería infinito numerable para una red con un bucle).
Limitaciones
Las redes generales de flujo de trabajo pueden contener varios tipos de construcciones [3] que el algoritmo α no puede redescubrir.
Construyendo toma un tiempo exponencial en el número de tareas, ya que no es subconjunto restringido y arbitrario de debe ser considerado.
Extensiones
Referencias
- ^ van der Aalst, WMP y Weijters, AJMM y Maruster, L (2004). "Minería de flujo de trabajo: descubrimiento de modelos de proceso a partir de registros de eventos", IEEE Transactions on Knowledge and Data Engineering , vol 16
- ^ van der Aalst y col. 2003
- ^ A. de Medeiros, AK y van der Aalst, WMP y Weijters, AJMM (2003). " Minería de flujo de trabajo: estado actual y direcciones futuras ". en: "volumen 2888 de Lecture Notes in Computer Science", Springer-Verlag
- ^ A. de Medeiros, AK y van Dongen, BF y van der Aalst, WMP y Weijters, AJMM (2004). " Minería de procesos: ampliación del algoritmo α para minar bucles cortos "
- ^ Wen, L y van der Aalst, WMP y Wang, J y Sun, J (2007). " Modelos de procesos de minería con constructos de no libre elección ", "Minería de datos y descubrimiento del conocimiento" vol 15, p. 145-180, Springer-Verlag