Ramex: A Sequence Mining Algorithm Using Poly-trees - New Contributions in Information Systems and Technologies - page 138

Prim algorithm finds the minimum or maximum spanning-tree in undirected
graphs. Back-and-Forward heuristic finds the Maximum Weighted Poly-tree by
applying the same technique to directed graphs. The time complexity of the Back-
and-Forward heuristic is equal to the Prim algorithm, which is Θ(E + V. log V) with E
edges and V vertexes.

3.3 Numeric Example

To exemplify the different approaches a numeric example is presented. We are going
to use an event log created by [2] and presented in Table 1.
In Figure 2, a numeric example is shown. Figure 2.a shows the original cyclic
network provided by the first phase of the algorithm. For the second phase two
approaches are possible. Figure 2.b shows the maximum weighted tree that results
from the application of the Forward heuristic. In Figure 2.c the maximum weighted
poly-tree is shown. Note that in vertex 4 the in-degree is two and the edge (4, 5) was
found using the maximum weighted back-vertex mode. Note also, that the sum of the
weights is greater than the previous one, showing that the poly-tree structure always
represents more weighted patterns.

Table 1. Event Log order by frequency

event stream #count event stream #count

14
11
9
8
5
3
2
2
1
1
1
Different applications can use the Forward or Back-and-Forward heuristic. The
Forward heuristic must be chosen if a starting node is given. Node 'a' was chosen in
the example. For instance, most of the web mining problems start in a root node, so
we suggest this first mode [6]. If there is no information about the starting node, the
best edge should be chosen, and the Back-and-Forward heuristic was applied in
previous works [16] and [20].

acdeh
abdeg
adceh
abdeh
acdeg
adceg
adbeh
acdefdbeh
adbeg
acdefbdeh

455
191
177
144
111
82
56
47
38
33

acdefbdeg
acdefdbeg
adcefcdeh
adcefdbeh
adcefbdeg
acdefbdefdbeg
adcefdbeg
adcefbdefbdeg
adcefdbefbdeh
adbefbdefdbeg
adcefdbefcdefdbeg