# Event Log Preprocessing for Process Mining: A Review
## 3 Research Methodology
### C5. Related Tasks
#### 3.6.2 Alignment  
Alignment requires that the events in the log are correlated with the activities in the process model, and the discrepancies and conformance degrees between a log and a model can be determined. Alignment is not only relevant for the conformance checking task, but also for event log repairing and model repairing. On the one hand, the event log repairing concentrates on repairing event sequences according to a predefined process model, while model repairing focuses on repairing the necessary parts of the process model, such that it can replay event sequences in the log [75].  
A sequential alignment between a trace and a process model is defined as a sequence of moves, each relating an event in the trace to an activity in the model. A cost function assigns a cost to each possible move. A sequential alignment with the lowest cost, according to the cost function is an optimal alignment. Unfortunately, the problem of finding the optimal alignment is NP-hard [96]. This indicates that when the process is large, it is intractable to determine the optimal alignment. The optimal alignment occurs when a trace in the log and an occurrence sequence in the model have the shortest edit distance.  
[PERSON] et al. [68] present a cost-based alignment approach to repair missing entries in the logs. The authors employ probabilistic filtering models to derive the most likely timestamp of missing events using path probabilities and stochastically enriched process models. Bayesian networks are used to capture the dependencies between the random durations by a stochastic Petri net.  
[PERSON] et al. [71] propose an approach for recovering missing events in process logs by decomposition of process into different sub-processes and heuristics to prune unqualified sub-processes that fail to generate the minimum recovery. In order to reduce the redundant recoveries in regard to parallel routings, the authors use an algorithm that leverages trace replaying to efficiently find a minimum recovery.  
[PERSON] et al. [67] propose a conformance checking approach based on the principle of finding an alignment of a given event log and its corresponding process model. The A* algorithm is used to find, for each trace in the event log, an optimal alignment, i.e., an alignment that minimizes the cost of the deviations. The authors adapt alignment-based approaches to be able to deal with the large search spaces induced by the inherent flexibility of declarative models. Based on such alignments, they provide diagnostics, at the trace level, showing why events need to be inserted/removed in a trace, and at the model level, coloring constraints, and activities in the model based on their degree of conformance.  
In [75], the authors use the structural and behavioral features of process models, effective heuristics based on process decomposition and trace replaying to reduce the search space for the optimal alignment. They use a divide-and-conquer strategy. The alignment requires that the events in the log are correlated with the activities in the process model. A general framework is developed to seek the optimal alignment between process models and event logs with missing, redundant, and dislocated events and activities, respectively. This framework is not only used to align event logs with process models, but is also utilized for repairing event logs. Their approach is realized in the tool Effa, which acts as a plugin of ProM. Some other works on alignment are presented in [63; 66; 70].