Find repeating patterns in data

Question

I have database of sequential events for multiple animals. The events are represented by integers so it looks something like:

Animal A: [1,6,4,2,5,7,8] 
Animal B: [1,6,5,4,1,6,7]
Animal C: [5,4,2,1,6,4,3]

I can manually see that for each event 6 event 1 first happens. And event 4 happens quickly after a 1,6 combination. But these are easy to spot in such a small dataset, the real lists are 10000+ events per animal. Is there a way to use an algorithm or machine learning to search for these kinds of patterns?

Answer 1

There are several ways you could approach this. Ultimately it would depend on what your data represents as to which method is best suited. Some options include:

sequence mining:

• n-gram frequency. You could apply a tf-idf tokeniser to your data to generate matrices for different size $n1,n2,...nx$ grams. This would yield the prevalence of set combinations in your data including [1,6] and [1,6,4].
• set similarity. The above ngram approach assumes that the patterns are sets. Where [1,6,4] and [1,6,5,4] are distinct. You could then apply some similarity score to find similar sets such as jaccard within and across each animal.

Then compare each animal based on some measure of the number and similarity of sets identified.

correlation and time series:

This wouldn’t find the unique patterns and sequences per se, but would yield information for sequence similarity.

• sliding window. You could pass different size sliding windows over the series to compute rolling means and sums. Then apply correlation, covariance, and time series analysis to determine the similarity of each animal as a series. Again it depends what your numeric data values represent as to wether this is applicable.

Answer 2

I think this problem could be represented as a Markov Chain.

Maybe a Markov model (or Markov Random Fields) could be used to estimate the probabilities. Normally it's easier than with the more standard Hidden Markov Model since there is no hidden state.

My suggestion would be to estimate the probabilities of the model (parameters) from the data, then it should be easier to discover the patterns based on these probabilities.