2
$\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.

$\endgroup$
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

$\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

$\endgroup$
  • $\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 Jun 14 '16 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.

$\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.