Repetición basada en tokens

Algoritmo de comprobación de conformidad

La técnica de repetición basada en tokens es un algoritmo de verificación de conformidad ^[1] que verifica qué tan bien un proceso se ajusta a su modelo al reproducir cada traza en el modelo (en notación de red de Petri ). ^[2] Utilizando los cuatro contadores de tokens producidos, tokens consumidos, tokens faltantes y tokens restantes, registra las situaciones en las que se fuerza la activación de una transición y los tokens restantes después de que finaliza la repetición. Con base en el recuento en cada contador, podemos calcular el valor de aptitud entre la traza y el modelo.

El algoritmo[2]

La técnica de repetición de token utiliza cuatro contadores para realizar un seguimiento de un rastro durante la reproducción:

• p : Tokens producidos
• c : Fichas consumidas
• m : Fichas faltantes (consumidas mientras no estaban allí)
• r : Fichas restantes (producidas pero no consumidas)

Invariantes:

• En cualquier momento: ${\displaystyle p+m\geq c\geq m}$
• Al final: ${\displaystyle r=p+m-c}$

Al principio, se produce una ficha para el lugar de origen (p = 1) y, al final, se consume una ficha del lugar de destino (c' = c + 1). Cuando termina la repetición, el valor de aptitud se puede calcular de la siguiente manera:

$${\displaystyle {\frac {1}{2}}(1-{\frac {m}{c}})+{\frac {1}{2}}(1-{\frac {r}{p}})}$$

Ejemplo

Supongamos que existe un modelo de proceso en notación de red de Petri como sigue:

Un modelo de proceso M con las actividades a, b, c, d

Ejemplo 1: Reproducir el seguimiento (a , b , c , d) en el modelo M

• Paso 1: se inicia un token. Se produce un token ( ). ${\displaystyle p=1}$

• Paso 2: La actividad consume 1 token para ser activada y produce 2 tokens ( y ). ${\displaystyle \mathbf {a} }$ ${\displaystyle p=1+2=3}$ ${\displaystyle c=1}$

• Paso 3: La actividad consume 1 token y produce 1 token ( y ). ${\displaystyle \mathbf {b} }$ ${\displaystyle p=3+1=4}$ ${\displaystyle c=1+1=2}$

• Paso 4: La actividad consume 1 token y produce 1 token ( y ). ${\displaystyle \mathbf {c} }$ ${\displaystyle p=4+1=5}$ ${\displaystyle c=2+1=3}$

  

• Paso 5: La actividad consume 2 tokens y produce 1 token ( , ). ${\displaystyle \mathbf {d} }$ ${\displaystyle p=5+1=6}$ ${\displaystyle c=3+2=5}$

• Paso 6: El token en el lugar final se consume ( ). El rastreo está completo. ${\displaystyle c=5+1=6}$

  

La aptitud de la traza ( ) en el modelo es: ${\displaystyle \mathbf {a,b,c,d} }$ ${\displaystyle \mathbf {M} }$

$${\displaystyle {\frac {1}{2}}(1-{\frac {m}{c}})+{\frac {1}{2}}(1-{\frac {r}{p}})={\frac {1}{2}}(1-{\frac {0}{6}})+{\frac {1}{2}}(1-{\frac {0}{6}})=1}$$

Ejemplo 2: Reproducir la traza (a, b, d) en el modelo M

• Paso 1: se inicia un token. Se produce un token ( ). ${\displaystyle p=1}$

• Paso 2: La actividad consume 1 token para ser activada y produce 2 tokens ( y ). ${\displaystyle \mathbf {a} }$ ${\displaystyle p=1+2=3}$ ${\displaystyle c=1}$

• Paso 3: La actividad consume 1 token y produce 1 token ( y ). ${\displaystyle \mathbf {b} }$ ${\displaystyle p=3+1=4}$ ${\displaystyle c=1+1=2}$

• Paso 4: La actividad debe iniciarse pero no hay suficientes tokens. Se produjo un token artificial y el contador de tokens faltantes se incrementa en uno ( ). El token artificial y el token en el lugar se consumen ( ) y se produce un token en el lugar final ( ). ${\displaystyle \mathbf {d} }$ ${\displaystyle m=1}$ ${\displaystyle [\mathbf {b,d} ]}$ ${\displaystyle c=2+2=4}$ ${\displaystyle p=4+1=5}$

  

• Paso 5: El token en el lugar final se consume ( ). El rastreo está completo. Queda un token restante en el lugar ( ). ${\displaystyle c=4+1=5}$ ${\displaystyle [\mathbf {a,c} ]}$ ${\displaystyle r=1}$

La aptitud de la traza ( ) en el modelo es: ${\displaystyle \mathbf {a,b,d} }$ ${\displaystyle \mathbf {M} }$

$${\displaystyle {\frac {1}{2}}(1-{\frac {m}{c}})+{\frac {1}{2}}(1-{\frac {r}{p}})={\frac {1}{2}}(1-{\frac {1}{5}})+{\frac {1}{2}}(1-{\frac {1}{5}})=0.8}$$

Referencias

1. van der Aalst, Wil (2016), van der Aalst, Wil (ed.), "Ciencia de datos en acción" , Minería de procesos: ciencia de datos en acción , Berlín, Heidelberg: Springer, págs. 3–23, doi :10.1007 /978-3-662-49851-4_1, ISBN 978-3-662-49851-4, consultado el 16 de noviembre de 2021
2. Rozinat, A.; van der Aalst, WMP (marzo de 2008). "Comprobación de conformidad de procesos basada en la monitorización del comportamiento real" . Sistemas de información . 33 (1): 64–95. doi :10.1016/j.is.2007.07.001. ISSN  0306-4379.