Medical process mining is gaining much attention in recent years, but the available mining algorithms can hardly cope with medical application peculiarities, that require to properly contextualize process patterns. Indeed, most approaches loose the connection between a mined pattern and the relevant portion of the input event log, and can have a limited precision, i.e., they can mine incorrect paths, never appearing in the input log traces. These issues can be very harmful in medical applications, where it is vital that mining results are reliable as much as possible, and properly reference the contextual information, in order to facilitate the work of physicians and hospital managers in guaranteeing the highest quality of service to patients. In this paper we propose a novel approach to medical process mining that operates in a context-aware fashion. We show on a set of critical examples how our algorithm is able to cope with the issues sketched above. The process model we mine can then be adopted to support e cient and exible trace retrieval, as described in [1]. Indeed, the model can be used as an indexing structure, well suited to quickly retrieve traces corresponding to the pattern being looked for. In the future, we plan to test the approach on a real-world medical dataset, taken from the stroke patient management domain.
Process mining describes a family of a-posteriori analysis techniques that exploit the so-called event log, which records information about the sequences (traces henceforth) of activities executed at a given organization. The most relevant and widely used process mining technique is discovery; process discovery takes as an input the event log and produces a process model, without using any a-priori information.
Despite the complexity of healthcare, medical process mining is a research
eld which is gaining attention in recent years (see, e.g., [2{4]), also as a means for
assessing the correct application of clinical guideline directives in practice. This
application domain indeed presents particular challenges and issues [
The currently available process mining solutions, ranging from commercial
tools (o ered, e.g., by Fujitsu Ltd and Celonis), to the open-source framework
ProM [
Speci cally, despite some di erences, many current algorithms show
important similarities (see Section 2), and have common limitations: (1) they learn
\context-free" patterns of processes; (2) they can mine paths that do not
correspond to any input trace in the log (i.e., they can have a limited precision [
Such limitations are quite relevant in general, and very relevant in the medical domain. Concerning limitation (1), it is well known that, e.g., the same (set of) activities may produce di erent e ects on patients, depending on the context (e.g., on the activities previously performed on the patients themselves). The impact of limitation (2) is obvious and dramatic: the mined model is the input for quality assessment procedures, such as veri cation of conformance with respect to clinical guidelines, or performance measurement and bottleneck detection. All these procedures will provide an unreliable output, if played on an unreliable input (in the sense that the model may exhibit a path that never appears in any input trace). However, surprisingly, limited precision is a common limitation of many current miners (see Section 2.) Limitation (3) is less critical, but still signi cant. Indeed, maintaining an explicit link between the mined patterns and the input traces matching such patterns, can be important not only to characterize contexts, but also to provide physicians with an evidence of the learned output.
In this paper, we propose an innovative approach that supports
contextaware process mining, and overcomes all the above limitations. Our mining
technique provides a process model in the form of a tree, called the \log-tree".
The log-tree perfectly adheres to the input traces (since all its paths correspond
to at least one trace in the log), and explicitly relates the mined patterns to
the log. Interestingly, in this way it can be exploited as an index, to e ciently
retrieve all the traces that contain the pattern of interest, along the lines of the
work in [
As discussed in the Introduction, several di erent miners have been developed in
the literature. However, many existing miners, including alpha miner [
In the following, for the sake of clarity and brevity, we will mainly refer to one miner to illustrate the common characteristics of these literature approaches. Speci cally, we will concentrate on heuristic miner. Indeed, heuristic miner can abstract from exceptional behavior and noise and, therefore, is suitable for many real-life logs, including medical ones.
Most mining algorithms are based on a common assumption, which we call uniqueness assumption: each event is unique in the output, so that each event appears at most once in the output of the process miner2.
As a second commonality, the mining methodology is typically based on two steps (corresponding to steps 1 and 3 in Algorithm 1 below, which abstractly characterizes the behavior of heuristic miner on a set T of traces): (i) a destructuring step, in which immediate precedence between pairs of events is detected in the input traces, and (ii) a re-structuring step, in which patterns of events are reconstructed, by combining the immediate precedence relations mined in the de-structuring step.
ALGORITHM 1: HM pseudocode
1 function HM(T) ;
2 (1) for each pair of events A and B do
3 search T to detect immediate precedence A ! B and B ! A
4 end
5 (2) Look for cycles of length one (same event repeated) or two (pair of events
repeated);
6 (3) for each triplet of events A,B, and C, such that A ! B and A ! C do
7 use formulae [
For the sake of brevity, here we cannot comment in detail the algorithm, and the formulae. We just focus on the main critical issues.
C1 Given the uniqueness assumption, the de-structuring step (step 1 in
Algorithm 1) evaluates the immediate precedence relations between events A
2 Actually, ProM's region-based miner [
C3 The uniqueness assumption imposes severe constraints on the re-structuring step.
The following examples illustrate the critical impact of issues C1, C2 and C3. The examples have been processed using heuristic miner, and provided as Petri Nets, which are commonly assumed as an incontestable formalism to represent (the semantics of) processes.
To simplify the presentation, with no loss of generality, we suppose that each trace is pre xed with a distinguished starting symbol (*) and post xed with another distinguished ending symbol (#).
(a) Example 1 (b) Example 2 part a (c) Example 2 part b
(d) Example 3
the (unique!) pattern. In this example, this is mainly due to the fact that the uniqueness assumption causes problems in the re-structuring phase (critical issue C3): the two occurrences of the event A in the traces must correspond to a unique transition in the output Petri Net. Thus, a cycle (returning from C to A) must be introduced in the output. Notably, the output Petri Net also admits patterns like *A# or *ABCABCA#, which are not present in any of the input traces (see Figure 1(a)).
The pattern shown in this example represents one of the typical care processes
for patients su ering from acute diseases. For instance, consider the diagnostic
process of patients su ering from cerebral ischemia. After the symptom onset,
the patient arrives at the emergency ward of the hospital. According to the
latest medical guidelines for the treatment of stroke [
In a similar manner, each of the following examples, presented only in an abstract way due to lack of space, introduces situations which can be concretely instantiated as real clinical processes, or parts of them.
Ex.2 Log content: 1000 equal traces: *ABCBA# This example highlights the limitations of \context-free" approaches. Consider, in particular, critical issue C1 above: since the precedence relations are searched without considering the context (and on the basis of the uniqueness assumption), there is no way to decide whether A precedes B (100% of traces, considering the rst part of the traces) or B precedes A (100% of traces, but considering the last part of the traces), and analogously for the relation between B and C. As a consequence, two separate Petri Nets are learned: the rst contains only the pattern *A#, while the second contains a loop composed by C and B (see Figure 1(b)). By using heuristic miner without the \all event connected option", a di erent model is learned (see Figure 1(c)), where it is possible to replay the input trace, but many other never observed behaviors can be generated as well.
sumption causes undesired e ects. In this example, two di erent patterns should be mined. However, during the de-structuring phase, no distinction is made between D in the rst type of traces (i.e., D in the context of being preceded by *A) and D in the second type of traces (i.e., D in the context of being preceded by *). Thus, the re-structuring phase (see critical issue C2) generates a \merging" between the two di erent patterns (due to the uniqueness of D), providing the Petri Net in Figure 1(d) as output. Notably, besides the correct patterns *AD# and *DB#, the output Petri Net also models the patterns *D# and ADB#, which do not correspond to any trace in the input log. 3
In order to overcome the limitations illustrated in the previous section, we propose an innovative approach to (medical) process mining, which is based on quite a di erent philosophy: in our methodology, process mining heavily takes into account contextual information, both in the data structure, and in the mining algorithm. Our approach is based on three main ideas: { in the data structure, we remove the uniqueness assumption: the same event may appear more than once in the output model, to represent the fact that it may occur in di erent contexts; { in the data structure, and in the mining algorithm, we explicitly maintain the context, i.e., the set of log traces that support a given path in the mined model; { in the mining algorithm, we take advantage of the ordering of events in the log traces (which represents, indeed, the context in which each single event occurs) to directly mine the output model, without distinguishing between a de-structuring and a re-structuring phase.
In the following, we present our approach and its application to the previously discussed critical examples. 3.1
Our mining algorithm takes in input a log (set of traces). The log is represented by a matrix, in which each row is a trace. It outputs the mined process as a tree, called a \log-tree", in which nodes represent events (i.e., activities), and arcs represent a precedence relation between them. More precisely, in our model, each node is represented as a pair < P; T >: { P denotes a (possibly unary) set of events; events in the same node are in AN D relation, or, more properly, may occur in any order (with respect to each other). Note that, in such a way, each path from the root node of the tree to a given node N denotes a set of possible process patterns (called support patterns of N henceforth), obtained by following the order represented by the arcs in the path to visit the tree, and ordering in each possible way the events in each node (for instance, the path fA; Bg ! fCg represents the support patterns \ABC" and \BAC"); { T represents the context, i.e., a set of references to all and only those traces in the log which exactly match one of the patterns in P (called support traces henceforth).
Our mining algorithm (see Algorithm 2 below) builds the log-tree described as above.
ALGORITHM 2: Mining pseudocode 1 function Build-Tree(index,< P; T >) ; 2 nextP getNext(index+1, T) ; 3 if nextP not empty then 4 nextEvents XORvsAND (nextP, T) ; 5 for each node < P ′; T ′ > 2 nextEvents do 6 AppendSon(< P ′; T ′ >,< P; T >) ; 7 Build-Tree(index + jP ′j,< P ′; T ′ >) ; 8 end 9 end
Build-Tree in Algorithm 2 takes in input a variable index, representing a given position in the traces (i.e., a column in the input matrix), and a node. Initially, it is called on the rst position, and on the root of the tree (which is a \dummy" node, corresponding to the * event; thus, initially, index=0, P=* and T is the set of all the traces). The function getNext simply inspects the traces in T to nd all possible next events (in the context T ). On the basis of the current context (support traces ) T, the function XORvsAND applies the formulae described in appendix A to identify which events are in AND and which are in XOR relation. The output of such a function is a set of nodes < P ′; T ′ >, one for each maximal set of events to be AND-ed. Note that, for each one of such sets P', the corresponding set T' of support traces is also computed, on the basis of the current context T. Finally, each new node is appended in the output tree (function AppendSon), and Build-Tree is recursively applied to each node (with the parameter index properly set).
A-posteriori, we create a dummy node #, and connect all the leaves to it; in this way, the log-tree can also be seen as a basic process model.
Notably, our mining algorithm explicitly manages the context, focusing at each step on the proper support traces, and always taking into account the global ordering of events in the traces to build the graph. As a consequence, di erently from the heuristic miner algorithm shown in Algorithm 1, we do not need any additional step to cope with long-distance dependencies (we have them \for free"). Analogously, we \naturally" cope with cycles by simply unfolding them. Thus, our algorithm already directly copes with cycles of any length (and no additional ad-hoc procedure for cycles is needed, di erently from the heuristic miner algorithm). 3.2
In Figure 2, we show the output of our miner, applied to the examples Ex.1-Ex.3
discussed in Section 2. Support traces are not reported in the gure, but are part
of the output itself. As it can be observed, the critical situations discussed in
Section 2 are all correctly managed by our approach. It is also worth noting that
our process graphs could be easily converted into Petri Nets.
Quite naturally, the log-tree is not only a model of the process at hand, but
also an index of the event log content, since, by means of the support traces,
it explicitly relates the mined patterns to the log. Indeed, as described in [
In this paper, we have introduced a novel process mining algorithm, able to overcome the limitations of many current approaches available in the literature. Speci cally, our algorithm: { learns \context-aware" patterns of processes; { has a high precision, since it provides patterns that always correspond to input traces in the log; { explicitly relates the mined patterns to the traces in the log \supporting" them. Our approach properly deals with critical situations that may occur in practical application domains, as illustrated by the examples in Section 2. These characteristics make the algorithm particularly well-suited for medical applications, where it is vital that mining results are reliable as much as possible, in order to facilitate the work of physicians and hospital managers in guaranteeing the highest quality of service to patients.
The mined process model can also be exploited to allow e cient trace
retrieval, as described in [
In the future, we plan to extensively test the overall approach on a real-world medical dataset, taken from the stroke patient management domain. In Algorithm 2, after nding the set of successors nextP of the considered set of events P , we focus on the discovery of the relation between them. In order to do this, we calculate the dependency frequency between every event pairs < A; B > in nextP nextP :
A ! B = ) (1) where jA > Bj is the number of traces in which A is immediately followed by B, and jA > Xj is the number of traces in which A is immediately followed by some event X, jY > Bj is the number of traces in which B is immediately preceded by some event Y. After evaluating the dependency frequency value A ! B and B ! A, we can have the following possible situations: