Compute the 'elbow' for a curve automatically and mathematically

One example for curve is shown as below. The elbow point might be x=3 or 4. How to compute the elbo开发者_C百科w for a curve automatically and mathematically?

I created a Python package that attempts to implement the Kneedle algorithm.

To recreate the function above and detect the point of maximum curvature:

x = range(1,21)
y = [0.065, 0.039, 0.030, 0.024, 0.023, 0.022, 0.019, 0.0185, 0.0187,
     0.016, 0.015, 0.016, 0.0135, 0.0130, 0.0125, 0.0120, 0.0117, 0.0115, 0.0112, 0.013]

kn = KneeLocator(
    x,
    y,
    curve='convex',
    direction='decreasing',
    interp_method='interp1d',
)

print(kn.knee)
7

import matplotlib.pyplot as plt
plt.xlabel('x')
plt.ylabel('f(x)')
plt.xticks(range(1,21))
plt.plot(x, y, 'bx-')
plt.vlines(kn.knee, plt.ylim()[0], plt.ylim()[1], linestyles='dashed')

update
Kneed has an improved spline fitting method for handling local minima, use interp_method='polynomial'.

kn = KneeLocator(
    x,
    y,
    curve='convex',
    direction='decreasing',
    interp_method='polynomial',
)

print(kn.knee)
4

And the new plot:

plt.xlabel('x')
plt.ylabel('f(x)')
plt.xticks(range(1,21))
plt.plot(x, y, 'bx-')
plt.vlines(kn.knee, plt.ylim()[0], plt.ylim()[1], linestyles='dashed')

You might want to look for the point with the maximum absolute second derivative which, for a set of discrete points x[i] as you have there, can be approximated with a central difference:

secondDerivative[i] = x[i+1] + x[i-1] - 2 * x[i]

As noted above, what you really want is the point with maximum curvature, but the second derivative will do, and this central difference is a good proxy for the second derivative.

Functions like this one are usually called L-curves for their shapes. They appear when solving ill-posed problems through regularization.

The 'elbow'-point is the point on the curve with the maximum absolute second derivative.

What you really want is the point with maximum curvature. When the slope is much smaller than 1, this can be approximated by the second derivative (as @ebo points out), but this is not always the case.