How do I find the point in a graph where the slope suddenly increases?

Question

0.00/5 (No votes)

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 2-Mar-18 17:00pm

Chris Maunder772.7K

Updated 2-Mar-18 18:00pm

Add a Solution

Comments

Patrice T 3-Mar-18 0:14am

Shouldn't you cross post in Algorithm discussion ?

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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

Peter_in_2780 · Answer 1 · 2018-03-02T18:01:00

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