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?
Thanks in advance.
Best Answer
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
[a] http://www.cs.ucr.edu/~eamonn/SDM_RealisticTSClassifcation_cameraReady.pdf