Różnice

Różnice między wybraną wersją a wersją aktualną.

Odnośnik do tego porównania

Both sides previous revision Poprzednia wersja
Nowa wersja
Poprzednia wersja
pl:dydaktyka:dss:lab03 [2018/10/22 01:37]
kkluza [Excercise]
pl:dydaktyka:dss:lab03 [2020/11/16 17:57] (aktualna)
kkluza [Report]
Linia 1: Linia 1:
-====== Simplified ​alpha algorithm ======+====== Simplified ​Alpha algorithm ======
  
-Let's consider the following traces (variants) ​in the log:+During this and the next laboratory, we will discuss a simple process mining solution.  
 +For this purpose, the widely known Alpha algorithm was simplified and adjusted to discover a BPMN process model. 
 + 
 +Let's consider the following traces (variants) ​of some workflow ​log:
 <​code>​ <​code>​
 a b c d e g a b c d e g
Linia 9: Linia 12:
 </​code>​ </​code>​
  
-For this workflow log, based on the Alpha algorithm, we can find the following relations:+For this workflow log, based on the Alpha algorithm, we can find the following relations ​(x,y - events): 
 +  * (>) direct succession: x>y iff for some case x is directly followed by y, 
 +  * (->) causality: x->y iff x>y and not y>x, 
 +  * (||) parallelism:​ x||y iff x>y and y>x, 
 +  * (#) choice/​unrelated/​no direct succession: x#y iff not x>y and not y>x. 
 + 
 +In the below implementation,​ we do not use directly "no direct succession"​ relation, as it can be just checked if there is causality or parallelism instead.
  
 <​code>​ <​code>​
Linia 40: Linia 49:
 </​code>​ </​code>​
  
-For the purpose of coding, we can also define the inverted causality for the events in causality relation which have more than one successor (this is not the part of the alpha algorithm itself, but can be helpful as temporary variable for using the alpha mining patterns):+For the purpose of coding, we can also define the inverted causality for these events in causality relation which have just one successor (this is not the part of the alpha algorithm itself, but can be helpful as temporary variable for using the alpha mining patterns):
  
 <​code>​ <​code>​
Linia 51: Linia 60:
 Next, use the following code to generate a simple BPMN process model: Next, use the following code to generate a simple BPMN process model:
  
-<code python ​bpmnalpha.py>+<code python ​bpmnalphatemplate.py>
 import graphviz import graphviz
  
Linia 152: Linia 161:
 G.view('​simple_graphviz_graph'​) G.view('​simple_graphviz_graph'​)
 </​code>​ </​code>​
 +
 +====== Alpha Plus ======
 +
 +Alpha+ is a simple extension of Alpha algorithm which can deal with short-loops and self-loops.
 +
 +In the picture below, the models on the left-hand side are the models discovered by Alpha algorithm. The models on the right-hand side are the models which could be discovered using Alpha+ algorithm. ​
 +
 +{{:​pl:​dydaktyka:​dss:​lab:​alpha-plus-issues.png?​600|}}
 +
 +On the UPEL platform, there are articles about the algorithms that use Petri nets. There is no simple translation from the Petri nets to BPMN, however, you for Alpha+, the situation is similar like in the case of Heuristic miner (presented during the lecture).
 +
 +So for discovering self-loops and short loops, you need to construct the additional matrix and exclude the discovered relations from the footprint matrix of the Alpha algorithm.
 +
 +^ | a | b | c | ... | 
 +| aτa |  | ✓ |  | |
 +| bτb |  |  |  | |
 +| cτc |  |  |  | |
 +| ... |  |  |  | |
  
 ====== Excercise ====== ====== Excercise ======
Linia 171: Linia 198:
 </​code>​ </​code>​
  
-Calculate (first manually, ​than in Python) the causality relations, determine parallel events as well as the set of start and end events, and try to discover the BPMN process model.+Calculate (first manually, ​then in Python) the causality relations, determine parallel events as well as the set of start and end events, and try to discover the BPMN process model
 + 
 +<fc #​ff0000>​Warning</​fc>:​ Alpha miner was originally invented to discover Petri net, so discovering directly BPMN with it is not straightforward. However, it shows the basic process mining idea and allows to notice some theoretical limits of process mining. Thus, Alpha miner is only of theoretical interest as it is too simple to be applicable to real-life logs. 
 +  * It does not address various issues such as noise, frequency etc. 
 +  * It has problems with some control-flow constructs (e.g. is not able to discover some kinds of structures like short loops, but also with some more complex structures). 
 +  * It does not allow for duplicate events in the trace. 
 +  * It can discover inconsistent models. 
 + 
 +====== Report ====== 
 + 
 +<fc #​ff0000>​**This lab will be conducted 26.10.2020 and 2.11.2020.\\ The deadline for the report is <​del>​10.11.2020</​del>​ 23.11.2020**.</​fc>​  
 + 
 +** The lab on <​del>​9.11.2020</​del>​ 16.11.2020 will be only as consultation hours for people who want to consult their mini-project concerning the implementation of Heuristic miner or some other advanced miner**.  
 + 
 +<fc #​ff0000>​**On the UPEL platform, you can find some log examples of various complexity**:​\\ 
 +https://​upel2.cel.agh.edu.pl/​weaiib/​mod/​resource/​view.php?​id=40748 
 +\\ 
 +Be aware that not for all of these logs you will be able to get a correct solution, as some of the constructs may not be supported by your algorithm. However, as the provided logs are quite simple, it should be easy to check your solutions using them. 
 +</​fc>​ 
 + 
 +The basic report should contain: 
 +  - a python file or an ipython notebook implementing the algorithm,​ 
 +  - an example input file for the implementation,​ 
 +  - a short pdf report on the using of the implementation and the results for the provided example, with some discussion of the interesting elements of your implementation. 
 + 
 +For 3 points (i.e. satisfactory grade 3.0):  
 +  * It is required to provide the implementation of the Alpha algorithm which may mostly be based on the code from the lab instruction.  
 + 
 +For 4 points (i.e. good grade 4.0):   
 +  * It is required to provide your implementation of any extension of the Alpha algorithm (e.g. Alpha+, elements of Alpha++ or Alpha#) which may be based on the code from the lab instruction.  
 + 
 +For 5 points (i.e. very good grade 5.0) [mini-project]: ​  
 +  * **It is required at least one consultation on <​del>​9.11.2020</​del>​ 16.11.2020** (or other date according to the individual arrangement). ​  
 +  * It is required to provide your implementation of Heuristic miner based on the previous implementation of an extension of the Alpha algorithm. 
 +  * It is also possible to choose some other advanced miner like ILP Miner, Split Miner, Evolutionary Tree Miner, Local Process Model Miner. For such a choice the extension of the deadline till the end of December is possible. In the case of correct implementation and evaluation of these complex miners, no other reports will be necessary and the final score will be 5.0 (bdb)
  
-<fc #​ff0000>​As ​the goal of this lab is to get understanding of Alpha mining algorithm, there is no report ​needed after this lab.</fc> But if you implement some other solution ​(e.g. Alpha+, Alpha++Alpha#, Heuristic ​or ILP miner)you will be able to present your work during ​the next class and get additional (extrapoints^_^ +Additional 0.5-1 point may be granted for the groups which will cover some of the following issues (this should be explained and justified in the report):  
 +  * Optimize the code in some smart way and justify ​this in the report 
 +  * Provide a better visualization for the BPMN process model (as the existing layout may not be suitable for some complex examplesso the group may enhance the layouting mechanism ​or use some external library for visualizing BPMN modelsand compare it to the simple mechanism provided in the lab instruction).
  
-<fc #​ff0000>​Warning</​fc>:​ Alpha miner was originally invented to discover Petri net, so discovering directly BPMN with it is not straightforward. Alpha miner is not good for real logs as it is not efficient and has many disadvantages (does not take into account the frequency of events, is not able to discover some kinds of structures like short loops). ​ 
  
pl/dydaktyka/dss/lab03.1540165022.txt.gz · ostatnio zmienione: 2019/06/27 15:57 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0