Mining Process Variants: Goals and Issues (Short Paper) [original]

Mining Process Variants: Goals and Issues

Chen Li

University of Twente

The Netherlands

[email protected]

Manfred Reichert

University of Ulm

Germany

[email protected]

Andreas Wombacher

University of Twente

The Netherlands

[email protected]

Abstract

Recently, Process-Aware Information Systems (PAIS)

were introduced, which allow for dynamic process and ser-

vice changes. This, in turn, has led to a large number of pro-

cess model variants, which are difficult to maintain and ex-

pensive to configure. This paper deals with goals and issues

related to the mining of process model variants. Our over-

all goal is to learn from process changes and to ”merge”

the resulting model variants into a generic process model

in the best possible way. By adopting this generic process

model in the PAIS, future cost of process change and need

for process adaptations will decrease.

1 Introduction

In today’s dynamic business world success of an enter-

prise increasingly depends on its ability to react to inter-

nal and external changes in a quick and flexible way. In

response to this need, Process-Aware Information Systems

(PAIS) emerged, which support the modeling, orchestration

and monitoring of business processes. Recently, a new gen-

eration of flexible PAIS (e.g. ADEPT2 [2]) was introduced,

which additionally allows for dynamic process and service

changes (i.e., to insert, delete or move activities).

The ability to adapt processes at different levels, results

in collections of process model variants (process variants

for short) created from the same process model, but slightly

differing from each other. Fig. 1 depicts an example. Fig.1a

shows a high-level view on a patient treatment process as

it is normally executed: a patient is admitted to hospital,

where he first registers, then receives treatment, and

finally pays. In emergency situations, however, it might

become necessary to deviate from this model; e.g., by first

starting treatment of the patient and allowing him to register

later during treatment. To capture this behavior of the re-

spective process instance, we need to move activity receive

treatment to a position parallel to activity register. This

leads to an instance-specific process variant S0as shown in

Fig. 1b. Generally, a large number of process variants de-

rived from the same original process model might exist [8].

S[∆>S’

receive

treatment

Admitted

a) S: original process model

b) S’: final execution & change

receive

treatment

pay

AND-Split AND-Join

admitted

∆=Move (S, register, admitted, pay)

e=<admitted, receive treatment, register, pay>

Figure 1. Example of a process variant

Such process variants are expensive to configure and diffi-

cult to maintain.

An interesting approach is provided by process mining

[4]. Its key idea is to discover a process model by analyzing

the execution log of the process instances. However, only

little work considered process variant mining so far. In this

paper we deal with related issues. Our goal is to learn from

process changes applied in the past and to ”merge” the re-

sulting process variants into a generic process model which

covers these variants best. By adopting this generic process

model within the PAIS, cost of change and need for future

process adaptations will decrease. This paper deals with the

following research questions:

Why is process variant mining needed and what are the

differences between traditional process mining and the min-

ing of process variants?

We motivate the need for mining process variants and

discuss some major challenges arising in this context. The

mining algorithm itself is out of the scope of this paper (see

[9]). We have developed respective techniques and utilized

them for comparing variant mining with conventional pro-

cess mining. Sec. 2 gives background information. In Sec.

3 we discuss why process changes should be expressed in

terms of high-level change operations. Sec. 4 discusses

major goals of process variant mining and shows why it is

different from traditional process mining. Sec. 5 discusses

related work. We conclude with a summary in Sec. 6.

2 Backgrounds

We first introduce basic notions needed in the following.

Process Model. Let Pdenote the set of all process

models. A process model S= (N, E, . . .)∈ P is block-

structured, where Nis the set of activities and Econstitutes

the set of precedence relations between them [2].

Process Change. A process variant results from an orig-

inal process model Sby applying a sequence of changes

to it [2]. Such changes modify initial model Sby alter-

ing its set of activities or by changing their order relations.

Thus, each change ∆of a process model Sconsists of a

sequence of change operations and results in another pro-

cess model S0, denoted as S[∆iS0. Examples of high-level

change operations include insert,delete, and move activity

as implemented in the ADEPT change framework [2]; e.g.,

move(S, A,B,C)means to move activity Afrom its cur-

rent position within Sto the position after Band before C,

while operation delete(S, A)deletes Afrom S. Issues con-

cerning the correct use of these operations are described in

[2]. Though the depicted change operations are discussed

in relation to ADEPT, they are generic in the sense that they

can be easily applied in connection with other process meta

models (e.g., Petri Nets) as well [1]. We refer to ADEPT

since it covers by far most high-level change patterns when

compared to other approaches [1].

Distance and Bias. The distance between two process

models Sand S0is the minimal number of change opera-

tions needed for transforming Sinto S0. The respective se-

quence of change operations is denoted as bias between S

and S0. Generally, the distance between two process mod-

els measures the complexity for model transformation. As

example take Fig. 1. Here, distance between Sand S0is

one, since we only need to perform one change operation

move(S, receivetreatment, admitted, pay)to transform

Sinto S0(see [5]).

Trace. A trace ton process model S= (N, E, . . .)de-

notes a valid execution sequence t≡< a1, a2, . . . , ak>of

activities ai∈Non Saccording to the control flow defined

by S. All traces producible on Sare summarized in set TS.

3 On Representing Process Changes

We first discuss basic aspects concerning the representa-

tion of process changes.

Why Do We Need a Change Log? Change and execu-

tion logs capture different runtime information on process

instances and are not interchangeable. Even if the origi-

nal model of a process instance is given, it is not possi-

ble to convert its change log to its execution log or vice

verse. Consider our example from Fig. 1. When apply-

ing the described change to original model S, we obtain

process variant S0(i.e. S[∆iS0) with change log ∆ =<

move(S, reveive treatment, admitted, pay)>. This

process variant represents an instance-specific model and

the trace of the particular instance is {admitted, receive

treatment, register, pay}. If original model Sand in-

stance trace had been the only available information, it

would be not possible to determine the respective change.

Note that the process model, which can produce the given

trace, is not unique; e.g., a process model with the four ac-

tivities contained in four parallel branches could produce

this trace as well. By contrast, it is generally not possi-

ble to derive the trace of a process instance from its struc-

ture and change log, because execution behavior of S0is

also not unique, e.g., trace < admitted, register, receive

treatment, pay > is also producible on S0.

High-level Change Operations vs. Change Primitives

We now discuss why it is beneficial to measure the distance

between process models based on high level change opera-

tions. Consider process model Sfrom Fig. 2a, it comprises

a parallel branching (Cand Dmay be performed concur-

rently), a conditional branching (either Eor Fis executed),

and a silent activity τ(depicted as empty node). Assume

that in two different scenarios high-level change operations

are applied to Sresulting in variants S1and S2respectively:

S[∆1iS1with ∆1=move(S, C,A,B)and S[∆2iS2with

∆2=move(S, A,B,C). Fig. 2 additionally depicts the

change primitives representing the snapshot differences be-

tween Sand variants S1and S2respectively. In comparison

with low-level primitives, the use of high-level change op-

erations offers several advantages:

High-level change operations with formal pre-/post-

conditions (e.g., [2]), guarantee soundness (e.g., absence of

deadlocks); i.e., their application to a sound process model

Sresults in another sound model S0[2]. This also applies to

our example from Fig. 2. By contrast, when applying single

primitives, soundness cannot be guaranteed in general.

High-level change operations enable more effective user

support when compared to low-level primitives. Generally,

a high-level change operation is based on a set of primitives

which collectively realize a particular change pattern. As

example take ∆1from Fig. 2. This operation is internally

based on 15 primitives to delete and add edges, to delete

the silent activity, and to update node types. By defining

changes with high-level operations, cost of change can be

reduced. As another benefit, high-level operations perform

model optimizations when realizing a process change. Re-

garding ∆1from Fig. 2, for example, movement of Cis

accompanied by deletion of silent activity τ, since the par-

allel branching is no longer needed.

Another important aspect concerns the number of change

operations needed to transform a process model Sinto an-

delEdge(StartFlow,A); delEdge(A,B);

delEdge(B,C); addEdge(B,A);

addEdge(A,C); addEdge(StartFlow,B)

delEdge(A,B); delEdge(B,C); delEdge(B,D);

delEdge(C, τ); delEdge(D,τ); delEdge(t,E);

delEdge(τ, F}; delNode(τ); addEdge(A,C);

addEdge(C,B); addEdge(B,D); addEdge(D,E);

addEdge(D,F); updateNodeType(D,

XorSplit); updateNodeType(B, empty);

A C

Change Primitives

∆

=Move (S, C, A, B)

model after change ∆

∆

=Move (S, A, B, C)

S[∆

original process model

model after change ∆

AND-Split

AND-Join

XOR-Split

XOR-Join

a) b)

Figure 2. High-Level Change Operations

other model S0. Regarding our example, for instance, we

only need one move operation to transform Sto either S1

or S2. When using change primitives instead, migrating S

to S1requires 15 primitives, while the second change ∆2

can be realized with 6primitives. This demonstrates that

the number of change primitives needed for model transfor-

mation does not provide an adequate means to express the

difference between two process models.

How Do High-level Changes Influence Process Behav-

ior? [3] measures similarity between two process mod-

els based on their trace sets, i.e., behavioral distance be-

tween models S1and S2is calculated as sum of the edit

distances of all possible pairs of traces (t1,t2) with ti∈ TSi

(i= 1,2). Obviously, this method evaluates to what degree

the behaviors of the two process models differ from each

other rather than on what the effort for transforming one

model into another is. On the one hand, application of one

change operation can significantly modify execution behav-

ior of the respective process model. On the other hand, sev-

eral changes might be required to realize a smooth change

of the behavior of a process model. When considering the

two models from Fig. 1, we obtain behavioral distance one.

However, when performing another change S[∆2iS00 with

∆2=move(S, pay, admitted, receivetreatment), be-

havioral distance between Sand S00 is four. Particularly,

when a change moves or adds activities to parallel branches,

the number of possible traces grows exponentially.

In our approach, we focus on the relationship between

behavior of process models and biases.

4 Mining Process Variants

So far, we have motivated the need for representing pro-

cess changes in terms of high-level change operations. This

section discusses the major goal of mining process variants,

namely to derive a generic process model out of a given col-

lection of process variants. This shall be done in a way such

that the different process variants can be efficiently config-

ured out of the generic model. We measure the efforts for

respective process configurations by the number of change

operations needed to transform the generic model into the

respective model variant. The challenge is to find a generic

model such that the average number of change operations

needed (i.e., the average distance) becomes minimal.

To make this more clear, we compare process variant

mining with traditional process mining. Obviously, input

data for process mining and process variant mining dif-

fer. While traditional process mining operates on execution

logs, mining process variants is based on change logs (i.e.,

the process variants we can obtain from them). In princi-

ple, methods like alpha algorithm or genetic mining [4] can

be applied to our problem as well. For example, we could

derive all traces producible by a given collection of process

variants [3] and then apply existing mining algorithms to

them. To make the difference between process mining and

process variant mining more evident, in the following, we

consider behavioral similarity between two process models

as well as structural similarity based on their bias.

The behavior of a process model Scan be represented

by the trace set TSit can produce. Therefore, two models

can be compared based on the difference between their trace

sets [3, 4]. By contrast, biases is used to express (structural)

distance between two process models based on model trans-

formations [5]. While process variant mining addresses

structural similarity, traditional process mining focuses on

behavior. Obviously, this leads to different choices in algo-

rithm design and also different mining results. Fig. 3 shows

one example. Assume that 55 process instances are running

on process variant S1and 45 instances on variant S2. If we

focus on behavior, like existing process mining algorithms

do [4], the discovered process model will be S; all traces

producible on Si(i= 1,2) can be produced on Sas well,

i.e. TSi⊆ TS(i= 1,2). However, if we adopt Sas refer-

ence model, all instances running on S1or S2will have non-

empty bias. The average weighted distance between Sand

Si(i= 1,2) is one; i.e., for each process instance we need

on average one high-level change operation to configure S

into Si(i= 1,2) (S[∆1iS1with ∆1=move(S, B,A,C)

and S[∆2iS2with ∆2=move(S, B,C,D)).

By contrast, if the goal is to reduce the average dis-

tance between genetic model and process (instance) vari-

ants, we should choose S0as reference model. Though S0

does not cover all traces S1and S2can produce, average

distance between generic model and process instances be-

comes minimal. More precisely, the average distance be-

tween S0and instances running either on S1or S2is 0.45;

while S0=S1, we only need to move Bfor the 45 instances

based on S2, i.e. S0[∆0iS2with ∆0=move(S0,B,C,D).

Though S0cannot cover all traces variants S1and S2can

produce, adapting S0rather than Sas new reference model

requires less efforts for process configuration, since the av-

erage weighted distance between S0and the instances run-

ning on both S1and S2is 55% lower than when using S.

Our discussions on the difference between behavioral

and structural similarity also demonstrate that current pro-

cess mining algorithms do not consider structural similarity

based on bias and change distance. We give an example to

illustrate the basic goal as well as relevant issues and chal-

AB C D

ACBD

AB C D

Focus on behavior

Focus on biases

55 instances

45 instances

A D

S’

Biases exist: 100 Executions cover: 100%

Biases exist: 45 Executions cover: 55%

Process variants Reference model

Figure 3. Mining focusing either on behavior

or minimization of biases

lenges for mining process variants. Consider Fig. 4 and

assume that process model Sdefines a standard business

process. Six process variants Si(i= (1, . . . , 6)) have been

configured out of S. Furthermore, on each of these variants

several instances are running. A simple statistics is given

to show the respective ratio (e.g., 30% of all instances are

running on variant S1and 8% on S5). Based on the rela-

tive frequency of each process variant (i.e., its weight), the

weighted average number of changes required for config-

uring the six process variants is 1.5. This means we have

to perform on average 1.5 changes on original model Sin

order to configure these process variants out of it.

When mining the six variants by our approach [9], we

obtain process model S0as result (cf. Fig. 4). This model

S0is better in the sense that it can reduce average distance

process variants have with respect to a reference process

model (if using S0instead of Sas reference model). The

weighted average number of change operations (i.e., aver-

age distance between reference model and process variants)

then decreases from 1.5 to 1.15 (cf. Fig. 4).

We also compared our result with the models obtained

through process mining algorithms, like Alpha and Al-

pha++ algorithms, Heuristic mining and Genetic mining

(see them at [4]). We first enumerate all traces producible

on the six variants, and use these traces as the input of the

process mining algorithms. Afterwards, we measure the re-

sult by computing average weighted distance between the

discovered models and the 6 process variants. Evaluation

results show that the process model discovered using our

approach has shortest average weighted distance to the pro-

cess variants (see [9] for details).

5 Related Work

A variety of techniques for process mining has been sug-

gested in literature [4]. As illustrated in this paper, tradi-

tional process mining is different from process variant min-

: 30%

: 15%

: 20%

: 8%

B C

DA C B E

B E

A B C D E

S: Original process model

=< Move (S, E, A, D) > σ

=< Move (S, C, B, E) >

=< Move (S, D, B, C), Move (S, E, B, C) >

=< Move (S, C, A, B), Move (S, E, B, D) >

Process Variants

Process Adaptations

=< Move (S, D, E,

End

), Delete (S, C) >

A B E D

: 7%

=<Delete (S, B), Move (S, E, C, D)>

ACED

A B C E D

S’: Discovered process model

Change Mining

S[∆>S’ : ∆=Move (S, D, C, E)

Average weighted distance: 1.5 changes / instance

Average weighted distance:

1.15 change/ instance

: 30%

: 15%

: 20%

: 8%

: 7%

Biases after process evolution

σ'

=< Move (S’, E, A, D) >

σ'

=< Move (S’, D, B, C),

Move (S’, E, B, C) >

σ'

=< Move (S’, C, A, B) >

σ'

=< Move (S’, C, B, E) >

σ'

=<Delete (S’, C) >

σ'

=<Delete (S’, B)>

Propagate schema change

Admitted to hospital

Receive treatment

Give feedback

Leave

Figure 4. One example

ing due to its different goal and inputs. A few techniques

have been proposed to learn from process variants by min-

ing change primitives [6]. However, this approach does not

consider important features of process meta model; e.g., it

is unable to deal with silent activities or loop backs, and

does also not differentiate AND- and OR-splits. Similar

techniques for mining change primitives exist in the fields

of association rule mining and maximal sub-graph mining

[7]; here common edges between different nodes are dis-

covered to construct a common sub-graph from a set of

graphs. None of the discussed approaches aims at creating a

generic process model, which allows for easy and optimized

configuration for process variants.

6 Summary and Outlook

We have motivated the need for process variant mining,

discussed its major goals as well as relevant issues, and

elaborated its differences when compared to traditional pro-

cess mining. Basically, as input our approach takes a col-

lection of process variants, and then produces a generic pro-

cess model as output which covers these variants best; i.e.,

the generic model has minimal average distance to process

variants. Note that this will reduce adaptation and config-

uration costs as well. When comparing our approach with

traditional mining techniques, we can see that the latter do

not satisfy the need for deriving a process model which is

easy configurable. This justifies the efforts for designing

specific algorithms for process variant mining, which we

will present in other papers.

References

[1] B. Weber, S. Rinderle, M. Reichert: Change Patterns and

Change Support Features in Process-Aware Information

Systems. CAiSE’07, LNCS 4495, 2007, pp. 574-588

[2] M. Reichert and P.Dadam. ADEPTflex - Supporting Dy-

namic Changes of Workflows Without Losing Control. Jour-

nal of Intelligent Information Systems, 10(2):93–129, 1998.

[3] A.Wombacher, M.Rozie: Evaluation of Workflow Similarity

Measures in Service Discovery. Service Oriented Electronic

Commerce 2006: 51-71

[4] http://ga1717.tm.tue.nl/wiki/

[5] C.Li, M.Reichert, A.Wombacher. Process Similarity Based

on High Level Change Operations. CTIT Technical Report,

University of Twente, The Netherlands.

[6] J.Bae, L. Liu, J. Caverlee, W. B. Rouse: Process Min-

ing, Discovery, and Integration using Distance Measures

ICWS06, pp. 479-488, 2006

[7] P. Tan, M. Steinbach, V. Kumar: Introduction to Data Min-

ing. Addison Wesley, 2006.

[8] R. Lu, S.W. Sadiq: Managing Process Variants as an Infor-

mation Resource. BPM’06, LNCS 4102, pp 426-431, 2006

[9] C. Li, M. Reichert, A. Wombacher: Discovering Process

Reference Models from Process Variants Using Clustering

Techniques. TR-CTIT-08-30. University of Twente. 2008.