logo

📂알고리즘

곡선에서 꺾인 지점을 탐지하는 방법: 니들 알고리즘

개요

특히 주성분분석 등을 할 때 그렇지만, 데이터과학 전반에서 곡선의 꺾인 지점을 찾을 일은 자주 있으면서도 주관적이기도 하다. 주관적이라서 꼭 나쁜 건 아니지만 이를 위한 대표적인 알고리즘으로 니들 알고리즘Kneedle algorithm이 알려져 있다.

알고리즘 1

alt text

직관적으로 말하자면 커브의 양끝을 잇는 직선을 그어서 눕혀놓고, 그 직선과 커브 사이의 거리가 큰 지점을 찾는다고 보면 된다.

알고리즘: 니들 $\mathrm{Kneedle}(D, S)$
In데이터 포인트 $D = \lbrace (x_i, y_i) \rbrace_{i=1}^{n}$
민감도 $S$
1.$D_s \gets \mathrm{Spline}(D)$# 스무딩. 생략해도 좋다.
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# 눕히는 과정
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$# 로컬 맥시마
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}$# 임계치
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니들포인트의 집합 $K$

설명

니들 알고리즘의 Kneedle은 무릎을 뜻하는 영어 단어 knee와 건초더미에서 바늘을 찾는다는 의미의 “needle in a haystack"을 섞은 말장난에서 유래했다.

코드

짜기 어렵지는 않은데 굳이 짤 것도 없다. 예로써 줄리아에서는 Kneedle.jl 패키지가 있어 가져다 쓰면 된다2.

plot_87

위와 같은 곡선이 주어져 있을 때, 니들 포인트 하나만 찾으면 다음과 같다.

plot_88

두개를 찾으면 다음과 같다.

plot_89

세 개를 찾으면 다음과 같다.

plot_90

전체 코드

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