# Sequential pattern matching in time series data

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?

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
• 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

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

• I am not looking for a complete match. I am looking for a similar match (like a fussy match), complete match is easy it is just a easy for loop. – ccsv Feb 3 '15 at 22:18
• This wasn't explained very clearly in the question. I think you also mean fuzzy matching, not fussy. You need to clarify the degree of 'fuzzyness', i.e. how many insertions, deletions or substitutions you are willing to accept and still call a match. see here – christopherlovell Feb 4 '15 at 10:26
• If you meant fuzzy, update your question. Otherwise I've answered it in its present form – christopherlovell Apr 13 '15 at 13:26