pattern recognition for sequence data

There are a lot of data sequences, I am trying to find pairs of sequences that are similar with other.

Trivially, we can define some distance measure, and compare each pair of sequence in terms of this measure. Or even we can solve this problem in a clustering framework. I have two questions, what are the general features to capture the sequence type of data? If I want to solve the problem in the context of either classification or clustering, I have to find the way to characterize the sequence.

A side problem is that, two sequences may be different, but the subsequence of one may be similar to a sub sequence of another one. How to solve this problem in a systematic way? Are there some algorithms/models to handle this kind of problem? Using sliding window approach can make computation exponentially large.

• Afaik. SPM works only after clustering your values. en.wikipedia.org/wiki/Sequential_pattern_mining For example it works on strings or originally it was designed for ecommerce orders to check which items are sold frequently together or after each other. It does not work for example on a temperature time series unless you do something like 10-20°C is one group and 0-10°C is another group. So for that you need to convert your data first. The upper sounds more like sequence clustering, but there is not enough info to decide. en.wikipedia.org/wiki/Sequence_clustering Apr 1, 2021 at 22:12
• Looks like I am 5 years late. Apr 1, 2021 at 22:13

The following article provide a critical comparison of many distance measures available for sequences of categorical data.

Studer, M. and Ritschard, G. (2016), What matters in differences between life trajectories: a comparative review of sequence dissimilarity measures. Journal of the Royal Statistical Society: Series A (Statistics in Society), 179: 481–511. doi: 10.1111/rssa.12125

It is available here in open access: http://onlinelibrary.wiley.com/doi/10.1111/rssa.12125/abstract

One trick I learned from the speech recognition literature is dynamic time warp.

https://en.wikipedia.org/wiki/Dynamic_time_warping

There is an implementation in R,

https://cran.r-project.org/web/packages/dtw/dtw.pdf

• Thank you for the reply. We have been trying DTW. At the same time, I am very interested to see whether there are some features, such as topological pattern of sequence, to characterize a sequence. This is because I want to treat each sequence as a data point in the context of machine learning framework. Jun 14, 2016 at 18:19

There is a huge literature on time series classification and clustering in the data mining community. Many algorithms have been proposed, many similarity metrics invented. But, as pointed out by [1], a large number of these algo are not effective in real world applications. The ref section should get you started on this topic.

[1] Keogh, E., & Kasetty, S. (2003). On the need for time series data mining benchmarks: a survey and empirical demonstration. Data Mining and knowledge discovery, 7(4), 349-371.