4
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – inf3rno
    Commented Apr 1, 2021 at 22:12
  • $\begingroup$ Looks like I am 5 years late. $\endgroup$
    – inf3rno
    Commented Apr 1, 2021 at 22:13

3 Answers 3

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – user785099
    Commented Jun 14, 2016 at 18:19
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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