Master Thesis - Alignment Repair
Most organizations, in a variety of fields such as banking, insurance and healthcare, execute several different (business) processes. Modern information systems allow us to track, store and retrieve data related to the execution of such processes, in the form of event logs. Often, an organization has a global idea, or even a formal specification, of how the process is supposed to be executed. In other cases, laws and legislations dictate explicitly in what way a process is ought to be executed. Hence, it is in the company's interest to assess to what degree the execution of their processes is in line with the corresponding specification.
Conformance checking techniques, originating from the field of process mining, aim at solving the aforementioned problem. Conformance checking techniques allow us to quantify to what degree the actual execution of a process, as recorded in an event log, conforms to a corresponding process specification. Recently, alignments were introduced, which rapidly developed into the de-facto standard in conformance checking. The major advantage of alignments w.r.t. alternative conformance checking techniques, is the fact that deviations and/or mismatches are quantified in an exact, unambiguous manner.
When computing alignments, we convert a given process model, together with the behaviour recorded in an event log, into a synchronous product net and subsequently solve a shortest path problem on its state space. Typically, the well known A*algorithm is used as an underlying solution to the shortest path problem. Moreover, several (in some cases alignment-specific) parametrization options are defined and applied on top of the basic A* solution.
Computing alignments is a rather time consuming operation. At the same time, in a lot of application scenarios the models we need to compute alignments for, are structured, and, very similar. Therefore, researchers have recently worked on algorithms for alignment repair. In this work, given an existing alignment of an “old process model” and event data, we identify, for a “new process model”, where the given new process model deviates from the old model. Subsequently, we assess whether this difference requires us to revise the alignment, or whether the alignment is also accurate for the new model. If this is not the case, the old alignment is repaired.
The code of the alignment repair algorithm is not widely available. Moreover, the algorithm is in a very initial state of work, i.e. there is a lot of room for improvement. In this MSc. project, the student is therefore asked to implement and improve alignment repair in the process mining library pm4py. Note that, initially a set of existing definitions/algorithms needs to be implemented, after which the student is explicitly encouraged to define alternative solutions for alignment repair.
Knowledge of basic computer science concepts, good programming skills (Java/Python) and an interest in theoretical and practical aspects of process mining (i.e. conformance checking) recommended.
- Process Mining Book ()
- Coursera Process Mining Course ()
- (Paper) Replaying History on Process Models for Conformance Checking and Performance Analysis
- (Paper) “Tuning Alignment Computation: An Experimental Evaluation” ()
- (Paper) “Repairing Alignments: Striking the Right Nerve” ()
Prof.dr.ir. Wil van der Aalst
ir. Sebastiaan van Zelst
For more Information
Send an e-mail to Sebastiaan van Zelst. Make sure to include detailed information about your background and scores for completed courses.