770 P. Fournier-Viger, R. Nkambou, and E.M. Nguifo 

FOR each pair (t, i) found newPrefix := Concatenate(prefix, (t, i)). IF newPrefix satisfies C3 and C4 Add newPrefix to R. IF (size of ISDB|newPrefix) >= minsup algoProjection(ISDB|newPrefix, R, minsup)
C3,C4). 

To illustrate the Hirate-Yamana algorithm, let's consider applying it to the database ISDB depicted in figure 3, with a *minsup* of 50 % and the constraint C2 equals to 2 time units. In the first part of *algoHirate*, frequent actions a, b and c are found. As a result <(0,a)>, <(0,b)> and <(0,c)> are added to R, the set of sequences found. Then, for a, b and c, the projected database ISDB|(0,a), ISDB|(0,b) and ISDB|(0,c) are created, respectively. For each of these databases, the algorithm *algoProjection* is executed. *algoProjection* first finds all frequent pairs (timestamp, item) that verify the constraints C1, C2 and *minsup*. For example, for ISDB| (0,a), the frequent pair (0,b) and (2,a) are found. These pairs are concatenated to (0,a) to obtain sequences <(0,a), (0,b)> and <(0,a), (2,a)>, respectively. Because these sequences respect C3 and C4, they are added to the set R of sequences found. Then, the projected database ISDB|<(0,a), (0,b)> and ISDB|<(0,a), (2,a)> are calculated. Because these databases contain more than *minsup* sequences, *algoProjection* is executed again. After completing the execution of the algorithm, the set of sequences R contains <(0,a)>, <(0,a), 
(0,b)>, <(0,a), (2,a)>, <(0,b)> and <(0,c)>. 

![0_image_0.png](0_image_0.png)

## 5 Extending Spm With Automatic Clustering Of Valued Actions

A second limitation that we encountered when we applied PrefixSpan to extract a problem space is that it relies on a finite set of actions. As a consequence, if some actions were designed to have parameters or values, they have to be defined as one or more distinct actions. For example, in our first experiment in RomanTutor, we categorized the joint rotations as small, medium and big, which correspond respectively to 0 