Sensitivity Parameter (S) does not work in polynomial fit?

[Irfanwustl]

From your README.md example, I was playing with your excellent algorithm kneed. However, it seems for the polynomial fit example, there is no effect of S parameter. Specifically, no difference between

kneedle = KneeLocator(x, y, S=1, curve='convex', direction='decreasing', interp_method='polynomial')

and

kneedle = KneeLocator(x, y, S=28.0, curve='convex', direction='decreasing', interp_method='polynomial')

Will you please have a look?

[arvkevi]

Hi, @Irfanwustl thank you for checking out the repo! I'm sorry it has taken so long to respond.

Depending on the type of curve, changing the S parameter will not always result in different knee points. In the example you are referring to, the polynomial fit is a significant factor.

When you change the fit of the line to 'interp1d', there are several local maxima (10, to be exact), giving the kneedle algorithm more opportunities to find a local knee point. When you change the line fit to 'polynomial', there is only one local maximum found. Changing S in this situation does not affect the x value of the knee point. The only effect S has here is in determining at which iteration the algorithm declares that local maximum (x value) the knee.

To illustrate my point, let's compare the two fit methods (interp_method) in your example. I frequently refer to the "difference curve" below. If you are unfamiliar with the algorithm, I strongly encourage you to read the paper for a better understanding before following along below.

from kneed import KneeLocator

x = list(range(90))
y = [
    7304, 6978, 6666, 6463, 6326, 6048, 6032, 5762, 5742,
    5398, 5256, 5226, 5001, 4941, 4854, 4734, 4558, 4491,
    4411, 4333, 4234, 4139, 4056, 4022, 3867, 3808, 3745,
    3692, 3645, 3618, 3574, 3504, 3452, 3401, 3382, 3340,
    3301, 3247, 3190, 3179, 3154, 3089, 3045, 2988, 2993,
    2941, 2875, 2866, 2834, 2785, 2759, 2763, 2720, 2660,
    2690, 2635, 2632, 2574, 2555, 2545, 2513, 2491, 2496,
    2466, 2442, 2420, 2381, 2388, 2340, 2335, 2318, 2319,
    2308, 2262, 2235, 2259, 2221, 2202, 2184, 2170, 2160,
    2127, 2134, 2101, 2101, 2066, 2074, 2063, 2048, 2031
]

Start with the bumpy fit line, using 'interp1d':

kl = KneeLocator(x, y, curve='convex', direction='decreasing', S=1.0, interp_method='interp1d')

There are 10 local maxima in the line (because it's bumpy):

print(kl.y_difference_maxima)
array([0.1820148 , 0.21378146, 0.27603415, 0.36877713, 0.38214819,
       0.38281302, 0.37233777, 0.33868105, 0.32308538, 0.28520745])

Using this fit method, S will play a significant role in determining the knee point. Sis used to set the threshold for determining what y_difference value the line needs to go below, before calling the point a knee point. Check out the thresholds when S=1.0:

print(kl.Tmx)
array([0.17077885, 0.20254551, 0.2647982 , 0.35754117, 0.37091224,
       0.37157706, 0.36110182, 0.32744509, 0.31184943, 0.27397149])

Now, let's increase S to 3.0 and see what effect that has on the algorithm:

kl = KneeLocator(x, y, curve='convex', direction='decreasing', S=3.0, interp_method='interp1d')

It's still the same line, because we didn't change the fit method. S has no effect on the local maxima:

print(kl.y_difference_maxima)
array([0.1820148 , 0.21378146, 0.27603415, 0.36877713, 0.38214819,
       0.38281302, 0.37233777, 0.33868105, 0.32308538, 0.28520745])

Notice that the local maxima haven't changed. It's only the threshold values where you can see the effect of increasing S:

print(kl.Tmx)
array([0.14830694, 0.1800736 , 0.24232629, 0.33506926, 0.34844033,
       0.34910515, 0.33862991, 0.30497318, 0.28937752, 0.25149958])

The thresholds for calling each local maxima a knee point have changed. Compared to the S=1.0 thresholds, the difference curve now has to dip a bit lower before the algorithm will call a knee point. Meaning, it will take more consecutive "flat" points to call a knee.

---

Understanding why S doesn't affect the knee in the polynomial fit will make more sense now. Using the same data, change the interp_method to 'polynomial':

kl = KneeLocator(x, y, curve='convex', direction='decreasing', S=1.0, interp_method='polynomial')

Check out the local maxima:

print(kl.y_difference_maxima)
array([0.36906561])

There's only one local maximum, meaning, there is only ever one knee point that the algorithm could ever call. The only thing that will change is how soon the algorithm will call the local maximum a knee. Look at the thresholds:

print(kl.Tmx)
array([0.35782966])

At S=1.0, the threshold is not much lower than the local maximum, meaning the algorithm would call this local maximum the knee point fairly quickly. For completeness, let's finish up by looking at 'polynomial' fit with S=3.0:

kl = KneeLocator(x, y, curve='convex', direction='decreasing', S=3.0, interp_method='polynomial')

Remember, there will only be one local maximum:

print(kl.y_difference_maxima)
array([0.36906561])

But the threshold will decrease, meaning it will take more iterations to call this local maximum the knee point:

print(kl.Tmx)
array([0.33535775])

Hopefully, this answers your question and gives you some insight into how the algorithm works.
This gives me a good idea for a feature. It would be nice to know at which x point in the curve did the algorithm find the knee.