What is the best way to detect repetition in xyz data for purposes of splitting data?

I'll use this picture to explain

What I want to do is define some patterns as trained patterns. Then given data I want to be able to determine if the pattern exists in the dataset, and if it does exist determine how many times it occurs. I have had success recognizing patterns with K-nearest neighbors but the data containing the pattern already has to be pulled out of a dataset. So for example if trying to recognize blue the data needs to look like this:

Which would suggest that I need to be able to split up data based on the patterns and then recognize with KNN. I'm also open to different methods of pattern recognition but right now my primary problem is finding a good way to split up the data

• I don't really understand your situation or what you're trying to do. Can you make this clearer somehow? Could you paste in a small example? – gung - Reinstate Monica Jun 22 '16 at 22:42
• @gung I updated my post does that make more sense? – Mike Sallese Jun 23 '16 at 0:52
• I don't get, among other things, the "splitting" of the data. I still think this is too broad. If you just want to know how to fit something like the drawn pattern, why not use $\sin(x) +\cos(x)$? – gung - Reinstate Monica Jun 23 '16 at 1:11
• @gung I want an algorithm that will tell me how many humps are in a given dataset of y values. If there were 6 humps vs 4 humps KNN would think they are different patterns. I want to be able to recognize any discrete number of humps. I assume that would need splitting of data to determine if any humps were present but doing so could be computationally expensive if having to scan through a large data set many times and may overcount – Mike Sallese Jun 23 '16 at 1:39
• @gung From a high level I want to be able to take in data (from an accelerometer which is just xyz values) and train certain patterns. Then I want to be able take in more data (hypothetically in real time but for now we'll ignore that) and classify what the data is. What I mean by this classification is that I want to be able to determine: 1.) whether one of the trained patterns has occurred 2.) if it has occurred, how many times did it occur – Mike Sallese Jun 23 '16 at 2:03

It sounds like you have a set of known patterns and want to find places in your signal where these patterns occur. A typical way of doing this is using the cross correlation. In this approach, you'd compute the cross correlation of your pattern with the signal. You can think of this as repeatedly shifting the pattern by some lag to align it with a different portion of the signal, then taking the dot product of the pattern and the local portion of the signal. This gives a measure of the similarity between the pattern and the local signal at each lag. When the signal matches the pattern, this will manifest as a peak in the cross correlation.

Different variants of the cross correlation exist. For example, some versions locally scale and/or normalize the signals. This can be useful if you want your comparison to be shift/scale invariant (e.g. you want the shape of the signal to be the same, but don't care about the actual magnitude; in the case of detecting accelerometer patterns, this might correspond to performing the same motion but more or less vigorously).

The cross correlation will naturally fluctate, reflecting varying degrees of similarity between the pattern and signal. So, the question is how to distinguish peaks that represent a 'true match' from those that reflect partial similarity. You'll have to define this based on the variant of cross correlation you use. For example, if the pattern exactly matches the signal at some offset, the magnitude of the unnormalized cross correlation will equal the squared $l_2$ norm of the pattern (i.e. the dot product of the pattern with itself). Some normalized versions of the cross correlation will have maximum amplitude 1. Another thing you'd need to define is some tolerance, to account for noise in the signal (you probably don't want to require an exact match).

Another possibility is that you want to use some other measure of similarity (e.g. the euclidean distance). In this case, you could use peaks in the cross correlation to identify candidate matches, then check them using whatever distance metric/similarity function you like.

One of main the reasons to use cross correlation is that it's very computationally efficient. For large signals, you can gain even more speed by computing it in the Fourier domain, using FFTs. Many packages/libraries are available to do this.

The cross correlation approach (and FFT acceleration) will also work for higher dimensional signals (e.g. images).

• cross correlation paired with similarity of some sort sounds like exactly what I'm looking for. I'm not familiar with cross correlation so I'm going to study up on this and try it out before I accept your answer. In terms of defining the known/trained patterns, what method would you recommend to do so? In other words, would leaving the known patterns as accelerometer values work or should I transform them somehow to be more informative when using cross correlation? – Mike Sallese Jun 25 '16 at 17:12
• If you know that only certain frequency components are relevant, then filtering might be beneficial (to remove noise and/or irrelevant features). This could be a lowpass/bandpass filter, or something like a Kalman filter. Alternatively, some form of smoothing could be used to reduce noise (e.g. Savitzky-Golay filtering). This preprocessing would be applied to the signal from which patterns are extracted, and to the signal that will be compared to the patterns. Otherwise, if the signal is clean, then using raw values could work. – user20160 Jun 25 '16 at 17:39
• ok thank you so much. I'm gonna try out what you've suggested so far – Mike Sallese Jun 25 '16 at 18:37

If you know the patterns ahead of time, you can just make a hash table of the patterns and pattern detection is just a matter of hashing segments of the input signal and looking for collisions. Conventional hashing will only work for exact, noise-free input signals. Locality-sensitive hashing can be made insensitive to small variations in input signal by checking that the incoming signal is sufficiently near the target.

This is exactly the definition of time series motifs

Here is a tutorial on the topic http://www.cs.unm.edu/~mueen/Tutorial/ICDMTutorial3.ppt

eamonn

If the activity is sinusoidal within a specific frequency band you could use the frequency to classify patterns. To achieve this you perform a fast-fourier transform (FFT) on the data and search for global maxima in the resulting power spectrum. Using different band-pass filters you can target specific frequency bands. Alternatively, you need to search for local maxima in the whole-band power spectrum. Just be advised that this method will not take phase into account.

If the activity is characterized by an irregular but predictable pattern, you could search for how many times the signal flips (the amplitude changes direction) and set up different maxima and minima criteria or time range criteria (e.g. a positive flip followed by a negative flip at at least -0.5 within 300 ms).

If you baseline correct the data - for the event at 0 ms - relative to some prior point (e.g. -100 ms to 0 ms) you can count how many times zero was crossed to get the length of the pattern. The baseline correction takes the global maximum and minimum of the baseline range and centers the signal on $$\frac{max-min}{2}$$

I agree with @user20160 that cross correlation (CC) will most likely be a valid and fast solution to your problem (in combination with scaling of your reference pattern + selecting the window position where correlation peaks occur).

What I want to point out is: if you run into problems because the pattern you search for is irregularly stretched or condensed in your time series, consider using Dynamic Time Warping (DTW) instead of CC. DTW can compensate for any stretching or condensing of your pattern using its warping property - which will be helpful in such cases.