Click here to Skip to main content
14,148,895 members
Rate this:
 
Please Sign up or sign in to vote.
See more:
Consider the graph in this image: Graph.PNG (42.7 KB)

It's a data series whose values (y axis) generally increase over time (x axis) but with quite prominent local maxima and minima along the way. Think of it as a stock price graph on a bad hair day.

At some point the dips down to the local minima aren't as pronounced and the entire graph tilts up. If you draw a line connecting the bottoms of each dip you see a clear point where the graph suddenly goes steeper.

Is there an algorithm that can identify that point reliably?

What I have tried:

I've thought about

1. Smoothing out the data by taking a rolling average and calculating the second derivative. When that hits a threshold we have the point. This seems a bit hit and miss

2. Finding the local minima, constructing a graph from those points, and then doing the second derivative thing.

3. Constructing two trend lines starting from either end of the graph. When the slope of the trend line strays outside a small threshold just continue the line forward and backward using the current slope. Where these two lines cross is the point I want.

I'm guessing this is a solved problem but haven't been able to find anything yet.
Posted
Updated 2-Mar-18 18:00pm
Comments
Patrice T 3-Mar-18 0:14am
   
Shouldn't you cross post in Algorithm discussion ?

1 solution

Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 1

I'd approach it as a constrained optimisation. Take two (intersecting) straight lines. Anchor one at the start point (probably mean of the first "few" points, or an arbitrary stab of the pen), the other similarly at the end. Allow the two slopes to vary (maybe with an extra constraint of (0 < left slope < right slope) and minimise the least squares difference from your raw data. I don't know what package I'd throw it at; maybe something in the Maple class.

Refining the thought bubble somewhat...
Let the intersection point wander round the "lower triangle". (Makes it easier to decide which line to fit a point to); either Monte Carlo it or do a more focused optimisation. Or even do a brute force grid search. I'm guessing the computational effort is in the femto-bitcoin realm.

Cheers,
Peter
   
v2
Comments
Chris Maunder 3-Mar-18 11:30am
   
Interesting. Taking the combined least squares difference of the two lines, one anchored from the start, one at the end, and both terminating at their intersection would certainly give a workable solution. Seems a little brute force, but I'll give it a try.
Peter_in_2780 3-Mar-18 16:50pm
   
While I appreciate mathematical elegance as much as anyone, my engineering mindset takes over when there is a specific problem to be attacked.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
Top Experts
Last 24hrsThis month


Advertise | Privacy | Cookies | Terms of Service
Web02 | 2.8.190518.1 | Last Updated 3 Mar 2018
Copyright © CodeProject, 1999-2019
All Rights Reserved.
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100