Sequential pattern mining on single sequence

Question

Can someone give me a hint about a good approach to find a frequent patterns in a single sequence.

For example there is the single sequence

3 6 1 2 7 3 8 9 7 2 2 0 2 7 2 8 4 8 9 7 2 4 1 0 3 2 7 2 0 3 8 9 7 2 0

I am looking for a method that can detect frequent patterns in this ordered sequence:

3 6 1 [2 7] 3 [8 9 7 2] 2 0 [2 7] 2 8 4 [8 9 7 2] 4 1 0 3 [2 7] 2 0 3 [8 9 7 2] 0

Also other information would be interesting like:

• What is the probability that 7 comes after 2
• When each number has a timestamp assigned to it, what is the estimated time interval that 7 occurs after 2

The sequential pattern mining methods I found require multiple sequences, but I have one large sequence where I want to detect regularities.

Thanks for any help!

Answer 1

Calculate a histogram of N-grams and threshold at an appropriate level. In Python:

from scipy.stats import itemfreq
s = '36127389722027284897241032720389720'
N = 2 # bi-grams
grams = [s[i:i+N] for i in xrange(len(s)-N)]
print itemfreq(grams)

The N-gram calculation (lines three and four) are from this answer.

The example output is

[['02' '1']
 ['03' '2']
 ['10' '1']
 ['12' '1']
 ['20' '2']
 ['22' '1']
 ['24' '1']
 ['27' '3']
 ['28' '1']
 ['32' '1']
 ['36' '1']
 ['38' '2']
 ['41' '1']
 ['48' '1']
 ['61' '1']
 ['72' '5']
 ['73' '1']
 ['84' '1']
 ['89' '3']
 ['97' '3']]

So 72 is the most frequent two-digit subsequence in your example, occurring a total of five times. You can run the code for all $N$ you are interested about.

Answer 2

I think you can use the Apriori algorithm. Count the number each single element occurs in the sequence. If the count is greater than some threshold $\varepsilon$ then the item is frequent. Then count the number of pairs of frequent items. Continue with the number of frequent $4$-tuples, etc.

Answer 3

You could use something like the following. As far as I know SPADE uses something similar too for multiple sequences.

36127389722027284897241032720389720

First you need to gather the positions of every item in your sequence.

length: 1

{
    0: [11,23,28,34], //4
    1: [2,22], //2
    2: [3,9,10,12,14,20,25,27,33], //9
    3: [0,5,24,29], //4
    4: [16,21], //2
    5: [], //0
    6: [1], //1
    7: [4,8,13,19,26,32], //6
    8: [6,15,17,30], //4
    9: [7,18,31] //3
}

Then check the support of these items against the minimum support you choose for frequent sequences.

min_sup: 3

{
    0: [11,23,28,34], //4
    2: [3,9,10,12,14,20,25,27,33], //9
    3: [0,5,24,29], //4
    7: [4,8,13,19,26,32], //6
    8: [6,15,17,30], //4
    9: [7,18,31] //3
}

In your case you need to find the items with consecutive positions. You can use wildcards too, but in that case the position difference will be more than 1 and you will find a lot more candidates.

length: 2

{
    00: [], //0
    02: [[11,12]], //1
    03: [[23,24],[28,29]], //2
    07: [], //0
    08: [], //0
    09: [], //0
    20: [[33,34]], //1
    22: [[9,10]], //1
    23: [], //0
    27: [[3,4],[12,13],[25,26]], //3
    28: [], //0
    29: [], //0
    30: [], //0
    32: [[24,25]], //1
    33: [], //0
    37: [], //0
    38: [[5,6],[29,30]], //2
    39: [], //0
    70: [], //0
    72: [[8,9],[13,14],[19,20],[26,27],[32,33]], //5
    73: [[4,5]], //1
    77: [], //0
    78: [], //0
    79: [], //0
    80: [], //0
    82: [], //0
    83: [], //0
    87: [], //0
    88: [], //0
    89: [[6,7],[17,18],[30,31]], //3
    90: [], //0
    92: [], //0
    93: [], //0
    97: [[7,8],[18,19],[31,32]], //3
    98: [], //0
    99: [] //0
}

min_sup: 3

{
    27: [[3,4],[12,13],[25,26]], //3
    72: [[8,9],[13,14],[19,20],[26,27],[32,33]], //5
    89: [[6,7],[17,18],[30,31]], //3
    97: [[7,8],[18,19],[31,32]], //3
}

You can try to combine the upper sequences based on the ending, or you can just check the positions.

length: 3

{
    272: [[12,13,14],[25,26,27]], //2
    727: [], //0
    897: [[6,7,8],[17,18,19],[30,31,32]], //3
    972: [[7,8,9],[18,19,20],[31,32,33]] //3
}

min_sup: 3

{
    897: [[6,7,8],[17,18,19],[30,31,32]], //3
    972: [[7,8,9],[18,19,20],[31,32,33]] //3
}

length: 4

{
    8972: [[6,7,8,9],[17,18,19,20],[30,31,32,33]] //3
}

min_sup: 3

{
    8972: [[6,7,8,9],[17,18,19,20],[30,31,32,33]] //3
}

There is only one pattern and you cannot combine it with itself, so the mining is complete.

{
    27: [[3,4],[12,13],[25,26]], //3
    72: [[8,9],[13,14],[19,20],[26,27],[32,33]], //5
    89: [[6,7],[17,18],[30,31]], //3
    97: [[7,8],[18,19],[31,32]], //3
    897: [[6,7,8],[17,18,19],[30,31,32]], //3
    972: [[7,8,9],[18,19,20],[31,32,33]] //3
    8972: [[6,7,8,9],[17,18,19,20],[30,31,32,33]] //3
}

If we exclude the sub-patterns of 8972.

{
    27: [[3,4],[12,13],[25,26]], //3
    72: [[13,14],[26,27]], //2
    8972: [[6,7,8,9],[17,18,19,20],[30,31,32,33]] //3
}

min_sup: 3

{
    27: [[3,4],[12,13],[25,26]], //3
    8972: [[6,7,8,9],[17,18,19,20],[30,31,32,33]] //3
}

I think it is the same as the patterns you have found.

361[27]3[8972]20[27]284[8972]4103[27]203[8972]0

Another option to keep the 72 too, because it occurs 3 times as a sub-sequence of 8972 and 2 other times independently from 8972. I think this should depend on whether you allow overlapping.

361[27]3[89(72)]202(72)84[89(72)]4103[2(7]2)03[89(72)]0

Note: I don't think sequential pattern mining is considered machine learning.

Answer 4

When it comes to a single sequence, episode mining fits the need. When you want to know the probability of one element following another, sequential association analysis, such as lag-sequential analysis (Bakeman & Gottman, 1997: Observing interaction: An introduction to sequential analysis) serves the need.