How to Detect Knee Points in a Curve: Kneedle Algorithm
Overview
Especially when doing things like principal component analysis, but throughout data science in general, finding the knee point of a curve is something that comes up frequently and yet is also subjective. Being subjective is not necessarily bad, but the Kneedle algorithm is known as the representative algorithm for this purpose.
Algorithm1

Intuitively speaking, one draws the straight line connecting both ends of the curve, lays it flat, and then finds the point where the distance between that line and the curve is large.
| Algorithm: Kneedle $\mathrm{Kneedle}(D, S)$ | ||
|---|---|---|
| In | Data points $D = \lbrace (x_i, y_i) \rbrace_{i=1}^{n}$ Sensitivity $S$ | |
| 1. | $D_s \gets \mathrm{Spline}(D)$ | # Smoothing. May be omitted. |
| 2. | for $i = 1, \cdots, n$ do | |
| 3. | $x_{\mathrm{sn}_i} \gets \dfrac{x_{s_i} - \min \lbrace x_s \rbrace}{\max \lbrace x_s \rbrace - \min \lbrace x_s \rbrace}$ | |
| 4. | $y_{\mathrm{sn}_i} \gets \dfrac{y_{s_i} - \min \lbrace y_s \rbrace}{\max \lbrace y_s \rbrace - \min \lbrace y_s \rbrace}$ | |
| 5. | $x_{d_i} \gets x_{\mathrm{sn}_i}$ | |
| 6. | $y_{d_i} \gets y_{\mathrm{sn}_i} - x_{\mathrm{sn}_i}$ | |
| 7. | end for | # Laying the curve flat |
| 8. | $D_{\mathrm{lmx}} \gets \lbrace (x_{d_i}, y_{d_i}) : y_{d_{i-1}} < y_{d_i},\ y_{d_{i+1}} < y_{d_i} \rbrace$ | # Local maxima |
| 9. | $K \gets \emptyset$ | |
| 10. | for $(x_{\mathrm{lmx}_i}, y_{\mathrm{lmx}_i}) \in D_{\mathrm{lmx}}$ do | |
| 11. | $T_{\mathrm{lmx}_i} \gets y_{\mathrm{lmx}_i} - S \cdot \dfrac{\sum_{k=1}^{n-1} \left( x_{\mathrm{sn}_{k+1}} - x_{\mathrm{sn}_k} \right)}{n-1}$ | # Threshold |
| 12. | for $j = i+1, \cdots, n$ do | |
| 13. | if $(x_{d_j}, y_{d_j}) \in D_{\mathrm{lmx}}$ then break | |
| 14. | if $y_{d_j} < T_{\mathrm{lmx}_i}$ then | |
| 15. | $K \gets K \cup \lbrace x_{\mathrm{lmx}_i} \rbrace$ | |
| 16. | break | |
| 17. | end if | |
| 18. | if $y_{d_{j-1}} > y_{d_j} < y_{d_{j+1}}$ then | |
| 19. | $T_{\mathrm{lmx}_i} \gets 0$ | |
| 20. | break | |
| 21. | end if | |
| 22. | end for | |
| 23. | end for | |
| Out | Set of knee points $K$ |
Explanation
The name Kneedle of the Kneedle algorithm comes from a pun mixing the English word knee with the phrase “needle in a haystack,” meaning to search for a needle in a haystack.
Code
It is not hard to write, but there is no need to write it yourself either. For example, in Julia there is the Kneedle.jl package, which you can simply use2.
Given a curve like the one above, finding just one knee point gives the following.
Finding two gives the following.
Finding three gives the following.
Complete Code
using Kneedle
x = 1:20
y = cumsum(1 ./ rand(20))
kr = kneedle(x, y)
knees(kr)
plot(x, y)
vline(plot(x, y), knees(kneedle(x, y, "convex_inc", 1)))
vline(plot(x, y), knees(kneedle(x, y, "convex_inc", 2)))
vline(plot(x, y), knees(kneedle(x, y, "convex_inc", 3)))
Satopaa, V., Albrecht, J., Irwin, D., & Raghavan, B. (2011, June). Finding a" kneedle" in a haystack: Detecting knee points in system behavior. In 2011 31st international conference on distributed computing systems workshops (pp. 166-171). IEEE. https://doi.org/10.1109/ICDCSW.2011.20 ↩︎
