Диссертация (1137084), страница 6
Текст из файла (страница 6)
= ∐︀1 , 2 , ..., ̃︀ is a sequence of length . By 1 ⋅ 2 we denote theconcatenation of two sequences, ↾ is the projection of the sequence onto the set , i.e. asubsequence of containing elements belonging to . ′ is a prefix of a sequence (denoted as ′ < ) if ∃ ′′ ≠ ∐︀̃︀ : = ′ ⋅ ′′ . We say that ′ ≤ if ′′ can be empty. By we denote -th memberof . We say ∈ if ∃ : 1 ≤ ≤ ⋃︀⋃︀ and = .We call a tuple of two elements (1 , 2 ) ∈ × a pair, in which the first element is 1 ((1 , 2 )) =1 , and the second one is 2 ((1 , 2 )) = 2 . This notation can be generalized to sequences of pairs,e.g. for a sequence ∈ ( × )∗ , () = ∐︁ (1 ), (2 ), .
. . , (⋃︀⋃︀ )̃︁.1.1.2Process ModelsA plenty of formalisms are used for process modelling, such as: transition systems, ordinary andhigh-level Petri nets, flowcharts, EPCs1 [27], BPMN models2 [28], and UML activity diagrams [29].In this thesis, we use workflow nets (WF-nets) — a subclass of Petri nets [30] — for modellingprocesses. The canonical set of Petri net notions has been accumulated by T. Murata [31]. Let usrecall those of them that are used later.A Petri net is a triple (,, ), where and are disjoint sets of places and transitions, and ∶ ( × ) ∪ ( × ) → N is a flow relation.
For a transition ∈ a preset ● and a postset ● aredefined as the subsets of such that ● = {⋃︀ (,) ≠ 0} and ● = {⋃︀ (,) ≠ 0}.t1p6t2p5t3p1t4p3p2t6p4Figure 1.1: Petri net12Event-driven Process Chains.Business Process Model and Notation.t525A marking ∶ → N specifies a current state of a Petri net. A transition ∈ is enabled at amarking iff ∀ ∈ , () ≥ (,). An enabled transition may fire yielding a new marking ′ , such that ′ () = () − (,) + (,) for each ∈ (denoted → ′ ).Graphically, ellipses denote places and boxes denote transitions. Figure 1.1 shows an examplePetri net. In this net the set of places is = {1 , 2 , 3 , 4 , 5 , 6 }, the set of transitions is ={1 , 2 , 3 , 4 , 5 }, and the set of arcs is = {( 1 , 4 ), (1 , 3 ), (2 , 1 ), (2 , 2 ), (2 , 6 ), (3 , 3 ),(4 , 3 ), (6 , 4 ), (3 , 5 ), (4 , 5 ), (5 , 5 ), (5 , 1 ), (1 , 6 ), (6 , 2 ) }.
Two black dots graphicallyrepresent the current marking of the net. This marking can also be represented as the vector 1 = (0, 0, 1, 1, 0, 0). These dots are called tokens. In this marking, transition 5 is enabled, and5can fire. This leads to the following marking change: 1 → 2 = (0, 0, 0, 0, 1, 0).A labelled Petri net is a tuple = (, , , ), where ∶ → ∪ { } is a transition labellingfunction, which maps transitions to activity labels from . A transition is called invisible, if() = , otherwise it is called visible.Definition 1.
A workflow net (WF-net) is a labelled Petri net = (,,,) with distinguishedinitial and final markings such that1. there is a single source place ∈ such that ●i = ∅, and = (︀⌋︀,2. there is a single sink place ∈ such that o● = ∅, and = (︀⌋︀,3. every node ∈ ∪ is on a path from to .Figure 1.2 shows an example of a Workflow net. A black token in the source place denotes theinitial marking.ht8asourcet1bc1t2c2cft3t6dec3t5c4t4gsinkt7Figure 1.2: Simple workflow netBy Tv (N ) we denote the set of all visible transitions in N .
A transition label is called uniqueif it labels exactly one transition in the net. Tvu (N ) denotes the set of all visible transitions withunique labels in N . The union of two WF-nets is a Petri net N U = N 1 ∪ N 2 , which is built by theunion of sets of places, transitions, and flow relations: 1 ∪ 2 = ( 1 ∪ 2 , 1 ∪ 2 , 1 ∪ 2 , ),where ∈ ( 1 ∪ 2 ) ↛ is a union of 1 and 2 , ( ) = (1 ) ∪ (2 ), () = 1 () if ∈ (1 ), and () = 2 () if ∈ (2 ) ∖ (1 ).We assume further that in a Petri net different transitions labelled with different labels.261.1.3Event LogsLet ⊆ be a set of process activities.
They are used to label model transitions. We assumethat an event in a log is a name of an activity, i.e. additional event attributes are not used. Thus,an event represents an activity in a trace of an event log.We define a trace as a finite sequence of activities from , i.e. ∈ ∗ . An event log (or log) is a finite multi-set of traces, i.e. ∈ ℬ(∗ ). For example, = (︀∐︀,,,,̃︀3 , ∐︀,,,,̃︀5 , ∐︀,,,,̃︀⌋︀is an event log with the same activities as in the model shown in Figure 1.2.A projection of an event log = (︀1 , 2 , .
. . , ⌋︀ onto a set of activities is a logL↾B = (︀1 ↾B , 2 ↾B , . . . , n ↾B ⌋︀, where ↾ is a projection of the trace onto for = 1, 2, . . . , .We call L↾B a sub-log of .To illustrate process mining techniques we will use an example process of handlingcompensation requests in some company. This process became a typical example in the field [5].An employee may ask the company to compensate a cost of tickets bought during a business trip.The company checks tickets related to a compensation request, and pay compensation if a checkverdict is positive. Otherwise, a rejection letter is send to the requester.The request handling canbe re-initiated if additional checks are needed.
This process is supported by an information systemthat records an event log. Table 1.1 shows a fragment of this event log.This fragment contains 22 event records. Each event record has the following attributes: aunique event identifier, a case identifier, an activity name, a performer name, and a timestamp.This is a typical set of attributes but others are also possible.A process case is a sequence of unique event records related to a single process instance. Eachcase has a unique identifier which is present among its event records.
That is, each process caseis related to a trace in the corresponding event log. There are 3 complete cases (1–3) and oneincomplete case (4) in the shown fragment of the event log. Cases are highlighted with differentcolours in Table 1.1. Often, an event log contains no case identifiers. In such a case, it is a firststep of analysis to select a log attribute that will be considered as such identifier.An event is recorded when a corresponding activity is performed by the performer at thespecified date and time. Table 1.1 lists event records according to their timestamps, as it usuallyhappens in real event logs. Note that the considered process contains the following activities:Register request (a), Check ticket (b), Examine casually (c), Examine thoroughly (d), Decide (e),Send rejection letter (f), Pay compensation (g), Re-initiate request (h).
Activity short-cuts aregiven in parentheses.It is possible to come up with some conclusions on process behaviour just investigating thislog. For example, one can see that each process instance begins with a request registration which isperformed either by Anna, or by Pyotr. In each trace, a first ticket check is also performed by oneof these two persons. After that Semen examines requests casually, whereas serious examinationsand decisions are made by Elena in all cases.
She also re-initiates a request once. The third caseends with a compensation payment that is performed by Galina. For example, one may guess that27Table 1.1: Event log of compensation requests handlingAnna, Pyotr, and Semen are junior clerks, Elena is a senior manager, and Galina is a paymaster.It is also possible to analyse employee workload and performance. Moreover, timestamps indicatethe working hours of the whole company and individual employees.However, real event logs are relatively large and can not be analysed manually. Fortunately,process mining provides researchers with automated analysis methods which are introduced inSection 1.2. In particular, Section 1.2.1 discusses how process models can be automaticallydiscovered from such an event log.In this thesis, most of event attributes except activity short-cuts are omitted.
Timestamps areused only for event ordering within traces. In particular, the event log shown in Table 1.1 consistsof the three complete traces, each of which is a sequence of events: = (︀∐︀, , , , ̃︀ , ∐︀, , , , ̃︀ , ∐︀, , , , ℎ, , , , ̃︀⌋︀.(1.1)28A reader may notice, that Figure 1.2 shows a workflow net corresponding to this event log.In practice, information systems record event logs in special databases or in a text format.So-called XES (eXtensible Event Stream for Achieving Interoperability in Event Logs and EventStreams) is a commonly-used and standardized event log format. The IEEE 1849-2016 XESStandard [32] is available at the page http://www.xes-standard.org/. Files in this format areacceptable by many academic and commercial process mining tools.
The list with XES-certifiedtools is available at the page http://www.xes-standard.org/tools. It is an extensible XMLbased format that is supported by IEEE CIS Task Force on Process mining3 . This format is asuccessor of MXML (Mining eXtensible Markup Language)4 format that is also XML-based, andhas been proposed in 2003.1234567891011121314151617181920212223242526272829303132333435363738394041< ! −− XES s t a n d a r d v e r s i o n : 1 .
0 −−>< ! −− OpenXES l i b r a r y v e r s i o n : 1 . 0RC7 −−>< ! −− OpenXES i s a v a i l a b l e from h t t p : //www. o p e n x e s . o r g / −−><l o g x e s . version=" 1 . 0 " x e s . f e a t u r e s=" n e s t e d − a t t r i b u t e s " o p e n x e s . version=" 1 . 0RC7"><e x t e n s i o n name=" L i f e c y c l e " p r e f i x=" l i f e c y c l e "u r i=" h t t p : //www. xes − s t a n d a r d . o r g / l i f e c y c l e . x e s e x t " /><e x t e n s i o n name=" Concept " p r e f i x=" c o n c e p t "u r i=" h t t p : //www. xes − s t a n d a r d .
o r g / c o n c e p t . x e s e x t " />< c l a s s i f i e r name=" Event ␣Name" k e y s=" c o n c e p t : n a m e " />< c l a s s i f i e r name=" ( Event ␣Name␣AND␣ L i f e c y c l e ␣ t r a n s i t i o n ) "k e y s=" c o n c e p t : n a m e ␣ l i f e c y c l e : t r a n s i t i o n " />< s t r i n g key=" c o n c e p t : n a m e " v a l u e="XES␣ Event ␣ Log " /><t r a c e>< s t r i n g key=" c o n c e p t : n a m e " v a l u e=" 1 " /><e v e n t>< s t r i n g key=" c o n c e p t : n a m e " v a l u e=" R e g i s t e r ␣ r e q u e s t " />< s t r i n g key=" l i f e c y c l e : t r a n s i t i o n " v a l u e=" c o m p l e t e " /><i n t key=" Event ␣ID" v a l u e=" 235 " /></ e v e n t><e v e n t>< s t r i n g key=" c o n c e p t : n a m e " v a l u e=" Check ␣ t i c k e t " />< s t r i n g key=" l i f e c y c l e : t r a n s i t i o n " v a l u e=" c o m p l e t e " /><i n t key=" Event ␣ID" v a l u e=" 236 " /></ e v e n t><e v e n t>< s t r i n g key=" c o n c e p t : n a m e " v a l u e=" Examine ␣ c a s u a l l y " />< s t r i n g key=" l i f e c y c l e : t r a n s i t i o n " v a l u e=" c o m p l e t e " /><i n t key=" Event ␣ID" v a l u e=" 239 " /></ e v e n t><e v e n t>< s t r i n g key=" c o n c e p t : n a m e " v a l u e=" D e c i d e " />< s t r i n g key=" l i f e c y c l e : t r a n s i t i o n " v a l u e=" c o m p l e t e " /><i n t key=" Event ␣ID" v a l u e=" 242 " /></ e v e n t><e v e n t>< s t r i n g key=" c o n c e p t : n a m e " v a l u e=" Send ␣ r e j e c t i o n ␣ l e t t e r " />< s t r i n g key=" l i f e c y c l e : t r a n s i t i o n " v a l u e=" c o m p l e t e " /><i n t key=" Event ␣ID" v a l u e=" 243 " /></ e v e n t></ t r a c e>...Figure 1.3: Fragment of an event log in XES formatFigure 1.3 shows a fragment of an event log in XES format.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
