Structural and temporal semantics heterogeneous information network (HIN) for process trace clustering
A method of generating process trace clusters includes receiving a set of process traces, where a process trace is an application level event log from a computer system; receiving an identification of node types and edge types of the application event log to generate a heterogeneous information network (HIN) graph, where a temporal node type value is a difference between a current system time and a reference timestamp divided by a user chosen time granularity parameter, performing dimension reduction of the HIN to generate clusters of new event types, generating a set of meta-paths that connect nodes of a same reduced event type in the application event log, calculating similarities between process traces using the new event type clusters, and clustering the set of process traces to generate a plurality of disjoint graph models of processes in the application event log based on the clusters of new event types.
1. A computer-implemented method of generating process trace clusters, the method executed by a computer comprising the steps of:
receiving a set of process traces, wherein a process trace is an application level event log of a business process from a computer system;
receiving an identification of node types and edge types of the application event log to generate a heterogeneous information network (HIN) graph of the application event log, wherein node types of said HIN include events, traces and temporal nodes, wherein each trace is a finite sequence of event type nodes, wherein a temporal node type value is set to be a difference between a current system time and a reference timestamp, divided by a user chosen time granularity parameter,
performing dimension reduction of the HIN by reducing a number of event types of the set of input traces to generate clusters of new event types;
generating a set of meta-paths that connect nodes of a same reduced event type in the application event log;
calculating similarities between process traces using the new event type clusters;
clustering the set of process traces to generate a plurality of disjoint partitions based on the clusters of new event types, wherein each partition is a graph model of the business process in the application event log; and
performing process mining on said graph models to determine whether events in the event log were executed in a correct sequence or to identify bottlenecks in the business process.
2. The method of claim 1 , further comprising repeating said steps of receiving an identification of node types and edge types, generating a set of meta-paths, performing dimension reduction, calculating similarities, and clustering the set of process traces using one of said plurality of disjoint partitions as input.
3. The method of claim 1 ,
wherein edge types of said HIN are associated with different types of interactions between different node types,
wherein an edge relationship between a trace node type and a temporal node type includes a starts-on edge that indicates a start time of a trace, an ends-on edge that indicates an end time of a trace, and a joined-on edge that indicates a time when a particular resource became available to a trace.
4. The method of claim 1 , wherein calculating similarities between process traces using the new event type clusters comprises calculating one or more of a structural metapath between new event type clusters and a temporal metapath between new event type clusters.
5. The method of claim 4 , wherein a structural path similarity between each pair of events type clusters connected by a meta-path P is calculated using
σ
P
(
e
j
,
e
k
)
=
2
×
|
Γ
P
(
e
j
,
e
k
)
|
|
Γ
P
(
e
j
,
e
j
)
|
+
|
Γ
P
(
e
k
,
e
k
)
|
wherein e j and e k represent event-type clusters and Γ P (e j ,e k ) is a set of paths from e j to e k following meta-path P, and |Γ P ( )| represents a cardinality of the set of paths represented by Γ P ( ).
6. The method of claim 5 , wherein a temporal path similarity between each pair of events type clusters connected by a meta-path P is calculated from SeqPathSim(x, y) of traces x=(a 1 , a 2 , . . . , a m ) and y=(b 1 , b 2 , . . . , b n ), wherein a i , b i are event type clusters, wherein SeqPathSim(x, y) generates a matrix v mn (x, y) defined by
v
m
,
n
(
x
,
y
)
=
{
v
m
-
1
,
n
-
1
(
x
,
y
)
for
a
m
=
b
n
,
min
v
for
a
m
≠
b
n
,
with
:
min
v
=
{
v
m
-
1
,
n
(
x
,
y
)
+
σ
P
EE
(
a
m
,
b
n
)
v
m
,
n
-
1
(
x
,
y
)
+
σ
P
EE
(
a
m
,
b
n
)
v
m
-
1
,
n
-
1
(
x
,
y
)
+
σ
P
ERE
,
P
ETE
(
a
m
,
b
n
)
.
7. The method of claim 6 , further comprising combining meta-path similarities using the following formula:
σ*( x,y )=Σ P i w i ×σ P i ( x,y ),
where σ P i (x, y) is a similarity between two traces x and y via meta-path P i , and w i is a weight associated with meta-path P i .
8. A non-transitory program storage device readable by a computer, tangibly embodying a program of instructions executed by the computer to perform the method steps for generating process trace clusters, the method executed by a computer comprising the steps of:
receiving a set of process traces, wherein a process trace is an application level event log of a business process from a computer system;
receiving an identification of node types and edge types of the application event log to generate a heterogeneous information network (HIN) graph of the application event log, wherein node types of said HIN include events, traces and temporal nodes, wherein each trace is a finite sequence of event type nodes, wherein a temporal node type value is set to be a difference between a current system time and a reference timestamp, divided by a user chosen time granularity parameter;
performing dimension reduction of the HIN by reducing a number of event types of the set of input traces to generate clusters of new event types;
generating a set of meta-paths that connect nodes of a same reduced event type in the application event log;
calculating similarities between process traces using the new event type clusters;
clustering the set of process traces to generate a plurality of disjoint partitions based on the clusters of new event types, wherein each partition is a graph model of the business process in the application event log; and
performing process mining on said graph models to determine whether events in the event log were executed in a correct sequence or to identify bottlenecks in the business process.
9. The computer readable program storage device of claim 8 , the method further comprising repeating said steps of receiving an identification of node types and edge types, generating a set of meta-paths, performing dimension reduction, calculating similarities, and clustering the set of process traces using one of said plurality of disjoint partitions as input.
10. The computer readable program storage device of claim 8 ,
wherein edge types of said HIN are associated with different types of interactions between different node types,
wherein an edge relationship between a trace node type and a temporal node type includes a starts-on edge that indicates a start time of a trace, an ends-on edge that indicates an end time of a trace, and a joined-on edge that indicates a time when a particular resource became available to a trace.
11. The computer readable program storage device of claim 8 , wherein calculating similarities between process traces using the new event type clusters comprises calculating one or more of a structural metapath between new event type clusters and a temporal metapath between new event type clusters.
12. The computer readable program storage device of claim 11 , wherein a structural path similarity between each pair of events type clusters connected by a meta-path P is calculated using
σ
P
(
e
j
,
e
k
)
=
2
×
|
Γ
P
(
e
j
,
e
k
)
|
|
Γ
P
(
e
j
,
e
j
)
|
+
|
Γ
P
(
e
k
,
e
k
)
|
wherein e j and e k represent event-type clusters and Γ P (e j ,e k ) is a set of paths from e j to e k following meta-path P, and |Γ P ( )| represents a cardinality of the set of paths represented by Γ P ( ).
13. The computer readable program storage device of claim 12 , wherein a temporal path similarity between each pair of events type clusters connected by a meta-path P is calculated from SeqPathSim(x, y) of traces x=(a 1 , a 2 , . . . , a m ) and y=(b 1 , b 2 , . . . , b n ), wherein a i , b i are event type clusters, wherein SeqPathSim(x, y) generates a matrix v mn (x, y) defined by
v
m
,
n
(
x
,
y
)
=
{
v
m
-
1
,
n
-
1
(
x
,
y
)
for
a
m
=
b
n
,
min
v
for
a
m
≠
b
n
,
with
:
min
v
=
{
v
m
-
1
,
n
(
x
,
y
)
+
σ
P
EE
(
a
m
,
b
n
)
v
m
,
n
-
1
(
x
,
y
)
+
σ
P
EE
(
a
m
,
b
n
)
v
m
-
1
,
n
-
1
(
x
,
y
)
+
σ
P
ERE
,
P
ETE
(
a
m
,
b
n
)
.
14. The computer readable program storage device of claim 13 , the method further comprising combining meta-path similarities using the following formula:
σ*( x,y )=Σ P i w i ×σ P i ( x,y ),
where σ P i (x, y) is a similarity between two traces x and y via meta-path P i , and w i is a weight associated with meta-path P i .