# Finding occurrences of specific patterns in time series

I have to locate occurrences of Cyllinder, Bell and Funnel patterns in univariate time series $X$ of gamma-ray sensoring.

This is a specific case of the general CBF synthetic problem found in a few works [1]. For each match, I have to show the class of the pattern (one of the three above), the start position $s$ and the end position $e$.

Let $X = x_1, x_2, ..., x_n$ be a time series of length $n$, then I need to determine the list of occurrences $O = [<class_1, s_1, e_1>, <class_2, s_2, e_2>, ..., <class_m, s_m, e_m>]$, where $m$ is the total number of patterns found in $X$.

Also, I can't make any assumptions on the amplitude nor the length of the patterns. It's even possible to have patterns inside patterns. It deppends solely on the scale of the analysis.

Here are examples of each class:

Cyllinder - A sudden drop, followed by a plateau, followed by a sudden rise

Bell - A smooth drop, followed by a sudden rise

Funnel - A sudden drop, followed by a smooth rise (corrected)

I thought of applying 1-Nearest-Neighbor with Dynamic Time Warping (1NN-DTW)[2] on sliding windows of different sizes, one size at a time representing the scales of interest.

The problem is that I only have positive samples selected manually by specialists. With this approach all the windows extracted from the sequence $X$ are classified as one of the 3 classes (the class of the nearest neighbor). That is not, of course, the correct answer to my problem.

I also thought about the following approaches:

1- determine a per-class minimum threshold for the DTW distance. If the nearest neighbor distance to the window is greater than its class threshold, the windows is considered to be a non-pattern.

This solution doesn't seem to be possible since DTW is not a metric, but an alignment cost. It does not make sense to compare the alignment cost between sequences $<A,B>$ and sequences $<C,D>$.

2- extract a feature vector or discrete wavelet transform signature of all samples and train a model such as support vector machine or multi-layer perceptron to classify a sample as Cylinder, Bell or Funnel.

This is my next shot. Haven't tried it yet, but since I only have positive examples, I need to find, again, some way to discard weak positive responses from the model, if that makes any sense. EDIT: I recently found a technique called One Class SVM. I could fit a 1-class SVM for each class and use them to find wether a subsequence is a Cyllinder, Bell, Funnel or neither.

3- hidden markov model to fit and predict occurences of the classes.

Don't even know how to start this alternative yet. Have to learn a lot about it.

Can you guys tell me if I am going in the right direction?

Can you suggest more promising approaches?

• In regard to using DTW, I hope that you might find some of the resources, linked in my related answer, interesting and useful. – Aleksandr Blekh Jan 15 '15 at 12:42
• So far options 1 and 2 did not work out well. Preparing myself to take road number 3. – Marcio Carvalho Feb 20 '15 at 13:22
• From the competent nature of your question, it is likely that you have already read this paper, in any case adding here as a source for future visitors. A time series classification task: 1- Classification Using Time Series Features, 2- Classification Using Similarity metrics (DTW, Gaussian radial basis kernel), 3- Hidden Markov Models. – Zhubarb Mar 4 '15 at 12:59

I think

"1- determine a per-class minimum threshold for the DTW distance. If the nearest neighbor distance to the window is greater than its class threshold, the windows is considered to be a non-pattern."

Is the right idea. It is what is essentially done in [a]

You can find VERY fast DTW sub-sequence code here http://www.cs.ucr.edu/~eamonn/UCRsuite.html

For what is it worth, yes, DTW is only a measure, not a metric. But...

For constrained DTW, it is 'almost' a metric. And you SHOULD use constrained DTW.

The non-metric property is not an issure here in any case.

eamonn

• Prof. Keogh, thanks for the pointed article. I tried a similar approach for DTW rejection threshold calculation. I determined the DTW centroid for each class and compared the intra-class distances to the inter-class distances. But the distance histograms sent me mixed messages, since the 3 centroid histograms presented considerable intersection between intra and inter-class distances. I used the normalized DTW distance. In your cited article, you chose the Uniform Scaling distance instead of Euclidean or DTW. – Marcio Carvalho Jan 16 '15 at 20:01
• Is Uniform Scaling better than or as good as DTW to deal with time shift of the sequences shapes? Is Uniform Scaling replaceable by DTW in your rejection threshold determination? – Marcio Carvalho Jan 16 '15 at 20:02

I could suggest an alternative: Slutsky's random cycles. He showed that random processes may have occasional periodicities, or cycles. It appears as if there's some kind of a periodic pattern when in fact it's simply a random process with moving averages. It's very interesting approach with applications in economics.