Il Process Mining può essere utilizzato per apprendere automaticamente modelli comportamentali che mostrano ciò che le persone e le organizzazioni fanno realmente. Le tecniche di Process Mining mettono quindi in relazione il comportamento osservato con il comportamento modellato.
Tale progetto è un estensione dell'algoritmo Model Repair Supported by Frequent Anomalous Local Instance Graphs disponibile al seguente link
L'obiettivo del progetto è riparare un modello di processo secondo un event log, in modo tale che il modello risultante possa riprodurre il log e sia il più simile possibile al modello originale. Per risolvere il problema, considerate già delle sub anomale (parti delle tracce che non le rendono adattabili al modello), legate insieme tramite il concetto di pattern (sequenza di sub correlate tra loro mediante relazioni d'ordine), attraverso tecniche di conformance checking, andiamo ad individuare la posizione appropriata nel modello in cui agganciare il pattern, continuando a riparare adattando tutte le tracce del log che contengono il sottografo anomalo. L'approccio è implementato in un modulo python e si appoggia sulla libreria open-source PM4PY.
Questo progetto come dicevamo non è altro che un'estensione del lavoro precedente, che permette di riparare il modello solamente con una sub. Il nostro approccio è stato quello di effettuare la riparazione del modello con il pattern selezionato, dopo aver considerato ed analizzato la relazione d'ordine che incorre tra le sub del pattern scelto ed estratto dal seguente file.
- Selezione pattern con il quale si sceglie di riparare il modello;
- Importazione log, rete e tracce;
- Stesura elenco trace contenenti il pattern ed individuazione del grafo con matching cost più basso;
- Individuazione delle istanze di sub e delle relazioni nel pattern.
Le relazioni d'ordine rappresentano il modo in cui le due sub sono correlate. Possiamo distinguere quattro tipologie di relazioni d'ordine:
- Strictly sequential: Le due sub sono collegate una di seguito all'altra, i place di uscita della prima sono quelli in entrata alla seconda;
- Sequential: Le sub condividono dei place di uscita e ingresso (sono consecutive) ma alla fine della prima sub è presente un percorso alternativo che torna al modello;
- Eventually: Le due sub non sono collegate direttamente ma sappiamo che esiste un percorso nel modello che ci permette di raggiungere la seconda al termine della prima;
- Interleaving: Ci sono trasformazioni della seconda sub che possono avvenire in maniera parallela a eventi della prima sub.
L'immagine sottoriportata contiene il modello di partenza sottoforma di rete di petri, da riparare con i pattern anomali più frequenti:
- Creazione di un'unica sub a partire dalle sub di partenza;
- Individuazione della transizione che congiunge i marking raggiungibili finali della prima sub con i marking raggiungibili iniziali della seconda sub e collegamento dei place;
- inserimento nel modello delle due sub collegate mediante l'algoritmo di Repairing.
Il pattern scelto per riparare il modello è l'11 in cui la sub2 e la sub17 sono collegate mediante la relazione d'ordine Strictly Sequential, come riportato nella seguente immagine:
Il risultato che si ottiene dopo la fase di repairing, con l'introduzione del pattern nel modello è la seguente:
Per quanto riguarda questa relazione d'ordine, si è optato per due strategie differenti:
- Repairing preciso: il modello viene riparato mediante l'utilizzo dell'algoritmo di Bellman-Ford per l'individuazione del cammino minimo all'interno del grafo;
- Repairing approssimato: il modello viene riparato non andando a considerare il pattern come una sub unica bensì andiamo a fare un repairing separato per ogni sub.
Il pattern scelto per riparare il modello è il 17 in cui la sub2 e la sub14 sono collegate mediante la relazione d'ordine Sequentially, come riportato nella seguente immagine:
- Individuazione dei nodi di start/end della prima e seconda sub;
- Individuazione dei nodi di start della seconda sub non agganciati direttamente ai nodi di end della prima sub;
- Per ogni nodo di end della prima sub, si costruisce l'albero dei costi;
- Per ogni nodo di start della seconda sub non agganciato direttamente ai nodi di end della prima sub, si individua l'albero di costo minimo;
- L'albero di costo minimo viene quindi utilizzato per l'aggiunta degli archi che definiscono il percorso minimo.
Il risultato che si ottiene dopo la fase di repairing, con l'introduzione del pattern nel modello è la seguente:
- Individuazione dei nodi di start e di end e i marking di start e di end raggiungibili per la prima e la seconda sub;
- Riparazione della rete con la prima sub e, successivamente, con la seconda
- Individuazione dei marking di start e di end raggiungibili per la prima e la seconda sub;
- Confronto tra i marking di start/end pre-repairing e post-repairing;
- Inserimento di un'eventuale transizione invisibile nel caso in cui i marking di start/end pre-repairing e post-repairing non coincidessero;
Il risultato che si ottiene dopo la fase di repairing, con l'introduzione del pattern nel modello è la seguente:
- Repairing della rete fatto separatamente per entrambe le sub appartenenti al pattern scelto, in quanto non esiste alcuna transizione che le collega, sappiamo solo che una viene dopo l'altra;
- Aggiunta di nuovi place per collegare le transizioni di end della prima sub con le transizioni di start della seconda sub, mediante una transizione invisibile;
- I nuovi place, e quindi la transizione invisibile, vengono aggiunti come condizione necessaria ma non sufficiente per garantire l'esecuzione della prima sub antecedentemente all'esecuzione della seconda sub.
Il pattern scelto per riparare il modello è il 15 in cui la sub105 e la sub4 sono collegate mediante la relazione d'ordine Eventually, come riportato nella seguente immagine:
Il risultato che si ottiene dopo la fase di repairing, con l'introduzione del pattern nel modello è la seguente:
- Individuazione della sub "più grande": viene presa per prima la sub contenente il maggior numero di elementi;
- Integrazione della sub "più grande" con la sub "più piccola" non contando eventuali trasformazioni in overlapping;
- Viene aggiunta una transizione invisibile nel caso in cui le due sub sono in parallelo, altrimenti viene individuata la transizione in comune, per poi andare ad integrare una sub nell'altra.
Per quanto riguarda questa relazione d'ordine, è necessario distinguere il caso in cui le due sub sono in overlapping e il caso in cui sono in parallelo.
Il pattern scelto per riparare il modello è il 21 in cui la sub63 e la sub2 sono collegate mediante la relazione d'ordine interleaving, come riportato nella seguente immagine:
Il risultato che si ottiene dopo la fase di repairing, con l'introduzione del pattern nel modello è la seguente:
Il pattern scelto per riparare il modello è l'11 in cui la sub2 e la sub17 sono collegate mediante la relazione d'ordine Interleaving, come riportato nella seguente immagine:
Il risultato che si ottiene dopo la fase di repairing, con l'introduzione del pattern nel modello è la seguente:
Questa repository contiene materiale aggiuntivo per gli articoli "Model Repair Supported by Frequent Anomalous Local Instance Graphs" e "Discovering Anomalous Frequent Patterns from Partially Ordered Event Logs". Nella cartella ProcessRepairing è possibile trovare le cartelle:
- scripts: contiene gli script Python che implementano l'algoritmo sopra discusso. In Repairing.py viene gestito il repairing del modello ad una sola sub mentre, in RepairingPattern.py viene gestito il repairing del modello mediante l'utilizzo di pattern di sub. In questa cartella sono presenti anche ulteriori script utili per generare la matrice delle occorrenze. È possibile inoltre trovare anche la cartella database la quale contiene tutti i file utili per la connessione al database locale.
- 'patterns_file_': in queste cartelle sono contenuti tutti i file facenti riferimento ai relativi dataset. Per lo sviluppo di questo progetto si è utilizzato in particolare il dataset patterns_file_testBank2000NoRandomNoise
Prima di mandare in esecuzione gli scripts prima citati, è necessario installare i seguenti tool:
- Installare la versione C di SUBDUE disponibile al seguente link. Posizionare gli eseguibili sgiso e gm generati nella cartella di dataset che si vuole testare;
- Installare le librerie Python PM4PY, pandas, IncrementalBar;
- Installare il tool XAMPP, verificare che il server mysql sia in run, importare il database presente nella cartella patterns_file_testBank2000NoRandomNoise e sostituire il contenuto della tabella traceId con il contenuto del file traceIdMapping. Controllare che il file connect.py sia conforme rispetto alle credenziali e alla porta in uso;
- Installare il software VirtualBox: è necessario predisporre una macchina virtuale per tutti coloro che non possiedono un sistema operativo macOS o qualsiasi altro sistema Unix-like per mandare in esecuzione il programma. Gli sviluppatori consigliano una macchina virtuale con sistema operativo openSUSE oppure Ubuntu.