## 3 Process Discovery over Uncertain Data  
Process discovery is another main objective in process mining, and involves automatically creating a process model from event data. Many process discovery algorithms rely on the concept of _directly-follows relationships_ between activities to gather clues on how to structure the process model. _Uncertain Directly-Follows Graphs_ (UDFGs) enable the representation of directly-follows relationships in an event log under conditions of uncertainty in the event data; they consist of directed graphs where the activity labels appearing in an event log constitute the nodes, and the edges are decorated with information on the minimum and maximum frequency observable for the directly-follows relation between pair of activities. Let us examine an example of UDFG. To build a significant example, we need to introduce an entire uncertain event log; since the full table notation for uncertain traces becomes cumbersome for entire logs, let us use a shorthand simplified notation. In a trace, we represent an uncertain event with multiple possible activity labels by listing all the associated labels between curly braces. When two events have mutually overlapping timestamps, we write their activity labels between square brackets, and we indicate indeterminate events by overlining them. Notice that this notation does not allow for the representation of every possible uncertain trace: in the case of timestamp uncertainty, it can only express mutual overlapping of time intervals. However, this notation is adequate to illustrate an example for process discovery under uncertainty. For instance, the trace \(\langle\overline{a},\{b,c\},[d,e]\rangle\) is a trace containing 4 events, of which the first is an indeterminate event with activity label \(a\), the second is an uncertain event that can have either \(b\) or \(c\) as activity label, and the last two events have an interval as timestamp (and the two ranges overlap). Let us consider the following event log: \(\langle a,b,e,f,g,h\rangle^{80},\langle a,\{b,c\},[e,f],g,i\rangle^{15},\langle a,\{b,c,d\},[e,f],g,\overline{j}\rangle^{5}\). For each pair of activities, we can count the minimum and maximum occurrences of a directly-follows relationship that can be observed in the log. The resulting UDFG is shown in Figure 4.  
This graph can be then used to discover process models of uncertain logs via process discovery methods based on directly-follows relationships. In a previous work [8] we illustrated this principle by applying it to the Inductive Miner, a popular discovery algorithm [9]; the edges of the UDFG can be filtered via the information on the labels, in such a way that the final model can represent all possible behavior in the uncertain log, or only a part. Figure 5 shows some process models obtained through inductive mining of the UDFG, as well as a description regarding how the model relate to the original uncertain log. UDFGs of uncertain event data are obtained on the basis of the behavior graphs of the traces in an uncertain event log, making their construction a necessary step to perform uncertain process discovery. In fact, the frequency information labeling the edges of UDFGs are obtained through a search among the possible connections within the behavior graphs of all the traces in an uncertain log. Figure 4: The _Uncertain Directly-Follows Graph_ (UDFG) computed based on the uncertain event \(\log~{}\langle a,b,e,f,g,h\rangle^{80}\), \(\langle a,\{b,c\},[e,f],g,i\rangle^{15}\), \(\langle a,\{b,c,d\},[e,f],g,f\rangle^{5}\). The arcs are labeled with the minimum and maximum number of directly-follows relationship observable between activities in the corresponding trace. Notice the large amount of connections extracted from a single and rather short trace. Uncertain directly-follows relationships are inferred from the behavior graphs of the traces in the log. The construction of this object is necessary to perform automatic process discovery over uncertain event data.