Discovery of process variants based on trace context tree

Figures & data

Table 1. An example of event logs.

Trace	CID	frequency
A B C E	$C_1$	3
A C B E	$C_2$	2
A B E	$C_3$	2
A D E	$C_4$	3

Table 2. The comparisons of different process variants discovery methods.

Methods classification	Study perspective	Variants discovery techniques	Main challenge
Process variability modelling methods	The reference model (or base model) of process system is given as known	Some process variants clusters or cohorts can be obtained via configuring personalised operations.	Model configurations may produce unfeasible process variants, and variants comparisons mostly realised from the perspective of control flow.
Configurable process mining methods	Event log is known	(1) Traces splitting techniques that form trace cohorts using trace splitting operations; (2) Trace fragmentation or slicing techniques.	Time complexity of the existing algorithms is comparative high, and some of them cannot distinguish similar-but-different behaviours among trace cohorts.
Trace clustering methods	Event log is known	Trace clustering methods using machine learning.	These methods could generate an incomprehensible “spaghetti like” process model, and some performance indicators such asfitness and precision are relatively low.

Figure 1. A reference model and its process variant. (a) The mined reference model $M_1$ for log $L_1$ using inductive mining method (b) A process variant model $M_2$ from $M_1$ by personalised operations.

Figure 2. The mined model of log L through inductive mining.

Figure 3. Two clusters deduced from log L through tracing clustering method (Xu & Liu, 2019). (a) The first cluster model through tracing clustering method (b) The second cluster model through tracing clustering method.

Table 3. Experimental results comparison among different methods for log $L=L_1\bigsqcup L_2$.

Method		Fitness	Precision
Heuristics mining for log L (Aalst, 2011)		0.946	0.902
Inductive mining for log L (Aalst, 2011)		1	0.41
Trace clustering by SOM (Xu & Liu, 2019)	Variant1	1	0.551
	Variant2	1	1
Trace clustering by Kmeans (Medeiros et al., 2007)	Variant1	1	1
	Variant2	1	0.577
Trace clustering by Agglomerative clustering (Zandkarimi et al., 2020)	Variant1	1	0.438
	Variant2	1	1
Trace clustering by SpectralClustering (Delias et al., 2015)	Variant1	1	1
	Variant2	1	0.439
Our method	Variant1	1	1
	Variant2	1	0.836

Table 4. An example of event log L to illustrate context log.

Frequency	Trace
5	yabcizdeop
3	yacbizdhop
2	yacibzlmn
2	yaibczlmn

Figure 4. The context tree corresponding to the event logs in Table 2.

Table 5. Event logs of credit disposal processes.

Case num	Trace	Case num	Trace
47	abcdehijlkmnopw	48	abrstuvoqw
50	abrstuvw	52	abrstuvopw
52	abdcfghnw	28	abdcehijklmnoqw
48	abcdfghnw	25	abdcehikjlmnop

Table 6. Frequency of activities.

Activity	Frequency	Activity	Frequency	Activity	Frequency
a	350	o	200	g	100
b	350	p	172	i	100
w	325	r	150	j	100
c	200	s	150	k	100
d	200	u	150	l	100
e	200	v	150	m	100
h	200	q	128	t	98
n	200	f	100

Table 7. kth-strict order relationships of nodes b and h.

len k	node b	node h
k = 1	a, r, c, d	e, i, n
k = 2	s, f, e	w, d, c, j, k
k = 3	t, u, g, h	f, b, m, l
k = 4	i, e, u, v	c, d, a, n, m
k = 5	j, k, h, v, o	b, m, o
k = 6	l, m, n, w, p, q	a, o, p, q
k = 7	n, w	p, q, w

Table 8. Activity alphabet with node b of length k.

len.k	$A_b^k$	num.alphabet
k = 1	a, c, d, r	4
k = 2	a, c, d, e, f, r, s	7
k = 3	a, r, c, d, s, f, e, t, u, g, h	11
k = 4	a, r, c, d, s, f, e, t, u, g, h, i, v	13
k = 5	a, r, c, d, s, f, e, t, u, g, h, i, v, j, k, o	16
k = 6	a, r, c, d, s, f, e, t, u, g, h, i, v, j, k, o, l, m, n, w, p, q	22
k = 7	a, r, c, d, s, f, e, t, u, g, h, i, v, j, k, o, l, m, n, w, p, q	22

Table 9. Activity alphabet with node h length k.

len. k	$A_h^k$	num.alphabet
k = 1	e, i, n	3
k = 2	e, i, n, w, d, c, j, k	8
k = 3	e, i, n, w, d, c, j, k, f, m, l	11
k = 4	e, i, n, w, d, c, j, k, f, m, l, a, n	13
k = 5	e, i, n, w, d, c, j, k, f, m, l, a, b, o	14
k = 6	e, i, n, w, d, c, j, k, f, m, l, a, b, o, p, q	16
k = 7	e, i, n, w, d, c, j, k, f, m, l, a, b, o, p, q	16

Table 10. Context logs for nodes b and h.

$L_b^5$	$L_h^5$	$L_h^6$
$⟨abcdehijk{⟩}^{47}$	$⟨abcdehijlkmnow{⟩}^{47}$	$⟨abcdehijlkmnopw{⟩}^{47}$
$⟨abrsuv{⟩}^{50}$	$⟨abhw{⟩}^{50}$	$⟨abhw{⟩}^{50}$
$⟨abdcfgh{⟩}^{52}$	$⟨abdcfhnw{⟩}^{52}$	$⟨abdcfhnw{⟩}^{52}$
$⟨abcdfgh{⟩}^{48}$	$⟨abcdfhnw{⟩}^{48}$	$⟨abcdfhnw{⟩}^{48}$
$⟨abrstuvo{⟩}^{48}$	$⟨abhow{⟩}^{48}$	$⟨abhoqw{⟩}^{48}$
$⟨abrsuv{⟩}^{52}$	$⟨abhow{⟩}^{52}$	$⟨abhopw{⟩}^{52}$
$⟨abdcehijko{⟩}^{28}$	$⟨abdcehijklmnow{⟩}^{28}$	$⟨abdcehijklmnoqw{⟩}^{28}$
$⟨abdcehikjo{⟩}^{25}$	$⟨abdcehikjlmno{⟩}^{25}$	$⟨abdcehikjlmnop{⟩}^{25}$

Table 11. Weighted frequency cosine similarity calculation results.

Context log	Result
$L_b^5$	0.99880
$L_h^5$	0.99962
$L_h^6$	0.99968

Figure 5. Context tree of $L_h^6$.

Figure 6. Process variants (a), (b), (c), (d) found in the event log. (a) Housing loan process (b) Student loan process (c) Commercial loan process (d) Small loan process.

Table 12. Comparison of process variants discovery methods.

Comparsion	Method of this paper	Activity recommendation method (Chan et al., 2014)
Input	Event log	Process model and event log
method	Discover process variants through	Assist development process
	clustering traces	variants through event logs
complexity	$O(pk+m(a+b)+x)$ (Section 5.4.2)	$O(n_A\times n_P\times n\times k)$

Table 13. Holistic information of datasets.

	Trace	Event	Activity
Library borrowing and returningbooks (Dataset 1)	570	7990	31
Bank credit process (Dataset 2)	350	3775	23

Table 14. Performance indicators comparisons with (Chan et al., 2014).

	Purposed method			Literature (Chan et al., 2014)
Variants	Fitness	Accuracy	Average configuration step	Fitness	Accuracy	Average configuration steps
Dataset 1.Variant1	0.973	1		0.753	0.681
Dataset 1.Variant2	1	1		0.744	0.694
Dataset 1.Variant3	1	1		0.755	0.688
Dataset 1.Variant4	1	1	3	0.702	0.68	4
Dataset 2.Variant1	1	0.826		0.765	0.639
Dataset 2.Variant2	1	0.891		0.769	0.651
Dataset 2.Variant3	1	0.949		0.762	0.674

Table 15. Performance indicators comparisons with (Xu & Liu, 2019).

	Purposed method		Trace clustering with CNN coding (Xu & Liu, 2019)
Variants	Fitness	Accuracy	Fitness	Accuracy
Data set 1.Variant1	0.973	1	1	0.888
Data set 1.Variant2	1	1	0.94	1
Data set 1.Variant3	1	1	1	1
Data set 1.Variant4	1	1	1	1
Data set 2.Variant1	1	0.826	1	0.888
Data set 2.Variant2	1	0.891	0.96	0.91
Data set 2.Variant3	1	0.949	0.916	0.95

Figure 7. Fitness and precision comparisons based on daset1 and dataset2. (a) Performance comparisons with (Chan et al., 2014) (b) Performance comparisons with (Xu & Liu, 2019).

Table 16. Comparisons among different methods for log $L^{\prime }=L_1^{\prime }\bigsqcup L_2^{\prime }$.

Method		Fitness	Precision
Heuristics mining for log L		0.951	0.94
Inductive mining for log L		1	0.41
Trace clustering by SOM	Variant1	1	0.551
	Variant2	1	1
Trace clustering by Kmeans	Variant1	1	1
	Variant2	1	0.437
Trace clustering by Agglomerative clustering	Variant1	1	0.437
	Variant2	1	1
Trace clustering by SpectralClustering	Variant1	1	1
	Variant2	1	0.437
Our method	Variant1	1	1
	Variant2	1	0.802

Table 17. Comparisons among different methods for BPIC 2015 log.

Method		Fitness	Precision
Inductive mining for log BPIC2015	BPIC2015-1	1	0.0055
	BPIC2015-2	1	0.0047
	BPIC2015-3	1	0.0056
	BPIC2015-4	1	0.0067
	BPIC2015-5	1	0.0052
Trace clustering by SOM for log BPIC2015	Variant1	1	0.011
	Variant2	1	0.0076
	Variant3	1	0.0054
	Variant4	1	0.0043
	Variant5	1	0.0072
Our method for log BPIC2015	Variant1	1	0.053
	Variant2	1	0.047
	Variant3	1	0.035
	Variant4	1	0.022
	Variant5	1	0.019

Figure 8. Fitness and precision comparisons for event logs with different variant distributions. (a) fitness of $L^{\mathrm{\prime }}$ (b) precision of $L^{\mathrm{\prime }}$ (c) fitness of BPIC2015 (d) precision of BPIC2015.

Figure 9. Execution time of different methods.

Xu, J., & Liu, J. (2019). A profile clustering based event logs repairing approach for process mining. IEEE Access, 7, 17872–17881. https://doi.org/10.1109/ACCESS.2019.2894905

 Web of Science ®Google Scholar

Van der Aalst, W. (2011). Process mining: Discovery, conformance and enhancement of business processes (2nd ed.). Springer.

 Google Scholar

Medeiros, A. K. A. D., Guzzo, A., Greco, G., Van der Aalst, W. M., Weijters, A., B. F. V. Dongen, & Sacca, D. (2007). Process mining based on clustering: A quest for precision. In International conference on business process management (pp. 17–29). Springer.

 Google Scholar

Zandkarimi, F., Rehse, J. R., Soudmand, P., & Hoehle, H. (2020). A generic framework for trace clustering in process mining. In 2020 2nd International conference on process mining (icpm) (pp. 177–184). IEEE.

 Google Scholar

Delias, P., Doumpos, M., Grigoroudis, E., Manolitzas, P., & Matsatsinis, N. (2015). Supporting healthcare management decisions via robust clustering of event logs. Knowledge-Based Systems, 84, 203–213. https://doi.org/10.1016/j.knosys.2015.04.012

 Web of Science ®Google Scholar

Chan, N. N., Yongsiriwit, K., Gaaloul, W., & Mendling, J. (2014). Mining event logs to assist the development of executable process variants. In International conference on advanced information systems engineering (pp. 548–563). Springer International Publishing.

 Google Scholar