Algoritmo alfa

El algoritmo α o α-miner 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 propuesto por primera vez por van der Aalst , Weijters y Măruşter. ^[1] El objetivo de Alpha miner es convertir el registro de eventos en una red de flujo de trabajo basada en las relaciones entre varias actividades en el registro de eventos. Un registro de eventos es un conjunto múltiple de rastros, y un rastro es una secuencia de nombres de actividades. Desde entonces se han presentado varias extensiones o modificaciones del mismo, que se enumerarán a continuación.

Alpha Miner fue el primer algoritmo de descubrimiento de procesos que se propuso y ofrece una buena descripción general del objetivo del descubrimiento de procesos y de cómo se ejecutan las distintas actividades dentro del proceso. Alpha Miner también fue la base para el desarrollo de muchas otras técnicas de minería de procesos, como la minería heurística y la minería genética, que se desarrolló sobre la base de la idea en la que se basa Alpha Miner. ^[2]

Descripción breve

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. ${\displaystyle W\subseteq T^{*}}$

Esto se logra examinando las relaciones causales observadas entre las tareas. Por ejemplo, una tarea específica podría preceder siempre a otra tarea específica en cada rastro de ejecución, lo que podría ser una información útil.

Definiciones utilizadas

• Un seguimiento de flujo de trabajo o seguimiento de ejecución es una cadena sobre un alfabeto de tareas . ${\displaystyle T}$
• Un registro de flujo de trabajo es un conjunto de seguimientos del flujo de trabajo.

Registro de eventos

El registro de eventos es el requisito principal para aplicar cualquier algoritmo de descubrimiento de procesos. Un registro de eventos consta de un identificador único para un caso, un nombre de actividad que describe la acción que ocurre en el proceso y una marca de tiempo. Un registro de eventos se puede representar como un conjunto múltiple de actividades. Para simplificar, el siguiente ejemplo utilizaría letras alfabéticas para representar una actividad. Considere un ejemplo de registro de eventos que se muestra en la siguiente figura:

Un registro de eventos es un conjunto de varios rastros, y un rastro es una secuencia de actividades. Por lo tanto, un registro de eventos como el anterior se puede representar mediante la siguiente notación:

${\displaystyle L1=[<A,B,C,D>,<A,C,B,D>,<A,E,D>]}$

Cada registro de eventos se puede resumir en un conjunto múltiple de rastros, y dichos rastros se pueden utilizar para desglosar las relaciones entre las distintas actividades del proceso. Según las reglas de Alpha Miner, las actividades que pertenecen a varios casos pueden tener cuatro tipos de relaciones entre ellas: ^[2]

• Sucesión directa: x > y si y solo si alguna relación x es directamente sucesiva a y. En nuestro ejemplo, podemos considerar que A > B , A > E , A > C.
• Causalidad: x → y si y solo si x > y y no y > x. En nuestro ejemplo, podemos considerar que A → E.
• Paralelas: x || y si y solo si x > y y y > x. En nuestro ejemplo, tenemos B || C.
• Opción: x # y si y solo si no (x > y) y no (y > x). En nuestro ejemplo, tenemos A # D.

Patrones

Patrón de secuencia: A → B

Patrón de división XOR: A → B, A → C y B # C

Patrón de división AND: A → B, A → C y B || C

Descripción

El minero alfa comienza convirtiendo un registro de eventos en relaciones de seguimiento directo, secuencia, paralelo y elección, y las usa para crear una red de Petri que describe el modelo de proceso. Inicialmente, el algoritmo construye una matriz de huellas. Usando la matriz de huellas y el patrón mostrado arriba, uno puede construir un modelo de proceso. Con base en las cuatro relaciones descritas anteriormente, primero se descubre una matriz basada en huellas. Usando la matriz basada en huellas se descubren lugares. Cada lugar se identifica con un par de conjuntos de tareas, para mantener baja la cantidad de lugares.

• ${\displaystyle Y_{W}}$es el conjunto de todos los pares de conjuntos máximos de tareas tales que ${\displaystyle (A,B)}$
  • Ni y contienen ningún miembro de > y ${\displaystyle A\times A}$ ${\displaystyle B\times B}$
  • ${\displaystyle A\times B}$es un subconjunto de →
• ${\displaystyle P_{W}}$contiene un lugar para cada miembro de , más el lugar de entrada y el lugar de salida ${\displaystyle p_{(A,B)}}$ ${\displaystyle Y_{W}}$ ${\displaystyle i_{W}}$ ${\displaystyle o_{W}}$

La relación de flujo es la unión de lo siguiente: ${\displaystyle F_{W}}$

• ${\displaystyle \{(a,p_{(A,B)})|(A,B)\in Y_{W}\wedge a\in A\}}$
• ${\displaystyle \{(p_{(A,B)},b)|(A,B)\in Y_{W}\wedge b\in B\}}$
• ${\displaystyle \{(i_{W},t)|t\in T_{I}\}}$
• ${\displaystyle \{(t,i_{O})|t\in T_{O}\}}$

El resultado es

• una estructura de red de Petri ${\displaystyle \alpha (W)=(P_{W},T_{W},F_{W})}$
• con un lugar de entrada y un lugar de salida ${\displaystyle i_{W}}$ ${\displaystyle o_{W}}$
• Debido a que cada transición de está en una ruta de a , es de hecho una red de flujo de trabajo. ${\displaystyle T_{W}}$ ${\displaystyle F_{W}}$ ${\displaystyle i_{W}}$ ${\displaystyle o_{W}}$

Para el ejemplo dado anteriormente, la siguiente red de Petri sería el resultado de la aplicación de alpha miner.

Propiedades

Se puede demostrar ^[3] que en el caso de un registro de flujo de trabajo completo generado por una red SWF sólida, la red que lo genera se puede reconstruir. Completo significa que su relación es máxima. No se requiere que estén presentes todos los rastros posibles (lo que sería infinito para una red con un bucle). ${\displaystyle \succ _{W}}$

Limitaciones

• Lugares implícitos: Alpha Miner no puede distinguir entre lugares implícitos y obligatorios y, por lo tanto, podría generar lugares adicionales no obligatorios en la red de Petri descubierta. ^[4]
• Bucles: Alpha Miner no puede descubrir bucles de longitud 1 y 2 en el modelo de proceso. ^[5]
• Las dependencias locales a menudo se pasan por alto en el minero alfa. ^[5]
• Sesgo de representación: el minero alfa solo puede descubrir redes de Petri, lo que agrega un sesgo de representación como el requisito de etiquetas visibles únicas para cada transición. ^[5]

Referencias

1. van der Aalst, WMP y Weijters, AJMM y Maruster, L (2004). "Minería de flujo de trabajo: descubrimiento de modelos de procesos a partir de registros de eventos", IEEE Transactions on Knowledge and Data Engineering , vol. 16
2. van der Aalst, W.; Weijters, T.; Maruster, L. (septiembre de 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 . 16 (9): 1128–1142. doi :10.1109/TKDE.2004.47. ISSN  1558-2191. S2CID  5282914.
3. van der Aalst y otros, 2003
4. "Descubrimiento de redes de Petri a partir de registros de eventos". ResearchGate . Consultado el 31 de agosto de 2021 .
5. "Limitaciones de Alpha Miner" (PDF) . Archivado (PDF) del original el 31 de agosto de 2021.