1
$\begingroup$

Here is my target, given a set of consecutive discrete 1-d data points within a window. I want to know whether there are good algorithms to detect certain typical shapes of the signal in the window. Including:

  1. A positive step
  2. A negative step
  3. An upward line
  4. A downward line
  5. A hill shape
  6. A bowl shape

The size of the given window could be of any length. And the data is from financial markets so it could be highly random. I wonder if there are good methods to detect whether the above typical shapes exist in the window, which could of course be given by a probability for each shape. I don't need very concrete descriptions of each algorithm, just need to get a direction for my further research.

$\endgroup$
0
$\begingroup$
  • A first comment is that the situation you describe can be mixed. A bowl shape can happen "during" a wide upward line. This questions the scale of the shape with respect to the size of the window.

  • A second comment is that your situations don't describe all possible situations. There might be at least a last "trash" or "underdetermined" situation (every other possibility).

  • A third comment is that each pair sounds relatively symmetrical, so with careful examination, it is possible to reduce, or nest, the sets of possiblities.

I would evoke two far-away types of techniques.

  1. Context-based: you define contexts, a set of mutually exclusive behaviors that covers all possibilities. For instance, you can define $S_-/S_+$, $L_-/L_+$, $C_-/C_+$ and $O$ for steps (positive/negative), line (upward, downward), circle (up and down) and other. Then define a metric (based on gradient, laplacian, possibly relative to scale) that provides the best match in a window. From the set of metric values, you can get a probability of looking like a context. We somehow used a similar approach (but not going to scales) in CHOPtrey: contextual online polynomial extrapolation for enhanced multi-core co-simulation of complex systems. This approach was chosen because of real-time constraints and a lack of knowledge in the generating cybersystems

Choptrey: pattern representation of functional contexts

  1. Learning-based: the current time is concentrated to deep-learning. So if you can build a database of trained labels (by experts) you can hope to achieve state of the art performance with neural networks and their avatars. Some recent advances seem to be scale-invariant and noise robust.

Between the above options, many intermediates can be found.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your insights. I also realise that the six patterns I mentioned could not represent all possibilities. I just hope the algorithm could recognize it when an obvious shape among them appears in the window, since in many cases we could recognize a shape just by our eyes. The deep learning method might generate the most desirable results for me but I am doing this out of my own interest, so I don't have enough resource and energy to implement it. I will focus more on some simple rule based methods first. Anyway, thanks again for your answer! $\endgroup$ – Adam Mar 20 at 3:14
  • $\begingroup$ Shapes are not obviois things. They depend on the eue of the beholder. Shape retrieval, shape matching are still active fields of research $\endgroup$ – Laurent Duval Mar 20 at 11:26
  • $\begingroup$ Exactly! Although at first I think it might be a simple problem, I find it very difficult when I really try to solve it. Could you recommend me several academic articles for some general introductions about this field? $\endgroup$ – Adam Mar 20 at 21:41
0
$\begingroup$

Do you know Calculus?

All those shapes correspond to bounded values over an interval of the function or its first and second derivatives.

There are many ways to approximate derivatives in discrete sequences.

You can design a metric for each of your conditions based on the derivatives, then evaluate those metrics on a sliding basis.

1) A step occurs when the first derivative is relatively close to zero, then has a spike, then returns to zero.

2) Same as 1, opposite sign.

3) An upward line exists when the first derivative is bound near a positive value and the second derivative is bound near zero.

4) Same as 3, opposite sign

5) A hill (approximated by a parabola) occurs when the second derivative is bound near a negative value.

6) Same as 5, opposite sign

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your response. My data comes from financial market which is extremely random. These derivative based methods might work well for smooth ideal signals theoritically, but they generate unsatisified results on my data set. For example, if I use y[n]-y[n-1] to estimate first order derivative, what I got before is a signal similar to white noise. $\endgroup$ – Adam Mar 20 at 21:37
  • $\begingroup$ It's more proper to say the data is noisy. Not all noise is random, nor well behaved. You are dipping your toe into a large pool of solutions, each with its own characteristics. If the ends aren't important (e.g. you're not trying real time prediction) my favorite technique is documented here dsprelated.com/showarticle/754.php. I use a factor of 0.5 with repeated smooths and differs. I can be implemented especially efficiently with integers as it devolves to a sum and a shift. Happy swimming. $\endgroup$ – Cedron Dawg Mar 21 at 0:35
  • $\begingroup$ @Adam Forgot the "at" tag, so here it is. $\endgroup$ – Cedron Dawg Mar 21 at 0:43
  • $\begingroup$ Thank you! I will read through your recommended material later. $\endgroup$ – Adam Mar 21 at 1:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.