Operational support assists users while process instances are being executed, by making predictions about the instance completion, or recommending suitable actions, resources or routing decisions, on the basis of the already completed process traces. Operational support can be particularly useful is the case of medical processes, where a given process instance execution may di er from the indications of the existing reference clinical guideline. In this paper, we propose a Case Based Reasoning approach to medical process management operational support. The framework enables the user to retrieve past traces by submitting queries representing complex patterns exhibited by the current process instance. Information extracted from the retrieved traces can guide the medical expert in managing the current instance in real time. The tool relies on a tree structure, allowing fast retrieval from the available event log. Thanks to its characteristics and methodological solutions, the tool implements operational support tasks in a exible, e cient and user friendly way.
Operational support is a process management activity meant to assist users while
process instances are being executed, by making predictions about the instance
completion, or recommending suitable actions, resources or routing decisions, on
the basis of the already completed instances [
In this paper we propose a case-based retrieval framework, where cases are
traces of process execution, aimed at enabling prediction and recommendation in
medical process operational support. In our framework, queries can be composed
of several simple patterns (i.e., single actions, or direct sequences of actions),
separated by delays (i.e., interleaved actions we do not care about). Delays can
also be imprecise (i.e., the number of interleaved actions can be given as a range).
To the best of our knowledge, an operational support facility like this is not
available in the tools described in the literature. Our framework relies on a tree
structure, called the trace tree, allowing fast retrieval, thus avoiding a at search
for all the traces in the log that match the input pattern. The trace tree is a
sort of \model" of the traces, that we learn using a process mining technique we
recently implemented [
The paper is organized as follows. In section 2 we illustrate our retrieval approach. In section 3 we discuss related work. In section 4 we present our concluding remarks and future work directions. 2
In our framework, trace retrieval relies on a tree structure, called the trace tree, in order to avoid a at search for all the traces in the log that match the input query. In the following, we will rst describe the trace tree semantics, and then introduce our query language and, nally, our retrieval procedure. Trace tree semantics. In the trace tree, nodes represent actions, and arcs represent a precedence relation between them. More precisely, each node is represented as a pair < P; T >.
P denotes a (possibly unary) set of actions; actions 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 starting 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 trace tree, and ordering in each possible way the actions in each node (for instance, the path fA; Bg ! fCg represents the support patterns \ABC" and \BAC").
T represents a set of pointers to all and only those traces in the log whose
pre xes exactly match one of the patterns in P (called support traces henceforth).
Speci cally, pre xes correspond to the entire traces if the node at hand is a leaf.
In the case of a node representing a set of actions to be executed in any order, T is
1 While the motivations for de ning such a novel mining algorithm, and its advantages
with respect to existing process mining literature contributions (e.g., ProM [
Since all traces start with a dummy common action #, the root node contains the action #, paired to the pointers to all log traces.
Query language. In a tool implementing this framework, the user can issue a query, composed of one or more simple patterns to be searched for. In turn, simple patterns are de ned as one or more actions in direct sequence. Multiple simple patterns can be combined in a complex pattern, by separating them by delays. A delay is a sequence of actions interleaved between two simple patterns; the semantics is that we do not care about these actions, so they will not be speci ed in the query. Instead, only their number will be provided, possibly in an imprecise way (i.e., we allow the user to express the number of interleaved actions as a range).
Formally, a query is represented in the following format: h(min1; max1)SP1(min2; max2)SP2:::(mink; maxk)SPk(mink+1; maxk+1)i where: { SPj is a simple pattern (i.e. a sequence of letters, representing the actions we are looking for; these actions have to be in direct sequence); { (minj ; maxj ) is the delay between two items (i.e., two simple patterns, or a simple pattern and the trace starting/ending point), expressed as a range in the number of interleaved actions.
As an example, the query h(0; 0)B(0; 1)E(2; 2)Z(0; 1)i looks for action B, which has to start at the very beginning of the trace (just after the start action # - all traces start with a dummy common action # in our approach). This rst simple pattern B must be followed (with zero or a single interleaved action in between) by action E. E must be followed by two actions, which we do not care about; after them, Z is required. Z can be the nal action, or can be followed by one additional action we do not care about.
For instance, in the stroke management domain, where we will test our approach, actions B, E and Z could correspond to \Arrival at the emergency department", \Neurological examination", and \Chest X-ray" respectively. Looking for \Arrival at the emergency department" at the very beginning of the trace allows the exclusion of all those patients that were rst stabilized at home or in the ambulance. The query then aims for searching for those situations where \Neurological examination" is executed early, and before \Chest X-ray"; in fact, this speci c ordering is not mandatory, because \Chest X-ray" is a procedure common to many di erent disease management processes, and may be executed at di erent times, also depending on the availability of the X-ray machine. Similarly, in some cases \Neurological examination" might be delayed, if the neurologist is not available. The two actions between \Neurological examination" and \Chest X-ray" would typically correspond to \CTA" and \ECG", always obtained to every patient in the case of a suspected stroke (but not explicitly queried in the example).
It is worth noting that a query written as above corresponds to a whole set of queries, each one obtained by choosing a speci c delay value and speci c actions in each of the (minj ; maxj ) intervals. Every query in this set can be made partially explicit as a string, containing as many dummy symbols as needed, to cover the corresponding delay length (where the dummy symbol is chosen because we are not interested in the speci c interleaved actions). For example, the query above would correspond to the following four partially explicit queries, whose length ranges from 6 to 8 actions (including #), where the dummy symbol has been properly inserted, according to the delay values information: #BE Z; #BE Z ; #B E Z; #B E Z
Since each could be substituted by any of the N types of actions recorded in the log and/or existing in the application domain, the example query corresponds to N 2 + 2 N 3 + N 4 totally explicit queries.
The problem is obviously combinatorial, with respect to the possible delay ranges and action types. We thus believe that extensional approaches (in which only explicit queries can be issued) would not be feasible in many domains. Our query language, allowing for compact \intensional" queries, is therefore a signi cant move in the direction of implementing an e cient and user-friendly operational support tool.
Trace retrieval. In order to retrieve the log traces that match a query, we have implemented a multi-step procedure, articulated as follows: (1) automaton generation; (2) tree search; (3) ltering.
To generate the automaton, in turn, we implement the following procedure:
1. transform the query into a regular expression;
2. apply the Berry and Sethi [
Steps (1) and (4) are trivial. As regards step (1) note that our query language
is just a variation of regular expressions, useful to express delays and \do not
care" (i.e., dummy) symbols in a compact way. The cost of step (1) is linear in
the number of delays used in the query. Steps (2) and (3) use classical algorithms
in the area of formal languages. The cost of step (2) is linear in the number of
symbols in the query expressed as a regular expression (i.e., the output of step
(1) [
Once the deterministic automaton has been obtained, it would be possible to exploit it in a classical way, by providing all event log traces in input to it, to verify which of them match the query. However, some of these traces may be identical, or share common pre xes of various length, so that the straightforward approach would lead to repeated analyses of the common parts. In order to optimize e ciency, we have therefore proposed a novel approach, that provides the trace tree as an input to the automaton. Each path in the trace tree may index several identical support traces, that will be considered only once, thus speeding up retrieval with respect to a at search into the event log. Moreover, in the tree common pre xes of di erent traces are represented just once, as common branches close to the root (di erent post xes can then stem from the common branches, to reach the various leaves). These common parts will be executed on the automaton only once, without requiring repeated, identical checks.
It is worth noting that providing a tree as an input to the automaton
represents a signi cantly novel contribution, since in the formal languages literature
the input to be executed on the automaton is typically a string. The work in
[
In detail, our approach operates as follows: the algorithm Search P rocess (see algorithm 1) takes in input the trace tree T and the deterministic automaton A, and provides as an output a set of pairs, composed of a trace tree leaf node and a corresponding string. Notably, there could be several pairs having the same leaf node. Each of the strings is an explicit instantiation of the query represented by the automaton, veri ed by (some of) the support traces in the leaf node. The output support traces are then provided as an input to the ltering step (see below).
Basically, Search P rocess executes a breadth rst visit of the trace tree; it exploits the variable searching, de ned as a set of triples, composed of a trace tree node, an automaton state, and the string that has been recognized on the automaton so far. Initially (line 4), searching contains the root (with the dummy action #), paired to the initial state of the query automaton and to the empty string. The visit procedure (lines 7-35) extracts one triple at a time from the set searching. If the node in the triple contains a set of actions to be executed in any order (line 9), we simulate all the permutations on the automaton, and save the states we reach and the corresponding recognized strings into new states set (line 12). If the node contains one single action, we simply simulate it on the automaton, and save the state we reach and the corresponding string into new states set (line 17). In both cases, the string saved in new states is the one in the input triple properly updated with the newly recognized symbols.
After the simulation, if the node at hand is a leaf (line 20), then for each item in new states we check whether the state component is a nal state (lines 22-24); if this is the case, node and the string paired to the nal state are saved in the output variable result (line 23). Otherwise, if node is not a leaf, we pair its children to all the items in new states, and save these objects into searching (lines 27-33). The visit terminates when searching is empty, i.e., all tree levels have been visited. The visit procedure is linear in the number of the trace tree nodes.
Referring to our example query, providing the trace tree in gure 1 as an input to the algorithm Search P rocess, after examining the root (which is triv
ALGORITHM 1: Pseudo-code of the procedure Search P rocess. ial), searching contains the children of the root A, B, and C, paired with the state of the deterministic automaton, and with the string #. We simulate the actions A, B, and C on the automaton. Only B (i.e., \Arrival at the emergency department") is recognized, generating a state saved in new states with the corresponding string #B (line 17). We then pair the children of node B (E, D, D E) to the item in new states and save these triples into searching (lines 27-33). In the stroke management domain, E corresponds to \Neurological examination" and D to \CTA". Continuing the visit, particularly interesting is the case of node D E, which requires consideration of all the possible permutations of actions D and E. Both the permutations DE and ED are initially recognized. However, as the visit proceeds and node P Z is reached (with P corresponding to \ECG" and Z corresponding to \Chest X-ray"), it turns out that DE must be followed by the permutation P Z to match the query; on the other hand, if the choice ED is made, it must be followed by ZP . Indeed, the query imposes some constraints that cannot be checked only locally, i.e., referring to a single node along the branch. After this step of the visit (depth 5 in the tree), the recognized partial strings paired to node P Z are #BDEOP Z and #BEDOZP (with O corresponding to \NMR"). Notably, the patterns #BDEOZP and #BEDOP Z do not match the input query.
If an output leaf node ends a branch which includes one or more nodes with actions to be executed in any order, it is possible that only some of the permutations of these actions are acceptable to answer the query. However, the trace tree leaf node indexes all the traces corresponding to the various support patterns (i.e., considering all possible permutations). Therefore, the support traces must be ltered.
To do so, without the need of operating directly on the input traces, we exploit the fact that, in each node with actions to be executed in any order, every permutation is explicitly stored, and each permutation indexes all and only the support traces corresponding to it. Thus, the basic idea of our ltering step is simple: for each output pair h Node, String i of the tree search step, we navigate the trace tree from N ode back to the root, maintaining, in each any order node, only the (pointers to) the traces corresponding to String (this can be easily done through the operation of intersection between sets of pointers).
The complexity of the ltering step is superiorly limited by the number of h Node, String i pairs identi ed as an output of the tree search step, multiplied by the tree depth.
Obviously, if the leaf node ends a branch that contains no nodes with actions to be executed in any order, the leaf support traces can be directly presented to the user, and the ltering step is not required. 3
Operational support techniques are implemented in the open source framework
ProM [
On the other hand, traces have been recently considered in the CBR
literature, as sources for retrieving and reusing user's experience. As an example, at
the International Conference on CBR in 2012, a speci c workshop was devoted
to this topic [
All these approaches implement forms of reasoning on traces. However, to the best of our knowledge, a tace-based CBR approach has never been exploited for operational support in Medical Process Management. 4
In this paper, we have introduced a novel framework for trace retrieval, designed to implement operational support tasks in a exible, e cient and user-friendly way. With respect to existing operational support facilities, our tool is more exible because it allows to search for traces that exhibit complex query patterns, identi ed in the input trace. The tool is also e cient and user-friendly, since: { by allowing for the use of (imprecise) delays in the query language, it enables users to express a very large number of explicit queries in a compact way; { by providing the trace tree as an input to the automaton: it speeds up retrieval relative to a at search into the event log; it executes common pre xes of di erent traces only once on the automaton, avoiding repeated, identical checks.
In the future, we plan to extensively test the overall framework on real world traces, which log the actions executed during stroke patient management in a set of Northern Italy hospitals.