logo

📂Algorithm

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

alt text

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)$
InData 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
OutSet 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.

plot_87

Given a curve like the one above, finding just one knee point gives the following.

plot_88

Finding two gives the following.

plot_89

Finding three gives the following.

plot_90

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)))

  1. 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 ↩︎

  2. https://github.com/70Gage70/Kneedle.jl ↩︎