Alpha-mineur. Analyse de la construction d'un modèle pour le Process Mining

L'algorithme alpha est la première technologie d'analyse de processus qui a permis de trouver les réseaux dits de flux de travail à partir des journaux de processus. L'algorithme a été développé en 2013 par le fondateur de la méthodologie Process Mining, le professeur Will MP van der Aalst.



Qu'est-ce que les réseaux Workflow (ci-après WF) est un réseau construit sur la base de réseaux Petri. Surtout, WF basé sur les réseaux Petri vous permet de présenter et d'analyser davantage les flux de travail.



Les caractéristiques distinctives de WF sont:

1. Un départ clair. (Une action unique qui ne déclenche que toutes les chaînes d'actions)
2. Clear End (action unique qui ne termine que toutes les chaînes d'actions)
3. Chaque action individuelle se situe entre l'élément 1. et le point 2.

Jetons un coup d'œil à quelques exemples:











Ces schémas ne sont pas WF. Pourquoi? Dans le premier cas, nous n'avons pas le début et la fin de la chaîne (ils sont indiqués par un cercle). Dans le second cas, l'action d n'a pas de fin.



Ci-dessous, j'ai donné un exemple d'un réseau WF correct - il y a un début et une fin, et toutes les actions sont situées entre eux et sont terminées.







Après avoir clarifié un peu ce qu'est WF, passons à l'algorithme alpha:



afin d'obtenir WF en utilisant l'algorithme alpha, nous devons mettre les choses en ordre dans notre journal. Pour ce faire, nous définirons les relations suivantes entre les transitions dans le journal des événements (plus tard, elles seront nécessaires pour construire un modèle):



1. Séquence directe.

Événement A> Événement B.

Dans un vrai journal d'événements, cela ressemblerait à ceci:







2. Relation causale.

Événement A → Événement B. Cela

signifie qu'il y a de telles transitions dans le journal des événements







Mais il n'y a pas de telles transitions :







Par conséquent, sur le diagramme, nous mettons le symbole

1. Événements parallèles.
   
   Le journal contient les deux transitions Événement A → Événement B et Événement B → Événement A.
2. Manque de cohérence.
   
   Événement A # Événement B et vice versa. Ces événements n'apparaissent pas dans le journal.

L'ensemble de données commun à toutes les transitions s'appelle l'ensemble L.



Prenons un petit exemple. Voici un journal de trois cas.







Écrivons les liens de notre journal qui sont utilisés dans l'algorithme alpha:

1. > ,
   
   > ,
   
   > ,
   
   > ,
   
   > ,
   
   > ,
   
   >
2. → ,
   
   → ,
   
   → ,
   
   → ,
   
   → ,
   
   →
3. ||

Sur la base des relations résultantes, nous dessinons WF.







Le modèle résultant couvre toutes les actions de notre journal et est facile à analyser.



Limitations de l'algorithme alpha.



Si votre journal contient des boucles simples ou doubles (répétitions d'actions), l'algorithme interprète mal et peut générer un modèle différent de ce qui est attendu. Revenons à notre journal plus tôt et ajoutons-y des répétitions:







Le modèle attendu ressemblera à ceci:







Mais l'algorithme alpha nous donnera une image complètement différente:







Quelle est la raison? L'action "Traitement d'une demande" n'a ni début ni fin. Dans le processus de génération du modèle, un ensemble A (où se trouvent tous les débuts) et un ensemble B (où se terminent les processus) sont créés. Étant donné qu'avec plusieurs répétitions, les ensembles de données disparaissent de nous, l'algorithme ne peut pas les trouver. En conséquence, cette action sort du modèle général.



La même situation se produit avec deux actions répétées d'affilée. L'algorithme Alpha n'en laissera qu'un seul, le second abandonnera et nous ne pourrons pas interpréter le modèle.



Comment résoudre ce problème? Il est nécessaire de prendre en compte autant que possible les caractéristiques du système que vous analysez. Si votre système écrit dans le journal non seulement les points principaux, mais également les actions générées automatiquement (par exemple, dans le cas d'une saisie manuscrite, le système peut effectuer une sauvegarde automatique toutes les 5 secondes et l'écrire dans le journal), il est alors logique de combiner ces actions en un seul élément.