Learning Outcomes

In this project, you will demonstrate your understanding of dynamic memory and linked data structures (Chapter 10) and extend your program design, testing, and debugging skills.  You will also learn about the problem of process discovery and implement a simple algorithm for discovering a process model from event data.

Process Discovery

Process mining is a relatively young research discipline that combines studies of inferences from data in data mining and machine learning with process modeling and analysis to discover, monitor, and improve real-world processes. The studied processes get formally captured in process models.

Figure 1 shows an example process model captured in Business Process Model and Notation (BPMN) language.  In the figure, actions are drawn as rectangles with rounded cor- ners. Diamonds represent gateways. An exclusive gateway has the “x” marker, while a parallel gateway has the “+” marker inside the diamond shape.  Directed arcs encode control flow dependencies. The circles with thin and thick borderlines de- note the start and end of the process, respectively.

A process model describes a collection of possible exe- cutions, or traces.  A trace is a sequence of events that rep- resent actions encountered when following control flow arcs

Figure 1: A process model.

and gateway routing decisions from the start to the end element of the model.  If execution reaches an ex- clusive gateway, it continues along exactly one of its outgoing arcs.   If execution reaches a parallel gate- way with multiple outgoing arcs, all the outgoing arcs are followed simultaneously.  A parallel gateway with multiple incoming arcs “waits” for all the incoming arcs to complete and then “passes” the execution to its outgoing arcs.   The fact that several paths in a model are executed simultaneously means that the ac- tions encountered on these paths are independent and can occur in any order.  According to these rules, the model in Figure 1 describes exactly three traces:  (a, b, c, d) , (a, b, e, f), and (a, b, f, e) .  For simplicity, the model in Figure 1 uses abstract action labels.  In practice, actions usually “wear” meaningful labels to de- scribe, for example, a business process or a distributed algorithm.  For instance, the process model from Fig- ure 1 with labels a =“receive loan application ”, b =“assess loan application ”, c =“reject loan application ”, d =“close loan application ”, e =“approve loan application ”, and f =“offer additional products ” describes some bank’s loan application handling process.

In the real-world, different loan applications can be processed by following the same sequence of actions; thus, a trace can be observed multiple times.  The problem of process discovery is a core problem in process mining that, given an event log, that is, a collection of observed traces, aims to automatically construct a process model that describes the traces.  A process model constructed in this way aims to aggregate and generalize information on how processes were executed in the real-world. Process analysts can then use this constructed process model to understand real-world processes, identify interesting and problematic patterns of actions, and use the model as a starting point for redesigning and improving the processes.

In this assignment, you will implement a program that reads an event log from input, analyzes patterns of actions in the input traces, and discovers and reports model fragments that could have produced the traces.

Input Data

Your program should read input from stdin and write output to stdout. The input will list traces, one per input line, where each trace is provided as a comma-separated list of events that terminates either with “/n”, that is, one newline character, or EOF, that is, the end of file constant defined in the header file. An event is encoded as a single alphabetic character that when provided as input to the isalpha() function defined in the  header file returns a non-zero integer.

The following file test0 .txt uses fifteen lines to specify fifteen traces, each composed of four events.

In general, input data can contain an arbitrary number of traces, with each trace composed of at least one event.

Stage 0 – Reading, Analyzing, and Printing Input Data (10/20 marks)

The first version of your program should read an event log from input, analyze it, and print basic statistics about the event log to the output. The first thirteen lines from the listing below correspond to the output your program should generate for the test0 .txt input file in Stage 0.

1 ==STAGE  0============================ 26 d  =  7 51 258  =  CON(e,f)

2 Number  of  distinct  events:  6 27 e  =  8 52 Number  of  events  removed:  8

3 Number  of  distinct  traces:  3 28 f  =  8 53 256  =  15

4 Total  number  of  events:  60 29 256  =  15 54 257  =  7

5 Total  number  of  traces:  15 30 ===================================== 55 258  =  8

6 Most  frequent  trace  frequency:  7 31 c        d        e        f    256 56 =====================================

7 abcd 32 c        0        7        0        0        0 57 256    257    258

8 a  =  15 33 d        0        0        0        0        0 58 256        0        7        8

9 b  =  15 34 e        0        0        0        4        0 59 257        0        0        0

10 c  =  7 35 f        0        0        4        0        0 60 258        0        0        0

12 e  =  8 37 62 259  =  CHC(257,258)

13 f  =  8 38 257  =  SEQ(c,d) 63 Number  of  events  removed:  0 14 ==STAGE  1============================ 39 Number  of  events  removed:  7 64 256  =  15

15 a        b        c        d        e        f 40 e  =  8 65 259  =  15

16 a        0      15        0        0        0        0 41 f  =  8 66 =====================================

17 b        0        0        7        0        4        4 42 256  =  15 67 256    259

18 c        0        0        0        7        0        0 43 257  =  7 68 256        0      15

19 d        0        0        0        0        0        0 44 ==STAGE  2============================ 69 259        0        0

20 e        0        0        0        0        0        4 45 e        f    256    257 70 -------------------------------------

21 f        0        0        0        0        4        0 46 e        0        4        0        0 71 260  =  SEQ(256,259)

23 256  =  SEQ(a,b) 48 256        4        4        0        7 73 260  =  15

24 Number  of  events  removed:  15 49 257        0        0        0        0 74 ==THE  END============================

25 c  =  7 50 ------------------------------------- 75

Lines 2 and 3 of the output report the number of distinct events and traces in the event log, respectively. The event log contains six distinct events, a through f, and three distinct traces, (a, b, c, d) , (a, b, e, f), and (a, b, c, d) . Lines 4 and 5 of the output report the total number of events and traces in the event log.  As there are fifteen traces in the log, each composed of four events, in total, there are sixty events in the event log. Line 6 provides information about the number of times the most frequent trace appears in the event log. Trace (a, b, c, d) is the most frequent trace; it appears seven times in the event log. The subsequent lines of the output should list all most frequent traces of the event log (one occurrence of each trace). If there are multiple traces with the same maximum frequency, they should all be listed, one per line, in lexicographical order, where uppercase characters precede all lowercase characters. Each trace should be printed as a string composed of characters that encode trace events in the order the events appear in that trace. As there is only one most frequent trace in the example input event log, it is printed on line 7; see the abcd string. In the following lines, see lines 8 to 13, your program should report all the events that appear in the event log, one per line, in ascending order of the corresponding ASCII codes, with information on how many times they appear in the event log.

You should not make assumptions about the maximum number of traces and events supplied. Use dynamic memory and data structures of your choice, for example, arrays or linked lists, to store the input event log.

The test input will always follow the proposed format.

Stage 1 – Identifying Sequences (16/20 marks)

Extend your program from Stage 0 to identify the most likely sequential (SEQ) patterns of actions based on the directlyfollows relationships between events in the event log. Two events are in the directly follows relationship if there is a trace in the log in which these events appear consecutively. First, your program should compute and print out all the directly follows relationships.  Lines 15 to 21 of the output listing report the directly follows relationships between the events together with their support, that is, the number of times the events follow each other in the traces of the event log, given as a two dimensional matrix. For example, event b directly follows event a once in each trace of the event log. Thus, its support is 15; see 15 in the third column of line 16 of the output; that is, sup(a, b) = 15. Each matrix column uses five characters, and each cell entry is right-justified.