8
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the hint, that's a good starting point. But is there also some approach that allows also the prediction of the next element based on probabilities, etc? $\endgroup$ – MikeHuber May 23 '15 at 15:25
  • 1
    $\begingroup$ That is a much more difficult problem (you should maybe ask it in a separate question). One idea that comes into mind is that if you find that some long sequence $S$ appears very frequently, you can use that for some predictions. For example, if you find that 8972 occurs very often, you know that 72 is going to be preceded by 89. $\endgroup$ – mmh May 23 '15 at 17:49
  • 1
    $\begingroup$ Also, I wanted to ask what do your sequences represent? $\endgroup$ – mmh May 23 '15 at 17:57
  • $\begingroup$ One application I want to use it for is to analyse errors or alarms I find in a log file. One interesting thing is to find frequent error-patterns, but also predicting an future error based on the past sequence would be interesting. Therefore i was looking for some help which approach/method can be used for that kind of problems. $\endgroup$ – MikeHuber May 23 '15 at 18:22
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.