Process mining started to be a very useful tool how to check processes in companies. The only thing that has to be done is to have at least some log about the activities performed by the software system. There are many methods that can be used then to analyze this data obtained from the log. Every usage of yet not used or rarely used method opens up new perspectives in process mining and reveals the unknown potential of its application to the practice. In this paper we have applied sequence alignment methods to the real process example and examined what results and bene ts could be obtained from such usage. The main purpose of this paper is to adjust methods for sequence alignment to be able to determine similarity between the business processes.
Generally, information systems support business processes. Enactments of the processes are partly managed by the systems, partly managed by users decisions and activities. It is not easy to understand whether the speci c process runs e ciently, because usually various activities are processed in parallel and process de nition allows plenty of process enactment variations. Our task was to analyze speci c process with request to suggest steps for its simpli cation, curtailment and enact the process cheaper.
The research described in this paper is based on our previous work that
included process reconstruction and path analysis [
The paper is organized as follows: Section 2 introduces the state of the art; Section 3 describes the process that is analyzed and log obtained from the company, Section 4 depicts the experiment that we have performed, describes the preparation of data that we have obtained, shows the usage of our process mining method and explains obtained results; concluding Section 5 provides a summary and discusses the planned future research. 2
Business process de nitions are sometimes quite complex and allow many variations. All of these variations are then implemented to supportive systems. If you want to follow some business process in a system, you have many decisions and process is sometimes lost in variations. Modeling and simulations can help you to adjust the process, nd weaknesses and bottlenecks during the design phase of the process.
The idea of process mining was introduced by Aalst in 2004 [
In the area of process mining the methods of the sequence alignment were
introduced by Esign and Karagoz [
The basic approach to the comparison of two sequences, where the order of
elements is important, is The longest common substring method (LCS). This is
used in exact matching problems [
Unlike substrings, the objects in a subsequence might be intermingled with
other objects that are not in the sequence. The longest common subsequence
method (LCSS) allows us to nd the common subsequence [
The third selected method was The time-warped longest common
subsequence (TWLCS) [
The methods LCS and LCSS used for the comparison of sequences nd the longest common subsequence z of compared sequences x and y, where (z x) ^ (z y). The relation weight wseq(x; y) between the sequences x and y was counted by Equation 1: wseq(x; y) =
l(z)2 M in(l(x); l(y))2 l(x)l(y) M ax(l(x); l(y))2 ; (1) where l(x) and l(y) are lengths of the compared sequences x and y, and l(z) is a length of a subsequence z. Equation 1 takes account of the possible di erence between l(x) and l(y). Due to this reason, z is adapted so that wseq(x; y) is strengthened in the case of similar lengths of sequences x and y, and analogically weakened in the case of higher di erence of l(x) and l(y). For the methods LCS and LCSS, wseq meets all the similarity conditions: wseq 0, wseq(x; x) = 1, wseq(x; x) > wseq(x; y) and wseq(x; y) = wseq(y; x).
The output z is only the sequence which characterizes the relation between the sequences x and y for T-WLCS method. Therefore, wseq(x; y) does not meet all the similarity conditions due to its characteristics. Respectively, it is possible that wseq(x; y) > wseq(x; x). Although we know that wseq(x; y) is not a similarity for T-WLCS method, due to a simpli cation, the 'sequence similarity' will be used as a relation weight wseq(x; y) between the sequences x and y for all the methods of sequence comparison in the following text.
As a complementary method for comparison of sequences we have used
common method used in informational retrieval, Leventhtein distance [
The analyzed company runs SAP system in ve countries and process approx. 30,000 supplier invoices per year. Examined business process of the invoice veri cation is implemented in SAP ERP and SAP DMS, user activities are controlled by SAP business work ow. Users participate in the invoice veri cation work ow in several di erent roles (creator, accountant completion, approver, and accountant decision and posting). Generally, it is process where the accountant should create the invoice, verify it, send to the approvers and nally when he gets it back he does invoice posting.
We have loaded the log of the process between 1/1/2012 and 6/30/2012,
totally we loaded 37,991 records for adjusting. Detailed description of the obtaining
log and data preprocessing is described in our previous work [
The main purpose of this paper is to adjust methods for sequence alignment to be able to determine similarity between the business processes. The rst step of the experiments was focused on one characteristic of the business processes: the duration of the events. In sequence alignment area, this problem is not common. That is the main reason for adjustment of the methods to this area. We have performed an experiment where we made decision about the categorization of the duration of events, prepared four types of sequences from the di erent viewpoints, analyzed the prepared sequences and applied the sequence alignment methods to determine the similarities of the sequences. Finally, we have selected the right method for our purposes and analyzed the applicability of our approach on the example. The following subsections describe the particular steps in detail. 4.1
Data Preparation and Categorization - Duration Category When we look at the histogram of all events that is depictured at Fig. 1, we can see that there are cases that where completed in one day, then cases that last two days etc. We can see interesting distribution of the process duration on this histogram that looks like the waves. The waves are caused by the fact that all events of this process are performed in window of approximately 8 working hours each day. Then there is a 16 hours delay till the next working day window appears.
We needed to categorize the duration of the events. After the consultation with the company, we have decided to set three categories for the event duration. First category is the process that last up to the 168 hours. It means that they were started in the window of one working week and ended the same week or the week after. Next, the second category is the category of processes that last from one week to one month. The last category is the category of all processes that last more than one month. Since there are four events in the process, one process should last up to 36 hours so all four together last up to one week. Similar categorization principle works for other categories too.
We set up aliases for the type of the events in the sequence. It means that Veri cation event is in the sequence like V, Creation event is C, Approval is A, and Posting is P. 4.2
According to information from the data log we could analyze information in detail and from di erent points of view. We have de ned four types of points of view, or we can say type of event cases: { Type A - Events without Time and Users, { Type B - Events with Time and without Users, { Type C - Events without Time and with Users, { Type D - Events with Time and Users.
Case type A focuses on the topological structure of the process only and does not care about meta-information of the events like time, or duration of the event, or user that performs particular event.
Example of the sequence for the case type A: 0,C;V;A;A;S;, where sequence is de ned by the following structure CaseID, event1;event2;event3;...;eventn
Case type B focuses on the topological structure of the process and combines it with the information about time, or duration, of the events. That can bring us another point of view to the process. Thanks to this we can see duration of the whole process, or its events. Tagging of the duration of the events is made by repeating the symbol of the event in the sequence. How much is the symbol repeated depends on the duration category of the particular event. If the event ts in the category three than the symbol is repeated three times, if the event ts in the category two than the symbol is repeated two times and for the category one is symbol repeated one time.
Example of the sequence for the case type B: 0,C;C;V;A;A;S;, where sequence is de ned by the following structure: CaseID, event1; event1 (repetition according to the duration cat.); event2; ...; eventn.
Case type C combines topological structure of the process and metainformation about the users. It brings us interesting view to the users involved in particular process.
Example of the sequence for the case type C: 0,C USER068; V USER068; A USER272; S USER068;, where sequence is de ned by the following structure: CaseID, event1 originator of the event1; event2 originator of the event2; event3 originator of the event3;...; eventn originator of the eventn.
Case type D combines all possible views to the process - topological, time view and users view. It can bring us superb and surprising view to the process that is not possible to see at the rst glance.
Example of the sequence for the case type D: 0,C USER260; C USER260;V USER260;A USER074;A USER202;S USER260;, where sequence is de ned by the following structure: CaseID, event1 originator of the event1(repetition according to the duration category); event2 originator of the event2; event3 originator of the event3;...; eventn originator of the eventn.
Thanks to the di erent case types we can discover processes that take least time, most time to accomplish it, or we can nd deviations in the process execution that is not possible to see only in the topological view. We can see if some users take more time to execute event, or if some users communicate more or less, etc. 4.3 Information about sequence types sequence distribution We have made sequence distribution diagrams for four case types. Some basic interesting information about particular process can be identi ed here.
Fig. 2 on the left side shows histogram of the most frequented sequences. Histogram nicely shows distribution of the frequency of the particular sequences. It is focused to the case type A. We can see that most frequented sequence in the examined process is sequence C,V,A,A,S. Second most frequented is C,V,A,A,A,A,S, etc. We can also discover the least frequented sequences that can be identi ed as some deviations in the process.
Right side of the Fig. 2 shows histogram which is focused to the case type B. There we can see that time (duration of events) in uences the amount of di erent sequences.
Fig. 3 depictures on the left side histogram of case type C and on the right side case type D the sequences with and without time, but with the identi cation of users (performers of the events). This information also in uences the di erence between the sequences.
We have used four methods to determine the similarity of sequences. Similarity was determined by the equation 1. The main purpose for determining the sequence similarity is that we would like to nd similar types of sequences (set business processes) as well as the deviations. The four di erent types of sequences allow us a whole new insight into the performed processes that cannot be done by conventional approaches.
Similarity between sequences was determined by several selected methods. The aim was to nd the score, which can show us how similar the event sequences in the case are. The weight distribution in Fig. 4 and Fig. 5 shows us that each method has its speci c behavior and due to this the score which determines the similarity between the sequences is di erent for each method. The advantages and disadvantages describes the following text.
Levenstein distance method does not respect the order of events within the sequences. It only represents amount of necessary steps to change one sequence to another. LCS method respects the events order within the sequences. However, it is suitable, when we can nd identical sequences. If the sequences have even a small di erence, the similarity weight changes signi cantly. LCSS method is more tolerant to slight distortions inside the sequences. Of course, it respects the order of events within the sequences. In comparison with LCS, if we add one more event into the sequence, we can nd the change of weight similarity, but not as signi cant then using LCS method. T-WLCS method has as similar behavior as LCSS method. Besides the event order in sequences, T-WLCS method emphasizes the event recurrence within the sequence. However, we must remind that the sequence weight is not similarity for T-WLCS method, it is only a score.
Histograms at Fig. 4 and Fig. 5 show us a distribution of weights for all four case types. These histograms show in fact the applicability of used methods to our example. We can see that the Levensthein and LCS methods are not very suitable for our purposes, because the distribution for these methods does not show much variability, weight distribution is closely concentrated. LCSS and T-WLCS methods seemed to be more promising and we have analyzed the similarities between the sequences in more detail.
Analysis of the result showed that T-WLCS is seems to be more appropriate for our purpose. We have based our decision also on our previous researches that showed suitability of these methods [29, 30]. Left side of Fig. 6 visualizes similarity between particular sequences of case type A. Similarity was analyzed by T-WLCS method which we choose like the best representative of the tested methods according to our research that was mentioned in the section 4.4 The structure of the graph show us that where we are able to discover which sequences are more similar than others and what are the connections between them. In the future work we will analyze these parts and we will try to nd why is it happening and what it means in the real business.
Right side of Fig. 6 visualizes similarity between particular sequences of case type B. That means there is involved time parameter. We can see that there are some di erences according graph on the left side of the Fig. 6. In any case the result is that time parameter have some impact to the examined structure and can show us another dependencies and clusters. That is the interesting result which is in one hand essential and expectable but in the other hand bring us to another view to the examined process that we are not able to see at the beginning of analysis. There are a lot of possibilities to future work that we can do. Obtained results show that the proposed approach can be successfully used for the data mining. We can relatively easily reach many types of ndings that have to be analyzed then by the customer and the reasons why something is made di erently or some process is made in two di erent ways has to be found.
Our approach allowed us to involve time and user metadata to the examination and we were able to found many interesting results. For example the concrete person behavior can be showed and analyzed what are her/his process instances and the behavior pattern. The goal of our paper was to nd out whether we can use the proposed approach to this application domain and how. We have found that the application is possible after the described adjustment and brings us an opportunity to obtain interesting results from the data logs that could not have been seen before by other methods or their execution is di cult.
We would like to continue with the extension of this approach in the future. We want to nd out what types of results we can obtain by the usage of di erent methods, examine the methods and accustom them for the usage on di erent real examples. Detailed interpretation of di erent case studies will help us then to determine which method and what views will be used then for data mining and real process examination. The idea is to have a very good control of the process by the usage of the data about already performed process instances.
This work was supported by the project (CZ.1.05/1.1.00/02.0070), funded by the European Regional Development Fund and the national budget of the Czech Republic via the Research and Development for Innovations Operational Programme, by the project New creative teams in priorities of scienti c research, reg. no. CZ.1.07/2.3.00/30.0055, supported by Operational Programme Education for Competitiveness and co- nanced by the European Social Fund and the state budget of the Czech Republic and by the internal grant agency of VSB { Technical University of Ostrava, Czech Republic, under the projects no. SP2014/157 "Knowledge modeling, simulation and design of processes" and no. SP2014/154 "Complex network analysis and prediction of network object behavior".