Sequential pattern matching in time series data

Question

If I have a time series set such as x=[0,2,5,2,3,1,0] that represents an artifact.

What is the best way to match a similar set as x in a larger data set y?

Answer 1

A few approaches come to mind but this list is far from exhaustive:

• Andreas Brandmaier's permutation distribution clustering is a method rooted in the dissimilarities between time series, formalized as the divergence between their permutation distributions. Personally, I think this is your "best" option

http://cran.r-project.org/web/packages/pdc/index.html

• Eamonn Keogh's SAX (Symbolic Aggregate Approximation) and iSAX routines develop "shape clustering" for time series

http://www.cs.ucr.edu/~eamonn/SAX.htm

• There are approaches based on text compression algorithms that remove the redundancy in a sequence of characters (or numbers), creating a kind of distance or density metric that can be used as inputs to clustering

see, e.g., http://link.springer.com/chapter/10.1007/978-0-387-84816-7_4

• This paper by Rob Hyndman Dimension Reduction for Clustering Time Series Using Global Characteristics, discusses compressing a time series down to a small set of global moments or metrics and clustering on those:

http://www.robjhyndman.com/papers/wang2.pdf

• Chapter 15 in Aggarwal and Reddy's excellent book, Data Clustering, is devoted to a wide range (a laundry list, really) of time-series clustering methods (pps 357-380). The discussion provides excellent background to many of the issues specific to clustering a time series"

http://users.eecs.northwestern.edu/~goce/SomePubs/Similarity-Pubs/Chapter-ClusteringTimeSeries.pdf

Answer 2

You can do this in R. Your time series data is represented by v and the pattern you wish to match by p. Returns match indices.

> v<-c(1,2,3,4,5,6,7,8,9,1,2,3,4,6,7,5,8,1,2,3,4,5)
> p<-"123"
> gregexpr(p,paste(v,collapse = ""))

[[1]]
[1]  1 10 18
attr(,"match.length")
[1] 3 3 3
attr(,"useBytes")
[1] TRUE